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

Frame selection is crucial for applying Large Multimodal Models (LMMs) to long videos due to severe frame redundancy and limited context windows, and this work introduces Matryoshka Evidence-to-Context (MEC) Frame Selection, a training-free framework that constructs a single priority sequence capable of serving multiple frame budgets. This method addresses the challenge of optimizing an isolated frame subset for each budget by formulating long-video frame selection as a Matryoshka ranking problem, where small prefixes concentrate query-conditioned evidence, while progressively larger prefixes preserve this evidence and add broader temporal context, allowing a single ranking to be truncated to any target budget without rerunning the selector.

The Matryoshka Ranking Problem

The core idea is to construct a single priority sequence whose small prefixes concentrate query-conditioned evidence, while progressively larger prefixes preserve this evidence and add broader temporal context. This contrasts with existing methods that optimize an isolated frame subset for each predefined budget, which may lead to previously selected evidence being replaced when the budget changes. The objective is defined as:

R⋆ ∈ arg max R∈ΠM ∑ K∈B πK QK(R:K; V, q)

where the utility function rewards concentrated query-conditioned evidence for tight budgets and progressively rewards complementary temporal and visual context as the prefix grows.

Reusable Sparse Video Index

To efficiently construct this ranking without substantial overhead, MEC first builds a reusable sparse video index. This index is independent of the query and caches low-resolution appearance encodings, local visual change estimates, and observability priors. The construction involves:

1. Duration-Adaptive Sparse Probing to create temporally ordered segments.

2. Low-Resolution Appearance Encoding using L2-Norm on resized grayscale frames to reduce storage and computation overhead.

