Rate-Limit LLM API Calls Per Tenant Without Dropping Requests

For: A backend engineer at a Series A B2B SaaS startup whose product just embedded an LLM feature — one power-user tenant is burning through the shared OpenAI quota and causing 429 errors for everyone else, and their current fix is a global rate limiter that treats all tenants identically

If one tenant is burning your shared OpenAI quota and starving the rest, the fix is a per-tenant token bucket keyed on estimated tokens-per-minute, not requests-per-minute, with excess calls parked in a bounded per-tenant queue instead of returned as a naked 429. Below is a runnable Python + Redis implementation you can drop into a FastAPI service in an afternoon.

The non-obvious part: request-count limiters look fair but are not. Tenant A sending 60 requests/min with 200-token prompts consumes ~12k tokens. Tenant B sending 60 requests/min with 6k-token prompts consumes 360k tokens and torches your OpenAI org quota. If you cap both at 60 RPM, you have punished Tenant A for Tenant B’s behaviour. Meter tokens.

What we’re building

• A Redis-backed token bucket per tenant, refilled at a configured tokens-per-minute rate.
• An estimator that predicts prompt + completion tokens before the API call using tiktoken.
• A bounded async queue per tenant so bursts wait a few seconds instead of failing.
• A reconciler that credits back unused tokens (or debits extra) once the real usage returns from OpenAI.

Tradeoffs up front, because you should know what this is bad at:

• Latency floor rises under sustained overload. Queued requests wait. If a tenant sends 10× their steady-state, p99 will climb before backpressure kicks in.
• Estimator is approximate. max_tokens is an upper bound; real completions are usually shorter. The reconciler fixes drift but the bucket briefly under-counts.
• Not a fairness scheduler. Within a tenant, it’s FIFO. If you need priority tiers per user, you’ll layer that on top.

Prerequisites

• Python 3.10+
• Redis 6.2+ (we use EVAL for atomic bucket updates)
• pip install fastapi uvicorn redis tiktoken openai httpx
• An OPENAI_API_KEY in your env

Step 1: Model the bucket in Redis with a Lua script

We need atomic “check-and-decrement” semantics. Two concurrent requests must not both see 5000 tokens available and both subtract 3000. Lua on Redis is single-threaded per key, which gives us the atomicity for free.

Create bucket.lua:

-- KEYS[1] = bucket key, e.g. tb:tenant:acme
-- ARGV[1] = capacity (max tokens)
-- ARGV[2] = refill_rate (tokens per second)
-- ARGV[3] = now (unix seconds, float)
-- ARGV[4] = requested tokens

local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1])
local ts = tonumber(data[2])
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local want = tonumber(ARGV[4])

if tokens == nil then
  tokens = capacity
  ts = now
end

local delta = math.max(0, now - ts) * rate
tokens = math.min(capacity, tokens + delta)

local allowed = 0
local wait = 0
if tokens >= want then
  tokens = tokens - want
  allowed = 1
else
  wait = (want - tokens) / rate
end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], 3600)

return {allowed, tostring(tokens), tostring(wait)}

The script returns whether the request was allowed, remaining tokens, and (if denied) how many seconds until enough tokens refill. That wait value is the whole reason we can queue instead of 429.

Step 2: Wrap it in a Python client

Create limiter.py:

import time
import asyncio
import redis.asyncio as redis

class TokenBucket:
    def __init__(self, r: redis.Redis, script_src: str):
        self.r = r
        self.script = r.register_script(script_src)

    async def consume(self, tenant: str, tokens: int,
                      capacity: int, rate_per_sec: float):
        key = f"tb:tenant:{tenant}"
        allowed, remaining, wait = await self.script(
            keys=[key],
            args=[capacity, rate_per_sec, time.time(), tokens],
        )
        return int(allowed) == 1, float(remaining), float(wait)

    async def acquire(self, tenant, tokens, capacity, rate_per_sec,
                      max_wait=15.0):
        deadline = time.time() + max_wait
        while True:
            ok, _, wait = await self.consume(tenant, tokens, capacity, rate_per_sec)
            if ok:
                return True
            if time.time() + wait > deadline:
                return False
            await asyncio.sleep(min(wait, 0.5))

Two entry points: consume for a non-blocking check, acquire for “wait up to N seconds, then give up.” The 500ms sleep cap prevents thundering herds — every waiter re-checks at slightly different intervals rather than all waking at exactly wait seconds.

Step 3: Estimate tokens before the call

