acceptodds
Under review as a conference paper at ICLR 2027

How Much Can We Prune? Exploring the Performance Limits of Visual Token Pruning

Abstract

Visual token pruning is increasingly used to reduce the memory and inference costs of vision-language models. Existing work has largely focused on designing method-specific selectors and demonstrating incremental improvements over prior methods at selected token budgets. It remains unclear whether the resulting performance reflects an inherent limit of visual token pruning or the limitations of current token-selection algorithms. We take a complementary perspective and ask: how well can visual token pruning perform when offline search cost is not the primary constraint? We formulate pruning for general image understanding as selecting, under a fixed budget, one shared visual-token subset that supports a broad distribution of questions about an image. We approximate this utility with a finite auxiliary QA set generated by a frontier VLM and optimize a teacher-forced answer-probability objective with the evaluated model frozen. Motivated by the conceptual monotonicity and diminishing returns of adding visual evidence, we construct nested subsets greedily and introduce QA mini-batch greedy (QA-MBG), which estimates token marginal gains from randomly sampled QA components at each step. Empirically, QA-MBG is both cheaper and more effective than full greedy. With one frontier-VLM call and approximately H100 GPU-hours per image, it produces a nested subset trajectory covering keep ratios up to . Across Qwen3-VL-4B and Gemma 4 E4B on images from nine benchmarks, we find significant headroom over evaluated pruning baselines on held-out QA and image-grounded long-form generation, while the searched subsets substantially narrow the gap to full-token inference.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Visual Token Pruning, Large Vision Language Model

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_VPHUOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper examines how much performance loss in visual token pruning can be recovered by more expensive offline subset selection. It uses auxiliary question-answer pairs generated by a frontier VLM to score candidate subsets through the frozen target model's answer likelihoods. The proposed QA mini-batch greedy algorithm samples questions at each selection step and builds nested, image-specific subsets that are reused across evaluation prompts. Experiments with two model families on 900 images from nine benchmarks demonstrate substantial headroom over existing selectors on held-out questions, alongside transfer to long-form descriptions. The contribution is an empirical characterization of achievable pruning performance under an offline search protocol.

Critical strengths
  1. The paper asks a useful diagnostic question that conventional accuracy-versus-budget comparisons do not answer. Producing feasible, unchanged-token subsets with consistently higher held-out performance demonstrates that some pruning loss is recoverable selector error. Reusing one image-specific subset across questions and description prompts makes this result more informative than a single-question oracle. The paper appropriately distinguishes achievable operating points from certified optima and explicitly treats search cost as part of the experimental protocol.

  2. The empirical investigation is unusually substantial. It covers two architectures, strong direct subset baselines, paired image-level bootstrap analyses, and several controls for auxiliary supervision. At 20% retention on the small Qwen set, dataset-agnostic generation reaches 92.79% relative performance and overlap-filtered search reaches 91.36%, versus 83.47% for the strongest baseline. The three-seed QA-MBG comparison also consistently outperforms full greedy. Together, these results support the main existence-of-headroom finding.

Critical weaknesses
  1. The strongest generalization controls remain limited in scope. Benchmark-agnostic generation and overlap removal are evaluated separately on the small Qwen cohort; the manuscript does not show their combination or analogous controls for Gemma. After overlap removal, the margin over the best baseline at 30% retention is only 0.46 relative-performance points (Table 20), and each removal condition is a single search run. Thus, the large main-experiment gaps are convincing under the stated auxiliary-supervision protocol, but a stronger claim about benchmark-independent, semantically disjoint general understanding is less firmly established. This limits the generality of the conclusion rather than invalidating the demonstrated feasible subsets.

  2. The long-form transfer evidence relies on a single model judge whose scores depend on the comparison group. Appendix D uses joint multi-candidate judging, and the full-token reference receives scores ranging from 3.954 to 3.622 across budget groups in Table 15. Appendix G correctly states that its intervals condition on the realized judgments and omit judge-rerun variability. The RealWorldQA example on p.47 also assigns 5/5 overall and groundedness to descriptions calling the wheels identical, despite the benchmark explicitly distinguishing their sizes. Within-group paired gains remain informative, but these observations motivate an independently calibrated check of the long-form conclusions. A small human or second-judge evaluation would materially strengthen this part of the contribution.

Questions for authors
  1. Does the headroom persist when dataset-agnostic generation and semantic-overlap filtering are applied jointly, with repeated search seeds? A representative check on Gemma would also clarify whether the current robustness conclusions extend beyond Qwen.

  2. How stable are the long-form paired rankings under an independent judge or a small blinded human audit, particularly if the candidate group is held fixed? Please distinguish ranking stability from absolute score calibration.

  3. Can the authors clarify how the reported approximately 0.5 H100 GPU-hours per image extrapolates beyond the single 945-token, 16-QA Qwen timing example in Appendix B? The main auxiliary pool averages 33.64 QAs, and Gemma uses a different architecture. Representative runtime statistics would make the released search targets easier to reproduce.

7 comments

Response to Reviewer VPHU (1/3)

We thank the reviewer for the careful reading and for questions that could be answered with experiments. We ran all three requested checks:

  1. the joint dataset-agnostic + overlap-filtered control on the full main set, for both backbones;
  2. two independent long-form judges, with and without a fixed candidate group, plus a blinded human audit;
  3. per-image runtime statistics for both backbones.

Revisions are marked in blue in the updated PDF.

Q1 / W1. Joint dataset-agnostic generation and overlap filtering, both backbones

