Why Time-to-First-Token Breaks
RAG pipelines, multi-turn chatbots, and plugin frameworks all prepend large context before the real query. That inflates prefill cost superlinearly — and once the cached prefix outgrows GPU and CPU memory, it spills to disk, where I/O latency dominates the wait for the first token.
Request → First Token Pipeline
Prefill processes the whole prompt at once and must resolve cached KVs from whichever memory tier holds them before the first output token appears.
The Memory Tier Stack
Hover a tier for capacity and latency. As prefix caches grow, they push down from HBM to DRAM to disk — and disk I/O can consume 51–98% of total TTFT.
How Bad Does It Get?
Chameleon, a GPT-plugin framework, prepends ~2,600 tokens of tool definitions before a ~590-token query on OPT-30B.
~4.4× more tokens → 9× slower time-to-first-token. Prefill cost does not scale linearly.
Reusing H2O's Importance Signal — Before Prefill, Not After Decoding
H2O found that a token's column-summed attention weight predicts whether it's safe to evict during decoding. IMPRESS's insight: heads within a layer largely agree on which tokens matter — so you can sample a few heads instead of computing every one.
Head Agreement Is Nearly Universal
Jaccard overlap of top-attention token sets across 8 heads, OPT-6.7B middle layer — average overlap exceeds 0.95. Hover any cell for the exact value.
Similarity-Guided Identification
3 probe heads compute real attention; if they agree, the layer's remaining heads skip computation entirely.
Agreement vs. Retention Ratio
Lower retention ratios (fewer tokens kept) reduce head agreement. Larger models agree more. Click a model to highlight its line.
Solving the Chunk Problem
Knowing which tokens matter isn't enough — prefix KVs are stored in fixed chunks for disk-read efficiency, and importance doesn't respect chunk boundaries. IMPRESS reorders KVs by importance and re-scores the cache accordingly.
Read Amplification From Chunking
Each row is one disk chunk (8 KV slots). Cell color = importance. Toggle to see how reordering clusters important KVs into fewer chunks.
Marking half a prefix important yields only 46% useful KVs per loaded chunk — a 2.2× read amplification.
Dual Min-Heap Cache Scoring
Score = access frequency × fraction of important KVs. Green bars mark the top-3 chunks that win the scarce GPU cache slots.
Radix Tree Reordering Scope
Reordering runs asynchronously, off the critical path, scoped to one radix-tree node at a time — a mapping list preserves prefix-match order.
Does It Deliver at the TTFT Line?
Built on FlexGen, tested on one A100 + one 2TB SSD across OPT (6.7B/13B/30B) and Llama2 (7B/13B), on PIQA, RTE, COPA, and OpenBookQA with few-shot exemplars as the shared prefix.
TTFT vs. Baselines
Normalized TTFT (lower is better) across systems. IMPRESS beats even the strongest baseline.
Up to 2.8× lower TTFT than the best baseline (AttentionStore+H2O/LFU), from a 3.8× cut in I/O time.
Tail Latency
RTE, OPT-30B. Tail latency improves even more sharply than the average.
Where the Speedup Comes From
Contribution of the three techniques to TTFT reduction shifts by workload — sometimes probe-head skipping dominates, sometimes score-based caching does.
GPU Cache Hit Ratio
Score-based caching lifts GPU hit ratio from ~68% to ~80%, holding across chunk sizes.