Cache-aware routing

I built a prefix cache with hash dedup earlier in this journey and measured KV cache hit rates across different traffic patterns. The results were clear: prefix caching can skip 50% to 90% of prefill computation when requests share common prefixes (system prompts, few-shot examples, document context). But all of that work assumed a single server.

The moment you scale to multiple workers behind a load balancer, prefix caching falls apart. A round-robin router scatters requests across workers, so each worker builds its own independent cache. The same system prompt gets cached N times (once on each worker), and multi-turn conversations hop between workers, missing the cache every time. Cache-aware routing fixes this.

The problem with load-balancing ignorance

Consider a deployment with 4 vLLM workers behind a round-robin load balancer. A chatbot application sends every request with the same 2,000-token system prompt. Without cache-aware routing:

# Round-robin: requests scatter across workers
# Request 1 -> Worker 0 (cache miss, prefill 2000 tokens)
# Request 2 -> Worker 1 (cache miss, prefill 2000 tokens)
# Request 3 -> Worker 2 (cache miss, prefill 2000 tokens)
# Request 4 -> Worker 3 (cache miss, prefill 2000 tokens)
# Request 5 -> Worker 0 (cache HIT on system prompt, prefill only new tokens)
# Request 6 -> Worker 1 (cache HIT)
# ...

# Each worker independently caches the same 2000-token prefix
# Total wasted prefill: 4 * 2000 = 8000 tokens of redundant compute
# Plus: multi-turn conversations miss cache when they hit a different worker

With cache-aware routing, all requests with the same system prompt go to the same worker (or at least the worker that has it cached):

# Cache-aware: requests routed to worker with matching prefix
# Request 1 -> Worker 0 (cache miss, prefill 2000 tokens, caches prefix)
# Request 2 -> Worker 0 (cache HIT, prefill only new tokens)
# Request 3 -> Worker 0 (cache HIT)
# ...
# Different system prompt -> Worker 1 (new prefix, cached there)

# Zero redundant prefill after the first request per prefix

How prefix hashing works

The router needs to quickly determine which worker has a matching prefix without actually storing the KV cache itself. The standard approach is prefix hashing: hash the token IDs of the prompt prefix and use the hash to select a worker.

import hashlib

def compute_prefix_hash(token_ids, block_size=16):
    """Hash the prefix in block-aligned chunks."""
    hashes = []
    for i in range(0, len(token_ids), block_size):
        block = token_ids[i:i+block_size]
        block_bytes = bytes(block)
        h = hashlib.sha256(block_bytes).hexdigest()[:16]
        hashes.append(h)
    return hashes

def route_to_worker(token_ids, num_workers, block_size=16):
    """Route request to worker with longest matching prefix."""
    prefix_hashes = compute_prefix_hash(token_ids, block_size)

    # Use consistent hashing: the first block's hash determines
    # the primary worker for this prefix family
    primary_worker = int(prefix_hashes[0], 16) % num_workers
    return primary_worker

This simple approach uses the first block's hash to deterministically route all requests with the same prefix start to the same worker. More sophisticated implementations consider longer prefixes and query the workers' cache state directly.

SGLang's cache-aware routing

SGLang implements a more sophisticated approach using a radix tree in the router. The router maintains a lightweight mirror of each worker's cache state as a radix tree (also called a prefix tree), where each node represents a block of cached tokens.

When a request arrives, the router:

Walks the prefix trees for all workers, finding the longest matching prefix on each.
Selects the worker with the longest match (maximum cache hit).
If multiple workers tie, selects the least loaded one.
Updates the local prefix tree to reflect the new request (optimistically assumes it will be cached).

class CacheAwareRouter:
    def __init__(self, num_workers):
        self.workers = [RadixTree() for _ in range(num_workers)]
        self.worker_loads = [0] * num_workers

    def route(self, token_ids):
        best_worker = -1
        best_match_len = -1

        for worker_id, tree in enumerate(self.workers):
            match_len = tree.longest_prefix_match(token_ids)

            # Prefer longer cache match, break ties by load
            if match_len > best_match_len or (
                match_len == best_match_len and
                self.worker_loads[worker_id] < self.worker_loads[best_worker]
            ):
                best_match_len = match_len
                best_worker = worker_id

        # Update state
        self.workers[best_worker].insert(token_ids)
        self.worker_loads[best_worker] += 1

        return best_worker, best_match_len