Setup.

  • On all 900 main-set images, we generated auxiliary QAs with the dataset-agnostic prompt: no benchmark names, task profiles, dataset-specific instructions, or same-benchmark examples.
  • We then applied the same-visual-fact overlap filter against every held-out question. It removed 3.9% of the generated QAs overall: 11.0% on DocVQA, 8.9% on InfographicVQA, and about 1% on MME, MMStar, RealWorldQA, and V*Bench.
  • We re-ran QA-MBG with unchanged settings on this pool for Qwen3-VL-4B and Gemma 4 E4B, and evaluated on all 2,226 held-out questions and both long-form prompts.

Results. Six-budget means over 5–30% retention. Actual QA is in native score; long-form uses the main long-form judge and protocol.

Qwen3-VL-4BGemma 4 E4B
Actual QA, original (benchmark-conditioned) pool66.9056.68
Actual QA, agnostic + filtered pool56.1647.02
Actual QA, strongest baseline57.03 (FLoC)51.70 (MustDrop)
Baselines exceeded by the agnostic + filtered pool11 of 149 of 13
Long-form gain over strongest baseline [95% CI]+0.46 [0.42, 0.50] (vs FLoC)+0.35 [0.32, 0.39] (vs PruMerge)
Share of the original pool's long-form gain retained84%81%

What this shows.

  • Held-out QA decreases, as expected. The joint control deliberately removes the auxiliary questions that target what the held-out questions ask. The filter also removes supervision covering those regions, so the decrease does not measure leakage alone.
  • It does not collapse. The searched subsets still exceed most baselines. On Qwen they are within 0.87 points of FLoC and above it at 5% and 10% retention.
  • The deficit concentrates on the targeted facts. It appears mainly on benchmarks whose held-out questions ask about one word, one small object, or one document field, such as TextVQA, V*Bench, and DocVQA. A generic generator rarely targets such a region, and on documents the filter removes the generic questions that do. The rest of the image remains well represented: AI2D, MME, MMStar, and RealWorldQA change by at most 3.00 points from the original pool. The subsets stay at or above the best per-benchmark baseline on AI2D and InfographicVQA for both backbones, on ChartQA and DocVQA for Qwen, and on MMStar and RealWorldQA for Gemma.
  • Long-form headroom remains. Long-form descriptions do not hinge on the removed facts. The searched subsets exceed every baseline at every budget on both backbones.

Interpretation. We agree that the QA headroom depends on the query distribution. It grows as the auxiliary questions more closely match the target questions:

  • With benchmark-conditioned generation, searched subsets are far above current selectors.
  • Withholding benchmark information or filtering overlapping QAs separately reduces the margin but retains it.
  • Applying both brings held-out QA to the level of the stronger baselines, while long-form headroom remains.

When a deployment serves a specialized use case, such as document processing or driving assistance, matching the auxiliary QA distribution to that use case can maximize performance. The benchmarks play this role in our main experiments.

The revision adds this experiment to Section 4.3 ("Controlling the QA distribution"), with the protocol, per-benchmark, and long-form results in the new Appendix N.

Repeated seeds. We prioritized running the joint condition on all 900 images for both backbones. This covers five times as many images as the small set and costs more than three seeds on it.

Response to Reviewer VPHU (2/3)

Q2 / W2. Long-form stability: independent judges, fixed group, human audit

Second judges.

  • We re-scored every original long-form request with two judges from other model families: the open-weight Qwen3.8-27B and Claude Haiku 5.5. That is 21,600 requests (900 images × 2 prompts × 6 budget groups × 2 backbones), with identical prompts, images, and anonymized candidate order.
  • To remove group dependence, we also built a fixed-group set of 3,600 requests. For each image and prompt, one request contains the same ten candidates: the full-token answer, plus QA-MBG and the two strongest baselines at 5, 10, and 20%. All three judges scored this set.

Ranking stability. The method ranking is identical under all three judges in both sets, and QA-MBG ranks first at every budget for every judge. The table gives the paired gain over the strongest baseline: the six-budget mean for the original groups, and the 5/10/20% mean for the fixed group.

GPT-5.6-LunaQwen3.8-27BHaiku 5.5
Qwen3-VL-4B vs FLoC, original groups0.6120.6780.711
Qwen3-VL-4B vs FLoC, fixed group0.4580.5520.620
Gemma 4 E4B vs PruMerge, original groups0.4500.4560.509
Gemma 4 E4B vs PruMerge, fixed group0.4870.5070.566

All 95% CI lower bounds are at least 0.42. The judges also agree closely with each other:

  • When two judges both strictly prefer one candidate of a pair, they agree on 90.6–95.2% of pairs, and on 88.3–94.0% for QA-MBG vs the strongest baseline.
  • Kendall's τ between judges over condition means is 0.89–0.95 for the original groups and 1.00 for the fixed group.
  • Item-level Pearson r is 0.78–0.84.

Calibration. Absolute score levels differ across judges; Qwen3.8-27B is the most lenient. The offsets themselves change with the group (Haiku 5.5 is 0.25–0.29 below Luna in the original groups but within 0.04 in the fixed group). We therefore compare only within-judge paired differences.

Group dependence.

  • The full-token drift the reviewer noted appears under all three judges. It is therefore a property of joint multi-candidate scoring, not of one judge.
  • It does not affect same-budget comparisons. For the three compressed methods of the fixed group, every same-budget ordering is the same in the original and fixed groups, under all three judges.
  • It does affect comparisons across budget groups. In the original groups, QA-MBG at 5% scores above the strongest baseline at 10% for both backbones and all three judges. In the fixed group it is slightly below in all six cases (e.g., Qwen3-VL under Luna: 2.633 vs 2.449 in the original groups, 1.963 vs 2.012 in the fixed group).

The revision states in Section 4.1 that long-form scores are compared only within a budget, and adds all of the above to the new Appendix D.5.

