id
flops/prefix-cache-hit-path-gemm-only
Arithmetic intensity
This record covers the cost-inversion and the provenance question on the hit path; the arithmetic itself (the AI = t_new GEMM identity and the 2*n_q*dh*t_new*L attention term, versus the miss path's 2*n_q*dh*L^2) is derived in [[prefix-cache-hit-miss]]. What belongs here is the shape of the trade: on a full prefix hit of length L_hit, the attention flops for those L_hit positions are not recomputed at all - they were computed once when the prefix was first seen - so what remains is the GEMM for the new tokens plus one attention pass whose queries are only the new positions. The price is paid in bytes instead of flops: the KV for L_hit tokens must be READ from wherever it lives (HBM, a DRAM tier, or a remote store), so the hit path converts a compute cost into a bandwidth cost, and the bandwidth available is set by which tier the prefix resides in rather than by kernel tiling. That inversion is the economic argument for prefix caching on shared-prefix workloads - RAG, multi-turn chat, agent loops, a fixed system prompt - and it is also why the hit path is a kv_transfer problem: a hit is a data movement that must be correct, not just fast.
Scales with
prefix_hit_length (the entire saving: attention flops avoided scale as L_hit^2)prefix_sharing_rate across requests (a cache that nothing shares is pure overhead)kv_residency (HBM vs DRAM vs remote determines the bytes-per-second the hit path gets)kv_cache_layout and block_granularity (a hit must land on a block boundary or be recomputed)block_table_and_hash_computation cost (per-request, grows with hit length)
Workarounds
RadixAttention-style prefix sharing over the KV tree so multi-turn prefixes are stored once (SGLang)Automatic prefix caching keyed on token-block hashes (vLLM; on by default in v1 for supported models)Keep the shared prefix resident in GPU HBM rather than in a lower tier - the tier only helps once the hot set fitsSelective recompute only the tokens whose KV came from a non-identical position (CacheBlend, used by LMCache for non-prefix reuse) to bound quality lossSemantic KV reuse (donor blocks from a different request) is explicitly gated and experimental - TRT-LLM's RFC requires explicit engine support before any non-identical KV is materialized
notes
The engineering trap in this class is that a hit path and a cold path that are not bit-identical produce an output that depends on cache state. vLLM issue #40896 is the clean demonstration with no external tier involved: with prefix caching on, the same request at temperature=0 returns output A on a freshly started server and output B thereafter, and disabling prefix caching makes it deterministic. The stated root causes in the wider issue set are all key-identity gaps, not arithmetic: blocks reused across LoRA adapters sharing a name (#30931), blocks reused across model/input-embedding variants that are omitted from the key, and - the general form - blocks produced under a different numerical configuration (attention backend, batch-invariance mode, GPU architecture) because those fields are not in the offload namespace or the connector compatibility hash (#58263). A reader should treat 'cache hit' as a claim about provenance, not just about tokens: a hit is only valid if every field that changes the produced KV is part of the key. The FLOP-level split between the hit and miss paths is derived in [[prefix-cache-hit-miss]]; this record's contribution is that the hit path is a transfer whose bytes must come from the right tier with the right provenance.