Applying token bucket in an LLM gateway

By Ivo Donker — compiled with AI support (Claude & Gemini) · Last updated: 6 August 2026

Managing the flow of requests to large language models (LLMs) presents developers with unique challenges. Where traditional API gateways get by with counting requests per minute, processing language models requires a fundamentally different approach. Handling a short query costs a fraction of the compute needed to summarize a complete document. To prevent overload and unexpected costs, applying the token bucket algorithm within the LLM gateway is the appropriate method.

In this article we cover how the token bucket works, why standard request limits fall short, how to handle uncertain input and output lengths, and how to implement this algorithm at scale within a distributed architecture.

Why standard request limits fall short

Traditional API gateways largely use request-based rate limiting, such as a maximum of one hundred requests per minute (RPM). With a standard REST API this produces a predictable load, because every API endpoint demands a comparable amount of compute or database capacity.

With language models that assumption is invalid. The real load on an LLM infrastructure and the costs tied to it are determined not by the number of HTTP calls but by the number of tokens processed (both input and output tokens). Two successive requests to the same gateway can differ enormously:

• Call A: A simple user question of 15 tokens resulting in a short answer of 20 tokens (35 tokens total).
• Call B: A request comprising an extensive system prompt, several documents as context and a generated analysis of 3,000 tokens (35,000 tokens total).

When a gateway limits purely on requests, call A counts just as heavily as call B. This lets a single user with sizeable prompts exhaust the full capacity of an upstream API provider or run up enormous bills while formally staying within their request quota. It is therefore necessary to limit on actual consumption of the underlying resource: the number of tokens per unit of time (tokens per minute, or TPM).

The token bucket concept in plain language

The token bucket algorithm is a proven mechanism from the networking world for regulating data flows. You can picture it as a physical bucket into which digital tokens are poured at a fixed, constant rate.

The algorithm works on three fixed principles:

1. Bucket capacity (burst size): The bucket has a maximum content. Above that level the bucket overflows; surplus tokens added are lost. This determines the maximum peak load that may be consumed at once.
2. Refill rate: Tokens are added to the bucket continuously at a preset speed, for example a fixed number of tokens per second. This rate determines average throughput over the long run.
3. Consumption up front: Before a request is forwarded to the LLM, the client has to take the required number of tokens out of the bucket. If enough tokens are present, the amount is deducted and the request proceeds. If there are too few, the request is refused or queued.

The great advantage of the token bucket is its flexibility: it allows short, sharp peaks in traffic as long as there is still stock in the bucket, but over a longer period it enforces the average refill rate without mercy.

Bucket size as a crucial design choice

The balance between maximum bucket capacity and refill rate is the most important parameter when setting up an LLM gateway. The choices you make here have a direct impact on user experience and backend stability.

When determining bucket capacity, analyze the application's expected pattern. For an interactive chat application a relatively low bucket capacity with a fast refill is more suitable, because requests are small and frequent. For background processing tasks (batch processing), a larger bucket capacity is required in order to accept large documents in one go, with processing spread out over a longer period afterwards.

The core problem with LLMs: uncertainty up front

In a traditional networking context, the gateway knows exactly how many bytes a packet contains before letting it through. That does not hold for LLM calls. The length of the input prompt can be computed accurately with a tokenizer, but the number of output tokens the model will generate is not known with certainty in advance.

To solve this, advanced gateways use a reservation-and-settlement cycle. This cycle consists of three steps:

In situations where the API provider imposes no limit through max_tokens, the gateway is forced to estimate output length based on historical data from comparable prompts. Designing these estimates carefully keeps the bucket from being blocked needlessly long by excessive reservations.

For a broad overview of how different vendors consolidate tokens and consumption, see the article on normalizing token usage across providers is worth consulting.

Handling a negative bucket balance

When the initial estimate of output tokens was too low, settlement afterwards can lead to a notable situation: actual consumption turns out larger than the amount reserved, pushing the bucket balance below zero.

Aborting an already started or completed streaming response the moment the bucket goes negative is explicitly not good practice. It produces a poor user experience and wasted compute, since the upstream provider bills for the already generated tokens regardless.

The correct handling of a negative bucket balance is as follows:

• Accept the negative value: Let the bucket balance drop below zero (to -200 tokens, for instance).
• Block follow-up requests: As long as the bucket balance is negative, new requests from that client are refused or queued.
• Recover through refill: Only when the automatic refill rate has brought the balance back above the threshold required for a new request is the client admitted again.

This way the system collects the overrun afterwards, without abruptly interrupting running processes.

Hierarchical buckets: multiple levels side by side

In a professional production environment, a single bucket per user does not suffice. To prevent overload at different layers of the chain, an LLM gateway applies hierarchical limits. A request has to be approved by several buckets in sequence before it is sent to the upstream provider.

A common layering covers the following levels:

