Vision-language models turn an image into hundreds or thousands of "visual tokens," and most of the compute goes into processing them. Pruning methods drop the tokens that look unimportant before the language model sees them. That works for describing scenes. It breaks on spatial questions such as "is the mug left of the laptop?" or "which box does this phrase refer to?" The tokens that answer those questions are often small, low-salience, or sit in the empty space between objects, and pruning removes them permanently.
We propose a different arrangement. The model first answers under an aggressive token budget, but it must express its answer as a small program: it declares the objects it sees with coordinates, and then computes the spatial relation in code. Running the program does two jobs. It produces the answer, and it acts as a detector for the specific places where pruning starved the model. A coordinate declared over a region that was mostly pruned means the model had no evidence there and was guessing. A program that crashes on an undeclared object means something went missing. When either happens, we restore the cached encoder tokens for that region only, at their original positions, and run again.
The bet has two parts. Execution failures localize pruning damage much better than the attention scores used at pruning time. And recall that happens only on failure should give a better accuracy-per-compute curve than either fixed-budget pruning or the obvious fallback of re-running at full resolution.
Core Claim
Every pruning method in the literature is one-shot and feed-forward. TokenNMS ranks tokens by self-attention and query relevance and applies diversity suppression. Nüwa groups tokens into spatially cohesive clusters and re-stretches position embeddings. IVC-Prune protects tokens that act as implicit coordinate anchors under rotary position embeddings, the scheme that encodes each token's position as a rotation. CoverPrune selects tokens for coverage via optimal transport. In each case, a token dropped by mistake stays dropped.
These papers also document where the losses concentrate. TokenNMS and Nüwa report that small objects are obliterated at high pruning ratios. Nüwa retains only 47.2% of unpruned referring-expression grounding performance at 64 tokens, while VisionZip and FastV fall to roughly 7–8%.
The spatial-reasoning literature explains why query-guided pruning is especially harmful here. Models answer spatial questions through object co-occurrence shortcuts: spatial prepositions appear in fewer than 0.2% of captions, per What's "up" with vision-language models?. Pruning that keeps the tokens best matching the nouns "dog" and "table" keeps exactly the evidence that feeds the shortcut. It discards the evidence needed to place the two objects relative to each other.
Our claim is that a program which computes the relation from declared coordinates turns this silent failure into a detectable one. The relation itself is computed symbolically, so the language model only has to localize each object. Localization has a checkable precondition: the declared box must overlap tokens the model actually saw.
We formalize that check as a support score. For a declared box $b$, let $G(b)$ be the set of patch-grid cells it covers and $R$ the set of currently retained cells. Then
$$s(b) = \frac{|R \cap G(b)|}{|G(b)|},$$
and any box with $s(b) < \tau$ triggers recall of $G(b)$, dilated by one cell. Here $\tau$ is a threshold tuned on a held-out split. The check is deterministic and does not depend on the model admitting uncertainty, which matters because the hallucinated coordinates we are trying to catch are produced confidently.
Relation to Closest Work
The nearest system is RECODE. It converts charts and geometry diagrams into executable plotting code, renders candidates, scores them against the image with a pixel-level squared-error critic, and refines the code. It reports 93.2% on ChartQA, 94.2% on Geometry3K, and 77% on CharXiv-Reasoning. RECODE supplies the method we reuse: answering through executed code rather than free text.
RECODE differs from us in two ways. It processes the full visual input on every iteration, and its feedback signal measures rendering fidelity rather than whether a specific region was observed. We use execution feedback for a different job: deciding which visual evidence to restore.
Synthesize Step-by-Step is related but offline. It trains on executable chart rationales, raising the human-written ChartQA split from 38.2% to 53.9%, and it never refines at test time.
SpatialThinker is also related. It structures spatial deduction as textual scene graphs with boxes and trains with reinforcement learning on box-overlap rewards. It shows that explicit coordinates help, but it ingests all tokens and has no execution step.
DCoT draws predicted boxes on the image and re-encodes it. It cannot correct a wrong first-turn box, and it does not compress anything.
The motivating evidence that free-text reasoning is unreliable here comes from MATH-Vision. There, 42.2% of GPT-4V failures were reasoning errors despite correct perception, and chain-of-thought sometimes lowered multimodal accuracy. This is why the relation is computed in code rather than in prose.
Research Program
The system is training-free in its first version. The vision encoder runs once at full resolution, and all of its output tokens are cached. A base pruner then passes a small budget to the language model; we use TokenNMS so that our gains sit on top of a strong method.
The model is prompted to emit a short Python program against a fixed library. The library lets the model declare objects with boxes. It provides relation functions such as left_of, above, in_front_of, and contains, computed from box geometry and, where needed, a depth ordering the model declares. It also provides a frame-change function for perspective questions.
An executor runs the program and applies three checks. The support check flags boxes with $s(b) < \tau$. A missing-entity check catches references to undeclared objects and maps the query noun phrase to the top query-relevance cells, including pruned ones. A consistency check flags contradictions, such as a relation and its converse both being asserted. Any failure restores the corresponding cached tokens with their original two-dimensional position indices.
Keeping original position indices is the part of the design that addresses the spatial-integrity concern raised by Nüwa and IVC-Prune: restored tokens land at their true coordinates instead of being re-packed. The model then re-emits its program. We cap the process at three rounds; Yan et al. report that refinement gains plateau after a few iterations.
We will study two implementation choices for restoration. The first appends restored tokens to the existing key-value cache with explicit position ids, which is cheap but means earlier tokens cannot attend to them. The second re-runs prefill on the enlarged set. A second phase fine-tunes the program writer on a few thousand spatial questions, with rewards for correct answers and for declaring fully supported boxes. This tests whether the model can learn to request evidence before being caught guessing.
The analyses ask three questions. The first is trigger recall: what fraction of pruning-induced errors raise a check, measured on items the full-token model answers correctly and the pruned model does not. The second is recall precision: what fraction of restored tokens fall inside ground-truth object boxes, using COCO annotations for VSR and RefCOCO. The third is whether recall corrects shortcut answers on What'sUp, where object identity is held fixed and only the configuration changes.
Baselines
The naive reference points are the unpruned model with direct answering and the unpruned model with the same program-writing prompt. The second is the accuracy ceiling for our method and isolates the value of code from the value of recall.
The fixed-budget pruners are TokenNMS, Nüwa, IVC-Prune, and uniform average pooling, each run at the same mean token count our method ends up using after recall. For general benchmarks, TokenNMS is the strongest reported general pruner, retaining 97.14% of performance going from 576 to 64 tokens on LLaVA-NeXT-7B. For grounding, Nüwa is the strongest, at 47.2% of unpruned RefCOCO performance at 64 tokens.
We will rerun all pruners ourselves on the same backbones, LLaVA-NeXT-7B and Qwen2.5-VL, with identical prompts. Each method receives the same threshold-tuning budget on held-out data. All computation is counted: encoder, every prefill, and every decoding round.
The most important competitor is a full-fallback cascade. It prunes to the same initial budget, runs the same program and checks, and on any failure re-runs with all tokens.
Two ablations isolate the key ingredient. The first is random recall: the same number of restored tokens per failure, placed uniformly at random. The second is uncertainty-triggered recall: the model is asked whether it needs more detail and names a region, without execution. A third ablation replaces code with free-text reasoning under identical recall, to test whether execution is necessary at all.
Beating the field means three things. On RefCOCO we should clearly exceed Nüwa's 47.2% relative retention at a matched mean of 64–128 tokens. On What'sUp and VSR we should match the unpruned program baseline at under a third of its prefill compute. And we should Pareto-dominate the full-fallback cascade on the accuracy-versus-total-compute curve.
Why not just…?
Why not just use average pooling, which already preserves layout? Nüwa itself reports that simple pooling often beats complex semantic pruning on grounding, so this is a real competitor. Pooling keeps the coordinate grid but blurs small objects and thin boundaries, which are exactly the failure cases in VSR and RefCOCO. We include pooling at matched budgets and as an alternative base pruner under our recall. If pooling plus recall wins, that is a useful finding rather than a refutation.
Why not just re-run at full resolution when the program fails? This cascade is the most serious threat. If failures are rare, its average cost may approach ours. Our advantage exists only if restored regions are small relative to the image and the restored tokens are the right ones. The recall-precision measurement and the head-to-head compute curve settle this directly. If the cascade matches us, the localized-recall half of the claim is false and only the trigger is useful.
Why not just not prune at all, since the code loop provides the accuracy? RECODE shows that code loops are accurate at full resolution. However, the cost multiplies across rounds, and multi-round multimodal contexts exhaust context windows, a 4k-token bottleneck DCoT cites explicitly. The unpruned program baseline measures exactly what we give up in accuracy and what we save in compute.
Why not just ask the model in plain language whether it needs a closer look? Models are confidently wrong on spatial questions: GPT-4o scores 34.98% on ViewSpatial-Bench against roughly 26% chance, with perspective flip-flopping. Self-reports are therefore unlikely to fire when they should. The uncertainty-triggered ablation tests this directly against the deterministic support check.
Proposed Experiments
Primary evaluation uses three benchmarks. What'sUp tests controlled prepositions; humans score 99% and fine-tuned BLIP 56%. VSR has 66 relations, including its concept zero-shot split; models plateau around 70% against 95.4% for humans. RefCOCO, RefCOCO+, and RefCOCOg test grounding.
Secondary evaluation uses ViewSpatial-Bench, where the frame-change function is exercised and the fine-tuned MVSM reaches 82.09%. Transfer evaluation uses ChartQA and Geometry3K, where small tick labels and vertices should trigger recall. Metrics are accuracy, or relative retention against the unpruned model, plotted against mean language-model-visible visual tokens, total prefill FLOPs across rounds, and wall-clock time. We also report trigger recall and recall precision.
Three checks decide the outcome. First, at least half of pruning-induced errors must raise a check; if most failures are silent, the mechanism cannot work. Second, execution-triggered recall must beat random and uncertainty-triggered recall at an equal restored-token count. Third, the method must dominate the full-fallback cascade on total compute at matched accuracy on RefCOCO and VSR. Passing the first two without the third would show that execution is a good damage detector, but that recovering the whole image is just as efficient.
References
- Decoupling Spatial and Semantic Token Compression for Vision-Language Model Acceleration
- Nüwa: Mending the Spatial Integrity Torn by VLM Token Pruning
- IVC-Prune: Revealing the Implicit Visual Coordinates in LVLMs for Vision Token Pruning
- CoverPrune: Coverage-Driven Token Pruning for 3D VLMs via Optimal Transport
- What's "up" with vision-language models? Investigating their struggle with spatial reasoning
- RECODE: Reasoning Through Code Generation for Visual Question Answering
- Synthesize Step-by-Step: Tools, Templates and LLMs as Data Generators for Reasoning-Based Chart VQA
- SpatialThinker: Reinforcing 3D Reasoning in Multimodal LLMs via Spatial Rewards
- DCoT: Dual Chain-of-Thought Prompting for Large Multimodal Models
- Measuring Multimodal Mathematical Reasoning with MATH-Vision Dataset
- CodeTransOcean: A Comprehensive Multilingual Benchmark for Code Translation
- ViewSpatial-Bench: Evaluating Multi-perspective Spatial Localization in Vision-Language Models