Certified Minimal Visual Evidence for Detecting Language-Prior Answers

Vision-language models often answer a question about an image from the question text alone. A model asked "what color is the banana?" says yellow whether or not the banana in the picture is green. Current fixes train the model to rely on one bounding box as its evidence: they cover the box and reward the model when its confidence drops. Many questions need more than one region, though. Counting, relative position, and comparing two objects all depend on several regions together. None of these fixes checks whether the evidence the model relies on is actually sufficient, or whether any image content was needed at all.

We propose to treat "which parts of the image does this answer depend on?" as a small minimal-explanation problem, sized so it can be computed exactly. The image is split into a few dozen regions. We then search for the smallest set of regions that keeps the answer stable when everything else is replaced with plausible filler. A key point follows from this definition. An answer driven by the language prior is one for which the empty set already suffices: no image content has to be kept for the answer to survive. The minimum worst-case size of such an explanation is provably hard to find. Still, with a pruned vocabulary of a few dozen regions, we can check every subset of size one, two, or three. We therefore get a certificate that no smaller evidence set exists, and we use it both to diagnose shortcut answers and to supply a multi-region training reward.

Core Claim

For an image $x$ split into regions $R$, a question $q$, and a model answer $f(q,x)$, define the stability of a region set $S \subseteq R$ as

$$\rho_x(S) = \Pr_{z \sim \mathcal{D}}\big[f(q,\, x_S \oplus z_{R\setminus S}) = f(q,x)\big],$$

where $x_S \oplus z_{R\setminus S}$ keeps the regions in $S$ and fills the rest from a completion distribution $\mathcal{D}$. The completion distribution can be mean-token replacement, noise patches, or inpainting. $S$ is $\delta$-relevant when $\rho_x(S)\ge\delta$. This is the probabilistic sufficient-reason notion that The Computational Complexity of Understanding Binary Classifier Decisions analyzed for Boolean circuits.

We define a grounding certificate as a set $S$ with three properties. First, $S$ is $\delta$-relevant. Second, the empty set is clearly not: $\rho_x(\emptyset) < \delta-\gamma$, where $\gamma$ is a fixed gap. Third, every subset of $R$ smaller than $|S|$ has been checked and fails.

The claim has three parts. First, prior-driven answers are exactly the instances where $\rho_x(\emptyset)\ge\delta$. Second, visual shortcuts show up as small certificates that sit on the wrong object, which the blind "remove the image" test cannot detect. Third, on natural images the minimal certificates are small enough, usually three regions or fewer, that exhaustive certification over a pruned vocabulary is affordable. The hardness results do not forbid this, because they concern worst-case circuits and unbounded explanation size, not a model's behavior on natural images.

Where This Sits

Three bodies of work each supply one part of this proposal.

The complexity results constrain the design. Waeldchen et al. show that deciding whether a small $\delta$-relevant set exists is $\text{NP}^{\text{PP}}$-complete. They also show it cannot be approximated within $d^{1-\alpha}$ even in the gapped, sampling-based version. The Parameterized Complexity of Finding Concise Local Explanations shows that minimum anchors are W[2]-hard when parameterized by explanation size $k$. Both results rule out a black-box method that promises near-minimal explanations over thousands of pixels. For a fixed small $k$ and a vocabulary of about 30 regions, however, exhaustive checking is polynomial and cheap, and we design around exactly that regime. VeriX and On the Computation of Necessary and Sufficient Explanations compute exact minimal explanations using solvers or compiled circuits. That requires white-box discrete models, which a multi-billion-parameter vision-language model is not. We give up exactness over all subsets in exchange for exactness up to size $k$ under sampling.

The shortcut literature motivates the problem. Evidence-RL rewards answers whose confidence drops more when an evidence box is mean-replaced than when other boxes are. CofactGVR compares a predicted box against a random noisy patch. Both score one region at a time and never test sufficiency or minimality, and CofactGVR's authors note it has no mechanism to decide whether looking at the image is necessary at all. VQA-VS shows that shortcuts include key objects and question-object combinations, not only question text. A text-only diagnostic therefore misses part of the problem.

The feature-selection literature supplies the search method. OpenFE tames large candidate pools with two tools. The first is successive halving on growing data samples. The second is scoring each candidate by how well it fits the residual of a base model. We reuse both, with one reinterpretation. The base model is the answer distribution under the empty evidence set, which is the language prior. A region's score is its incremental log-probability gain over what the prior already predicts.

Research Program

The system has three stages. In the first stage, each image is split into class-agnostic regions (roughly 20 to 40 segments, merged from superpixels). We add a few coarse background cells so that non-object evidence such as texture or text layout can also be selected.

In the second stage, we score and prune regions. Each region $r$ gets a residual score. The score is the average gain in the log-probability of the model's answer when $r$ is added to the currently kept set, measured over completion samples. Following OpenFE's Stage I, all regions are scored with a few completion samples, the bottom half is discarded, and the sample count is doubled for the next round, until about 8 to 12 regions survive.

In the third stage, we certify. We estimate $\rho_x(\emptyset)$ first. If it clears $\delta$, the instance is labeled prior-sufficient. Otherwise we check every subset of the survivors in order of increasing size, up to $k=3$, and stop at the first $\delta$-relevant set. Each check is a gapped sampling test with a Hoeffding-style sample count. We report the certificate only relative to the pruned vocabulary and the chosen $\mathcal{D}$, and state it that way. The pruning step is the only place where minimality over the full region set can be lost. We measure that loss on a subsample by running the exhaustive check over all regions.

