acceptodds
Under review as a conference paper at ICLR 2027

FoveaTree: Information-Density Trees for Query-Guided Visual Token Pruning in Video Large Language Models

Abstract

Video large language models (Video LLMs) have demonstrated strong multimodal understanding across a range of tasks, including visual question answering and video captioning. Yet, encoding each frame into hundreds of visual tokens makes inference over temporal visual content expensive. Existing methods reduce this cost by merging similar tokens or using text-to-vision attention to select task-relevant tokens. Nevertheless, these methods still face two main challenges: (1) Hierarchy-blind Pruning: many similarity-based methods rely on pairwise similarity or training a lightweight neural network to predict importance scores without explicitly considering the regional compressibility of a frame, which can misguide the merging or removal of critical evidence. (2) Attention Drift: position-dependent effects from Rotary Position Embedding (RoPE), which encodes token positions in the decoder, together with preferences for nearby or recent tokens and attention sinks can shift query-to-vision attention away from task relevance, causing attention-based pruning to underweight and discard task-relevant visual tokens. Motivated by these observations, we propose FoveaTree, a two-stage, training-free visual-token pruning framework for efficient video inference. The first stage estimates regional compressibility from the feature distortion incurred when merging a region to construct a quadtree-derived density map, which guides the dropping, merging, and retention of visual regions. Based on the surviving units and inherited tree topology, the second stage introduces an efficient tree-structured pruning mechanism in the middle layers of the LLM to mitigate Attention Drift and further reduce low-relevance visual content using text-to-vision attention. We validate FoveaTree under different Video LLM architectures, i.e., InternVL3.5-8B and Qwen3-VL-8B, on five video question-answering benchmarks and one captioning benchmark with token budgets of 50%, 30%, and 10%; our method consistently achieves overall state-of-the-art performance across all evaluated settings, demonstrating a superior accuracy-efficiency trade-off.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Video large language models, visual-token pruning, regional compressibility, tree-structured pruning, text-to-vision attention

Reviews

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

The paper proposes a training-free visual token pruning framework designed to accelerate VLM during inference without degrading performance. It addresses two major limitations of existing compression methods: hierarchy-blind pruning and attention drift. The reported experiment results achieves state-of-the-art accuracy-efficiency trade-offs across multiple video understanding and captioning benchmarks.

Critical strengths
  1. The paper reported strong performance results compared to existing training-free pruning methods across multiple backbones and retention ratios (Sec 3.2)
  2. It also reported noticeable speedups with minimal peak memory overhead compared to baselines (Sec 3.3)
  3. The proposed scheme is training free, easily adaptable to diverse VLM architectures.
Critical weaknesses
  1. The paper did not seem to have established a general optimal guarantee, but relies on heuristic design choices.
  2. Does the same hyperparameters work across different video resolution, length, etc?
  3. How does the performance change on rare events and unusual scenes?
  4. MGDE builds a quadtree on a per-frame base (Sec 2.2.) Temporal structure is not explicitly modeled. Does this spatial only hierarchy affect performance and would a spatiotemporal hierarchy improve the capability?
Questions for authors

Please see last section.

6 comments
AuthorsOpenReview ↗

Response to Weakness 1: Optimality Guarantees and Design Choices

Reviewer concern: The paper did not seem to have established a general optimal guarantee, but relies on heuristic design choices.

Thank you for raising this question. For visual-token pruning, the optimal selection depends on the video, the question, and the model's subsequent reasoning. Pruning decisions based on feature or attention scores therefore cannot guarantee globally optimal task performance across all inputs and tasks. FoveaTree is a training-free compression algorithm for practical video understanding, designed to achieve a favorable accuracy–efficiency trade-off under a given token budget; we do not claim a general guarantee of global optimality. We evaluate this objective through task performance and computational cost across models and tasks, which form the main evidence for our contribution.

AuthorsOpenReview ↗

Response to Weakness 2: Hyperparameter Robustness Across Video Resolutions and Durations

Reviewer concern: Does the same hyperparameters work across different video resolution, length, etc?

Thank you for raising this question. Yes, the same pruning hyperparameters apply across the video resolutions, durations, and datasets evaluated in this paper, without retuning for individual inputs. Our main experiments already cover these variations, as summarized below.

