Image-Aware Lookahead for Grammar-Constrained Decoding in Vision-Language Models

Vision-language models (VLMs) are language models that read an image after a small learned layer, the projector, converts the vision encoder's features into vectors the language model treats as extra input tokens. They are increasingly asked to turn an image into machine-readable output: a chart into plotting code, a scanned table into HTML, a form into JSON. Text-only work already shows how to make output syntactically valid. A decoder can check every token against an automaton, a small state machine that accepts exactly the valid strings, and it can be built to guarantee that a valid ending is still reachable within the token budget. The harder problem is that forcing validity bends the model's output distribution, and the best fix so far uses a cheap surrogate model to look ahead and judge which valid continuations the language model is likely to prefer. In every existing system that surrogate reads only text. When the right structure depends on the picture (how many bars, how many table rows, which plot type), a text-only lookahead is guessing blind.

We propose to give the lookahead model the image. A small projector, trained on the VLM's own visual tokens, maps them to the starting-state distribution of the surrogate model. That surrogate is a hidden Markov model (HMM), a simple probabilistic sequence model whose agreement with an automaton can be computed exactly. Because only the starting distribution depends on the image, the exact HMM-times-automaton computation keeps the same per-step cost. The claim is concrete. Syntactic validity is cheap to obtain. Content accuracy under constraint is not, and the missing ingredient is cross-modal projection into the proposal model, not into the language model.

Core Claim

Two text-only methods supply the machinery. Mitigating Bias in Locally Constrained Decoding via Tractable Proposals represents constraints as GPU-tensorized automata. Its globally constrained decoding (GCD) guarantees that a valid completion remains reachable, at about 1.1x overhead. Its probabilistic variant (P-GCD) multiplies the automaton with an HMM distilled from the language model to propose tokens inside sequential Monte Carlo (SMC), which samples many partial outputs and reweights them toward the target distribution. Decoupling Task-Solving and Output Formatting in LLM Generation uses the same HMM-plus-automaton combination to steer an unconstrained model to 100% format adherence. On GSM8k with Qwen2.5-7B this lifted accuracy to 88.6%, against 82.7% when the format was demanded in the prompt. Both distill the HMM over text corpora and evaluate only on text tasks.

Our conjecture is that in a VLM these lookahead weights are wrong in an image-dependent way. Whether a partial JSON object should close after three entries or seven is decided by the image. An HMM trained without the image can only express the average over images.

Formally, let $v$ be the VLM's projected visual tokens and $g(v)$ their mean-pooled vector. We set the HMM's initial hidden-state distribution to

$$\pi(z_1 \mid v) = \mathrm{softmax}(W\, g(v) + b),$$

where $z_1$ is the first hidden state and $W, b$ are the only image-dependent parameters. The transition and emission matrices stay shared. The SMC proposal at step $t$ is then

$$q(x_t \mid x_{<t}, v) \propto p_{\mathrm{VLM}}(x_t \mid x_{<t}, v)\; \Pr_{\mathrm{HMM}}\big(\text{reach an accepting automaton state within budget} \mid x_{\le t}, v\big).$$

Here $x_t$ is the token at step $t$ and $p_{\mathrm{VLM}}$ is the VLM's next-token distribution. The second factor is computed exactly by the forward algorithm on the HMM–automaton product. Conditioning only $\pi$ changes the initial vector of that computation and nothing else, so inference cost matches text-only P-GCD.

Relation to Prior Work

Several papers motivate the gap. Reading or Reasoning? Format Decoupled Reinforcement Learning for Document OCR finds that VLM token entropy on tables and formulas is an order of magnitude higher than on plain text. This is exactly where a lookahead that knows the image should matter most. Words or Vision: Do Vision-Language Models Have Blind Faith in Text? shows VLMs over-weight text when it conflicts with the image. A text-only proposal adds another text-driven prior on top of that bias. A long schema in the prompt is one such text signal.

Two other papers work at the projector. ChartMoE specializes connector experts toward tables, JSON and code, reaching 84.64% on ChartQA, but decodes without constraints. Deep Pre-Alignment for VLMs improves how visual features enter the language model but never measures structured output. Both change the projection into the language model. We leave the VLM untouched and project into the decoder's surrogate.

Two reinforcement-learning papers are the main competitors on our benchmarks. Breaking the SFT Plateau tunes the model with execution and rendering rewards. FD-RL, the document-OCR paper above, tunes it with format-specific rewards. Both change weights and leave inference unconstrained. Our method is complementary to them and can be stacked on top.

Research Program

