Rate Limiting Algorithms

Token bucket, sliding window and GCRA, what each actually guarantees, and the two problems unique to limiting an LLM: metering tokens you have not generated yet, and doing it across many instances.

AI EngineeringAdvanced⏱ 3 hours11 min readrate limitingtoken bucketGCRAsliding windowdistributed limiting

AssumesGateways, Authentication and Quota

Token bucket

DefinitionToken bucket

A bucket holds at most $B$ tokens and refills at $r$ tokens per second. A request of cost $c$ is admitted if the bucket holds at least $c$ tokens, which are then removed.

class TokenBucket:
    def __init__(self, rate: float, capacity: float):
        self.rate, self.capacity = rate, capacity
        self.tokens = capacity
        self.updated = now()

    def _refill(self) -> None:
        t = now()
        self.tokens = min(self.capacity, self.tokens + self.rate * (t - self.updated))
        self.updated = t

    def allow(self, cost: float = 1.0) -> bool:
        self._refill()
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

    def retry_after(self, cost: float = 1.0) -> float:
        self._refill()
        return max(0.0, (cost - self.tokens) / self.rate)

Note there is no timer: the bucket is refilled lazily on read, so an idle bucket costs nothing.

PropositionWhat a token bucket guarantees

For any interval $[t_0, t_0+t]$ , the total cost admitted by a token bucket of rate $r$ and capacity $B$ is at most

B + r\,t ,

and this bound is attained — so the long-run rate is $r$ and the worst-case burst is $B$ .

Key idea

$B$ and $r$ are independent knobs and they mean different things to a user. $r$ is the sustained throughput you are selling. $B$ is how much clumping you forgive — how many requests a client may fire at once after a quiet period. Setting $B = r$ (one second of burst) is a common default; setting $B$ large makes the limiter friendly and the downstream service's peak load larger by exactly $B$ .

What a fixed window gets wrong

PropositionThe fixed window admits twice its limit

A fixed-window counter allowing $N$ requests per window of length $W$ — reset to zero at times $0, W, 2W, \dots$ — admits $2N$ requests within an interval of length $2\varepsilon$ for any $\varepsilon > 0$ .

Sliding window counter

The usual compromise: keep the current and previous window counts and interpolate.

def allow_sliding(key, now, window, limit):
    cur_start = now - (now % window)
    frac = (now - cur_start) / window                 # how far into the current window
    prev, cur = counters.get(key, cur_start - window), counters.get(key, cur_start)
    estimate = prev * (1 - frac) + cur
    if estimate >= limit:
        return False
    counters.incr(key, cur_start)
    return True

This assumes the previous window's requests were spread uniformly, which is an approximation — it can admit slightly over the limit for bursty traffic and slightly under for smooth traffic. It costs two counters per key rather than a full log of timestamps, and it removes the $2\times$ boundary burst, which is the trade most services want.

GCRA: the same thing without a counter

PropositionGCRA is a token bucket without the counter

The generic cell rate algorithm keeps one timestamp, the theoretical arrival time $\mathrm{TAT}$ . With emission interval $T$ and tolerance $\tau$ , a request at time $t$ is admitted iff $t \ge \mathrm{TAT} - \tau$ , after which $\mathrm{TAT} \leftarrow \max(t, \mathrm{TAT}) + T$ .

This admits exactly the same request sequences as a token bucket of rate $r = 1/T$ and capacity

B \;=\; 1 + \frac{\tau}{T} .

Key idea

GCRA stores one timestamp per key rather than a level plus a timestamp, and needs no refill arithmetic. In a distributed store that is one round trip against one value, which is why it is the usual choice when the limiter state lives in Redis. The equivalence means you lose nothing by using it: $\tau = (B-1)T$ converts a token-bucket configuration directly.

The LLM problem: metering what has not happened

HeuristicReserve on entry, reconcile on exit

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

Token limits are the meaningful limits for a model service — requests per minute cannot distinguish a 20-token reply from a 4000-token one — but output length is unknown when the admission decision is made. The workable pattern is two-phase:

async def metered(tenant, req):
    estimate = count_input_tokens(req) + (req.max_tokens or model.default_max)
    lease = await limiter.reserve(tenant, estimate)      # hold the pessimistic amount
    if lease is None:
        raise TooManyRequests(retry_after=limiter.retry_after(tenant, estimate))
    try:
        resp = await model.generate(req)
        return resp
    finally:
        actual = resp.usage.input_tokens + resp.usage.output_tokens if resp else estimate
        await limiter.reconcile(lease, actual)           # refund or charge the difference

Reserve the pessimistic figure — input plus max_tokens — and refund on completion.

Assumptions

Reserving the maximum systematically under-admits: if requests declare max_tokens = 4096 but average 300 output tokens, the limiter holds about thirteen times the tokens actually consumed, and a tenant hits their limit at roughly a thirteenth of their real entitlement. The mitigations are to reserve a predicted length with a safety margin and accept occasional overshoot, or to require callers to set max_tokens honestly and price accordingly. Reserving optimistically instead means the limit can be exceeded by an unbounded amount, which defeats the purpose.

Limiting across many instances

PropositionSplitting a budget across instances under-admits

Suppose a tenant's limit is $R$ and it is divided statically as $R/N$ across $N$ gateway instances. If the tenant's traffic is distributed over instances with fractions $f_1,\dots,f_N$ summing to $1$ , the admitted rate is

R\sum_{i=1}^N \min\!\left(f_i,\ \frac1N\right) \;\le\; R ,

with equality only when $f_i = 1/N$ for every $i$ . In the worst case — all traffic on one instance — the admitted rate is $R/N$ .

Key idea

Static splitting is only correct when load balancing is perfectly even — and with keep-alive connections, sticky sessions or a handful of large tenants, it is not. The options are:

Shared state — one Redis counter per key. Correct, and adds a network round trip to every request plus a dependency that must fail open.
Lease-based — instances lease chunks of budget from a central allocator and spend them locally, refreshing when low. One round trip per chunk rather than per request; slightly bursty at chunk boundaries.
Sticky routing by key — hash the tenant to one instance, which then holds the whole budget locally. No shared state, but an instance restart loses the counter and a hot tenant has no horizontal headroom.

Most production limiters are (2) with (1) as the source of truth, because it keeps the per-request cost local while keeping the budget global.

Telling the client what to do

HTTP/1.1 429 Too Many Requests
Retry-After: 2
anthropic-ratelimit-tokens-limit: 400000
anthropic-ratelimit-tokens-remaining: 0
anthropic-ratelimit-tokens-reset: 2026-09-21T14:32:00Z

Retry-After should be computed from the limiter state — for a token bucket, exactly $(c - \text{tokens})/r$ — not a fixed constant. Returning the true value lets a well-behaved client wait precisely long enough; returning a constant makes every client retry at the same instant, which is the synchronised-retry failure discussed in Reliability Patterns.

What this does not say

Rate limiting decides whether a request runs, not when it runs among those admitted. A limiter that admits a request hands it to a queue, and the queue's discipline — first-come, shortest-first, priority — is a separate decision covered by Scheduling, Admission Control and Fairness. Limiting and scheduling are often conflated, and the symptom is a system that is fair in admission and wildly unfair in latency.

References

Lecture notesATM Forum (1996). ATM Forum Traffic Management Specification Version 4.0Original definition of the generic cell rate algorithm as a virtual scheduling procedure.
Lecture notesM. Nottingham, R. Fielding (2012). RFC 6585: Additional HTTP Status CodesDefines 429 Too Many Requests and its relationship to Retry-After.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionToken bucketA counter refilled at a constant rate and capped at a burst capacity, decremented by the cost of each admitted request.
PropositionWhat a token bucket guaranteesproof includedOver any interval of length t a token bucket admits at most B + rt units of cost, and this is tight.
PropositionThe fixed window admits twice its limitproof includedA fixed-window counter of N per window permits 2N requests in an interval shorter than one window, straddling a boundary.
PropositionGCRA is a token bucket without the counterproof includedThe generic cell rate algorithm with emission interval T and tolerance tau admits exactly the sequences a token bucket of rate 1/T and capacity 1 + tau/T admits.
HeuristicReserve on entry, reconcile on exitOutput length is unknown in advance, so a token limiter must hold a reservation against an estimate and settle the difference when generation ends.
PropositionSplitting a budget across instances under-admitsproof includedStatically dividing a rate limit among N instances admits only the fraction of the budget that reaches each instance, which under skewed routing is far below the intended rate.