DatasetDurationSource resolution / format
Video-MMEShort: ~0–2 min; medium: 4–15 min; long: 30–60 minMainly 1280×720 / 640×360; 16:9
VDCTypically tens of seconds; local range: ~8–163 s1080p / 720p / 4K; also 4:3 and portrait
MVBenchMostly seconds to tens of seconds; some clips last minutes480×320 / 480×270 / 720p / 1080p / 224×224; varied formats
VNBenchLong-video retrieval; sample-dependentSource-dependent
NExT-QATypically tens of secondsVarious resolutions; mainly landscape
VALOR32K-AVQA Visual~10 sVarious resolutions; mainly landscape

These datasets span short clips and long videos, diverse resolutions, and landscape, portrait, and square formats. We use the same MGDE and ATP hyperparameters under each benchmark's established sampling and preprocessing protocol. The cross-dataset results in the main tables and appendix support the applicability of this configuration across these input conditions.

AuthorsOpenReview ↗

Response to Weakness 3: Rare Events and Unusual Scenes

Reviewer concern: How does the performance change on rare events and unusual scenes?

Thank you for raising this question. MVBench, included in our main experiments, contains the official Unexpected Action task, whose videos come from FunQA and evaluate the understanding of unexpected or unusual actions. Our evaluation therefore already includes samples relevant to unusual scenes and events. The 3,800 MVBench samples we evaluate exclude only the missing Fine-grained Pose task and include Unexpected Action.

We further summarize accuracy on Unexpected Action, comparing the full model with FoveaTree at different visual-token retention ratios:

ModelFull50% retention30% retention10% retention
InternVL3.5-8B87.0%87.0%86.5%85.0%
Qwen3-VL-8B81.0%81.0%82.0%81.0%
Qwen2.5-VL-7B83.5%82.5%83.0%83.0%
LLaVA-OneVision-7B83.0%84.0%83.5%84.0%

FoveaTree maintains accuracy close to the full model across all four backbones, with improvements in some settings. Even at 10% visual-token retention, it preserves strong understanding of unexpected and unusual actions.

Reviewer_etM8OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes FoveaTree, a two-stage training-free visual token pruning framework for efficient VideoLLM inference. To address hierarchy-blind pruning and attention drift, FoveaTree first constructs a quadtree-based density map to guide token dropping, merging, and retention based on regional compressibility. It then introduces tree-structured pruning within the LLM to mitigate attention drift and further remove irrelevant tokens. Extensive experiments across several VideoLLM backbones and six benchmarks demonstrate competitive performance under different token budgets, achieving a strong accuracy-efficiency trade-off.

Critical strengths

The paper is well constructed and easy to follow.
The method is well motivated by the strong analysis on the insight “Hierarchy-blind Pruning” and “Attention Drift“
The paper provides detailed experimental results, including commonly used benchmarks on video QA & caption across several popular VideoLLMs.

Critical weaknesses
  1. Further analysis of MGDE and ATP. The component ablation study reveals an interesting finding: while MGDE and ATP individually lead to slight performance drops on VideoMME, their combination outperforms the original InternVL3.5-8B. Further analysis of this complementary effect would provide valuable insights into the effectiveness of the proposed framework.
  2. Detailed latency breakdown. Tables 3 and 4 demonstrate the overall efficiency of FoveaTree. Providing a breakdown of the computational overhead of MGDE and ATP would further clarify their individual contributions to the overall latency.
  3. Insights into ATP layer selection. The results show that ATP performs best when applied at layer 18. It would be interesting to further investigate why this layer is particularly effective and whether attention drift continues to evolve during MLLM forward propagation after token merging or pruning.
  4. Evaluation of temporal and spatial understanding. Given the promising results of FoveaTree, additional evaluations on fine-grained temporal understanding (e.g., event duration estimation and timestamp localization) and spatial localization would help demonstrate how well the method preserves detailed visual information under aggressive token compression.
Questions for authors

Please see Weaknesses

5 comments
AuthorsOpenReview ↗

Response to Weakness 1: Complementary Effects of MGDE and ATP

Reviewer concern: Further analysis of MGDE and ATP. The component ablation study reveals an interesting finding: while MGDE and ATP individually lead to slight performance drops on VideoMME, their combination outperforms the original InternVL3.5-8B. Further analysis of this complementary effect would provide valuable insights into the effectiveness of the proposed framework.

Thank you for raising this question. MGDE and ATP are complementary and are most effective when combined. MGDE uses feature distortion to identify regions with high information density and derive a spatial hierarchy. It preserves the main content with rich details and distinctive features while removing some visual redundancy. ATP uses the question to focus selection on relevant regions and reduce interference from unrelated content.

When used alone, MGDE preserves the main visual content, but its query-independent nature also retains other regions with distinctive features, providing limited guidance for question-specific understanding. When used alone, ATP lacks density-based guidance and is affected by Attention Drift, which limits its ability to retain question-relevant regions and can also cause irrelevant regions to be retained. These factors affect task performance.

