Cache-Aware Load Balancing in Production LLM Serving: Architecture, Prefix Affinity, and Multi-Replica Routing Trade-Offs

When scaling large language model inference across multiple GPU worker nodes, standard Layer-4 and Layer-7 load balancing algorithms create an unseen performance cliff. Round-robin, least-connections, and random routing distribute HTTP/gRPC requests uniformly across compute replicas. However, modern LLM inference engines rely on prompt caching mechanisms, such as vLLM Automatic Prefix Caching and SGLang RadixAttention, to reuse key-value (KV) activations from previous requests.

When an uninformed load balancer disperses multi-turn conversations, shared system prompts, or agent tool schemas across independent GPU workers, cache locality collapses. A worker receiving a prompt with a 4,000-token prefix must recompute the entire KV cache from scratch if that specific worker did not process the previous turn.

Cache-aware load balancing solves this bottleneck by tracking prompt prefixes and worker cache states at the routing layer, steering requests toward GPU replicas that already hold the matching KV blocks.

Why Generic Load Balancers Break Prefix Caching

In autoregressive transformer serving, inference consists of two distinct computational phases: the prefill phase (processing input prompt tokens) and the decode phase (generating output tokens one by one). Prefill is computationally intensive and memory-bandwidth heavy, scaling quadratically or linearly with prompt length.

To minimize redundant prefill computation, modern serving engines store computed KV tensors in GPU High Bandwidth Memory (HBM):

• Hash-Based Block Matching (vLLM APC): Prompts are split into fixed-size logical token blocks (typically 16 or 32 tokens). The engine hashes the token sequence of each block and checks its internal hash table for pre-computed KV tensors.
• Radix Trees (SGLang RadixAttention): The engine maintains a radix tree in host memory where edges represent token sequences and nodes point to cached GPU memory pages. It identifies the longest matching prefix and reuses those tensors directly.

In a single-GPU deployment, repeated prompts achieve high prefix cache reuse. However, when horizontally scaling to N replicas behind a standard round-robin load balancer, the probability that a follow-up request with an identical prefix lands on the same GPU replica drops to 1/N. For an 8-replica cluster, cache hit rates degrade by up to 87.5%, forcing GPUs to spend cycles re-running matrix multiplications for identical text prefixes.

Cache-Aware Routing Architectures

Production systems use three primary architectural patterns to restore cache locality across distributed clusters.

1. Approximate Prefix Trees (Router-Side Tries)

In the approximate prefix tree model, the load balancer maintains an internal Trie or Radix Tree representing the cached prefixes across all connected worker replicas.

• Request Ingestion: When a new prompt arrives at the router, the router tokenizes or hashes prefix chunks of the text and traverses its local prefix tree.
• Affinity Lookup: The tree identifies which worker has the longest shared prefix match.
• State Simulation: Once the router forwards the request to the target worker, it inserts the new sequence into that worker's virtual cache branch within the tree.
• Eviction Emulation: The router tracks an approximate Least Recently Used (LRU) policy to prune virtual nodes when a worker's simulated memory capacity is reached.

This approach requires no continuous telemetry traffic from the GPU workers, eliminating network coordination overhead. Implementations like the LMSYS SGLang Router and Ray Serve PrefixCacheAffinityRouter utilize this design.

Incoming Request: [System Prompt (2k)] + [RAG Context (4k)] + [User Query]
                                  │
                     ┌────────────┴────────────┐
                     ▼                         ▼
            Router Prefix Tree        Worker Queue Metrics
                     │                         │
            Worker 1: 6k match        Worker 1: Queue Depth = 2
            Worker 2: 2k match        Worker 2: Queue Depth = 0
            Worker 3: 0k match        Worker 3: Queue Depth = 1
                     │
                     ▼
         Routing Decision Engine:
         Score = (0.7 * MatchTokens) - (0.3 * QueueLatency)
                     │
                     ▼
             Route to Worker 1

2. Event-Driven Synchronized KV Registries

In high-throughput environments with dynamic memory pressure, simulated LRU trees can drift from physical GPU memory reality due to chunked prefill preemptions, memory fragmentation, or unexpected sequence terminations.

Event-driven routing introduces an explicit control plane:

• GPU workers emit lightweight KV events (such as BlockAllocated and BlockEvicted) over Unix domain sockets or zero-copy IPC to the local router daemon.
• The router updates a shared global memory index with exact block hashes.
• Routing decisions reflect verified physical GPU memory occupancy rather than probabilistic simulation.

While event-driven architectures offer exact prefix hit prediction, they introduce message overhead and require fast synchronization to prevent control plane bottlenecks under high request concurrency.

3. Disaggregated Cache-Centric Architectures (Mooncake and TokenLake)

More advanced production frameworks decouple compute scheduling from memory location entirely. In Moonshot AI's Mooncake serving architecture, prefill and decode instances are physically disaggregated.

Mooncake utilizes a global scheduler ("Conductor") that treats CPU DRAM, local NVMe SSDs, and remote GPU HBM as a unified distributed KV cache pool. If a target worker lacks the necessary prefix in local VRAM, the transfer engine pulls the cached KV blocks over high-speed RDMA from adjacent nodes rather than recomputing the prefill tokens on the GPU.

The Locality vs. Load Balancing Dilemma

