acceptodds
Under review as a conference paper at ICLR 2027

One Ranking, Any Budget: Matryoshka Evidence-to-Context Frame Selection for Long-Video Understanding

Abstract

Frame selection is essential for applying Large Multimodal Models (LMMs) to long videos due to severe frame redundancy and limited context windows. Since the appropriate frame budget varies with the downstream LMM, reasoning demands, and latency constraints, a practical selector should serve multiple budgets. However, existing methods typically optimize an isolated frame subset for each predefined budget: when the budget changes, previously selected evidence may be replaced rather than progressively augmented. A fixed-weight ranking allows prefix reuse across budgets but applies the same weighting at every position, overlooking the distinct roles of early and later ranks. We formulate long-video frame selection as a Matryoshka ranking problem: constructing a single priority sequence whose small prefixes concentrate query-conditioned evidence, while progressively larger prefixes preserve this evidence and add broader temporal context. Efficiently constructing such a ranking is itself challenging, as densely sampling long videos and evaluating frame–query relevance incurs substantial overhead. We therefore introduce atryoshka vidence-to-ontext () Frame Selection, a training-free framework that builds a reusable sparse video index, discovers candidates through sparse probing and local zooming, and greedily constructs a position-adaptive ranking—early positions emphasize evidence; later positions progressively favor temporal coverage while preserving visual diversity. A single ranking can thus be truncated to any target budget without rerunning the selector. Across four benchmarks and six frame budgets, \textbf{MEC improves average accuracy over uniform sampling by 3.77 points, matches strong state-of-the-art selectors, and reduces end-to-end selection latency by 47.37-51.19\\%.}

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
long video understanding, frame selection

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rk4TOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes MEC (matryoshka evidence-to-content), a training-free long video key frame selection method which uses only one time selection process for different frame budgets, i.e number of frames 8/16/128/256, etc. The main motivation of the paper is budget-independent frame ranking: low-budget models can use query-evidence frames; for higher budgets, they can progressively select context and diversity frames.

Overall, in the paper, MEC has been evaluated on multiple benchmarks, i.e, Video-MME, Video-MME-v2, LongVideoBench, and MLVU. MEC achieves ~3.77% average improvement compared to uniform sampling and 47.37-51.19% lower selection latency.

Critical strengths

The proposed nested frame selection method is intuitive and solves the most critical problem in existing long-video frame selection methods: the need to rerun the model for different frame budgets. MEC run the selector only once and uses it for different frame budgets, motivated by MRL[1] training. The authors also provide a detailed analysis of temporal coverage and visual diversity, and they argue that temporal coverage matters more than any other component. Overall, the reported performance improvements, i.e 54.15% -> 62.45% over uniform sampling on LongVideoBench, prove the effectiveness of the paper.

[1] Aditya Kusupati et al. Matryoshka Representation Learning. URL: https://arxiv.org/abs/2205.13147

Critical weaknesses

Even though the nested ranking looks intuitive, it lacks overall algorithmic novelty. Most of the methods used are already well known, i.e MRL[1], temporal coverage, and evidence ranking. The paper only uses these and positions them in the paper.

Another important weakness is that the paper only performs benchmarks against uniform sampling, AKS and WFS-SB, but there are many other recent works for frame selection, i.e FOCUS[2], AKeyS[3], FrameThinker[3]. Without direct comparison with these methods, it would be difficult to assess whether MEC is SOTA or not at this stage,

[1] Aditya Kusupati et al. Matryoshka Representation Learning. URL: https://arxiv.org/abs/2205.13147

[2] Zirui Zhu et al. FOCUS: Efficient keyframe selection for long video understanding. In International Conference on Learning Representations, 2026. URL: https://arxiv.org/pdf/2510.27280

[3] Sunqi Fan et al. Agentic Keyframe Search for Video Question Answering. URL: https://arxiv.org/abs/2503.16032

[4] Zefeng He et al. FrameThinker: Learning to Think with Long Videos via Multi-Turn Frame Spotlighting URL: https://arxiv.org/abs/2509.24304

Questions for authors

Request the authors to provide a detailed assessment and comparison with FOCUS[1], AKeyS[2], FrameThinker[3] or any other recent relevant methods. I understand that all the methods may not use the same backbone, and reproducible code may not be available. Where possible, try to compare your model on the same backbone, i.e Qwen3.5-VL, with the same frame budget and report the performance in terms of accuracy as well as the end-to-end latency. This benchmark is very important to position your paper. if you can provide a detailed comparison report and your method performs well, I will be happy to raise my score.