In combination, MGDE first removes redundancy in low-information-density regions and provides density information and a spatial hierarchy. ATP then uses this information to retain question-relevant regions more completely and accurately, mitigate the effects of Attention Drift, and reduce redundancy in irrelevant regions. The two modules thus complement each other to preserve, and sometimes improve, the model's capabilities. To illustrate this process, we added a visualization in Appendix E.5 comparing their joint effect. The complete FoveaTree method shows the best visual retention among these configurations.

AuthorsOpenReview ↗

Response to Weakness 2: Detailed Latency Breakdown

Reviewer concern: Detailed latency breakdown. Tables 3 and 4 demonstrate the overall efficiency of FoveaTree. Providing a breakdown of the computational overhead of MGDE and ATP would further clarify their individual contributions to the overall latency.

Thank you for raising this question. To clarify the individual computational costs of MGDE and ATP, we randomly select 10 Video-MME videos and measure FoveaTree's latency by stage on Qwen3-VL-8B using the same configuration as the main experiments. Times below are in milliseconds. Visual-side compression and input assembly are included in the total latency, while the vision encoder's forward pass is excluded from this measurement. Each stage and the total latency are timed independently. The MGDE stage includes visual-side compression and input assembly before the LLM, while the ATP stage includes attention extraction, tree pruning, token merging, and sequence reorganization within the LLM.

Stage / metricFoveaTree 30%FoveaTree 10%
Original visual tokens4,6084,608
Visual tokens entering the LLM2,490.82,490.8
Visual tokens after ATP1,358.6477.4
MGDE + input assembly32.031.6
Prefill, layers 1–18127.0126.8
ATP24.825.1
Later prefill + decode376.1333.1
Independently measured total latency546.2507.8

LLM computation accounts for most of the latency. MGDE and input assembly take approximately 32 ms, and ATP takes approximately 25 ms. Because MGDE is independent of the final token budget, the LLM-entry visual-token count is identical at both retention ratios, and prefill latency for the first 18 layers remains nearly unchanged. ATP at layer 18 reduces the visual-token count to averages of 1,358.6 and 477.4, respectively, reducing subsequent prefill and decoding latency from 376.1 ms to 333.1 ms.

AuthorsOpenReview ↗

Response to Weakness 3: ATP Layer Selection

Reviewer concern: Insights into ATP layer selection. The results show that ATP performs best when applied at layer 18. It would be interesting to further investigate why this layer is particularly effective and whether attention drift continues to evolve during MLLM forward propagation after token merging or pruning.

Thank you for raising this question. Our choice of ATP placement draws on prior studies of how text–vision interactions evolve across LLM layers, together with our layer-position ablation and attention statistics. PyramidDrop finds that attention is more dispersed in shallow layers and becomes more concentrated on question-relevant image regions in intermediate layers. FastV also shows that attention allocation to visual tokens changes substantially across layers, making pruning position relevant to both information retention and computational efficiency. These findings motivate pruning at an intermediate layer, where question-related visual cues have developed and sufficient subsequent computation remains to benefit from compression.

To further explain this choice, we measure the visual-attention share at each layer of Qwen3-VL on 10 Video-MME videos: for each question token, we sum its attention weights over all visual tokens, then average over question tokens, attention heads, and videos. The table shows six representative layers. Layer numbers are one-based; the ATP layer setting used in our paper is code index 18, whose attention-scoring position corresponds to layer 19 in the table.

Attention layer (one-based)Visual-attention share
111.87%
128.22%
1820.17%
19 (code index 18; ATP scoring)27.37%
2521.53%
367.37%

Across the complete 36-layer profile, the visual-attention share reaches its maximum of 27.37% at ATP's scoring position, indicating strong attention from question tokens to visual content at this position. Together with the task-performance ablation over pruning positions in the main paper, this supports our choice of layer setting 18. We observe a similar pattern of stronger visual attention in intermediate layers across all models evaluated in our experiments. This share measures how much attention the question text assigns to visual content; the pruning position is selected jointly from these statistics and the task-performance ablation.

Regarding attention evolution after pruning, our focus is the effect of Attention Drift on token selection at the pruning stage. ATP uses spatial hierarchy and question relevance to preserve important visual information and provide a compressed visual representation for subsequent reasoning. Its effectiveness is evaluated through final task performance. Attention evolution in later layers concerns the model's internal forward computation and constitutes a separate mechanism-analysis question beyond the scope of this work.

