A stateless HTTP service is easy to load balance because every request is roughly identical and finishes in milliseconds. An LLM replica is the opposite. One request arrives with 200 prompt tokens and asks for 30 output tokens. The next arrives with 32,000 prompt tokens and asks for 4,000. The first costs 40ms of GPU time. The second occupies a slice of GPU memory for two full minutes and will not release it until the last token is sampled. Round robin treats both as one unit of work, and that arithmetic error is what turns a healthy fleet into a fleet where half the GPUs idle while the other half return 503s.

Think of a restaurant expediter rather than a turnstile. A turnstile counts bodies. An expediter looks at what is already on each burner, how long each dish takes, and whether the sauce for the new order is already reduced and sitting in a pan. That last part matters more than anything in LLM serving, because a replica that already holds the KV cache blocks for a 3,000 token system prompt can start generating in 40ms while a cold replica needs 600ms to recompute the same attention keys and values.

Here is the target. We are fronting 64 GPU replicas across three model pools: 16 replicas of a 70B model with tensor parallelism across 2 A100 80GB cards each, 40 replicas of an 8B model on single cards, and 8 replicas hosting roughly 60 LoRA adapters for enterprise tenants. Traffic is 5,000 requests per second at peak, averaging 1,800 input tokens and 300 output tokens. The SLA is 400ms time-to-first-token (TTFT) at p99 and 50ms time-per-output-token (TPOT) at p95. The fleet costs roughly $2,600 per hour on demand, so a 20 percent utilization gap is $12.5 million a year of GPUs doing nothing.

A naive gateway fails in four specific ways. It sends a 32k-token prompt to a replica whose KV cache is at 95 percent, which forces the engine to preempt and swap out three in-flight sequences, spiking their TPOT from 24ms to 400ms. It uses least-connections, which looks correct until you notice one connection can mean 30 tokens or 4,000 tokens of remaining work. It buffers streaming responses, which destroys TTFT as a user-visible metric even when the GPU produced the first token on time. And it keeps a queued request alive after the client has already hung up, burning GPU seconds on output nobody will read. We need to solve for load signals that reflect GPU memory rather than request counts, cache affinity that survives fleet churn, and admission control that sheds work before the GPU is oversubscribed, all simultaneously.

Requirements and Constraints

Functional Requirements

• Accept OpenAI-compatible requests on POST /v1/chat/completions and POST /v1/completions, with stream=true and stream=false both supported
• Route each request to a replica in the correct model pool, resolving aliases such as gpt-fast to a concrete pool
• Support LoRA adapter selection per request, routing to hosts that already have the adapter resident
• Stream tokens back as Server-Sent Events with per-delta flush and no buffering
• Propagate client cancellation to the replica so the engine aborts the sequence and frees KV blocks
• Enforce per-tenant token quotas and concurrency limits before the request touches a GPU
• Retry idempotently on replica failure, but only before the first token has been emitted
• Emit a usage record per request with input, output, and cache-hit token counts for billing and attribution

Non-Functional Requirements

• TTFT p50 under 180ms, p99 under 400ms for prompts up to 4,000 tokens
• TPOT p95 under 50ms so a 300 token answer completes in under 15 seconds
• Gateway overhead itself under 10ms p99, excluding time spent waiting on a GPU
• Throughput of 5,000 requests per second and 1.5 million output tokens per minute
• GPU utilization above 75 percent measured as KV cache block occupancy, not nvidia-smi percent
• Availability of 99.95 percent for the gateway tier, which must survive losing any single replica without user-visible errors
• Cost under $9 per million output tokens for the 70B pool and under $0.80 for the 8B pool
• Cancellation latency under 100ms from client disconnect to KV block release

Constraints

• Replicas run vllm with PagedAttention and continuous batching enabled. We do not modify the engine, we only steer traffic into it.
• Hardware is A100 80GB. The 70B model in FP16 needs 140 GB of weights, so it cannot fit on one card and tensor parallelism degree 2 is the minimum replica size.
• Model weights are pinned per replica. We are not swapping base models at request time, only LoRA adapters.
• Out of scope: training, fine-tuning, speculative decoding inside the engine, and multi-region failover. We assume one region with three availability zones.

High-Level Architecture

Six components carry the whole design. The auth and quota layer validates the API key and decrements a token bucket in Redis, rejecting over-budget tenants in about 2ms. The admission controller decides whether the fleet has room for this request at all, and if not, whether to queue it or shed it immediately with a 429 and a Retry-After header. The replica router is the heart of the system: it scores candidate replicas on KV cache pressure, pending prefill work, and prefix cache overlap, then picks a winner. The replica registry tracks which replicas are alive, which model and adapters they host, and how much KV headroom each has. The prefix cache map records which replica most recently held the KV blocks for a given prompt prefix hash. The SSE multiplexer owns the client connection, forwards each token delta the moment it arrives, and writes the usage record when the stream terminates.

A request flows like this. The client opens a connection and sends a chat completion with stream=true. Auth resolves the tenant, checks the token bucket, and attaches a deadline derived from the request’s max_tokens and the tenant’s SLA tier. The gateway tokenizes the prompt locally with the same tokenizer the model uses, which costs about 4ms for 1,800 tokens and gives us two things we cannot get otherwise: an exact token count for quota math, and a rolling hash of the prompt prefix in 16-token blocks for cache affinity. The router looks up the prefix hash, finds that replica-03 served a request with the same 1,500-token system prompt 90 seconds ago, checks that replica-03 still has KV headroom, and dispatches there.

