Skip to content

Why 1 + 1 < 1 in Visual Token Pruning: Beyond Naive Integration via Multi-Objective Balanced Covering

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Existing visual token pruning methods for MLLMs naively combine prompt alignment (PA) and visual preservation (VP) objectives with fixed strategies, ignoring how their relative importance shifts with the prompt-visual coupling of each task. This paper derives the first closed-form Hausdorff-distance error bound for visual token pruning, reveals a provable trade-off between PA and VP governed by prompt-visual coupling strength, and proposes Multi-Objective Balanced Covering (MoB) — a training-free algorithm that converts this trade-off into a budget-allocation problem via greedy radius trading.

Problem

Multi-objective visual token pruning methods (e.g., MustDrop) fail to consistently outperform single-objective baselines (Figure 1a). The root cause is that existing methods statically combine VP and PA across all tasks, ignoring that their relative importance depends on prompt-visual coupling — the Hausdorff distance between prompt and visual token distributions. Fine-grained tasks (TextVQA, POPE) exhibit weak coupling and benefit more from PA; coarse-grained tasks (MMB, VizWiz) show strong coupling and benefit more from VP. No prior method formalizes or exploits this distinction.

Method

Theoretical foundation. Under a Lipschitz continuity assumption on the transformer stack (w.r.t. Hausdorff distance), the authors derive a closed-form error bound (Lemma 1) showing that pruning error depends on three pairwise distances: dH(S,P) (PA), dH(S,V) (VP), and dH(V,P) (coupling η). Using ε-covering theory, Theorem 1 establishes that for any partition S = Sp ⊔ Sv of retained tokens, the product dH(Sp,P)·dH(Sv,V) is lower-bounded by max{D₁K^{−2/d_eff}, D₂η²}, revealing an intrinsic trade-off whose dominant term switches between budget-governed and coupling-governed regimes.

MoB algorithm. MoB operationalizes the trade-off as budget allocation: given total budget K, split it into Kp tokens for PA and K−Kp for VP. (1) Prompt center set Sp: k-fold nearest-neighbor covering — over-sample k nearest visual tokens per prompt token into a candidate set, then retain the Kp candidates maximizing worst-case prompt alignment. The hyperparameter k is larger under weak coupling, smaller under strong coupling. (2) Visual center set Sv: Farthest Point Sampling on V\Sp to maximize coverage of the visual token space. Budget split Kp is selected per coupling pattern (optionally using an η-prior estimated from the data). Complexity is O(N(L+K)d) — multilinear in token counts, compatible with flash attention.

Key Contributions

  • First closed-form error bound for visual token pruning via Hausdorff distance, unifying VP and PA contributions under prompt-visual coupling.
  • Formal quantification of the VP–PA trade-off (Theorem 1): optimal per-objective attainment level is ε* = max{η/z, D₁K^{−1/d_eff}}, showing coupling strength governs which objective dominates.
  • MoB: training-free, provably bounded, multilinear-complexity algorithm with greedy radius trading reducing the attainment trade-off to Kp budget allocation.
  • Empirical demonstration across 14 benchmarks covering image and video understanding on LLaVA-1.5-7B, LLaVA-Next-7B, Qwen2-VL-7B, and Video-LLaVA-7B.

Results

  • LLaVA-1.5-7B, 88.9% token reduction (K=64): MoB achieves 96.4% of vanilla performance vs. 90.1% for MustDrop (VP+PA) and 84.6% for SparseVLM; 2.7% improvement over the second-best baseline.
  • LLaVA-1.5-7B, 66.7% reduction (K=192): MoB with η-prior reaches 100.6% of vanilla (i.e., matches vanilla with only 33.3% of tokens).
  • Video-LLaVA-7B, 93.4% reduction: MoB preserves 97.9% performance, +1.6% over TwigVLM (ICCV'25), +4.7% over VisionZip.
  • LLaVA-Next-7B: 1.3–1.5× inference speedup with negligible performance loss.
  • Qwen2-VL-7B, 77.8% reduction: MoB retains 95.2% performance vs. 94.3% for DART and 91.0% for FastV.
  • MoB outperforms all baselines (FastV, SparseVLM, MustDrop, DART, FasterVLM, VisionZip, TwigVLM) on most benchmarks; advantage grows at more aggressive pruning rates.

Limitations

  • Theoretical guarantees rely on Lipschitz continuity of the transformer composition w.r.t. Hausdorff distance (Assumption 1), which is generally plausible but not universally verified for all MLLM architectures.
  • Kp (the budget split) requires a preliminary search or prior estimation of coupling η per task/benchmark, introducing tuning overhead not present in single-objective methods.
  • The η-prior mechanism for automatic coupling estimation is left to future work; current practice uses per-benchmark hyperparameter tuning.
  • Farthest Point Sampling for VP is iterative and may be slower in practice for very large N despite multilinear worst-case complexity.

Relevance to Vision-Language Models

Visual token reduction is a central efficiency challenge for MLLMs at scale (LLaVA-Next uses 2880 tokens; Video-LLaVA uses 2048), and this paper provides both a rigorous theoretical grounding and a practical training-free solution. By characterizing prompt-visual coupling as the decisive factor governing whether PA or VP should dominate, MoB directly improves the efficiency–accuracy trade-off for the inference pipeline of standard VLMs without modifying architecture or requiring fine-tuning. The framework generalizes across image and video domains and across model families (LLaVA, Qwen2-VL), making it broadly applicable to VLM deployment research. For researchers tracking VLMs, this work advances the understanding of why naïve multi-objective combination fails and provides actionable guidance for token budget design.