Blinded human audit.

  • Design. Twelve raters each compared 10 pairs, giving 120 ratings over 66 distinct comparisons; 54 comparisons were rated by two raters. Each pair is QA-MBG versus the strongest same-budget baseline from the fixed-group set. Pairs are balanced across backbones and span budgets and image domains. Raters saw the image, the prompt, and the two anonymized descriptions in random order, and chose A, B, or tie.
  • Preference. QA-MBG was preferred 68 times, the baseline 33 times, with 19 ties. The win rate (tie = ½) is 0.65 [0.55, 0.75]: 0.67 [0.55, 0.78] for Qwen and 0.62 [0.50, 0.75] for Gemma.
  • Comparison with the judges. On the same items, the judges give 0.75 (Luna), 0.75 (Qwen3.8), and 0.80 (Haiku). The direction agrees, but the judges are more decisive than humans.
  • Agreement. Where both a judge and a human state a preference, they agree on 61–70% of items (46/76, 49/70, 55/85). Two humans agree on 26/40 such items (65%), with κ = 0.21 overall. Judge–human agreement is thus close to human–human agreement on this task.
  • Finer splits. Per-budget splits have 24–72 ratings each and wide intervals. Appendix D.5 (Table 13) reports them with the backbone and image-domain splits.

The p.47 example. Thank you for catching this. Giving 5/5 groundedness to descriptions that call the wheels identical is a judge error. We replaced all nine qualitative examples in Appendix Q: they now come from the fixed candidate groups, show the scores of all three judges, and mark each description by hand against the image (verified content in green, errors in red).

Response to Reviewer VPHU (3/3)

Q3. Representative runtime statistics

Thank you for pointing this out. The single-image example in Appendix B was meant to isolate the execution optimizations; it was not the source of the per-image cost.

We now report per-image statistics for the main runs of both backbones (revised Appendix B.3):

  • They are measured from the per-step profiles logged during search.
  • Each image was searched on one H100 80GB.
  • They cover search only; model loading and evaluation are excluded.
Qwen3-VL-4BGemma 4 E4B
Visual tokens nn, mean (range)777 (196–980)1,083 (1,032–1,120)
Greedy steps (to ratio 0.3)233325
QA–candidate evaluations per image1.24M2.06M
Time per evaluation1.5 ms1.9 ms
GPU-hours per image, mean0.511.07
10th / 50th / 90th percentile0.04 / 0.66 / 0.770.99 / 1.07 / 1.17
Maximum0.951.43
Total for 900 images≈460≈970

How the cost extrapolates.

  • At step tt, all n−tn-t remaining candidates are scored on m=⌈αM⌉m=\lceil\alpha M\rceil sampled QAs.
  • Reaching b=0.3nb=0.3n therefore takes E=m∑t<b(n−t)≈0.255 m n2E=m\sum_{t<b}(n-t)\approx 0.255\,m\,n^2 QA–candidate evaluations.
  • With the main pool (M=33.6M=33.6 on average), m≈7m\approx 7.
  • The logged counts match this formula, and search time is linear in EE. A single constant of 1.5 ms per evaluation explains the Qwen per-image times with R2=0.99R^2=0.99.
  • Cost is therefore quadratic in the number of visual tokens and linear in the number of QAs sampled per step. Other images, pool sizes, or sampling fractions can be extrapolated directly from EE and the per-evaluation constant.

Why the Appendix example understated the cost. Its 16-QA pilot pool gives 4 QAs per step, not about 7. A main-pool image of the same size therefore costs more: main-run DocVQA images (about 950 tokens) average 0.77 GPU-hours.

Variation across images and backbones.

  • In Qwen3-VL, the token count follows image resolution, so the cost spans more than an order of magnitude. MMStar images (about 256 tokens) take 0.05 h, while DocVQA and V*Bench images (about 950 tokens) take 0.74–0.77 h. This explains the low 10th percentile.
  • Gemma 4 caps images at 1,120 soft tokens, so its cost is nearly constant at about 1.1 h. That is about twice Qwen's, because Gemma has more visual tokens and a slightly higher time per evaluation.

Comparison with full greedy. On the 180-image small set, full greedy performs 4.7× as many evaluations. It takes 3.4× the GPU time for Qwen (1.7 vs 0.5 h) and 3.5× for Gemma (3.9 vs 1.1 h).

What the cost buys (new, Section 4.4). The search is a one-time cost per training image, and its subsets serve as training targets: a 0.73M-parameter selector distilled from the 900 searched images leads every compared selector on 15,410 held-out questions from unseen images, on both backbones, at the inference cost of a training-free selector.

Changes to the paper (marked in blue)

  • Abstract and introduction. They state ≈0.5 (Qwen3-VL-4B) and ≈1.1 (Gemma 4 E4B) H100 GPU-hours per image. Appendix B.3 now contains the runtime tables, the cost model, and the per-benchmark breakdown. The single-image probe is kept only as an execution microbenchmark.
  • New full-set experiment. The joint dataset-agnostic + overlap-filtered experiment on 900 images for both backbones is added to Section 4.3, with the protocol, per-benchmark, and long-form results in the new Appendix N. The conclusion states that held-out QA performance can drop as the auxiliary QAs depart from the target distribution, while long-form performance is largely maintained.
  • New Appendix D.5. It reports the second judges (Qwen3.8-27B, Haiku 5.5), the fixed-group re-scoring, ranking vs. calibration, group dependence, and the blinded human audit. Section 4.1 states that long-form scores are compared only within a budget, and Section 4.2 summarizes the judge and human results.
  • p.47. All nine qualitative examples in Appendix Q are replaced (fixed groups, three judges, errors marked by hand).
  • New Section 4.4 (Figure 4) and Appendix P. A selector distilled from the searched subsets, compared with learned and training-free selectors on held-out questions, with per-benchmark scores and FLOPs.
