Debiting on response admits everything already in flight

The limiter that replaced the request counter did everything the previous chapter asked of it. It held a bucket of 100,000 tokens per tenant per minute, it debited that bucket in tokens rather than requests, and it took its figures from usage.input_tokens and usage.output_tokens on the provider's response, so its ledger matched the invoice to the token. At 09:14 on a Thursday a customer's nightly summarisation job started late and opened 200 concurrent requests inside 400 milliseconds, each one asking for a document summary that would run to roughly 2,000 output tokens. The limiter admitted all 200. Over the following forty seconds it debited 400,000 tokens against a 100,000-token minute, correctly, one response at a time.

Nothing malfunctioned. Every check consulted the authoritative balance and every debit recorded the true cost. The gap is in the ordering, because the decision and the charge happen at opposite ends of the generation, and a generation is slow.

09:14:02.118 rl.check tenant=acme balance=100000 verdict=allow  req=r0001
09:14:02.119 rl.check tenant=acme balance=100000 verdict=allow  req=r0002
09:14:02.121 rl.check tenant=acme balance=100000 verdict=allow  req=r0003
...
09:14:02.503 rl.check tenant=acme balance=100000 verdict=allow  req=r0200
09:14:33.902 rl.debit tenant=acme tokens=2094 balance=97906     req=r0001
09:14:34.410 rl.debit tenant=acme tokens=1988 balance=95918     req=r0002
09:14:35.077 rl.debit tenant=acme tokens=2151 balance=93767     req=r0003
...
09:15:12.664 rl.debit tenant=acme tokens=2007 balance=-300412   req=r0200

Two hundred allow verdicts read the same number, 100,000, because at the moment each of them ran, nothing had been spent. The first debit lands 31.8 seconds after the first check, which is how long it takes to stream 2,000 tokens at around 63 tokens per second, and by then the other 199 requests are already committed to the provider and cannot be recalled. The bucket goes negative and stays negative, and the tenant is throttled hard for the next four minutes — which is the limiter finally reacting to a burst that finished before it noticed.

The window is the generation, and it is thirty seconds wide#

The size of the overshoot is not a matter of luck. Between the admission check and the settling debit there is a window equal to the request's own latency, and every request that arrives inside that window makes its decision against a balance that does not include any of its neighbours. The worst case is therefore the number of requests that can arrive during one generation, multiplied by what each will cost, and neither factor is small: at 400 requests per minute with a 30-second mean latency, roughly 200 requests are in flight at any moment by Little's law, which says the number of items in a system is the arrival rate multiplied by the time each one spends there, so a bucket of 100,000 tokens can be overshot by 400,000 without a single check behaving incorrectly. Raising the refill rate does not help, because the failure is not about the rate. Lowering it makes the throttle that follows the burst longer and more punishing.

Changing the limiting algorithm does not close the window either, which is worth establishing before reaching for one. A fixed-window counter, which allows N per calendar minute and resets on the boundary; a sliding-window log, which keeps the timestamp of every recent request and counts the ones inside a trailing window; and a token bucket differ in how they smooth traffic across time — ByteByteGo's Rate Limiter System Design walks the menu and the trade-offs under bursty arrivals — and all three share the same structure here: a decision function that consults recorded consumption, and a recording step that happens later. If consumption is recorded at settlement, every algorithm in that menu decides against stale state, and the staleness is measured in generation latency rather than in milliseconds. The fix has to change when the charge lands, not which curve smooths it.

Retail payments solved this shape long before anyone metered a language model. A fuel pump cannot know what a tank will cost before it is filled, so the terminal places an authorisation hold for an estimated amount, the pump dispenses against that hold, and the settlement afterwards adjusts the charge to the true figure and releases the rest. The hold is what stops a card with $20 of credit from authorising eight pumps at once. The critical property is that the hold is placed before the work, at a number that is wrong, and being wrong in a bounded, correctable direction is what makes it useful.

Reserving an estimate and refunding the difference#

Admission therefore has to charge something at check time. The input side is exactly countable — you have the messages in hand and can run them through the tokenizer, or call the provider's token-counting endpoint if the templating is complex enough that local counting drifts. The output side has to be an estimate, and the whole of chapter 4 is about choosing it well; for now take the route's max_tokens where it is set. The reservation is the sum, it is debited atomically along with the check, and when the response lands you refund the difference between what you reserved and what the provider says you actually used.

The atomicity matters as much as the reservation. Reading the balance, deciding, and writing the new balance as three separate round trips reintroduces the same race in miniature, and under 200-way concurrency that read-modify-write loses updates constantly. In Redis the standard answer is a Lua script, which the server runs as a single unit, so refill, check and debit land together.

-- KEYS[1] = bucket hash for the tenant, fields: tokens, ts
-- ARGV: 1 capacity, 2 refill_per_sec, 3 requested, 4 now_ms
local b     = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local cap   = tonumber(ARGV[1])
local rate  = tonumber(ARGV[2])
local want  = tonumber(ARGV[3])
local now   = tonumber(ARGV[4])
local tokens = tonumber(b[1]) or cap
local ts     = tonumber(b[2]) or now

tokens = math.min(cap, tokens + (now - ts) / 1000 * rate)

