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

Zihan Meng; Weidong Chen; Dexiang Hong; Xinyan Liu; Zhendong Mao

cs.CVOct 12, 2026

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

Authors: Zihan Meng, Weidong Chen, Dexiang Hong, Xinyan Liu, Zhendong Mao

Organizations: University of Science and Technology of China · Harbin Institute of Technology

Abstract

Video large language models (Video LLMs) encode each frame into hundreds of visual tokens, making video inference expensive. Existing methods reduce this cost through similarity-based merging or attention-based selection but face two challenges: Hierarchy-blind Pruning, which overlooks regional compressibility and can discard critical evidence, and Attention Drift, where positional effects and attention sinks shift text-to-vision attention away from task relevance. We propose FoveaTree, a two-stage, training-free visual-token pruning framework. First, Merge-Gain Density Estimation measures the feature distortion caused by regional merging and constructs a quadtree-derived density map to guide token dropping, merging, and retention. Second, Attention Tree Pruning uses the surviving units and inherited tree topology to refine text-to-vision attention in intermediate LLM layers, preserving relevant regional evidence while removing low-relevance content. We evaluate FoveaTree on InternVL3.5-8B and Qwen3-VL-8B across five video question-answering benchmarks and one captioning benchmark at 50%, 30%, and 10% visual-token retention. FoveaTree consistently achieves overall state-of-the-art performance across the evaluated settings, offering a strong accuracy-efficiency trade-off.

Figures & tables

Figure 1: Illustration of Hierarchy-blind Pruning on fine-grained domains from VideoMME ( Fu et al., 2025a ) and VDC ( Chai et al., 2025 ) . Avg. Perf. summarizes performance retention on the complete evaluation set and is projected onto each domain’s full-model score, whereas the method curves report the measured domain-level performance. The gray regions show the resulting gap on OCR, counting, object recognition, and detailed captioning across pruning ratios.

Figure 2: Architectural comparison of FrameFusion and MGDE. FrameFusion merges corresponding tokens across adjacent frames; MGDE instead constructs an explicit multiscale regional hierarchy.

Figure 3: Visualization of our tree-based attention pruning and the conventional attention-based top- $k$ pruning used by LearnPruner ( Takezoe et al., 2026 ) at 50% and 30% visual-token retention for two input frames. The comparison illustrates Attention Drift around peripheral and task-irrelevant regions (red boxes), while the tree structure improves robustness to this bias at both budgets.

Figure 4: FoveaTree overview. MGDE builds a regional hierarchy and compresses visual tokens before decoder prefill; ATP then uses text-to-vision attention to prune the surviving hierarchy.

Figure 5: MGDE density maps from three vision encoders. Layer-0 features preserve texture and boundary cues, yielding regional hierarchies, whereas deeper features obscure spatial details.

Figure 6: Visualization of ATP on one pruned video frame after MGDE. MGDE provides the surviving visual units and their inherited quadtree. ATP assigns text-to-vision attention scores to these units, propagates them to ancestor nodes, and performs top-down tree cutting and merging.

Figure 7: Token-selection frequencies of LearnPruner’s top- $k$ pruning and ATP. ATP reduces peripheral selections and retains more tokens in the central region.

Method	Video QA					Video Caption		Avg.
Method	VideoMME	NExT-QA	MVBench	Valor32k	VNBench	VDC Acc.	VDC Score	Avg.
InternVL3.5 (16,384 Tokens)	65.67	80.22	72.19	76.63	59.85	40.47	1.90	100.00%
Retain 8,192 Tokens ( $\downarrow$ 50.0% )
ToMe (ICLR-2023)	62.64	76.48	69.02	73.14	57.18	38.67	1.82	95.52%
FastV (ECCV-2024)	62.05	75.79	68.27	72.51	56.96	38.45	1.89	95.40%
VisionZip (CVPR-2025)	63.26	77.24	69.42	74.10	57.89	39.20	1.81	96.33%

Table 1: InternVL3.5-8B results at 10%, 30%, and 50% visual-token retention. Bold and underlined values mark the best and second-best compressed results; the gray line provides the baseline result.