Reviewer_YNEdOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates visual token pruning in vision-language models (VLMs), focusing on the performance that can be achieved under a fixed token budget. Rather than developing another low-cost token selector, the authors relax the offline search constraint to examine the gap between existing pruning methods and stronger feasible token subsets. They formulate the task as selecting one shared visual-token subset that supports multiple questions about the same image. A frontier VLM generates auxiliary question-answer pairs, and a frozen target VLM scores candidate subsets using teacher-forced reference-answer probabilities. The authors further propose QA mini-batch greedy (QA-MBG), which samples a subset of QA components at each greedy step. Experiments on two VLMs, nine benchmarks, and 900 images show that the searched subsets outperform evaluated pruning baselines on question answering and image-grounded long-form generation, while narrowing the gap to full-token inference.

Critical strengths
  1. Meaningful problem formulation and a useful evaluation perspective. The paper asks an important question that is not directly answered by conventional pruning evaluations: how much visual-understanding performance can be retained under a fixed token budget? Its distinction between unavoidable information loss and errors caused by token-selection strategies provides a useful way to interpret existing performance gaps. In addition, selecting one shared subset for multiple questions is more relevant to general image understanding than optimizing the retained tokens for only one known query.
  2. A coherent search framework with careful implementation. The authors turn the broad objective of supporting diverse image-grounded questions into a measurable QA-based objective and construct nested subsets through greedy selection. QA mini-batching offers a practical way to reduce the number of QA evaluations at each step, while candidate batching, prefix-KV reuse, and teacher-forced scoring make the offline search more manageable. The overall pipeline is clearly specified and supported by implementation details.
  3. Broad experiments and useful robustness analyses. The evaluation covers two VLM families, nine benchmarks, and both short-answer QA and long-form image description. The paper also studies the effects of QA sampling fraction, auxiliary-QA pool size, the QA generator, benchmark conditioning, and semantic overlap. These analyses provide a relatively broad assessment of the proposed search procedure and help establish that the observed gains are not limited to a single model or evaluation format.
Critical weaknesses
  1. The methodological novelty is relatively limited. The main technical pipeline builds on established ideas in token-subset selection, greedy optimization, and stochastic sampling of objective components. Although the paper adapts these ideas to a shared multi-QA token-selection objective, the resulting contribution appears to be primarily a combination and task-specific adaptation of existing optimization principles rather than a substantially new algorithmic mechanism. In particular, the distinction between QA-MBG and existing mini-batch optimization strategies is not sufficiently developed. The paper should clarify what new algorithmic or theoretical insight is obtained beyond applying these ideas to this setting.
  2. The claimed performance limits are not sufficiently supported by theory. The objective is motivated by approximate monotonicity and diminishing returns, but the authors acknowledge that the frozen-VLM answer-probability objective does not strictly satisfy the assumptions required for standard submodular guarantees. Consequently, the greedy trajectory cannot be interpreted as a near-optimal solution, and the searched subsets establish feasible empirical operating points rather than an actual performance limit. Moreover, the observation that QA-MBG outperforms full greedy is explained mainly through a possible regularization effect. More direct analysis is needed to establish why resampling QA components improves an irreversible sequence of greedy decisions.
  3. The representativeness of the auxiliary QA set remains uncertain. The method approximates the distribution of questions about an image using a finite set of questions generated by a frontier VLM and assigns equal weight to all QA pairs. However, it is unclear whether this set adequately represents the diverse information needs that arise in general image understanding. Generated questions may exhibit systematic coverage biases, and uniform weighting may not reflect the frequency or importance of different question types in real use. The dataset-agnostic and overlap controls are useful, but they do not fully establish that the auxiliary QA set is a faithful approximation of an unknown and potentially shifting query distribution.
  4. The high offline search cost limits the demonstrated practical value. The reported search cost is approximately 0.5 H100 GPU-hours per image, in addition to the use of an external frontier VLM to generate auxiliary QA pairs. This cost is understandable for an exploratory study of achievable performance, but it creates a substantial gap between the proposed procedure and practical low-cost token pruning. The paper does not demonstrate how the searched subsets can be transferred to an efficient selector or used to improve a deployable pruning method. A clearer account of how the empirical frontier can guide practical token-selection algorithms would strengthen the significance of the work.
Questions for authors
  1. Methodological novelty. What are the substantive algorithmic or theoretical contributions of QA-MBG beyond adapting established subset-selection and mini-batch optimization ideas to a multi-QA objective? Which properties of the proposed formulation cannot be obtained by directly applying existing optimization strategies?
  2. Validity of the performance-frontier claim. Given that the objective does not strictly satisfy monotonicity and submodularity, how can the authors assess whether the searched subsets are close to optimal? Could exhaustive search or a stronger optimization procedure on small instances provide a reference for the gap between QA-MBG and the actual optimum?
  3. Coverage and representativeness of auxiliary QAs. How sensitive is the selected subset to the types, diversity, and coverage of generated questions? Can the authors provide evidence that the auxiliary QA set represents a broad distribution of image-grounded information needs, particularly when the test-time query distribution differs from the generation setting?
  4. Why QA-MBG can outperform full greedy. Can the authors provide a more direct analysis of why sampling only a fraction of the QA components produces better downstream subsets than evaluating the full QA objective at every step? Is this effect consistent across models, datasets, and additional search seeds?
  5. Practical use of the searched subsets. Given the substantial per-image offline search cost, can the searched subsets be used to train or distill a lightweight token selector? How do the authors envision translating the empirical performance frontier into a practical pruning method, and how should the offline search cost be accounted for when assessing the overall benefit?
