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

HieraVid: Hierarchical Token Pruning for Fast Video Large Language Models
Apr 2, 2026Yansong Guo, Chaoyang Zhu, Jiayi Ji +2Token Pruning Video-Language Models
Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China Xiamen University Xiamen, Fujian, China
ForestPrune: High-ratio Visual Token Compression for Video Multimodal Large Language Models via Spatial-Temporal Forest Modeling
Mar 24, 2026Shaobo Ju, Baiyang Song, Tao Chen +6Video Token Compression Visual Token Pruning
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.
MMG-Vid: Maximizing Marginal Gains at Segment-level and Token-level for Efficient Video LLMs
Aug 28, 2025Junpeng Ma, Qizhe Zhang, Ming Lu +4Efficient VLM Inference Video Token Compression
State Key Laboratory of Multimedia Information Processing, School of Computer Science, Peking University · Fudan University · Taobao & Tmall Group of Alibaba

Apr 2, 2026J/K move · Enter open · S save

HieraVid: Hierarchical Token Pruning for Fast Video Large Language Models

Yansong Guo, Chaoyang Zhu, Jiayi Ji, Jianghang Lin+1

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

HieraVid: Hierarchical Token Pruning for Fast Video Large Language Models

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

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