PaperlayerView exact revision on arXiv

Source-linked AI summary

StackTok: Accelerating VLMs Inference with Budget-Adaptive Visual Token Selection

Zhenbin Wang, Lei Zhang, Lituan Wang, Wei Huang, Yan Wang, Zhenwei Zhang

arXiv:2609.16841v1cs.CVcs.AI

TL;DR

Longer visual-token sequences raise VLM inference costs, while the appropriate balance between query relevance and visual coverage varies across queries and token budgets. StackTok uses relevance as its objective and budget-calibrated coverage as support, adapting its selection priorities to the current subset. It ranks first among training-free selectors in every reported model–budget setting.

  • Problem

    High-resolution VLM inputs create long visual-token sequences that raise inference costs, and fixed relevance–coverage trade-offs do not adapt to differing queries and token budgets.

    Source: Introduction · p. 1

  • Method

    StackTok builds a size-indexed coverage reference, calibrates support with query–vision affinity entropy, and interleaves relevance- and coverage-oriented additions under a fixed token budget.

    Source: Introduction · p. 2

  • Results

    Across five VLMs and ten benchmarks, StackTok ranks first among training-free selectors in every tested model–budget setting.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    StackTok provides a training-free framework whose selection priorities adapt to the input and evolving retained set.

    Source: Conclusion · p. 7

    The method retains exactly min(K, |U|) eligible tokens from the encoded image rather than selecting a variable number.

    Source: Overview and Problem Setup · p. 3

Abstract

from arXiv · show

Increasing image resolution produces ever-longer visual-token sequences in vision-language models (VLMs), substantially raising their inference cost. To reduce this overhead without retraining, existing methods select compact token subsets that prioritize query relevance, visual coverage, or a fixed trade-off between them. The appropriate balance, however, varies across queries and token budgets: localized questions favor relevance, whereas holistic questions demand broader visual coverage. We introduce StackTok, a training-free selector that treats query relevance as the objective and visual coverage as budget-calibrated support. StackTok builds a size-indexed coverage reference from a coverage-only greedy sequence and adjusts its support target using query--vision affinity entropy. A reference-gated interleaved selection policy then switches between relevance- and coverage-oriented additions according to the current subset's support deficit. For high-resolution inputs, StackTok allocates one shared token budget across crops according to the combined marginal gain of locally nominated tokens. Evaluated with five VLMs over ten distinct image-understanding benchmarks, StackTok ranks first among training-free selectors in every tested model--budget setting. On high-resolution LLaVA-NeXT-7B, it retains 95.26% of full-token performance with only 160 of 2{,}880 (5.6%) visual tokens.

Introduction

Longer visual-token sequences raise VLM inference costs, while relevance and coverage selectors make different trade-offs under tight budgets. StackTok uses query relevance as its objective, coverage as budget-calibrated support, and adapts selection priorities to the input and retained subset.

Motivation

  • Longer visual sequences substantially increase prefilling latency and memory consumption, motivating training-free selection before LLM inference.The paper contrasts 576 tokens for a 336 × 336 LLaVA-1.5 image with up to 2,880 for LLaVA-NeXT.Source: Introduction · p. 1
  • Relevance-only selection can discard broader context, coverage-only selection can retain regions unrelated to the query, and fixed scalarization cannot adapt across queries or subset sizes.Localized questions and holistic scene descriptions call for different subsets.Source: Introduction · p. 1
  • StackTok treats relevance as the objective and coverage as a support requirement calibrated to the retained-token budget, rather than as a fixed exchange rate.The block-stacking analogy maps useful reach to query relevance and support to visual coverage.Source: Introduction · p. 1, Figure 1 · p. 2

StackTok

  • StackTok builds a size-indexed coverage reference, adjusts its support target using query–vision affinity entropy, and interleaves relevance- and coverage-oriented additions.For high-resolution inputs, it allocates a shared token budget across crops according to combined marginal gains.Source: Introduction · pp. 1–2

Contributions

  • Across five VLMs and ten benchmarks, StackTok ranks first among training-free selectors in every tested model–budget setting.The contribution statement also describes a shared-budget extension for multi-crop selection.Source: Introduction · p. 2

Related Work

Prior work reduces inference costs within language backbones, while visual-token reduction addresses the input-side cost introduced by multimodal inputs. Existing VLM selectors emphasize query relevance, visual representativeness, or a fixed combination; StackTok instead varies which criterion guides selection.

