Keyframe Residual Coding for GPU-Resident Streaming Video KV Caches

A video language model that watches a live stream builds up a memory of everything it has seen. This memory is the key-value (KV) cache, the per-token vectors that attention looks back at. It grows by thousands of tokens per second of video and soon outgrows GPU memory. Current systems handle this in one of two ways. They either throw tokens away for good, which keeps the system fast but loses the detail needed when a later question asks about the past. Or they ship whole uncompressed chunks of the cache to CPU memory and back over the PCIe bus (the comparatively slow link between CPU and GPU), which keeps everything but makes each question wait on the bus and on host-side bookkeeping.

This proposal exploits a third fact. Consecutive video frames are nearly identical, so the cache entry for a given image patch in frame $t$ is close to the entry for the same patch in frame $t-1$. We propose to store each patch location's cache as a full-precision "keyframe anchor" every few frames, plus very low-bit residuals for the frames in between, much as video codecs store I-frames and P-frames. Encoding, indexing, retrieval and reconstruction all run inside GPU kernels. Only the small residuals ever cross PCIe, and only when GPU memory is exhausted. The anchors that stay on the GPU double as the index that decides which residuals to fetch back when a question arrives, so the CPU never has to search anything.

Core Claim

At a matched byte budget, coding video KV entries as residuals against a temporal anchor at the same patch location gives lower attention error than either absolute low-bit quantization or token eviction. The reason is that the frame-to-frame variation of a patch's key is much smaller than the variation of keys across the whole cache. For a uniform quantizer, mean squared error scales as $r^2 2^{-2b}$, where $r$ is the range of the quantized values and $b$ is the bit width. Matching the error of absolute quantization therefore needs about

$$ \Delta b \approx \log_2 \frac{\sigma_K}{\sigma_\Delta} $$

fewer bits per entry. Here $\sigma_K$ is the spread of keys within a layer and head, and $\sigma_\Delta$ is the spread of residuals against the anchor at the same patch location. If $\sigma_K/\sigma_\Delta$ is around 4 to 8 for static or slowly moving content, a 2-bit residual matches roughly a 4-to-5-bit absolute code. That would move video KV compression past the 4–5× "accuracy wall" that AnchorKV reports for plain low-bit quantization, without discarding any token.

The second half of the claim concerns systems. Because anchors stay resident on the GPU, the decision about which past segments a question needs can be made by attending the question over the anchors alone, in device memory. This removes both the host-side search of CPU vector-database designs and the uncompressed block reloads of offloading designs.

Relation to Prior Work

Three papers motivate the gap. InfiniPot-V measures temporal redundancy along the time axis of the key cache with cosine similarity and uses it to evict patches permanently. It cuts peak memory by up to 94% and runs at 14 FPS on a Jetson AGX Orin. We use the same observation, that keys carry temporal structure, but we turn redundancy into cheap residuals instead of deletions. OVO-Bench shows that models routinely fail at backward tracing when past detail is gone, which is exactly the cost of eviction. ReKV offloads full-precision 64-frame KV chunks to host memory and retrieves relevant chunks at question time. It reaches 11–17 FPS and beats uniform sampling by +3.8% on MLVU and +7.4% on QAEGO4D with LLaVA-OV-7B. ReKV is the closest system; we differ in coding what crosses the bus, in granularity (per patch location rather than 64-frame chunks), and in keeping index and reconstruction on the GPU.

The method borrows from several sources. AnchorKV supplies the anchor-plus-2-bit-residual representation and fused Triton kernels, reaching 20× compression with 99.3% of uncompressed RULER accuracy on text. Its anchors are chosen by similarity over a flat token sequence and it never leaves VRAM. Our anchors are defined by the video's own structure (same patch, nearby time), and our residuals are designed to spill. SpeCache keeps a 1–2-bit "scout" copy of the cache on the GPU to decide what full-precision entries to prefetch from CPU RAM, giving 4.6× throughput at 32k context. Our anchors play the scout role, but they are full precision and video-structured rather than a uniformly quantized shadow of text tokens.

The general principle that it pays to keep control logic and variable-length encoding on the device comes from end-to-end GPU compression. GPULZ moved matching, prefix sums and encoding fully onto the GPU and saw up to 272× over a CPU-assisted predecessor. Device-side hashing in WarpCore shows that a GPU-resident index can be updated without host involvement.

Two papers constrain the design. DyCoke shows that video models re-attend to tokens from different frames at different decoding steps, which argues against one-shot eviction; its recycle bin, however, is bounded by VRAM. Synk et al. show that attention over long contexts is extremely sparse (under 2% of tokens), which supports fetching only a small set of segments. Their CPU-side nearest-neighbor search is the host bottleneck we are trying to avoid.

Research Program

The system has four kernels, all of which run without returning control to the host. The model's backbone is LLaVA-OneVision-7B, which StreamingBench, ReKV and DyCoke all use.

The encoding kernel runs immediately after each frame's KV entries are produced, layer by layer. It never materializes an uncompressed multi-frame block, which addresses the grow-then-shrink memory spike documented by InfiniPot-V. For each patch location and head, it compares the new pre-rotary key and value against the current anchor. Keys are taken before rotary position encoding is applied so that position rotation does not inflate residuals; rotation is reapplied at reconstruction. If the residual norm exceeds a threshold, the kernel promotes the frame to a new anchor. Otherwise it writes a 2-bit residual with a per-group scale. This threshold makes anchor density adaptive: static scenes produce few anchors and action bursts produce many. That answers InfiniPot-V's admitted limitation of fixed compression ratios. Output sizes vary, so the kernel allocates from a preallocated ring of fixed-size pages using a device-side prefix sum, as in GPULZ, avoiding device malloc.