Cache hit savings

A cache hit on a 2,000-token system prompt skips roughly 2,000 tokens of prefill computation. For a 70B model on an H100, that saves about 60 ms of prefill time per request. At 100 requests per second, that is 6 seconds of GPU time saved every second, effectively giving you 6x more prefill capacity for those requests.

The load balancing tradeoff

Cache-aware routing creates a tension with load balancing. If you always route to the worker with the best cache match, you can create hot spots: one worker handles all the traffic for a popular prefix while others sit idle.

The solution is a scoring function that balances cache benefit against load:

def route_with_balance(token_ids, workers, alpha=0.5):
    """Balance cache hits against load distribution."""
    scores = []
    for worker_id, tree in enumerate(workers):
        match_len = tree.longest_prefix_match(token_ids)
        load = worker_loads[worker_id]

        # Cache benefit: tokens of prefill saved (normalized)
        cache_score = match_len / len(token_ids)

        # Load penalty: higher load = lower score (normalized)
        max_load = max(worker_loads) or 1
        load_score = 1.0 - (load / max_load)

        # Combined score
        score = alpha * cache_score + (1 - alpha) * load_score
        scores.append(score)

    return scores.index(max(scores))

The alpha parameter controls the tradeoff. At alpha=1.0, you maximize cache hits (pure affinity routing). At alpha=0.0, you minimize load imbalance (pure load balancing). In practice, alpha=0.5 to 0.7 works well: prefer cache hits but do not allow extreme imbalance.

Multi-turn conversation affinity

Cache-aware routing has a second, equally important use case: conversation affinity. In a multi-turn chat, each turn builds on the previous turns' context. If turn 2 hits the same worker as turn 1, the worker already has the KV cache for the conversation history and only needs to prefill the new user message. If it hits a different worker, the entire conversation history must be re-prefilled.

# Multi-turn without affinity:
# Turn 1 (500 tokens) -> Worker 0 (prefill 500)
# Turn 2 (800 tokens) -> Worker 2 (prefill 800, including 500 from turn 1)
# Turn 3 (1200 tokens) -> Worker 1 (prefill 1200, including 800 from turns 1-2)
# Total prefill: 500 + 800 + 1200 = 2500 tokens

# Multi-turn with affinity:
# Turn 1 (500 tokens) -> Worker 0 (prefill 500, cache all)
# Turn 2 (800 tokens) -> Worker 0 (cache hit 500, prefill 300 new)
# Turn 3 (1200 tokens) -> Worker 0 (cache hit 800, prefill 400 new)
# Total prefill: 500 + 300 + 400 = 1200 tokens (52% reduction)

For conversation-heavy workloads, affinity routing can reduce total prefill compute by 40% to 60%. The router achieves this by hashing on the conversation ID (or session ID) rather than the token content.

Cache eviction and router consistency

The router's prefix tree is an optimistic mirror of the workers' actual cache state. When a worker evicts entries from its KV cache (due to memory pressure), the router's tree becomes stale. There are two approaches to handle this:

Periodic sync. Workers periodically report their cache contents to the router. Simple but introduces staleness.
Event-driven updates. Workers send eviction notifications to the router in real time. More accurate but adds complexity and network traffic.
Optimistic with fallback. The router assumes its tree is correct. If a worker reports a cache miss on a token sequence the router thought was cached, the router updates its tree. This is the simplest approach and works well in practice because false positives (router thinks cached but it is not) only cost a redundant prefill, not a correctness error.

Cache-aware routing turns prefix caching from a single-server optimization into a system-wide strategy. Without it, every worker independently discovers and caches the same prefixes, wasting memory and compute. With it, your multi-worker deployment behaves like a distributed cache with intelligent placement.

Next we explore chunked prefill for long context, where we break up massive prefill operations to keep the serving system responsive for all requests.