Method	Video QA					Video Caption		Avg.
Method	VideoMME	NExT-QA	MVBench	Valor32k	VNBench	VDC Acc.	VDC Score	Avg.
Qwen3-VL (5,753 Tokens)	66.15	83.43	67.49	78.27	58.63	45.28	2.31	100.00%
Retain 2,876 Tokens ( $\downarrow$ 50.0% )
ToMe (ICLR-2023)	62.88	79.27	64.32	74.46	55.83	43.11	2.20	95.17%
FastV (ECCV-2024)	63.59	80.20	64.92	75.35	56.77	43.76	2.24	96.45%
VisionZip (CVPR-2025)	64.25	81.00	65.42	76.30	57.18	44.20	2.24	97.25%

Table 2: Qwen3-VL-8B results at 10%, 30%, and 50% visual-token retention. Bold and underlined values mark the best and second-best compressed results; the gray line provides the baseline result.

Method	Time	Mem	Latency	TFLOPs	Acc.	Time	Mem	Latency	TFLOPs	Acc.
InternVL3.5 (16,384 Tokens)	111:47	20.26	2.484	322.0	65.67	111:47	20.26	2.484	322.0	65.67
	Retain 4,928 Tokens ( $\downarrow$ 70.0% )					Retain 1,664 Tokens ( $\downarrow$ 90.0% )
ToMe (ICLR-2023)	74:58	17.67	1.666	86.5	61.59	89:28	16.90	1.988	33.6	56.92
FastV (ECCV-2024)	106:34	19.09	2.368	204.2	61.22	98:06	19.09	2.180	177.8	58.22
VisionZip (CVPR-2025)	49:11	17.67	1.093	86.5	62.56	44:25	16.90	0.987	33.6	60.10
FrameFusion (ICCV-2025)	54:22	17.94	1.208	93.0	62.24	35:52	17.94	0.797	43.9	60.42

Table 3: Efficiency analysis at 30% and 10% visual-token retention on InternVL3.5 on Video-MME.

Figure 8: Fine-grained performance and retained-token visualizations. FoveaTree achieves the strongest results across the shown token-retention ratios, while the right panel illustrates that it preserves relevant regions more completely than the compared methods under matched budgets.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Video QA					Video Caption		Avg.
Method	VideoMME	NExT-QA	MVBench	Valor32k	VNBench	VDC Acc.	VDC Score	Avg.
LLaVA-OV (12,544 Tokens)	58.56	80.57	58.26	74.11	62.87	41.85	2.17	100.00%
Retain 6,272 Tokens ( $\downarrow$ 50.0% )
ToMe (ICLR-2023)	57.17	78.86	56.84	72.48	61.51	41.13	2.12	97.81%
FastV (ECCV-2024)	55.92	76.98	55.79	70.83	60.24	39.88	2.08	95.62%
VisionZip (CVPR-2025)	57.04	78.32	56.59	72.21	61.35	40.86	2.11	97.38%

Appendix

Table 9: LLaVA-OV-7B results at 10%, 30%, and 50% visual-token retention. Bold and underlined values mark the best and second-best compressed results; Full provides the unpruned reference.

Method	Time	Mem	Latency	TFLOPs	Acc.	Time	Mem	Latency	TFLOPs	Acc.
Qwen3-VL (5,753 Tokens)	41:24	18.26	0.920	77.247	66.15	41:24	18.26	0.920	77.247	66.15
	Retain 1,725 Tokens ( $\downarrow$ 70.0% )					Retain 575 Tokens ( $\downarrow$ 90.0% )
ToMe (ICLR-2023)	29:40	17.35	0.659	26.333	61.70	32:05	17.05	0.713	12.697	56.00
STTM (ICCV-2025)	31:54	18.02	0.709	51.789	64.54	31:34	17.97	0.702	44.971	63.38
FlashVID (ICLR-2026)	26:57	17.51	0.599	28.835	64.77	20:59	17.08	0.466	13.469	63.95
FoveaTree (Ours)	24:25	17.80	0.543	34.303	65.38	22:40	17.62	0.504	27.835	64.92