The spill kernel runs when VRAM residuals exceed budget. It moves the oldest residual pages to pinned host memory with asynchronous copies. Anchors and a compact per-segment summary stay resident.

The retrieval kernel runs when a question arrives. It attends the question tokens over the resident anchors, picks the top segments, and issues fetches only for those segments' residual pages.

The reconstruction kernel decodes anchor plus residual, applies rotary encoding, and feeds attention directly.

The analysis component comes first. Before building the full system, we measure $\sigma_K/\sigma_\Delta$ per layer and head on StreamingBench and OVO-Bench videos at 1, 2 and 4 FPS. We also measure the attention-output error of residual versus absolute coding at matched bytes. This tells us early whether the core claim holds and at which sampling rates. At low frame rates adjacent frames diverge and the advantage may vanish.

Baselines

The naive reference is the uncompressed full KV cache. We run it with uniform frame subsampling, using the densest rate that fits in GPU memory on the same 48 GB A6000-class card. This is the setting against which ReKV reports its +3.8% (MLVU) and +7.4% (QAEGO4D) gains, and StreamingBench reports a 56.36% average for LLaVA-OneVision-7B under its own protocol. Beating it means higher accuracy at equal or lower peak memory.

The strongest offloading competitor is ReKV, run with its released configuration on the same backbone, GPU and host memory. We report accuracy, time from question to first answer token, and bytes moved over PCIe per question. Its reported numbers are the MLVU and QAEGO4D gains above and 11–17 FPS encoding. No reported result was found on Lacuna for ReKV's absolute RVS-Ego or RVS-Movie scores, so we will rerun it. Beating ReKV means matching its accuracy with at least 4× fewer PCIe bytes per question and lower question latency, or exceeding its accuracy at equal bytes.

The strongest in-memory competitor is InfiniPot-V at the same total byte budget as our VRAM-resident footprint. It reports a 94% peak memory reduction and 14 FPS on Orin, but no absolute StreamingBench or OVO-Bench score was found on Lacuna, so we rerun it. Beating it means higher OVO-Bench backward-tracing accuracy at matched budget without dropping real-time perception accuracy. We also run DyCoke, which reports 57.5 on MVBench against a 58.0 full-token baseline with 1.54× speedup, as the merge-plus-recycle reference.

Two ablations isolate the key ingredient. The first replaces temporal anchors with AnchorKV's similarity-chosen anchors over the flattened video token sequence, holding bits fixed. If this matches us, the temporal structure contributes nothing. The second replaces residuals with absolute 2-bit and 4-bit quantization of every entry at equal bytes. A third, systems-only ablation moves the retrieval step to a CPU nearest-neighbor index over the same anchors, in the style of Synk et al., to measure what GPU residency buys in latency. All methods get the same tuning budget: a grid over their one or two main hyperparameters, chosen on a held-out slice of StreamingBench.

Why not just…?

Why not just quantize ReKV's offloaded blocks to 4 bits? This is the real threat. It is simple, needs no new representation, and cuts PCIe traffic by 4×. The test is the bytes-matched ablation above. If absolute 4-bit offload matches our accuracy and latency at the same bytes, the temporal-residual idea is not worth its complexity and we would report that. The bit-saving relation predicts it should fail when $\sigma_K/\sigma_\Delta$ is large, and the pre-study measures that ratio directly before any system work. AnchorKV's observation that absolute low-bit codes stall around 4–5× compression gives some prior reason to expect a gap at higher ratios, though that evidence is from text.

Why not just subsample frames more aggressively? StreamingBench finds that removing redundant frames can help some models by up to 35%, so subsampling is a strong baseline and we will tune its rate rather than fix it. However, OVO-Bench's backward tracing and real-time perception depend on brief micro-actions that uniform sampling skips. ReKV's gains over uniform sampling show that cache management beats it on long video. Our comparison holds memory fixed, so a gain over subsampling cannot come simply from seeing more frames at higher cost.

Why not just evict, as InfiniPot-V does? Eviction is cheaper and InfiniPot-V reports negligible average accuracy loss. Averages can hide the backward-tracing failures that OVO-Bench isolates, and text evidence from AnchorKV shows eviction collapsing to 0.18 on needle retrieval versus 0.94 for anchor-residual coding. We report OVO-Bench results split by task family so that any eviction advantage on real-time perception is visible rather than averaged away.

Why not just apply AnchorKV directly to video tokens? It already runs fused on the GPU and might discover temporal neighbors on its own. The anchor-choice ablation settles this. If similarity-chosen anchors match temporal anchors, our contribution reduces to the spill-and-retrieve path. That path would still need to be justified against ReKV on its own terms.

Proposed Experiments

Each experiment answers one question in order. The first is a measurement study of residual-to-key spread ratios and matched-byte attention error across layers, heads and frame rates. It is the go/no-go check for the whole proposal: if the ratio is near 1 at the 1–2 FPS rates streaming models actually use, we stop. The second is accuracy at matched memory on StreamingBench, OVO-Bench (split by backward tracing, real-time perception and forward responding), MLVU, QAEGO4D, and the hour-long RVS-Ego and RVS-Movie, against every baseline above. The third measures systems cost on an A6000-class GPU and on a Jetson AGX Orin: sustained ingestion FPS, peak VRAM including transient spikes, question-to-first-token latency, and PCIe bytes per question. On the Orin, the InfiniPot-V comparison is most direct.

Two outcomes would be decisive. The proposal is supported if bytes-matched residual coding beats absolute quantization on backward tracing, and if GPU-side anchor retrieval beats both ReKV and the CPU-index ablation on question latency at equal accuracy. If either fails, the result still shows which part of the video cache problem is about representation and which is about where the search runs.