PyramidDrop: https://arxiv.org/abs/2410.17247

FastV: https://arxiv.org/abs/2403.06764

Reviewer_S8ihOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes FoveaTree, a training-free, two-stage visual token pruning framework for Video LLMs. MGDE constructs a quadtree based on regional feature distortion to guide token dropping, merging, and retention, while ATP uses query-conditioned attention and hidden-state heterogeneity to perform hierarchical pruning within the LLM. Experiments on six benchmarks and four Video LLM backbones show strong performance retention at 10%–50% visual token budgets. On InternVL3.5-8B, the method retains 100.62% of full-model performance at a nominal 30% token budget, with a 1.24× inference speedup.

Critical strengths
  1. The combination of regional compressibility and query-guided hierarchical pruning is well motivated. The two-stage design provides a practical way to preserve spatially coherent visual evidence without additional training. 2、The evaluation is comprehensive, covering six benchmarks, four model backbones, and three token budgets. The results demonstrate strong accuracy retention, particularly under aggressive compression. 3、The paper includes component ablations, efficiency measurements, and token-budget audits, providing useful evidence for the method's effectiveness across different settings.
Critical weaknesses

1.The explanation of Attention Drift is not fully established. The visualizations show different token-selection patterns, but do not isolate whether the improvements come from mitigating positional attention bias or simply enforcing spatial coherence through the tree structure. 2.MGDE performs query-independent token dropping before ATP, making discarded evidence unrecoverable. Since feature distortion does not necessarily reflect task relevance, the robustness of this early pruning stage for small or low-texture but important objects remains unclear. 3.The accuracy-efficiency trade-off and token-budget accounting need clarification. At 30% retention on InternVL3.5, TFLOPs decrease by 53.2%, but end-to-end latency improves by only 1.24×. Additionally, Table 2 lists 1,725 retained tokens for Qwen3-VL at 30%, whereas Appendix Table 14 reports approximately 1,393 actual tokens and a maximum of 1,440, making the reported budget definitions difficult to reconcile.

Questions for authors
  1. Can the authors provide controlled experiments distinguishing the effect of hierarchical spatial aggregation from actual mitigation of Attention Drift, particularly for objects located near image boundaries?
  2. How robust is MGDE's query-independent dropping to low-texture or small task-relevant objects? Please report evidence-retention statistics or targeted failure cases. 3.Could the authors reconcile the Qwen3-VL token counts in Table 2 and Appendix Table 14, and provide an efficiency breakdown separating MGDE, ATP, and LLM computation? An additional comparison at matched actual token counts would help establish fairness.
3 comments
AuthorsOpenReview ↗

Response to Weakness 3 and Question 3

Reviewer concern (Weakness 3): The accuracy-efficiency trade-off and token-budget accounting need clarification. At 30% retention on InternVL3.5, TFLOPs decrease by 53.2%, but end-to-end latency improves by only 1.24×. Additionally, Table 2 lists 1,725 retained tokens for Qwen3-VL at 30%, whereas Appendix Table 14 reports approximately 1,393 actual tokens and a maximum of 1,440, making the reported budget definitions difficult to reconcile.

Reviewer question (Question 3): Could the authors reconcile the Qwen3-VL token counts in Table 2 and Appendix Table 14, and provide an efficiency breakdown separating MGDE, ATP, and LLM computation? An additional comparison at matched actual token counts would help establish fairness.

Thank you for raising this question. Below, we explain the computational overhead of each stage and clarify the token-budget accounting. FoveaTree applies ATP at layer 18, so the reduction to the final token count primarily benefits subsequent LLM computation. MGDE, prefill through the first 18 layers, and attention extraction and sequence reorganization in ATP still incur overhead. Consequently, the reduction in TFLOPs does not translate proportionally into end-to-end speedup. We conducted additional measurements of FoveaTree with InternVL3.5-8B on 10 videos from VideoMME. At both the 30% and 10% budgets, an average of 11,709.8 visual tokens enter the LLM; ATP reduces this number to 4,810.2 and 1,632.8, respectively. The independently measured total latencies are 1,966.8 ms and 1,415.3 ms, respectively.

Stage / MetricFoveaTree 30%FoveaTree 10%
Original visual tokens16,38416,384
Visual tokens entering the LLM11,709.811,709.8
Visual tokens after second-stage pruning4,810.21,632.8
MGDE311.1304.9
Prefill through the first 18 layers862.1845.1
ATP91.180.2
Subsequent prefill + decode702.5185.1
Independently measured total latency1,966.81,415.3
Peak GPU memory (GiB)19.0219.31