Use tiktoken to count prompt tokens, then add the caller’s max_tokens as the completion upper bound. This is the reserved cost; we’ll reconcile with actual usage after.

import tiktoken

_enc = tiktoken.encoding_for_model("gpt-4o-mini")

def estimate_tokens(messages: list[dict], max_completion: int) -> int:
    # rough per-message overhead the OpenAI cookbook documents as ~4 tokens
    prompt = sum(len(_enc.encode(m["content"])) + 4 for m in messages)
    return prompt + max_completion

Yes, this over-reserves. That is deliberate. It is safer to under-utilise the bucket by 10% than to blow through OpenAI’s org-level TPM limit and get everyone 429’d by the upstream.

Step 4: Wire it into a FastAPI endpoint

Create app.py:

import os, pathlib, asyncio
from fastapi import FastAPI, HTTPException, Header
from pydantic import BaseModel
import redis.asyncio as redis
import httpx
from limiter import TokenBucket
from estimator import estimate_tokens

app = FastAPI()
r = redis.from_url("redis://localhost:6379", decode_responses=True)
script_src = pathlib.Path("bucket.lua").read_text()
bucket = TokenBucket(r, script_src)

# per-tenant config — load from DB in production
TENANT_LIMITS = {
    "acme":    {"capacity": 40_000, "rate": 40_000 / 60},   # 40k TPM
    "globex":  {"capacity": 10_000, "rate": 10_000 / 60},   # 10k TPM
    "default": {"capacity":  5_000, "rate":  5_000 / 60},
}

class ChatReq(BaseModel):
    messages: list[dict]
    max_tokens: int = 512
    model: str = "gpt-4o-mini"

@app.post("/chat")
async def chat(req: ChatReq, x_tenant: str = Header(...)):
    cfg = TENANT_LIMITS.get(x_tenant, TENANT_LIMITS["default"])
    reserved = estimate_tokens(req.messages, req.max_tokens)

    got = await bucket.acquire(
        tenant=x_tenant,
        tokens=reserved,
        capacity=cfg["capacity"],
        rate_per_sec=cfg["rate"],
        max_wait=10.0,
    )
    if not got:
        raise HTTPException(429, {
            "error": "tenant_quota_exhausted",
            "retry_after_hint_seconds": 10,
        })

    async with httpx.AsyncClient(timeout=60) as client:
        resp = await client.post(
            "https://api.openai.com/v1/chat/completions",
            headers={"Authorization": f"Bearer {os.environ['OPENAI_API_KEY']}"},
            json={"model": req.model, "messages": req.messages,
                  "max_tokens": req.max_tokens},
        )
    data = resp.json()

    # Step 5 happens here — reconcile
    actual = data.get("usage", {}).get("total_tokens", reserved)
    drift = reserved - actual  # positive means we over-reserved
    if drift > 0:
        # credit back the unused tokens
        await bucket.consume(x_tenant, -drift, cfg["capacity"], cfg["rate"])

    return data

Step 5: The reconciliation trick

Notice the last block. We reserved reserved tokens optimistically. OpenAI returns usage.total_tokens. If we over-reserved by 300 tokens, we credit them back by calling consume with a negative value. The Lua script handles this cleanly — subtracting a negative is addition, and math.min(capacity, ...) caps the refund.

If actual usage exceeded our estimate (rare but happens with tool calls or when your estimator underweights system prompts), drift is negative and we skip the credit. The next request eats the debt naturally because the bucket is already lower than it should be.

Step 6: Run it and prove it works

Start Redis and the app:

redis-server --daemonize yes
uvicorn app:app --port 8000

In another terminal, hammer it as one tenant:

for i in $(seq 1 20); do
  curl -s -X POST http://localhost:8000/chat \
    -H "X-Tenant: acme" \
    -H "Content-Type: application/json" \
    -d '{"messages":[{"role":"user","content":"say hi"}],"max_tokens":50}' \
    -o /dev/null -w "%{http_code} %{time_total}s\n" &
done; wait

Expected output (abridged):

200 0.812s
200 0.847s
200 1.203s
200 2.740s
200 3.918s
...
429 10.041s   # only after ~10s of queueing

The key observation: most requests succeed with elevated latency instead of failing. Only when a tenant exceeds their bucket and the queue wait exceeds max_wait do you return 429. Meanwhile, a second tenant hitting the same server:

curl -X POST http://localhost:8000/chat -H "X-Tenant: globex" ...
200 0.611s   # unaffected by acme's storm

