Per-Key Rate Limiting for Agent Tool Calls: Stop One User From Breaking Everything

xception with backoff metadata when limits are breached. 4. In-Process State: This implementation operates within a single process. It is optimized for low-latency, high-throughput scenarios where distributed consistency is not required. For multi-node deployments, the state must be externalized to a shared store like Redis.

Implementation

The following TypeScript/Python-style implementation demonstrates a production-ready TenantRateGuard. It includes proactive memory management to address idle key accumulation, a common oversight in simpler implementations.

import time
import threading
from collections import deque
from contextlib import contextmanager
from typing import Dict, Any, Optional

class TenantQuotaExceeded(Exception):
    """Raised when a tenant exceeds their allocated rate limit."""
    def __init__(self, retry_delay: float):
        self.retry_delay = retry_delay
        super().__init__(f"Quota exceeded. Retry after {retry_delay:.2f}s")

class TenantRateGuard:
    """
    Sliding-window rate limiter for multi-tenant agent tools.
    Enforces per-key limits with thread safety and memory management.
    """
    
    def __init__(self, max_requests: int, duration_seconds: float):
        if max_requests <= 0:
            raise ValueError("max_requests must be positive")
        if duration_seconds <= 0:
            raise ValueError("duration_seconds must be positive")
            
        self.max_requests = max_requests
        self.duration = duration_seconds
        self._windows: Dict[str, deque] = {}
        self._lock = threading.Lock()

    @contextmanager
    def authorize(self, tenant_key: str):
        """
        Context manager to check rate limits and record usage.
        
        Args:
            tenant_key: Unique identifier for the tenant (e.g., user_id, session_id).
            
        Raises:
            TenantQuotaExceeded: If the limit is reached.
        """
        with self._lock:
            current_time = time.monotonic()
            
            # Initialize window for new tenant
            if tenant_key not in self._windows:
                self._windows[tenant_key] = deque()
            
            window = self._windows[tenant_key]
            cutoff = current_time - self.duration
            
            # Prune expired timestamps
            while window and window[0] < cutoff:
                window.popleft()
            
            # Check capacity
            if len(window) >= self.max_requests:
                earliest = window[0]
                backoff = self.duration - (current_time - earliest)
                raise TenantQuotaExceeded(retry_delay=backoff)
            
            # Record request
            window.append(current_time)
        
        yield

    def prune_idle_keys(self, max_idle_duration: Optional[float] = None):
        """
        Removes entries for tenants that have been idle longer than the window.
        Call this periodically to prevent memory drift in long-running processes.
        """
        cleanup_threshold = max_idle_duration or (self.duration * 2)
        current_time = time.monotonic()
        
        with self._lock:
            keys_to_remove = []
            for key, window in self._windows.items():
                # If window is empty or oldest entry is beyond cleanup threshold
                if not window or (current_time - window[-1]) > cleanup_threshold:
                    keys_to_remove.append(key)
            
            for key in keys_to_remove:
                del self._windows[key]

Usage Pattern

Define distinct guards for different tool categories to enforce severity-aware limits. Read-heavy tools can tolerate higher throughput than write or delete operations.

# Define guards with appropriate thresholds
search_guard = TenantRateGuard(max_requests=20, duration_seconds=60.0)
write_guard = TenantRateGuard(max_requests=5, duration_seconds=60.0)
delete_guard = TenantRateGuard(max_requests=2, duration_seconds=300.0)

TOOL_GUARDS = {
    "search_web": search_guard,
    "create_record": write_guard,
    "update_record": write_guard,
    "delete_record": delete_guard,
}

def execute_agent_tool(tool_name: str, tenant_id: str, payload: dict) -> dict:
    guard = TOOL_GUARDS.get(tool_name)
    
    if guard:
        try:
            with guard.authorize(tenant_key=tenant_id):
                return invoke_tool(tool_name, payload)
        except TenantQuotaExceeded as e:
            return {
                "status": "rate_limited",
                "retry_after": e.retry_delay,
                "message": "Tenant quota exceeded for this tool."
            }
    
    # Fallback for unguarded tools
    return invoke_tool(tool_name, payload)

Pitfall Guide

1. The Global Limit Trap

   • Explanation: Relying solely on global rate limits protects the API provider but allows one tenant to consume the entire quota, causing errors for all other tenants.
   • Fix: Implement per-key limits to ensure fair resource distribution. Global limits should act as a circuit breaker, not the primary isolation mechanism.

2. Tool Severity Blindness

   • Explanation: Applying the same rate limit to all tools ignores the risk profile. A tenant making 50 search calls may be benign, while 50 delete calls could be catastrophic.
   • Fix: Create separate guards per tool category. Assign stricter limits to destructive or expensive operations.

