Evidence-Bound Program Decoding for Chart Reasoning

When a vision-language model answers a question about a scientific chart, it often reads the picture well enough but then reasons with things that are not in it: a legend entry that does not exist, a value from the wrong series, an axis tick it made up. We propose to have the model answer by writing a short executable program over the chart. During generation, every place where the program names something from the chart, such as a series, a label, or a numeric reading, is restricted to entries that were actually extracted from the image or retrieved from the figure's caption and surrounding text. Everything else in the program (arithmetic, comparisons, control flow) stays unconstrained. When the model needs a reference that is not in the evidence, it cannot invent one. It must emit an explicit lookup that triggers targeted re-reading of the image or further retrieval, and if that also fails, it must say the question is unanswerable.

The opportunity is concrete. On real arXiv charts, CharXiv reports GPT-4o at 47.1% on reasoning questions against 80.5% for humans, and finds that models routinely hallucinate answers to unanswerable questions. MATH-Vision attributes 42.2% of GPT-4V's errors to reasoning after correct recognition. Grammar-constrained decoding restricts which tokens the model may emit at each step by masking the rest. It is fast and reliable for syntax. It is also known to hurt accuracy in larger models when applied to a whole output, and it has never been used to bind references to perceived evidence. Our bet is that the harm comes from constraining too much, and that the benefit comes from constraining the right handful of tokens.

Core Claim

In chart reasoning, hallucination concentrates at reference sites: the tokens where the model points to an entity or value in the figure. Our claim is that constraining only those sites to a retrieved evidence set, and adding an explicit lookup-or-abstain escape, removes most fabricated references and improves refusal on unanswerable questions. It should do this without the accuracy loss that full-grammar constraints impose on larger models. If the claim holds, the gain over a baseline that places the same evidence in the prompt should come mainly from the model being unable to name what it did not see. Better information alone should not account for it.

The formal object is simple. Let $E_t$ be the evidence set available at step $t$, the extracted and retrieved chart entities plus anything added by earlier lookups. Let $R(y_{<t})$ be true when the partial program $y_{<t}$ is inside a reference slot. Let $T(E_t)$ be a prefix tree over the token spellings of $E_t$ together with the lookup token. The mask applied to the logits $z_v$ of vocabulary item $v$ is then

$$\tilde z_v = \begin{cases} z_v & \text{if } \neg R(y_{<t}) \text{ and } v \text{ is syntactically valid, or } R(y_{<t}) \text{ and } v \text{ extends a prefix in } T(E_t) \\ -\infty & \text{otherwise.} \end{cases}$$

Outside reference slots, only a light syntax check applies, and we will also test turning it off.

Relation to Prior Work

The closest method is Graph-constrained Reasoning (GCR). GCR compiles a retrieved knowledge-graph subgraph into a prefix tree and constrains decoding so that only real reasoning paths can be generated. It reaches a 100% faithful-path ratio, compared with 48–62% unconstrained. We reuse its core technique of a prefix-tree constraint built from retrieved evidence. We depart from it in three ways:

  • Where the evidence comes from. In our setting the evidence is perceived from an image rather than stored in a clean graph.
  • How much is constrained. We constrain only reference slots inside a program, not the whole output.
  • What happens when evidence is missing. GCR's documented weakness is that missing graph entries become unreachable. We replace that failure with a lookup that grows the evidence set during decoding.

Two papers show that retrieval alone leaves the reference problem unsolved, which motivates the proposal:

  • Reducing hallucination in structured outputs via RAG retrieves valid workflow steps and table names into the prompt and decodes greedily. Hallucinated steps still remain below 7.5% but nonzero, and hallucinated tables below 4.5%. - Adaptive Termination in Agentic Multimodal RAG grounds multimodal answers with embedding similarity. It concedes that this measures topical closeness, not whether a claim is actually supported, and it lets its reasoning agent write free text.

Our approach differs from both by enforcing grounding inside decoding rather than checking it in the prompt or afterward.