[1] Zirui Zhu et al. FOCUS: Efficient keyframe selection for long video understanding. In International Conference on Learning Representations, 2026. URL: https://arxiv.org/pdf/2510.27280

[2] Sunqi Fan et al. Agentic Keyframe Search for Video Question Answering. URL: https://arxiv.org/abs/2503.16032

[3] Zefeng He et al. FrameThinker: Learning to Think with Long Videos via Multi-Turn Frame Spotlighting URL: https://arxiv.org/abs/2509.24304

6 comments

Thank you very much for taking the time to review our paper, for recognizing the practical value of MEC, and for your encouraging support in offering to raise your score. We try our best to address your questions as follows.

Q & W2. Comparisons with Recent Methods in Accuracy and Latency

Accuracy comparison under a unified protocol. Following your suggestion, we evaluated FOCUS (ICLR 2026), QCA (ECCV 2026), and AdaQ (2026) alongside AKS (CVPR 2025) and WFS-SB (CVPR 2026) under a strictly unified protocol. All methods use the exact same frozen Qwen3.5-9B answerer, evaluation samples, target frame budgets (K∈{8,32,128}K \in \{8, 32, 128\}), downstream preprocessing, prompts, and deterministic decoding across the full Video-MME test set (2,700 questions) and LongVideoBench validation set (1,337 questions).

Table A. Accuracy (%) across three frame budgets on Video-MME and LongVideoBench.

MethodVideo-MME (8 / 32 / 128)Avg. ↑\uparrowLongVideoBench (8 / 32 / 128)Avg. ↑\uparrow
Uniform58.96 / 66.15 / 72.4865.8654.15 / 58.86 / 65.0059.34
AKS [1]62.07 / 68.22 / 73.3367.8761.18 / 61.33 / 67.6163.37
WFS-SB [2]63.52 / 68.56 / 73.3768.4862.00 / 63.35 / 68.0664.47
FOCUS [3]62.96 / 67.15 / 70.1166.7461.26 / 61.71 / 67.3963.45
QCA [4]63.52 / 68.00 / 73.4168.3159.54 / 62.45 / 68.0663.35
AdaQ [5] †\dagger60.30 / 68.85 / 72.5267.2257.74 / 62.75 / 66.6462.38
MEC (Ours)63.85 / 69.11 / 73.7468.9062.45 / 63.58 / 68.3664.80

†\dagger For transparency, AdaQ uses its official sampling procedure adapted to fixed KK with a predefined seed. At K=128K=128, its candidate pool is smaller than KK for 33.22% of Video-MME and 27.00% of LongVideoBench questions.

MEC achieves the highest accuracy at every individual frame budget and the best three-budget average on both Video-MME (68.90%) and LongVideoBench (64.80%). Specifically, MEC improves average accuracy over FOCUS by +2.16 pp on Video-MME (reaching +3.63 pp at K=128K=128) and +1.35 pp on LongVideoBench, while outperforming QCA by +0.59 / +1.45 pp and AdaQ by +1.68 / +2.42 pp on Video-MME / LongVideoBench, respectively.

Selection efficiency and end-to-end latency. We also profiled cumulative wall-clock latency on an identical 18-video workload sampled from Video-MME (one question per video across all three budgets K∈{8,32,128}K \in \{8, 32, 128\}).

Table B. Cumulative multi-budget workload latency across 18 videos (seconds, lower is better).

MethodSelector Time (s) ↓\downarrowFull Workload Time (s) ↓\downarrow
FOCUS [3]201.71614.85
QCA [4]531.89966.71
AdaQ [5]363.52762.53
MEC (Ours)242.79675.80

Note: Selector Time measures the total wall-clock duration across all 18 videos for generating outputs across all three budgets, including initialization, preprocessing, feature extraction, scoring, selection, and local I/O. Full Workload Time additionally includes three separately initialized downstream QA inference processes.

MEC reduces selector latency by 54.35% vs. QCA and 33.21% vs. AdaQ, cutting full-workload time by 30.09% and 11.37%, respectively. While FOCUS is slightly faster in raw selection time (201.71 s vs. 242.79 s), MEC delivers substantially higher accuracy (+2.16 pp on Video-MME and +1.35 pp on LongVideoBench) with modest additional overhead. Crucially, MEC constructs a single budget-independent ranking whose prefixes directly serve all target budgets, whereas competing selectors—even when caching intermediate features—still require budget-dependent selection for each target KK.

