acceptodds
Under review as a conference paper at ICLR 2027

ResKV-Tree: Residual KV-Caching Tree For Streaming Video Understanding

Abstract

Streaming video understanding requires storing historical evidence for questions that are unknown when frames arrive, making it essential to reduce memory redundancy while preserving potentially useful details. Existing methods rely on granularity-agnostic storage that compresses all evidence uniformly, making it difficult to preserve information at different granularities. To address this, we propose Residual KV-Caching Tree (ResKV-Tree), a hierarchical KV-caching structure for effective and efficient evidence retrieval. During the construction of ResKV-Tree, we select nodes to merge based on semantic similarity, temporal proximity, and evidence saliency, then apply KV non-maximum suppression (KV-NMS) to remove redundant KV pairs using key-based saliency estimation and value-based redundancy suppression. To form the hierarchical structure, we recursively promote salient KV pairs to parent nodes and keep residual ones in children. During question answering, best-first search is employed to explore hierarchical paths starting from the roots and efficiently retrieve relevant evidence at different granularities. Extensive evaluations on two streaming and three offline video understanding benchmarks demonstrate the superiority of ResKV-Tree over baselines and recent methods across three different backbones.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Streaming video understanding, Hierarchical KV caching, KV cache compression, Question-guided evidence retrieval

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_1wAMOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents ResKV-Tree, a hierarchical KV cache representation for training-free streaming video understanding. The paper focus on the query-agnostic streaming video understanding setting, where future questions are unknown when video frames arrive. ResKV-Tree addresses limitations in existing methods by recursively organizing historical KV pairs into a hierarchical "residual tree" structure.

The the number of roots reaches a predefined budget, two roots are merged. The KV-NMS module removes redundant KV pairs by combining a saliency score based on a proxy query and a value space similarity score. Among the remaining KV pairs, the salient ones are promoted to a new parent, and others remain in the child nodes. At test time, the pipeline does a best-first search over the tree using the true user query.

The experiments involve three LLM backbones, three offline video benchmarks, and two streaming video benchmarks, and demonstrate that ResKV-Tree consistently improves over the baselines.

Critical strengths
  • The proposed residual hierarchy is well-motivated. It alleviates the tension between compression and preserving fine-grained evidence with an intuitive design. The tree search step allows retrieval at different levels of granularity.
  • The empirical results are strong and reasonably comprehensive. ResKV-Tree consistently improves performance across three backbones and both streaming and offline benchmarks. The improvement on OVO-Bench are particularly large.
Critical weaknesses
  • There is not sufficient evidence for the claimed efficiency advantages. Efficiency is an important motivation for the proposed method. The paper mainly reports end-to-end TTFT and peak GPU memory after 1024 frames. Isolating the latency for tree construction, maintenance, and search costs and reporting them separately can be helpful.
  • Hyperparameter selection process is unclear. The proposed pipeline introduced many hyperparameters and it is unclear how their values are selected; in particular, whether they were selected on a held-out validation set and then kept fixed across all reported benchmarks and backbones.
Questions for authors
  • I found the irreversible KV pruning design in KV-NMS a bit unintuitive. Have you compared the current KV-NMS design against a variant that does not permanently discard redundant KV pairs, but instead retains or demotes them to deeper residual nodes?
  • How do the computational and memory costs scale with video length?
Reviewer_LqdXOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper proposes ResKV-Tree, a training-free KV-cache memory for streaming video QA. Each 16-frame chunk is encoded by a frozen Video-LLM, and its pre-RoPE KV pairs are scored against a fixed pseudo-question. With more than N=8 roots per layer, two roots are merged according to a semantic/temporal/saliency score. "KV-NMS" drops the most value-redundant half of their KV pairs; the most salient half of the rest goes to a new parent, and the remainder stays in the children. At query time, a per-layer best-first search collects up to 4K KV pairs. Experiments cover five benchmarks and three backbones.