That is the whole point. Noisy neighbour isolated.

Step 7: Observability you actually need

Emit these four metrics or you’re flying blind:

• llm_bucket_remaining{tenant} — gauge, sampled every 5s. Alerts when a tenant sits at zero for >60s.
• llm_queue_wait_seconds{tenant} — histogram of the wait value returned by Lua. p95 is your early warning.
• llm_estimate_drift_tokens{tenant} — reserved - actual. Persistent positive drift means you’re over-reserving; tune down max_tokens defaults.
• llm_tenant_rejections_total{tenant} — counter of true 429s. Should be near zero for healthy tenants.

The drift metric is the one nobody adds and everyone regrets. Without it you cannot tell whether your bucket is sized wrong or your estimator is lying.

Common errors and troubleshooting

NOSCRIPT No matching script

Redis flushed the script cache (restart, failover). register_script handles reloads automatically on newer redis-py, but if you cached the SHA yourself, catch NOSCRIPT and re-EVAL.

Bucket never refills

You’re passing rate as tokens-per-minute instead of tokens-per-second. The Lua script expects per-second. A 60k TPM bucket has rate = 1000.

Every request queues even when idle

Your capacity is smaller than a single request’s reserved tokens. If max_tokens=4096 and capacity is 3000, the bucket can never satisfy one call. Set capacity >= max_per_request_tokens.

Latency spikes under load even for small tenants

Check that you’re using redis.asyncio and not the sync client. A sync Redis call inside an async handler blocks the event loop and one tenant’s wait stalls everyone.

Tenants report inconsistent quota with multi-region deployments

Each region has its own Redis. Either accept regional quotas (usually fine) or move to a single global Redis with the tradeoff of cross-region latency on every request. Do not try to sync buckets across regions in application code — the race conditions will haunt you.

What to do next

The pattern above solves the immediate 429 storm. Three enhancements worth considering once it’s stable:

1. Priority lanes within a tenant. Interactive chat should preempt background summarisation. Add a second bucket per tenant tagged interactive vs batch and drain from a priority queue.
2. Model-aware buckets. GPT-4o and gpt-4o-mini have different upstream TPM limits. Bucket per (tenant, model) pair.
3. Cost-aware, not just token-aware. Once you have several models, meter USD-equivalent per tenant so a tenant can’t bypass their budget by moving to a more expensive model.

If you’re building multi-tenant LLM features in a B2B SaaS and want a second pair of eyes on the architecture — queue design, tenant tiering, cost attribution — the team at CodeNicely’s AI studio has shipped this pattern in production for several scaleup clients. But the code above is enough to unblock you today.

Frequently Asked Questions

Why meter tokens instead of requests for LLM rate limiting?

Because OpenAI, Anthropic, and every other major LLM provider enforces their own limits primarily in tokens-per-minute, not requests-per-minute. A request-count limiter lets tenants with long prompts consume 10–30× more upstream quota than tenants with short prompts while looking identical to your limiter. Metering estimated tokens aligns your fairness model with the actual constrained resource.

What’s the difference between a token bucket and a leaky bucket for this use case?

A token bucket allows short bursts up to the bucket capacity, then throttles to the refill rate — which matches how chat traffic actually behaves (bursty). A leaky bucket smooths everything to a constant rate, which adds unnecessary latency for tenants who are within their fair share but happen to send two requests back-to-back. Token bucket is almost always the right choice for LLM APIs.

Should I queue requests in Redis or in memory?

The bucket state must be in Redis so multiple app instances agree. The wait itself (the asyncio.sleep) can and should happen in the app process — you do not want a separate queue worker for this. If you need durability (e.g. background batch jobs that must not be lost on restart), use a real job queue like Celery or SQS in front of the limiter, not as a replacement for it.

How do I set the right TPM limit per tenant?

Start with the tenant’s pricing tier: multiply their monthly LLM budget by a peak-to-average ratio (2–4× is typical) and divide by minutes in a month. Then instrument for two weeks and adjust based on the llm_queue_wait_seconds p95. If p95 wait exceeds 2 seconds regularly, either raise their cap or their plan price.

Does this work with streaming responses?

Yes, with one adjustment: reconcile after the stream completes, not before you start it. Reserve tokens up front, stream normally, and when the final chunk arrives with usage data (OpenAI sends this in the last SSE event when you pass stream_options: {include_usage: true}), credit back the drift. Do not try to meter mid-stream — the coordination cost isn’t worth it.