Discussion of AKeyS and FrameThinker. We will include the comparisons above and also cite and discuss AKeyS [6] and FrameThinker [7] in the revised manuscript. Because AKeyS relies on caption-assisted agentic tree search and FrameThinker couples iterative multi-turn frame acquisition with an RL-trained policy, we distinguish them from standalone, single-pass visual selectors evaluated under a frozen answerer.

References

[1] Tang et al. Adaptive Keyframe Sampling for Long Video Understanding. CVPR 2025.

[2] Chen et al. Wavelet-based Frame Selection by Detecting Semantic Boundary for Long Video Understanding. CVPR 2026.

[3] Zhu et al. FOCUS: Efficient Keyframe Selection for Long Video Understanding. ICLR 2026.

[4] Peng et al. QCA: Query- and Content-Aware Keyframe Selection for Long Video Understanding. ECCV 2026.

[5] Zhang et al. Towards Fast and Effective Long Video Understanding of Multimodal Large Language Models via Adaptive Quasi-Gaussian Sampling. arXiv:2606.24187, 2026.

[6] Fan et al. Agentic Keyframe Search for Video Question Answering. arXiv:2503.16032, 2025.

[7] He et al. FrameThinker: Learning to Think with Long Videos via Multi-Turn Frame Spotlighting. ICLR 2026.

W1. Algorithmic Novelty of Matryoshka Keyframe Ranking

While Matryoshka Representation Learning (MRL) and individual selection cues (relevance, temporal coverage, diversity) are established building blocks, translating the nested-prefix principle from continuous representation learning to discrete, training-free subset selection introduces distinct structural challenges. Whereas MRL optimizes nested dimensions of a continuous vector during training, long-video frame selection operates at inference time over discrete observations whose utility is inherently set-dependent—a frame's marginal value depends on what is already included in the prefix. Moreover, a single shared ranking creates positional asymmetry across prefixes: early positions are exposed to all downstream budgets and must secure diagnostic query evidence, whereas later positions serve larger budgets by contributing complementary temporal context and visual diversity without displacing earlier selections.

To our knowledge, MEC is the first framework to formulate long-video keyframe selection as a Matryoshka ranking problem. Addressing the challenges above led to our core technical design: a set-aware, position-adaptive evidence-to-context greedy surrogate, supported by a reusable sparse video index and query-conditioned local zooming that avoid costly full-video dense scoring.

Reviewer_rk4TOpenReview ↗

Addressed some of my concerns - ablation on performance under the same frame budgets

Thanks to the authors for addressing my concerns in the rebuttal. Based on the accuracy comparison under the same frame budget and using the same selector, MEC demonstrates superior performance over the existing methods. I also appreciate the additional comparison with AKeyS and FrameThinker reported in the rebuttal.

My concern remains around the end-to-end latency. Compared to FOCUS, MEC improves avg accuracy by 2.16 pp on Video-MME and 1.35 pp on LongVideoBench; however, the improvements come at a cost of ~10% higher end-to-end latency and ~20% higher selector latency. I will request the author to provide the following additional ablations

  1. Please report the end-to-end comparison latency for each of the frame budgets, i.e 8/32/64/128 separately.
  2. If possible, compare MEC and FOCUS under the same end-to-end latency budget rather than only frame budgets
Reviewer_Y4wgOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes to formulate long-video frame selection as a Matryoshka ranking problem to avoid redundant computation and adaptively balance the key evidence and temporal coverage. The authors introduce a sophisticated Matryoshka Evidence-to-Context (MEC) framework to create the budge-independent frame selection sequence, allowing keyframe selection at any given budget once it is computed. Comprehensive evaluation is conducted on four long video understanding benchmarks with multiple LMMs. The paper also shows the ablation of each component and the inference-time speed up results compared to budget-conditioned methods.

Critical strengths
  1. The formulation of the problem is interesting and practical. Constructing a budget-independent priority sequence for each video enables the adaptive-budget inference without redundant computation. Still, it would be more intriguing if the paper further discuss the method to adaptively determine the budget for each video, under a total budget constraint over the dataset.
Critical weaknesses
  1. The method section is difficult to understand. The text is fragmented by many standalone subheadings, and there is not enough explanatory text to convey the the logical flow or the role each subsection plays within it. I suggest expanding the overview at the beginning of the section and each subsection that explains how these contents connect.
  2. The method is complicated and introduces a number of hyper-parameters: three for the Multi-Cue Evidence Scoring, and even more for the Greedy Matryoshka Ranking. Considered that the overall accuracy improvement compared to the baselines in table 1 is marginal, it is unconvincing that the proposed method can perform robustly without careful tuning of these hyper-parameters.