To explain the difference in Qwen3-VL token counts between Table 2 and Appendix Table 14, we clarify the sources of these two statistics. The main results table and the appendix audit table cover different evaluation scopes. The main table reports results across multiple evaluation datasets, and 1,725 denotes the 30% budget based on the reference visual sequence length used in that table; it does not mean that every VideoMME input retains this number of tokens. Appendix Table 14 covers only VideoMME and computes the budget from the actual number of visual tokens in each input. For Qwen3-VL, dynamic resolution leads to different absolute token budgets across inputs and datasets. In the VideoMME audit, the average budget is 1,406.04 tokens and the actual average output is 1,393.19 tokens, a difference of 12.85 tokens. This shortfall arises because MGDE compresses some units below their budgets before ATP. For VDC, the average budget and actual average output are 1,873.01 and 1,779.0 tokens, respectively, because Qwen's dynamic-resolution mechanism allocates different numbers of tokens depending on video-frame dimensions. We will further clarify this accounting in the appendix and thank the reviewer for pointing it out. Appendix C.3 provides details on token-budget alignment and comparison fairness. We compare methods under the same budget cap. When MGDE's output falls below the budget, FoveaTree retains the remaining tokens without padding, so the final token counts are not strictly matched for every input.

Please let us know if you have any follow-up questions. We are happy to clarify. If you think our response addresses your concerns, please consider raising your score.

Dear Reviewer S8ih,

Thank you for your careful evaluation of our work and for providing thoughtful and constructive feedback. Your comments have been valuable in helping us further clarify our methodological contributions, strengthen our experimental validation, and improve the overall presentation of the paper.

With the discussion period approaching its conclusion, we would greatly appreciate hearing whether our responses and clarifications adequately address your concerns. If any questions or issues remain, we would be happy to provide further explanations.

Thank you again for your time, careful consideration, and constructive suggestions, which have helped us improve the quality of our work.

Best regards,

The Authors

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

This paper introduces FoveaTree, a two-stage, query-guided visual token pruning method for Video LLMs. This training-free method consists of two components: Merge-Gain Density Estimation (MGDE) builds a quadtree for each frame and prunes tokens by dropping, merging or keeping them, based on the distortion and gain caused by merging. Attention Tree Pruning (ATP) propagates scores bottom-up through the resulting tree to assess the region-level relevance of tokens and to meet the assigned token budget. Each component addresses a specific challenge: MGDE mitigates hierarchy-blind pruning by assessing the regional compressibility of each frame using layer-0 features from the visual encoder. ATP mitigates attention drift by applying text-to-vision attention over the hierarchy built by MGDE, which improves query-relevant pruning. The authors validate their method on multiple video benchmarks covering video understanding, temporal reasoning and detailed captioning.

Critical strengths
  • The paper is well written and easy to follow.
  • The method achieves state-of-the-art performance across benchmarks and backbones, with computational costs comparable to or lower than those of previous work.
  • The paper is well motivated, providing empirical evidence of both attention drift and hierarchy-blind pruning.
Critical weaknesses
  • The method is fairly complex and has multiple parameters that may require dataset-specific tuning. The merge-gain threshold is fixed at 0.005 without any discussion or ablation, and the leaf cap LmaxL_{max} is set per backbone, again without ablation or justification.
  • As the authors acknowledge, the method does not include temporal processing, so it may miss temporal context during pruning.
  • The method has relatively high memory requirements compared to FlashVID, its closest competitor in terms of performance. Table 10 also shows that FlashVID is faster and uses less memory at low token retention rates. It would be useful to know where the latency of the method comes from.
Questions for authors

I am not sure I understand what "Avg. Perf." represents in Figure 1. My understanding is that it is the "expected" average domain-level performance, derived from the performance retention on the full evaluation set. If so:

  • Which pruning method is used to compute this average? Is it the average over all methods?
  • How does FoveaTree compare to these methods on each domain in terms of relative performance retention?

Figure 8 reports overall performance on the specific domains, but not relative to each method's performance on the full set, so it does not show that FoveaTree resolves this issue.

What should be addressed

  • For a fixed budget, report the latency induced by each component (MGDE and ATP).
  • Explain how the merge-gain threshold and the leaf cap are set. An ablation of the merge-gain threshold on VideoMME would help assess the method's sensitivity to this parameter.
  • Clarify how Figure 1 is obtained and compare FoveaTree to the other methods (see the questions above).
2 comments

Please let us know if you have any follow-up questions. We are happy to clarify.

I thank the authors for their detailed response. I have no further questions and maintain my recommendation for acceptance.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.