Appendix

Table 10: Efficiency analysis at 30% and 10% visual-token retention on the additional backbones on Video-MME.

Depth $D$	VideoMME	VDC Acc.	Avg.	Lat.
$D=2$	63.87	38.92	96.71%	1.871
$D=3$	65.24	40.31	99.47%	1.942
$D=4$	66.01	41.39	101.40%	2.006
$D=5$	65.83	41.02	100.80%	2.089

Appendix

Table 11: Ablation on the maximum quadtree depth

D

at 30% retention. Latency follows the efficiency protocol of the main paper.

$\kappa_{u}$	VideoMME	VDC Acc.	Avg.
$\kappa_{u}=\delta_{u}$	65.18	40.42	99.57%
$\kappa_{u}=\rho_{u}$	64.15	39.47	97.61%
$\kappa_{u}=a_{u}$	63.36	38.71	96.07%
$\kappa_{u}=\delta_{u}+\rho_{u}$	66.01	41.39	101.40%

Appendix

Table 12: Ablation on the ATP split-score composition at 30% retention.

Figure 10: Cross-backbone comparison. Top: average relative performance versus the visual-token retention ratio on InternVL3.5-8B, Qwen3-VL-8B, Qwen2.5-VL-7B, and LLaVA-OneVision-7B for FoveaTree, FlashVID, FrameFusion, and ToMe; the dashed line marks the unpruned reference. Bottom: total Video-MME runtime under the efficiency protocol of the main paper for FoveaTree, FlashVID, STTM, and ToMe; the dashed line marks the runtime of the unpruned model.

Symbol	Meaning
$N_{t}$	number of original visual tokens
$r$	nominal retention ratio
$B_{t}$	ATP budget upper bound, $\min(N_{t},\lceil rN_{t}\rceil)$
$M_{t}$	number of tokens surviving MGDE
$K_{t}$	number of tokens finally emitted by ATP
$B_{t}-K_{t}$	budget left unfilled by MGDE

Appendix

Table 13: Definition of the per-unit token-budget symbols.

Model	Ret.	Units	Actual	Range	Unfilled	Max unfilled	Util.	Over-budget
InternVL3.5	50%	172,800	8,043.21	5,048–8,192	148.79	3,144	98.2%	0
InternVL3.5	30%	172,800	4,881.93	3,591–4,928	46.07	1,337	99.1%	0
InternVL3.5	10%	172,800	1,656.70	1,326–1,664	7.30	338	99.6%	0
LLaVA-OneVision	30%	172,800	3,628.93	1,685–3,776	147.07	2,091	96.105%	0
LLaVA-OneVision	10%	172,800	1,251.26	795–1,280	28.74	485	97.755%	0
Qwen3-VL	30%	86,400	1,393.19	956–1,440	12.85	452	99.086%	0

Appendix

Table 14: Token-budget audit over all 2,700 Video-MME question-video inputs for each backbone. Actual is the mean final visual-token count per input; Range is its minimum and maximum. Unfilled and Max unfilled are the mean and maximum of each input’s own budget minus its final token count. Util. is total retained tokens divided by total budget. Units counts native temporal units across all inputs; Over-budget counts units exceeding their own budgets. Budgets are computed separately for each input, including dynamic-resolution inputs.

Explore similar work

Apr 2, 2026

HieraVid: Hierarchical Token Pruning for Fast Video Large Language Models

