# Why Is Your LLM Recomputing the Same Prompt 1,000 Times a Day? > Source: > Published: 2026-09-09 12:01:03+00:00 **TL; DR** Real LLM traffic is enormously repetitive. System prompts, chat history and shared documents mean requests overlap heavily at the start. Attention is causal, so a token’s cached state depends only on the tokens **before** it. Two requests with an identical prefix produce an identical cache for that prefix. **Prefix caching** keeps that state after a request finishes so the next request can reuse it, skipping prefill entirely for the shared portion. vLLM identifies reusable state by **hashing each cache block together with the hash of everything before it**. SGLang organises the same information as a **radix tree**. The gain shows up as lower time-to-first-token and reclaimed prefill capacity — often dramatic for long shared prompts. The cost is memory: blocks kept for future reuse are blocks unavailable to active requests. Here is a pattern that shows up in almost every production LLM deployment. An application has a system prompt — instructions, tone, policy, tool definitions, maybe a few examples. It might be 4,000 tokens. Every single request begins with it. The user’s actual question is 20 tokens on the end. So the server processes those 4,000 tokens. Then the next request arrives and it processes the same 4,000 tokens again. Then again. A thousand times an hour, computing an identical result and discarding it each time. This article is about why that happens, why it is fixable, and how modern inference engines fix it. A quick definition, because the rest depends on it. When a model processes text, each token produces a **key** and a **value** vector at every layer. Generating subsequent tokens requires the keys and values of everything before them, so the engine stores that state rather than recomputing it. This store is the **KV cache**, and building it for the input prompt is the **prefill** phase — the work done before the first output token appears. Prefill is expensive and scales with prompt length. For a large model, processing several thousand prompt tokens can take a noticeable fraction of a second, and that time lands directly on the user’s time-to-first-token. Normally, when a request finishes, its cache is released and the state is gone. That is the behaviour we are about to question. Repeated prefixes are not a corner case. They are the dominant shape of production traffic. **System prompts.** Every request from an application carries the same instruction block. Often thousands of tokens, identical every time. **Multi-turn conversations.** Models are stateless. Turn five of a chat re-sends turns one through four in full. The prefix of each turn is the entire conversation so far — and it was computed on the previous turn. **Shared documents.** In retrieval and document-analysis workloads, many users ask different questions against the same document. The document is the prefix. **Few-shot examples.** Prompts with fixed demonstrations before the variable part. In workloads like these the shared portion is frequently the large majority of the prompt. The overlap alone does not justify reuse. What justifies it is a property of how attention works. Attention in a generative model is **causal**: a token can attend to the tokens before it, never to the tokens after. Which means a token’s key and value depend only on itself and on everything preceding it — and on nothing that follows. The consequence is exact and worth stating carefully: If two requests begin with the identical sequence of tokens, the KV cache for that shared portion is identical — regardless of what either request contains afterwards. Nothing appended later can retroactively change it. That is what makes the state safely reusable rather than merely similar. Note the strictness. The prefix must match **from the very first token**, and it must match exactly. Shared text in the middle of two prompts is not reusable, because the state at that position depends on the different text preceding it. Prefix caching earns its name precisely. Suppose an application has a 4,000-token system prompt and users send short questions. Without prefix caching, every request prefills 4,020 tokens. With it, the first request prefills 4,020 and each subsequent one prefills roughly 20 — the shared 4,000 are read from cache. Two things improve, and they are worth separating. **Time to first token drops sharply.** Prefill was the dominant term for the request; almost all of it disappears. To put rough numbers on it: if a deployment prefills at a few thousand tokens per second, those 4,000 shared tokens were costing on the order of a second of TTFT on every request, before the model even looked at the user’s question. A hit removes nearly all of it. For long shared prompts this is the difference between a sluggish interface and an immediate one. **Prefill capacity is reclaimed.** The GPU cycles that were being spent recomputing identical state become available for real work. Across a busy server this raises throughput even for requests that never hit the cache. The saving scales with how much of the prompt is shared. A 100-token system prompt is not worth much. A 20,000-token document that fifty users are querying is worth an enormous amount. Modern engines do not store a sequence’s cache as one contiguous region. They split it into fixed-size **blocks**, each holding a set number of tokens — 16 is a common default — allocated on demand. That choice, made originally to avoid wasting memory, turns out to be exactly what prefix caching needs. Reuse operates at block granularity: a block is either identical to one already in memory, or it is not. The practical consequence is that reuse is **block-aligned**. If two prompts share 4,005 tokens and the block size is 16, the engine can reuse the first 250 complete blocks — 4,000 tokens — and recomputes the partial remainder. A trivial rounding loss, but it explains why matches are reported in blocks rather than exact token counts. This is the mechanism at the centre of the article. The engine needs to answer one question quickly: *have I already computed the state for this exact block, in this exact position, with this exact history?* All three conditions matter. A hash of just the block’s own tokens is not enough. The same 16 tokens appearing at the start of one prompt and in the middle of another have completely different state, because the state depends on everything preceding them. Hashing only the contents would produce a false match and silently corrupt the output. So vLLM **chains the hashes**. Each block’s hash is computed from its own tokens *together with the hash of the preceding block*: Each hash therefore identifies not “these 16 tokens” but “these 16 tokens, arrived at through exactly this history.” Two blocks match only if their entire preceding sequence matched, which is precisely the condition that makes reuse correct. Those hashes go into a lookup table pointing at physical blocks. When a request arrives, the engine hashes its prompt block by block and looks each one up. Lookup walks forward from the first block and stops as soon as one misses. ``` Cached: [ A ][ B ][ C ][ D ][ E ]New: [ A ][ B ][ C ][ X ][ Y ] ✓ ✓ ✓ ✗ └── reused ──┘ └ computed ┘ ``` This is exactly the behaviour multi-turn chat needs. Each new turn shares every block of the conversation so far and diverges only at the newly appended message. The reused portion grows with the conversation, so prefill cost per turn stays roughly flat instead of climbing with history length. It also answers the question in this article’s title. When a deployment has prefix caching enabled and is *still* recomputing everything, the cause is almost always **variable content at the front of the prompt.** A timestamp, session ID, user name or A/B flag injected at the top of an otherwise-fixed system prompt changes block 0 — which changes hash₀, which changes every hash downstream, which destroys every match for the entire prompt. One dynamic line at the top can cost you the other four thousand tokens. The fix is mechanical: **put stable content first, variable content last.** Fixed instructions, tool definitions and examples at the top; anything that changes per request at the bottom. vLLM’s hash table is one way to organise this. SGLang takes another, called **RadixAttention**. A radix tree stores strings by shared prefix: common beginnings become shared branches, and divergence creates a fork. Applied to token sequences, the cached prefixes form a tree where each path from the root is a cached sequence, and any shared prefix is stored once on a shared path. Both approaches answer the same question and both evict with LRU. The difference is structural: a hash table gives direct lookup of a known block, while a tree makes the *relationships* between cached prefixes explicit — you can see which sequences share what, which branches are hot, and where a new request would attach. SGLang uses that visibility for cache-aware scheduling, ordering requests to maximise reuse. For a practitioner the takeaway is not which is better. It is that both engines cache prefixes, both evict LRU, and both benefit from the same prompt structure. Cached prefixes cannot be kept forever. Memory is finite and the pool is shared with active requests. The elegant part of the design is that a finished request’s blocks are not immediately wiped. They are marked free and left in place. If a new request hashes to them before they are needed elsewhere, it gets a hit at no cost. If memory pressure arrives first, they are reclaimed, least-recently-used first. So prefix caching largely runs on memory that would otherwise sit idle. It does not reserve a separate pool; it defers cleanup. That is why engines can enable it by default — in the common case it costs nothing and sometimes saves a great deal. The cost appears under pressure. When the server is saturated, blocks retained for possible reuse are blocks unavailable to active sequences, so the engine faces a real trade-off between **memory for reuse** and **memory for concurrency**. Hot, highly-shared workloads want more retention; workloads with unique prompts want none. Prefix caching is close to free, but it is not universal. **Unique prompts.** Workloads where every request is genuinely different get nothing. All lookups miss, and the retained blocks are pure overhead. **Variable content at the front.** The single most common reason a cache appears to do nothing — see Section 7. **Cache too small for the working set.** If the hot prefixes exceed available memory, entries are evicted before they are reused and the hit rate collapses. **Short prompts.** Saving a few hundred tokens of prefill is not material. **Decode is untouched.** Prefix caching removes redundant prefill. Generation still runs one token at a time, at the same speed. A request that spends most of its time generating will barely notice a cache hit. One operational note: because entries are keyed on token IDs, only genuinely identical content matches, and no content crosses between requests. What is observable is *timing* — hits are faster than misses. In shared multi-tenant deployments that is worth being aware of. Two numbers tell you whether this is working. **Prefix cache hit rate** — the share of prompt blocks served from cache. Engines expose this directly. If it is near zero on a workload you expect to be repetitive, look for variable content at the front of your prompts before looking anywhere else. **TTFT, at p50 and p95** — hits and misses have very different profiles, so the average conceals the behaviour. A deployment with a high hit rate typically shows a fast median and a long tail of misses, and the gap between them is roughly what the cache is worth. Prefix caching changes the economics of a request in a way that has a consequence beyond the server it runs on. Two identical requests no longer cost the same. One that lands where its prefix is cached skips almost all of its prefill and answers immediately. The same request landing elsewhere pays the full cost. The difference can be large. Which is fine on a single server. It is not fine on twenty. In a real deployment, traffic arrives at a load balancer sitting in front of many replicas, and each replica has its own cache holding its own set of prefixes. Those caches are not shared. Server A may hold the state for a request that would be nearly free to serve there — while a round-robin balancer, knowing nothing about any of this, sends it to Server B to be computed from scratch, evicting something useful in the process. And cached state is only part of it. LLM requests were never interchangeable to begin with. A 200-token prompt with a 20-token answer costs almost nothing. A 30,000-token prompt with a 4,000-token answer occupies a large share of a server’s memory for a long time. A load balancer counting connections cannot tell them apart, and counts them the same. So the routing layer is making decisions about wildly unequal work, with no idea where the valuable state lives. **What would a load balancer have to know about an inference server to route to it well?** That is the next layer of the stack. **1. What really happens when you click ‘Send’ on ChatGPT** — A journey through modern AI Infrastructure **2. What Do You Do With a Model That’s Too Big for Your GPU?** — Quantization, Sharding and Parallelism Explained **3. How Does One GPU Serve Hundreds of Users at the Same Time?** — Inside an LLM inference server **4. The KV Cache Explained: Why Long Conversations Get Expensive** — How LLMs remember context without recomputing everything **5. Why Is Your LLM Recomputing the Same Prompt 1,000 Times a Day?** — Prefix caching, radix trees and block hashing explained **6. Why Traditional Load Balancing Breaks for LLMs** — Building an LLM-aware router (Next Article) **7. Kubernetes for LLM Inference: How AI Workloads Run Across a GPU Cluster** **8. LLM-D Explained** — How modern AI infrastructure routes, schedules and scales LLM inference **9. Inside a Modern AI Inference Platform** — The full stack end-to-end **Sources** [Why Is Your LLM Recomputing the Same Prompt 1,000 Times a Day?](https://pub.towardsai.net/why-is-your-llm-recomputing-the-same-prompt-1-000-times-a-day-675e0cdab4b3) was originally published in [Towards AI](https://pub.towardsai.net) on Medium, where people are continuing the conversation by highlighting and responding to this story.