Token-based rate limiting for an LLM API

➔? Design token/cost-based rate limiting for an AI API where each request consumes variable units (1 request = 10 to 100,000 tokens)

Concepts Involved

Rate Limiting API Gateway Redis Backpressure

Problem Statement

Design rate limiting for an LLM API where requests vary wildly in cost. A simple request might use 50 tokens while a complex one uses 100,000 tokens. Limiting by request count is meaningless — you must limit by total tokens consumed per minute (TPM), using a token bucket with weighted cost per request.

Core challenge: The fundamental assumption of most rate limiters — "1 request = 1 unit of consumption" — is broken. A user sending 10 requests at 100K tokens each consumes 1000x more resources than a user sending 10 requests at 100 tokens each. You must weight each request by its actual cost and deduct from a shared budget.

90K

TPM (tokens/min)

tier-1 limit

Variable

cost per request

10 to 100K tokens

Dual Limit

TPM + RPM

both enforced

Token Bucket

with weighted cost

deduct N per request

Functional Requirements

What the system must do · token/cost-based rate limiting for LLM APIs

Must Have (Core)

1. Rate limit by tokens consumed (not request count)
2. Dual limits: TPM (tokens per minute) + RPM (requests per minute)
3. Reserve-then-refund for unknown output token costs
4. Per-model weight multiplier (GPT-4 token = 10x GPT-3.5 budget)
5. Standard response headers with token counts and reset times
6. Streaming support — deduct tokens incrementally during streaming responses

Out of Scope (this design)

✗ Request queuing/scheduling (priority queues, fairness)
✗ Model selection logic (routing to appropriate model)
✗ Cost/billing calculation (pricing, invoicing)
✗ Prompt caching (semantic dedup, cache hits)
✗ Content moderation (safety filters, policy enforcement)

Non-Functional Requirements

Quality constraints shaping the token-based rate limiting design

Property	Target	Why It Matters / Design Impact
Accuracy	Exact token accounting (input + output)	Deduct actual tokens consumed. No approximation — users pay per token, limits must be precise.
Latency	<3ms per admission check (pre-flight reserve)	Reserve check happens before inference. Must not add perceptible latency to API response time.
Recovery	Refund unused tokens within 1s of response completion	Reserved max_tokens but used less. Refund difference immediately to avoid unfairly starving user budget.
Streaming	Deduct tokens incrementally during streaming	Long streaming responses (30s+) need progressive accounting. Can't wait until stream ends.
Model Weights	GPT-4 token costs 10x GPT-3.5 from same budget	Expensive models consume more budget per token. Unified budget across models with weight multipliers.

Key tension: Pre-flight reservation vs. Actual cost. You don't know output tokens until generation completes. Must reserve estimated max upfront and refund unused — or risk over-serving users who exceed their budget.

Scale Estimation

Given numbers from the question → derive infrastructure sizing

Given (from question): 90K TPM per user · 500 RPM per user · average request uses 2K tokens (input + output)

Step	What to Derive	Calculation	Result	Design Decision
1	Requests before TPM limit	90K TPM ÷ 2K avg tokens/request	~45 requests (if all average-sized)	But variable: 1 request at 90K tokens = entire budget consumed.
2	Redis memory per user	per-user bucket state = 3 fields × 64 bytes	~200 bytes/user	Trivial per-user footprint. Token bucket + request counter + reservation.
3	Total memory (1M users)	1M users × 200 bytes	~200MB	Well within single Redis instance. Fits comfortably in memory.
4	Peak Redis ops	500 RPM × 1M users ÷ 60 seconds	~8.3M checks/sec	Requires Redis Cluster at peak. Shard by user_id.
5	Refund operations	Same frequency as requests (one refund per completed response)	~8.3M refunds/sec at peak	Refund is async (post-response). Can batch or pipeline.

Interview tip: Show the variance problem first (step 1) — "45 requests if average, but 1 request can consume entire budget." This proves why request counting is meaningless. Then show Redis can handle the scale (step 3-4).

APIs

Rate limit check runs BEFORE inference · response headers inform client of remaining budget

POST /v1/chat/completions

Rate check executes before inference. Reserve estimated tokens (input + max_tokens), then refund unused after completion.

// Success response headers

x-ratelimit-limit-tokens: 90000

x-ratelimit-remaining-tokens: 58000

x-ratelimit-reset-tokens: 2025-01-15T10:31:00Z

// Request-based limits (also enforced)

x-ratelimit-limit-requests: 500

x-ratelimit-remaining-requests: 423

429 Too Many Requests (Token or Request limit hit)

Returned when TPM or RPM limit exceeded. Body indicates which limit was hit.

// 429 response body

{ "error": { "type": "tokens", "message": "Rate limit exceeded: TPM" } }

// or

{ "error": { "type": "requests", "message": "Rate limit exceeded: RPM" } }

Data Model

Redis token bucket state + request counter + reservation tracking