Three findings constrain the design:

  • Full constraints can hurt capable models. Grammar-Constrained Decoding Makes LLMs Better Logical Parsers shows grammar constraints raise small models' executable rate from near zero to over 60% on FOLIO. For qwen2.5-14b, 5-shot GSM-symbolic accuracy falls from 0.56 unconstrained to 0.36 constrained. This is the result that argues against constraining whole programs, and our reference-only design is a direct response to it.
  • Chain-of-thought is fragile on charts. CharXiv and MATH-Vision show that step-by-step reasoning in natural language behaves inconsistently for multimodal models, because an early misreading contaminates everything downstream. This argues for an intermediate program whose references can be checked, rather than free prose.
  • Programs over charts are a known supervision format. Synthesize Step-by-Step turns chart components into executable rationales for training. We use a similar program format at inference time, with a constraint rather than supervision.

The methods for making masking cheap come from existing engines. GREATGRAMMA reports 5–32 ms of masking overhead per token, and Formatron reports a 2x throughput gain at 100% structural compliance. Either can supply the syntax layer. The evidence prefix tree is small, one per figure, so it adds negligible cost.

The file lists other decoding-time hallucination fixes. KCTS uses tree search with a token-level hallucination detector. ReVisiT reweights logits using the model's internal vision tokens, adding 1–3% inference time. Both are soft interventions on free text. Neither can guarantee that a named entity exists in the evidence, and ReVisiT by design cannot use external retrieval.

Research Program

The system has four parts.

Evidence store. For each figure, we build an index from three sources:

  • a structured reading of the chart produced by the same vision-language model (series names, legend entries, axis labels, tick values, and, where the model estimates them, data points with a confidence score);
  • optical character recognition of all visible text;
  • retrieval of the caption and nearby paragraphs, where the benchmark provides the source paper.

Each entry becomes a typed terminal: a series, a label, a number with its source, or a subplot identifier.

Program language. The model writes in a small Python subset with typed accessor functions such as series lookup, value-at-tick, subplot selection, argmax, and difference. Every argument that names chart content is a reference slot.

Decoding. The syntax layer is optional and is ablated. The reference layer applies the evidence prefix tree. A LOOKUP("…") escape is always available inside a reference slot, and UNANSWERABLE is a legal program.

Lookup. A lookup runs a targeted re-read, cropping the relevant image region and asking the model a narrow extraction question, or runs a retrieval query over the paper text. The result is added to $E_t$ and decoding resumes. A cap of three lookups bounds the cost.

Analysis. The main analysis measures where hallucinations occur. We will annotate a sample of unconstrained program outputs and free-text answers, labeling each error as a fabricated reference, a wrong but real reference, an arithmetic or logic error, or a misreading. The core claim predicts that fabricated references form a large share of CharXiv reasoning errors. If they are rare, the method has little to fix, and we will report that.

Baselines

Do nothing (direct answering). The reference point is the backbone vision-language model answering directly with chain-of-thought prompting, in its standard evaluation setup. We will use Qwen2.5-VL-7B, the model ReVisiT evaluates on, plus one smaller and one roughly 14B-scale open model. For context, CharXiv reports GPT-4o at 47.1% reasoning accuracy and InternVL Chat V1.5 at 29.2%. No reported result was found on Lacuna for Qwen2.5-VL-7B on CharXiv, so we will measure it ourselves under the benchmark's protocol.

Evidence in the prompt, unconstrained program (strongest competitor). This baseline isolates our key ingredient. The model receives exactly the same evidence store as text in its prompt, including caption retrieval. It writes the same program language with no reference constraint, and on execution failure it gets up to three retries with the error message. This is structured retrieval in the style of Reducing hallucination in structured outputs via RAG, combined with program execution and self-repair. It is the strongest competitor because it has every piece of information our method has. It also gets a matched compute budget: its retries are sized to equal our lookups in total forward passes.

To beat it, our method must meet two conditions on CharXiv reasoning. It must improve accuracy, or at least not lose accuracy, at every model scale. It must also cut the fabricated-reference rate and improve accuracy on unanswerable questions, with confidence intervals from bootstrap resampling over questions that exclude zero. No reported result was found on Lacuna for program-based answering on CharXiv.