A pure cache-affinity routing policy introduces an operational vulnerability known as the hot prefix problem. If thousands of concurrent client requests share an identical system prompt or document context (common in customer support bots or RAG pipelines), a naive cache-affinity router directs all traffic to the single replica that initially cached that prefix.

This results in severe queue contention, increased Time-To-First-Token (TTFT) due to queue waiting time, and idle GPU capacity across the rest of the cluster.

Multi-Tier Routing and Scoring Heuristics

Production routers mitigate hot prefix bottlenecks through multi-tier scheduling algorithms:

1. Imbalance Thresholds: The router evaluates the queue depth of the highest-affinity worker against cluster averages. If worker queue depth exceeds the cluster mean by a configured threshold, the router bypasses cache affinity and sheds load to a colder replica.
2. Composite Utility Functions: Schedulers calculate a composite routing cost for each replica: Score = (alpha * EstimatedCacheHitRatio) - (beta * QueueWaitPenalty). If the compute time saved by reusing cached KV tokens is smaller than the queuing delay on the hot worker, the router deliberately chooses a cold worker and incurs the prefill penalty to maintain overall Service Level Objectives (SLOs).
3. Power of Two Choices (P2C) Fallback: When multiple replicas meet acceptable load and cache criteria, the router samples two random candidate replicas and selects the one with the superior latency profile.

Production Framework Comparisons

SGLang Model Gateway (SGL-Router)

• Routing Model: Layer-7 reverse proxy implemented in Rust over gRPC and HTTP.
• Prefix Tracking: Approximate Radix Tree simulated across workers without continuous synchronization messages.
• Imbalance Strategy: Dynamic load penalty weighted against prefix match length.
• Measured Impact: LMSYS benchmarks report up to a 1.9x throughput increase and 3.8x cache hit rate improvement (from 20% to 75% hit rates) on multi-worker clusters with shared prefixes.

Ray Serve PrefixCacheAffinityRouter

• Routing Model: Native Python and C++ routing actor managing distributed vLLM deployments.
• Prefix Tracking: Character-level prefix tree tracking vLLM Automatic Prefix Caching state.
• Imbalance Strategy: Configurable imbalanced_threshold parameter with automatic fallback to Power of Two Choices.
• Measured Impact: Reduces Time-To-First-Token (TTFT) by up to 60% on multi-turn conversations and iterative agent loops.

Mooncake (Moonshot AI / Kimi)

• Routing Model: Disaggregated KV-centric Conductor orchestrating prefill and decode pools.
• Prefix Tracking: Global distributed KV index spanning DRAM, SSD, and HBM.
• Imbalance Strategy: Automatic prefill-to-decode allocation with RDMA-backed KV chunk migration.
• Measured Impact: Enables Kimi to handle up to 75% more requests and achieves up to 525% throughput gains under strict latency SLOs.

TokenLake

• Routing Model: Segment-level unified cache pool for elastic long-context serving.
• Prefix Tracking: Segment-level prefix tree indexing fine-grained token segments across heterogeneous nodes.
• Imbalance Strategy: Dynamic segment migration and elastic prefill-decode load balancing.
• Measured Impact: Improves throughput under fixed SLO targets by up to 2.6x and boosts cache hit rates by up to 2.1x over baseline cache-aware routers.

Implementation Best Practices for ML Engineers

When deploying cache-aware routing in production LLM clusters, consider the following design guidelines:

1. Tokenization Placement: Evaluating prefix trees at the token level requires running tokenizers on the CPU router. For high-concurrency gateways handling tens of thousands of requests per second, CPU tokenization can become a throughput bottleneck. Using character-level or byte-level string hashing over structured prompt templates (e.g., hashing the raw system prompt text) provides a low-overhead approximation that avoids CPU tokenization costs.
2. Standardize System Prompt Layouts: Prefix caching requires identical token ordering from token index 0. Ensure that variable metadata (timestamps, user IDs, session identifiers) is injected at the end of the prompt rather than before shared instruction blocks.
3. Calibrate Imbalance Penalties to Hardware: On high-compute GPUs like Nvidia H100 or B200, prefill compute is exceptionally fast relative to memory transfers for short prompts. Set lower imbalance thresholds for short sequences (favoring load distribution) and higher imbalance thresholds for long-context RAG documents (favoring cache reuse).
4. Monitor Cache Thrashing Metrics: Track cache hit ratios, queue eviction rates, and TTFT variance across replicas. A wide standard deviation in GPU memory utilization often indicates that the routing cache weight is set too high relative to the queue penalty.

Sources

• SGLang v0.4: Zero-Overhead Batch Scheduler and Cache-Aware Load Balancer (LMSYS Org)
• Ray Serve: Prefix-Aware Routing Documentation (Ray / Anyscale)
• Ray Serve: Reduce LLM Inference Latency by 60% with Custom Request Routing (Anyscale)
• Mooncake: A KVCache-Centric Disaggregated Architecture for LLM Serving (arXiv:2407.00079)
• TokenLake: A Unified Segment-level Prefix Cache Pool for Fine-grained Elastic Long-Context LLM Serving (arXiv:2508.17219)
• KV Cache Routing: Why Standard Load Balancers Break Prefix Caching (TrueFoundry)