Questions for authors
  1. By looking at the scores computed when determining the prioity sequence, is it possible to adaptively determine the minimal sufficient keyframe set size for each video?
4 comments

Thank you very much for taking the time to review our paper and for your positive assessment of the practical value and efficiency of our Matryoshka ranking formulation. We try our best to address your questions as follows.

Q. Extending Priority Scores to Determine Minimal Sufficient Keyframe Sets

Score-only adaptive stopping setup. Thank you for raising this inspiring question. Because MEC constructs a query-conditioned priority sequence whose prefixes are strictly nested, the minimal sufficient frame budget can be determined dynamically at the video–query level, and early stopping can be executed on the fly without re-running selection. To explore this capability, we conducted a score-only adaptive stopping study using two signals derived directly from our selector: query-evidence-weighted residual visual coverage and the largest uncovered temporal gap. Combining both criteria, the stopping rule selects the shortest prefix from K∈{8,32,128}K \in \{8, 32, 128\} that satisfies the sufficiency thresholds without relying on downstream LMM answer confidence. We calibrated the thresholds on 540 Video-MME questions (180 videos), evaluated them on the remaining disjoint 720 videos (2,160 questions), and transferred the exact same thresholds zero-shot to LongVideoBench (1,337 questions).

Table A. Adaptive frame-budget exploration. Each entry reports Accuracy (%) / Average frames per question across K∈{8,32,128}K \in \{8, 32, 128\}.

StrategyVideo-MMELongVideoBench
Fixed K=8K=863.24 / 8.0062.45 / 8.00
Fixed K=32K=3269.07 / 32.0063.58 / 32.00
Fixed K=128K=12873.10 / 128.0068.36 / 128.00
GT Oracle: First Correct†79.17 / 42.2676.14 / 45.46
GT Oracle: Stable Correct†73.10 / 52.4068.36 / 59.34
Score-only Joint Stopping71.99 / 93.0266.79 / 91.74

† Note: Both retrospective ground-truth (GT) oracles operate over K∈{8,32,128}K \in \{8, 32, 128\} as upper bounds. First Correct selects the smallest budget yielding a correct answer, whereas Stable Correct selects the smallest budget at which the answer is correct and remains correct at all larger tested budgets (defaulting to K=128K=128 if none qualifies).

Key takeaways and open challenge. The retrospective oracles show substantial headroom for adaptive budgeting: on Video-MME, First-Correct reaches 79.17% accuracy with only 42.26 frames on average, and Stable-Correct matches full K=128K=128 accuracy using fewer than half the frames (52.40 on Video-MME; 59.34 on LongVideoBench). Our preliminary score-only rule reduces the average budget by ~27–28% relative to K=128K=128 (to 93.02 and 91.74 frames) while retaining most of the full-budget accuracy (within 1.11 pp on Video-MME and 1.57 pp zero-shot on LongVideoBench). This demonstrates that MEC provides a strong structural foundation for adaptive budget allocation, while also highlighting an open challenge: selector scores measure evidence relevance and spatio-temporal coverage, which only indirectly reflect whether the downstream LMM has sufficient information to reason and answer correctly.

W1. Improving Methodological Clarity in Section 3

Thank you for pointing out the fragmented subheadings and insufficient transitional text in Section 3. In the revised manuscript, we will merge the fragmented subheadings, expand the opening overview, and add clear transitions between subsections so that the three stages and their inputs/outputs read as a unified, coherent pipeline.

W2. Hyperparameter Robustness Across Perturbations

MEC uses a single frozen configuration across all four benchmarks, six frame budgets, and three downstream LMMs, without any dataset-, model-, or budget-specific tuning. For the Greedy Matryoshka Ranking schedule parameters (we+,we−,γ)(w_e^+, w_e^-, \gamma) in Eq. (10), varying the schedule shape and endpoints changes average accuracy by only 0.46 pp (Tables 2b and 6). To verify robustness across the remaining components, we conducted an expanded sensitivity study on Video-MME across K∈{8,32,128}K \in \{8, 32, 128\} around our frozen default setting (H00: evidence weights (λr,λΔ,λo)=(0.7,0.2,0.1)(\lambda_r, \lambda_\Delta, \lambda_o) = (0.7, 0.2, 0.1) in Eq. (6), diversity weight wd=0.2w_d = 0.2 in Eq. (11), and active-segment ratio η=0.25\eta = 0.25), evaluating both single-parameter and joint perturbations under the exact same protocol:

Table B. Hyperparameter sensitivity on Video-MME. Accuracy (%) at K∈{8,32,128}K \in \{8, 32, 128\} and difference in three-budget mean accuracy (ΔAvg.\Delta\text{Avg.}, pp) relative to the default setting.

IDParameter PerturbationK=8K=8K=32K=32K=128K=128Avg.ΔAvg.\Delta\text{Avg.} (pp)
H00Default: (λr,λΔ,λo)=(0.7,0.2,0.1), wd=0.2, η=0.25(\lambda_r,\lambda_\Delta,\lambda_o)=(0.7,0.2,0.1),\ w_d=0.2,\ \eta=0.2563.8569.1173.7468.90—
H01Evidence weights (0.6,0.3,0.1)(0.6, 0.3, 0.1)63.1169.4473.8168.79−0.11
H02Evidence weights (0.8,0.1,0.1)(0.8, 0.1, 0.1)63.8169.1573.7468.90+0.00
H03Evidence weights (0.65,0.2,0.15)(0.65, 0.2, 0.15)63.0769.1573.4168.54−0.36
H04Evidence weights (0.75,0.2,0.05)(0.75, 0.2, 0.05)63.3369.0473.9668.78−0.12
H05Diversity weight wd=0.1w_d = 0.163.5969.5274.0469.05+0.15
H06Diversity weight wd=0.3w_d = 0.363.3068.8573.5268.56−0.34
H07Joint A: (0.6,0.3,0.1), wd=0.3(0.6, 0.3, 0.1),\ w_d = 0.362.6369.5673.5668.58−0.32
H08Joint B: (0.75,0.2,0.05), wd=0.1(0.75, 0.2, 0.05),\ w_d = 0.163.7869.3773.0768.74−0.16
H09Active-segment ratio η=0.125\eta = 0.12563.4169.4474.2669.04+0.14
H10Active-segment ratio η=0.50\eta = 0.5063.4169.9373.9369.09+0.19

Across all tested single and joint perturbations, the three-budget mean accuracy fluctuates within a tight band of −0.36-0.36 to +0.19+0.19 pp relative to the default, and several alternative settings perform comparably or slightly better (e.g., H05, H09, H10). These results confirm that MEC operates within a broad, stable parameter region rather than relying on delicate hyperparameter tuning. We will include both the adaptive stopping and hyperparameter sensitivity analyses in the revised manuscript.

Reviewer_Y4wgOpenReview ↗

Thanks For the Response

I thank the authors for their response, especially their efforts to design a new experiment about the adaptive set size. The results, as suggested by the authors, despite having a large gap to the upper bound, seem promising and effectively exploit the advantages of the proposed approach. I encourage the authors to continue the exploration in this direction. Nevertheless, the hyper-parameter sensitivity experiment does not convince me about the robustness of the current method, and my concern regarding the complexity of the method remains. Also considered that the method section in the original submission required certain improvement in clarity, I therefore maintain my current score and encourage the authors to refine the paper and consider submitting it to a future venue.

Thank you for your follow-up and for acknowledging our adaptive-budget experiments. We understand your remaining concerns about the method's complexity and hyperparameter robustness.

Regarding robustness, our additional experiments vary the evidence weights, diversity weight, and segment activation ratio, both individually and jointly. Across ten perturbations, the three-budget mean accuracy changes by only −0.36 to +0.19 pp relative to the default (Table 14). While these experiments cover a local parameter range, we believe they provide evidence that MEC does not rely on finely tuned parameter values. We also use the same configuration across all benchmarks and downstream models.

We have further revised Section 3 to improve the flow of the method description and clarify the role of each component.

We sincerely appreciate your feedback and hope these revisions help address your concerns. Thank you again for your time!

Reviewer_B17aOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces Matryoshka Evidence-to-Context (MEC), a training-free frame-selection framework that constructs one reusable ranking for multiple frame budgets. Short prefixes emphasize query-conditioned evidence, while progressively longer prefixes add temporal coverage and visual diversity. MEC first builds a sparse video index containing appearance, visual-change, and observability information. It then performs sparse probing, segment activation, and local zooming to construct a candidate pool. Finally, a position-adaptive greedy objective balances evidence, temporal coverage, and diversity when producing the nested ranking. The method is evaluated on four long-video benchmarks, six frame budgets, and multiple downstream LMMs. MEC improves average accuracy over uniform sampling by 3.77 points and reports favorable accuracy–latency trade-offs relative to AKS and WFS-SB. Ablations examine candidate discovery, the ranking objective, fixed versus position-adaptive schedules, and shared versus budget-specific selection.

