Vision-language models can name the objects in a picture but often fail when an answer depends on how those objects relate. They miss "left of", "every red cup", and "more chairs than tables". Training data written from fixed templates makes this worse, because a model can learn the template's wording instead of its meaning. We propose to write a small compositional grammar that maps sentences to logical formulas and run it in reverse, as a generator. For any logical question about a scene, the grammar produces many differently worded sentences that provably mean the same thing, along with minimally altered versions whose answer flips. A checker that evaluates logical formulas against the scene's annotated object graph supplies the correct answer for every variant.
We then fine-tune a compact vision-language model with reinforcement learning. The model is rewarded only when it answers a whole family of questions consistently. Getting one question right by luck or by a wording heuristic earns little. The grammar and the checker are used only during training. At test time the model reads raw pixels and plain questions, so the parser errors that sink classic symbolic pipelines cannot occur. The bet is that rewarding consistency across a family of questions with the same meaning removes template shortcuts more effectively than more data, more paraphrases, or answer-only rewards.
Core Claim
Template-generated relational data fails for two separate reasons. Its wording is rigid, so models latch onto surface patterns. Its training signal is per-question, so a model can be right for the wrong reason. A grammar in which syntax and logic are tied together (combinatory categorial grammar, CCG, where every word carries a typed λ-calculus meaning and phrases combine by function application) fixes the first problem without the hallucination risk of LLM paraphrasing. A deterministic first-order model checker fixes the second, if its verdicts are aggregated over the whole family of variants rather than over single questions.
Our claim is specific. A 3B–7B model trained with a family-consistency reward should close a large part of the compositional-split gap on COVR and the contrast-set gap on GQA. On contrast sets it should exceed what supervised "inoculation" on perturbed questions achieves. It should also do better than the same model trained with answer-only rewards on exactly the same generated data.
Where This Sits
Three findings motivate the work. Scaling does not close the gap: Benchmarking and Understanding Compositional Relational Reasoning of LLMs shows that from 7B to 70B parameters, sub-task skill grows while the gap to full compositional performance widens. Benchmarking Systematic Relational Reasoning with Large Language and Reasoning Models finds that even reasoning models such as o3-mini act as "shallow disjunctive reasoners" whose accuracy falls as reasoning paths must be intersected. Embodied models break in the same way: Nouns, Not Modifiers reports OpenVLA-7B at 90.0% on object nouns but 47.5% on spatial modifiers, with 80% on "right" against 15% on "left". That asymmetry is exactly what a model would show if it never learned that "A left of B" and "B right of A" are the same fact.
Two lines of work constrain the design. Template engines expose shortcut learning but do not cure it. COVR builds 640 program types from 15 templates plus human paraphrase and watches VisualBERT fall to 1.6% on some zero-shot splits. It also finds that about 70% of its generation errors trace back to faulty scene graphs, which warns us that any reward computed from GQA or Visual Genome graphs will be noisy. Generate Any Scene shows that programmatic generation is about 90x faster than LLM prompting and avoids LLM "common pattern bias", but it produces stiff phrasing. We keep its programmatic faithfulness and replace its string rendering with grammar-driven realization.
Three papers already pair perturbations or consistency with relational QA. Automatic Generation of Contrast Sets from Scene Graphs builds answer-flipping minimal pairs from 6 regex templates and fine-tunes on 80k of them. MUTANT adds a pairwise consistency loss over image and text mutations. Neither has a guarantee that its linguistic variants preserve or flip meaning as intended, and neither uses a reinforcement signal that scores a whole family of questions.
Two papers supply our methods. Visual-Textual Entailment with Quantities Using Model Checking and Knowledge Injection parses hypotheses with CCG and λ-calculus and checks them against scene graphs treated as first-order models, in about 1.18 seconds per image versus over 60 seconds for theorem proving. That system checks at inference time and inherits parser failures. We move the checker into the training loop and remove it from inference. AutoTriton shows that Group Relative Policy Optimization (GRPO) — a reinforcement learning method that scores several sampled outputs relative to each other — specializes an 8B model well when rewards come from an exact executor. Model checking is our executor.
The closest system is SaGe (Scene Graph Thinking). It specializes Qwen2.5-VL-3B/7B with supervised fine-tuning and then reinforcement learning on scene-graph reasoning traces. It rewards node grounding and relevance because relation-level rewards seemed too fragile. We differ in three ways: our questions come from a formal grammar rather than heuristics and prompting, our reward is exact at the level of relations and quantifiers, and our reward scores families of questions rather than single traces.
Research Program
The first component is a bidirectional grammar. We will write a CCG lexicon covering the relation, attribute, and object vocabulary of GQA scene graphs. Its semantics cover existential and universal quantification, "no", "exactly/at least n", numeric comparatives, negation, and relative clauses, which matches COVR's logical operators. The lexicon also includes meaning postulates, such as left_of(x,y) ⇔ right_of(y,x) and above(x,y) ⇔ below(y,x).
Running chart generation from a target formula enumerates surface realizations of that formula. These include active and passive forms, fronted or embedded relative clauses, converse relations, and quantifier placement. A lexicon of a few hundred entries composes into far more sentence shapes than hand-written frames, which is the economic argument against templates. We will test that argument by counting distinct realizations per formula and reporting the authoring hours.
The second component is the family construction. For a scene graph $G$ and a sampled formula $\varphi$, the family $F(\varphi)$ has two parts. The first is the set of grammar realizations of $\varphi$, all of which receive the same answer. The second is the realizations of minimal logical edits $\varphi'$, such as a swapped relation argument, a changed quantifier, a negated predicate, or a shifted count, whose answers the model checker computes on $G$. Edits are kept only if the checker confirms that the answer changes. Faithfulness is therefore guaranteed by construction relative to $G$, though not relative to the true image, given COVR's warning about graph noise.
The third component is the family-consistency reward. The policy, a Qwen2.5-VL model at 3B and 7B to match SaGe's scale, answers each family member from the image alone. For member $i$ with checker answer $a_i$ and model answer $\hat a_i$, the reward is
$$r_i = \mathbb{1}[\hat a_i = a_i]\cdot\Big(\tfrac{1}{|F|}\sum_{j\in F}\mathbb{1}[\hat a_j = a_j]\Big)^{\gamma},$$
where $\gamma \ge 0$ sets how strongly a correct answer is discounted when its siblings are wrong. $\gamma = 0$ recovers answer-only reward.
GRPO is applied with several samples per family member, so advantages are computed within each member's samples while the reward carries information about the whole family. The prediction follows from the reward's form. A wording-dependent heuristic that answers only some realizations correctly is penalized multiplicatively, so its expected reward falls well below that of a policy that has actually read the relation. Before reinforcement learning, a short supervised warm start on checker-labeled answers stabilizes training, following the SFT-then-RL recipe of SaGe and AutoTriton.
The fourth component is noise control. Because COVR attributes about 70% of its errors to scene graphs, we will estimate reward noise on a hand-audited sample of 500 families. We will also compare training on Visual Genome graphs with training on a filtered subset in which detector outputs agree with the annotation, and report whether noise caps the gains.
Baselines
The naive reference point is the base Qwen2.5-VL model of the same size, prompted zero-shot, together with the published VisualBERT numbers on COVR. VisualBERT reaches roughly 68% on in-distribution data and falls as low as 1.6% on specific zero-shot compositional splits, against roughly 92% for humans (COVR). Since our backbone differs, we rerun the zero-shot base model ourselves and treat the VisualBERT figures only as context.
The strongest existing method on the contrast-consistency question is inoculation: supervised fine-tuning on 80k automatically perturbed contrast pairs. It raised LXMERT's GQA contrast-set accuracy from 67.2% to 77.2%, with a multi-perturbation contrast consistency of 46.1% before inoculation (Automatic Generation of Contrast Sets from Scene Graphs). We will reimplement inoculation on our backbone with their 6 regex templates, matching example count, GPU hours, and hyperparameter search budget to our method. Beating it means higher contrast-set accuracy and higher contrast consistency on our backbone. A second check is whether we reach the 77.2% contrast-set accuracy LXMERT reached after inoculation, reported as a cross-architecture reference only.
The strongest existing reinforcement-learning method for structured visual reasoning at this scale is SaGe. Its 7B model reports 79.4 on CVBench-2D and 80.5 on CVBench-3D (Scene Graph Thinking). We will compare on CVBench-2D to check that our specialization does not cost general spatial perception. We will also train a SaGe-style node-proxy-reward model on our scene graphs with matched compute where feasible, and compare on COVR and the contrast sets, the relation-centric benchmarks SaGe did not report.
Three ablations isolate the key ingredients, all on identical images, graphs, step counts, and tuning budgets. The first keeps the grammar-generated families but sets $\gamma = 0$, which tests whether family-level reward matters beyond the data. The second keeps $\gamma > 0$ but builds families from template realizations only, with logical edits but one surface form per formula. This tests whether grammar-driven wording diversity matters. The third replaces reinforcement learning with supervised fine-tuning on the same families, which tests whether the reward signal, not just the data, does the work. Our method counts as succeeding only if it beats all three on the COVR zero-shot splits.
Why not just…?
Why not just prompt a frontier model or a reasoning model? The file's evidence says scaling and step-by-step reasoning do not compose relations reliably. GPT-4 reaches 71.5% on the synthetic GAR benchmark, and the compositionality gap widens with scale (Benchmarking and Understanding Compositional Relational Reasoning of LLMs). o3-mini degrades as reasoning paths multiply (Benchmarking Systematic Relational Reasoning), and GPT-4o tops out at 46.78% on EEE-Bench (EEE-Bench). We will still report a frontier vision-language model on our family-consistency metric, because consistency, not accuracy, is the quantity we claim to improve.
Why not just paraphrase template questions with an LLM and train with answer rewards? This is the most serious threat. LLM paraphrase gives wording diversity cheaply and may match the grammar's diversity on human-written test questions. Against it, Generate Any Scene documents common-pattern bias and cost. Paraphrase also cannot guarantee that a rewritten "left of" still means left, which matters most for exactly the converse and quantifier cases we target.
We will run this arm directly, at two strengths. In the plain version an LLM paraphrases template outputs into families. In the strengthened version the paraphrases are filtered by back-parsing with our grammar where possible. Both are scored on the COVR human-paraphrased test set and on a converse-relation consistency probe. If LLM-paraphrase families match grammar families on both, the grammar's contribution reduces to cost and auditability. We would then report that honestly and keep only the family reward as the contribution.
Why not just do supervised fine-tuning on more perturbed data, as inoculation does? Inoculation helps, but per-question supervision still allows a model to fit each variant independently. AutoTriton and Scene Graph Thinking both found supervised training insufficient without a reinforcement stage. Our supervised-on-same-families ablation tests this claim in our setting. If it ties the reinforcement-learning model, we drop reinforcement learning.
Why not just keep the CCG parser and model checker at inference, as the visual entailment system does? That system's strict quantity accuracy is only 20% (Visual-Textual Entailment with Quantities). It also needs gold scene graphs and breaks on out-of-grammar human phrasing, the failure mode pipeline papers repeatedly report (Logical Inferences with Comparatives and Generalized Quantifiers). Using the symbolic machinery only during training sidesteps both problems.
Proposed Experiments
The primary test is the COVR zero-shot and few-shot compositional splits. Their test questions are human-paraphrased, so they partly lie outside our grammar, which makes them a fair test of whether grammar-taught relations transfer to natural language. The second test is the GQA automated contrast sets, scored on accuracy and on multi-perturbation contrast consistency.
The third test is a converse-relation probe built from held-out GQA images: pairs such as "left of A" / "right of B" with identical truth. It measures the left–right asymmetry that Nouns, Not Modifiers reports. Within this probe we will hold out entire grammar constructions, such as relative clauses or passives, from training to test whether they generalize. On the specialization tax described in Specializing Smaller Language Models towards Multi-Step Reasoning, we will track CVBench-2D/3D and MMStar before and after training, with SaGe's MMStar 62.3% as a reference.
As a text-only transfer check, we will apply the same grammar-and-checker recipe to STaR's spatial (RCC-8) and temporal (Interval Algebra) constraint networks. There, path-consistency checking plays the role of the model checker. For STaR, no reported result was found on Lacuna for a numeric baseline: the file reports only that zero-shot models are near random and that Qwen2.5-72B is the strongest of them, so we will run Qwen2.5-72B ourselves. A digital-logic extension, using EEE-Bench schematics whose netlists serve as the graph, is an optional stretch goal and is not part of the core claim.
Three results would settle the core claim. First, on the COVR zero-shot splits, the full method must beat all three ablations and the LLM-paraphrase arm. Second, the gap between answer-only reward ($\gamma = 0$) and family reward must be larger on the contrast and converse probes than on in-distribution accuracy, which is what the reward's form predicts. Third, in the audited noise analysis, gains should shrink in proportion to estimated scene-graph error. If family reward helps only in-distribution, or LLM-paraphrase families match it everywhere, the central claim is wrong.
References
- Benchmarking and Understanding Compositional Relational Reasoning of LLMs
- Large Language and Reasoning Models are Shallow Disjunctive Reasoners
- Nouns, Not Modifiers: OpenVLA Parses Objects but Fails at Spatial Composition
- COVR: A Test-Bed for Visually Grounded Compositional Generalization with Real Images
- Generate Any Scene: Scene Graph Driven Data Synthesis for Visual Generation Training
- Automatic Generation of Contrast Sets from Scene Graphs: Probing the Compositional Consistency of GQA
- MUTANT: A Training Paradigm for Out-of-Distribution Generalization in Visual Question Answering
- Visual-Textual Entailment with Quantities Using Model Checking and Knowledge Injection
- AUTOTRITON: Automatic Triton Programming with Reinforcement Learning in LLMs
- Scene Graph Thinking: Reinforcing Structured Visual Reasoning for Multimodal Large Language Models
- EEE-Bench: A Comprehensive Multimodal Electrical And Electronics Engineering Benchmark
- Logical Inferences with Comparatives and Generalized Quantifiers
- Specializing Smaller Language Models towards Multi-Step Reasoning