3. Local Visual-Change Estimation by comparing adjacent probes on the sparse grid to highlight visually distinctive moments, defined as ∆n = (1/2 max m∈AdjP (n) fn − fm squared.

Query-Conditioned Evidence Discovery

Once the index is built, MEC discovers query-conditioned evidence through a multi-cue scoring mechanism. The evidence score for a frame is defined as:

En(q) = λrρn(q) + λ∆∆n + λoOn

where Relevance (λr=0.7), Visual Change (λ∆=0.2), and Observability (λo=0.1) are weighted cues. Following this scoring, the framework refines promising regions using:

1. Evidence-Guided Segment Activation, which retains segments with the largest mean evidence scores based on an activation ratio η=0.25 to form the active set A(q).

2. Anchor-Centered Local Zooming, where the highest-evidence probe serves as an anchor, and Uni(a−j, aj, Lz) samples distinct interior frames around this anchor to form a compact candidate pool C(q).

Position-Adaptive Matryoshka Ranking

The final stage involves greedily constructing the ranking using a position-dependent surrogate score:

uk(n) = we(k)En(q) + wc(k)Hn(k) + wdDn(k)

This score balances query-conditioned evidence (we), temporal coverage (wc, where wc = 1 - we - wd), and visual diversity (wd). The ranking is constructed by appending the candidate with the highest surrogate utility at each rank k, ensuring that every shorter ranking is an exact prefix of every longer one.

Experimental Validation and Efficiency

Extensive experiments across four long-video benchmarks (Video-MME, LongVideoBench, MLVU) and six frame budgets demonstrate MEC's effectiveness. MEC improves average accuracy over uniform sampling by 3.77 percentage points across the benchmarks. Furthermore, it significantly reduces end-to-end selection latency by 47.37–51.19% compared to state-of-the-art selectors like AKS and WFS-SB, while remaining competitive with a favorable accuracy–latency trade-off across all tested downstream LMMs (Qwen3.5, LLaVA, InternVL). The framework is training-free and uses a shared configuration across all experiments.

Limitations

The paper notes limitations in sparse discovery (sparse-discovery blind spots), where the grid may miss brief, visually isolated events that fall between probes. Additionally, reliance on lightweight proxies like BLIP-2 ITM scores and fixed evidence mixtures means the system may fail to capture evidence emerging from ordered pairs or long temporal dependencies. Finally, the greedy construction is a surrogate for global optimization; it does not guarantee global optimality for any individual budget or weighted aggregate of utilities.

Here are the specific improvements to AI systems based on the Matryoshka Evidence-to-Context (MEC) Frame Selection framework, and what these improved systems can achieve:

---

1. 】Multi-Budget Adaptability for Constrained Context Windows

The MEC framework allows a single, reusable frame selection sequence to be truncated into any target budget (K) without rerunning the entire complex selector.

2. 】Specific Improvement:

Improve Long-Video Understanding Models (LMMs) by enabling them to operate efficiently under varying input constraints (e.g., different context window sizes or processing budgets).

3. 】Improved AI System Capability:

• Reduce end-to-end selection latency by up to 51% compared to fixed budget optimizers, allowing real-time processing of long videos with limited computational resources.

4. 】Generalization Across Downstream Architectures and Models

The MEC selector is training-free and architecture/model agnostic, relying on a reusable sparse index and query-conditioned scoring (BLIP-2 ITM).

5. 】Specific Improvement:

Decouple the frame selection mechanism from the specific Large Multimodal Model (LMM) architecture or internal tokenization strategy.

6. 】Improved AI System Capability:

• Transfer a single, robust frame selection configuration across different LMMs (e.g., Qwen3.5-9B, LLaVA-OneVision-2), ensuring consistent performance regardless of the downstream model's specific input representation or compression method.

7. 】Position-Adaptive Evidence Prioritization

The system constructs a Matryoshka ranking where early ranks emphasize query-conditioned evidence, and later ranks progressively favor temporal coverage and visual diversity.

8. 】Specific Improvement:

Implement a dynamic, position-dependent weighting scheme that shifts the optimization focus from purely relevance (early) to context expansion (later) based on the required budget K.

9. 】Improved AI System Capability:

• Achieve superior reasoning for complex queries by ensuring that critical, fleeting evidence is concentrated in the initial frames while maintaining a broad temporal understanding of the video's narrative structure in subsequent frames.

10.】Efficient Candidate Pool Construction via Sparse Probing and Local Zooming

The framework builds a reusable sparse index (caching low-resolution appearance, local visual change, and observability) and uses query-conditioned discovery through multi-cue scoring, segment activation, and anchor-centered zooming to form a compact candidate pool.

11.】Specific Improvement:

Develop an efficient pre-processing pipeline that generates a query-independent visual scaffold (sparse index) independent of the specific question asked. The system then refines the search space by focusing only on temporally relevant and visually distinctive regions around discovered anchors.

12.】Improved AI System Capability:

• Significantly reduce the computational overhead associated with exhaustively sampling long videos, enabling faster query processing while maintaining high fidelity for key evidence discovery.

13.】Robustness Against Sparse Discovery Blind Spots (Mitigation via Contextual Refinement)

The framework explicitly identifies limitations related to sparse probing missing critical, temporally isolated events (e.g., the final state). The greedy ranking mechanism is designed to leverage temporal coverage and diversity terms to mitigate these omissions where possible.

14.】Specific Improvement:

Inference time, if necessary, can be extended by utilizing the structure of the Matryoshka ranking (where prefixes are exact subsets) to ensure that even if a specific frame is missed in an initial sparse probe, it can be recovered by subsequent ranks that prioritize temporal or diversity coverage.

15.】Component Ablation and Hyperparameter Optimization

The MEC framework allows for detailed ablation studies on its core components: evidence scoring mixture, position-adaptive schedules (evidence/coverage/diversity weights), and ranking horizon (M).

16.】Specific Improvement:

System designers can precisely tune the trade-off between evidence concentration and temporal context expansion by adjusting the rank weight schedule.

17.】Improved AI System Capability:

• Tailor the frame selection strategy dynamically based on whether the task requires immediate, precise evidence (low budget) or broader narrative understanding (high budget), leading to optimal accuracy for any deployment scenario.

18.】Enhanced Visual Quality Priors (Observability Scoring)

The system incorporates a query-independent observability prior that combines frame sharpness and well-exposedness, suppressing severely degraded frames without relying on semantic content scores.

19.】Specific Improvement:

Integrate a dual-metric visual quality assessment into the evidence scoring process to filter out noise (e.g., blurry or poorly exposed frames) before they even enter the query relevance calculation, ensuring the model focuses its attention on visually viable data points.