Why the First Token for the Same Prompt Can Drop from 92.5 Seconds to 0.54 Seconds

In production, prompts are rarely brand new every time. The system prompt, tool definitions, and previous turns are usually identical, with only the final segment being new content. A GPU that has just served the previous turn still holds the KV cache for the shared prefix in its memory. If the router does not know this and sends the next request to another GPU, that card has to recompute the entire prefix before it can emit the first token.

Avi Chawla gave a benchmark in a tweet: with 8 vLLM pods and 16 H100s, prefix-aware routing reduced the p90 time-to-first-token to 0.54 seconds, while random routing on the same set of pods was 92.5 seconds. That is a gap of two orders of magnitude. TTFT is time-to-first-token, and p90 means 90% of requests are below this value.

What the prefix-aware router does is not complicated. A request arrives with prefix blocks A through D and a new suffix E. The router hashes the prompt block by block, and each hash covers all content before it. It then uses these hashes to look up a block-to-worker index. The index stores locations, not KV tensors. In the example, Worker A has 2 matching blocks, Worker C has 3, and Worker B has 4, so the request goes to Worker B. Worker B reuses the cached KV for A through D, computes the KV only for E, and starts decoding. After E is written to cache, the cache event refreshes the routing index, and the next turn continues to land on Worker B. When no worker matches, the request performs a full prefill on the worker selected by the router. A real router also considers load, so it does not send everything to the GPU with the hottest cache and create the longest queue. All of this assumes the prefix cache itself is valid; a small change near the beginning of the prompt makes every later block miss.

To understand this routing, you need to separate the four layers of caching in the LLM stack. Avi Chawla's article discusses KV cache, prefix caching, prompt caching, and semantic cache together because they are all called caching, but they store different things. The first three layers use exact matching, so a miss affects only cost and latency. The fourth layer uses fuzzy matching, and a hit can directly return a wrong answer while the HTTP status is still 200. One commenter put it bluntly: the first three layers change the amount of computation, while the fourth layer can change the answer.

The KV cache belongs to a single request. During prefill, the model computes and stores keys and values for every prompt token at every layer. During decode, it computes only the new token and then attends to those stored vectors. Queries are not cached because of causal masking: a token's query is used only once, in the step that processes it, while its key and value are read repeatedly by later tokens. Caching changes each decode step from matrix-matrix multiplication to matrix-vector multiplication, but every step must still load the entire cache from HBM, so decode shifts from compute-bound to memory-bandwidth-bound. Cache size grows linearly with the number of tokens. For a 70B model in BF16 with a 128K context, the cache for a single request is about 40GB, close to the entire model at 4-bit weights. GQA sharing KV heads, DeepSeek's MLA compressing the latent, and 4-bit cache quantization all aim to reduce this memory footprint. With an ordinary generate call, the cache is released when the call ends, so in a 20-turn chat, if the cache is not retained at turn 20, the first 19 turns are prefilled again at full cost.

Prefix caching keeps the cache alive after a request ends. vLLM by default uses blocks of 16 tokens and computes a chained hash from the parent block's hash plus the current block's token IDs. Block lookup proceeds in order and stops at the first miss; later blocks are not attempted because their keys depend on the earlier hashes. A matched block's reference count is incremented to prevent eviction. Partial blocks at the tail with fewer than 16 tokens are not indexed and must be recomputed every time. The salt in the hash function can be passed per tenant, so the same text generates different keys for different tenants and physical blocks are not shared. RAG traffic is the easiest place to get burned: system instructions, retrieved chunks, and the query are concatenated, and the retrieved chunks may appear in a different order each time; under chained hashing, two requests may share nothing at all. LMCache implements CacheBlend, which reuses block caches at arbitrary positions, recomputes only a small number of tokens with the largest deviations, and repairs cross-block attention and positional encoding; time-to-first-token can be 2 to 3 times faster than full recomputation.

Prompt caching is how hosted-model providers package prefix caching into a price sheet. Anthropic charges 1.25x the base input price for cache writes and 0.1x for cache reads; OpenAI uses the same multipliers on current models. The cached object is still the KV tensor, and it still requires an exactly identical rendered prefix. cache_control is placed on the last block you want to cover, and it writes a cache entry from the start of the request through that block. User messages below the marker change every time and cannot be placed in the cached region. cache_creation_input_tokens and cache_read_input_tokens in usage show whether there was a hit. If both are 0, the prefix did not reach the model's minimum cacheable length; the request is processed normally and no error is raised. Anthropic looks back for old writes up to 20 blocks; if you insert more than 20 blocks between two calls, the earlier writes fall out of range.

Semantic cache takes a different path. It embeds the prompt, finds the nearest neighbor among stored prompts, and if the similarity exceeds a threshold, directly returns the stored response string. It saves both input tokens and output tokens, but every request pays for an embedding, whether it hits or not. In Avi Chawla's example, 'How do I reset my password' and 'How can I reset my password' have a similarity of 0.961, which is a true paraphrase. 'Is the API rate limited' and 'Is the API not rate limited' have a similarity of 0.952; they differ by a negation, so the answers should be opposite. The two scores differ by less than 0.01. Raise the threshold and the hit rate drops; lower it and confident wrong answers increase. One commenter noted that the most troublesome part of semantic cache is expiration: the same question can have a different answer four hours later, embeddings cannot see the time difference, and time-sensitive content needs a hard TTL before the similarity check. Another commenter pointed out that semantic cache is not suitable for tool calls that fetch stateful data.

There are also several easy-to-miss points in production. Variable content should go later in the prompt; putting timestamps, request IDs, or usernames at the start of the system prompt invalidates every block after them. The order of tool schemas also affects caching; reordering once can make everything cold. On Anthropic, toggling web search, citations, thinking config, or tool_choice rewrites the prompt text, and downstream blocks are invalidated along with it. A/B testing two reasoning efforts amounts to splitting the cache in half. Summarizing history rewrites the prefix, and the next call pays for cold tokens; truncating tool output in place keeps the prefix bytes identical. Cache entries are bound to a model, so routing to a cheaper model still requires cold prefill of the entire history. To find where two prompts start to mismatch, compare token IDs directly, not just the text in the logs. In Avi Chawla's example, turn 1 did not specify a system message, and the chat template filled in the model default; the two prompts diverged at index 3, so the cache could not be reused.

Source: Avi Chawla's article KV, Prefix, Prompt and Semantic Caching in LLMs, clearly explained, tweet Daily Dose of Data Science, CacheBlend implementation LMCache.

Of these four cache layers, which one has cost you the most debugging time?