9 comments

Response to Reviewer YNEd (1/5)

We thank the reviewer for the detailed and constructive review. The questions led to several new experiments:

  • exhaustive search on small instances and stronger local search (Q2);
  • a full-set distribution-shift test on both backbones (Q3);
  • a three-seed full-greedy comparison on Gemma, together with a direct mechanism analysis (Q4);
  • a lightweight selector distilled from the searched subsets (Q5).

Revisions are marked in blue in the updated PDF.

Q1 / W1. Methodological novelty

We agree that the ingredients are established: greedy subset selection and sampling of objective components. The paper positions QA-MBG as the decomposable-objective counterpart of mini-batch submodular maximization (Schwartzman et al.), and distinguishes it from stochastic greedy. Four things, however, go beyond a direct application of these strategies.

  1. A novel search-supervised training pipeline for token selectors. Prompted by the reviewer's Q5, we trained a lightweight selector on the searched subsets. It outperforms every learned and training-free baseline at every budget on both backbones (details in Q5). This establishes, to our knowledge, the first pipeline of its kind: a VLM generates per-image QAs that operationalize understanding of the image, QA-MBG searches discrete token subsets that the frozen model scores against them, and a selector is trained to reproduce the searched subsets. Existing learned selectors that keep the VLM frozen, such as VisionSelector, DiffPrune, and LearnPruner, instead backpropagate a next-token loss on VQA or caption data through a relaxed selection: a differentiable top-k, noise-based throttling, or a straight-through mask. VisionSelector and DiffPrune also train at one fixed budget. Our labels differ in three ways.

    • They come from evaluating discrete subsets, so there is no gap between a soft training mask and hard top-k inference.
    • They reflect set-level choices: each token is selected given those already kept, and the subset supports many questions about the image at once.
    • They cover every budget at once because the trajectory is nested, so one selector serves all budgets.

    Training needs no backpropagation through the VLM. A 0.73M-parameter MLP learns from precomputed embeddings of 900 images, whereas VisionSelector uses 144,548 training samples.

  2. Sampling improves solution quality, not only cost. In existing analyses, component sampling is an approximation, and its quality is measured against full-objective greedy. Here the sampled version is better than full greedy on held-out QA and on long-form generation. For every tested QA fraction α, it is better even on the search objective at the end of the trajectory: at 30% retention, 0.670 / 0.686 / 0.715 (α = 0.1 / 0.2 / 0.5) versus 0.655 for full greedy. The reversal holds on both backbones (Q4). Existing theory takes full greedy as the reference, so it does not predict this.

  3. A mechanism for the reversal. Per-step QA sampling concentrates each step on a resampled subset of questions. Over a long search, this gives a better path than maximizing the all-question sum, and the gain is largest on the weakest questions (Q4). A deterministic focused rule also beats full greedy, so the benefit comes from focus rather than randomness. QA-MBG obtains it while evaluating only a fraction of the questions.

  4. Formulation and protocol.

    • We search one shared subset per image for a distribution of questions, with the evaluated model frozen.
    • The search runs once and yields a nested trajectory, which is reused for held-out questions and long-form prompts.
    • Teacher-forced scoring, prefix-KV reuse, and candidate batching make 1.2–2.1M QA–candidate evaluations per image feasible.

We regard the measurement as the central contribution: a reproducible, feasible frontier that shows large headroom over current selectors, together with a pipeline that turns this frontier into training targets for a deployable selector. The question it answers, how much of the pruning loss is recoverable selector error rather than unavoidable information loss, is not answered by conventional accuracy-versus-budget evaluations. The reviewer's first strength makes this point, and Reviewers 27kZ and VPHU make it as well. QA-MBG is the component that makes the frontier attainable. The revision states this ordering of contributions more clearly.

Response to Reviewer YNEd (2/5)

Q4 / W2 (second part). Why QA-MBG outperforms full greedy, and consistency

Consistency across models and seeds.

  • Qwen3-VL-4B, small set, three QA-MBG seeds:
    • At 20% retention, relative actual-QA performance is 96.63% (range 96.18–97.15), versus 83.03% for full greedy.
    • Long-form quality is 3.099 (range 3.081–3.115), versus 2.021.
    • Every seed beats full greedy at all six budgets in both evaluations (Figure 3; all budgets in Appendix I, seeds in Appendix I.3).
  • Gemma 4 E4B (new), small set, three seeds:
    • The six-budget native mean is 54.48 ± 0.77, versus 51.03 for full greedy (full tokens: 61.77). The 95% CI of the seed-mean difference is [0.23, 6.84].
    • QA-MBG is behind only at 5% (46.41 vs 47.33).
    • Long-form quality is 2.89 vs 2.03 (+0.86 [0.77, 0.94]). QA-MBG is ahead at every budget and on all nine benchmarks (Appendix I.4).

Why sampling helps. Full greedy adds the token with the largest gain summed over all questions. QA-MBG instead concentrates each step on a resampled subset. Over hundreds of irreversible steps, this focus gives a better path (Qwen, 30% retention, auxiliary pool of the main experiments):

Full greedyQA-MBG α = 0.1α = 0.2α = 0.5Top-20%
Search objective (all-QA mean)0.6550.6700.6860.7150.703
Lowest 20% of QAs per image0.2010.2450.2590.2980.288
Actual QA, six-budget mean (%)80.9593.8992.1490.7894.17