Two methodological questions receive direct study. The first is the completion distribution. Mean replacement and noise produce off-manifold images. Inpainting stays on-manifold but can reintroduce the prior itself, for example by painting a yellow banana. We run every diagnostic under two completion families and accept only conclusions that hold under both.

The second is use as a training signal. We replace Evidence-RL's single-box confidence-drop bonus with a certificate bonus. The bonus is paid when the answer is correct, the empty set is not sufficient, and a certificate of size at most $k$ exists and overlaps the regions that the question refers to. A per-rollout search is too expensive, so the certificate is computed once per training question for the reference answer. During reinforcement learning, only the cheap test "does the rollout's answer survive under this certificate, and fail under the empty set?" is run.

Baselines

The naive reference point is the model with no evidence analysis. For diagnosis, that means predicting errors from the model's own answer confidence. For training, it means the base backbone evaluated zero-shot. FREAK reports 42–45% for the best frontier models against 86.71% for humans (FREAK). HallusionBench reports 31.42% question-pair accuracy for GPT-4V and below 16% for open-source models (HallusionBench). These numbers frame how much room there is.

The strongest existing training method is Evidence-RL. It reports a +14.22% absolute gain on FREAK over its base model, but the file does not give the base score for a specific backbone. We will therefore reproduce it on Qwen2.5-VL-7B, one of its published backbones. The reproduction uses the same filtered COCO val2017 training subset, the same GRPO step count, and the same rollout budget as our certificate-reward variant. Beating it means a higher FREAK accuracy than our reproduction, with the gain concentrated in the Counting and Position tasks where multiple regions matter, and no loss on MMMU or ScienceQA. For HallusionBench under Evidence-RL there is no reported result found on Lacuna, so we will measure it ourselves. CofactGVR is a second trained reference. Its MME score of 2428.5 and its 78.7-point MME drop under random-region intervention give a sanity check that any grounded model we train should also show a large drop.

The strongest diagnostic baseline is the blind test: compare the answer with the full image against the answer with the image removed. We will also run greedy anchor-style deletion, which adds the region that most increases stability until the set reaches $\delta$. This is the strongest search competitor. Two further search baselines are top-$k$ attention or gradient saliency and Evidence-RL's single best box. All search baselines get the same model-query budget per instance. For minimal explanation sizes on vision-language models, we found no reported result on Lacuna, so every search baseline is run by us.

Three ablations isolate the key ingredients. The first drops the empty-set condition, which tests whether prior-sufficiency detection is what matters. The second caps certificates at $k=1$, which reduces to a single-region reward like Evidence-RL's. The third replaces residual-over-prior scoring with scoring against a blank-image base, which tests whether the OpenFE-style residual adds anything.

Why not just…?

Why not just run the model with and without the image? This blind test is a real threat for the text-prior case, because it measures roughly the same thing as $\rho_x(\emptyset)$. It has two weaknesses. Removing the whole image is itself a distribution shift, so an answer can change because the image is absent rather than because the prior is weak. More importantly, it says nothing about visual shortcuts, where the model looks only at a salient key object that happens to correlate with the answer. VQA-VS shows these shortcuts cause drops of 6.46% to 31.82% on its OOD splits. We will compare how well each signal predicts errors (AUROC) on VQA-VS key-object and question-object splits and on HallusionBench. If the blind test matches the certificate on the visual-shortcut splits, we drop the diagnostic claim and keep only the training use.

Why not just use greedy deletion instead of certification? Greedy search may find sets nearly as small as ours at the same budget, and the worst-case inapproximability result offers greedy no guarantee but does not predict that it fails on natural images. If greedy matches on size, the remaining contribution is the lower bound: greedy cannot tell a model-intrinsic three-region dependency from a search failure, while exhaustive checking up to $k$ can. We will report how often greedy sets are provably non-minimal, and treat a rate near zero as evidence that certification is unnecessary for the reward.

Why not just score several boxes independently, as Evidence-RL does with one? Independent scores miss conjunctions. A counting answer may survive when either of two apples is removed but not when both are, so each apple alone looks irrelevant. The FREAK Counting and Position subsets and CountBench test this directly. The $k=1$ ablation is the version of this alternative that controls for everything else.

Why not just use saliency maps? Saliency ranks regions but never checks that the top regions are sufficient on their own. We will report the fraction of top-$k$ saliency sets that reach $\delta$-relevance at the same size as our certificates.

Proposed Experiments and Decisive Checks

The first experiment is diagnostic and uses HallusionBench's 181 edited images with their originals. Differencing each pair gives the edit location. The prediction is that when the model answers an edited image wrongly, its certificate is either prior-sufficient or disjoint from the edited region, and that correct answers have certificates overlapping it. We measure error-prediction AUROC and the overlap between certificates and edit locations, against the blind test and greedy search. We repeat this on FREAK, using its edit locations where available, and on VQA-VS OOD splits using the released code (PhoebusSi/VQA-VS).

The second experiment tests tractability. We plot the distribution of certified minimal sizes and the model queries per instance. We check how much pruning loses against full exhaustive checking on 500 instances, and whether conclusions agree between mean-replacement and inpainting completions. If most certificates on FREAK and VQA-VS exceed size three, the core claim that natural answers have narrow evidence fails, and the method would need structural parameters such as region-graph width. The anchor complexity results suggest such parameters, but we do not assume them.

The third experiment is the training comparison against the reproduced Evidence-RL. Evaluation covers FREAK by task, HallusionBench question-pair accuracy, the VQA-VS OOD splits, CountBench, MMMU, and ScienceQA, all under matched compute. The result would favor this proposal if the certificate reward beats Evidence-RL on the multi-region FREAK tasks and on the VQA-VS visual-shortcut splits, while the $k=1$ ablation does not.