Your LLM proxy hits 429 errors during traffic spikes despite having “working” rate limits. The culprit is request-based throttling that ignores token-intensive prompts exhausting TPM limits independently. OpenAI’s gpt-4o allows 10,000 requests/minute OR 2,000,000 tokens/minute. Whichever limit hits first blocks the other. This guide covers AI gateway rate limiting algorithms so you can implement a dual-dimensional rate limiter handling both request and token throughput with correct burst behavior.
Table of Contents
What is the best rate limiting algorithm for AI gateways?
AI gateways need specialized rate limiting that handles both requests-per-minute (RPM) and tokens-per-minute (TPM) limits. Token bucket algorithms allow burst capacity with steady refill rates, ideal for variable LLM prompt sizes. Sliding window algorithms enforce strict quotas with precise time boundaries, preferred for cost-sensitive strict compliance. Production implementations typically combine both: token bucket for overall capacity with sliding window for short-term strict enforcement.
The core difference between token bucket and sliding window rate limiting lies in burst handling. Token bucket permits temporary spikes up to bucket capacity before throttling, while sliding window rejects any request exceeding the fixed rate within the rolling window. Token bucket suits variable workloads like LLM proxying. Sliding window suits strict quota compliance where every overage incurs cost.
Why AI gateways need specialized rate limiting algorithms
Traditional web API rate limiters count requests per time window. One request equals one unit of consumption. LLM APIs break this assumption because they enforce dual limits: requests per minute (RPM) and tokens per minute (TPM).
OpenAI enforces these limits independently. Hitting either limit triggers a 429 Too Many Requests error. According to OpenAI’s documentation [platform.openai.com], limits vary by model tier and account level. Anthropic follows a similar pattern with separate request and token quotas [docs.anthropic.com].
The RPM vs TPM constraint problem
A proxy tracking only request counts will fail when a single request with a 50,000-token prompt exhausts the TPM budget. The request passes the RPM check but still receives a 429 from upstream. This mismatch causes unpredictable failures during traffic spikes when users submit large context prompts.
Token consumption varies by orders of magnitude between requests. A simple question consumes 50 tokens. A document analysis with full context consumes 100,000 tokens. Request-counting rate limiters cannot model this variance.
How token costs vary unpredictably with context
LLM token counts depend on input length, output length, and model-specific tokenization. GPT-4o uses different tokenization than Claude models. Multimodal inputs (images plus text) compound estimation errors. Vision tokens often cost more than text tokens, and exact costs vary by image resolution and model version.
Function calling adds overhead. Each tool definition in the schema counts toward input tokens. Response streaming prevents upfront output token estimation. These factors make traditional fixed-cost rate limiting inadequate for AI gateways.
For resilience patterns that complement rate limiting, see our guide on redis rate limiting for ai gateway resilience.
Token bucket algorithm: mechanics and AI gateway fit
The token bucket algorithm maintains a bucket of tokens that refills at a fixed rate. Each request consumes tokens equal to its estimated cost. The bucket has a maximum capacity allowing configurable burst handling. This algorithm is defined in RFC 2219 [datatracker.ietf.org].
Token bucket suits AI workloads because it handles variable token costs per request and allows controlled bursts. When your gateway receives a sudden spike of requests, the full bucket absorbs them before throttling begins. Users experience responsive service during normal operation and graceful degradation during sustained overload.
Mathematical formalization and parameters
Token bucket has three parameters:
- Bucket capacity (B): Maximum tokens the bucket can hold. This defines burst capacity.
- Refill rate (R): Tokens added per time unit. This defines steady-state throughput.
- Initial tokens: Starting token count, typically equal to B.
For each request consuming N tokens:
- If
tokens >= N: allow request, subtract N from tokens - If
tokens < N: reject request (or queue)
Every time interval T, add R * T tokens, capping at B.
Handling variable token costs per request
LLM requests require token estimation before execution. The gateway must estimate input tokens from the prompt and output tokens from either the max_tokens parameter or a configurable default.
import tiktoken
import os
class TokenEstimator:
"""Estimate token count for OpenAI API requests."""
def __init__(self, model: str = "gpt-4o"):
# tiktoken 0.7.0+ supports current models
self.encoding = tiktoken.encoding_for_model(model)
self.default_max_tokens = 4096
def estimate_request_tokens(
self,
messages: list[dict],
max_tokens: int | None = None,
functions: list[dict] | None = None
) -> int:
"""
Estimate total tokens for a chat completion request.
Returns estimated input + output tokens.
"""
# Encode messages
input_tokens = 0
for message in messages:
# Each message has formatting overhead (~4 tokens)
input_tokens += 4
for value in message.values():
if isinstance(value, str):
input_tokens += len(self.encoding.encode(value))
# Add function definitions if present
if functions:
for func in functions:
input_tokens += len(self.encoding.encode(str(func)))
# Estimate output tokens
output_estimate = max_tokens if max_tokens else self.default_max_tokens
return input_tokens + output_estimate
def estimate_vision_tokens(
self,
image_detail: str = "auto"
) -> int:
"""
Estimate tokens for image inputs.
'low' detail: 85 tokens
'high' detail: 85 + tiles (varies by size, ~170-1105 per image)
'auto': defaults to 'low' unless specified
"""
if image_detail == "low":
return 85
elif image_detail == "high":
# Approximate for high-detail, actual varies by dimensions
return 765 # Average for typical images
return 85 # auto defaultThis estimator handles text and vision inputs. For safety, add a 5-10% buffer to account for estimation errors, especially with function calling or multimodal content.
Python implementation with OpenAI token estimation
Here is a working token bucket rate limiter for an LLM gateway:
import time
import threading
import tiktoken
from dataclasses import dataclass
from typing import Optional
@dataclass
class TokenBucketConfig:
"""Configuration for token bucket rate limiter."""
bucket_capacity: int # Max tokens in bucket (burst capacity)
refill_rate: float # Tokens refilled per second
initial_tokens: Optional[int] = None
class TokenBucket:
"""
Thread-safe token bucket for rate limiting.
Supports variable token consumption per request.
"""
def __init__(self, config: TokenBucketConfig):
self.capacity = config.bucket_capacity
self.refill_rate = config.refill_rate
self.tokens = config.initial_tokens or config.bucket_capacity
self.last_refill = time.monotonic()
self.lock = threading.Lock()
def _refill(self) -> None:
"""Refill tokens based on elapsed time."""
now = time.monotonic()
elapsed = now - self.last_refill
refill_amount = elapsed * self.refill_rate
self.tokens = min(self.capacity, self.tokens + refill_amount)
self.last_refill = now
def consume(self, tokens: int) -> bool:
"""
Attempt to consume tokens from the bucket.
Returns True if successful, False if insufficient tokens.
"""
with self.lock:
self._refill()
if self.tokens >= tokens:
self.tokens -= tokens
return True
return False
def wait_time(self, tokens: int) -> float:
"""Calculate seconds until enough tokens are available."""
with self.lock:
self._refill()
if self.tokens >= tokens:
return 0.0
deficit = tokens - self.tokens
return deficit / self.refill_rate
class LLMRateLimiter:
"""
Dual-dimensional rate limiter for LLM APIs.
Tracks both requests and tokens with separate token buckets.
"""
def __init__(
self,
rpm_limit: int,
tpm_limit: int,
model: str = "gpt-4o"
):
# Convert per-minute limits to per-second rates
self.request_bucket = TokenBucket(TokenBucketConfig(
bucket_capacity=rpm_limit, # Burst up to full minute quota
refill_rate=rpm_limit / 60.0
))
self.token_bucket = TokenBucket(TokenBucketConfig(
bucket_capacity=tpm_limit,
refill_rate=tpm_limit / 60.0
))
self.estimator = TokenEstimator(model)
def check_rate_limit(
self,
messages: list[dict],
max_tokens: int | None = None,
functions: list[dict] | None = None
) -> tuple[bool, str]:
"""
Check if request passes both RPM and TPM limits.
Returns (allowed, reason) tuple.
"""
estimated_tokens = self.estimator.estimate_request_tokens(
messages, max_tokens, functions
)
# Check both limits atomically
request_allowed = self.request_bucket.consume(1)
if not request_allowed:
return False, "RPM limit exceeded"
tokens_allowed = self.token_bucket.consume(estimated_tokens)
if not tokens_allowed:
return False, "TPM limit exceeded"
return True, "OK"
# Example usage
if __name__ == "__main__":
# OpenAI gpt-4o Tier 1 limits (example)
limiter = LLMRateLimiter(
rpm_limit=500,
tpm_limit=200000,
model="gpt-4o"
)
messages = [{"role": "user", "content": "Explain rate limiting algorithms"}]
allowed, reason = limiter.check_rate_limit(messages, max_tokens=1000)
print(f"Request allowed: {allowed}, Reason: {reason}")This implementation separates request and token tracking. Both checks must pass for a request to proceed. The gateway rejects with specific reasons to help debugging.
Sliding window algorithm: precise control for strict quotas
Sliding window tracks exact request counts in a rolling time window. It provides hard boundaries with no burst tolerance. Every request older than the window period drops from the count, ensuring precise rate enforcement.
Sliding window has higher memory overhead than token bucket because it stores timestamps for each request. This makes it suitable for strict TPM enforcement where every token overage incurs cost.
Fixed vs sliding window log implementation
Fixed window divides time into discrete intervals (minute 1, minute 2). Requests in minute 1 don’t affect the count for minute 2. This creates edge-case spikes when requests cluster at window boundaries.
Sliding window log maintains a sorted list of request timestamps. Each request adds its timestamp to the log. The window removes timestamps older than the current time minus the window duration. This prevents boundary spikes but requires O(n) storage where n is requests per window.
import time
import threading
from collections import deque
from dataclasses import dataclass
@dataclass
class SlidingWindowConfig:
"""Configuration for sliding window rate limiter."""
window_seconds: float # Window duration in seconds
max_requests: int # Maximum requests in window
max_tokens: int # Maximum tokens in window
class SlidingWindowLog:
"""
Sliding window log for precise rate limiting.
Maintains timestamps of requests within the window.
"""
def __init__(self, config: SlidingWindowConfig):
self.window_seconds = config.window_seconds
self.max_requests = config.max_requests
self.max_tokens = config.max_tokens
# Store (timestamp, token_count) tuples
self.request_log: deque[tuple[float, int]] = deque()
self.lock = threading.Lock()
def _prune_old_entries(self) -> None:
"""Remove entries outside the current window."""
cutoff = time.monotonic() - self.window_seconds
while self.request_log and self.request_log[0][0] < cutoff:
self.request_log.popleft()
def check_and_record(self, token_count: int) -> tuple[bool, str]:
"""
Check if request is allowed and record it if so.
Returns (allowed, reason) tuple.
"""
with self.lock:
self._prune_old_entries()
current_requests = len(self.request_log)
current_tokens = sum(t[1] for t in self.request_log)
# Check request count
if current_requests >= self.max_requests:
return False, "Request limit exceeded in window"
# Check token count
if current_tokens + token_count > self.max_tokens:
return False, "Token limit exceeded in window"
# Record the request
self.request_log.append((time.monotonic(), token_count))
return True, "OK"
def get_current_usage(self) -> dict:
"""Return current usage statistics."""
with self.lock:
self._prune_old_entries()
return {
"requests": len(self.request_log),
"tokens": sum(t[1] for t in self.request_log)
}Circular buffer optimization for memory
Circular buffers optimize sliding window by dividing the window into fixed slots. Instead of storing every timestamp, store counts per slot. This reduces memory from O(n) to O(slots) at the cost of minor precision.
For a 1-minute window with 6 slots, each slot represents 10 seconds. Requests map to slots by timestamp. The rate check sums slots within the window window_containing current time.
Distributed sliding window with Redis
Production gateways need distributed rate limiting across multiple instances. Redis provides atomic operations for sliding window implementation. Use sorted sets (ZADD) with timestamps as scores.
For distributed rate limiting implementation details, refer to our rate limiter design: 5 patterns that scale guide.
import redis
import time
import json
class RedisSlidingWindow:
"""
Distributed sliding window using Redis sorted sets.
Atomic operations via Lua scripting for consistency.
"""
LUA_SCRIPT = """
local key = KEYS[1]
local window = tonumber(ARGV[1])
local max_requests = tonumber(ARGV[2])
local max_tokens = tonumber(ARGV[3])
local tokens = tonumber(ARGV[4])
local now = tonumber(ARGV[5])
-- Remove old entries
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
-- Count current requests and tokens
local entries = redis.call('ZRANGE', key, 0, -1)
local request_count = 0
local token_count = 0
for i = 1, #entries do
local data = cjson.decode(entries[i])
request_count = request_count + 1
token_count = token_count + data.tokens
end
-- Check limits
if request_count >= max_requests then
return {0, 'request_limit'}
end
if token_count + tokens > max_tokens then
return {0, 'token_limit'}
end
-- Add new entry
local entry = cjson.encode({tokens = tokens, ts = now})
redis.call('ZADD', key, now, entry)
redis.call('EXPIRE', key, math.ceil(window))
return {1, 'ok'}
"""
def __init__(
self,
redis_client: redis.Redis,
key_prefix: str = "rate_limit:",
window_seconds: float = 60.0,
max_requests: int = 1000,
max_tokens: int = 1000000
):
self.redis = redis_client
self.key_prefix = key_prefix
self.window_seconds = window_seconds
self.max_requests = max_requests
self.max_tokens = max_tokens
self.script = self.redis.register_script(self.LUA_SCRIPT)
def check_rate_limit(
self,
identifier: str,
token_count: int
) -> tuple[bool, str]:
"""
Check and record rate limit for identifier.
Args:
identifier: Unique key (user_id, api_key, etc.)
token_count: Estimated tokens for this request
Returns:
(allowed, reason) tuple
"""
key = f"{self.key_prefix}{identifier}"
now = time.time()
result = self.script(
keys=[key],
args=[
self.window_seconds,
self.max_requests,
self.max_tokens,
token_count,
now
]
)
allowed = result[0] == 1
reason = result[1]
return allowed, reasonThe Lua script executes atomically, preventing race conditions where multiple instances check simultaneously. This pattern works for both Kong Gateway 3.7+ and custom proxy implementations.
Token bucket vs sliding window: decision matrix
Choose token bucket for LLM proxying with variable prompt sizes when burst tolerance is needed. Choose sliding window for strict API quota compliance, predictable traffic, or when every token overage incurs cost.
| Factor | Token Bucket | Sliding Window |
|---|---|---|
| Memory overhead | O(1) per key | O(n) per key where n = requests/window |
| Latency | O(1) lookup | O(1) for circular buffer, O(log n) for sorted sets |
| Burst handling | Allows bursts up to bucket capacity | No bursts, strict limit |
| Smoothness | Gradual throttling with refill | Immediate rejection at boundary |
| Token variance | Excellent for variable costs | Requires estimation for each request |
| Distributed complexity | Moderate (atomic increment) | Higher (sorted set operations) |
Latency and memory comparison
Token bucket requires constant memory: one counter and one timestamp per rate-limited key. Sliding window log requires storing every request timestamp within the window. For 10,000 requests per minute, sliding window stores 10,000 entries. Token bucket stores 2 numbers.
Redis token bucket uses INCR to decrement tokens. The operation is atomic and O(1). Redis sliding window uses ZADD with timestamp sorting. Each request is O(log n) where n is current entries.
Burst behavior analysis
Token bucket allows traffic bursts until the bucket empties. A user sending 100 requests instantly gets all 100 through if the bucket has capacity. This improves perceived performance for interactive AI applications where user actions create natural traffic spikes.
Sliding window rejects requests immediately once the count reaches the limit. A user sending 100 requests when the limit is 99 gets one rejection. The user experiences immediate throttling regardless of prior idle time.
For AI gateways with variable prompt sizes, this distinction matters. Token bucket enables large prompts after idle periods. Sliding window may
