Systems that answer questions about charts, diagrams, and drawn graphs increasingly split the job in two. A vision model turns the image into symbolic facts, such as edges or data values. A language model then writes a small program that computes the answer from those facts. When the final answer is wrong, nobody can say which half failed. The program may be fine and the facts wrong, or the facts may be fine and the program subtly wrong. This note proposes closing that ambiguity using strong equivalence. Strong equivalence comes from logic programming: two programs are strongly equivalent if they produce the same answers whatever extra rules or input facts are added to them. Checking it reduces to a finite search for a small counterexample. If the language model writes its reasoning program in a logic language, we can check whether alternative programs for the same question behave identically on every possible input, rather than on the one input that perception happened to produce. Once the reasoning half is certified this way, any remaining error has to come from perception. We can then spend the verification budget only on the perceived facts that the certified program actually depends on.
This matters because the evidence says perception is the dominant failure. Perception errors account for about 62% of Gemini 2.0 Flash's errors on elementary visual math (VCBench), and scaling the captioning stage beats scaling the reasoning stage (CodePercept). Yet the generated programs are also unreliable: verifying programs lifted script execution accuracy by up to 39.4% in VLAgent. Current pipelines test the two halves together on a single noisy input, so the two error sources stay tangled.
Core Claim
Our central observation is that the input-independence guarantee from logic programming is exactly the property missing from neurosymbolic visual question answering. There is a relevant equivalence notion for each kind of context the reasoning program may meet. Two programs are uniformly equivalent if they agree on every set of input facts. Here the input facts are whatever the perception module emits, so uniform equivalence means "these two programs give the same answer no matter what perception reports." Strong equivalence additionally allows arbitrary added rules. That is the right notion when a question program is later combined with reusable background modules, such as a rule for reading dual-axis charts or a rule that flags unanswerable questions.
The theory says both checks are decidable and usually manageable at the scale we need. For propositional programs, strong equivalence is coNP-complete, and non-equivalence is witnessed by a single "here-and-there" model. That is a pair of atom sets $(X,Y)$ with $X \subseteq Y$, and it translates directly into a concrete distinguishing context (Lin and Chen; Truszczynski). Removing recursion does not make the check easier, since stratified and acyclic programs remain coNP-complete (Eiter et al.). It does not get worse either, which matters because generated question programs are almost always stratified.
We claim that grouping sampled programs by certified behavioral equivalence, rather than by their output on the perceived input, gives three things. First, it gives a reasoning answer that is robust to perception noise. Second, it gives small counterexample inputs that the language model can use to repair its own program in text alone. Third, it gives a principled list of answer-relevant facts to send back for independent visual re-checking.
The perception-side check is deliberately not strong equivalence. Two sets of facts are strongly equivalent only if they are identical, so applying the machinery there would be trivial. The formal tools earn their place on the program side. The perception side benefits indirectly, because the program can now be trusted.
Research Program
Program generation. For each question, a multimodal model first extracts facts from the image into a fixed vocabulary per domain. For graphs, this is nodes, edges, and weights. For charts, it is series, categories, discretized values, and axis metadata. Separately, a language model sees the question and the vocabulary, but not the image. It writes $k$ candidate answer programs in a restricted fragment of Answer Set Programming, a logic language in which programs define their outputs as "stable models." The fragment is stratified normal rules plus integer comparisons that are evaluated when the program is expanded into variable-free form ("grounded"). We exclude aggregates at first, because the equivalence characterizations in the file do not cover them. We will report what fraction of questions in each benchmark is expressible in this fragment, since coverage is a real risk.
Bounded checking. Uniform equivalence for programs with variables is co-NEXPTIME-hard for strong equivalence and undecidable once negative constraints appear (Eiter et al.). We therefore check equivalence over a bounded domain. The bound covers the size of the perceived instance plus slack, for example up to 25 nodes, matching the largest graphs in VisionGraph. Within that bound the check is propositional. We encode the search for a distinguishing here-and-there model as a satisfiability problem in the standard way and solve it with an off-the-shelf solver. Any guarantee is therefore "equivalent on all instances up to size $n$." We will state that plainly rather than claim unbounded certification.
Semantic voting and repair. Pairwise checks partition the $k$ programs into behavioral classes. When classes disagree, the solver returns a minimal distinguishing instance, for example a four-node graph with a tie in path weight or a chart with an empty series. The language model is shown this tiny instance as plain text and asked which output is correct. This adjudication involves no perception at all, so it is exactly where MIRAGE's finding applies: correcting reasoning chains alone recovers about 70% of failures (MIRAGE). The winning class becomes the certified program.
Answer-relevant perception checks. Given the certified program and the perceived facts, we compute which individual facts would change the answer if added, removed, or perturbed by one discretization step. An independent re-extraction, in the style of BeaconChart, is run only on those facts. BeaconChart's verifier re-checks fields chosen by a planner, so a wrong planner means the wrong fields get checked. In our design the fields to check are chosen by the semantics of a certified program instead.
Reusable background modules. Chart conventions and corrective lessons are stored as logic rules rather than BeaconChart-style natural-language notes. Strong equivalence is what makes this library safe to use. A new question program can be replaced by a cached, previously verified one when the two are strongly equivalent, because the guarantee holds whatever background rules are added. New corrective rules can likewise be tested for redundancy against the existing library, using simplification patterns of the kind Lin and Chen discovered.
Baselines
The naive reference point is the backbone multimodal model answering directly, with and without chain-of-thought prompting. On CharXiv reasoning, the file reports 47.1% for GPT-4o and 29.2% for InternVL Chat V1.5 (CharXiv). On ChartX, base Qwen3-VL-32B is reported at 63.45%, a figure derived from BeaconChart's stated 8.6-point gain.
The strongest existing chart method is BeaconChart. It is a plan, extract, and verify pipeline with an independent re-extracting verifier and a memory of corrective instructions. It reports 91.60% on ChartQA and 72.05% on ChartX with Qwen3-VL-32B, and it raises error detection given failure from 27.95% to 54.15% (BeaconChart). It is the strongest competitor because it already attacks the perception error cascade with independent verification. We will run it with the same Qwen3-VL-32B backbone and the same total generated-token budget per question. Our method must beat 72.05% on ChartX at equal or lower token cost to count as an improvement. Matching it at substantially lower cost would be a secondary success.
On graph problems, the strongest method is VisionGraph's Description-Program-Reasoning pipeline (DPR). It uses a fine-tuned describer, a generated Python program, and an interpreter. It reports 92.86% on easy Connectivity and 24.14% on easy Shortest Path, against near 0% zero-shot (VisionGraph). We reuse its describer, so that only the reasoning and verification stages differ.
The key ablation is execution-based self-consistency. It samples the same $k$ programs, runs each on the perceived facts, and takes a majority vote over outputs. This isolates our central ingredient, voting over behavior on all inputs versus behavior on one input.
A second ablation is differential fuzzing. It replaces the exact equivalence check with $N$ random synthetic instances and lets the same compute budget pick $N$.
A third ablation keeps the certified program but runs BeaconChart-style full re-extraction instead of the answer-relevant re-check. This separates the value of the program-side certification from the value of the targeted perception check.
Why not just…?
Why not just majority-vote the programs' outputs on the perceived input? It is cheap, and on clean inputs it may match our method. Its weakness is structural. Two programs can agree on a misperceived instance and disagree on the true one, and output voting cannot tell "the programs disagree" apart from "the perception is wrong." The ablation will settle this. On VisionGraph, ground-truth graphs are available, and we can measure how often execution voting selects a program that fails uniform equivalence with the reference encoding. If that rate is near zero and downstream accuracy is equal, the formal check adds nothing on these benchmarks, and we will report that.
Why not just fuzz the programs on random inputs? This is the most serious threat. Random testing approximates uniform equivalence and needs no theory. Our bet is that disagreements between generated programs cluster in corner cases that random sampling rarely hits, such as ties, empty sets, and rules triggered by negation. The non-trivial coNP-hardness of the stratified case suggests these corner cases are combinatorially sparse. We will report, at matched wall-clock time, the fraction of truly inequivalent program pairs that fuzzing misses and the resulting accuracy gap. If fuzzing closes the gap, the honest conclusion is that the contribution is the decomposition and the targeted perception check, not the solver.
Why not just hand-write reference programs per task? For VisionGraph's eight fixed algorithms, this is correct, and there we use reference programs only to validate the checker. CharXiv, ChartQA, and VCBench pose open-ended questions with no fixed program library. That is why candidate programs must be generated and why certifying them across samples is necessary.
Why not just scale the model or use CodePercept-style code perception? Scaling leaves CharXiv reasoning 33.4 points below human performance, and spatial hallucinations persist under scale (MIRAGE). CodePercept improves the perception module itself and is complementary rather than competing. Its pixel-match reward says nothing about whether the downstream reasoning is correct. We will plug a stronger perception module into our pipeline if one is available.
Proposed Experiments
The first experiment is a decomposition study on VisionGraph using ground-truth graphs. Running certified programs on gold facts gives the reasoning ceiling. Running them on perceived facts gives the perception-limited accuracy. This yields a cleaner perception-versus-reasoning split than captioning-based studies, because the reasoning half is verified rather than sampled. We expect Shortest Path to show most of its remaining gap on the perception side, consistent with VisionGraph's diagnosis that models omit weighted edges.
The second experiment is the head-to-head on ChartX, ChartQA, and CharXiv reasoning against BeaconChart and DPR-style pipelines with matched backbone and token budget. We report accuracy, cost, and BeaconChart's error-detection-given-failure metric, and we compute that metric for our answer-relevant re-check as well.
The third experiment covers coverage and solver cost. It reports the fraction of questions expressible in the fragment, and the median and tail checking time at domain sizes 10, 25, and 50.
Two outcomes would decide the claim. The first is whether exact equivalence voting beats both execution voting and fuzzing on questions where they disagree. The second is whether answer-relevant re-checking matches full re-extraction at a fraction of the tokens. If neither holds, the proposal reduces to a measurement tool, which is still useful but much smaller.
References
- Benchmarking Multimodal Mathematical Reasoning with Explicit Visual Dependency
- CodePercept: Code-Grounded Visual STEM Perception for MLLMs
- A Neurosymbolic Agent System for Compositional Visual Reasoning
- Discovering Classes of Strongly Equivalent Logic Programs
- The Modal Logic S4F, the Default Logic, and the Logic Here-and-There
- Complexity Results for Checking Equivalence of Stratified Logic Programs
- VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Context
- MIRAGE: Assessing Hallucination in Multimodal Reasoning Chains of MLLM
- BeaconChart: Verifier-Guided Corrective Instruction for Chart Understanding
- CharXiv: Charting Gaps in Realistic Chart Understanding in Multimodal LLMs