Video Large Language Models (Video LLMs) achieve strong performance on video understanding tasks but suffer from high inference costs due to the large number of visual tokens. We study training-free, query-agnostic video token compression, where heuristic importance rules can over-represent large redundant visual groups and miss less frequent visual patterns, particularly under aggressive token budgets. We propose KiToke, a distribution-aware compression framework that treats visual tokens as samples from the video's spatiotemporal token distribution. KiToke uses global embedding density as a proxy for representational redundancy and inverse-density sampling to balance token allocation across visual patterns of different frequencies. It further aggregates unselected tokens into retained anchors within detected temporal intervals to reduce cross-transition mixing. Across evaluated backbones, KiToke achieves the highest average accuracy among compared training-free methods and remains robust down to 1% retention, where most evaluated baselines underperform uniform random token sampling. On LLaVA-OneVision, it preserves 98.5% and 89.2% of the uncompressed model's four-benchmark mean accuracy at 10% and 1% token retention, with 6.8x and 12.5x prefill speedups, respectively, including compression overhead.
Figures & tables
Figure 1: Distribution-aware token compression improves robustness across retention ratios. (a) KiToke uses global token density as a proxy for redundancy and inverse-density sampling to promote broad visual coverage. (b) Normalized performance vs. retention ratio for representative token compression methods, including Random. All prior methods shown at 1% retention fall below Random. Performance is normalized by each uncompressed backbone before averaging over LLaVA-OneVision, LLaVA-Video, and Qwen3-VL, using four benchmarks. (c) Normalized average accuracy versus prefill latency on LLaVA-OneVision-7B at 1% retention. Accuracy is the four-benchmark mean normalized to the uncompressed model. Latency includes compression overhead.
Figure 2: Overview of KiToke. (a) Visual tokens are compressed between the vision projector and the LLM. (b) Anchors are sampled using inverse-density scores computed from the full-video token distribution. (c) Unselected tokens are merged into anchors within content-adaptive temporal intervals using the same scores.
Figure 3: Performance comparison with state-of-the-art methods across video understanding benchmarks on LLaVA-Video and Qwen3-VL . Mean accuracy over four video understanding benchmarks is normalized to the uncompressed backbone (100%). Detailed benchmark-level results are reported in Appendix B .
Anchor selector
Mean accuracy (%)
Uniform sampling
50.4
Density-proportional, full video
48.8
k -center Gonzalez (1985)
50.1
DivPrune Alvar et al. (2025)
50.8
FastVID Shen et al. (2025a)
50.4
FLoC Cho et al. (2026)
50.3
Table 3: Controlled query-agnostic token allocation. We vary density scope only for selection, keeping intervals and inverse-density merge weights fixed for all selectors. Four-benchmark mean accuracy (%) on LLaVA-OneVision-7B at 1% retention is reported.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Hyperparameter ablations on LLaVA-OneVision-7B at 1% visual-token retention. Panels (a)–(c) vary Gaussian bandwidth α , the threshold on adjacent-frame change ct , and the threshold on its absolute increase Δt , respectively. Filled markers identify the defaults α=800 and (τc,τΔ)=(110,70) . The vertical axis is mean accuracy over MVBench, LongVideoBench, MLVU, and VideoMME without subtitles, normalized by the uncompressed LLaVA-OneVision-7B mean (100%).
Figure 5: Model-size ablation at 1% visual-token retention. Comparison at 0.5B, 7B, and 72B model sizes. The vertical axis reports normalized average accuracy: 100Aˉcompressed/Aˉuncompressed , where Aˉ is the mean accuracy over MVBench, LongVideoBench, MLVU, and VideoMME without subtitles. Each compressed result is normalized by the uncompressed result for the same model variant.
Figure 6: Qualitative comparison of temporal interval construction. Each example (a)–(e) shows 12 frames in temporal order, with zero-based display positions 0–11. FastVID and KiToke boundaries are shown in the corresponding rows, marked by red separators and downward triangles. In these examples, KiToke produces boundaries that align more closely with the illustrated content changes than FastVID.
Figure 7: Qualitative comparison of token selection (case 1). All methods show the same five frames, labeled with zero-based indices 1, 5, 6, 7, and 31. The bars show choice-normalized probabilities over A–D, and “Pred” identifies the option parsed from the generated answer. Compressed methods use γ=1% retention, with LLaVA-OneVision as the uncompressed reference. Anchors are fully opaque, while non-anchor locations are faded and, for KiToke, may contribute through merging. Green marks the ground-truth choice.
Figure 8: Qualitative comparison of token selection (case 2). All methods show the same five frames, labeled with zero-based indices 0, 4, 11, 15, and 26. The bars show choice-normalized probabilities over A–D, and “Pred” identifies the option parsed from the generated answer. Compressed methods use γ=1% retention, with LLaVA-OneVision as the uncompressed reference. Anchors are fully opaque, while non-anchor locations are faded and, for KiToke, may contribute through merging. Green marks the ground-truth choice.
Figure 9: Qualitative comparison of token selection (case 3). All methods show the same five frames, labeled with zero-based indices 0, 13, 14, 16, and 18. The bars show choice-normalized probabilities over A–D, and “Pred” identifies the option parsed from the generated answer. Compressed methods use γ=1% retention, with LLaVA-OneVision as the uncompressed reference. Anchors are fully opaque, while non-anchor locations are faded and, for KiToke, may contribute through merging. Green marks the ground-truth choice.
Figure 10: Qualitative comparison of token selection (case 4). All methods show the same five frames, labeled with zero-based indices 7, 18, 27, 28, and 31. The bars show choice-normalized probabilities over A–D, and “Pred” identifies the option parsed from the generated answer. Compressed methods use γ=1% retention, with LLaVA-OneVision as the uncompressed reference. Anchors are fully opaque, while non-anchor locations are faded and, for KiToke, may contribute through merging. Green marks the ground-truth choice.
Figure 11: Qualitative comparison of token selection (case 5). All methods show the same five frames, labeled with zero-based indices 7, 8, 12, 21, and 24. The bars show choice-normalized probabilities over A–D, and “Pred” identifies the option parsed from the generated answer. Compressed methods use γ=1% retention, with LLaVA-OneVision as the uncompressed reference. Anchors are fully opaque, while non-anchor locations are faded and, for KiToke, may contribute through merging. Green marks the ground-truth choice.