The Hot Doc Problem

Looking for TL;DR? Check key takeaways

The previous post covered token-native storage: persist text as BPE token IDs with a static entropy coder for ~3× lossless compression, free OOD detection, and a representation aligned with how LLMs consume retrieved context. After publishing, the obvious follow-up question surfaced: once you've stored documents efficiently, what happens at inference time?

RAG has two compute costs that rarely get discussed together:

1. Retrieval: embedding lookup, ANN search — fast, well-studied
2. Prefill: the LLM attends over the retrieved context before generating — slow, repeated, and largely ignored

The second one is what this post is about.

The Same Document, Over and Over

In a real RAG deployment, query traffic doesn't hit documents uniformly. Power-law-ish popularity shows up in every large search system — but as we'll see below, how concentrated it is varies enormously by workload, and that variation turns out to decide everything.

Modelling this correctly turns out to be subtle, and an earlier version of this post got it wrong. Under Zipf(s), the fraction of queries covered by caching the top k documents is H(k,s) / H(N,s) — a ratio of generalized harmonic numbers that depends on both the corpus size N and the exponent s. My first version simulated coverage at N=1,773 (WikiText test articles) and put Wikipedia-scale storage costs next to it. Those two columns described different systems: at a consistent N=6.7M with s=1.0, the numbers look like this:

Inverted, the headline is striking: under s=1.0, getting 42% query coverage at Wikipedia scale needs only ~571 documents — about 20 GB of int8 KV. That's not a storage problem at all; it fits on one NVMe drive with room to spare.

But before celebrating, the exponent deserves the same scrutiny as the corpus size. s=1.0 was an assumption, and coverage is brutally sensitive to it. Documents (and storage) needed to cover 42% of queries at N=6.7M:

Three-tenths of an exponent swings the hot tier from "fits in GPU memory" to "needs a storage cluster." So which s is real? I pulled actual English Wikipedia pageview data (Wikimedia REST API, May 2026, 6.7B monthly user views) as an empirical anchor: the top 1,000 articles cover only 7.7% of article views, and the rank-frequency slope over the top 1,000 fits s ≈ 0.55 — far flatter than the Zipf(1.0) I assumed. For Wikipedia-style browsing traffic, hot-document KV caching is hopeless: meaningful coverage requires caching a double-digit percentage of the corpus.

Pageviews are a browsing proxy, not RAG traffic, and that cuts both ways. Workloads where queries funnel into a small document set — customer-support KBs (most tickets hit the same dozen articles), product docs, internal wikis, agent system prompts — sit at the concentrated end, plausibly s ≥ 1. The honest conclusion: the hot-doc opportunity is real but workload-conditional, and the exponent is the whole game. Measure your own doc-hit distribution before provisioning a KV tier. The good news from the corrected math: if your workload is concentrated, the hot tier is small enough to be trivial.

What Is TurboRAG?

Before running our own experiment, I looked for prior art. TurboRAG (EMNLP 2025) pre-computes KV caches for documents offline and stores them on disk. At inference, it loads the cached KV directly, skipping the prefill entirely — reporting 8.6× TTFT reduction.

The catch is the deployment story:

• Storage: 28MB per ~600-token chunk → 28TB for a full Wikipedia-scale corpus
• Model-specific: cached KV can't transfer between model versions or quantizations
• Fine-tuning required: block-diagonal attention masks change the model's behavior, so you need to fine-tune to make quality hold (~$3k per model variant)
• No cold fallback: if a document wasn't pre-cached, you have no graceful path

103 GitHub stars as of June 2026. Not deployed in production anywhere I can find.

The tiered alternative sounds more practical: use standard prefix caching (already in every LLM serving stack) for hot docs, fall back to normal prefill for cold docs, store only token IDs for everything (the 3× compression from the previous post). But does standard prefix caching actually work?

Experiment: Does vLLM Prefix Caching Help?

I ran this on Modal (A10G, 24GB), Qwen2.5-7B-Instruct, vLLM 0.6.6 with enable_prefix_caching=True. An earlier version of this experiment measured total latency — which turned out to be the wrong metric. The revised version uses AsyncLLMEngine with token-level streaming to measure TTFT directly, tests two doc lengths, and verifies the cache is actually hitting via vLLM engine metrics.

Setup:

• Hot doc: one Wikipedia article (202 words short, 380 words long), queried 6 times in a row
• Cold docs: 10 different articles, each queried once
• Output: 32 tokens per query
• Prompt template: fixed system_prompt + document + question (stable prefix for cache lookup)

Results:

vLLM confirmed the cache was working: 75.8% prefix cache hit rate after the first query over the hot doc.

TTFT halves. Total latency barely moves.

Why TTFT and Total Latency Diverge

total_latency = prefill_time + n_output_tokens / decode_throughput

prefill(300 tokens, A10G)  ≈ 70–100ms
decode(32 tokens, A10G)    ≈ 1,060ms