3. Memory Drift from Idle Keys

   • Explanation: In long-running processes, the dictionary of windows accumulates entries for tenants that have stopped making requests. Even empty deques consume memory.
   • Fix: Implement a periodic cleanup routine (e.g., prune_idle_keys) that removes entries for tenants inactive beyond a safe threshold.

4. Distributed State Assumption

   • Explanation: This in-process implementation does not share state across multiple worker nodes. If your agent service scales horizontally, each node maintains independent counters, effectively multiplying the allowed rate.
   • Fix: For distributed deployments, externalize the state to Redis or a similar shared store. Use atomic Lua scripts to maintain the sliding window logic across nodes.

5. Fixed Window Burst Vulnerability

   • Explanation: Fixed windows reset at clock boundaries, allowing a tenant to fire the maximum limit at the end of one window and immediately again at the start of the next, resulting in a 2x burst rate.
   • Fix: Use a sliding window algorithm that tracks individual timestamps, ensuring the rate is averaged continuously over the duration.

6. Missing Backoff Signals

   • Explanation: Returning a generic "429 Too Many Requests" without a retry delay forces the client to guess when to retry, leading to thundering herd problems.
   • Fix: Calculate and return the precise retry_delay based on the oldest timestamp in the window, enabling clients to back off intelligently.

7. TOCTOU Race Conditions

   • Explanation: Without proper synchronization, concurrent requests may both read the current count as below the limit before either records their usage, allowing the limit to be exceeded.
   • Fix: Ensure the check-and-append operation is atomic. Use a mutex lock or atomic database operations to prevent race conditions.

Production Bundle

Action Checklist

• Define Tenant Keys: Identify the unique identifiers for tenants (e.g., user_id, org_id, api_key).
• Categorize Tools: Group tools by risk and cost profile (e.g., read, write, delete, expensive_compute).
• Configure Guards: Instantiate TenantRateGuard for each tool category with appropriate thresholds.
• Wrap Tool Calls: Integrate the authorize context manager into your tool execution pipeline.
• Handle Exceptions: Implement error handling for TenantQuotaExceeded to return structured retry metadata.
• Schedule Cleanup: Add a background task to invoke prune_idle_keys periodically.
• Monitor Metrics: Track rate limit hits per tenant to identify abuse patterns and adjust thresholds.

Decision Matrix

Scenario	Recommended Approach	Why	Cost Impact
Single-Node Agent Service	In-Process Sliding Window	Low latency, zero external dependencies, simple implementation.	Minimal (CPU/Memory only)
Multi-Node Cluster	Distributed Redis Backend	Ensures consistent limits across all workers; prevents limit multiplication.	Moderate (Redis infrastructure)
High-Volume Read Tools	Per-Key Limit + Burst Allowance	Accommodates legitimate spikes while preventing sustained abuse.	Low
Destructive Operations	Strict Per-Key Limit + Audit Log	Prevents data loss; provides traceability for security reviews.	Low
Cost-Sensitive Environments	Rate Limit + Token Budget Pool	Combines frequency control with financial caps for comprehensive governance.	Low

Configuration Template

Use a declarative configuration to manage rate limits without code changes. This supports dynamic updates and environment-specific tuning.

rate_limits:
  defaults:
    max_requests: 10
    duration_seconds: 60
    
  tools:
    search_web:
      max_requests: 20
      duration_seconds: 60
      description: "Read-heavy search tool"
      
    create_record:
      max_requests: 5
      duration_seconds: 60
      description: "Write operation"
      
    delete_record:
      max_requests: 2
      duration_seconds: 300
      description: "Destructive operation with strict limits"
      
    expensive_analysis:
      max_requests: 3
      duration_seconds: 60
      description: "High-cost compute tool"

maintenance:
  cleanup_interval_seconds: 300
  idle_key_ttl_multiplier: 2.0

Quick Start Guide

1. Install Dependencies: Ensure your environment includes threading and collections (standard library). No external packages required for in-process usage.
2. Define Guards: Create instances of TenantRateGuard for your tool categories based on your configuration.
3. Integrate Wrapper: Modify your tool execution function to use the authorize context manager before invoking the tool.
4. Handle Limits: Catch TenantQuotaExceeded and return the retry_delay to the caller.
5. Deploy Cleanup: Add a periodic task to call prune_idle_keys to maintain memory health.

By implementing granular rate fences, you transform your agent infrastructure from a shared liability into a resilient, multi-tenant platform where every user receives fair and predictable access to tools.