Video Large Language Models (VideoLLMs) have demonstrated impressive capabilities in video understanding, yet the massive number of input video tokens incurs a significant computational burden for deployment. Existing methods mainly prune video tokens at input level while neglecting the inherent information structure embedded in videos and large language models (LLMs). To address this, we propose HieraVid, a hierarchical pruning framework that progressively and dynamically reduces visual redundancy. Based on two observations that videos possess the segment-frame structure and LLMs internally propagate multi-modal information unidirectionally, we decompose pruning into three levels: 1) segment-level, where video tokens are first temporally segmented and spatially merged; 2) frame-level, where similar frames within the same segment are jointly pruned to preserve diversity; 3) layer-level, redundancy gradually shrinks as LLM layer increases w/o compromising performance. We conduct extensive experiments on four widely used video understanding benchmarks to comprehensively evaluate the effectiveness of HieraVid. Remarkably, with only 30% of tokens retained, HieraVid achieves new state-of-the-art performance, while maintaining over 98% and 99% of the performance of LLaVA-Video-7B and LLaVA-OneVision-7B, respectively.

Yansong Guo, Chaoyang Zhu, Jiayi Ji +2

Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China Xiamen University Xiamen, Fujian, China

Token Pruning Video-Language Models Visual Token Pruning Video Token Compression

Ask PDF

Mar 24, 2026

ForestPrune: High-ratio Visual Token Compression for Video Multimodal Large Language Models via Spatial-Temporal Forest Modeling

Due to the great saving of computation and memory overhead, token compression has become a research hot-spot for MLLMs and achieved remarkable progress in image-language tasks. However, for the video, existing methods still fall short of high-ratio token compression. We attribute this shortcoming to the insufficient modeling of temporal and continual video content, and propose a novel and training-free token pruning method for video MLLMs, termed ForestPrune, which achieves effective and high-ratio pruning via Spatial-temporal Forest Modeling. In practice, ForestPrune construct token forests across video frames based on the semantic, spatial and temporal constraints, making an overall comprehension of videos. Afterwards, ForestPrune evaluates the importance of token trees and nodes based on tree depth and node roles, thereby obtaining a globally optimal pruning decision. To validate ForestPrune, we apply it to two representative video MLLMs, namely LLaVA-Video and LLaVA-OneVision, and conduct extensive experiments on a bunch of video benchmarks. The experimental results not only show the great effectiveness for video MLLMs, e.g., retaining 95.8% average accuracy while reducing 90% tokens for LLaVA-OneVision, but also show its superior performance and efficiency than the compared token compression methods, e.g., +10.1% accuracy on MLVU and -81.4% pruning time than FrameFusion on LLaVA-Video.

Shaobo Ju, Baiyang Song, Tao Chen +6

Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, 361005, P.R. China. · National University of Defense Technology.

Video Token Compression Visual Token Pruning Video-Language Models

Ask PDF

Aug 28, 2025

MMG-Vid: Maximizing Marginal Gains at Segment-level and Token-level for Efficient Video LLMs

Video Large Language Models (VLLMs) excel in video understanding, but their excessive visual tokens pose a significant computational challenge for real-world applications. Current methods aim to enhance inference efficiency by visual token pruning. However, they do not consider the dynamic characteristics and temporal dependencies of video frames, as they perceive video understanding as a multi-frame task. To address these challenges, we propose MMG-Vid, a novel training-free visual token pruning framework that removes redundancy by Maximizing Marginal Gains at both segment-level and token-level. Specifically, we first divide the video into segments based on frame similarity, and then dynamically allocate the token budget for each segment to maximize the marginal gain of each segment. Subsequently, we propose a temporal-guided DPC algorithm that jointly models inter-frame uniqueness and intra-frame diversity, thereby maximizing the marginal gain of each token. By combining both stages, MMG-Vid can maximize the utilization of the limited token budget, significantly improving efficiency while maintaining strong performance. Extensive experiments demonstrate that MMG-Vid can maintain over 99.5% of the original performance, while effectively reducing 75% visual tokens and accelerating the prefilling stage by 3.9x on LLaVA-OneVision-7B. Code is available at https://github.com/ylnxxts/MMG-Vid.

Junpeng Ma, Qizhe Zhang, Ming Lu +4

State Key Laboratory of Multimedia Information Processing, School of Computer Science, Peking University · Fudan University · Taobao & Tmall Group of Alibaba

Efficient VLM Inference Video Token Compression Visual Token Pruning Temporal Video Understanding

Ask PDF