On a cache hit, the document's ~250 tokens are already in the KV cache. Only the ~15-token question needs prefilling, so TTFT drops from ~150ms to ~73ms — a 2× speedup. But the model still has to generate 32 tokens autoregressively at ~28 tok/s, and that takes over a second regardless. The prefill savings are real but invisible in total latency.

The breakeven: prefix caching improves total latency meaningfully only when generation is short enough that prefill dominates. For typical RAG answer lengths (50–200 tokens), generation wins.

This means the value of prefix caching is entirely about the user experience of streaming: cutting TTFT from 150ms to 73ms is a noticeable improvement. For batch processing or non-streaming APIs, it's irrelevant.

Concurrent Requests: The Real Win

Under concurrent load (8 simultaneous requests for the same hot doc), wall time stayed flat at ~1.2s — all 8 requests returned together in the time it would take to serve one cold request. TTFT per request was 87ms. For a system where 12% of queries hit the same single document, this means those requests can be batched and served nearly for free.

The Multi-Chunk Reality

The experiment above shares a hidden flaw with TurboRAG's benchmarks: the document sits at position 0, immediately after a fixed system prompt — the best case for prefix caching. A real RAG prompt holds k retrieved chunks ordered by relevance, and APC only reuses KV blocks whose entire prefix from the prompt start matches a previously processed prompt. A hot chunk sitting behind a different first chunk gets zero reuse. Zipf coverage of documents does not translate into cache hit rate.

How bad is it? vLLM's block matching (16-token blocks, hash chain from prompt start) can be simulated exactly. With Zipf(s=1.0)-drawn chunk sets and steady-state cache, the fraction of prompt tokens served from cache:

At a realistic k=5, relevance ordering wastes ~70% of the single-doc cache benefit. The mitigation in the third column is nearly free: order chunks canonically (globally hot chunks first) instead of by relevance score, so prompts that share hot chunks share a prefix. It's a one-line change in prompt assembly that doubles cache reuse.