Appendix J.2 gives the endpoint objective and lower tail, Appendix J.1 gives actual QA for every rule and budget, and Appendix H gives the trajectories.

  • Full greedy ends with a lower value of its own objective than every tested fraction α. Gemma (α = 0.2, three seeds) shows the same: 0.638 vs 0.619 (Appendix J.2).
  • Focusing each step on a subset of questions helps, and randomness is not required. QA-MBG and top-k share one property: each step can favor some questions over the sum across all of them. Top-k is deterministic. It ranks candidates by the sum of their largest per-question gains (the top 1, or the top 10%, 20%, or 50% of questions). Every top-k variant beats full greedy on actual QA (six-budget means 90.97–94.17% vs 80.95%), as does every QA-MBG setting (90.78–93.89%) (Appendix J.1). Top-k, however, evaluates every question at every step. QA-MBG reaches comparable quality while evaluating only a fraction α.
  • The gain is largest on the weakest questions: +0.044 to +0.097 on the lowest 20%, more than the gain in the mean. On Gemma, the lowest 20% score 0.211 vs 0.169. Along the trajectory, full greedy leads at the smallest budgets; the lower-tail advantage of sampling appears afterwards and grows toward the final budget (Appendix H). One plausible reading: the sum keeps favoring tokens that help many questions at once, while resampling periodically gives every question priority.

Short horizons. The exhaustive experiment (Q2) is consistent with this. With at most four selected tokens, full greedy is near-optimal and ahead of QA-MBG on the objective (0.94–0.999 vs. 0.80–0.86 of the optimum). The advantage of sampling appears only over long trajectories.

Regularization. We agree that the regularization explanation in the main text was too speculative. The revision replaces it with the analysis above. The main text gives the objective and lower-tail evidence for both backbones and the top-k control; Appendices H and J give the trajectories and full results. The revision also states that the analysis characterizes search behavior; it is not a causal proof.

Response to Reviewer YNEd (3/5)

Q2 / W2. Closeness to the optimum; "performance limits"

Terminology. We agree. Searched subsets are feasible operating points, i.e., lower bounds on the achievable performance at each budget; they are not certified optima. The revision replaces "performance limits" with "achievable performance" throughout the text, and in the title if permitted.

Exhaustive search on small instances (new).

  • Images. 120 images with natively small token grids (36–64 visual tokens), with Qwen3-VL-4B. They cover natural scenes, text-rich images, and diagrams from GQA, OCR-VQA, and AI2D.
  • Auxiliary QAs. Generated with one benchmark-agnostic prompt. A QA was kept if the full-token model answers it correctly and visual evidence matters (gain ≥ 0.10 over no visual tokens). This left 2,317 QAs, about 19 per image.
  • Search. We enumerated every subset of k ≤ 4 tokens, up to C(64,4) ≈ 635k subsets per image.

The table reports the search objective (mean teacher-forced answer probability) relative to the exact optimum. In parentheses is the share of all subsets that score higher.

k1234
Full greedy.999 (0.05%).978 (0.12%).960 (0.04%).944 (0.02%)
QA-MBG (3 seeds).864 (12.7%).821 (6.7%).805 (4.6%).801 (3.0%)
FLoC.71.61.58.57

For FLoC, about 35% of all subsets score higher; for random subsets, about 50%. Full greedy finds the exact optimum on 98 / 50 / 30 / 15% of images for k = 1 / 2 / 3 / 4.

Held-out accuracy on the 886 original questions of these images is below (exact match; full tokens 64.9, no visual tokens 27.8):

k1234
Exhaustive optimum33.441.044.249.8
Full greedy33.240.644.547.6
QA-MBG34.840.343.346.7
FLoC35.339.442.043.9
Random35.036.341.342.6
  • At k = 1, no method differs from random. At k = 2–3, the optimum and full greedy are ahead of random (e.g., +4.7 [1.3, 7.9] for the optimum at k = 2), but within noise of QA-MBG and FLoC.
  • At k = 4, the optimum is ahead of QA-MBG by +3.0 [0.8, 5.3]. QA-MBG is ahead of FLoC by +2.8 [0.7, 5.0] and of random by +4.2 [2.2, 6.3].
  • Despite the lack of formal guarantees, greedy is near-optimal on the objective at these sizes. This is consistent with approximately diminishing returns.
  • QA-MBG is clearly suboptimal over such short horizons, as discussed in Q4.

Stronger search at the main-experiment scale (new).

  • Setup. On the small Qwen set (180 images; 5, 10, and 20% retention; Opus 5 auxiliary pool of Appendix O), starting from the QA-MBG subsets, we ran three searches:
    • batched best-improvement 1-swap hill climbing;
    • random r-token perturbation search;
    • cost-matched best-of-random subsets.
  • Objective and held-out QA. Swap raises the search objective by 0.046–0.054 and perturbation by 0.013–0.018. Held-out QA changes by −1.0 to +1.6 points; no paired interval excludes zero.
  • Long-form. Long-form quality does not improve: QA-MBG 2.44, perturbation 2.41, swap 2.40 (differences not significant). Random subsets reach 1.74.

Stronger optimization of the same objective therefore adds little. This is far less than the gap between searched subsets and existing selectors, which is 10.12 points on average for Qwen on the main set. The remaining uncertainty about the frontier lies more in the objective (which questions are asked) than in the optimizer. This agrees with the distribution-shift result in Q3.

Comments on the paper

8 comments

Response to Reviewer 27kZ (1/3)

We thank the reviewer for the positive assessment and for two concrete questions. We ran new experiments for both:

  • exhaustive search on small instances and stronger local search (Q1);
  • the joint dataset-agnostic + overlap-filtered control on the full set, for both VLMs (Q2);
  • a lightweight selector trained on the searched subsets (W1, W2).

Revisions are marked in blue.

W1 / Q1. Relation to mini-batch subset optimization; closeness to the optimum

