Token-Based Rate Limiting for LLM APIs: Buckets, Fairness and Priority Lanes

Why requests are the wrong unit

GPU cost per request scales with tokens. Prefill work grows with prompt length (and attention cost grows faster than linearly for very long prompts), while decode work grows with output tokens and holds a batch slot and KV cache memory for the whole generation. A useful first-order cost is a weighted sum such as work = a × input_tokens + b × output_tokens, where output tokens cost several times more per token than input tokens on most deployments; many providers price them that way for the same reason.

The arithmetic of the lab's runaway agent makes the problem concrete. It sends 2 requests per second, 120 per minute, comfortably under a 400 requests-per-minute limit. Its context grows from 6,000 to 24,000 tokens and it asks for about 1,000 output tokens each time. In token terms that is roughly 2 × (15,000 + 1,000) = 32,000 tokens per second, close to 1.9 million tokens per minute, while a chat tenant at 1.5 requests per second with 900-token prompts and 250-token answers uses about 1,700. A request limit sees the agent as smaller than the chat app. In the lab, interactive requests that start within 2 seconds fall from 100% to about 70% when the agent arrives under a request limit.

The token bucket

A token bucket has a capacity B and a refill rate r. Each tenant's bucket refills continuously at r tokens per second up to B; a request is admitted if the bucket holds at least its cost, which is then removed. Over any window of length t, a tenant can consume at most B + r × t tokens, so r sets the long-run rate (the advertised tokens per minute divided by 60) and B sets the largest burst. The same behaviour can be implemented as the generic cell rate algorithm (GCRA), which stores a single timestamp per key and is popular in Redis-backed limiters.

class TokenBucket:
    def __init__(self, tokens_per_min, burst_seconds):
        self.rate = tokens_per_min / 60.0          # refill, tokens per second
        self.cap = self.rate * burst_seconds       # bucket size
        self.level, self.t = self.cap, now()

    def try_reserve(self, cost):
        t = now()
        self.level = min(self.cap, self.level + (t - self.t) * self.rate)
        self.t = t
        if self.level < cost:
            wait = (cost - self.level) / self.rate
            return False, wait                     # reply 429 with Retry-After: ceil(wait)
        self.level -= cost
        return True, 0.0

    def refund(self, unused):
        self.level = min(self.cap, self.level + unused)

# per request: cost = input_tokens + max_tokens; on completion refund(max_tokens - output_tokens)

Return HTTP 429 (defined in RFC 6585) with a Retry-After header computed from the deficit, and include remaining-budget headers so well-behaved clients can pace themselves. Clients that retry immediately without backoff turn a short overload into a retry storm, so publish the expected client behaviour (exponential backoff with jitter, honour Retry-After) alongside the limit.

Charging for output you have not generated yet

The input token count is known at admission; the output count is not. There are three common ways to charge, each with a failure mode:

Some hosted APIs document variants of these. For example, some count max_tokens toward the limit at admission, and some publish separate input and output token limits and describe a token bucket; check the current rate-limit documentation of your provider before assuming either. For your own gateway, reservation with refund is the safest default. Its cost shows up in bucket sizing: a chat request that reserves 900 + 1,024 tokens but uses 900 + 250 holds about 770 extra tokens of budget for the few seconds it runs.

Sizing the bucket for legitimate bursts

A bucket that is too small rejects real users during ordinary bursts; one that is too large lets a misbehaving client dump a large amount of work on the backend at once. Size it from the burst you want to absorb. In the lab, each app tenant is contracted for 200,000 tokens per minute, a refill of 3,333 tokens per second. Normal traffic of 1.5 requests per second reserves about 2,900 tokens per second and, after refunds, nets about 1,700. During a 30-second burst at 2.5 times the rate:

# illustrative arithmetic, matching the lab's synthetic tenants
reserve rate  = 3.75 req/s × 1,924 tokens          ≈ 7,200 tokens/s
refund rate   = 3.75 req/s × ~770 tokens (lagged)  ≈ 2,900 tokens/s
net draw      ≈ 4,300 tokens/s  vs  refill 3,333 tokens/s
deficit       ≈ 1,000 tokens/s × 30 s ≈ 30,000 tokens
+ reservations in flight ≈ 3.75 × 4 s × 770 ≈ 11,500 tokens
bucket needed ≈ 42,000 tokens ≈ 13 s of refill   (the lab needs 15 to 20 s)

The general rule: bucket size should cover the excess of peak draw over refill for the length of the burst you consider legitimate, plus the budget held by in-flight reservations. Anything larger is permission for a client to front-load work, which the backend has to absorb through its queue.

Rate limits do not order the queue

A rate limit decides who may send work. It does not decide which admitted work runs first. When the backend is near capacity, admitted requests wait in the gateway or the server's queue, and the order of that queue determines latency. With first-in-first-out, a chat turn that arrives behind fifty 4,000-token batch prompts waits for all of them to be admitted. Static limits can paper over this only by keeping the backend well below capacity: in the lab, a 600,000 tokens-per-minute limit keeps chat fast with a busy batch tenant, but the backend runs at about 40% and batch throughput is a quarter of what the hardware could deliver.

Two scheduling policies fix the ordering without refusing work:

• Priority lanes. Tag each request with a class (interactive, batch, background) and always admit the highest class first. vLLM, for example, offers a priority scheduling policy with a per-request priority value; check your version's documentation for the flag and semantics. Strict priority can starve low classes, so add an aging rule or a minimum share for batch.
• Fair queueing. Serve tenants in proportion to weights rather than arrival order, so one tenant's backlog cannot delay others. Classic weighted fair queueing tracks virtual finish times; for LLMs, the Virtual Token Counter scheduler (Sheng et al., OSDI 2024) counts served input and output tokens per client and serves the client with the least service so far, which gives fairness in tokens rather than requests.

The production pattern combines the two layers: token limits at the gateway stop abuse and enforce contracts, while a scheduler in front of or inside the inference server protects latency for interactive traffic and lets batch soak up the rest. Mission three in the lab asks for exactly this: 5,000 batch tokens per second and 99% of interactive requests starting within 2 seconds, which no static limit achieves.

Where the knobs live

Rate limiting usually sits in an API gateway or service mesh, with shared state in Redis or a dedicated rate-limit service. Envoy provides a local token-bucket filter and a global rate-limit service integration; most API gateways (Kong, Apigee, cloud API gateways) and LLM gateways such as LiteLLM offer per-key request and token limits. Token-aware limits require the gateway to count tokens, which means running the model's tokenizer (or a close approximation) on the request and reading the usage block from the response. Check the exact options in your gateway's version; token-based plugins are evolving quickly.

Agents need limits of their own

Agent loops change the shape of traffic in ways that tenant-level limits miss. Each step resends the growing conversation, so prompt tokens per request rise over the life of a run, often linearly with the step count, while the request rate stays flat. Twenty steps over a context that grows by 1,000 tokens per step consume about 20 × 10,500 ≈ 210,000 prompt tokens for a single task, before any output. A tenant-wide budget lets one stuck run consume the whole team's allowance. Three additional limits help: a per-run token budget enforced by the orchestrator (stop or summarise when it is spent), a per-run step cap, and a per-tenant concurrency limit on in-flight generations so a fleet of parallel runs cannot all hold long requests at once. Prefix caching reduces the compute cost of resent context on servers that support it, but most token-based limits still count those tokens, so decide deliberately whether cached prompt tokens should cost less in your accounting.

A worked example: Belgavi's Book Store

Suppose the hypothetical Belgavi's Book Store shares one inference backend between four customer-facing apps, a nightly catalogue-enrichment batch job and a new research agent. Every number below comes from the lab's synthetic model. With no limits and first-in-first-out, everything works until the agent ships: the backend saturates, interactive p95 queue wait reaches about 8 seconds, and only 70% of chat requests start within the 2-second target. The existing 400 requests-per-minute limit never triggers, because the agent sends 120.