Redis · Token Bucket (TPM)

// Token bucket per user (refills at 1,500 tokens/sec)
ratelimit:tokens:{user_id} → HASH {
  bucket_level: 58000,       // current tokens available
  last_refill: 1705312200,   // timestamp of last refill calculation
  capacity: 90000,           // max bucket size (TPM limit)
  refill_rate: 1500          // tokens added per second
}

Redis · Request Counter (RPM)

// Fixed window request counter per user
ratelimit:requests:{user_id} → HASH {
  count: 77,                 // requests in current window
  window_start: 1705312200   // current window start timestamp
}

Redis · Reservation Tracking

// Active reservation per in-flight request
reservation:{request_id} → {
  reserved_tokens: 5000,     // tokens reserved (input + max_tokens)
  user_id: "u_42",
  created_at: 1705312205
}
TTL: 120s (auto-expire if response never completes)

// On completion: deduct actual, refund (reserved - actual) back to bucket
// Actual: 1K input + 800 output = 1,800 tokens
// Refund: 5,000 - 1,800 = +3,200 back to bucket_level

Architecture · Token Bucket with Variable Deduction

Each request deducts its token cost from the bucket — large requests consume more of the budget

Decision	Choice	Why
Algorithm	Token bucket with variable deduction (deduct N tokens per request, not 1)	Natural fit: bucket holds TPM budget, each request removes its token count. Refills at TPM/60 per second.
Dual limits	TPM (tokens per minute) + RPM (requests per minute)	TPM prevents resource exhaustion. RPM prevents connection exhaustion (even cheap requests have connection overhead).
Pre-check vs post-check	Pre-check with estimated cost (input tokens), post-deduct with actual cost (input + output)	Can't know output tokens before generation. Pre-reserve estimate, adjust after completion.
Estimation	Estimate output tokens from model + max_tokens param	Reserve max_tokens at admission. Refund unused tokens after response completes.
Storage	Redis: bucket level + last_refill_timestamp per user	Atomic check-and-deduct via Lua script. Refill calculated lazily on each request.
Overflow	429 with tokens_remaining, tokens_reset headers	Client knows exactly when they can retry and how many tokens they have left.

Token bucket with weighted cost: Bucket capacity = 90,000 (TPM limit). Refill rate = 1,500 tokens/sec. Request arrives needing 5,000 tokens → check if bucket ≥ 5,000 → if yes, deduct 5,000 and process → if no, return 429 with retry time = (5000 - current_level) / refill_rate.

The estimation problem: You don't know how many output tokens a request will use until generation completes. Two strategies: (1) Reserve max_tokens upfront, refund unused after completion. (2) Post-deduct only — risk over-serving but simpler. OpenAI uses strategy 1 for strict enforcement.

Why request counting fails: User A sends 10 requests × 100K tokens = 1M tokens (massive GPU cost). User B sends 10 requests × 100 tokens = 1K tokens. Both "used 10 requests" but A consumed 1000x more compute. Request-based limiting is meaningless for variable-cost APIs.

Real-world: OpenAI · TPM + RPM dual limits per tier. Anthropic · tokens per minute per model. Google Vertex AI · requests + characters per minute. AWS Bedrock · tokens per minute per model per account.

Resilience & Edge Cases

Failure	Impact	Recovery
User sends max_tokens=100K but response is 50 tokens	Reserved 100K, used 50 — budget unfairly consumed	Refund unused tokens after response completes. Bucket level += (reserved - actual).
Streaming response (tokens arrive over 30s)	Can't know final cost until stream ends	Reserve estimated amount. Deduct actual incrementally. If reservation runs out mid-stream, allow completion but mark over-budget.
Batch API (100 requests in one call)	Single request consumes entire TPM budget	Pre-estimate total batch cost. Reject if batch would exceed remaining budget. Or split batch across multiple windows.
Model cost varies (GPT-4 vs GPT-3.5)	Same tokens, different compute cost	Weighted tokens by model: GPT-4 token = 10x GPT-3.5 token in budget terms. Or separate budgets per model.
Concurrent requests drain budget simultaneously	All get admitted, total exceeds budget	Atomic reservation in Redis Lua. If 5 concurrent requests each need 20K and budget is 90K, 5th gets 429.

Interview Cheat Sheet

Key points for token/cost-based rate limiting

1. Token bucket with variable deduction · deduct N tokens per request, not 1 (breaks "1 req = 1 unit" assumption)
2. Dual limits: TPM + RPM · tokens for resource cost, requests for connection cost
3. Reserve-then-refund pattern · reserve max_tokens upfront, refund unused after response completes
4. Lazy refill calculation · on each request: elapsed_since_last × refill_rate added to bucket
5. Model-weighted tokens · expensive models cost more tokens from the same budget
6. Response headers · x-ratelimit-remaining-tokens, x-ratelimit-reset-tokens for client self-throttling

System Design Case Study