Full-grammar constraint. This baseline constrains the entire program with a grammar through a GREATGRAMMA- or Formatron-style engine, with evidence entities compiled into the grammar's terminals. It tests the Logical Parsers concern directly. We expect it to match our method on small models and fall behind on the larger one.

Soft decoding-time guidance. ReVisiT applied to free-text answers, run with its published settings on the same backbones, represents the soft-guidance line of work.

Ablations.

  • Reference constraint without the lookup escape. This reproduces the GCR-style incompleteness failure and should hurt when extraction is incomplete.
  • Lookup escape without the constraint. The model may call lookup but may also name anything.
  • Evidence restricted to image extraction only. This drops caption retrieval and measures what the retrieval component contributes.

Tuning is matched throughout. Each method gets the same prompt-development set of 200 CharXiv validation questions and the same number of prompt variants.

Why not just…?

Why not just put the extracted table in the prompt and let the model write code? This is the real threat, and it is why the evidence-in-the-prompt baseline exists. Reducing hallucination in structured outputs via RAG shows that prompt-level evidence cuts fabricated names sharply but leaves a residue under 7.5%. GCR shows that prompted triples yield only 48–62% faithful paths, against 100% under decoding constraints. We are not assuming chart evidence behaves the same way. If our method's advantage over that baseline is within noise on accuracy, fabricated-reference rate, and unanswerable-question accuracy, the constraint adds nothing, and we will say so.

Why not just constrain the whole program with a grammar? On the file's evidence, full constraints tax capable models: qwen2.5-14b drops from 0.56 to 0.36 on GSM-symbolic in Logical Parsers. Our hypothesis is that the tax comes from masking reasoning tokens. The scale sweep comparing full-grammar and reference-only constraints tests this directly. If full grammar causes no harm on charts at 14B, reference-only is simply the cheaper equivalent.

Why not just run unconstrained, execute, and re-prompt on errors? Execution catches only crashes. A program that references a real but wrong series, or a value the model invented and typed as a literal, runs without error. The evidence-in-the-prompt baseline already includes this retry loop, so its residual fabricated-reference rate measures what execution feedback misses. OmniSearch also shows that iterative agents can fall into repeated hallucination loops on dense visuals.

Why not just use soft decoding guidance such as ReVisiT? Soft reweighting favors visually salient tokens but cannot exclude an entity that is absent, and it has no path to retrieved text. We include it as a baseline. Our expectation is that it helps object-level captioning more than multi-step chart questions.

Proposed Experiments

Main benchmark. The primary benchmark is CharXiv, using the reasoning split, the unanswerable subset, and the multi-subplot figures, where CharXiv reports 30–50% degradation for open models. Metrics are:

  • reasoning accuracy;
  • accuracy on unanswerable questions;
  • fabricated-reference rate, meaning the fraction of referenced entities absent from the figure, computed on a 500-question subset where we annotate ground-truth chart entities;
  • wall-clock latency per question and number of lookups.

Second benchmark. VeriSciQA, described in its paper, tests generalization across 20 domains and 12 figure types. Its construction from citing text also gives natural retrieval passages for the caption-retrieval component.

Negative control. We use MATH-Vision's arithmetic and transformation-geometry subjects. There, errors are mostly spatial and deductive rather than referential, so the method should give little gain. A large gain there would suggest our improvements come from something other than binding references, such as better program formatting.

Decisive checks. Four results decide the outcome:

  1. The gap between our method and the evidence-in-the-prompt baseline on fabricated references and unanswerable-question accuracy.
  2. Whether the reference-only constraint avoids the scale-dependent accuracy drop that full-grammar constraints show between the 7B and roughly 14B backbones.
  3. Whether removing the lookup escape reproduces the incompleteness failure. This should show up as more wrong refusals and forced wrong references on questions whose entities the first extraction missed.
  4. Whether the size of the gain tracks the error analysis. Improvements should be largest in the categories where fabricated references dominate.

If the first check fails, we abandon the constraint and report that prompt-level evidence is enough. If the second fails, the result becomes a negative finding about constraints on capable models.