DeltaS: Reading the Gated Linear Attention State for KV Cache Eviction in Streaming Video

Summary (Overview)

• Proposal: DeltaS, a query-agnostic, training-free KV cache eviction method for streaming video understanding in hybrid (linear + full attention) architectures, which uses the normalized change in the recurrent state (state drift) of gated-delta linear attention as a retention signal.
• Key insight: In gated-delta linear attention, the recurrent state is updated by the residual between incoming input and what can already be retrieved from the state; thus, larger state changes indicate chunks bringing more new information worth retaining.
• Results: DeltaS outperforms all query-agnostic, bounded-memory baselines on six long-video benchmarks (best on all six at M=8,192; five of six at M=16,384), surpassing the strongest baseline by 2.1 and 1.7 points on average, respectively, with gains growing under tighter memory budgets (up to +5.6 points on the longest benchmark).
• Efficiency: The state drift signal costs only 1.9% of the forward pass (2.07 ms per chunk), with total overhead of 6.4 ms per eviction event—the lowest among signal-computing methods.
• Controlled comparison: With budget and retention policy held fixed, state drift outperforms position-, attention-, and key-value-based retention signals, demonstrating that the recurrent state and KV cache of hybrid architectures can work cooperatively.

---

Introduction and Theoretical Foundation

Background and Motivation

Streaming video understanding requires processing an unbounded input stream under a bounded memory budget. Recent open-source multimodal backbones increasingly adopt hybrid architectures that interleave linear and full attention layers, introducing two distinct forms of temporal memory:

1. Fixed-size recurrent state in linear attention layers
2. Token-wise KV cache in full attention layers

In the 3:1 hybrid backbone used in this work (Qwen3.5-9B), the recurrent states remain fixed at 48 MiB, while the KV cache of full-attention layers grows linearly with stream length, exceeding 10 GiB after one hour. Thus, hybrid architectures still require explicit KV cache management for bounded-memory streaming.

A critical constraint: eviction must occur before the question arrives, so retention signals must be query-agnostic. Existing methods derive token scores from the KV cache itself (position, attention, or key-value representations), with attention-based scores requiring proxy queries or extra computation.

Theoretical Foundation: Gated Delta Rule

The key theoretical insight is the update structure of gated-delta linear attention. For a single linear-attention head, the state update follows:

$$S_{t} = S_{t-1} \left(\alpha_{t} (I - \beta_{t} k_{t} k_{t}^{\top})\right) + \beta_{t} v_{t} k_{t}^{\top}, \tag{1}$$

where $t$ indexes tokens, $k_t$ is the L2-normalized key vector, $v_t$ is the value vector, $\alpha_t$ controls state decay, and $\beta_t$ determines write strength. Rearranging:

$$S_{t} = \alpha_{t} S_{t-1} + \beta_{t} \left(v_{t} - \alpha_{t} S_{t-1} k_{t}\right) k_{t}^{\top}. \tag{2}$$

The update depends on the residual between the incoming value $v_t$ and the value retrieved from the decayed state, $\alpha_t S_{t-1} k_t$. This residual, scaled by write gate $\beta_t$, determines what gets written to the state. Therefore, how much a chunk changes the state reflects how much new information it brings beyond what the state already holds.

Multi-Scale Temporal Memory

The recurrent state operates at multiple temporal scales: some heads retain state contributions for only a few seconds, while others preserve more than half of an earlier contribution after one minute. The ranking of per-head retention horizons is nearly identical across three benchmarks ($\rho \approx 0.998$), providing a rich reference against which incoming chunks can be evaluated.

---

Methodology

State Drift Definition

DeltaS compares the recurrent states before and after processing each video chunk, defining the state drift as:

$$\Delta S = \frac{1}{L} \sum_{i=1}^{L} \frac{\left\| S_{\text{after}}^{i} - S_{\text{before}}^{i} \right\|_F}{\left\| S_{\text{before}}^{i} \right\|_F}, \tag{3}$$

where $L$ is the number of linear-attention layers and $\|\cdot\|_F$ denotes the Frobenius norm over the full state of each layer (including all heads). Normalization by the pre-chunk state magnitude makes the change comparable across layers, and averaging yields a single score per video chunk.

DeltaS Algorithm

Key design components:

1. Chunk-level scoring: Each chunk (one second of video, containing 98–112 visual tokens + 20 timestamp tokens) receives a single $\Delta S$ score assigned to all its tokens.

2. Reserved regions: The first $n_s = 4$ tokens serve as attention sinks; the most recent $n_w = 1{,}024$ tokens form a local context window—both retained independently of the score.

3. Temporal bucketing: To mitigate early-stream bias (state drift scores tend to be higher near the beginning), candidate tokens are divided into $N = 4$ equal temporal spans based on chunk arrival times, with equal budget shares allocated to each span. Within each span, higher $\Delta S$ tokens are retained first.

4. Position preservation: Retained tokens keep their original position indices (no reassignment), preserving positional spacing and eliminating the need for key re-rotation.

5. Question isolation: The state is saved before processing each question and restored afterward (including KV entries and scores), preserving query-agnostic behavior.

Algorithm 1: DeltaS: state-guided KV eviction

Input: budget M; sink n_s; window n_w; buckets N
1: while a new chunk c arrives do
2:   S_before ← S
3:   PREFILL(c)                     ▷ updates S, appends c to KV
4:   ΔS ← mean_i(‖S^i − S_before^i‖_F / ‖S_before^i‖_F)
5:   score[t] ← ΔS for all tokens t of c
6:   if |KV| > M then
7:     I_sink ← first n_s, I_window ← last n_w
8:     B_1…B_N ← N equal time spans of the rest
9:     I_ΔS ← top-((M−n_s−n_w)/N) of each B_j by score
10:    KV ← KV[I_sink ∪ I_ΔS ∪ I_window]
11:  end if
12: end while

