Prefix-aware routing in an LLM cluster

Ordinary LLM cluster balancing almost always looks at the wrong things. It sees free memory, queue length, the number of active sequences, and GPU utilization. But it does not see whether the prefill for a particular request has already been completed. As a result, it can easily send a long document to an available but cold worker while a neighboring worker already holds that document's ready KV cache.

With repeated system prompts, large policies, contracts, medical records, and RAG contexts, doing less computation is often more important than having a freer GPU. This does not mean pinning all traffic to one GPU. It means using routing that first estimates the cost of repeating prefill, then compares it with the queue and available memory.

An available GPU does not mean a fast response

An available GPU is useful for a cold request, but it gains no advantage from the fact that another worker has already processed 30,000 tokens of the same document. It must run those tokens through the model again, create KV states for every layer, and only then start generating the response.

A warm worker is different. If a new request begins with the same tokens, the engine finds matching KV-cache blocks and computes only the tail: the user's question, new messages, tools, or the small part of the context that changed. In that case, time to first token depends not on the document's full length, but on the uncovered continuation and the queue in front of the worker.

This is where ordinary balancing fails. It treats two requests as equally expensive when they have the same input size. They are equally expensive for a GPU only while cold. After warming, one request has already been partly computed.

This is especially visible in three types of workloads:

• one long system prompt used across many conversations;
• one document that different users query in different ways;
• a set of templates where only customer fields, the date, language, or a short task at the end change.

If every request carries unique context, routing by a warm prefix will not help. Do not build a complex system for the sake of the word cache. First prove that your traffic really repeats the beginning of the prompt.

Prefix cache matches tokens, not meaning

A prefix cache reuses KV states for an identical sequence of tokens at the beginning of a request. It does not understand that two paragraphs mean the same thing. It does not treat JSON objects with different field orders as equal. It does not know that a space before a line break does not change the meaning.

The vLLM documentation describes automatic prefix caching this way: the engine reuses KV pairs from a previously processed prefix and skips recomputing it. In vLLM's project documentation, blocks are linked by hashes of the block's tokens and the preceding prefix. This is the right operational model: you need an identical tokenized history up to the point where the requests diverge, not merely similar input.

That leads to an uncomfortable but useful conclusion. In most systems, the first enemy of cache hits is not the scheduler but the application code.

For example, these two constructions are logically equivalent, but may be different to the cache:

System instruction\\n
Document: ...\\n
Question: What is the payment deadline?

System instruction\\n
Request time: 2026-07-23T10:15:00Z\\n
Document: ...\\n
Question: What is the payment deadline?

In the second version, you inserted a changing field before the document. Every token after the timestamp shifted relative to the first request, so the long document was no longer a shared prefix. Teams usually notice the problem late: the cache hit rate is low, GPUs are busy with prefill, and the template is considered «almost identical».

Separate two things that are often confused:

1. Document matching. This is useful, but it does not guarantee a prefix hit if changing data appears before the document.
2. Prefix matching. This is what actually lets you use a ready KV cache.

The consequence is simple: put stable, long data before changing data. Request metadata, the session ID, date, experiment group, and the user's question should come after the section you want to reuse.

Ordinary balancing destroys cache locality

Round robin, least connections, and choosing the least-loaded GPU distribute requests evenly. For web servers and short API calls, that is reasonable. For LLM inference with a long, repeated context, uniformity can create unnecessary work.

Imagine four replicas of the same model. You have 200 requests about one 40,000-token policy. With simple round robin, each replica will eventually warm that document, which is already better than having no cache at all. But then a second document of the same size arrives, followed by a third, while KV-cache memory is limited. Each replica starts storing a random mixture of prefixes. Evictions become more frequent, and the chance of reaching the needed warm set decreases.

With a prefix-aware approach, the router tries to group requests with the same beginning on a limited number of workers. It creates locality: a particular document and template are more likely to remain on the GPUs where they have already been computed. This does not mean permanent pinning. It means a new request is preferred where it is cheaper.

The Preble paper on distributed prompt scheduling describes this more usefully than many cache marketing materials. The authors treat a request with a prefix-cache hit as closer to decode load, and a request with a miss as closer to prefill load. The distinction matters more than it may seem. Prefill quickly consumes substantial compute on a long input. Decode lasts longer, but works with already-created states and places a different load on memory.

If a load balancer cannot distinguish these workloads, it may simultaneously:

• send a cold, long request where a heavy prefill is already running;
• send a cache hit to an idle GPU and turn it into a cache miss;
• overload one pool with long documents even though another pool has warm matches;
• evict a prefix that is expensive to recreate in favor of random short traffic.

An ordinary load balancer is not «bad». It simply has no signal for the cost of work that has already been done.

A warm prefix should not always win

The rule «always go where there is a hit» quickly turns into a queue in front of one GPU. This is how early prefix-aware routing implementations fail. The team sees a high cache hit rate and celebrates, while users wait because the router keeps them tied to the same warm worker for too long.