Critical strengths
  1. A training-free, plug-in method with consistent gains.
    • Against HERMES's published numbers, it is better on all three backbones.
    • With Qwen3-VL-8B, it also beats HERMES on all three Backward Tracing tasks.
    • The Qwen3-VL-8B variant reaches 82.20 on StreamingBench and 69.04 on OVO-Bench.
  2. A clean, fully specified design.
    • Parent and child sets are disjoint, so nothing is stored twice.
    • Pre-RoPE keys allow position-free scoring and re-positioning.
    • Algorithms 1–3 and all hyperparameter values are given.
    • Residual retention, tree search, the merge criteria, KV-NMS variants and tree arity are ablated.
    • TTFT and peak memory are compared with four systems.
Critical weaknesses
  1. The gains are not attributed to the proposed components.
    • Table 3's stripped variant has no residual retention and no tree search. It already raises Qwen2.5-VL-7B from 73.3 to 78.3 on StreamingBench and from 52.3 to 62.2 on OVO-Bench. That is about 70% of the final gain, and it already beats HERMES on OVO-Bench. The two core components add only 2.2–3.9 points.
    • The method is motivated by recovering historical detail, but the gains over HERMES are mostly on Real-Time perception (+8.5 to +11.7 on OVO-Bench) rather than Backward Tracing (+0.1 to +7.0). With LLaVA-OV, ResKV-Tree even trails HERMES on EPM and ASI. Frame rate may explain part of the Real-Time gain: HERMES runs LLaVA-OV at 0.5 fps, ResKV-Tree at 1 fps.
    • The first merge needs at least 144 s of history, and MVBench clips average about 16 s. So no merge ever happens on MVBench, and the +3.6 there cannot come from the tree.
    • The decisive ablation is missing: flat top-B retrieval over the same KV-NMS-pruned store. There are also no statistics on how deep retrieval goes or how often residual children are actually used.
  2. The baseline numbers are mixed and partly below official results. The tables combine copied and re-run numbers at different frame rates, without saying which is which.
    • Qwen2.5-VL-7B (offline): The base row (64.5 / 66.9 / 65.0 on VideoMME / MLVU / MVBench) is below the official 65.1 / 70.2 / 69.6. Against the official numbers, ResKV-Tree is below its own backbone on MLVU (69.1) and MVBench (68.6).
    • Qwen3-VL-8B (streaming): The base (75.66) is the authors' own run, while the "+HERMES" row is copied from HERMES's 2-fps run, whose own base is 78.92. Against that base, the StreamingBench gain falls from +6.5 to +3.3.
    • ThinkStream: Table 1 lists ThinkStream-3B, while Table 7 lists the stronger ThinkStream-7B. The 7B model's Backward Tracing (60.68) beats every ResKV-Tree variant (best 56.30).
  3. Memory is unbounded, so the budget comparison is not like-for-like.
    • Algorithm 1 never revisits residual children. With α=β=0.5, about one third of all encoded KV is kept permanently, so storage grows linearly with stream length.
    • Comparing at "HERMES's 4K budget" is therefore misleading. HERMES's 4K is its entire fixed-size per-layer cache. ResKV-Tree's 4K is only a retrieval budget over an unbounded store, which is the very trade-off Fig. 1(b) criticises HERMES for.
    • Fig. 4 reports a single point at 1024 frames (18.82 vs. 17.66 GB). It does not say where the trees are stored (the small gap suggests CPU), how memory scales with stream length, or how ReKV (31.14 GB) was configured.
Questions for authors
  1. Baselines.
    • For the base models, HERMES and ResKV-Tree: what frame rate, number of frames, resolution and visual tokens per frame does each use?
    • Which rows are copied and which re-run? Why do the Qwen bases differ from the official and HERMES-reported values?
    • Can you report the same backbone with chunked 1-FPS encoding, using (i) only the latest chunk and (ii) flat top-B retrieval over the KV-NMS-pruned store? Please split the OVO-Bench gain into Real-Time and Backward.
  2. Memory.
    • Where are the trees stored?
    • How do stored KV size, peak GPU/CPU memory and per-chunk construction time scale with stream length, e.g. 1–3 h?
    • How does ResKV-Tree compare with HERMES at matched total memory?
    • How was ReKV configured for Fig. 4?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.