A video language model watching a live stream has to keep an internal record of every frame it has seen: the key and value vectors (the "KV cache") that later questions attend to. That record grows with every frame, and most of it is redundant, because consecutive frames show the same scene. Current systems handle this in one of three ways. They throw tokens away (sliding windows, attention-based eviction). They average tokens together (frame prototypes, cosine-similarity merging). Or they quantize everything. Each option loses information in a way that nobody can bound, and the losses surface exactly where streaming benchmarks are hardest: recalling earlier events and telling repeated actions apart.
This note proposes a different operation, taken from online kernel learning. We never delete a redundant token and we never move a key. Instead we absorb the token into a small, continuously maintained dictionary of stored tokens. The key observation is that one attention head's softmax output is a ratio of two kernel expansions over the stored keys. So the classical test for whether a new point is redundant, approximate linear dependence (ALD), applies directly to attention. That test asks whether the point's feature vector is almost a linear combination of the dictionary's feature vectors. When a token passes it, its value vector and its share of the softmax mass can be folded into the dictionary's stored values and masses, with an explicit per-token error bound on the attention output for every possible future query. The cache then stays bounded without committing to any query in advance.
Core Claim
Write one attention head with temperature $\tau=\sqrt{d}$ and use the identity
$$ \exp(q^\top k/\tau) = c(q)\, g(k)\, G(q,k),\qquad G(q,k)=\exp\!\big(-\|q-k\|^2/2\tau\big),\; g(k)=\exp\!\big(\|k\|^2/2\tau\big),\; c(q)=\exp\!\big(\|q\|^2/2\tau\big). $$
Here $q$ is a query and $k$ a key. $G$ is a Gaussian kernel whose feature map $\psi$ has unit norm, $g$ is a per-key mass, and $c(q)$ cancels in the softmax ratio. For a dictionary of stored keys $k_1,\dots,k_m$ with accumulated value vectors $V_j$ and scalar masses $W_j$, attention is then exactly
$$ o(q)=\frac{\sum_{j} G(q,k_j)\,V_j}{\sum_{j} G(q,k_j)\,W_j}. $$
Initially $V_j=g(k_j)v_j$ and $W_j=g(k_j)$, which recovers standard attention. Both the numerator and the denominator are functions in the Gaussian kernel's feature space (the reproducing kernel Hilbert space, RKHS), and they share one dictionary.
The absorption rule works as follows. When a new token $(k_t,v_t)$ arrives, compute its projection coefficients $a=K^{-1}G_t$ and residual $\delta_t=1-G_t^\top K^{-1}G_t$. Here $K$ is the dictionary's Gram matrix and $G_t$ is the vector of kernel values between $k_t$ and the dictionary keys. If the weighted residual $g(k_t)\|v_t\|\sqrt{\delta_t}$ is below a tolerance $\varepsilon$, set $V_j \mathrel{+}= a_j g(k_t) v_t$ and $W_j \mathrel{+}= a_j g(k_t)$ and discard the token. Otherwise, add the token to the dictionary.
Because $\|\psi(q)\|=1$, the Cauchy–Schwarz inequality bounds the change in the numerator by $g(k_t)\|v_t\|\sqrt{\delta_t}$ for every query, and the denominator obeys the same bound with $\|v_t\|$ replaced by 1. The weighting by $g(k_t)$ matters. It means high-norm "outlier" keys, which Compactor found carry information that attention scores miss, are automatically protected from absorption. When the fixed memory budget is reached, the atom whose removal costs least under the same bound is itself absorbed into the remaining atoms. This is the budgeted-dictionary logic of Sparse Representation for Gaussian Process Models, transplanted to attention.
The claim to test is this: at equal memory, absorption preserves the information that backward-tracing and fine-grained streaming questions need better than eviction, averaging, or static anchor projection. The dictionary should also grow roughly logarithmically in stream length on static footage, as the eigenvalue-decay analysis of Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression predicts for Gaussian kernels.
Relation to Prior Work
Four papers motivate or constrain the design.
AnchorKV is the closest method. It stores full-precision anchor tokens and represents every other text token by an anchor index, a scalar coefficient and a 2-bit residual, retaining 99.3% of RULER at 20× compression. It still keeps one entry per token inside the softmax, chooses anchors heuristically and once after prefill, and never updates them. Our proposal removes absorbed tokens from the cache entirely, so attention cost shrinks as well as memory. It chooses atoms by an explicit redundancy test, and it maintains them online over unbounded streams.
Compactor uses approximate leverage scores to decide which text tokens to keep, as a batch step after prefill. It supplies evidence that geometry-based retention works, but it drops the tokens it does not select. We keep their contribution.
StreamMem and DyCoke are the averaging family. StreamMem merges non-selected tokens into one prototype per frame. DyCoke merges tokens that are cosine-similar across adjacent frames. Both average keys, which changes the kernel itself and blurs detail. Our rule never alters a stored key, and it measures redundancy against the span of the whole dictionary rather than against one neighbour.
DSCache constrains the design. It shows that repeatedly updating one streaming cache contaminates recent events, the "cumulative effect", and fixes this with a separate recent-frame buffer. We adopt its split: recent frames stay raw and only the past is absorbed. We then test whether bounded absorption reduces contamination relative to its compaction.
QueryStream is not a direct competitor. It requires knowing the question in advance, and our setting is query-agnostic ingestion.
The data-redundancy literature enters as a lens rather than as a mechanism. Learning and Data Selection in Big Datasets argues that the data size sufficient for a target accuracy grows sublinearly with the data available. Dataset-pruning methods such as Dyn-Unc show that informativeness-based selection beats uniform sampling. We ask the streaming analogue: does the number of genuinely new directions in a head's key stream grow sublinearly? We measure this directly as dictionary size against stream length.
Research Program
The first stage is offline and cheap. We record full KV streams from a video language model on long videos and replay them through the absorption rule. At each budget we measure the exact attention-output error, using held-out query vectors taken from real question tokens. We compare three treatments of the same selected dictionary: absorbing redundant tokens, dropping them, and averaging them. This stage also checks whether the error bound is tight enough to be useful, and how dictionary growth depends on scene type (static camera, egocentric motion, edited movies).
The second stage builds the method into inference. Running an exact ALD test per head and per layer with thousands of atoms costs $O(m^2)$ per token, which is too slow. We therefore project each token onto only its $s$ nearest atoms (with $s$ around 4 to 16), using coefficients restricted to be nonnegative. This keeps the masses $W_j$ positive, which the denominator's stability requires, and turns the $m\times m$ inverse into many small solves. Tokens are processed one frame at a time. The masses $g(k)$ are exponential in the key norm, so all accumulation is carried out in log space relative to a running per-head maximum.
We operate on keys after the rotary position encoding (RoPE) has been applied, so the kernel identity stays exact for relative positions. A variant uses DSCache-style re-indexing to test whether storing keys before position encoding lets repeated scenes far apart in time be absorbed into one another. The tolerance $\varepsilon$ is adjusted online to hit a fixed byte budget. This addresses the threshold sensitivity flagged for ALD methods in the online kernel literature. The rule is training-free and plugs into the DSCache codebase (pangzhan27/DSCache), which already supports StreamingBench and OVO-Bench.
Baselines
The naive reference is a FIFO sliding window at the same memory budget. It keeps the most recent frames' tokens and evicts the oldest. StreamMem reports that simple eviction reaches 55.8% on RVS-Ego. A second naive reference is uniform frame subsampling tuned to the same token count. We also report the uncompressed model where it fits in memory. For LLaVA-OneVision-7B, StreamingBench reports 56.36%.
The strongest query-agnostic streaming competitor with an absolute reported number is StreamMem: 57.6% on RVS-Ego at 6K tokens per layer. We will run it through its proxy-query selection and prototype merging at exactly 6K tokens per layer, on the same base model and frame rate. Beating it means exceeding its accuracy at equal bytes, where our byte count includes the stored masses and values. It also means matching it at a strictly smaller budget.
DSCache is the second strong competitor. It reports a 2.5% average gain over prior methods on StreamingBench and OVO-Bench, but no absolute number was found in the file. We will rerun its released code under identical settings, including its recent-frame buffer. That comparison isolates the past-cache treatment, since both systems share the recent-frame buffer.
We also transplant two static text methods into the streaming loop, to check that the gain is not merely from online operation. One is AnchorKV-style nearest-anchor projection that keeps per-token entries; the other is Compactor-style leverage-score retention that drops everything else. DyCoke's adjacent-frame cosine merging is run at matched token count. All methods get the same tuning budget, a grid of equal size over their main threshold, selected on a held-out split of each benchmark.
Three ablations isolate the key ingredients. The first uses the same ALD selection but drops redundant tokens instead of absorbing them. This tests whether absorption, not selection, is what helps. The second absorbs by averaging keys into atoms instead of keeping keys fixed and folding into values and masses. This tests the kernel-exact update. The third sets $s=1$, i.e. absorption into the single nearest atom, and removes the $g(k)$ weighting from the redundancy test. This tests whether multi-atom projection and outlier protection matter.
Why not just…?
Why not just keep a sliding window and a bigger GPU? Windows lose early context entirely, so backward-tracing questions become unanswerable regardless of memory. The file documents this: StreamMem reports eviction below structured memory on RVS-Ego, and AnchorKV reports eviction methods collapsing to 0.18 on Needle-in-a-Haystack against 0.94 for its representation. Our experiments report OVO-Bench Backward Tracing separately so this failure is visible. A window that grows with the hardware still grows as $O(T)$.
Why not just merge similar tokens by averaging, as DyCoke and StreamMem do? Averaging is the real simple competitor, and it may be enough on short clips. DyCoke loses only half a point on MVBench (57.5 against 58.0). The difference we expect is on long streams and fine detail. Averaging moves keys, so later queries see a kernel centred somewhere no real token was, and the error is unbounded. Absorption leaves keys fixed. The offline replay stage measures attention-output error for both at equal budgets, and the key-averaging ablation settles the question directly. If averaging matches absorption on benchmark accuracy, we will report that the kernel-exact update is unnecessary in practice.
Why not just run AnchorKV online? This is the most serious threat, because nearest-anchor projection is close to our $s=1$ variant. The distinction is that AnchorKV keeps one softmax entry per token, so it compresses bytes but not attention length, and it never revises its anchors. We run exactly this transplant as a baseline. If it matches us at equal bytes and equal decode latency, the contribution reduces to the budget-maintenance rule. We will report the result in those terms.
Why not just quantize the whole cache? AnchorKV reports that pure quantization rarely goes beyond 4–5× compression without degrading reasoning. StreamingTOM (StreamingTOM) needed temporal token reduction on top of 4-bit memory to control prefill cost. Quantization is also orthogonal to our method: we will quantize the dictionary's values and report the combination, rather than treating quantization as a rival.
Proposed Experiments
The main evaluation uses StreamingBench, OVO-Bench and RVS-Ego/RVS-Movie. Base models are LLaVA-OneVision-7B and Qwen2.5-VL-7B. Each method is evaluated at cache budgets of 2K, 4K, 6K and 12K tokens per layer, measured in bytes, and we report accuracy, peak memory, per-frame ingestion latency and time to first token. Offline long-form evaluation on Video-MME's long subset checks that absorption does not harm general understanding. MVBench serves as a short-clip sanity check, where every compressor should nearly tie.
Three checks decide the outcome. First, on replayed KV streams, absorption must give lower worst-case and mean attention-output error than dropping or averaging at every budget. The measured error should track the predicted bound $\sum_t g(k_t)\|v_t\|\sqrt{\delta_t}$; if the bound is loose by orders of magnitude, the theoretical story fails even if accuracy holds. Second, at 6K tokens per layer on RVS-Ego, the method must exceed StreamMem's 57.6%. It must also improve OVO-Bench Backward Tracing and Hallucination Detection over DSCache's compaction, the tasks where discarded state transitions should matter most. Third, dictionary size plotted against stream length should look logarithmic on static-camera footage and closer to linear on edited video. That would confirm that the dictionary tracks the real redundancy of a stream rather than a fixed schedule.
If ingestion overhead exceeds the savings in decoding, or the drop-instead-of-absorb ablation matches the full method, the proposal fails in a clearly identifiable way.
References
- Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores
- Sparse Representation for Gaussian Process Models
- Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression
- AnchorKV: Anchor-Residual KV Cache Compression
- StreamMem: Query-Agnostic KV Cache Memory for Streaming Video Understanding
- DyCoke: Dynamic Compression of Tokens for Fast Video Large Language Models
- Decouple and Cache: KV Cache Construction for Streaming Video Understanding
- QueryStream: Advancing Streaming Video Understanding with Query-Aware Pruning and Proactive Response
- Learning and Data Selection in Big Datasets
- Large-scale Dataset Pruning with Dynamic Uncertainty
- StreamingBench: Assessing the Gap for MLLMs to Achieve Streaming Video Understanding
- StreamingTOM: Streaming Token Compression for Efficient Video Understanding