You need to compare the expected cost of the two options. For each candidate, the router estimates:

expected latency =
  queue wait
  + prefill for uncovered tokens
  + impact on active decode requests
  + risk of insufficient KV memory

For a candidate with a warm prefix, the second term is smaller, sometimes dramatically so. But the first and third terms may be larger. If long generations are already running on that GPU, a cache hit is not permission to grow the queue indefinitely.

A practical rule is to prefer a warm worker while its predicted time to first token is no worse than the cold alternative by more than a preset margin. The margin is necessary because queue estimates are never perfect, and a cache hit has real value for future requests.

Instead of keeping one «best» worker, it is useful to maintain a ranked list:

1. An exact hit with an acceptable queue.
2. A partial hit with an acceptable queue.
3. An available worker if warm candidates delay the request too long.
4. A separate cold pool if working replicas are holding expensive hot prefixes.

Partial hits matter. If the first 24,000 of 30,000 tokens match, the request's cost still changes substantially. But do not replace match length with match percentage. Matching 2,000 of 2,100 tokens and matching 2,000 of 100,000 tokens produce the same absolute prefill savings, even though the percentages look completely different.

A stable prompt template gives you more than a clever router

A router cannot fix prompts that the application accidentally changes on every call. First, put the input into a form that can be cached.

A good message order for «one document, many questions» tasks looks like this:

{
  "model": "chosen-model",
  "messages": [
    {
      "role": "system",
      "content": "Answer only from the attached document. If the fact is not there, say so."
    },
    {
      "role": "user",
      "content": "<document id=contract-184>...full normalized document text...</document>\\n\\nQuestion: What is the payment deadline?"
    }
  ]
}

The user's question comes after the document. The document ID is stable. The text goes through the same normalization every time. The system instruction does not contain the current date, a random trace ID, or a username.

Poor ordering often appears because it is convenient for the developer:

{
  "role": "user",
  "content": "User=84721; request=af1e; time=...\\nQuestion: What is the payment deadline?\\nDocument: ..."
}

Here, changing data appears before the long context. To a person, this is harmless. To a prefix cache, it is a boundary after which the shared document is no longer shared.

Normalization must be deterministic. Fix:

• line-break format;
• key order in serialized JSON;
• rules for removing extra spaces;
• the system prompt template version;
• the order of RAG context fragments.

The last point often causes debate. Developers want to sort retrieved chunks only by relevance, then wonder why an identical request does not produce a hit. If two fragments have similar relevance, use a stable tie-breaker, such as the source ID and its position. A small sacrifice in random output variation often pays for itself through reuse of a long prefix.

Do not insert dynamic fields into the system prompt for tracing. Pass the trace ID in headers, gateway metadata, or a separate log. Prompt tokens are too expensive a layer for service noise.

Long documents and RAG contexts need different rules

A follow-up question about one complete document is almost an ideal use case for a prefix cache. The document stays stable, questions diverge at the end, and repeated prefill is expensive. In this kind of traffic, the router can use a hash of the normalized document as part of the prefix key.

RAG is more difficult. For each request, the retriever selects fragments, changes their order by score, adds neighboring chunks, and sometimes rewrites headings. The general meaning remains, but the token prefix changes. If you try to cache the entire RAG assembly as one unit, you will get many short-lived entries and little benefit.

For RAG, I prefer to divide context into two layers:

1. Stable layer: the system instruction, response policy, terminology guide, immutable rules base, and tool profile.
2. Variable layer: retrieved fragments, the question, the specific user's history, and fresh data.

Put the stable layer first and try to keep it warm. Do not force the variable layer into a cache-hit pattern. This is especially true for searches across a large collection, where the document set changes in almost every request.

There is also an intermediate case: a user is having a conversation about one set of retrieved documents. Then it helps to pin that set to the session, preserve fragment order, and add new messages only at the end. This works not because a «chat» is magical, but because the conversation history grows as a prefix rather than being rebuilt from scratch each time.

Do not confuse KV caching with caching a completed answer. A completed answer can be returned only for a fully identical request under an appropriate freshness policy. KV caching lets you ask a new question about the same document. These are different layers, with different risks and different keys.

The routing key should reflect compatibility, not just text

You cannot safely route a request by one visible-text hash. The same text may be incompatible with a cache entry on another worker because of a different model, tokenizer, adapter, or configuration that affects input tokens.

I would describe the minimum candidate key like this:

cache_namespace =
  model_revision
  + tokenizer_revision
  + adapter_id
  + prompt_template_version
  + normalized_prefix_hash

normalized_prefix_hash does not necessarily need to cover the entire request. For a long document, it may cover the stable system text and the document up to the point where the question begins. But the router must know that the engine can actually use this prefix and at which block boundary it stores the KV cache.

An application hash cannot be treated as proof of a cache hit. It is only an index for finding a likely candidate. After the worker is selected, the inference engine itself confirms the actual token match and reports the length of the found prefix, if its metrics support this.

