Inference-Aware Load Balancing for LLMs (part 5): prefix-cache-aware routing, measured

Sending each LLM request to the replica that already holds its prompt: how the llm-d router's approximate prefix index works, what the picker scores, router against Service in two passes, four at a time, and where it stops working.
Hand-drawn: router 85% prefix hits at 0.305 s against Service 43% at 0.690 s

On this page

Sixty different 600-word system prompts, each sent twice, to two replicas of a model. On the second pass through the llm-d router, 85.0% of the prompt tokens were already cached and the median request took 0.305 s; through a plain Kubernetes Service, 43.2% and 0.690 s. This is part 5 of Inference-Aware Load Balancing for LLMs: how the router knows where a prompt is cached without asking the replicas, what the picker scored, what changes at four requests at a time, and where it stops working. This post goes with a video on the LevelUP I.T. YouTube channel.

Pass 2, one at a time: the router against a plain Service
Pass 2, one at a time: the router against a plain Service

Why prefixes repeat

A chat resends the whole conversation on every turn plus one new message; an application puts the same long system prompt (instructions, tools, policies) on every request; retrieval sends the same chunks for many questions about one document; an agent resends its tools and history every step. Part 2 measured a cached prefix on one replica at 2.31 s to the first token cold and 0.25 s warm. With several replicas, the cache helps only if the request reaches the replica that holds it, and in a conversation the cost of missing it grows every turn: turn 20 re-prefills 19 turns.

How the router knows

It does not ask the replicas; it remembers what it sent where. With the prefix scorer in the profile, the router creates two producers by itself (its start-up log shows them): a token producer (by default an estimate, without the model's tokenizer) and the approx-prefix-cache-producer, which hashes the tokens in blocks (64 by default, tuned from the servers' metrics), each hash including every block before it as vLLM's own prefix cache does, and looks up which endpoints recently received those hashes. After each pick it records the chosen endpoint for the request's blocks in an LRU per server (default 31,250 blocks, auto-tuned from metrics). The index is what the router sent, not what the server still holds; the router also has a precise producer fed by the servers' KV-cache events, not used here.

The prefix scorer gives the share of the prompt's blocks found on an endpoint, 0 to 1. Weighted 3 in the default profile, a score of 0.875 adds 2.625 to that endpoint's total, far more than the load differences on an idle pool; a busy holder can still lose (queue and KV scores of 0 cost up to 4 points).

The approximate prefix index
The approximate prefix index

This post is for paying subscribers only

Subscribe to LevelUp I.T. newsletter and stay updated.

Don't miss anything. Get all the latest posts delivered straight to your inbox. It's free!
Great! Check your inbox and click the link to confirm your subscription.
Error! Please enter a valid email address!