On the replica, vllm recognizes 96 of the 115 prompt blocks as already resident in its prefix cache, computes only the 19 new blocks, and emits the first token in 178ms instead of the 610ms a cold prefill would take. The sequence joins the running decode batch mid-flight. Every sampled token flows back over the open HTTP connection to the multiplexer, which writes it to the client as a data: frame and flushes. When the engine emits the stop reason, the multiplexer closes the stream, writes a usage_record, and updates the prefix map so the next request with that system prompt lands on the same replica.

The Token Budget and Admission Layer

This component’s job is to make sure no request reaches a GPU unless the fleet can finish it inside the caller’s deadline and the caller has the budget to pay for it.

A smart engineer’s first instinct is to rate limit on requests per second. That fails immediately in LLM serving because requests are not comparable. A tenant sending 100 requests per second with 50-token prompts uses less GPU than a tenant sending 3 requests per second with 30,000-token prompts. Rate limiting on requests lets the second tenant consume 20x their fair share while looking well behaved on the dashboard.

We limit on tokens, and we limit twice: a token bucket for sustained throughput and a concurrency semaphore for instantaneous GPU footprint. The token bucket refills at the tenant’s contracted rate. The semaphore caps how many sequences a tenant can have in flight, which is what actually bounds their KV cache consumption.

-- Atomic token bucket plus concurrency check for one LLM request. EVALSHA this.
-- KEYS[1] = tenant token bucket, KEYS[2] = tenant in-flight counter
-- ARGV: refill_rate_tps, burst_capacity, cost_tokens, max_inflight, now_ms, ttl_s
local bucket = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(bucket[1])
local ts = tonumber(bucket[2])
local rate = tonumber(ARGV[1])
local burst = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local max_inflight = tonumber(ARGV[4])
local now = tonumber(ARGV[5])

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

-- refill based on elapsed wall time, clamped at burst capacity
local elapsed = math.max(0, now - ts) / 1000.0
tokens = math.min(burst, tokens + elapsed * rate)

if tokens < cost then
  local deficit = cost - tokens
  local retry_after = math.ceil(deficit / rate)
  return {0, 'quota', retry_after}
end

local inflight = tonumber(redis.call('GET', KEYS[2]) or '0')
if inflight >= max_inflight then
  return {0, 'concurrency', 1}
end

tokens = tokens - cost
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], tonumber(ARGV[6]))
redis.call('INCR', KEYS[2])
redis.call('EXPIRE', KEYS[2], 300)
return {1, 'ok', 0}

The cost we charge is input_tokens + max_tokens, a pessimistic reservation. When the stream ends we refund the difference between max_tokens and the actual output count. Without the reservation, a tenant can open 500 streams that each declare max_tokens: 8000 and pass the quota check while committing 4 million tokens of future work.

Admission control sits after quota and answers a different question: does the fleet have room right now. We compute a fleet-wide queue budget in token units, which is the sum of free KV blocks across healthy replicas in the target pool multiplied by block size, minus the tokens already reserved by queued requests.

# Fleet-level admission decision using KV headroom rather than request counts.
import time
from dataclasses import dataclass

BLOCK_SIZE = 16  # tokens per PagedAttention block, must match vllm --block-size

@dataclass
class ReplicaState:
    replica_id: str
    total_blocks: int
    used_blocks: int
    queue_tokens: int      # pending prefill tokens not yet started
    decode_tps: float      # measured tokens/sec/seq on this replica
    healthy: bool
    updated_ms: int

def free_tokens(r: ReplicaState) -> int:
    return max(0, (r.total_blocks - r.used_blocks) * BLOCK_SIZE)

class AdmissionController:
    def __init__(self, headroom_ratio: float = 0.15, stale_ms: int = 5000):
        # keep 15% of KV free so continuous batching never has to preempt
        self.headroom_ratio = headroom_ratio
        self.stale_ms = stale_ms

    def admit(self, pool: list[ReplicaState], need_tokens: int,
              queued_tokens: int, deadline_ms: int) -> tuple[bool, str, int]:
        now = int(time.time() * 1000)
        live = [r for r in pool if r.healthy and now - r.updated_ms < self.stale_ms]
        if not live:
            return False, "no_healthy_replica", 5

        capacity = sum(free_tokens(r) for r in live)
        reserve = int(sum(r.total_blocks * BLOCK_SIZE for r in live) * self.headroom_ratio)
        available = capacity - reserve - queued_tokens

        if need_tokens > available:
            # estimate drain time from slowest observed decode rate
            slowest = min((r.decode_tps for r in live), default=1.0)
            wait_ms = int((need_tokens - available) / max(slowest, 1.0) * 1000)
            if wait_ms > deadline_ms:
                return False, "deadline_exceeded", max(1, wait_ms // 1000)
            return True, "queued", wait_ms
        return True, "admitted", 0

The headroom_ratio is the parameter people get wrong. Set it to zero and you maximize throughput on paper, but the engine starts preempting sequences: vllm swaps a running sequence’s KV blocks to CPU memory, and when it swaps back the sequence’s TPOT jumps by an order of magnitude. Set it to 0.4 and you leave 32 GB of A100 memory unused on every card. We landed on 0.15 by measuring preemption count against block occupancy and taking the knee of the curve.