A useful routing log looks like this:

{
  "request_id": "req_8f2c",
  "model": "chosen-model",
  "prefix_key": "pfx_4b19",
  "selected_worker": "gpu-03",
  "candidate_workers": ["gpu-03", "gpu-01"],
  "predicted_cached_tokens": 24576,
  "actual_cached_tokens": 24320,
  "queue_wait_ms": 38,
  "prefill_tokens": 912,
  "decision": "prefer-warm-worker"
}

The pair predicted_cached_tokens and actual_cached_tokens is important. If they regularly diverge, you have found an input-identification problem, not a GPU problem. The cause may be a hidden timestamp, a template change, a different tokenizer on part of the fleet, or a normalizer that behaves differently in two services.

For a multi-tenant environment, add the tenant or policy namespace to the key. Do not route based on text matching alone if isolation rules prohibit sharing a particular cache. Even when KV blocks are technically separated, the decision about whether a route is allowed must come before latency optimization.

The router needs a cold path and starvation protection

A hot prefix can easily monopolize the scheduler. If one popular contract or system prompt creates a continuous stream, the router will keep selecting the same GPU. Eventually, a request for another important document arrives and waits too long, even though free resources are available elsewhere.

You need limits that prevent cache locality from becoming unfairness.

First, set a maximum wait time for warm preference. After that deadline, the request follows the ordinary rule, even if it loses the hit. This is not a compromise against caching. It protects user latency, which always matters more than an attractive average hit rate.

Second, reserve a quota for cold requests. It can be a separate replica pool or a share of slots on each worker. The principle is the same: a unique request must get a chance to start prefill rather than waiting behind an endless stream of popular prefixes.

Third, account for generation length. A short question with a huge document benefits greatly from a warm prefix. A long generation may occupy decode slots for a long time, so sending all hot traffic there is risky. The router should see at least an approximate output-token limit and apply different thresholds to short answers and extended generations.

Finally, do not make affinity permanent. A prefix may be evicted, a model may restart, or a worker may lose memory during an update. Store the presumed warm state with a lifetime and reduce its confidence after misses. A router that trusts a nonexistent cache is worse than honest round robin: it sends traffic into a queue without saving computation.

Metrics should show the prefill you saved

Cache hit rate alone is easy to misread. If every hit is counted equally, a hit on 64 tokens looks as good as one on 30,000 tokens. For cost and latency, these are different events.

At a minimum, track five groups of metrics:

• cached input tokens and uncached input tokens by model and pool;
• time to first token separately for warm hits, partial hits, and cold misses;
• average queue wait by routing decision;
• KV-cache evictions and the age of evicted prefixes;
• the share of requests that left a warm candidate because of the wait threshold.

Add a breakdown by prefix class. A system template, full document, session, and RAG assembly have different life cycles. An aggregate metric will hide the fact that one stable template works extremely well while another class fills memory with almost no reuse.

A simple accounting measure is also useful. For every request, save the number of tokens that would have been processed in a cold start and the number actually sent to prefill. The difference is not an exact count of GPU seconds, but it shows the direction and helps identify regressions after a template change.

Do not try to infer the effect only from total GPU utilization. After caching is enabled, utilization may even rise if the system starts handling more useful work or reaches decode faster. Check user-facing metrics: time to first token, total latency, timeout rate, and the cost of processed input tokens.

Introduce routing for one measurable traffic class

There is no need to begin with «all company prompts». Choose one flow where repetition is obvious: analyzing one document for many employees, an assistant with a large immutable instruction, or a service that handles standardized forms.

Roll it out in this order:

1. Collect several days of logs and calculate common token-prefix lengths, not just text matches.
2. Fix the template and move changing fields after the cacheable block.
3. Enable prefix caching in a limited pool and collect actual cached-token counts from the inference engine.
4. Add warm preference with a strict wait limit and a cold fallback route.
5. Compare warm, partial, and cold requests by time to first token, queue time, and evictions.

If there are almost no actual hits at step three, do not move on to complex GPU-selection formulas. Go back to the prompt template. In real systems, this usually produces more improvement than another coefficient in a scoring function.

AI Router can be a convenient place for this experiment because it preserves the OpenAI-compatible request format while leaving pool selection to the API gateway. But a gateway cannot create repetition by itself. Repetition comes from discipline in how the application assembles context.

Fewer computations matter more than free memory only when repetition is proven

Prefix-aware routing does not replace load balancing. It adds the cost of already completed prefill to the decision. In a cluster without repeated prefixes, that is unnecessary complexity. In a cluster that repeatedly reads the same long context, ignoring the warm KV cache means knowingly paying for the same work several times.

Do not begin by choosing a fashionable scheduler. Start with one question for your logs: which first 10,000 tokens do users send repeatedly? If the answer is system instructions, documents, policies, or persistent RAG blocks, you already have a routing opportunity. The remaining task is to stop scattering them across cold GPUs.