1. User level (per user/API key): Prevents a single individual user from consuming an organization's or application's budget.
2. Team or department level (per tenant/group): Guarantees that a specific team does not claim the whole organization's capacity.
3. Provider level (per provider/model): Protects the central account with the model vendor (such as OpenAI or Anthropic). This level keeps the organization as a whole from exceeding the TPM limits imposed by the vendor.

On every incoming call the gateway checks whether all applicable buckets have enough capacity available for the initial reservation. If even one bucket has insufficient balance, the request is held back. If you are considering setting up such an architecture on your own infrastructure, read more in the guide on hosting your own LLM gateway.

Streaming responses and premature termination

When using streaming (server-sent events), tokens are sent one by one from the model vendor to the client. This lets the gateway track consumption live during generation.

If no hard reservation has been made up front, or when a client is working with a very tight budget, the gateway can count incoming stream chunks. As soon as the permitted limit within the session is reached, the gateway steps in:

• Controlled closure: The gateway stops forwarding new tokens from the provider to the client.
• Send a closing signal: The gateway sends a clean closing message (such as a specific finish_reason: "length" or a custom error message) to the client, so the client application knows the answer was cut off because a limit was reached.
• Upstream cancellation: The HTTP connection with the upstream provider is severed immediately to stop the pointless generation of further tokens and avoid unnecessary cost.

For deeper insight into the networking aspects of this process, we refer to the guide on streaming responses.

Distributed storage and atomic updates

Modern API gateways rarely run on a single server; they are scaled across multiple instances or containers. This means the state of the token buckets cannot be kept in the local memory of a single instance but has to live in a central, fast storage system such as Redis or KeyDB.

In a distributed architecture there is a risk of race conditions: two gateway instances read a bucket balance of 500 tokens simultaneously, both approve a request of 400 tokens, and then write back an incorrect final balance. The limit is thereby exceeded.

To prevent this, all operations on the bucket have to be performed atomically . In practice this is achieved in two ways:

• Lua scripts inside the database: Computing the refilled tokens based on elapsed time, checking the balance and deducting the reserved tokens all happen within a single Lua script directly on the in-memory database. This guarantees that no other instance can change the bucket balance during the computation.
• Lazy evaluation: Instead of running a background process that refills millions of buckets every second, the bucket balance is only computed the moment a request comes in. The script takes the previous state, computes how much time has passed since the last request, multiplies that time by the refill rate, adds it to the old balance (capped at bucket capacity) and then performs the consumption.

What do you send back to the client?

When a request is refused because a bucket is empty, the gateway has to give the client enough information to handle the situation gracefully. This keeps stuck clients from needlessly hammering the gateway with new calls.

A well-designed gateway returns the standard HTTP status code 429 Too Many Requests, supplemented with specific HTTP headers:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 12
X-RateLimit-Limit-Tokens: 100000
X-RateLimit-Remaining-Tokens: 0
X-RateLimit-Reset-Tokens: 12s

{
  "error": {
    "code": "rate_limit_exceeded",
    "message": "Token capaciteit overschreden. Probeer het opnieuw over 12 seconden.",
    "type": "tokens"
  }
}

The fields in this response each have a clear function:

• Retry-After: The minimum number of seconds the client has to wait before the bucket has refilled enough for an average call.
• X-RateLimit-Remaining-Tokens: Current available capacity (zero in this case).
• X-RateLimit-Reset-Tokens: The exact time after which the bucket is fully refilled.

When the client interprets these headers correctly, it can insert an automated pause. For strategic patterns around retries, see the article on retries and backoff.

Relation to provider budgets: limit conservatively

A crucial mistake when setting up your own LLM gateway is copying exactly the limits the upstream provider (such as OpenAI or Anthropic) has set on your account. If a provider gives you a limit of 150,000 TPM, it is unwise to set the gateway's internal token buckets to 150,000 TPM as well.

There are several reasons to set your gateway's internal limits more conservatively than the provider's hard limits:

• Network latency and synchronization delay: There is always a small delay between the moment of measurement in the gateway and processing at the provider. Under extreme peaks this can lead to a slight overrun on the provider's side.
• Tokenizer differences: If the gateway uses a fast, approximate tokenizer to compute input, a small deviation can arise relative to the provider's official tokenizer.
• Buffer for administrative tasks: By keeping a margin (setting the gateway to 85-90% of the provider limit, for instance), you preserve capacity for critical system prompts, internal monitoring or administrative tasks that must never be blocked.

Cost per task also plays an important role in determining the financial ceilings you build into the gateway per user or team. More information on cost allocation can be found in the overview of cost per task.

Conclusion

The token bucket algorithm is an indispensable part of a modern LLM gateway. By steering on tokens instead of requests, you match the variable load inherent to language models. Combining an initial reservation with settlement afterwards, absorbing negative bucket balances and performing state synchronization atomically in Redis produces a robust infrastructure. By feeding clear limits and accurate HTTP headers back to the client, the entire application chain stays stable, predictable and financially manageable.

Further reading

• Normalizing token usage across providers
• Hosting your own LLM gateway
• Handling streaming responses
• Retry and backoff strategies
• Analyzing cost per task