if want > tokens then
  redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
  -- seconds until the request would fit, for Retry-After
  return {0, math.ceil((want - tokens) / rate)}
end

tokens = tokens - want
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], 600000)
return {1, math.floor(tokens)}

The refund is the mirror image and must be unconditional, which in practice means it lives in a finally rather than on the success path, because a request that fails after admission has still consumed a reservation that nobody else can use until it comes back.

async def guarded_completion(tenant: str, messages, max_tokens: int, model: str):
    reserved = count_input_tokens(model, messages) + max_tokens
    ok, hint = await bucket.reserve(tenant, reserved)
    if not ok:
        raise RateLimited(retry_after=hint, reserved=reserved)

    used = 0
    try:
        resp = await client.messages.create(
            model=model, max_tokens=max_tokens, messages=messages
        )
        used = resp.usage.input_tokens + resp.usage.output_tokens
        return resp
    finally:
        # refund whatever the generation did not consume; on an exception
        # used stays 0 and the entire reservation is returned.
        await bucket.refund(tenant, max(0, reserved - used))

Run the 09:14 burst against this and the arithmetic changes at the first check. Each request reserves 2,300 tokens — 300 of counted input plus a 2,000-token max_tokens — so the bucket admits 43 of them and refuses the other 157 with a Retry-After derived from the refill rate. Those 43 settle around 2,100 tokens each and refund roughly 200 apiece, which returns about 8,600 tokens to the bucket over the next half-minute and lets a few more through. The tenant's job takes longer and finishes; the platform spends 100,000 tokens in that minute rather than 400,000, and no other tenant on the shared account ceiling ever learns that the job ran.

One detail in the refund path is easy to omit and produces a limiter that leaks capacity upward. A refund is a credit to the bucket, and a credit applied without clamping can push the balance above capacity — a tenant who reserves 2,300 tokens against a nearly full bucket, then has 2,000 refunded a moment after the bucket has refilled, ends up holding more than the burst allowance permits. The clamp belongs in the same place as the refill's, so that tokens = min(capacity, tokens + credit) is the only way a balance ever increases. Without it a tenant with many small over-reservations accumulates phantom headroom, and the burst you tested in the previous paragraph is no longer the burst they can take.

Capacity and refill rate are two decisions, not one#

A token bucket has two dials and they answer different questions. The refill rate is the sustained throughput a tenant is entitled to, averaged over any window long enough to matter. The capacity is how much unused entitlement they may accumulate and spend in a single instant, which is the burst allowance, and it is a separate policy choice that people habitually set equal to the per-minute rate without deciding anything.

Consider the common configuration of capacity 100,000 with a refill of 100,000 per minute. A tenant that has been idle for an hour arrives with a full bucket and can spend the whole 100,000 tokens in one second, then continues at 100,000 a minute thereafter; the hour of idleness earns them nothing beyond the first bucketful, because capacity caps the accumulation. That configuration is correct only if a 100,000-token instantaneous claim from one tenant is something the rest of the system can absorb — your provider ceiling, your concurrency pool and your latency budget for everyone else all have to survive it. Against a 2,000,000-tokens-per-minute account ceiling one such burst is 5% and unremarkable; eight tenants waking at the same second is 800,000 tokens claimed in about a second, and providers enforce their per-minute ceilings over short sliding windows rather than at minute boundaries, so that arrives as a platform-wide 429 rather than as a smooth minute.

There is a test for this and it belongs in the same suite as the sweep from chapter 1: leave a tenant idle for longer than capacity / refill, fire a single batch whose reservation total exceeds capacity, and assert on the split. With capacity 100,000 and a 150,000-token batch, expect the first 100,000 admitted and the remainder refused with a Retry-After of about 30 seconds, then assert that the bucket is at zero and that it reads 50,000 exactly thirty seconds later. A limiter that admits the whole 150,000 has a refill bug, and one that refuses the entire batch is checking the total against capacity rather than admitting request by request.

Where the ledger and the limiter part company#

Reserve-and-refund is not an accounting system and should not be asked to be one. Your invoice reconciliation, your per-customer cost reports and your margin analysis all take their figures from the provider's reported usage after the fact, where accuracy is the only virtue that matters and lateness costs nothing. The bucket exists to make a decision under uncertainty before the work happens, and it accepts a wrong number in exchange for making that decision at all. Keeping the two separate stops an argument that otherwise recurs every quarter, in which someone notices that the limiter's numbers do not match finance's numbers and proposes to fix the limiter.

The refund is also weaker than it looks, and it is worth naming what it does not do. It returns capacity for subsequent requests; it cannot revisit the admission decision that has already been made, because that request is at the provider. If your estimate is systematically too large, every refund is punctual and correct and the tenant still runs at a fraction of their entitlement, since concurrency is capped by capacity divided by the reservation rather than by actual consumption. There is also a durability hole in the sketch above: a process that dies between reserving and refunding leaks the reservation permanently, and a busy tenant can lose their whole bucket to a rolling deploy. Both of those are properties of the estimate and its lifetime rather than of the bucket.

Before either can be settled there is a question the last two chapters have made it easy to answer wrongly. Having watched request counts fail twice — blind to completion length in chapter 1, and blind to concurrency here — the natural conclusion is that the request limiter can now be deleted. Chapter 3 explains why the provider, and your own gateway, both still keep one.