Relation to mini-batch methods. We agree that QA-MBG is closely related to these methods. The paper presents it as the decomposable-objective counterpart of mini-batch submodular maximization (Schwartzman et al.). It differs from stochastic greedy, which samples token candidates rather than objective components. We do not claim the sampling strategy itself as new. Two results go beyond it: the direction of its effect (below) and a search-supervised way of training token selectors (3/3).

Existing analyses do not predict the direction of the effect: sampling QAs gives better subsets than full greedy, not just cheaper ones. This holds on both backbones, with three QA-MBG seeds each (small set, 180 images):

QA-MBG (3 seeds)Full greedy
Qwen3-VL-4B, actual QA at 20% (relative %)96.63 (96.18–97.15)83.03
Qwen3-VL-4B, long-form (0–5)3.102.02
Gemma 4 E4B, actual QA, six-budget mean (native)54.48 ± 0.7751.03
Gemma 4 E4B, long-form (0–5)2.892.03

Why sampling helps (details: our response to Reviewer YNEd, Q4):

  • Full greedy maximizes the gain summed over all questions. QA sampling concentrates each step on a resampled subset.
  • Over hundreds of irreversible steps, this gives a better path. At 30% retention on Qwen, full greedy ends lower even on its own objective (0.655 vs 0.670–0.715 for α = 0.1–0.5), most of all on the weakest 20% of questions (0.201 vs 0.245–0.298).
  • A deterministic focused rule (top 20% of per-question gains) also beats full greedy, so focus matters, not randomness. QA-MBG gets this while evaluating only a fraction of the questions.

Gemma shows the same pattern (0.638 vs 0.619; lowest 20%: 0.211 vs 0.169). The revision gives this analysis in the main text.

Monotonicity and submodularity. We agree these properties are not established. Frozen-VLM QA utility is at most approximately monotone and submodular. We use the properties only to motivate greedy construction, and we do not claim the (1 − 1/e) guarantee. The revision states this explicitly. It also replaces "performance limits" with "achievable performance": searched subsets are feasible operating points, i.e., lower bounds at each budget, not certified optima.

Exhaustive search on small instances (new).

  • Instances. 120 images with natively small token grids (36–64 visual tokens, Qwen3-VL-4B), from GQA, OCR-VQA, and AI2D, with 2,317 auxiliary QAs from one benchmark-agnostic prompt.
  • Search. We enumerated every subset of k ≤ 4 tokens, up to ≈635k subsets per image.
k1234
Objective / optimum: full greedy.999.978.960.944
Objective / optimum: QA-MBG.864.821.805.801
Objective / optimum: FLoC.71.61.58.57
Held-out acc.: exhaustive optimum33.441.044.249.8
Held-out acc.: full greedy33.240.644.547.6
Held-out acc.: QA-MBG34.840.343.346.7
Held-out acc.: FLoC35.339.442.043.9
  • Full greedy is near-optimal at these sizes. Its subsets fall in the top 0.02–0.12% of all subsets, and it finds the exact optimum on 98 / 50 / 30 / 15% of images, consistent with approximately diminishing returns.
  • QA-MBG is clearly below the optimum over these short horizons (top 3–13%). Its advantage over full greedy appears only on long trajectories.
  • Held-out questions (886; full tokens 64.9). At k = 1, no method differs from random. At k = 2–3, the optimum and full greedy beat random (e.g., +4.7 [1.3, 7.9] at k = 2), but are within noise of QA-MBG and FLoC. At k = 4, the optimum leads QA-MBG by +3.0 [0.8, 5.3], and QA-MBG leads FLoC by +2.8 [0.7, 5.0].

Stronger offline search at the main-experiment scale (new; details in our response to Reviewer YNEd, Q2). On the small Qwen set, starting from the QA-MBG subsets, 1-swap hill climbing and random perturbation search raise the objective by 0.01–0.05. Held-out QA changes by −1.0 to +1.6 points (none significant), and long-form quality does not improve: QA-MBG 2.44, perturbation 2.41, swap 2.40. Cost-matched random subsets reach 1.74.

Conclusion. Stronger optimization of the same objective adds little relative to the gap over existing selectors (about 10 points for Qwen on the main set). The remaining uncertainty about the frontier lies more in the objective, i.e., which questions the auxiliary set covers, than in the optimizer (see Q2).

Response to Reviewer 27kZ (2/3)

W2 / Q2. QA generation cost and benchmark conditioning; full-set control on both VLMs

Full-set control (new).

  • Generation. As requested, we generated auxiliary QAs on all 900 main-set images with the dataset-agnostic prompt: no benchmark names, task profiles, dataset-specific instructions, or same-benchmark examples.
  • Overlap filter. We applied the same-visual-fact filter against every held-out question. It removed 3.9% of the generated QAs: 11.0% on DocVQA, 8.9% on InfographicVQA, and about 1% on MME, MMStar, RealWorldQA, and V*Bench.
  • Search and evaluation. We re-ran QA-MBG with unchanged settings for both VLMs, and evaluated on all 2,226 held-out questions and both long-form prompts.

Six-budget means over 5–30% retention:

Qwen3-VL-4BGemma 4 E4B
Actual QA, original (benchmark-conditioned) pool66.9056.68
Actual QA, agnostic + filtered pool56.1647.02
Actual QA, strongest baseline57.03 (FLoC)51.70 (MustDrop)
Baselines exceeded by the agnostic + filtered pool11 of 149 of 13
Long-form gain over strongest baseline [95% CI]+0.46 [0.42, 0.50] (vs FLoC)+0.35 [0.32, 0.39] (vs PruMerge)
Share of original long-form gain retained84%81%

Per benchmark (six-budget mean; Orig./Agn. = original/agnostic + filtered pool, BL = best baseline on that benchmark):