Switching to tokens per minute with reservation and refund, at 800,000 per tenant, caps the agent's draw and restores chat while the batch job still gets about 1,700 output tokens per second. A month later the apps' contract is set at 200,000 tokens per minute and a promotion produces a 30-second burst; with a 5-second bucket, 9% of interactive requests are rejected. A 20-second bucket absorbs it without raising the contract. Finally, the team adds an interactive priority lane. With the lane in place, the per-tenant limit can rise to 1.4 million tokens per minute, enough for the batch job to use the spare capacity, while chat stays fast even with the agent and a burst on at once.

Detecting problems in production

• Per-tenant token usage versus limit as a time series. A tenant at 100% of its limit for hours is either under-provisioned or misbehaving; look at its prompt length trend.
• 429 rate by tenant and class. Interactive 429s during bursts point at bucket size; steady 429s point at the limit itself.
• Queue wait by class at the scheduler. Rising interactive wait with flat 429s means the queue order, not the limit, is the problem.
• Share of backend work by tenant, computed from usage blocks. Agents with growing context show a steadily rising share at a flat request rate.
• Retry amplification: requests received divided by unique requests. Above about 1.2 during an incident suggests clients ignoring Retry-After.

Common mistakes

Limiting requests instead of tokens is the most common. Close behind: forgetting that reservation with refund needs a larger bucket than the average rate suggests; applying one limit to all tenants regardless of class, which either starves batch or exposes chat; computing token counts with the wrong tokenizer, so limits drift from real usage after a model change; and relying on limits to protect latency while the backend queue stays first-in-first-out. Finally, limits keyed only by API key let one key shared across many end users exhaust a whole team's budget; for agent workloads, key limits by agent run or end user as well.

How the lab missions map to this

The lab simulates 120 seconds of traffic from four chat apps, a batch tenant and an optional runaway agent against a backend of four replicas with a linear step-time model. The stacked chart shows the backend work each tenant consumes, the red line is the admission queue, and floating 429 labels mark rejected requests. Mission one shows a request limit failing against a long-context agent. Mission two asks you to size a bucket for a burst under a fixed contract. Mission three shows that static limits waste capacity and asks you to use queue order instead. Mission four combines the agent, the burst and heavy batch under a policy that every tenant must have a token limit.

Run the lab: Token buckets and priority lanes: keep one tenant from starving the rest

The chart below stacks the backend work each synthetic tenant consumes over two minutes, with the dashed line at capacity and the red line showing the admission queue. Floating 429 labels mark requests the gateway rejected. Start wide open, turn on the runaway agent, then try request limits, token limits and queue orders.

Prefer a full-width view? Open the standalone lab. Your stars are saved in this browser and shown on the series hub.

What to do next

1. Switch tenant limits from requests per minute to tokens per minute, charging prompt plus max_tokens at admission and refunding unused output.
2. Cap max_tokens per tenant class so reservations stay meaningful.
3. Size each bucket from the burst you consider legitimate, using peak draw minus refill times burst length plus in-flight reservations.
4. Return 429 with Retry-After and remaining-budget headers, and document client backoff with jitter.
5. Add a priority class or fair-share weights at the scheduler so interactive traffic does not wait behind batch prompts.
6. Dashboard per-tenant token usage, 429 rate by class and queue wait by class; alert on a tenant whose share rises at flat request rate.

Sources and further reading

• RFC 6585: Additional HTTP Status Codes (429 Too Many Requests)
• Fairness in Serving Large Language Models (Sheng et al., OSDI 2024)
• Envoy documentation: local rate limit filter
• Anthropic API documentation: rate limits
• OpenAI platform documentation: rate limits

Related in this series:

• Autoscaling LLM Servers: Why GPU Utilization Lies and Queue Depth Wins
• TTFT, TPOT and Goodput: Setting LLM Latency SLOs That Mean Something
• Why Agent Loops Run Away and How Step Budgets Stop Them

Diagrams, examples and the lab model are original educational material. Lab numbers are calculated by a synthetic model, not measured on real hardware or services.

Views are my own and do not represent any employer, past or present.