SparPR recovers KV caches on a consumer GPU — copy versus recompute — What does it mean?

The news. On October 13, 2026, a group from Southwest Jiaotong University and partner institutions posted SparPR (Sparse Partial Recomputation) to arXiv. It is a training-free runtime layered on the FlexGen offloading engine, with no change to model weights. On an RTX 3070 Ti laptop with 8 GB of GPU memory it reports 31% to 63% lower latency at 1K to 4K prompt tokens and finishes an 8K-token run where FlexGen times out. Read the paper →

Picture a reader with a small desk and a warehouse across town. Every page already read must stay reachable, because the next sentence may need any of them. That is the KV cache: it adds one entry per token in every layer, and on an 8 GB laptop GPU it overflows the desk long before the model's context window runs out. The standard rescue is to shelve old pages in the warehouse (host RAM, then SSD) and fetch them on demand, which is what FlexGen does. Every fetch is a courier trip over PCIe, and a decode step that needs the whole history waits on the courier. The PCIe link is much slower than the GPU's own memory, so the trips, not the arithmetic, set the pace.

SparPR starts from two observations. A decode step does not need every old page, and a missing page does not always need a courier. A page can be re-derived from a note card: SparPR checkpoints a hidden state and, on the sparse path, rebuilds a block's keys and values through the attention projections only, without re-running the MLP or a full forward pass. Whether the rebuild beats the trip depends on the block size, the bus speed and the GPU's compute, so the choice has to be made at runtime, not fixed in advance.

The runtime answers three questions in order, and each maps to a piece of the reader's routine.

1. Which pages matter right now? Each block has an index card: its mean key vector per head, a few numbers that stay on the GPU. The current query is compared with the cards only, so scoring never touches the offloaded blocks themselves, which keeps the check cheap. The top-k blocks by similarity are kept. Because k is a count, the selection stays stable as the number of candidate blocks grows.

2. How many pages should be kept? SparPR estimates the copy cost of one block (its bytes, keys plus values, divided by the effective host-to-device bandwidth) and its recompute cost (which scales with block length and the square of the hidden dimension). Their ratio sets the keep ratio: the paper's rule of thumb is that when copying dominates, keep more blocks to avoid repeated loads, and when recomputing dominates, keep fewer. A Minimum Keep Floor stops the budget from shrinking too far under pressure.

3. Rebuild the sparse set, or fetch everything? Kept blocks are scattered across the context, and recovering them one at a time adds fragmentation and fixed overhead. So adjacent blocks are merged into continuous spans, and the sparse cost (which grows with both blocks kept and spans formed) is compared with the full-recovery cost. If sparse recovery is not cheaper than a set fraction of full recovery, the runtime falls back to the dense path. That fraction is the Dense Fallback Threshold.

Here is why fragmentation matters, with illustrative numbers (the paper does not publish these constants). Take a history of 100 blocks. Copying one block costs 10 ms, so full recovery costs 100 × 10 = 1,000 ms. Rebuilding one block costs 4 ms, each span adds 16 ms of organizing overhead, the sparse path has a fixed 40 ms overhead, and the threshold is 0.8, so the fallback line sits at 800 ms. Suppose the query selects 40 blocks.

• If they merge into 5 spans, sparse cost is 40 × 4 + 5 × 16 + 40 = 280 ms, far below 800 ms, so the sparse path wins.
• If the same 40 blocks are scattered into 40 separate spans, the cost is 40 × 4 + 40 × 16 + 40 = 840 ms, above 800 ms, so the runtime falls back to dense recovery.

The same blocks, kept in a different arrangement, flip the decision. The paper's ablation shows the same pattern: without span merging, sparse cost rose from 728 ms to 1,085 ms, worse than the 952 ms FlexGen baseline in that test (Table 6).

The measured results come from one laptop (RTX 3070 Ti 8 GB, Ryzen 9 6900HX, 16 GB RAM) running OPT-6.7B at batch size 4. In this setup DeepSpeed and HF Accelerate ran out of memory before 1K tokens, and a Quest-style query-aware selection ran out of memory at 1,200 tokens. Only FlexGen and SparPR stayed runnable, and the gap between them widened with context length because SparPR bounds the growth of the recovery cost.

At 4K tokens that is 4,174 s down to 1,553 s, a 2,621 s saving, and the 8K run finishes in about 44 minutes where the baseline never does. The seconds are large because FlexGen spills to CPU memory and disk on this small GPU; the table shows relative savings on one setup, not interactive speed.

Query-aware selection holds up when the budget is tight, but it is not free of loss. SparPR's needle accuracy still falls as the context grows, since longer distractor text makes the needle's block harder to pick out. In the ablation at 1,000 tokens, SparPR-full scored 0.957 against FlexGen's 0.983, a small regression bought for the lower latency. The authors name their own limits: one model (OPT-6.7B), one consumer GPU, and a constructed needle task rather than standard long-context benchmarks. Treat the speedups as a demonstration of the copy-versus-recompute idea, not as a general figure for other models or hardware.

Goes deeper in: LLM Internals → KV Cache → Memory Cost

Related explainers

• Selective KV recomputation for RAG caches — another case where re-running a chosen subset of cached blocks beats reusing all of them
• Partial loads from a lower cache tier — the serving-side view of fetching only part of an offloaded cache