Critical strengths
  1. The paper addresses a practical deployment requirement that is often treated only indirectly: serving arbitrary budgets from one selection run. A nested ranking avoids independently rerunning the selector whenever the downstream budget changes and preserves early evidence as the budget grows. Evaluating six budgets across four benchmarks and several LMMs is well aligned with this motivation.

  2. MEC combines competitive accuracy with a substantially cheaper candidate-discovery and selection pipeline. The improvement over uniform sampling is consistent enough to be practically relevant, while the sparse index and local-zooming design avoid densely scoring every frame. The latency evaluation is reasonably conservative in that each budget independently reruns MEC selection rather than claiming additional savings from cross-budget reuse. The component ablations also demonstrate the importance of candidate discovery and temporal coverage.

Critical weaknesses
  1. The independent contribution of the proposed Matryoshka ranking mechanism appears relatively modest. Position-adaptive weighting improves over the fixed-weight variants by only approximately 0.40–0.95 points on average, and the shared M=256M=256 ranking improves over budget-specific M=KM=K selection by approximately 0.67 points on average. Larger degradations result from removing coverage or restricting the method to evidence alone. This suggests that much of the overall gain may come from candidate discovery and the general evidence–coverage–diversity design, rather than from the central position-adaptive ranking contribution. The current presentation does not sufficiently separate these sources of improvement.

  2. The comparative evidence is narrower than the broad state-of-the-art framing suggests, and several margins lack uncertainty estimates. The principal comparisons focus on Uniform, AKS, and WFS-SB, despite the paper discussing other recent strong selectors. MEC also does not outperform the strongest alternative in every dataset and budget. Since several conclusions rely on sub-point average differences, the absence of paired confidence intervals makes it difficult to determine which improvements are reliable.

Questions for authors
  1. What is the precise conceptual novelty of Matryoshka frame ranking beyond truncating a conventional priority ordering into nested prefixes? In particular, how does the formulation extend the nested-prefix principles in Matryoshka Representation Learning (Kusupati et al., 2022) and Matryoshka Multimodal Models (Cai et al., 2025), rather than mainly transferring that terminology to frame selection? Among AKS, Nar-KFC, BOLT, MDP3, AdaRD-Key, and WFS-SB, which methods cannot already be expressed as, or directly adapted to, a reusable ranking, and what structural property prevents this?

  2. Equation (3) defines an all-prefix oracle objective, whereas Equation (11) uses a hand-designed greedy surrogate with a scheduled transition from evidence to coverage. What formal or empirical connection justifies this surrogate as an approximation to Equation (3)? Why should monotonically shifting weight from evidence to coverage improve the aggregate utility across budgets, rather than merely encoding a useful heuristic prior? Are there query types or budget distributions for which a fixed-weight ranking would be more appropriate?

  3. Given that position-adaptive weighting improves over fixed-weight variants by only 0.40–0.95 points, and shared ranking improves over budget-specific selection by 0.67 points on average, what evidence establishes the proposed Matryoshka mechanism—rather than candidate discovery and the standard relevance/coverage/diversity terms—as the main source of improvement?

4 comments

Thank you very much for taking the time to review our paper and for recognizing our practical multi-budget motivation, conservative latency evaluation, and consistent gains over uniform sampling. We try our best to address your questions as follows.

Q1. Conceptual Novelty and Relationship to Existing Selectors

What is new compared to MRL and M³. We inherit rather than reinvent the nested-prefix principle of Matryoshka Representation Learning (MRL; Kusupati et al., 2022) and Matryoshka Multimodal Models (M³; Cai et al., 2025). While MRL trains continuous embedding prefixes across dimensions and M³ learns multi-granularity visual tokens, MEC instantiates this principle in a training-free manner on query-conditioned sequences of discrete video frames. Rather than truncating a static list sorted by independent relevance scores, MEC selects each frame based jointly on the already selected prefix set and the current rank position, concentrating diagnostic query evidence in short prefixes while progressively adding complementary temporal context at later ranks.

Adapting existing selectors to shared rankings. The structural distinction among existing selectors is whether selection depends on the target budget KK. AKS, MDP³, WFS-SB, and BOLT partition segments or allocate quotas using KK, so their native outputs across budgets are not nested. KFC and AdaRD-Key use set-aware greedy selection and are closer to shared rankings, though KFC’s budget-dependent processing and post-greedy refinement can replace earlier frames and AdaRD-Key’s VB-Scale adjusts its relevance–diversity trade-off with KK. Existing greedy methods can certainly be adapted to produce reusable rankings; the key distinction is whether a selector intentionally organizes progressive evidence expansion across prefixes within a single sequence. To verify this, we calibrated shared-prefix variants of KFC and AdaRD-Key (λ=0.30\lambda = 0.30) on 180 Video-MME videos, froze them, and evaluated on the remaining 720 disjoint videos (2,160 questions).

