When a vision-language model answers a question about a chart or a diagram, a common recipe is to first have it describe the image in text and then reason over that description. This split helps. It also quietly limits what the description can express. A description is a list of things the model claims to see. It has no standard way to say "there is definitely no edge between B and D." It also has no way to say "this line is either the red series or the orange one, I can't tell." Logicians call knowledge bases of this kind Horn: they hold only positive facts and if-then rules with a single conclusion. They cannot state that something is absent, and they cannot hold a genuine either-or. We propose to let the perception step say both things. Each atomic visual fact is reported as present, checked-absent, or uncertain between named alternatives. A small exact logic solver then reasons by cases, and the model looks at the image again only at the specific uncertain facts that would change the answer.
This matters because the bottleneck in multimodal reasoning is mostly perceptual. About 80% of failures on abstract visual puzzles trace to misreading the image rather than to faulty logic (Your Reasoning Benchmark May Not Test Reasoning). The usual repair is to spend more effort on perception everywhere: re-describe, sample several descriptions, zoom into every region. Our bet is that most perceptual uncertainty does not matter for a given question, and the part that does can be found exactly by case analysis. We evaluate on freshly rendered images whose ground-truth facts are known. That lets us measure perception and reasoning errors separately, at the level of individual facts, on data no model can have memorized.
Core Claim
Decoupled perception-then-reasoning pipelines force every visual fact to a single positive guess. Three failures follow. Absent elements are inferred only from silence, so the model treats "I didn't mention it" as "it isn't there." Ambiguous elements are collapsed to one reading. And the model has no principled signal for where to look again.
We claim that a perception interface with explicit absence and explicit disjunction, paired with exact case analysis, fixes all three. Compared with self-consistency sampling at the same number of model calls, it should improve accuracy on questions that hinge on absence or ambiguity, and it should not hurt questions answerable by plain positive chaining.
The central object is a question decomposed into a formula tree whose leaves are perceptual atoms, such as "edge(A,B)" or "series 3 exceeds 40 at x=2010." The perception module returns three things: a set $P$ of atoms asserted true or asserted false after an explicit check, a set $U$ of unresolved atoms, and domain constraints $C$, such as "each line has exactly one color" or "a point belongs to exactly one series." The answer is determined when it agrees across every completion:
$$ q \text{ is determined} \iff \forall\, \sigma \in \mathrm{Sat}(P \cup C,\, U):\; \sigma \models q \;\;\text{or}\;\; \forall\, \sigma:\; \sigma \not\models q, $$
Here $\mathrm{Sat}(P\cup C, U)$ is the set of truth assignments to the uncertain atoms $U$ that are consistent with the confirmed facts and constraints. If $q$ is not determined, the solver computes a smallest subset $S \subseteq U$ whose resolution would determine $q$. Each atom in $S$ becomes a targeted visual query: a crop or zoom plus a yes/no question. The loop repeats until $q$ is determined or the budget runs out. If the budget runs out, the system answers "cannot be determined from the image."
Choosing $S$ is the classical idea behind assumption-based truth maintenance, applied to percepts: track which assumptions each conclusion depends on.
Relation to Prior Work
Two pieces of prior work motivate the proposal.
- Perception is the bottleneck. The two-stage decoupling study (Your Reasoning Benchmark May Not Test Reasoning) converts each puzzle image to an atomistic description and attributes errors by hand-designed stages. It raised GPT-4o on Mini-ARC from 8.05% to 20.13%. Its descriptions are positive-only, though, and its puzzles are static.
- Rereading is needed, but no mechanism exists. Position: Reasoning After Perception Means Reasoning Without Vision argues that a single compressed perception pass discards information and that reasoning should actively query the image again. It shows near-zero frontier accuracy on its Turing Eye Test. It gives no rule for which query to issue. Our minimal-determining-set computation is one such rule.
Three pieces of prior work supply the method or a baseline.
- Perceive, program, execute. VisionGraph's Description-Program-Reasoning pipeline (VisionGraph) has a fine-tuned model write an adjacency matrix, GPT-4V write code, and an interpreter execute it. It lifted easy connectivity accuracy from 69.64% to 92.86%. The flow is one-way: a dropped edge silently becomes "no edge." That is exactly the absence-by-silence failure we target.
- Query trees with grounded leaves. Analytica (Analytica) decomposes queries into trees of testable propositions and grounds the leaves with tools. It argues that Boolean aggregation creates tipping points under noisy leaves, so it uses weighted linear sums instead.
- Deterministic case handling. Consequence-based reasoning for non-Horn description logics (Consequence-Based Reasoning beyond Horn Ontologies) shows disjunctions can be handled deterministically rather than by explosive branching. We borrow that stance, not that algorithm.
Analytica's argument directly opposes ours, and we address it head on. Our hypothesis is that the instability comes from forcing noisy leaves to point values, not from hard logic itself. If the uncertainty is represented as a disjunction, hard logic is only applied to facts that have actually been checked. The experiments compare against linear aggregation explicitly.
We are honest about scale. Scenes contain tens of atoms, so case analysis is trivial for an off-the-shelf SAT or answer-set solver. The contribution is the perception interface and the targeting rule, not reasoning speed.
Three lines of work constrain the evaluation design.
- Static scores collapse under fresh generation. DyVal generates text reasoning tasks from random directed acyclic graphs. Models strong on static leaderboards scored near zero on its tasks. Its logic generators are definite-implication chains with no reasoning by cases.
- Verified generation. A²RBench verifies generated tasks programmatically. It also shows that generators which are themselves language models hit an expressive ceiling.
- Dynamic multimodal generators score end to end. PuzzleBench and vision-language bootstrapping procedurally generate visual tasks but score only end to end.
We therefore generate with a fixed symbolic program rather than a language model. That avoids the generator ceiling and yields exact leaf-level ground truth.
Research Program
We would build three components.
The generator. It samples a scene specification (a set of ground facts), renders it as a graph diagram, bar or line chart, or multi-panel figure with standard plotting libraries, and samples a question formula over the facts. Questions fall into three strata:
- Positive-chaining questions, answerable by Horn-style forward chaining.
- Absence-dependent questions. For example, "is there any path from A to F avoiding red edges," where the answer requires asserting that edges are missing.
- Case-dependent questions. Here rendering knobs (occlusion, overlapping markers, near-identical hues, dense ticks) make some atoms genuinely ambiguous to a careful human. The answer is either invariant across readings or truly undetermined.
The generator records which atoms are ambiguous by construction. A fresh instance set is drawn for every evaluation run, so no reported score depends on images that exist anywhere online.
The solver. It has three parts:
- Decomposer. A language model turns the question into a formula tree over a fixed predicate vocabulary. On generated data we can also supply the oracle tree, which isolates decomposer error.
- Perception module. The vision-language model is prompted per leaf atom to return true, false-after-checking, or a disjunction among listed alternatives.
- Case-analysis core and targeting loop. As defined above.
The attribution harness. Because leaf ground truth is known, we can swap any subset of leaves for oracle values. This splits total error into decomposer error, leaf perception error, and reasoning error given correct leaves. It is exact, unlike the hand-coded four-step attribution in prior work.
Baselines
Naive reference. The same vision-language model answers end to end with chain-of-thought, given the image and question. This is the number every other method must clear. We expect it to be weakest on absence-dependent questions, where rationalized hallucinations are documented (VCBench).
Describe-then-reason. The two-stage pipeline of Your Reasoning Benchmark May Not Test Reasoning, with the same model in both stages. Its reported result is 20.13% success on Mini-ARC with GPT-4o versus 8.05% one-stage. We rerun it on our data rather than compare across datasets.
Describe-program-execute. The adjacency-extraction-plus-code pipeline of VisionGraph. It reports 92.86% on easy connectivity and 24.14% on easy shortest path with GPT-4V. We reproduce it on the VisionGraph test split with our current backbone, so the comparison uses the same model.
Self-consistency at matched calls. This is the strongest competitor on our specific question. It samples $k$ independent full descriptions, runs the solver on each, and takes a majority vote. $k$ is chosen so the total number of perception calls and image tokens matches our method's average. It attacks the same ambiguity by brute force. If our targeting rule has no value, this baseline will tie us.
Soft linear aggregation. Analytica-style weighted aggregation of leaf probabilities over the same formula tree (Analytica). This tests whether hard case analysis beats soft averaging once uncertainty is explicit.
Ablations. Each removes one ingredient:
- No absence: checked-false is replaced by closed-world silence.
- No disjunction: every leaf must be a point guess.
- Random targeting: re-queries go to random uncertain atoms instead of the minimal determining set, at equal budget.
All methods share the backbone model, the decoding temperature, the prompt-tuning budget (the same number of development-set iterations per method), and the image-call budget wherever budget is a free parameter.
Beating a baseline means a higher accuracy on the absence-dependent and case-dependent strata whose 95% bootstrap interval excludes zero, consistent across at least three freshly generated instance sets. It also requires no statistically significant loss on the positive-chaining stratum.
Why not just…?
Why not just sample several descriptions and vote? This is the real threat. On atoms that are hard to see, independent samples may agree on the same wrong reading. Sampling also spends budget uniformly on atoms irrelevant to the question. Neither consideration is established in the file. The matched-budget self-consistency baseline settles it directly. If self-consistency ties us on the case-dependent stratum, we would conclude the disjunctive interface adds nothing beyond more samples and report that.
Why not just zoom into every element? Exhaustive re-querying is the budget-unconstrained upper bound of our loop, so we run it as a ceiling. The question is how close targeted re-querying gets at a fraction of the calls. We report accuracy against the number of perception calls for both methods. Exhaustive zooming also cannot produce a principled "undetermined" answer, so on truly ambiguous instances we expect it to guess.
Why not just fine-tune the vision encoder? Hard-negative CLIP tuning raised retrieval by over 26 points but downstream chart accuracy by only about 3 points (On the Perception Bottleneck of VLMs for Chart Understanding). Encoder tuning on diagnostic tests also failed to transfer out of distribution (Position: Reasoning After Perception Means Reasoning Without Vision). Encoder tuning is also complementary: a better encoder shrinks $U$ but does not tell the reasoner what is absent. We test this by running our loop on top of a stronger backbone and checking whether the gain persists.
Why not just use soft aggregation, as Analytica recommends? Soft averaging cannot represent "exactly one of these is true" or produce a determined answer from an undetermined leaf. It may still be more robust when leaves are confidently wrong. The linear-aggregation baseline over identical trees, broken down by stratum, shows which effect dominates.
Proposed Experiments
Generated benchmark. The first experiment is the full comparison on the generated benchmark across the three strata and four ambiguity levels. We report accuracy, F1 on the "undetermined" label, and perception calls per question.
Exact attribution. The second experiment is the attribution study. Leaves are swapped for oracle values, which quantifies how much error each pipeline loses to perception versus reasoning versus decomposition. In particular, it tests whether describe-then-reason fails on absence questions because of missing "false" atoms rather than misread positive atoms.
Contamination check. The third experiment asks whether gains depend on contamination. We generate a static frozen split and a per-run fresh split from the same distribution and compare the gap across methods. We also apply A²RBench-style token remapping, renaming node labels and series names, to test reliance on surface form (A²RBench).
Transfer to real images. The fourth experiment moves to real images on two benchmarks:
- VisionGraph shortest path and connectivity. Absence of edges is load-bearing here.
- The CharXiv reasoning split (CharXiv). GPT-4o is reported at 47.1% against 80.5% for humans. We use the backbone's own rerun as the comparison point, with leaf predicates limited to a fixed vocabulary of chart facts. We would also hand-label a few hundred CharXiv questions by whether they depend on absence.
Decisive check. The single decisive result is this: on absence-dependent and case-dependent questions, at matched perception budget, targeted case analysis beats self-consistency and random targeting, and the advantage grows with ambiguity level. If the curves coincide, the claim is wrong.
References
- Your Reasoning Benchmark May Not Test Reasoning: Revealing Perception Bottleneck in Abstract Reasoning Benchmarks
- Position: Reasoning After Perception Means Reasoning Without Vision
- VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Context
- Analytica: Soft Propositional Reasoning for Robust and Scalable LLM-Driven Analysis
- Consequence-Based Reasoning beyond Horn Ontologies
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation
- PuzzleBench: A Fully Dynamic Evaluation Framework for Large Multimodal Models on Puzzle Solving
- Dynamic Multimodal Evaluation with Flexible Complexity by Vision-Language Bootstrapping
- Benchmarking Multimodal Mathematical Reasoning with Explicit Visual Dependency
- On the Perception Bottleneck of VLMs for Chart Understanding
- CharXiv: Charting Gaps in Realistic Chart Understanding in Multimodal LLMs