Computational Efficiency

The signal computation requires only:

• A copy of the previous state (fixed size, doesn't grow with stream length)
• Frobenius norms of the state difference and previous state

No additional forward pass or explicit attention computation is needed.

---

Empirical Validation / Results

Experimental Setup

• Backbone: Frozen Qwen3.5-9B (24 linear-attention layers, 8 full-attention layers; 3:1 interleaving)
• Video sampling: 2 fps, fixed pixel-budget setting (StreamingVLM)
• Budgets: M = 8,192 and M = 16,384 tokens per layer (~256 MiB and ~512 MiB total KV memory)
• Benchmarks: MLVU, Video-MME, Video-MME v2, LongVideoBench, LVBench, EgoSchema
• Baselines: InfiniPot-V, StreamMem, HERMES, plus random/recency/uniform controls; Full KV and ReKV as reference settings

Main Results

Table 1: Performance on six long-video benchmarks under two KV cache budgets (M = 8,192 / 16,384)

Key findings:

• DeltaS achieves the best results among query-agnostic, bounded-memory methods on all six benchmarks at M=8,192 and five of six at M=16,384
• Average gains of 2.1 points (M=8,192) and 1.7 points (M=16,384) over StreamMem (strongest baseline)
• At M=8,192, DeltaS (58.7 avg) nearly matches StreamMem at double the budget (58.8 avg)
• On LVBench (longest benchmark): +5.6 points at M=8,192 and +4.3 points at M=16,384
• Gains generally grow as retention rate decreases (from 36.4% on EgoSchema to 1.8% on LVBench)

Controlled Comparison of Retention Signals

Table 2: Controlled comparison (M = 8,192, shared policy)

Both state-based signals outperform all cache-internal signals. DeltaS exceeds the strongest cache-internal signal (VaN) by 0.7–2.1 points and the state-based baseline β‖e‖ by 0.5–1.2 points.

Ablation: Temporal Bucketing

• Without bucketing, retained tokens concentrate heavily toward the beginning of the video
• Temporal bucketing brings the cumulative retention distribution closer to the uniform diagonal
• Bucket count $N = 4$ yields the largest average accuracy gain across LongVideoBench, MLVU, and LVBench; gains decrease at $N = 8$

Efficiency Analysis

• State drift signal: 2.07 ms = 1.9% of the 107 ms chunk forward time
• Total additional cost (signal + selection + eviction): 6.4 ms per eviction event
• InfiniPot-V: 15.4 ms; StreamMem and HERMES exceed the chunk forward time itself
• β‖e‖ (token-level residual computation): 206.1 ms total—DeltaS achieves higher accuracy at substantially lower cost

---

Theoretical and Practical Implications

Theoretical Implications

1. Cooperative memory in hybrid architectures: The results demonstrate that the two memories of hybrid architectures (fixed-size recurrent state and growing KV cache) can work cooperatively rather than independently. The recurrent state serves not only as a summary of past context but also as a reference signal for deciding what to retain in the token-wise cache.

2. Prediction error as importance signal: The success of state drift validates the theoretical connection between delta-rule residual updates and information novelty. Chunks that induce larger state changes are precisely those that bring more new information—a principle aligned with prediction-error-based memory theories (B'MOJO, Titans, HOLA).

3. Multi-scale temporal reference: The recurrent state combines heads with different retention horizons (from seconds to minutes), providing a reference that spans multiple temporal scales. This multi-scale property makes it a richer signal than any single-scale cache-internal measure.

4. Query-agnostic retention is viable: The strong performance (58.7 avg at M=8,192) approaches the query-aware ReKV baseline (59.8) while remaining fully query-agnostic, suggesting that effective retention decisions can be made without knowing the question.

Practical Implications

1. Memory efficiency: DeltaS at half the budget (M=8,192) nearly matches the best baseline at double the budget (M=16,384), enabling longer streaming sessions under the same memory constraints.

2. Negligible overhead: With signal computation costing only 1.9% of the forward pass and total overhead of 6.4 ms per eviction event (lowest among signal-computing methods), DeltaS is practical for real-time streaming applications.

3. No training or architecture changes: DeltaS works on frozen pretrained models with no additional training, proxy queries, or new memory modules, making it immediately deployable.

4. Scaling to longer videos: The advantage grows as retention rates decrease, making DeltaS particularly valuable for very long videos where only a tiny fraction of content can be retained.

---

Conclusion

DeltaS introduces a principled, query-agnostic, training-free KV cache eviction method for streaming video in hybrid architectures. By reading the normalized state change (state drift) of gated-delta linear attention, it identifies video chunks that bring the most new information and prioritizes their retention in the full-attention KV cache.

Key takeaways:

• State drift outperforms position-, attention-, and key-value-based retention signals under controlled conditions
• DeltaS achieves best-in-class performance across six long-video benchmarks, with larger gains under tighter memory budgets
• Temporal bucketing effectively mitigates early-stream bias while improving accuracy
• The approach requires minimal computational overhead, reusing states already produced by the forward pass

Future directions:

• Validation across other hybrid architectures and model scales
• Extension to other state-update rules beyond gated delta
• Finer-grained scoring within chunks (currently all tokens in a chunk share a single score)
• The authors note that some benchmarks (StreamingBench, OVO-Bench) do not consistently reward longer context, suggesting the need for benchmarks that better isolate long-term retention capabilities

Limitations (as acknowledged by the authors): single-backbone evaluation, dependence on the gated delta rule's residual update structure, and chunk-level (rather than token-level) scoring granularity.