Table A. Disjoint Video-MME evaluation split: Accuracy (%) across three budgets.

Selection MethodK=8K=8K=32K=32K=128K=128Avg. ↑\uparrow
KFC, per-budget60.4664.1772.4165.68
KFC, shared prefix61.5766.6773.1967.15
AdaRD-Key, per-budget60.8367.9673.0667.28
AdaRD-Key, shared prefix (λ=0.30\lambda = 0.30)61.6267.4572.8267.30
MEC (Ours)63.2469.0773.1068.47

Both adapted variants achieve 100% strict nesting, and KFC-prefix improves over per-budget KFC by +1.47 pp, confirming that reusable rankings are not exclusive to MEC. On the disjoint split, MEC further outperforms the calibrated KFC-prefix and AdaRD-prefix baselines by +1.32 pp and +1.17 pp on average.

Q2. Connection Between All-Prefix Objective and Position-Scheduled Surrogate

Connection between Eq. (3) and the scheduled surrogate. Equation (3) formulates the ideal multi-budget optimization target: maximizing expected downstream QA utility across all prefix budgets simultaneously. Because directly querying the downstream LMM at every candidate step is computationally prohibitive, Eqs. (10)–(11) serve as a tractable greedy surrogate using evidence, coverage, and diversity, rather than a formal theoretical approximation bound. This surrogate reflects the shifting marginal utility of localized evidence versus broader temporal context as the prefix grows: early ranks must first secure high-relevance evidence to answer the query, whereas once primary evidence is present, expanding temporal coverage captures complementary events that redundant high-relevance frames cannot provide. We tested this directly via a counterfactual experiment on Video-MME. Holding the initial prefix SkS_k, query, candidate pool, and LMM fixed, we appended 8 frames using a fixed Evidence-heavy policy, a fixed Coverage-heavy policy, and MEC, measuring the marginal accuracy change (ΔAcc.\Delta\text{Acc.}, pp):

Table B. Counterfactual marginal accuracy gains (ΔAcc.\Delta\text{Acc.}, pp) under fixed prefixes.

Prefix + 8 FramesEvidence-heavyCoverage-heavyMEC
Early: 8→168 \to 16+6.52+4.44+6.59
Middle: 96→10496 \to 104+1.11+0.67+1.26
Late: 224→232224 \to 232+0.33+0.44+0.78

When fixed weights are preferable. Table B shows that adding high-evidence frames helps more at early ranks, while the relative value of coverage rises at later ranks; MEC tracks the stronger strategy across stages via a lightweight linear schedule. That said, fixed or budget-specific weights can be preferable for strictly localized needle-in-a-haystack queries, global multi-event queries requiring immediate coverage, or deployments fixed to a single budget KK.

Q3 & W1. Performance Attribution of Matryoshka Ranking

Position-adaptive scheduling is not the main source of raw accuracy gains at an isolated budget. Relevance, coverage, and diversity are established principles shared by most keyframe selectors, and our multi-cue candidate discovery together with the joint objective drives the primary gain over Uniform. Rather than claiming large extra single-budget gains from the schedule alone, our core contribution is organizing the selected frames into a single, strictly nested representation that can be reused across budgets without replacing earlier frames. This allows MEC to match state-of-the-art per-budget selectors while substantially reducing latency across multi-budget workloads.

W2. Expanded Strong Baselines and Statistical Uncertainty

Expanded strong baselines. Beyond Uniform, AKS, and WFS-SB, we evaluated FOCUS, QCA, and AdaQ on full Video-MME and LongVideoBench across 8, 32, and 128 frames under the exact same downstream LMM (Qwen3.5-9B) and evaluation protocol.

Table C. Accuracy (%) across three frame budgets on Video-MME and LongVideoBench.

MethodVideo-MME (8 / 32 / 128)Avg. ↑\uparrowLongVideoBench (8 / 32 / 128)Avg. ↑\uparrow
Uniform58.96 / 66.15 / 72.4865.8654.15 / 58.86 / 65.0059.34
AKS [1]62.07 / 68.22 / 73.3367.8761.18 / 61.33 / 67.6163.37
WFS-SB [2]63.52 / 68.56 / 73.3768.4862.00 / 63.35 / 68.0664.47
FOCUS [3]62.96 / 67.15 / 70.1166.7461.26 / 61.71 / 67.3963.45
QCA [4]63.52 / 68.00 / 73.4168.3159.54 / 62.45 / 68.0663.35
AdaQ [5] †\dagger60.30 / 68.85 / 72.5267.2257.74 / 62.75 / 66.6462.38
MEC (Ours)63.85 / 69.11 / 73.7468.9062.45 / 63.58 / 68.3664.80