We first build the constraints. These are bounded-depth JSON schemas for chart attribute extraction, using the schemas implied by ChartMoE-Align. We also build fixed-arity CSV and bounded-nesting HTML table grammars for document tables. Finally we build a restricted, bounded-nesting Matplotlib subset for chart-to-code. Python is not regular, so the code automaton is an approximation. We report execution rate separately to expose what it misses.

We next distill two HMMs from samples of the same open 7B VLM. Training images come from ChartMoE-Align, Chart2Code-3M and document pages disjoint from OmniDocBench. The first HMM is unconditioned. The second has the image-conditioned initial state and is trained jointly with $W$ by gradient ascent on forward-algorithm likelihood.

DECO-G needed millions of text pairs. We will chart likelihood and downstream accuracy against sample count from roughly 50k to 1M to find how much paired data image conditioning actually needs.

Finally, we analyze where gains come from. One measurement is the SMC effective sample size. Another is the KL divergence (a measure of how far one distribution is from another) between the proposal and the VLM's constrained target. We also stratify results by how much the image determines structure, for example the number of series or rows.

Baselines

The naive reference is the VLM decoding freely with the schema described in the prompt. The file reports no number for this exact configuration on our base model. As context, ChartMimic reports that several smaller open models fall below 50% execution success, while GPT-4o reaches 93.2% execution and 81.2 on Direct Mimic. Above that sit token-by-token grammar masking (locally constrained decoding) and GCD, run with identical automata and token budgets. GCD is the cheap validity floor that any proposal method must beat on content, not on validity.

The strongest decoding competitor is P-GCD with an unconditioned HMM distilled on the same VLM's multimodal samples. It is the cleanest ablation of our key ingredient, because it sees the same data, same HMM size and same particle count, and lacks only the image projection. A further control uses our conditioned HMM but feeds it a randomly mismatched image. If gains survive mismatched images, the projector is not carrying visual information.

The strongest trained competitors are MSRL and FD-RL. On ChartMimic, MSRL reports 96.5% execution and an 83.8 high-level score Breaking the SFT Plateau. On OmniDocBench, FD-RL reports a 90.41 average and 87.35 table TEDS Reading or Reasoning?. Where we cannot reproduce their models, we compare to these published numbers using the same base-model size. We also apply our decoder on top of an RL-tuned checkpoint where one is available.

All decoding methods are compared at matched wall-clock time, with particle counts adjusted so that P-GCD variants are not granted extra compute. The HMM distillation budget is identical across the conditioned and unconditioned HMMs.

Beating the competitors means three things. Validity must be 100% under the automaton. Content must improve significantly over unconditioned P-GCD at matched compute. On ChartMimic, our decoder on top of the base model must close a meaningful fraction of the gap to MSRL's 83.8 without any weight updates.

Why not just…?

Why not just use GCD, which already guarantees validity at about 1.1x cost? This is the real threat. If GCD's outputs on charts and tables are as accurate as any proposal-based method, the lookahead model is unnecessary. The first experiment measures the content gap between GCD and P-GCD with an unconditioned HMM on ChartMimic and OmniDocBench tables. If that gap is negligible, we stop and report a negative result rather than add image conditioning.

Why not just distill the existing text-only HMM on VLM outputs and skip the image projector? This baseline captures the output style of image-conditioned generation, but it averages over images by construction. It is our central ablation. If the conditioned HMM does not beat it, and the gain does not concentrate on image-determined structure, the cross-modal piece adds nothing.

Why not just run more SMC particles with the unconditioned proposal? More particles can repair a poor proposal at higher cost. We plot accuracy against wall-clock time for both proposals. The claim holds only if the conditioned proposal dominates that curve, rather than merely winning at one particle count.

Why not just train with reinforcement learning, as MSRL and FD-RL do? Reinforcement learning raises execution rates but leaves residual failures, such as MSRL's 3.5% non-executing code. It also requires updating the weights of every deployed model. Our decoder needs only a small HMM and projector per model and schema family. We test whether the two combine, and an additive gain would answer the objection directly.

Decisive Checks

On ChartMimic Direct and Customized Mimic we report execution rate and both high-level and low-level scores. On OmniDocBench tables we report TEDS, and on held-out ChartMoE-Align charts we report JSON and CSV field-level exact match. The idea survives only if three results hold together. First, GCD trails unconditioned P-GCD on content. Second, conditioned P-GCD beats unconditioned P-GCD at matched wall-clock time. Third, that advantage disappears under mismatched images and grows with how strongly the image determines output structure.

A secondary check uses the text-preference setup from Words or Vision, with schemas whose example values contradict the image. The question is whether an image-aware proposal reduces the drift toward prompt-supplied values that a text-only proposal should amplify.