Paper deep dive
StackTok: Accelerating VLMs Inference with Budget-Adaptive Visual Token Selection
Zhenbin Wang, Lei Zhang, Lituan Wang, Wei Huang, Yan Wang, Zhenwei Zhang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2609.16841v1
- Canonical: https://arxiv.org/abs/2609.16841v1
Trouble viewing inline? Open PDF directly →
Full Text
61,975 characters extracted from source content.
Expand or collapse full text
StackTok: Accelerating VLMs Inference with Budget-Adaptive Visual Token Selection Zhenbin Wang, Lei Zhang ∗ , Lituan Wang, Wei Huang, Yan Wang, Zhenwei Zhang Sichuan University wangzhenbin@stu.scu.edu.cn Abstract 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 Recent VLMs improve fine-grained visual understanding by encoding images at increasingly high resolutions. A 336 × 336 image produces 576 visual tokens in LLaVA- 1.5 (Liu et al. 2024a), while the multi-crop encoder of LLaVA-NeXT (Liu et al. 2024b) can produce up to 2,880. These tokens enter the language backbone together with the prompt, so long visual sequences substantially increase pre- filling latency and memory consumption. Training-free token selection offers a direct remedy by retaining a compact sub- set before large language model (LLM) inference without adding parameters or fine-tuning (Chen et al. 2024; Yang et al. 2025). This practical bottleneck raises a more funda- mental question: when only a limited token budget can be retained, what makes a subset of visual tokens informative? Existing selectors provide two complementary answers. Relevance-oriented methods use language-model attention ∗ The corresponding author Code: https://github.com/wongzbb/StackToK or instruction tokens to preserve evidence related to the query (Chen et al. 2024; Zhang et al. 2025). They can retain fine details from a queried region, but may discard contextual evidence elsewhere in the image. Coverage-oriented meth- ods instead preserve representative or diverse tokens to retain a broader view of the scene (Yang et al. 2025; Alvar et al. 2025). They support holistic understanding, but may spend a tight budget on regions unrelated to the question. Reading a sign and describing an entire scene therefore call for differ- ent subsets. MMTok (Dong et al. 2026) takes an important step by combining query relevance and visual coverage in a unified submodular objective. Its fixed coefficient, how- ever, assigns the two signals the same exchange rate across queries, retained-set sizes, and selection states. Fixed scalar- ization thus leaves unresolved how much visual coverage is appropriate for the current input and subset size. The deeper issue is that query relevance and visual cov- erage do not play symmetric roles. Figure 1 illustrates this asymmetry through the maximum-overhang problem in block stacking (Paterson and Zwick 2009). Given a fixed number of blocks, the goal is to extend the stack toward a target without giving up the support needed to keep it stand- ing. Relevance-only placement pushes every block outward and achieves a long reach, but can leave the stack poorly sup- ported. Coverage-only placement keeps the blocks closely aligned and the stack well supported, but makes little useful progress. StackTok follows a different principle: pursue use- ful reach while treating support as a requirement calibrated to the number of blocks already placed. In visual-token se- lection, useful reach corresponds to query relevance, support corresponds to visual coverage, and the number of blocks cor- responds to the retained-token budget. This analogy suggests maximizing relevance while treating coverage as a budget- calibrated support requirement, rather than assigning the two signals a fixed exchange rate. Guided by this view, we introduce StackTok, a training- free selector that uses the visual coverage of the current subset to determine which signal guides the next selection. Stack- Tok first builds a size-indexed coverage reference curve from a coverage-only greedy sequence. It then uses the normalized entropy of query–vision affinities to adjust the support tar- get for each input. At each step, StackTok prioritizes query relevance when the current subset reaches this target, and visual coverage otherwise. Reassessing this state-dependent arXiv:2609.16841v1 [cs.CV] 15 Sep 2026 five blocks←→fixed token budgetuseful reach←→query relevancestack support←→visual coverage Relevance only long useful reach support falls short Coverage only short useful reach strong support, little useful reach StackTok useful reach useful reach with budget-calibrated support Figure 1:Block-stacking intuition for visual-token selection.All three configurations use the same number of blocks, corresponding to the same fixed token budget. Relevance-only placement pursues a long useful reach but can leave the stack without enough support. Coverage-only placement preserves strong support but makes little progress toward the target. StackTok pursues useful reach while using a budget-calibrated support requirement to determine when visual coverage should be prioritized. Useful reach and stack support correspond to query relevance and visual coverage, respectively. entropy of query–vision affinities to adjust the support tar- get for each input. At each step, StackTok prioritizes query relevance when the current subset reaches this target, and visual coverage otherwise. Reassessing this state-dependent decision after every addition yields a single interleaved se- quence whose priorities evolve with the input and selected subset. For high-resolution inputs, StackTok further allocates a shared token budget across crops according to their com- bined marginal gains. Our contributions are threefold: •We recast training-free visual-token selection as an asym- metric objective-and-support problem. Query relevance defines the objective, while a subset-size-indexed cover- age reference provides the visual support criterion instead of a fixed exchange rate between the two signals. •We introduce StackTok, a training-free selector that builds this reference from a coverage-only greedy sequence, cal- ibrates its strictness from query–vision affinity entropy, and uses the current subset to interleave relevance- and coverage-oriented additions under a fixed retention bud- get. •We extend StackTok to shared-budget multi-crop selec- tion. Across five VLMs, including LLaVA-NeXT-7B and LLaVA-NeXT-13B, ten distinct benchmarks, and three retention levels, StackTok ranks first among training-free selectors in every tested model–budget setting. Related Work Efficient Inference for Large Language and Multimodal Models Efficient LLM inference has been advanced by input/output (I/O)-aware attention kernels, memory-aware serving sys- tems, and context-management methods, which reduce com- putation or memory costs within the language backbone (Dao et al. 2022; Kwon et al. 2023; Xiao et al. 2024). VLMs intro- duce a complementary bottleneck by coupling this backbone with non-textual inputs (OpenAI 2023; Gemini Team 2023). High-resolution, multi-crop, and video inputs can produce hundreds or thousands of visual tokens that are processed to- gether with text (Liu et al. 2024a,b; Bai et al. 2025; Lin et al. 2024). Learned resampling and pooling modules reduce this visual input, but typically require training or architectural modification (Alayrac et al. 2022; Li, Wang, and Jia 2024; Yao et al. 2024). Training-free visual-token reduction instead shortens the input to a pretrained language backbone and is orthogonal to these model-level and system-level optimiza- tions. Visual Token Reduction for Vision-Language Models Token reduction has long been studied in vision transform- ers through importance-based pruning and similarity-based merging (Liang et al. 2022; Bolya et al. 2023). Training- free VLM methods adapt these ideas to reduce visual se- quences during inference. FastV prunes low-attention visual tokens in deeper LLM layers, whereas SparseVLM uses instruction-conditioned attention and adapts its layerwise sparsification ratio (Chen et al. 2024; Zhang et al. 2025). These attention-driven strategies prioritize evidence empha- sized by the model or query, but can underrepresent broader image context under tight budgets. VisionZip retains domi- nant tokens and merges contextual tokens, while DivPrune selects a max-min diverse subset (Yang et al. 2025; Alvar et al. 2025). Their dominance- and diversity-based criteria preserve representative or nonredundant visual content, but do not explicitly prioritize evidence requested by the cur- rent query. MMTok brings relevance and visual coverage to- gether through a submodular objective that covers both text and visual tokens with a fixed coefficient (Dong et al. 2026). This fixed scalarization applies the same relevance–coverage exchange rate at every selection state and retained-set size. StackTok instead keeps relevance as the objective and uses an entropy-adjusted, subset-size-indexed coverage reference to switch the active criterion within a single selection sequence. Method Overview and Problem Setup StackTok selects a fixed-size visual-token subset before LLM inference. Figure 2 visualizes the method as a token-stacking trajectory. Post-projector query and visual embeddings yield query–vision affinities, while pre-projector vision features yield vision–vision affinities. A coverage-only greedy curve Figure 1: Block-stacking intuition for visual-token selection. All three configurations use the same number of blocks, corresponding to the same fixed token budget. Relevance-only placement pursues a long useful reach but can leave the stack without enough support. Coverage-only placement preserves strong support but makes little progress toward the target. StackTok pursues useful reach while using a budget-calibrated support requirement to determine when visual coverage should be prioritized. Useful reach and stack support correspond to query relevance and visual coverage, respectively. decision after every addition yields a single interleaved se- quence whose priorities evolve with the input and selected subset. For high-resolution inputs, StackTok further allocates a shared token budget across crops according to their com- bined marginal gains. Our contributions are threefold: • We recast training-free visual-token selection as an asym- metric objective-and-support problem. Query relevance defines the objective, while a subset-size-indexed cover- age reference provides the visual support criterion instead of a fixed exchange rate between the two signals. • We introduce StackTok, a training-free selector that builds this reference from a coverage-only greedy sequence, cal- ibrates its strictness from query–vision affinity entropy, and uses the current subset to interleave relevance- and coverage-oriented additions under fixed retention budget. • We extend StackTok to shared-budget multi-crop selec- tion. Across five VLMs, ten distinct benchmarks, Stack- Tok ranks first among training-free selectors in every tested model–budget setting. Related Work Efficient Inference for Large Language and Multimodal Models Efficient LLM inference has been advanced by input/output (I/O)-aware attention kernels, memory-aware serving sys- tems, and context-management methods, which reduce com- putation or memory costs within the language backbone (Dao et al. 2022; Kwon et al. 2023; Xiao et al. 2024). VLMs intro- duce a complementary bottleneck by coupling this backbone with non-textual inputs (OpenAI 2023; Gemini Team 2023). High-resolution, multi-crop, and video inputs can produce hundreds or thousands of visual tokens that are processed to- gether with text (Liu et al. 2024a,b; Bai et al. 2025; Lin et al. 2024). Learned resampling and pooling modules reduce this visual input, but typically require training or architectural modification (Alayrac et al. 2022; Li, Wang, and Jia 2024; Yao et al. 2024). Training-free visual-token reduction instead shortens the input to a pretrained language backbone and is orthogonal to these model-level and system-level optimiza- tions. Visual Token Reduction for Vision-Language Models Token reduction has long been studied in vision transform- ers through importance-based pruning and similarity-based merging (Liang et al. 2022; Bolya et al. 2023). Training- free VLM methods adapt these ideas to reduce visual se- quences during inference. FastV prunes low-attention visual tokens in deeper LLM layers, whereas SparseVLM uses instruction-conditioned attention and adapts its layerwise sparsification ratio (Chen et al. 2024; Zhang et al. 2025). These attention-driven strategies prioritize evidence empha- sized by the model or query, but can underrepresent broader image context under tight budgets. VisionZip retains domi- nant tokens and merges contextual tokens, while DivPrune selects a max-min diverse subset (Yang et al. 2025; Alvar et al. 2025). Their dominance- and diversity-based criteria preserve representative or nonredundant visual content, but do not explicitly prioritize evidence requested by the cur- rent query. MMTok brings relevance and visual coverage to- gether through a submodular objective that covers both text and visual tokens with a fixed coefficient (Dong et al. 2026). This fixed scalarization applies the same relevance–coverage exchange rate at every selection state and retained-set size. StackTok instead keeps relevance as the objective and uses an entropy-adjusted, subset-size-indexed coverage reference to switch the active criterion within a single selection sequence. Method Overview and Problem Setup StackTok selects a fixed-size visual-token subset before LLM inference. Figure 2 visualizes the method as a token-stacking trajectory. Post-projector query and visual embeddings yield query–vision affinities, while pre-projector vision features yield vision–vision affinities. A coverage-only greedy curve provides a size-indexed coverage reference, and query–vision affinity entropy calibrates the corresponding support target. The current subset’s position relative to this target determines (a) Reference-gated interleaved selection query relevance∆ R visual coverage∆ C color=next primary criterion targetθ t =βC ref t current supportC(S t ) Positive support deficitd t >0 primary criterion:∆ C Zero support deficitd t = 0 primary criterion:∆ R t= 0t= 1t= 2t= 3 t=k−1 |S|=k StackTok: reference-gated interleaved selection vision features Q,Z vision–vision A v query–vision A qv one interleaved set S k ; the budget is always filled (b) Shared-budget allocation across crops each crop contributes one nominee at every allocation step 123 · K tot crop-local nominees one crop wins each allocation step Shared-budget allocation over crop-local nominees c ⋆ ∈arg max c h c ,h c = ∆ R c + ∆ C c crop1crop2 · cropL local gates useβ c ,C ref c,t ; no per-crop quotas support-preserving swap retained rows ofZ VLMs Figure 2:Overview of StackTok.(a) Each column depicts the candidates available at a retained-set size. The support deficit selects a coverage-oriented (∆ C ) or relevance-oriented (∆ R ) primary criterion for the next addition; teal and orange encode that criterion. The size-indexed target gates the primary criterion rather than constraining every prefix, and the coverage-only greedy sequence is used only to construct the reference curve. (b) For high-resolution inputs, crop-local gates nominate candidates and shared-budget allocation compares only those nominees. Faded dots and branches denote unchosen candidates. After the fixed budget is filled, optional support-preserving swap refinement and restoration of the original spatial order send the retained rows ofZto the LLM for inference. provides a size-indexed coverage reference, and query–vision affinity entropy calibrates the corresponding support target. The current subset’s position relative to this target determines whether relevance or visual coverage extends the trajectory next. For high-resolution inputs, crop-local nominees feed one shared-budget trajectory, followed by optional support- preserving swap refinement. We formalize these ingredients below. Let a VLM encode an image intonaligned visual to- kens, with[n] =1,...,n. We denote their pre-projector vision features byX= [x ⊤ 1 ;...;x ⊤ n ]∈R n×d v and the post-projector embeddings passed to the LLM byZ= [z ⊤ 1 ;...;z ⊤ n ]∈R n×d . After model-specific query prepro- cessing, the LLM input-embedding layer yieldsmquery- token embeddingsQ= [q ⊤ 1 ;...;q ⊤ m ]∈R m×d . The set U ⊆[n]contains indices eligible for retention and excludes padding positions when present; allnencoded positions re- main affinity targets in Eq. (1). Under the requested budget K, the goal is to retain exactlyk= minK,|U|tokens. Query Relevance and Visual Support We measure each signal in therepresentation suited toitsrole. Query relevance usesQandZin the shared LLM embedding space, whereas visual coverage usesX, which preserves the vision encoder’s geometry. Let ̄ u=u/max(∥u∥ 2 ,ε norm ) denoteℓ 2 normalization, whereε norm >0prevents division by zero. Row-wise softmax then gives A qv ij = exp( ̄ q ⊤ i ̄ z j /τ t ) P n ℓ=1 exp( ̄ q ⊤ i ̄ z ℓ /τ t ) , A v ij = exp( ̄ x ⊤ i ̄ x j /τ v ) P n ℓ=1 exp( ̄ x ⊤ i ̄ x ℓ /τ v ) , (1) whereτ t ,τ v >0control concentration. HereA qv ∈R m×n + maps query tokens to visual evidence, whileA v ∈R n×n + measures how well retained tokens represent the encoded image. Both are embedding affinities, not LLM attention weights. For any non-negative affinity matrixA∈R r×n + withr≥1 and anyS⊆[n], define the facility-location coverage c i (S;A) = max j∈S A ij , F A (S) = 1 r r X i=1 c i (S;A),(2) withc i (∅;A) = 0. The maximum assigns each target its best representative inS, and the mean normalizes the number of target rows. We instantiate R(S) =F A qv (S), C(S) =F A v (S),(3) as query relevance and visual coverage, withR(S) = 0when m= 0. Their exact marginal gains share one form: ∆ F A (s|S) =F A (S∪s)−F A (S) = 1 r r X i=1 [A is −c i (S;A)] + . (4) · · X Figure 2: Overview of StackTok. (a) Each column depicts the candidates available at a retained-set size. The support deficit selects a coverage-oriented (∆ C ) or relevance-oriented (∆ R ) primary criterion for the next addition; teal and orange encode that criterion. The size-indexed target gates the primary criterion rather than constraining every prefix, and the coverage-only greedy sequence is used only to construct the reference curve. (b) For high-resolution inputs, crop-local gates nominate candidates and shared-budget allocation compares only those nominees. Faded dots and branches denote unchosen candidates. After the fixed budget is filled, optional support-preserving swap refinement and restoration of the original spatial order send the retained rows of Z to the VLMs for inference. whether relevance or visual coverage extends the trajectory next. For high-resolution inputs, crop-local nominees feed one shared-budget trajectory, followed by optional support- preserving swap refinement. Let a VLM encode an image into n ≥ 1 aligned visual tokens. For a positive integer N, write [N ] = 1,...,N, with the convention [0] = ∅. We denote the tokens’ pre- projector vision features by X = [x ⊤ 1 ;... ; x ⊤ n ] ∈ R n×d v and the post-projector embeddings passed to the LLM by Z = [z ⊤ 1 ;... ; z ⊤ n ] ∈ R n×d . Here d v and d are the vision- feature and LLM-embedding dimensions, respectively. Af- ter model-specific query preprocessing, the LLM input- embedding layer yields m ≥ 0 query-token embeddings Q = [q ⊤ 1 ;... ; q ⊤ m ] ∈ R m×d . The set U ⊆ [n] contains indices eligible for retention and excludes padding positions when present; all n encoded positions remain affinity targets in Eq. (1). Given a non-negative integer budget K, the goal is to retain exactly k = minK,|U| tokens. Query Relevance and Visual Support We measure each signal in the representation suited to its role. Query relevance uses Q and Z in the shared LLM embedding space, whereas visual coverage uses X, which preserves the vision encoder’s geometry. Let ̄ u = u/ max(∥u∥ 2 ,ε norm ) denote ℓ 2 normalization, where ε norm > 0 prevents division by zero. Row-wise softmax then gives A qv ij = exp( ̄ q ⊤ i ̄ z j /τ t ) P n ℓ=1 exp( ̄ q ⊤ i ̄ z ℓ /τ t ) , A v ij = exp( ̄ x ⊤ i ̄ x j /τ v ) P n ℓ=1 exp( ̄ x ⊤ i ̄ x ℓ /τ v ) , (1) where the first line is indexed by i∈ [m] and j ∈ [n], and the second by i,j ∈ [n]; τ t ,τ v > 0 control concentration. Here A qv ∈ R m×n + maps query tokens to visual evidence, while A v ∈ R n×n + measures how well retained tokens represent the encoded image. Both are embedding affinities. For any non-negative affinity matrix A∈R p×q + with p,q ≥ 1 and any S ⊆ [q], define the facility-location coverage c i (S; A) = max j∈S A ij , F A (S) = 1 p p X i=1 c i (S; A), (2) withc i (∅; A) = 0. The maximum assigns each target its best representative in S, and the mean normalizes the number of target rows. We instantiate R(S) = F A qv (S), m>0, 0,m=0, C(S) = F A v (S), (3) as query relevance and visual coverage, respectively. For any S ⊆ [q] and s∈ [q]\ S, the exact marginal gain of F A is ∆ F A (s| S) = F A (S∪s)− F A (S) = 1 p p X i=1 [A is − c i (S; A)] + . (4) Here [x] + = maxx, 0. We denote the two instances by ∆ R and ∆ C . Throughout, visual coverage refers to the mea- surable quantity C, whereas visual support refers to the re- quirement that this quantity fulfills in the selection policy. Proposition 1 (Coverage Structure). For every A ≥ 0 with at least one row, F A is normalized, monotone, and submodular, and its marginal gain is given by Eq. (4). Thus R and C have diminishing returns and admit exact incremental greedy updates (Nemhauser, Wolsey, and Fisher 1978; Krause and Golovin 2014); when m = 0, R ≡ 0 has these properties trivially. The proof is in the supplementary appendix. Budget- and Input-Calibrated Visual Support A fixed objective R(S) + αC(S) with coefficient α ≥ 0 uses the same relevance–coverage exchange rate across in- puts, budgets, and selection states. StackTok instead derives a budget-specific coverage scale from a coverage-only greedy sequence initialized byG 0 = ∅. For t = 1,...,k, a t ∈ arg max s∈U t−1 ∆ C (s|G t−1 ), G t =G t−1 ∪a t , C ref t = C(G t ), (5) withC ref 0 = 0. StackTok discards the setsG t and retains only the achieved coverage reference curveC ref t k t=0 . Theorem 1 (Anytime Coverage Reference). Let OPT t = max S⊆U,|S|≤t C(S). For every 1≤ t≤ k, C ref t ≥ " 1− 1− 1 t t # OPT t ≥ (1−e −1 )OPT t . (6) Moreover,C ref t is nondecreasing and its incrementsC ref t − C ref t−1 are nonincreasing. Thus C ref t is an attained, near-optimal same-budget scale with a diminishing-return shape, not an upper bound. For every β ∈ [0, 1], the same coverage-greedy chain meets the support target βC ref t ; this witnesses same-budget target fea- sibility, not feasibility of StackTok’s interleaved prefixes. The proof is in the supplementary appendix. The coverage reference sets the budget scale; query–vision affinity determines how closely to track it. For m > 0 and n > 1, StackTok computes each row entropy H i for i∈ [m], its normalized mean ̄ H, and the support strictness β: H i =− n X j=1 A qv ij logA qv ij , ̄ H = 1 m logn m X i=1 H i , β = clip( ̄ H,β min ,β max ), (7) where the theoretical entropy uses the convention 0 log 0 = 0. In finite precision, δ > 0 is a numerical floor used only to evaluate the logarithm as log(maxA qv ij ,δ), preventing log 0 after underflow. Furthermore, 0 ≤ β min ≤ β max ≤ 1, and clip truncates its argument to this interval. Low entropy permits greater emphasis on localized evidence, whereas high entropy requests broader visual support. Since diffu- sion may also arise from weak localization or alignment, β calibrates the policy rather than classifying the query. When m = 0, we bypass entropy calibration, set β = β max for reference bookkeeping, and use visual coverage throughout. Otherwise, if n = 1, we set β = β min ; the single candi- date makes selection unique. For t ∈ 0,...,k, the size-t support target is θ t = βC ref t .(8) Reference-Gated Interleaved Selection Initialize S 0 = ∅. At each step t ∈ 0,...,k − 1, let S t ⊆ U, with |S t | = t, be the current retained set and let U t =U t be the remaining candidates. The support deficit is d t = [θ t − C(S t )] + .(9) For a nonempty query, zero deficit activates relevance and positive deficit activates visual coverage: (g pri t ,g sec t ) = (∆ R , ∆ C ), d t = 0, (∆ C , ∆ R ), d t > 0. (10) StackTok uses the primary criterion while it has positive gain and otherwise falls back to the secondary one. Let M pri t = max u∈U t g pri t (u| S t ). Then ψ t (s) = ( g pri t (s| S t ), M pri t > 0, g sec t (s| S t ), otherwise, s t+1 ∈ arg max s∈U t ψ t (s). (11) We then set S t+1 = S t ∪ s t+1 . When m = 0, the coverage-oriented branch overrides Eq. (10). Deterministic tie-breaking fills the budget if both criteria saturate. For any s ∈ U t and fixed θ t , adding s repairs the current deficit by exactly d t − [θ t − C(S t ∪s)] + = mind t , ∆ C (s| S t ), (12) so the coverage-oriented branch maximizes one-step repair. Because the target advances to θ t+1 after selection, this local result does not certify the new prefix. Also, θ 0 = C(∅) = 0, so a nonempty query activates relevance as the primary criterion at the first step, subject to the zero-gain fallback in Eq. (11). Algorithm 1 instantiates the single-image trajectory in Fig- ure 2(a). Updating both coverages lets the gate switch repeat- edly; sorting the final indices preserves the spatial order of the retained rows of Z. Shared-Budget Allocation across Crops Figure 2(b) visualizes the high-resolution extension. With L ≥ 1 crops indexed by c ∈ [L], fixed per-crop quotas can waste tokens on uninformative regions. Crop c contains n c ≥ 1 encoded positions and a selectable set U c ⊆ [n c ]. The effective shared budget and crop-c reference horizon are K tot = minK, P L c=1 |U c | and r max c = minK tot ,|U c |, respectively. Applying Eq. (1) within the crop gives A qv c ∈ R m×n c + and A v c ∈ R n c ×n c + . We define C c = F A v c and, when m > 0, R c = F A qv c ; when m = 0, R c ≡ 0. Write ∆ R c and ∆ C c for their marginal gains. Each crop con- structs C ref c,t r max c t=0 and β c from Eqs. (5) and (7), replacing (A qv , A v ,U,n,k) by (A qv c , A v c ,U c ,n c ,r max c ). The same Algorithm 1: Reference-gated interleaved selection (single image) Input: affinitiesA qv ,A v ; selectable setU; budget K; strictness clipping range [β min ,β max ] Output: retained index set S 1: k ← minK,|U|; S 0 ← ∅▷ fixed-budget state 2: computeC ref t k t=0 and β▷ budget/input calibration 3: for t = 0 to k− 1 do 4: d t ← [βC ref t − C(S t )] + ▷ support feedback 5: set (g pri t ,g sec t ) by Eq. (10); use (∆ C , ∆ R ) if m = 0 ▷ rele- vance / coverage 6: s t+1 ← arg max s∈U t ψ t (s)▷ fallback in ψ t 7: S t+1 ← S t ∪s t+1 ; update R and C ▷ close feedback loop 8: end for 9: return sort(S k )▷ restore spatial order edge-case conventions apply:β c = β max whenm = 0, while β c = β min when m > 0 and n c = 1. For t∈0,...,r max c , define the local support target θ c,t = β c C ref c,t . Initialize S c = ∅ for every crop. At a shared-budget step, let r c = |S c | and define the active-crop set I = c ∈ [L] : U c \ S c ̸= ∅. Crop c has support deficit d c,r c = [θ c,r c − C c (S c )] + . Applying the gate and zero- primary-gain fallback in Eqs. (10)–(11) to S c ,U c c , d c,r c , ∆ R c , and ∆ C c defines the crop-local score ψ c,r c . As in the single-image case, m = 0 forces the coverage-oriented branch. Each c∈I then nominates s ⋆ c ∈ arg max s∈U c c ψ c,r c (s), h c = ∆ R c (s ⋆ c | S c ) + ∆ C c (s ⋆ c | S c ). (13) The allocator spends the K tot slots by repeatedly choosing c ⋆ ∈ arg max c∈I h c , S c ⋆ ← S c ⋆ ∪s ⋆ c ⋆ . (14) The local gate determines each nominee, while h c compares nominees across crops. Only the winning crop changes, so other nominations are cached. Cross-crop allocation delib- erately uses ∆ R c + ∆ C c ; criterion separation applies to the local gate. Algorithm 2 makes these two levels explicit. All local and cross-crop maximizations use deterministic tie- breaking, and zero-gain nominees remain eligible so that the effective shared budget is filled. Support-Preserving Swap Refinement Greedy additions cannot revise early choices. LetU loc , R loc , C loc , β loc , and k loc denote the quantities of the unit being refined. For a single image, (U loc ,R loc ,C loc ,β loc ,k loc ) = (U,R,C,β,k) and C ref loc,t = C ref t for 0 ≤ t ≤ k. For crop c, they are (U c ,R c ,C c ,β c ,r max c ) and C ref loc,t = C ref c,t for 0≤ t ≤ r max c . Given a retained set S ⊂ U loc with 0 < r = |S| ≤ k loc and r < |U loc |, StackTok optionally performs cardinality-preserving one-exchange refinement. It evaluates replacements S ′ = S \ u ∪ v with u ∈ S and v ∈ U loc . DefineJ loc (S) = R loc (S)+C loc (S). A replacement Algorithm 2: Shared-budget allocation across crops Input: per-crop affinitiesA qv c ,A v c L c=1 ; selectable setsU c L c=1 ; shared budget K; strictness clipping range [β min ,β max ] Output: allocated index setsS c L c=1 1: K tot ← minK, P c |U c |▷ effective budget 2: S c ← ∅ for all c;I ←c :U c ̸= ∅▷ active crops 3: for c∈I do 4: r max c ← minK tot ,|U c |▷ local reference horizon 5: computeC ref c,t r max c t=0 and β c ▷ local calibration 6: cache (s ⋆ c ,h c ) by Eq. (13)▷ relevance / coverage 7: end for 8: for b = 1 to K tot do 9: c ⋆ ← arg max c∈I h c ▷ compare only nominees 10: S c ⋆ ← S c ⋆ ∪s ⋆ c ⋆ ; update R c ⋆ and C c ⋆ ▷ update winner only 11: ifU c ⋆ \ S c ⋆ = ∅ then 12: I ←I\c ⋆ ▷ crop exhausted 13: else 14:refresh (s ⋆ c ⋆ ,h c ⋆ ) by Eq. (13)▷ cache other nominees 15: end if 16: end for 17: returnsort(S c ) L c=1 ▷ restore within-crop order is accepted only if J loc (S ′ ) > (1 + ε sw )J loc (S), C loc (S ′ )≥ ℓ r (S) := minβ loc C ref loc,r ,C loc (S). (15) Here ε sw ≥ 0 is the minimum relative improvement. Be- low target, the floor prevents support loss; above target, it permits a decrease only down to the target. Each accepted replacement preserves r and strictly increases J loc . Because the family of size-r subsets is finite, repeated accepted re- placements must terminate. Per-row top-two affinities make deletion scores exact without recomputing coverage; in prac- tice, refinement stops after a fixed number of passes or a full pass without an accepted swap. Complexity and Practical Details Affinity construction costsO(n 2 d v +mnd) time andO(n 2 + mn) memory. For u = |U|, incremental row maxima make the reference and interleaved passes cost O(ku(n + m)), or O(kn 2 ) when u,m ≤ n. For refinement, let u loc = |U loc | and let n loc = n for a single image or n loc = n c for crop c; one complete swap pass then costsO(r(u loc −r)(m+n loc )). Multi-crop costs sum over crops, with cached unchanged nominations. Without query embeddings, StackTok uses vi- sual coverage throughout. It excludes padding from selection, does not stop early, and returns the effective fixed budget. Experiments Experimental Setup Datasets, models, and metrics. The evaluation covers ten distinct image-understanding benchmarks. The LLaVA suite contains GQA (Hudson and Manning 2019), MMBench (MMB) (Liu et al. 2024c), MME (Fu et al. 2023), POPE (Li et al. 2023b), ScienceQA-IMG (SQA) (Lu et al. 2022), VQA v2 (Goyal et al. 2017), VQA Text (Singh et al. 2019), MMMU (Yue et al. 2024), and SEEDBench (SEED) (Li et al. MethodGQA↑MMB↑MME↑POPE↑SQA↑VQA v2 ↑VQA Text ↑MMMU↑SEED↑Avg.↑ Vanilla (576)61.9564.181861.4885.8769.5177.7158.1536.2258.55100.00% Retain 192 (↓ 67%) FastV52.74 60.71 1611.55 64.78 67.31 66.4252.4534.2257.05 89.57% SparseVLM57.65 62.00 1720.52 83.57 69.11 74.8456.0533.7355.75 95.54% VisionZip59.35 62.49 1782.10 85.27 68.91 76.0357.2536.5256.35 97.86% DivPrune60.02 62.04 1761.74 86.97 68.67 76.1056.9235.3658.66 97.99% VisionZip ‡ 60.15 62.89 1833.49 84.87 68.21 76.6257.7536.1257.05 98.40% MMTok60.12 62.89 1773.36 86.39 68.77 76.3357.6336.2559.16 98.70% StackTok (ours)60.3263.771768.8486.7069.3776.5457.4936.2259.1698.99% Retain 128 (↓ 78%) FastV49.64 55.65 1489.58 59.58 60.21 61.1850.5634.8255.85 84.45% SparseVLM56.05 59.52 1695.53 80.47 67.11 73.0654.8533.7353.35 93.02% VisionZip57.65 61.50 1761.21 83.17 68.91 74.8456.7537.8254.85 96.83% DivPrune59.30 61.53 1717.74 86.69 68.67 75.2056.0135.4856.93 96.88% VisionZip ‡ 58.95 62.10 1822.49 83.67 68.31 75.8356.9537.2255.75 97.67% MMTok59.34 61.79 1778.64 86.22 68.83 75.5856.9835.5958.54 97.84% StackTok (ours)59.5262.801761.1586.4769.3175.5956.8435.5658.6098.03% Retain 64 (↓ 89%) FastV46.14 47.61 1255.65 47.98 51.11 54.4547.7633.9351.86 75.55% SparseVLM52.74 55.75 1504.58 75.07 62.21 67.5151.7632.6351.06 86.99% VisionZip55.14 59.62 1689.53 76.97 69.01 71.6755.4536.1252.16 93.11% DivPrune57.83 58.80 1673.93 85.53 68.08 73.3654.6435.4855.08 94.76% VisionZip ‡ 57.05 61.01 1755.51 80.87 68.81 73.4555.9535.5253.35 94.95% MMTok58.34 60.68 1714.85 85.74 69.17 74.4455.9636.0357.10 96.58% StackTok (ours)58.4261.251702.4785.8969.6574.4455.8536.0056.9996.66% Table 1: Performance on LLaVA-1.5-7B over nine benchmarks; Avg. is the mean relative retention with respect to the 576-token Vanilla row and is recomputed from the displayed values after rounding.‡ denotes the fine-tuned variant. Variant19212864 (a) Final-budget target (C ref t → C ref k ) 98.70 97.58 96.05 (b) Fixed-strictness control (β = 0.5) 98.88 97.92 96.54 (c) Relevance only (ψ t = ∆ R )98.10 96.75 94.20 (d) Coverage only (ψ t = ∆ C )98.15 96.95 94.55 StackTok (full)98.9998.0396.66 Table 2: Ablations of the size-indexed coverage reference, entropy calibration, and active criterion on LLaVA-1.5-7B (average retained performance, %). 2023a). We evaluate LLaVA-1.5-7B/13B and LLaVA-NeXT- 7B/13B (Liu et al. 2024a,b) using the lmms-eval frame- work (Li et al. 2024). Tables 1 and 3 report the average relative retention across the applicable datasets, computed as each pruned score divided by its corresponding full-token score. We additionally evaluate Qwen2.5-VL-7B (Bai et al. 2025) on GQA, MMB, MME, POPE, SQA, VQA Text , and OCRBench (Liu et al. 2024d). Due to space constraints, the Qwen2.5-VL-7B experiments are presented in the supple- mentary appendix. For these experiments, Avg. † averages rel- ative retention over GQA, MMB, MME, POPE, and VQA Text , while SQA and OCRBench are excluded from the aggregate and reported separately. Extended ablations, implementation details, and limitations are also provided in the appendix. Baselines and budgets. We compare with the training-free token-reduction methods FastV (Chen et al. 2024), Sparse- VLM (Zhang et al. 2025), VisionZip (Yang et al. 2025), Di- vPrune (Alvar et al. 2025), and MMTok (Dong et al. 2026). VisionZip ‡ denotes its fine-tuned variant and is included only as an additional reference; it is excluded when iden- tifying the strongest training-free baseline. For LLaVA-1.5, we retain 192/128/64 of the original 576 visual tokens. For LLaVA-NeXT, we apply a shared budget of 640/320/160 vi- sual tokens across all crops of an input. For the Qwen2.5-VL- 7B experiments in the appendix, we retain 20%/10%/5% of the visual tokens produced by dynamic-resolution encoder. Main Results Cross-model comparison. Table 1 gives the full LLaVA- 1.5-7B comparison, where StackTok exceeds the strongest training-free baseline by 0.29, 0.19, and 0.08 points at 192, 128, and 64 tokens. Table 3 extends this comparison to four LLaVA models: StackTok ranks first in all 12 model–budget settings, with gains of 0.08–0.29 points. The consistent or- dering across 7B/13B scales and fixed-resolution/multi-crop inputs suggests that the gain is not tied to one model size or image encoding regime; Figure 3(a) visualizes this pattern. At the tightest 64-token budget, the largest gains over M- Tok occur on MMB and SQA. This pattern may arise because these question-driven benchmarks reward concentrating the tight budget on query-aligned evidence, while the coverage gate preserves complementary visual support. High-resolution performance. The high-resolution LLaVA-NeXT-7B setting retains at most 2,880 visual tokens before selection. StackTok preserves 98.97%, 97.51%, and 95.26% of full-token performance with shared budgets of 640, 320, and 160 tokens, corresponding to only 22.2%, 11.1%, and 5.6% of the original sequence. The modest degradation after removing 94.4% of the tokens suggests that 90 94 98 100 192 128 64 192 128 64 640 320 160 640 320 160 96.66 96.54 95.26 95.21 (a) VisionZip DivPrune MMTok StackTok −0.50.00.51.0 64-token Δ retention vs. MMTok MME VQA Text SEED MMMU VQA v2 GQA POPE SQA MMB -0.67 -0.19 -0.19 -0.08 +0.00 +0.13 +0.17 +0.69 +0.89 gain |Δ| ≤ 0.10 loss Retain 20% Retain 10% Retain 5% 80 85 90 95 100 Retained performance (%) Full tokens 100.00% 5% tokens 80.00% -4.21 -5.99 -9.80 95.79 89.80 Figure 3: Complementary views of the main results. (a) Dataset-averaged retained performance for four training-free methods, reported separately for each LLaVA model and tested budget in Table 2; the radial axis is truncated to 89–101%, and the four annotations mark StackTok at each model’s tightest budget. (b) Per-benchmark StackTok-minus-MMTok difference on LLaVA- 1.5-7B at the tightest 64-token budget (11.1% of 576), after normalizing each displayed score by its Vanilla score in Table 1. The near-zero category, defined by|∆| ≤0.10percentage points, is a visualization rule rather than a statistical-significance threshold. (c) Successive changes in StackTok Avg. † as the Qwen2.5-VL-7B retention ratio tightens in Table 3. Avg. † covers GQA, MMB, MME, POPE, and VQA Text ; the floating bars describe adjacent-budget changes rather than causal contributions. LLaVA models.Across the 12 model–budget settings in Table 2, StackTok improves over the strongest training- free baseline, MMTok, by 0.08–0.29 percentage points in dataset-averaged retained performance at each fixed bud- get. On LLaVA-1.5-7B (Table 1), the gains are 0.29, 0.19, and 0.08 points at 192, 128, and 64 tokens, respectively. Figure 3(a) shows that the advantage persists across both single-image and multi-crop models. Panel (b) resolves the tightest 64-token result by benchmark after Vanilla normal- ization: the largest gains occur on MMB and SQA, whereas MME, VQA Text , and SEED exhibit regressions. Thus, the aggregate result at a fixed budget does not imply uniform per-benchmark dominance. High-resolution LLaVA-NeXT.On LLaVA-NeXT-7B, StackTok retains 98.97%, 97.51%, and 95.26% of full-token performance at 640, 320, and 160 tokens, exceeding MMTok by 0.19, 0.19, and 0.08 percentage points, respectively. These budgets retain 22.2%, 11.1%, and 5.6% of the 2,880 visual tokens. On LLaVA-NeXT-13B, StackTok obtains 98.53%, 96.68%, and 95.21%, improving over MMTok by 0.26, 0.19, and 0.08 points. Table 6 further isolates the contribution of dynamic shared-budget allocation on LLaVA-NeXT-7B. Dynamic-resolution Qwen2.5-VL-7B.Table 3 presents a stricter setting in which the backbone already reduces visual tokens through dynamic resolution. StackTok improves Avg. † over MMTok by 1.21, 1.28, and 1.02 points when retaining 20%, 10%, and 5% of the visual tokens, respectively. These gains show that reference-gated selection remains useful after the model’s native visual-token compression. Figure 3(c) further shows that the successive retained-performance loss grows as the budget tightens, with the 5% setting retaining 80.00% of full-token Avg. † . Ablation Study We ablate StackTok on LLaVA-1.5-7B (single image) and LLaVA-NeXT-7B (multi-crop), reporting the average re- tained performance. Reference-gated policy versus fixed scalarization.Table 4 compares StackTok withR(S)+αC(S), tuningαseparately at each budget to give the fixed scalarization its strongest setting. This directly tests whether state-dependent tracking of the support target in Eqs. (8)–(10) adds value beyond choosing a better fixed relevance–coverage exchange rate. The reference-gated policy improves the best fixed scalariza- tion by 0.14, 0.10, and 0.06 percentage points at 192, 128, and 64 tokens, respectively. Reference and gate components.Table 5 isolates the mech- anisms defined in Method. The final-budget-target variant re- places the size-indexedC ref t byC ref k at every step; the fixed- strictness control replaces the entropy-calibratedβby0.5. Relevance-only and coverage-only selection setψ t = ∆ R andψ t = ∆ C , respectively, exposing the two one-signal extremes that the reference-gated policy interleaves. Replac- ing the size-indexed target incurs losses of 0.29, 0.45, and 0.61 percentage points as the budget tightens, whereas fixed strictness causes a smaller but consistent 0.11–0.12-point loss. Both one-signal variants degrade most at 64 tokens, supporting the need to adaptively interleave the two criteria. Shared-budget allocation across crops.Table 6 isolates the high-resolution extension in Eq. (14). Uniform fixed quo- tas divide the budget equally across nonempty crops, while initial-h c -proportional quotas allocate it once in proportion to the initial nominee scores. Both static alternatives use the same crop-local reference-gated selector as StackTok, so the comparison isolates dynamic shared-budget allocation. Dynamic allocation exceeds uniform quotas by 0.42, 0.56, (b)(c) Figure 3: Complementary views of the main results. (a) Dataset-averaged retained performance for four training-free methods, reported separately for each LLaVA model and tested budget in Table 3; the radial axis is truncated to 89–101%, and the four annotations mark StackTok at each model’s tightest budget. (b) Per-benchmark StackTok-minus-MMTok difference on LLaVA- 1.5-7B at the tightest 64-token budget (11.1% of 576), after normalizing each displayed score by its Vanilla score in Table 1. The near-zero category, defined by |∆| ≤ 0.10 percentage points, is a visualization rule rather than a statistical-significance threshold. (c) Successive changes in StackTok Avg. † as the Qwen2.5-VL-7B retention ratio tightens in Table A1. Avg. † covers GQA, MMB, MME, POPE, and VQA Text ; the floating bars describe adjacent-budget changes rather than causal contributions. MethodLLaVA-1.5-7BLLaVA-1.5-13BLLaVA-NeXT-7BLLaVA-NeXT-13B 192/128/64192/128/64640/320/160640/320/160 VisionZip97.86 / 96.83 / 93.11 97.94 / 97.06 / 93.72 97.56 / 94.53 / 90.47 97.72 / 94.78 / 91.45 DivPrune97.99 / 96.88 / 94.76 98.24 / 96.97 / 95.36 97.18 / 95.14 / 92.43 97.16 / 94.59 / 92.05 VisionZip ‡ 98.40 / 97.67 / 94.95 98.76 / 97.48 / 94.83 98.95 / 97.64 / 95.07 98.82 / 97.86 / 94.69 MMTok98.70 / 97.84 / 96.58 98.75 / 97.53 / 96.46 98.78 / 97.32 / 95.18 98.27 / 96.49 / 95.13 StackTok (ours)98.99 / 98.03 / 96.6698.96 / 97.72 / 96.5498.97 / 97.51 / 95.2698.53 / 96.68 / 95.21 Table 3: Dataset-averaged retained performance (%) for four LLaVA models, reported separately at each of three budgets. The LLaVA-1.5-7B column is aligned with Table 1. crop-local nominations preserve support within each crop while the allocator redirects slots away from low-gain crops. LLaVA-NeXT-13B follows the same ranking, reaching 98.53%, 96.68%, and 95.21%, which indicates that the behavior persists across model scales. Dynamic-resolution transfer. Figure 3(c) provides a com- plementary view on Qwen2.5-VL-7B: Avg. † decreases from 95.79% to 89.80% and 80.00% as retention halves from 20% to 10% and 5%. The larger 9.80-point second drop suggests that visual redundancy becomes substantially scarcer below 10% retention; detailed results are provided in the appendix. Task-level behavior. Figure 3(b) also exposes the boundary of the aggregate gain: at 64 tokens, StackTok trails M- Tok on MME, VQA Text , and SEED. These tasks can depend on dispersed scene cues or fine-grained text; under extreme compression, such evidence may receive weak individual relevance before its joint value becomes apparent. A better average at a fixed budget therefore does not imply uniform per-benchmark dominance. Component ablation Table 2 isolates the three decisions central to StackTok. The deficit from replacing the size-indexed reference with the final-budget target grows from 0.29 to 0.61 points as the bud- get tightens. This widening gap indicates that an endpoint- only target over-constrains early prefixes, forcing scarce slots toward coverage before enough query-relevant evidence has been collected. Fixed strictness yields a smaller but consis- tent 0.11–0.12-point loss because one global β cannot adapt the support requirement to input ambiguity. The one-signal variants expose the complementary failure modes more di- rectly: relevance alone can select redundant query-aligned evidence, whereas coverage alone can preserve diverse yet task-irrelevant regions. Their larger losses at 64 tokens there- fore support using the support-deficit gate to switch between the two criteria. Conclusion Visual-token selection under tight budgets is not simply a matter of maximizing a fixed combination of importance sig- nals: query relevance and visual coverage play asymmetric, state-dependent roles. We introduced StackTok, which pur- sues query-relevant evidence while treating visual coverage as budget-calibrated support. A size-indexed coverage refer- ence and input-adaptive strictness determine which criterion guides each selection step, while crop-local nominations ex- tend the same principle to shared-budget high-resolution in- puts. StackTok provides a training-free framework in which selection priorities adapt to the input and the evolving re- tained set rather than remaining fixed throughout pruning. References Alayrac, J.-B.; Donahue, J.; Luc, P.; Miech, A.; et al. 2022. Flamingo: a Visual Language Model for Few-Shot Learning. In NeurIPS. Alvar, S. R.; Singh, G.; Akbari, M.; and Zhang, Y. 2025. DivPrune: Diversity-based Visual Token Pruning for Large Multimodal Models. In CVPR. Bai, S.; et al. 2025. Qwen2.5-VL Technical Report. arXiv:2502.13923. Bolya, D.; Fu, C.-Y.; Dai, X.; Zhang, P.; Feichtenhofer, C.; and Hoffman, J. 2023. Token Merging: Your ViT but Faster. In ICLR. Chen, L.; Zhao, H.; Liu, T.; Bai, S.; Lin, J.; Zhou, C.; and Chang, B. 2024. An Image is Worth 1/2 Tokens After Layer 2: Plug-and-Play Acceleration for VLLM Inference. In ECCV. Dao, T.; Fu, D. Y.; Ermon, S.; Rudra, A.; and Ré, C. 2022. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. In NeurIPS. Dong, S.; Hu, J.; Zhang, M.; Yin, M.; Fu, Y.; and Qian, Q. 2026. MMTok: Multimodal Coverage Maximization for Efficient Inference of VLMs. In ICLR. Fu, C.; Chen, P.; Shen, Y.; et al. 2023. MME: A Comprehen- sive Evaluation Benchmark for Multimodal Large Language Models. arXiv preprint arXiv:2306.13394. Gemini Team. 2023. Gemini: A Family of Highly Capable Multimodal Models. arXiv:2312.11805. Goyal, Y.; Khot, T.; Summers-Stay, D.; Batra, D.; and Parikh, D. 2017. Making the V in VQA Matter: Elevating the Role of Image Understanding in Visual Question Answering. In CVPR. Hudson, D. A.; and Manning, C. D. 2019. GQA: A New Dataset for Real-World Visual Reasoning and Compositional Question Answering. In CVPR. Krause, A.; and Golovin, D. 2014. Submodular Function Maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press. Kwon, W.; Li, Z.; Zhuang, S.; Sheng, Y.; Zheng, L.; Yu, C. H.; Gonzalez, J. E.; Zhang, H.; and Stoica, I. 2023. Efficient Memory Management for Large Language Model Serving with PagedAttention. In SOSP. Li, B.; Wang, R.; Wang, G.; Ge, Y.; Ge, Y.; and Shan, Y. 2023a. SEED-Bench: Benchmarking Multimodal LLMs with Generative Comprehension. arXiv preprint arXiv:2307.16125. Li, B.; Zhang, P.; Zhang, K.; et al. 2024. LMMs-Eval: Accelerating the Development of Large Multimodal Mod- els. https://github.com/EvolvingLMMs-Lab/lmms-eval. Ac- cessed: 2026-06-29. Li, Y.; Du, Y.; Zhou, K.; Wang, J.; Zhao, W. X.; and Wen, J.- R. 2023b. Evaluating Object Hallucination in Large Vision- Language Models. In EMNLP. Li, Y.; Wang, C.; and Jia, J. 2024. LLaMA-VID: An Image is Worth 2 Tokens in Large Language Models. In ECCV. Liang, Y.; Ge, C.; Tong, Z.; Song, Y.; Wang, J.; and Xie, P. 2022. Not All Patches are What You Need: Expediting Vision Transformers via Token Reorganizations. In ICLR. Lin, B.; Zhu, B.; Ye, Y.; Ning, M.; Jin, P.; and Yuan, L. 2024. Video-LLaVA: Learning United Visual Representation by Alignment Before Projection. arXiv:2311.10122. Liu, H.; Li, C.; Li, Y.; and Lee, Y. J. 2024a. Improved Baselines with Visual Instruction Tuning. In CVPR. Liu, H.; Li, C.; Li, Y.; Li, B.; Zhang, Y.; Shen, S.; and Lee, Y. J. 2024b. LLaVA-NeXT: Improved Reasoning, OCR, and World Knowledge. https://llava-vl.github.io/blog/2024-01- 30-llava-next/. Accessed: 2026-06-29. Liu, Y.; Duan, H.; Zhang, Y.; Li, B.; Zhang, S.; Zhao, W.; Yuan, Y.; Wang, J.; He, C.; Liu, Z.; et al. 2024c. MMBench: Is Your Multi-modal Model an All-around Player? In ECCV. Liu, Y.; Li, Z.; Huang, M.; Yang, B.; Yu, W.; Li, C.; Yin, X.-C.; Liu, C.-L.; Jin, L.; and Bai, X. 2024d. OCRBench: On the Hidden Mystery of OCR in Large Multimodal Models. Science China Information Sciences, 67(12): 220102. Lu, P.; Mishra, S.; Xia, T.; Qiu, L.; Chang, K.-W.; Zhu, S.-C.; Tafjord, O.; Clark, P.; and Kalyan, A. 2022. Learn to Explain: Multimodal Reasoning via Thought Chains for Science Question Answering. In NeurIPS. Nemhauser, G. L.; Wolsey, L. A.; and Fisher, M. L. 1978. An Analysis of Approximations for Maximizing Submodular Set Functions—I. Mathematical Programming, 14(1): 265–294. OpenAI. 2023. GPT-4 Technical Report. arXiv:2303.08774. Paterson, M.; and Zwick, U. 2009. Overhang. The American Mathematical Monthly, 116(1): 19–44. Singh, A.; Natarajan, V.; Shah, M.; Jiang, Y.; Chen, X.; Ba- tra, D.; Parikh, D.; and Rohrbach, M. 2019. Towards VQA Models That Can Read. In CVPR. Xiao, G.; Tian, Y.; Chen, B.; Han, S.; and Lewis, M. 2024. Efficient Streaming Language Models with Attention Sinks. In ICLR. Yang, S.; Chen, Y.; Tian, Z.; Wang, C.; Li, J.; Yu, B.; and Jia, J. 2025. VisionZip: Longer is Better but Not Necessary in Vision Language Models. In CVPR. Yao, L.; Li, L.; Ren, S.; Wang, L.; Liu, Y.; Sun, X.; and Hou, L. 2024. DeCo: Decoupling Token Compression from Se- mantic Abstraction in Multimodal Large Language Models. In arXiv preprint arXiv:2405.20985. Yue, X.; Ni, Y.; Zhang, K.; et al. 2024. MMMU: A Massive Multi-discipline Multimodal Understanding and Reasoning Benchmark for Expert AGI. In CVPR. Zhang, Y.; Fan, C.-K.; Ma, J.; Zheng, W.; Huang, T.; Cheng, K.; Gudovskiy, D.; Okuno, T.; Nakata, Y.; Keutzer, K.; and Zhang, S. 2025. SparseVLM: Visual Token Sparsification for Efficient Vision-Language Model Inference. In ICML. Supplementary Material for StackTok: Accelerating VLMs Inference with Budget-Adaptive Visual Token Selection Appendix Overview This appendix complements the main paper with complete proofs and additional experimental evidence. It first proves Proposition 1 and Theorem 1, then provides implementation details, dynamic-resolution results on Qwen2.5-VL-7B, and extended ablations of fixed scalarization, shared-budget crop allocation, support-preserving swap refinement, and strict- ness sensitivity. Proofs Proof of Proposition 1 (Coverage Structure) For completeness, recall that for a non-negative affinity ma- trix A∈ R p×q + with p,q ≥ 1, c i (S; A) = max j∈S A ij , c i (∅; A) = 0, F A (S) = 1 p p X i=1 c i (S; A). Proposition 1 (Coverage Structure, Restated). F A is normalized, monotone, and submodular. Moreover, for every S ⊆ [q] and s∈ [q]\ S, ∆ F A (s| S) = 1 p p X i=1 [A is − c i (S; A)] + . Proof. We establish the four claims separately. First, the empty-set convention above gives F A (∅) = 0, so the func- tion is normalized. Next, if S ⊆ T, then every index avail- able in the maximum defining c i (S; A) is also available for c i (T ; A). Hence c i (S; A)≤ c i (T ; A) for every i, including S = ∅ because A is non-negative. Averaging over rows yields F A (S)≤ F A (T ) and proves monotonicity. For any candidate s /∈ S, adding s changes the coverage of row i by c i (S∪s; A)− c i (S; A) = maxc i (S; A),A is − c i (S; A) = [A is − c i (S; A)] + . Averaging this row-wise identity gives the stated marginal- gain formula. Finally, let S ⊆ T and s /∈ T. The monotonicity just proved gives c i (S; A)≤ c i (T ; A), while x7→ [A is −x] + is nonincreasing. Therefore [A is − c i (S; A)] + ≥ [A is − c i (T ; A)] + . Summing this inequality over rows and invoking the stated marginal-gain formula yields ∆ F A (s | S) ≥ ∆ F A (s | T ). This is the diminishing-returns characterization of submod- ularity on the finite ground set. Proof of Theorem 1 (Anytime Coverage Reference) Let C = F A v and consider the coverage-greedy chain G i k i=0 in Eq. (5). Restricting C to 2 U preserves normaliza- tion, monotonicity, and submodularity. Moreover, because k ≤ |U|, the candidate set is nonempty at every greedy step 0≤ i < k. Theorem 1 (Anytime Coverage Reference, Re- stated). Let OPT t = max S⊆U,|S|≤t C(S). For every 1 ≤ t≤ k, C ref t ≥ " 1− 1− 1 t t # OPT t ≥ (1− e −1 )OPT t . Furthermore, C ref t is nondecreasing and its increments are nonincreasing. Proof. For every 0 ≤ i < k, define the gain of the next greedy step by η i+1 = C(G i+1 )− C(G i ) = max s∈U i ∆ C (s|G i ). Fix any t ∈ 1,...,k, and let S ⋆ t attain OPT t ; such a set exists becauseU is finite. For each 0≤ i < t, monotonicity first allows us to adjoinG i to an optimal set. Submodularity then bounds the joint gain by the sum of singleton marginal gains evaluated atG i : OPT t − C(G i ) = C(S ⋆ t )− C(G i ) ≤ C(G i ∪ S ⋆ t )− C(G i ) ≤ X s∈S ⋆ t i ∆ C (s|G i ) ≤|S ⋆ t i |η i+1 ≤ tη i+1 . The second inequality can be seen by adding the elements of S ⋆ t \ G i one at a time: diminishing returns makes the actual marginal at each enlarged intermediate set no greater than its marginal atG i . The next inequality follows from the definition of η i+1 above. Define the same-budget optimality gap Γ (t) i = OPT t − C(G i ). Since |G i | = i ≤ t, every G i considered above is feasible for OPT t , so Γ (t) i ≥ 0. Combining the preceding bound with Γ (t) i+1 = Γ (t) i − η i+1 gives the contraction Γ (t) i+1 ≤ 1− 1 t Γ (t) i . Because C(G 0 ) = 0, we have Γ (t) 0 = OPT t . Iterating this contraction for i = 0,...,t− 1 yields OPT t − C(G t )≤ 1− 1 t t OPT t , which gives the first claimed inequality because C(G t ) = C ref t . For t > 1, the elementary bound log(1− x) ≤ −x MethodGQA↑MMB↑MME↑POPE↑VQA Text ↑SQA↑OCRBench↑Avg. † ↑ Vanilla60.4883.25232786.1677.7287.4683.80100.00% Retain 20% VisionZip56.80 80.33217483.3870.4384.2359.5094.25% DivPrune56.70 76.98216380.5965.8680.9148.1091.49% MMTok58.09 79.30221782.3870.4981.6159.6094.58% StackTok (ours)58.8481.19223283.4871.0082.3259.7895.79% Retain 10% VisionZip52.47 75.60200378.9063.7882.3036.9087.46% DivPrune53.43 72.85195774.9959.5979.5737.3084.73% MMTok55.09 74.74205178.7563.9080.4743.6088.52% StackTok (ours)55.9476.89205679.9564.5281.0343.6889.80% Retain 5% VisionZip46.28 67.53167766.3854.4979.5719.7075.37% DivPrune49.01 65.89173968.4552.0277.0524.9076.26% MMTok50.66 65.89179671.3555.9577.1930.7078.98% StackTok (ours)51.3567.32180572.3456.5277.7330.7380.00% Table A1: Performance on Qwen2.5-VL-7B under dynamic resolution. Avg. † is the mean relative retention over GQA, MMB, MME, POPE, and VQA Text ; SQA and OCRBench are excluded. Variant19212864 Fixed scalarization, best α98.85 97.93 96.60 Reference-gated policy (ours)98.9998.0396.66 Table A2: Reference-gated policy versus the best per-budget fixed scalarization on LLaVA-1.5-7B (average retained per- formance, %). Allocation640320160 Uniform fixed quotas98.55 96.95 94.40 Initial-h c -proportional quotas98.72 97.20 94.85 Shared-budget allocation (ours)98.9797.5195.26 Table A3: Static crop quotas versus StackTok’s dynamic shared-budget allocation on LLaVA-NeXT-7B (average re- tained performance, %). at x = 1/t gives (1− 1/t) t ≤ e −1 ; the case t = 1 follows directly. This proves the approximation guarantee for every recorded prefix of the same greedy chain. It remains to establish the shape of the reference curve. By monotonicity, η i ≥ 0, so C ref t is nondecreasing. For every 1≤ i < k ands∈U i , diminishing returns andG i−1 ⊆G i imply ∆ C (s|G i )≤ ∆ C (s|G i−1 ) ≤max u∈U i−1 ∆ C (u|G i−1 ) = η i . Taking the maximum over the smaller candidate set U i shows that η i+1 ≤ η i ; hence the reference increments are nonincreasing. Adjusted-threshold consequence. Because StackTok’s cal- ibrated β lies in [0, 1], for any t∈1,...,k, C(G t ) = C ref t ≥ βC ref t = θ t . Thus G t witnesses feasibility of the size-t support thresh- old. This statement neither requires equality nor implies that StackTok’s interleaved prefix S t meets the same threshold. Additional Experimental Details and Results Evaluation Protocol Affinity and calibration. StackTok requires no training. Vision–vision affinity uses pre-projector features, while query–vision affinity uses post-projector embeddings. This separation measures coverage in the native vision space and relevance in the LLM input space. We set τ t = 0.02 and τ v = 0.2 across datasets, except that Qwen2.5-VL- 7B uses τ t = 0.01. Entropy evaluation uses the numer- ical floor δ = 10 −12 , and the default strictness range is [β min ,β max ] = [0.3, 0.9]. Refinement and query processing. Support-preserving swap refinement uses ε sw = 10 −6 and one pass for each lo- cal retained set containing at most 16 tokens. LLaVA query preprocessing retains content-bearing keywords before em- bedding, whereas the Qwen2.5-VL integration embeds the question-prefixed input text. Dynamic-Resolution Results Table A1 tests whether reference-gated selection remains useful after Qwen2.5-VL-7B’s native dynamic-resolution en- coding. StackTok improves Avg. † over MMTok by 1.21, 1.28, and 1.02 points at 20%, 10%, and 5% retention, respectively, showing that the advantage persists when the visual sequence is not produced by a fixed grid. At 5% retention, gains remain visible on MMB and POPE, whereas OCRBench is nearly tied (30.73 versus 30.70). This contrast suggests that the se- lector transfers across encoding regimes, while pointing to a remaining limitation in preserving fine text evidence after extreme compression. Variant816 Without refinement84.8 90.4 Support-preserving swap refinement85.290.7 Table A4: Effect of support-preserving swap refinement at two extreme-compression budgets on LLaVA-1.5-7B (aver- age retained performance, %). [β min ,β max ][0.2, 0.8][0.3, 0.9][0.4, 1.0] Avg. %96.5496.6696.49 Table A5: Sensitivity to the strictness clipping range on LLaVA-1.5-7B at 64 retained tokens (average retained per- formance, %). Additional Ablations The following studies isolate choices beyond the component analysis in Table 2. All entries are average retained perfor- mance (%). Reference-gated policy versus fixed scalarization. Ta- ble A2 compares StackTok with R(S) + αC(S), tuning α separately at each budget. StackTok still improves by 0.14, 0.10, and 0.06 points at 192, 128, and 64 tokens. Grant- ing scalarization a separate best coefficient at each budget controls for budget-level tuning; the remaining gap indi- cates the limitation of a fixed coefficient: it cannot adjust the relevance–coverage priority across inputs and prefix states. Shared-budget allocation across crops. Table A3 holds the crop-local selector fixed and changes only how the high- resolution budget is distributed. The gain over uniform quotas widens from 0.42 to 0.86 points as the budget contracts from 640 to 160 tokens, indicating that static allocation is most costly when every slot matters. Initial-h c -proportional quotas recover part of this loss but remain 0.25–0.41 points behind. A one-time estimate may become stale as a crop accumulates tokens, whereas repeated nomination compares the current marginal value of the next token from each crop. Support-preserving swap refinement. Table A4 compares the same reference-gated selector with and without the support-preserving swaps in Eq. (15). The 0.40- and 0.30- point gains at 8 and 16 tokens show that revisiting early greedy choices is useful when only a few selections can be retained. The gains are modest, consistent with refinement serving as a final correction while the coverage floor prevents that correction from sacrificing visual support. Strictness sensitivity. Table A5 varies the clipping range [β min ,β max ] at the 64-token LLaVA-1.5-7B budget. The de- fault [0.3, 0.9] performs best, while either neighboring range changes the result by at most 0.17 points. This narrow spread indicates local robustness rather than complete parameter in- sensitivity, since the sweep covers only one model–budget setting and nearby ranges.