†\dagger AdaQ uses its official sampling procedure adapted to fixed KK; at K=128K=128, its candidate pool is smaller than KK for 33.22% of Video-MME and 27.00% of LongVideoBench questions.

Statistical uncertainty and claim boundaries. To assess statistical reliability where margins are small, we also computed paired, video-clustered 95% confidence intervals across all six budgets.

Table D. Six-budget mean accuracy differences (pp) and paired video-clustered 95% CIs.

BenchmarkMEC −- Uniform95% CIMEC −- WFS-SB95% CI
Video-MME+2.71[+1.95, +3.50]+0.49[−0.18, +1.14]
Video-MME-v2 (micro acc.)+2.24[+1.70, +2.84]−0.05[−0.67, +0.56]
LongVideoBench+4.66[+3.80, +5.53]−0.10[−0.71, +0.55]
MLVU (macro score)+5.48[+4.44, +6.53]+0.03[−1.01, +1.03]
Four-Benchmark Macro Avg.+3.77[+3.08, +4.49]+0.09[−0.30, +0.51]

Tables C and D confirm that MEC achieves the highest mean accuracy among all tested baselines, delivers statistically significant gains over Uniform, and reaches statistical parity with the strongest per-budget selector (WFS-SB), while uniquely providing strict cross-budget prefix reuse and lower latency. We will include these baseline comparisons, confidence intervals, and clarified discussions in the revised manuscript.

References

[1] Tang et al. Adaptive Keyframe Sampling for Long Video Understanding. CVPR 2025.

[2] Chen et al. Wavelet-based Frame Selection by Detecting Semantic Boundary for Long Video Understanding. CVPR 2026.

[3] Zhu et al. FOCUS: Efficient Keyframe Selection for Long Video Understanding. ICLR 2026.

[4] Peng et al. QCA: Query- and Content-Aware Keyframe Selection for Long Video Understanding. ECCV 2026.

[5] Zhang et al. Towards Fast and Effective Long Video Understanding of Multimodal Large Language Models via Adaptive Quasi-Gaussian Sampling. arXiv:2606.24187, 2026.

AuthorsOpenReview ↗

Follow-up on Our Response and Revised Manuscript

Dear Reviewer,

Thank you again for your detailed review and constructive suggestions. We have incorporated the additional experiments into our revised manuscript, including shared-prefix comparisons, fixed-prefix counterfactual analyses, and paired confidence intervals (Tables 10–12). We have also clarified the motivation and limitations of our greedy surrogate in Section 3.

As the discussion period draws to a close, we would be grateful if you could take another look at our responses and let us know whether any major concerns remain. We would be happy to provide further clarification.

Thank you for your time and consideration!

AuthorsOpenReview ↗

Thank You for Your Review

Dear Reviewer,

As the discussion period approaches its end, we would greatly appreciate any further feedback, particularly if any of your main concerns remain unresolved.

We would be happy to address any remaining questions or provide further clarification.

Thank you again for your time and consideration!

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response

Dear Reviewers and Area Chair,

Thank you for your careful reviews and constructive feedback. We have conducted additional experiments and prepared a revised manuscript, with changes highlighted in blue. The main updates are summarized below:

  • Method clarification (B17a, Y4wg, rk4T). We revised Section 3 to improve the explanation of our three-stage framework, clarify the connection between the all-prefix objective and the greedy surrogate, and better distinguish the contributions of candidate discovery and position-adaptive ranking.
  • Additional comparisons (B17a, rk4T). We added FOCUS, QCA, and AdaQ under a unified evaluation protocol, along with shared-prefix variants of KFC and AdaRD-Key.
  • Further analyses (B17a, Y4wg). We included fixed-prefix counterfactual experiments, paired confidence intervals, hyperparameter sensitivity tests, and an exploratory study on adaptive frame budgets.
  • Latency evaluation (rk4T). Following the reviewer's suggestions, we measured per-budget end-to-end latency and compared MEC with FOCUS under approximately matched latency budgets, explicitly discussing the accuracy–latency trade-offs.

We hope these additions and revisions help address your concerns and make our contributions clearer. We sincerely appreciate your time and welcome any further feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.