I validated this on the GPU (same Qwen2.5-7B / A10G setup, k=5, 50 Zipf-drawn queries per condition, fresh engine per condition, TTFT taken from vLLM's own request metrics rather than wall-clocking the stream):

(The predicted fractions are lower than the steady-state table because 50 queries include the cache-filling phase.) The measured ~23ms TTFT gap matches the predicted cached-fraction delta within noise — the simulation is a reliable planning tool, and it runs in seconds on a laptop at any corpus scale.

One unmeasured cost: canonical ordering moves chunks away from their relevance positions, and models attend unevenly across the context ("lost in the middle"). Whether the reordering hurts answer quality is workload-dependent and needs its own eval before you ship this.

Longer Contexts: Where the TTFT Win Actually Lives

The 2× TTFT speedup above came from ~330-token prompts — the smallest realistic case, where there's barely any prefill to skip. Rerunning cold-vs-warm on longer single-document contexts (64 output tokens):

Two things worth staring at. First, warm TTFT is flat at ~50ms regardless of context length — on a hit, you only prefill the question, so first-token latency becomes independent of how much context you stuffed in. The 2× from the earlier experiment wasn't the ceiling; it was the floor. TurboRAG's headline 8.6× TTFT reduction reproduces without any fine-tuning once the context is long enough — standard vLLM APC gets there at ~3k tokens.

Second, total latency still barely moves (1.1–1.2×), because 64 output tokens at ~28 tok/s costs ~2.2s no matter what. The breakeven is unchanged: prefix caching pays on total latency only when prefill time rivals generation time — very long contexts with short outputs. For streaming UX, though, "first token in 50ms instead of 430ms" is the difference between instant and laggy.

What the Storage Numbers Tell You

KV state is bulky. For Llama-3.1-8B with 8 GQA key-value heads:

KV bytes/token = 32 layers × 2 (K+V) × 8 heads × 128 dims × 2 bytes = 131,072 bytes

A 531-token document (Wikipedia average) stores ~68MB of KV at fp16, ~34MB at int8 — roughly 30,000× larger than the same document stored as compressed token IDs (~1.3KB). That asymmetry is why tiering exists at all: token IDs for everyone, KV state only for documents that earn it.

But the corrected coverage math above changes what "the limiter" is. Under a concentrated workload (s ≈ 1.0), 42% coverage costs ~20GB — storage is a non-issue; one NVMe drive holds the hot tier of a corpus a thousand times larger. Under a flat workload (s ≈ 0.55, like actual Wikipedia browsing), no storage budget rescues you — caching 67,000 documents buys ~8% coverage. Storage was never the limiter. The query distribution is.

The serving-path question remains: is loading ~34–68MB of KV from NVMe into GPU memory faster than recomputing prefill? NVMe sequential reads at ~7GB/s put the load at ~5–10ms against ~50ms of prefill for a short document — a real win on paper, but the full path (NVMe → host RAM → PCIe → GPU, plus dequantization for a quantized tier) is unmeasured here, and vanilla vLLM has no NVMe KV tier; you'd need LMCache or a custom KV connector. I'm flagging that as napkin math, not a result. Quantized-KV answer quality is also unevaluated — exact prefix caching is bit-identical reuse, but an int4 offline tier is not.

What Actually Helps

The honest summary of where gains are real:

Storage (always worth it):

• Token ID storage: 3× compression vs LZ4, zero inference cost, works everywhere
• No model-specific state, no cache invalidation, no fine-tuning

Prompt assembly (free, do it now):

• Canonical chunk ordering (hot chunks first) roughly doubles prefix-cache reuse at k=5–10 vs relevance ordering — one line in prompt assembly
• Validate the quality impact (position effects) on your own evals before shipping

KV caching (conditional on your query distribution):

• The win is TTFT for streaming, and it scales with context length: 2× at ~330-token prompts, 8.5× at ~3.3k tokens — warm TTFT pins at ~50ms regardless of context size
• No fine-tuning, no architectural changes — just enable_prefix_caching=True
• Whether hot docs cover enough traffic to matter depends almost entirely on the Zipf exponent of your workload — measure it before provisioning anything
• TurboRAG-style offline precomputation only makes sense if you have a stable model, fixed corpus, and TTFT SLAs you can't meet otherwise

What doesn't help:

• KV caching for total latency when outputs are long (generation dominates at every context length I tested)
• Hot-doc caching under flat query distributions (s ≈ 0.55, like Wikipedia browsing traffic — no cache size rescues 7.7% top-1000 coverage)
• Relevance-ordered multi-chunk prompts: they silently throw away ~70% of the cache benefit single-doc benchmarks promise
• Storing KV for all documents (28TB for Wikipedia — the TurboRAG paper's approach)

Tiered Architecture (What I'd Actually Build)

Given the data, the practical design — now explicitly conditioned on measuring your workload first:

Layer 0 — Universal (any workload):
  Store documents as token IDs + static ANS → ~3× compression,
  self-contained, model-agnostic
  Assemble prompts with canonical chunk ordering → ~2× cache reuse, free

Layer 1 — GPU-resident APC (concentrated workloads, s ≳ 1):
  Just enable_prefix_caching=True and let vLLM keep hot prefixes in HBM.
  Under s=1.0 at Wikipedia scale, ~571 docs cover 42% of queries —
  at ~34MB int8 KV per doc that's ~20GB: NVMe-trivial, and the hottest
  few dozen docs fit directly in spare HBM.

Layer 2 — NVMe KV tier (only if Layer 1 evicts too much):
  Quantized KV via LMCache or a custom connector.
  Unvalidated here: load-path latency and int4 quality both need
  measurement before you build this.

On an APC hit: warm TTFT pins at ~50ms regardless of context length. On a miss: normal prefill, decompress token IDs on the fly (< 1ms from the compression post).

The key differences from TurboRAG: no fine-tuning, standard attention, model-agnostic token storage at the base layer. And at ~3k-token contexts, standard APC already reproduces TurboRAG's 8.6× TTFT reduction — the fine-tuning bought nothing you can't get from enable_prefix_caching=True plus sensible prompt assembly.

If your measured query distribution is flat (s ≲ 0.8), stop at Layer 0: the math says no KV tier will pay for itself.

Key Takeaways

• Zipf coverage is H(k,s)/H(N,s) — it depends on corpus size and exponent. An earlier version of this post mixed N=1,773 hit rates with N=6.7M storage costs; at consistent Wikipedia scale under s=1.0, 42% coverage needs only ~571 docs (~20GB int8 KV). Storage was never the limiter — the query distribution is.
• The exponent is the whole game: 42% coverage costs 0.3GB at s=1.2, 20GB at s=1.0, 14TB at s=0.7. Real Wikipedia pageviews fit s ≈ 0.55 (top-1000 articles = 7.7% of views) — hot-doc caching is hopeless for browsing-like traffic and viable for concentrated workloads (support KBs, product docs). Measure your own doc-hit distribution first.
• Single-doc cache benchmarks are the best case. At k=5 relevance-ordered chunks, only ~20% of prompt tokens hit the prefix cache (vs ~70% single-doc). Canonical chunk ordering (hot chunks first) recovers ~2× of that for free — validated on GPU: 160ms → 137ms median TTFT, matching the simulated cached-fraction delta. Quality impact of reordering is unmeasured.
• The TTFT win scales with context length: 2× at ~330-token prompts, 8.5× at 3.3k tokens (426ms → 50ms). Warm TTFT is flat ~50ms regardless of context size. Standard APC reproduces TurboRAG's 8.6× headline at ~3k tokens with zero fine-tuning.
• Total latency stays generation-bound at every tested length (1.1–1.2× with 64-token outputs). Prefix caching is a streaming-UX and GPU-throughput optimization, not a total-latency one.
• The practical stack: token ID storage everywhere (3× compression, free) + canonical prompt ordering (free) + vLLM APC for TTFT-sensitive streaming. Build an NVMe KV tier only after measuring s and APC eviction on your traffic.
• TurboRAG's 28TB / fine-tuning requirement makes it a research result, not a deployment recommendation.

The full experiment code is on GitHub.