Efficient Inference for Large Language and Multimodal Models

  • I/O-aware attention kernels, memory-aware serving, and context management reduce computation or memory costs within language backbones, while visual-token reduction addresses a complementary VLM bottleneck.Training-free visual-token reduction shortens the input to a pretrained backbone and is orthogonal to model- and system-level optimizations.Source: Efficient Inference for Large Language… · p. 2

Visual Token Reduction for Vision-Language Models

  • Attention-driven selectors prioritize model- or query-emphasized evidence, whereas dominance- and diversity-based methods preserve representative content without explicitly prioritizing the current query.The cited examples include FastV and SparseVLM for attention-driven selection, and VisionZip and DivPrune for dominance- and diversity-based selection.Source: Visual Token Reduction for… · p. 2
  • MMTok combines relevance and coverage with a fixed coefficient, while StackTok uses an entropy-adjusted, subset-size-indexed coverage reference to switch the active criterion.The fixed scalarization applies the same exchange rate across selection states and retained-set sizes.Source: Visual Token Reduction for… · p. 2

Method

StackTok measures query relevance and visual coverage in representations suited to each signal, then uses a size-indexed coverage reference and input-adaptive strictness to guide fixed-budget selection. Its multi-crop extension shares one budget across crops, and optional swaps refine the retained set while preserving support.

Overview and Problem Setup

Reference-Gated Interleaved Selection

  • At each addition, the support deficit selects relevance or coverage as the primary criterion, with fallback to the secondary criterion if the primary gain is zero.The target gates the criterion rather than constraining every prefix, and the policy reassesses the state after each addition.Source: Figure 2 · p. 3, Reference-Gated Interleaved Selection · p. 4

Shared-Budget Allocation across Crops

Query Relevance and Visual Support

  • Facility-location coverage instances measure query relevance and visual coverage, and their diminishing returns allow exact incremental greedy updates.When there are no query tokens, relevance is identically zero.Source: Query Relevance and Visual Support · pp. 3–4

Budget- and Input-Calibrated Visual Support

  • A coverage-only greedy sequence supplies the size-indexed reference, while normalized query–vision affinity entropy calibrates how closely the support target is tracked.Low entropy permits greater emphasis on localized evidence; high entropy requests broader visual support, but entropy does not classify the query.Source: Budget- and Input-Calibrated Visual… · p. 4

Support-Preserving Swap Refinement

  • Optional cardinality-preserving one-exchange refinement accepts replacements that strictly increase relevance-plus-coverage while respecting a support floor.Below target the floor prevents support loss; above target it permits a decrease only down to the target.Source: Support-Preserving Swap Refinement · p. 5

Complexity and Practical Details

  • Affinity construction costs O(n^2 d_v + mnd) time and O(n^2 + mn) memory, while one complete swap pass costs O(r(uloc−r)(m+nloc)).Without query embeddings, StackTok uses visual coverage throughout, excludes padding, and returns the effective fixed budget.Source: Complexity and Practical Details · p. 5

Experiments

The experiments compare StackTok with training-free token selectors across multiple VLMs and budgets. StackTok ranks first in all 12 tested LLaVA model–budget settings, with strong retention even for high-resolution inputs.

Experimental Setup

  • The evaluation covers ten image-understanding benchmarks, four LLaVA models, and Qwen2.5-VL-7B; reported retention is relative to full-token scores.LLaVA-1.5 retains 192, 128, or 64 of 576 tokens; LLaVA-NeXT uses shared budgets of 640, 320, or 160 tokens across crops.Source: Experimental Setup · pp. 5–6

Main Results

  • At 160 tokens, StackTok retains 95.26% of full-token performance on LLaVA-NeXT-7B, using 5.6% of its 2,880 visual tokens.The shared budgets also retain 98.97% and 97.51% at 640 and 320 tokens, respectively.Source: Main Results · p. 6
  • StackTok ranks first in all 12 LLaVA model–budget settings, exceeding the strongest training-free baseline by 0.08–0.29 points.The comparison spans four LLaVA models and three budgets.Source: Main Results · p. 6, Table 3 · p. 7
  • At 64 tokens, StackTok trails MMTok on MME, VQAText, and SEED, so its aggregate advantage does not imply uniform benchmark dominance.The passage notes these tasks may depend on dispersed scene cues or fine-grained text.Source: Main Results · p. 7
  • Replacing the size-indexed reference with a final-budget target causes a larger performance deficit as budgets tighten; fixed strictness also incurs a consistent loss.One global β cannot adapt support requirements to input ambiguity, while relevance-only and coverage-only variants expose complementary failure modes.Source: Component ablation · p. 7