Qwen Orig.Qwen Agn.Qwen BLGemma Orig.Gemma Agn.Gemma BL
AI2D80.5677.6677.1972.6971.7570.03
ChartQA72.5559.1856.8953.7942.4246.81
DocVQA78.8751.4450.5366.9435.4756.98
InfographicVQA62.9048.0038.0845.9832.2032.06
MME80.8380.5882.3350.6748.5067.58
MMStar46.3945.3747.1044.4743.8641.64
RealWorldQA64.8361.8364.1756.8354.1754.17
TextVQA53.3635.8861.7265.2448.4360.00
V*Bench61.8345.5061.5053.5046.3354.67

What this shows.

  • Held-out QA decreases, as expected, because the joint control deliberately removes the auxiliary questions targeting what the held-out questions ask. This also removes supervision covering those regions, so the decrease does not measure leakage alone.
  • It does not collapse. The searched subsets still exceed most baselines, and on Qwen they are within 0.87 points of FLoC.
  • The deficit concentrates on the targeted facts: one word, one small object, or one document field, as in TextVQA, V*Bench, and DocVQA. A generic generator rarely targets such a region, and on documents the filter removes the generic questions that do. AI2D, MME, MMStar, and RealWorldQA change by at most 3.00 points from the original pool.
  • Long-form headroom remains. The searched subsets exceed every baseline at every budget on both VLMs.

Interpretation. The headroom partly generalizes beyond benchmark-conditioned supervision: long-form headroom persists, and held-out QA stays at the level of the stronger baselines. QA headroom grows as the auxiliary questions better match the target questions, so a specialized deployment can maximize performance by matching the auxiliary QA distribution to its use case, as the benchmarks do in our main experiments.

Response to Reviewer 27kZ (3/3)

W2 / Q2 (continued). QA generation and search cost

QA generation cost.

  • One call per image. One generator call produces the image's whole auxiliary set (33.6 QAs on average), which serves the entire nested trajectory.
  • No frontier model required. On the small set, the open-weight Qwen3.8-27B generator (new) gives 92.65% six-budget mean relative performance. GPT-5.6-SOL gives 91.69% and Opus 5 gives 93.14%. In long-form, Qwen3.8-27B reaches 3.15, versus 2.64 for the best baseline (Appendix O).
  • Pool size. Coverage matters, with diminishing returns. At 20% retention, 25% of the pool gives 86.33%, 75% gives 93.87%, and the full pool gives 96.18%.

Search cost. The search takes 0.51 (Qwen3-VL-4B) and 1.07 (Gemma 4 E4B) H100 GPU-hours per image on average. Full greedy needs 3.4–3.5× the GPU time. Details are in Appendix B.3 and our response to Reviewer VPHU (Q3).

QA generation and search are paid once, on the training images, and their output trains a deployable selector (below).

W1 (continued). Search-supervised selector training (new, Section 4.4)

We trained a 0.73M-parameter MLP that scores visual tokens to reproduce the searched subsets. At inference it needs no auxiliary QAs and no search. It is evaluated on 15,410 held-out questions from the nine benchmarks, excluding every question about the 900 search images (full tokens: 78.56 Qwen, 64.64 Gemma). The learned baselines (VisionSelector, DiffPrune, LearnPruner) are trained with their authors' recipes and data on the same frozen backbone. The selector leads every compared method at all six budgets on both VLMs; four are shown.

Keep ratio5%10%20%30%
Qwen3-VL-4B: distilled selector57.6265.2471.9575.38
Qwen3-VL-4B: best learned46.4653.8565.0872.06
Qwen3-VL-4B: best training-free48.3254.6962.6068.65
Gemma 4 E4B: distilled selector44.3751.3757.9260.73
Gemma 4 E4B: best learned42.3348.9156.1159.26
Gemma 4 E4B: best training-free41.6548.8954.5958.31

To our knowledge, this is the first pipeline of its kind: a VLM generates per-image QAs that operationalize understanding of the image, QA-MBG searches discrete token subsets that the frozen model scores against them, and a selector learns to reproduce these subsets. Existing learned selectors that keep the VLM frozen instead backpropagate a next-token loss on VQA or caption data through a relaxed selection (a differentiable top-k, noise-based throttling, or a straight-through mask), and VisionSelector and DiffPrune train at one fixed budget. Our labels differ in three ways:

  • they come from evaluating discrete subsets, so there is no gap between a soft training mask and hard top-k inference;
  • they reflect set-level choices: each token is selected given those already kept, for many questions at once;
  • they cover every budget at once, because the trajectory is nested, so one selector serves all budgets.

Training needs no backpropagation through the VLM; the MLP learns from precomputed embeddings of 900 images. At inference it adds 1.1 GFLOPs to a 0.69-TFLOP language-model prefill, the cost of a training-free method.

Changes to the paper (marked in blue)

  • Wording. "Performance limits" becomes "achievable performance". Searched subsets are described as lower bounds, and monotonicity and submodularity are stated as approximate motivation only.
  • New Appendix K. Exhaustive search on small instances and local search at the main scale.
  • Main text: full-set control. Section 4.3 now includes the full-set dataset-agnostic + overlap-filtered experiment for both VLMs, with full results in the new Appendix N. It also reports the open-weight generator.
  • Main text: QA-MBG vs. full greedy. It reports the comparison on both backbones and the mechanism analysis (search objective and lower tail on both backbones, and the top-k control). Appendix B.3 gives runtime statistics.
  • New Section 4.4 (Figure 4) and Appendix P. A selector distilled from the searched subsets, compared with learned and training-free selectors on held-out questions, with per-benchmark scores and FLOPs.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.