Prefix cache affinity routing for multi-replica LLM serving. Route each request to the replica that already holds its prompt prefix, without creating hotspots.
Production LLM deployments run many replicas behind a gateway. Each replica keeps a radix KV cache, so a prompt prefix it has already processed (a system prompt, a tool schema, a few shot block) is served from cache instead of being prefilled again. That cached prefill is usually the largest single cost in time to first token.
The default gateway policy is round robin, or its slightly smarter cousin least loaded. Both are cache blind. They scatter a tenant's requests across every replica, so the same long prefix is prefilled once per replica instead of once per cluster. When the combined working set of prefixes is larger than a single replica's cache, every replica thrashes: it evicts one tenant's prefix to make room for another, then has to recompute it on the next request. The cache exists but barely helps.
The naive fix, route by longest cached prefix, recovers the cache but concentrates a heavy tenant onto one replica and risks a queueing hotspot.
prefixroute is a small, dependency light library and benchmark that models this exact situation and provides a routing policy that fixes it:
RadixCache: a token level radix (prefix) tree per replica with LRU eviction under a fixed token budget. Matching a prompt returns how many leading tokens are already cached; frequently matched prefixes are protected from eviction.- Four routing policies behind one interface:
RoundRobin,LeastLoaded,Affinity, andAffinityBalanced. AffinityBalanced(the recommended policy) prefers the replica with the longest cached prefix but refuses to pile onto a replica that is already much busier than the least busy one, falling back to load balancing. It keeps most of the cache benefit and bounds the tail.- A discrete event
simulatethat charges prefill time for uncached tokens only, queues requests per replica, and reports mean and p99 time to first token, cache hit rate, and total prefill tokens. - A
workloadgenerator that produces a realistic multi-tenant trace: shared per tenant prefixes, unique user turns, Poisson arrivals, and skewed (Zipf) tenant popularity.
Most prefix cache work optimizes a single prompt or a single replica. The cross replica routing decision is where a multi replica cluster actually wins or loses its cache, and it is usually left to a cache blind load balancer. This project isolates that decision, shows the cost of getting it wrong, and provides a routing policy that captures the cache benefit while staying safe under skewed load. The naive affinity policy is included on purpose, so the load guard in AffinityBalanced can be measured rather than assumed.
FigJam board: https://www.figma.com/board/c4TfGM2EzzgO2lQpAEnJ39
The diagram shows the flow from the multi-tenant workload generator, through the router and its four policies, into the per replica FIFO simulator and radix caches, and out to the metrics and the comparison chart.
flowchart TD
A["Request arrives (tenant prefix + unique turn)"] --> B["Policy.choose(tokens, replicas, now)"]
B --> C{"For each replica: cached prefix length and projected load"}
C --> D["Pick best cached prefix within the load guard"]
D --> E["Replica radix cache: match -> cached tokens"]
E --> F["Prefill only the uncached tokens"]
F --> G["TTFT = queue wait + uncached tokens / prefill rate"]
G --> H["Insert full prompt into the replica cache, evict LRU leaves"]
The metric is time to first token (TTFT), which for a cold prompt is dominated by prefilling the uncached prefix. The trace is 4000 requests across 12 tenants and 4 replicas, each replica holding a 4000 token radix cache, with skewed tenant popularity and Poisson arrivals. All policies run on the identical trace.
| Policy | Mean TTFT | p99 TTFT | Prefix cache hit rate | Prefill tokens |
|---|---|---|---|---|
| Round robin (baseline) | 182.9 ms | 631.1 ms | 56.3% | 1,574,980 |
| Least loaded | 87.6 ms | 281.4 ms | 56.2% | 1,576,552 |
| Affinity (naive) | 17.7 ms | 100.0 ms | 85.7% | 513,810 |
| Affinity balanced (prefixroute) | 17.6 ms | 94.8 ms | 83.3% | 599,590 |
The baseline is round robin, the common cache blind gateway default. Under it the cluster wide working set of tenant prefixes does not fit in a single replica cache, so the hit rate sits at 56% and the replicas spend most of their time recomputing prefixes that another replica already has. Switching to prefix affinity routing raises the hit rate to 83% and cuts the prefill work by more than half, which drops mean TTFT from 182.9 ms to 17.6 ms (a 90% reduction) and p99 TTFT from 631.1 ms to 94.8 ms. Against the stronger least loaded baseline the mean TTFT reduction is 80%. The balanced policy matches naive affinity on mean TTFT and beats it on p99, because the load guard keeps a heavy tenant from queueing behind itself on a single replica.
Numbers above are produced by running examples/benchmark.py; they are not hand entered. Re-running regenerates docs/before_after.png and docs/results.json.
git clone https://github.com/joelvarun/prefixroute.git
cd prefixroute
pip install -r requirements.txt
# Run the benchmark: prints the table, regenerates the chart and results.json
python examples/benchmark.py
# Minimal library usage example
python examples/quickstart.py
# Unit tests (radix cache correctness, eviction, routing policies)
python tests/test_prefixroute.pyUse the library directly:
from prefixroute import AffinityBalanced, RadixCache, Replica
replicas = [Replica(RadixCache(capacity_tokens=20000)) for _ in range(4)]
policy = AffinityBalanced(load_slack_s=0.05)
tokens = system_prompt_token_ids + user_turn_token_ids
idx = policy.choose(tokens, replicas, now=current_time_seconds)
# ... serve on replicas[idx], then:
replicas[idx].cache.insert(tokens)From python examples/benchmark.py:
trace: 4000 requests, 12 tenants, 4 replicas, 4000 token cache per replica
round_robin mean_ttft= 182.9 ms p99_ttft= 631.1 ms prefill_tokens= 1,574,980 hit_rate= 56.3% imbalance= 1.03
least_loaded mean_ttft= 87.6 ms p99_ttft= 281.4 ms prefill_tokens= 1,576,552 hit_rate= 56.2% imbalance= 1.05
affinity mean_ttft= 17.7 ms p99_ttft= 100.0 ms prefill_tokens= 513,810 hit_rate= 85.7% imbalance= 1.31
affinity_balanced mean_ttft= 17.6 ms p99_ttft= 94.8 ms prefill_tokens= 599,590 hit_rate= 83.3% imbalance= 1.46
From python examples/quickstart.py:
request 0: routed to replica 0 cached_prefix= 0 tokens prefill= 53 tokens
request 1: routed to replica 0 cached_prefix= 50 tokens prefill= 2 tokens
request 2: routed to replica 0 cached_prefix= 50 tokens prefill= 4 tokens
The shared 50 token system prompt is prefilled once and then served from cache on every later request routed to the same replica.
The simulator is compute oriented. It charges prefill time proportional to uncached prefix tokens and serves each replica as a single FIFO queue, which captures the first order behavior of time to first token under prefix caching. It does not model decode time, paged attention memory limits, tensor parallel sharding, or network latency. The point is to isolate the routing decision and its effect on cache reuse, and the relative ordering of the policies is what the benchmark establishes.
MIT. See LICENSE.