Conclusion

StackTok treats query relevance as the objective and visual coverage as budget-calibrated support. Its selection priorities adapt to the input and evolving retained set rather than remaining fixed during pruning.

Conclusion

  • StackTok frames query relevance and visual coverage as asymmetric, state-dependent roles, with coverage serving as budget-calibrated support.A size-indexed coverage reference and input-adaptive strictness guide selection at each step; crop-local nominations extend the approach to shared-budget high-resolution inputs.Source: Conclusion · p. 7

Appendix Overview

The appendix supplements the main paper with proofs, implementation details, additional experiments, and extended ablations.

Appendix Overview

  • The appendix proves Proposition 1 and Theorem 1, then reports Qwen2.5-VL-7B dynamic-resolution results and extended ablations.The ablations cover fixed scalarization, shared-budget crop allocation, support-preserving swap refinement, and strictness sensitivity.Source: Appendix Overview · p. 9

Proof of Proposition 1 (Coverage Structure)

Proposition 1 establishes normalized, monotone, and submodular coverage for the affinity-based coverage function. Its proof derives monotonicity and diminishing returns from the row-wise coverage definition.

Proof of Proposition 1 (Coverage Structure)

  • The coverage function is normalized, monotone, and submodular.Normalization follows from the empty-set convention; monotonicity follows because adding selected items cannot reduce row coverage.Source: Proof of Proposition 1 (Coverage… · p. 9
  • Adding a candidate changes each row’s coverage by a row-wise marginal gain, and averaging these changes gives the function’s marginal-gain formula.The proof then compares gains for nested selected sets.Source: Proof of Proposition 1 (Coverage… · p. 9
  • For nested sets S ⊆ T, the marginal gain from adding s is no larger at T, establishing diminishing returns.Summing the row-wise inequality yields the submodularity condition.Source: Proof of Proposition 1 (Coverage… · p. 9

Proof of Theorem 1 (Anytime Coverage Reference)

The proof establishes a coverage reference with diminishing increments and an approximation guarantee across its recorded prefixes. Each greedy prefix witnesses feasibility of its size-specific support threshold, though StackTok’s interleaved prefix is not guaranteed to meet it.

Additional Experimental Details and Results Evaluation Protocol

The additional experiments test StackTok under dynamic resolution and examine its policy, crop allocation, refinement, and strictness choices. Results favor StackTok across these comparisons, with the strictness sweep indicating local robustness only for one model–budget setting.

Additional Experimental Details and Results Evaluation Protocol

  • The evaluation uses pre-projector vision–vision affinities and post-projector query–vision affinities, with no training or fine-tuning.Qwen2.5-VL-7B uses τ_t = 0.01; other datasets use τ_t = 0.02, with τ_v = 0.2.Source: Evaluation Protocol · p. 10

Dynamic-Resolution Results

  • Avg.† gains over MMTok are 1.21, 1.28, and 1.02 points at 20%, 10%, and 5% retention under Qwen2.5-VL-7B dynamic resolution.At 5% retention, OCRBench is nearly tied: 30.73 versus 30.70.Source: Dynamic-Resolution Results · p. 10

Additional Ablations

  • StackTok improves over the best per-budget fixed scalarization by 0.14, 0.10, and 0.06 points at 192, 128, and 64 tokens.Source: Additional Ablations · p. 11
  • The shared crop-budget allocator’s gain over uniform quotas widens from 0.42 to 0.86 points as the budget contracts from 640 to 160 tokens.Initial-h_c-proportional quotas remain 0.25–0.41 points behind.Source: Additional Ablations · p. 11
  • Support-preserving swaps improve average retained performance by 0.40 and 0.30 points at 8 and 16 tokens, respectively.Source: Additional Ablations · p. 11, Table A4 · p. 11
  • The default strictness range [0.3, 0.9] performs best, while neighboring ranges change the 64-token result by at most 0.17 points.The sweep covers only one model–budget setting.Source: Additional Ablations · p. 11, Table A5 · p. 11

Related papers

Loading 2609.16841v1…