Constraint-Anchored Reasoning Traces

# Constraint-Anchored Reasoning Traces
Source: [https://arxiv.org/html/2607.16727](https://arxiv.org/html/2607.16727)
Zehua ChengandWei Dai and Jiahao SunFLock\.ioUnited Kingdom[sun@flock\.io](https://arxiv.org/html/2607.16727v1/mailto:[email protected])

\(2026\)

###### Abstract\.

Autoregressive multimodal large language models \(MLLMs\) suffer from error snowballing: a single incorrect inference early in a chain\-of\-thought \(CoT\) trace corrupts all downstream reasoning\. We find that in state\-of\-the\-art open\-source MLLMs, once the first error occurs, the reasoning cascades into failure across all remaining steps in 65% of such cases \(a metric we term the*snowball rate*\)\. Existing mitigations—sampling multiple chains, post\-hoc self\-verification, or full program synthesis—either lack symbolic grounding, catch errors too late, or sacrifice the flexibility of natural language reasoning\. We proposeConstraint\-Anchored Reasoning Traces \(CART\), a neuro\-symbolic framework that trains MLLMs to interleave natural language reasoning steps with symbolic constraint assertions: lightweight, machine\-checkable statements about visual content \(e\.g\.,count\(red\_objects\) = 3\)\. A dual\-pronged Constraint Propagation Module—combining a learned neural grounding head with Boolean Constraint Propagation—continuously verifies these anchors against extracted visual features and checks their mutual logical consistency\. When a contradiction is detected, a backtrack controller halts generation and reverts to the last consistent checkpoint, preventing error propagation\. A variable\-frequency emission mechanism allows the model to adaptively control anchor density, avoiding trace bloat\. We construct 218K training instances by augmenting GQA, CLEVR\-CoGenT, and VCR with ground\-truth constraint annotations derived from scene graphs, and fine\-tune open\-source MLLMs \(LLaVA\-NeXT, Qwen2\-VL\) via LoRA\. On five benchmarks, CART reduces the snowball rate from 0\.65 to 0\.14, improves GQA accuracy by \+4\.6 percentage points over training\-only baselines, and achieves 89\.1 F1 on POPE—all with at most 18% inference overhead\.

multimodal reasoning, chain\-of\-thought, error correction, neuro\-symbolic systems, constraint propagation, visual question answering, large language models

††copyright:acmlicensed††journalyear:2026††doi:XXXXXXX\.XXXXXXX††conference:The 34th ACM International Conference on Multimedia; October 2026; Dublin, Ireland††ccs:Computing methodologies Knowledge representation and reasoning††ccs:Computing methodologies Spatial and physical reasoning## 1\.Introduction

Multimodal large language models \(MLLMs\) have demonstrated remarkable capabilities across vision\-language tasks, yet their autoregressive generation paradigm harbors a critical structural vulnerability:error snowballing\. When a model commits an incorrect inference early in a chain\-of\-thought \(CoT\) reasoning trace, every subsequent step conditions on this erroneous prefix, causing downstream reasoning to cascade into compounding failures\(Zhanget al\.,[2023a](https://arxiv.org/html/2607.16727#bib.bib12); Weiet al\.,[2022](https://arxiv.org/html/2607.16727#bib.bib13)\)\. In compositional visual question answering—where answering a single question may require counting objects, identifying spatial relations, and reasoning about attributes—a single misidentified object can corrupt the entire deductive chain without external correction\.

Existing approaches to mitigate reasoning errors in MLLMs fall into three broad categories, each with fundamental shortcomings\.Sampling\-based methods\(Wanget al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib14); Yaoet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib15)\)generate multiple candidate chains and select answers by majority vote or heuristic scoring, but provide no mechanism to identifywhichstep failed orwhy—they merely hope that the correct chain appears among the samples\.Post\-hoc self\-verification\(Shinnet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib16); Madaanet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib17)\)prompts the model to critique its own output, but this verbal self\-assessment lacks grounding in the visual input; the same model that produced the error is unlikely to reliably detect it through introspection alone\.Program synthesis\(Gupta and Kembhavi,[2023](https://arxiv.org/html/2607.16727#bib.bib18); Suríset al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib19)\)sidesteps natural language reasoning entirely by generating executable code, achieving strong symbolic guarantees but sacrificing the interpretability and flexibility of natural language traces—a critical limitation when the reasoning domain is not reducible to a fixed API\.

We observe that what is needed is aprincipled middle ground: a framework that preserves the flexibility of natural language reasoning while injecting verifiable symbolic checkpoints that can catch errorsas they occurand trigger corrective actionbeforethey propagate\. To this end, we proposeConstraint\-Anchored Reasoning Traces \(CART\), a framework that trains MLLMs to interleave standard reasoning steps withsymbolic constraint assertions—lightweight, machine\-checkable statements about visual content \(e\.g\.,count\(red\_objects\) = 3,left\_of\(dog, cat\) = True\)\. A dedicatedConstraint Propagation Module \(CPM\)continuously verifies these anchors against extracted visual features via a neural grounding head and checks their mutual logical consistency via Boolean Constraint Propagation \(BCP\)\. When a contradiction is detected—either between an anchor and the image or among accumulated anchors—generation halts and abacktrack controllerreverts the trace to the last consistent checkpoint, preventing error propagation\.

A key design insight of CART isvariable\-frequency anchor emission: rather than rigidly alternating between reasoning steps and constraints, the model learns to emit zero, one, or multiple anchors after each step, with an explicit null token when no meaningful constraint applies\. This adaptive density avoids both the trace bloat of forced emissions and the under\-constraining of sparse ones\.

We train CART by augmenting existing visual reasoning datasets \(GQA\(Hudson and Manning,[2019](https://arxiv.org/html/2607.16727#bib.bib2)\), CLEVR\-CoGenT\(Johnsonet al\.,[2017](https://arxiv.org/html/2607.16727#bib.bib1)\), VCR\(Zellerset al\.,[2019](https://arxiv.org/html/2607.16727#bib.bib3)\)\) with ground\-truth constraint annotations derived from scene graphs and structured programs, yielding 218K training instances\. Fine\-tuning is performed via LoRA on open\-source MLLMs \(LLaVA\-NeXT\(Liuet al\.,[2024a](https://arxiv.org/html/2607.16727#bib.bib7)\), Qwen2\-VL\(Wanget al\.,[2024](https://arxiv.org/html/2607.16727#bib.bib11)\)\), jointly optimizing a task loss, a constraint grounding loss, and a novel backtrack\-aware loss that teaches the model to recover from simulated errors\.

Our contributions are summarized as follows:

- •We formalize the error snowballing problem in autoregressive multimodal reasoning and propose CART, a neuro\-symbolic framework that interleaves natural language reasoning with verifiable symbolic constraint anchors and a runtime constraint propagation module\.
- •We introduce a variable\-frequency anchor emission mechanism, a dual\-pronged verification engine combining neural visual grounding with symbolic Boolean Constraint Propagation, and a backtrack controller with formal error\-reduction guarantees \(Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)\)\.
- •We define three novel diagnostic metrics—snowball rate, constraint violation rate, and error attribution precision—that directly measure error propagation behavior beyond standard end\-task accuracy\.
- •Extensive experiments on five benchmarks \(GQA, CLEVR\-CoGenT, VCR, MM\-Vet, POPE\) demonstrate that CART achieves state\-of\-the\-art accuracy while reducing the snowball rate from 0\.65 to 0\.14, with only 10–18% inference overhead\.

## 2\.Related Work

Chain\-of\-thought reasoning in MLLMs\.Chain\-of\-thought prompting\(Weiet al\.,[2022](https://arxiv.org/html/2607.16727#bib.bib13)\)and its variants have become the de facto approach for eliciting multi\-step reasoning from large language models\. Zero\-shot CoT\(Kojimaet al\.,[2022](https://arxiv.org/html/2607.16727#bib.bib20)\)and few\-shot prompting strategies improve performance on arithmetic and commonsense benchmarks, while multimodal extensions\(Zhanget al\.,[2023b](https://arxiv.org/html/2607.16727#bib.bib21); Luet al\.,[2022](https://arxiv.org/html/2607.16727#bib.bib22)\)adapt these techniques to vision\-language tasks\. However, standard CoT provides no mechanism to detect or correct intermediate errors\. Tree\-of\-Thoughts\(Yaoet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib15)\)explores multiple reasoning branches via breadth\-first or depth\-first search with LLM\-based evaluation, but the evaluator shares the same failure modes as the generator\. Self\-Consistency\(Wanget al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib14)\)marginalizes over sampled chains by majority voting, improving robustness statistically but offering no per\-chain error correction\. DDCoT\(Zhenget al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib23)\)decomposes questions into sub\-questions for divide\-and\-conquer reasoning but still relies on the model’s internal representations for correctness\. CART differs from all of these by introducingexternally verifiablesymbolic checkpoints that ground intermediate reasoning in the visual input, enabling targeted correction rather than statistical aggregation\.

Neuro\-symbolic visual reasoning\.The integration of symbolic reasoning with neural perception has a rich history in visual question answering\. Neural Module Networks\(Andreaset al\.,[2016](https://arxiv.org/html/2607.16727#bib.bib24); Huet al\.,[2017](https://arxiv.org/html/2607.16727#bib.bib25)\)compose differentiable modules according to syntactic parses of questions, while NS\-VQA\(Yiet al\.,[2018](https://arxiv.org/html/2607.16727#bib.bib26)\)uses a scene parser to construct symbolic representations for program execution\. More recently, VisProg\(Gupta and Kembhavi,[2023](https://arxiv.org/html/2607.16727#bib.bib18)\)and ViperGPT\(Suríset al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib19)\)leverage LLMs to generate executable Python programs that invoke specialized vision modules\. Faithful CoT\(Lyuet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib27)\)translates reasoning chains into symbolic programs for verification\. These fully symbolic approaches achieve strong guarantees on structured benchmarks like CLEVR but struggle with the ambiguity and open\-ended nature of real\-world visual reasoning \(e\.g\., VCR\), where rigid program templates cannot capture the full spectrum of deductive strategies\. CART occupies a complementary niche: it retains natural language as the primary reasoning medium while selectively injecting symbolic assertions at points where visual grounding can be verified, preserving flexibility where needed and enforcing precision where possible\.

Error correction and self\-refinement\.Several recent works address the brittleness of autoregressive reasoning through iterative refinement\. Reflexion\(Shinnet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib16)\)maintains an episodic memory of verbal self\-reflections to improve subsequent attempts, while Self\-Refine\(Madaanet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib17)\)iterates between generation and self\-critique within a single inference pass\. In the visual domain, visual verification approaches\(Denget al\.,[2024](https://arxiv.org/html/2607.16727#bib.bib28)\)prompt MLLMs to re\-examine the image after generating an answer\. However, these methods rely on the model’s own internal representations for error detection—the same representations that produced the error\. CART introduces apartially externalverification loop: the neural grounding head is anchored to*independently extracted*visual evidence \(region features from a frozen Grounding DINO\(Liuet al\.,[2024b](https://arxiv.org/html/2607.16727#bib.bib9)\)detector\) rather than relying solely on the generator’s own attention over the image, and BCP provides a non\-differentiable, sound consistency check over the accumulated anchors\. We note that the grounding head is not fully independent of the generator—it also consumes the anchor’s LLM hidden\-state embedding \(§[3\.2\.2](https://arxiv.org/html/2607.16727#S3.SS2.SSS2)\)—but grounding the check in external visual features and a symbolic consistency test still mitigates the purely self\-referential failure mode of methods that verify using only the generator’s internal representations\.

![Refer to caption](https://arxiv.org/html/2607.16727v1/x1.png)Figure 1\.Overview of the CART framework\. Given an image and question, the MLLM generates interleaved reasoning steps and symbolic constraint anchors\. The Constraint Propagation Module \(CPM\) verifies each anchor via a neural grounding head and Boolean Constraint Propagation\. When a violation is detected, the backtrack controller reverts to the last consistent checkpoint and resumes generation with a<RETRY\>token\.Architecture diagram showing the CART pipeline: an MLLM generates reasoning steps interleaved with constraint anchors, which are verified by the CPM \(neural grounding head and BCP\)\. A backtrack controller handles detected violations\.
## 3\.Methodology

We presentConstraint\-Anchored Reasoning Traces \(CART\), a framework that augments autoregressive multimodal reasoning with interleaved symbolic constraint assertions and a runtime constraint propagation module capable of detecting inconsistencies and triggering targeted backtracking\. We detail the formulation, architecture, theoretical guarantees, and training procedure below\.

### 3\.1\.Problem Formulation

Letℐ\\mathcal\{I\}denote the space of images and𝒬\\mathcal\{Q\}the space of natural\-language questions\. A multimodal large language model \(MLLM\)ℳθ\\mathcal\{M\}\_\{\\theta\}parameterized byθ\\thetaproduces, given an imageI∈ℐI\\in\\mathcal\{I\}and questionq∈𝒬q\\in\\mathcal\{Q\}, an answeraavia an autoregressive chain\-of\-thought \(CoT\) trace𝐫=\(r1,r2,…,rT\)\\mathbf\{r\}=\(r\_\{1\},r\_\{2\},\\ldots,r\_\{T\}\), where eachrtr\_\{t\}is a reasoning step \(a span of tokens\)\. The final answera=fans​\(𝐫\)a=f\_\{\\text\{ans\}\}\(\\mathbf\{r\}\)is extracted from the terminal step\. We denote the visual feature bank extracted by the MLLM’s frozen vision encoder as𝐕=ϕ​\(I\)∈ℝN×dv\\mathbf\{V\}=\\phi\(I\)\\in\\mathbb\{R\}^\{N\\times d\_\{v\}\}, whereNNis the number of spatial tokens anddvd\_\{v\}is the per\-token feature dimension\.

Error snowballing\.We define anerror eventat stepttaset=𝟙​\[sem​\(rt\)≠sem​\(rt∗\)\]e\_\{t\}=\\mathbb\{1\}\[\\text\{sem\}\(r\_\{t\}\)\\neq\\text\{sem\}\(r\_\{t\}^\{\*\}\)\], wheresem​\(⋅\)\\text\{sem\}\(\\cdot\)extracts the semantic proposition of a step andrt∗r\_\{t\}^\{\*\}is the ground\-truth counterpart\. Thesnowball rate𝒮\\mathcal\{S\}is the conditional probability that all subsequent steps are erroneous given a first error:

𝒮=ℙ​\[⋂t′=t\+1T\{et′=1\}\|et=1,∀t′′<tet′′=0\]\.\\mathcal\{S\}=\\mathbb\{P\}\\\!\\Big\[\\bigcap\_\{t^\{\\prime\}=t\+1\}^\{T\}\\\{e\_\{t^\{\\prime\}\}=1\\\}\\;\\Big\|\\;e\_\{t\}=1,\\;\\forall\_\{t^\{\\prime\\prime\}<t\}\\;e\_\{t^\{\\prime\\prime\}\}=0\\Big\]\.
Standard autoregressive generation exhibits high𝒮\\mathcal\{S\}because the model conditions on its own \(erroneous\) prefix with no corrective mechanism\.

Objective\.We seek to learn parametersθ∗\\theta^\{\*\}and a constraint\-checking mechanism𝒞\\mathcal\{C\}that jointly minimize task loss while reducing𝒮\\mathcal\{S\}:

\(1\)θ∗=arg⁡minθ⁡ℒtask​\(θ\)⏟answer accuracy\+λc​ℒcst​\(θ\)⏟constraint grounding\+λb​ℒbt​\(θ\)⏟backtrack policy,\\theta^\{\*\}=\\arg\\min\_\{\\theta\}\\;\\underbrace\{\\mathcal\{L\}\_\{\\text\{task\}\}\(\\theta\)\}\_\{\\text\{answer accuracy\}\}\+\\lambda\_\{c\}\\underbrace\{\\mathcal\{L\}\_\{\\text\{cst\}\}\(\\theta\)\}\_\{\\text\{constraint grounding\}\}\+\\lambda\_\{b\}\\underbrace\{\\mathcal\{L\}\_\{\\text\{bt\}\}\(\\theta\)\}\_\{\\text\{backtrack policy\}\},whereλc,λb\>0\\lambda\_\{c\},\\lambda\_\{b\}\>0are balancing coefficients\. Each loss term is defined in Appendix[D](https://arxiv.org/html/2607.16727#A4)\.

### 3\.2\.Constraint\-Anchored Reasoning Traces

CART introduces three interlocking components: \(i\)variable\-frequency anchor\-interleaved generation, \(ii\) aconstraint propagation module \(CPM\), and \(iii\) abacktrack controller\. We describe each in turn and justify every design choice\.

#### 3\.2\.1\.Variable\-Frequency Anchor\-Interleaved Generation

We augment the reasoning trace vocabulary with a distinguished set ofconstraint anchors\. Formally, an anchorccis a symbolic assertion drawn from a domain\-specific constraint languageℒc\\mathcal\{L\}\_\{c\}:

c=pred\(arg1,…,argk\)⋈v,⋈∈\{=,≠,<,\>,≤,≥\},c\\;=\\;\\texttt\{pred\}\(\\texttt\{arg\}\_\{1\},\\ldots,\\texttt\{arg\}\_\{k\}\)\\bowtie v,\\quad\\bowtie\\;\\in\\;\\\{=,\\neq,<,\>,\\leq,\\geq\\\},wherepredis a visual predicate \(e\.g\.,count,color,spatial\_rel\),argi\\texttt\{arg\}\_\{i\}are grounded entity references, andvvis a value\. Examples includecount\(red\_objects\) = 3andleft\_of\(dog, cat\) = True\. The languageℒc\\mathcal\{L\}\_\{c\}is intentionally kept lightweight—propositional with bounded\-arity predicates and finite domains—so that checking is efficient \(see Proposition[13](https://arxiv.org/html/2607.16727#A1.Thmtheorem13)\)\.

Variable\-frequency emission\. Rather than enforcing a rigid one\-to\-one alternation between reasoning steps and anchors, we allow the model to emitzero, one, or multipleanchors after any reasoning step\. Anchors are delineated by<CON\>and</CON\>delimiter tokens; the model may emit multiple such delimited spans consecutively, or none at all\. When no meaningful constraint applies to a reasoning step, the model emits an explicit<NULL\_CON/\>token\. Formally, the mixed trace has the structure:

𝐫=\(r1,𝐜1,r2,𝐜2,…,rT,𝐜T\),\\mathbf\{r\}=\\big\(r\_\{1\},\\mathbf\{c\}\_\{1\},\\;r\_\{2\},\\mathbf\{c\}\_\{2\},\\;\\ldots,\\;r\_\{T\},\\mathbf\{c\}\_\{T\}\\big\),where𝐜t∈ℒc∗∪\{<NULL\_CON/\>\}\\mathbf\{c\}\_\{t\}\\in\\mathcal\{L\}\_\{c\}^\{\*\}\\cup\\\{\\texttt\{<NULL\\\_CON/\>\}\\\}denotes a possibly\-empty sequence of anchors following steprtr\_\{t\}\. Let𝒜=\{\(t,j\):ct,j∈𝐜t,ct,j≠<NULL\_CON/\>\}\\mathcal\{A\}=\\\{\(t,j\):c\_\{t,j\}\\in\\mathbf\{c\}\_\{t\},\\;c\_\{t,j\}\\neq\\texttt\{<NULL\\\_CON/\>\}\\\}index all non\-null anchor emissions across the trace\.Justification\.Variable\-frequency emission avoids two failure modes of rigid alternation: \(a\) inflating the trace with vacuous anchors for steps that admit no verifiable visual constraint \(degrading generation quality\), and \(b\) under\-constraining steps where multiple independent visual facts are established\. The<NULL\_CON/\>token is necessary because simply omitting the anchor field would create an ambiguous parse: the delimiter\-based parser cannot distinguish “no anchor emitted” from “anchor emission failed\.” Training the model on traces with varying anchor density \(including explicit nulls\) teaches it to self\-assess which steps warrant symbolic checkpoints\.

#### 3\.2\.2\.Entity Grounding Mechanism

Anchors reference entities by natural\-language name strings \(e\.g\., ‘dog‘, ‘red cylinder‘\)\. Resolving these strings to image regions is essential for the visual grounding check\. We use Grounding DINO\(Liuet al\.,[2024b](https://arxiv.org/html/2607.16727#bib.bib9)\)as a frozen, off\-the\-shelf entity grounding module\. Specifically:

- •For each anchorct,jc\_\{t,j\}with entity arguments\(arg1,…,argk\)\(\\texttt\{arg\}\_\{1\},\\ldots,\\texttt\{arg\}\_\{k\}\), each argument string is passed to Grounding DINO along with the imageII, producing a set of candidate bounding boxes with confidence scores\.
- •The top\-1 box per argument \(confidence threshold≥0\.3\\geq 0\.3\) is projected onto the spatial token grid of the vision encoder, yielding a subset of spatial token indicesℛi⊆\{1,…,N\}\\mathcal\{R\}\_\{i\}\\subseteq\\\{1,\\ldots,N\\\}for eachargi\\texttt\{arg\}\_\{i\}\.
- •RoI\-Align\(Heet al\.,[2017](https://arxiv.org/html/2607.16727#bib.bib8)\)extracts region\-level visual features𝐯i=MeanPool​\(\{𝐕n:n∈ℛi\}\)∈ℝdv\\mathbf\{v\}\_\{i\}=\\text\{MeanPool\}\(\\\{\\mathbf\{V\}\_\{n\}:n\\in\\mathcal\{R\}\_\{i\}\\\}\)\\in\\mathbb\{R\}^\{d\_\{v\}\}for each argument\.
- •If Grounding DINO fails to detect a named entity \(confidence below threshold for all candidates\), we fall back tofull\-image mean pooling𝐯i=MeanPool​\(𝐕\)∈ℝdv\\mathbf\{v\}\_\{i\}=\\text\{MeanPool\}\(\\mathbf\{V\}\)\\in\\mathbb\{R\}^\{d\_\{v\}\}and flag the anchor asweakly grounded\.

Grounding accuracy\.We evaluated the Grounding DINO entity localization on a held\-out set of 2,000 anchor\-entity pairs manually annotated with ground\-truth bounding boxes\. At IoU≥0\.5\\geq 0\.5, grounding accuracy is89\.3%\(GQA/CLEVR entities\) and82\.7%\(VCR entities, which include more complex referring expressions\)\. The fallback to full\-image pooling is triggered for 6\.2% of entities overall\.

Justification\.Using a dedicated open\-vocabulary detector rather than the MLLM’s own attention maps provides more reliable spatial localization\. Attention\-based grounding in MLLMs has been shown to be diffuse and unreliable for fine\-grained spatial reasoning\. Grounding DINO’s open\-vocabulary capability handles the diverse entity descriptions generated by the LLM without requiring a fixed object taxonomy\.

Algorithm 1CART Inference1:Image

II, question

qq, model

MθM\_\{\\theta\}, grounding head

gψg\_\{\\psi\}, BCP, GroundingDINO, threshold

τv\\tau\_\{v\}, max retries

BB
2:Answer

aa
3:

V←ϕ​\(I\)V\\leftarrow\\phi\(I\);

Σ←∅\\Sigma\\leftarrow\\emptyset;

trace←\[\]\\text\{trace\}\\leftarrow\[\];

retries←0\\text\{retries\}\\leftarrow 0
4:whilenotEND\_TOKENand

retries≤B\\text\{retries\}\\leq Bdo

5:

rt←Mθ\.gen\_step​\(trace,I,q\)r\_\{t\}\\leftarrow M\_\{\\theta\}\.\\text\{gen\\\_step\}\(\\text\{trace\},I,q\)
6:

Ct←Mθ\.gen\_anchors​\(trace\+\[rt\],I,q\)C\_\{t\}\\leftarrow M\_\{\\theta\}\.\\text\{gen\\\_anchors\}\(\\text\{trace\}\+\[r\_\{t\}\],I,q\)
7:if

Ct=<NULL\_CON/\>or malformedC\_\{t\}=\\texttt\{<NULL\\\_CON/\>\}\\textbf\{or malformed\}then

8:

trace←trace\+\[rt,<NULL\_CON/\>\]\\text\{trace\}\\leftarrow\\text\{trace\}\+\[r\_\{t\},\\texttt\{<NULL\\\_CON/\>\}\];continue

9:endif

10:

all\_ok←True\\text\{all\\\_ok\}\\leftarrow\\text\{True\}
11:for

c∈Ctc\\in C\_\{t\}do

12:

vc←RoI\_Pool\(V,GroundingDINO\(c\.entities,I\)\)v\_\{c\}\\leftarrow\\text\{RoI\\\_Pool\}\(V,\\text\{GroundingDINO\}\(c\.\\text\{entities\},I\)\)
13:

pv​i​s←gψ​\(\[vc;LLM\_hid​\(c,trace\)\]\)p\_\{vis\}\\leftarrow g\_\{\\psi\}\(\[v\_\{c\};\\text\{LLM\\\_hid\}\(c,\\text\{trace\}\)\]\)
14:if

pv​i​s<τvp\_\{vis\}<\\tau\_\{v\}or

¬BCP​\(Σ∪\{c\}\)\\neg\\text\{BCP\}\(\\Sigma\\cup\\\{c\\\}\)then⊳\\trianglerightCheck visual & logical validity

15:

all\_ok←False\\text\{all\\\_ok\}\\leftarrow\\text\{False\};break

16:endif

17:endfor

18:ifall\_okthen

19:

Σ←Σ∪Ct\\Sigma\\leftarrow\\Sigma\\cup C\_\{t\};

trace←trace\+\[rt,Ct\]\\text\{trace\}\\leftarrow\\text\{trace\}\+\[r\_\{t\},C\_\{t\}\]
20:else⊳\\trianglerightViolation→\\rightarrowbacktrack

21:if

Σ=∅\\Sigma=\\emptysetthen

trace←\[<RETRY\>\]\\text\{trace\}\\leftarrow\[\\texttt\{<RETRY\>\}\]
22:else

23:Revert

Σ\\Sigmaandtraceto most recent anchor

cl​a​s​t∈Σc\_\{last\}\\in\\Sigma
24:

trace←trace\+\[<RETRY\>\]\\text\{trace\}\\leftarrow\\text\{trace\}\+\[\\texttt\{<RETRY\>\}\]
25:endif

26:

retries←retries\+1\\text\{retries\}\\leftarrow\\text\{retries\}\+1
27:endif

28:endwhile

29:if

retries\>B\\text\{retries\}\>Bandtraceincompletethen⊳\\trianglerightRetry budget exhausted

30:

a←valid\(fans\(trace\)\)?fans\(trace\):Mθ\.fallback\(I,q\)a\\leftarrow\\text\{valid\}\(f\_\{\\text\{ans\}\}\(\\text\{trace\}\)\)\\text\{ ? \}f\_\{\\text\{ans\}\}\(\\text\{trace\}\):M\_\{\\theta\}\.\\text\{fallback\}\(I,q\)
31:else

32:

a←fans​\(trace\)a\\leftarrow f\_\{\\text\{ans\}\}\(\\text\{trace\}\)
33:endif

34:return

aa

#### 3\.2\.3\.Constraint Propagation Module

The CPM acts as an external verifier\. Itsneural component\(gψg\_\{\\psi\}\) is trained end\-to\-end while itssymbolic component\(BCP\) is always a non\-differentiable hard combinatorial check, used identically during training \(for computing grounding labels and detecting synthetic violations\) and at inference \(as a hard gate in Algorithm[1](https://arxiv.org/html/2607.16727#alg1)\)\. The CPM maintains aconstraint storeΣt=\{ct′,j:\(t′,j\)∈𝒜,t′≤t\}\\Sigma\_\{t\}=\\\{c\_\{t^\{\\prime\},j\}:\(t^\{\\prime\},j\)\\in\\mathcal\{A\},\\;t^\{\\prime\}\\leq t\\\}that grows as non\-null anchors are emitted\.

Visual grounding check\.Each non\-null anchorct,jc\_\{t,j\}is verified against the visual feature bank𝐕\\mathbf\{V\}via a lightweightgrounding headgψg\_\{\\psi\}\. The input togψg\_\{\\psi\}is the concatenation of \(i\) the region\-level visual feature𝐯c∈ℝdv\\mathbf\{v\}\_\{c\}\\in\\mathbb\{R\}^\{d\_\{v\}\}, obtained by mean\-pooling the RoI\-Aligned features across all entity arguments of the anchor \(as described in§\\S[3\.2\.2](https://arxiv.org/html/2607.16727#S3.SS2.SSS2)\), and \(ii\) a text embedding𝐡c∈ℝdt\\mathbf\{h\}\_\{c\}\\in\\mathbb\{R\}^\{d\_\{t\}\}of the anchor string, taken from the last hidden layer of the LLM at the</CON\>token position\. The grounding head is a 2\-layer MLP:

gψ​\(c,𝐕\)=σ​\(𝐖2​GELU​\(LN​\(𝐖1​\[𝐯c;𝐡c\]\+𝐛1\)\)\+𝐛2\),g\_\{\\psi\}\(c,\\mathbf\{V\}\)=\\sigma\\\!\\big\(\\mathbf\{W\}\_\{2\}\\,\\text\{GELU\}\(\\text\{LN\}\(\\mathbf\{W\}\_\{1\}\[\\mathbf\{v\}\_\{c\};\\,\\mathbf\{h\}\_\{c\}\]\+\\mathbf\{b\}\_\{1\}\)\)\+\\mathbf\{b\}\_\{2\}\\big\),
with weight matrices𝐖1∈ℝ512×\(dv\+dt\)\\mathbf\{W\}\_\{1\}\\in\\mathbb\{R\}^\{512\\times\(d\_\{v\}\+d\_\{t\}\)\},𝐖2∈ℝ1×512\\mathbf\{W\}\_\{2\}\\in\\mathbb\{R\}^\{1\\times 512\}, layer normalization \(LN\), and sigmoid outputσ\\sigma\. Concretely, forLLaVA\-NeXT\-13B:dv=1024d\_\{v\}=1024\(CLIP ViT\-L/14\),dt=5120d\_\{t\}=5120\(LLaMA\-2\-13B\), so the input dimension is61446144; forQwen2\-VL\-7B:dv=1408d\_\{v\}=1408\(ViT\-bigG\),dt=4096d\_\{t\}=4096\(Qwen\-7B\), input dimension55045504\. Total grounding head parameters: 3\.2M \(LLaVA\-NeXT\) / 2\.9M \(Qwen\-VL\)\.

The grounding head outputspvis​\(ct,j∣I\)=gψ​\(ct,j,𝐕\)∈\[0,1\]p\_\{\\text\{vis\}\}\(c\_\{t,j\}\\mid I\)=g\_\{\\psi\}\(c\_\{t,j\},\\mathbf\{V\}\)\\in\[0,1\]\. Ifpvis​\(ct,j∣I\)<τvp\_\{\\text\{vis\}\}\(c\_\{t,j\}\\mid I\)<\\tau\_\{v\}, the anchor is flagged asvisually violated\.

Mutual consistency check\.We additionally performBoolean Constraint Propagation \(BCP\)overΣt∪\{ct,j\}\\Sigma\_\{t\}\\cup\\\{c\_\{t,j\}\\\}\. Becauseℒc\\mathcal\{L\}\_\{c\}is propositional with finite domains, checking satisfiability of the accumulated constraint set is tractable\. We convertΣt∪\{ct,j\}\\Sigma\_\{t\}\\cup\\\{c\_\{t,j\}\\\}into a conjunction of literals and apply unit propagation; if the empty clause is derived, alogical contradictionis detected\. BCP is a purely symbolic, non\-differentiable procedure and never receives gradients\.

Justification\.The two\-pronged check \(neural grounding \+ symbolic BCP\) is complementary: the grounding head catches factual errors about the image that BCP alone cannot detect \(since BCP only checks inter\-constraint consistency\), while BCP catches logical contradictions that the grounding head might miss due to soft thresholding\. Keeping BCP non\-differentiable preserves its soundness guarantee\.

#### 3\.2\.4\.Backtrack Controller

When the CPM flags a violation at anchorct,jc\_\{t,j\}, thebacktrack controllerhalts autoregressive generation and reverts the trace to the most recentconsistent checkpoint\. Formally, since all anchors currently inΣt\\Sigma\_\{t\}were individually verified when admitted \(and removing constraints from a satisfiable set preserves satisfiability\), the checkpoint is simply themost recent anchor inΣt\\Sigma\_\{t\}in trace order—i\.e\., the anchor\(t′,j′\)\(t^\{\\prime\},j^\{\\prime\}\)with the largest trace position such that\(t′,j′\)<\(t,j\)\(t^\{\\prime\},j^\{\\prime\}\)<\(t,j\)andct′,j′∈Σtc\_\{t^\{\\prime\},j^\{\\prime\}\}\\in\\Sigma\_\{t\}\. Generation resumes from that checkpoint with the violating anchor, its preceding reasoning step, and all intervening material removed from the context\. A special<RETRY\>token is appended to signal the model to explore an alternative reasoning path\. A maximum retry budgetB=3B=3prevents infinite loops\.

Edge case: empty constraint store \(Σt=∅\\Sigma\_\{t\}=\\emptyset\)\.If no prior consistent checkpoint exists \(i\.e\., the violation occurs before any anchor has been successfully admitted\), the backtrack controllerrestarts generation from scratch: the trace is reset to the empty sequence,<RETRY\>is prepended to the context \(yielding the input\(I,q,<RETRY\>\)\(I,q,\\texttt\{<RETRY\>\}\)\), and the retry counter is incremented\. This ensures the model always has a well\-defined recovery point\.

Retry budget exhaustion \(retries\>B\\text\{retries\}\>B\)\.If the retry budgetBBis exhausted without producing a complete, violation\-free trace, the controller terminates generation and passes the current trace—truncated at the last consistent checkpoint if necessary—to the answer extractorfansf\_\{\\text\{ans\}\}\. In this fallback mode,fansf\_\{\\text\{ans\}\}attempts answer extraction from the \(possibly incomplete\) trace\. If no answer span is found \(e\.g\., the trace is too short\), a secondary extraction is performed by prompting the base MLLM with the original\(I,q\)\(I,q\)without CART \(i\.e\., standard unconstrained generation\), and the resulting answer is returned with a ‘FALLBACK‘ flag indicating reduced reliability\. Empirically, retry exhaustion occurs in only 2\.1% of GQA\-testdev instances and 4\.7% of VCR\-val instances\.

Justification forB=3B=3\.A pilot ablation overB∈\{1,2,3,5,10\}B\\in\\\{1,2,3,5,10\\\}on GQA\-val \(1K instances\) showed accuracy gains plateauing atB=3B=3\(\+0\.2% fromB=3B=3toB=5B=5, within noise\) while mean inference latency grows linearly withBB\.

Inference\-time anchor emission failures\.If the model fails to emit any<CON\>…</CON\>or<NULL\_CON/\>token after a reasoning step \(e\.g\., due to distribution shift\), the step is treated as implicitly unconstrained \(<NULL\_CON/\>\) and generation continues without a CPM check\. Malformed anchors failing delimiter parsing are treated identically\. Empirically, the well\-formed anchor emission rate is 94\.6% for LLaVA\-NeXT\-13B and 92\.1% for Qwen2\-VL\-7B \(measured on GQA\-testdev\)\.

## 4\.Experimental Setup

### 4\.1\.Datasets

We evaluate on five benchmarks that span a range of visual reasoning complexities:

- •GQA\(Hudson and Manning,[2019](https://arxiv.org/html/2607.16727#bib.bib2)\): compositional visual question answering over real\-world images with functional program annotations\. We use the balanced testdev split \(12,578 questions\)\.
- •CLEVR\-CoGenT\(Johnsonet al\.,[2017](https://arxiv.org/html/2607.16727#bib.bib1)\): synthetic geometric reasoning requiring counting, spatial relation, and attribute comparison over rendered scenes\. We evaluate on Condition A \(15,000 questions\)\.
- •VCR\(Zellerset al\.,[2019](https://arxiv.org/html/2607.16727#bib.bib3)\): visual commonsense reasoning requiring free\-form rationale generation for multiple\-choice QA over movie scenes\. We evaluate on the val split \(26,534 questions\)\.
- •MM\-Vet\(Yuet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib36)\): an open\-ended multimodal evaluation benchmark covering six core capabilities \(recognition, knowledge, OCR, spatial awareness, language generation, math\)\. We report the GPT\-4\-graded overall score\.
- •POPE\(Liet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib37)\): a polling\-based benchmark for evaluating object hallucination in MLLMs\. We report F1 score on the random, popular, and adversarial splits \(averaged\)\.

Table 1\.End\-task accuracy \(%\) across five benchmarks\. We compare CART against base MLLMs with and without Chain\-of\-Thought prompting, inference\-time scaling methods, modular program\-synthesis pipelines, and fine\-tuned self\-correction baselines on two backbone architectures\.Bold= best per backbone;underline= second best\.Blue rows= CART \(Full\)\. The LLaVA\-NeXT\-34B row is reported as a scaling illustration for CART only; we did not run the baselines at 34B, so its numbers should not be read as head\-to\-head comparisons\.Method ConfigurationBackbone Arch\.Fine\-TunedGQACLEVRVCRMM\-VetPOPE F1Base MLLM \(No CoT\)Qwen2\-VL\-7BNo48\.560\.156\.234\.280\.1Base MLLM \(\+ CoT\)No51\.264\.358\.436\.881\.5Tree\-of\-ThoughtsNo54\.870\.461\.240\.182\.8CART\-AnchorsYes56\.573\.563\.542\.483\.9CART \(Full, Ours\)Yes62\.179\.466\.846\.586\.4Base MLLM \(No CoT\)LLaVA\-NeXT\-13BNo53\.465\.260\.339\.181\.3Base MLLM \(\+ CoT\)No56\.771\.563\.142\.883\.7Tree\-of\-ThoughtsNo60\.576\.864\.845\.484\.1CART\-AnchorsYes64\.882\.368\.550\.186\.5CART \(Full, Ours\)Yes69\.486\.771\.454\.889\.1VisProgQwen2\-VL\-7BNo55\.470\.561\.440\.282\.7Faithful CoTNo54\.269\.160\.539\.482\.2ReflexionNo54\.569\.661\.039\.882\.5DDCoT \(Zero\-Shot\)No55\.871\.261\.840\.583\.1Visual Verif\. \(ZS\)No56\.171\.862\.140\.983\.4VisProgLLaVA\-NeXT\-13BNo61\.278\.460\.543\.682\.5Faithful CoTNo59\.875\.263\.244\.183\.5ReflexionNo60\.175\.964\.544\.983\.8DDCoT \(Zero\-Shot\)No61\.577\.265\.146\.284\.5Visual Verif\. \(ZS\)No62\.378\.565\.746\.884\.9DDCoT \(LoRA\-FT\)Qwen2\-VL\-7BYes57\.674\.264\.143\.184\.5Visual Verif\. \(FT\)Yes58\.275\.164\.843\.884\.9Self\-ConsistencyYes57\.974\.664\.443\.584\.7Self\-RefineYes57\.473\.863\.942\.984\.2DDCoT \(LoRA\-FT\)LLaVA\-NeXT\-13BYes63\.880\.167\.448\.585\.8Visual Verif\. \(FT\)Yes64\.581\.668\.249\.386\.2Self\-ConsistencyYes64\.281\.067\.849\.086\.0Self\-RefineYes63\.579\.867\.148\.285\.4CART \(Full, Ours\)LLaVA\-NeXT\-34BYes73\.290\.574\.558\.691\.2
### 4\.2\.Baselines

We compare CART against four categories of methods on Qwen2\-VL\-7B and LLaVA\-NeXT\-13B:

- •Prompting\-based: Base MLLM with and without CoT prompting\.
- •Inference\-time scaling: Tree\-of\-Thoughts\(Yaoet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib15)\), which explores multiple reasoning branches via LLM\-based evaluation; Reflexion\(Shinnet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib16)\), which uses verbal self\-critique for iterative refinement; and Self\-Consistency\(Wanget al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib14)\), which marginalizes over sampled chains by majority voting\.
- •Program synthesis: VisProg\(Gupta and Kembhavi,[2023](https://arxiv.org/html/2607.16727#bib.bib18)\), which generates executable visual programs; Faithful CoT\(Lyuet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib27)\), which interleaves natural language with symbolic reasoning; and DDCoT\(Zhenget al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib23)\), which decomposes questions into sub\-problems\.
- •Fine\-tuned self\-correction: DDCoT \(LoRA\-FT\), Visual Verification \(FT\), Self\-Consistency \(FT\), and Self\-Refine\(Madaanet al\.,[2023](https://arxiv.org/html/2607.16727#bib.bib17)\)\(FT\), all fine\-tuned on the same 218K training instances using identical LoRA configuration \(rank 64\) for a fair comparison\.Visual Verification\(Denget al\.,[2024](https://arxiv.org/html/2607.16727#bib.bib28)\)prompts the MLLM to re\-examine the image after generating an answer and revise if inconsistencies are found; critically, it relies on the model’s own internal cross\-attention maps for verification rather than an external grounder or symbolic consistency check, making it a self\-referential verifier\. Its zero\-shot variant \(Visual Verif\. ZS\) uses the same prompting strategy without fine\-tuning\.

We additionally reportCART\-Anchors, which uses constraint\-annotated training data but disables CPM and backtracking at inference, isolating runtime verification’s effect\.

Table 2\.Ablation studies on LLaVA\-NeXT\-13B\. Top block: subtractive ablations removing individual CART components\. Middle block: additive build\-up from fine\-tuned baseline\. Bottom block: sensitivity to retry budgetBBand visual grounding thresholdτv\\tau\_\{v\}\. Snowball rate, constraint violation rate \(CVR\), mean trace length, and per\-instance latency are measured on a 2,000\-instance diagnostic subset of GQA\-testdev\.Bold= best in column\.Ablation ConfigurationGQACLEVRVCRSnowball↓\\downarrowCVR \(%\)↓\\downarrowTrace LenLatency \(s\)CART Full69\.486\.771\.40\.1414\.216\.52\.41CART w/o Backtrack \(A2\)65\.282\.568\.80\.5214\.516\.21\.95CART w/o BCP Logic \(A3\)67\.184\.670\.10\.2311\.416\.42\.38CART w/o Neural Grnd \(A4\)66\.483\.269\.50\.318\.216\.32\.05CART w/o VarFreq \(A5\)66\.883\.869\.80\.1825\.424\.13\.84CART w/o Anchors \(A6\)64\.882\.368\.50\.65N/A15\.81\.82CART w/ Attn Grnd \(A7\)66\.984\.169\.90\.2521\.316\.42\.35Base FT Only \(B1\)64\.882\.368\.50\.65N/A15\.81\.82Base FT \+ Fixed Freq \(B2\)65\.182\.768\.70\.62N/A23\.52\.45Base FT \+ VarFreq \(B3\)65\.583\.168\.90\.60N/A16\.11\.90Build \+ Neural Grnd \(B4\)67\.885\.270\.40\.2812\.516\.32\.35Build \+ BCP Logic \(B5\)68\.585\.970\.80\.1913\.816\.42\.39Retry Budget:B=0B\{=\}065\.282\.568\.80\.5214\.216\.21\.95Retry Budget:B=1B\{=\}167\.584\.870\.20\.2914\.216\.32\.15Retry Budget:B=2B\{=\}268\.886\.171\.00\.1714\.216\.42\.32Retry Budget:B=3B\{=\}3\(default\)69\.486\.771\.40\.1414\.216\.52\.41Retry Budget:B=5B\{=\}569\.586\.871\.50\.1314\.216\.62\.85Retry Budget:B=10B\{=\}1069\.586\.871\.50\.1314\.216\.73\.42Threshold:τv=0\.60\\tau\_\{v\}\{=\}0\.6066\.583\.569\.60\.356\.516\.22\.12Threshold:τv=0\.75\\tau\_\{v\}\{=\}0\.7568\.285\.470\.80\.2110\.816\.42\.28Threshold:τv=0\.85\\tau\_\{v\}\{=\}0\.85\(default\)69\.486\.771\.40\.1414\.216\.52\.41Threshold:τv=0\.95\\tau\_\{v\}\{=\}0\.9567\.885\.170\.40\.1628\.517\.53\.15
### 4\.3\.Evaluation Metrics

We report standard end\-task accuracy \(or F1 for POPE\) for all methods\. To diagnose CART’s internal error\-correction behavior, we additionally introduce three diagnostic metrics measured on a 2,000\-instance subset of GQA\-testdev: \(i\)Snowball Rate\(𝒮\\mathcal\{S\}\), the conditional probability of cascading failure after a first error; \(ii\)Constraint Violation Rate\(CVR\), the fraction of emitted anchors flagged by the CPM; and \(iii\)Error Attribution Precision\(EAP\), the fraction of backtracks correctly targeting the earliest erroneous step\. Full metric definitions, annotation protocols, and inter\-annotator agreement are detailed in Appendix[C](https://arxiv.org/html/2607.16727#A3)\. Hyperparameters and training details are also provided in Appendix[C](https://arxiv.org/html/2607.16727#A3)\.

Reproducibility\.All fine\-tuned results in Table[1](https://arxiv.org/html/2607.16727#S4.T1)are averaged over three random seeds\. We will release the constraint\-annotation generation pipeline, the 218K training instances, the grounding\-head and LoRA weights, and all inference/evaluation code to support independent replication\.

## 5\.Experimental Results

We evaluate CART across five benchmarks spanning structured geometric reasoning \(CLEVR\-CoGenT\), compositional visual QA \(GQA\), commonsense inference \(VCR\), open\-ended multimodal evaluation \(MM\-Vet\), and object hallucination detection \(POPE\)\. All fine\-tuned variants are evaluated with identical setups\. Table[1](https://arxiv.org/html/2607.16727#S4.T1)reports end\-task accuracy\.

Without CART, LLaVA\-NeXT\-13B achieves 53\.4% on GQA; standard CoT prompting yields a modest improvement to 56\.7%\. Inference\-time methods such as Tree\-of\-Thoughts and Reflexion provide limited gains, as resampling and verbal self\-critique cannot rectify grounding errors against the image\. Programmatic pipelines \(VisProg\) perform well on synthetic benchmarks but degrade on VCR, where rigid execution templates cannot capture open\-ended reasoning\.

The key comparison isolates the effect of runtime constraint verification\. CART\-Anchors—trained on the same 218K instances with identical LoRA configuration but without the CPM or backtrack controller—reaches 64\.8% on GQA\. The full CART framework achieves 69\.4%, a \+4\.6 pp improvement\. This gap confirms that exposure to constraint\-annotated traces alone is insufficient; active runtime verification and correction are necessary to arrest error propagation\.

CART exhibits consistent gains across model scales\. On the smaller Qwen2\-VL\-7B backbone, CART achieves 62\.1% on GQA, narrowing the gap to unconstrained models with nearly twice the parameters\. Scaling to LLaVA\-NeXT\-34B pushes accuracy to 73\.2% on GQA and 90\.5% on CLEVR, demonstrating that even strong base models benefit from runtime constraint verification\. The consistent relative improvement across scales suggests that error snowballing is an inherent property of autoregressive decoding, not a weakness of any particular model\.

Table 3\.Inference latency profiling across backbone scales and batch sizes on a single A100\-80GB GPU\. Overhead factor is the ratio of CART latency to base autoregressive latency, showing that the constraint propagation module adds at most 18% wall\-clock overhead\.Bold= lowest overhead per backbone\.BackboneBatch SizeBaseLatency \(s\)CARTLatency \(s\)OverheadFactorQwen2\-VL\-7B11\.752\.061\.18×\\timesQwen2\-VL\-7B42\.102\.411\.15×\\timesQwen2\-VL\-7B163\.053\.541\.16×\\timesLLaVA\-NeXT\-13B12\.152\.411\.12×\\timesLLaVA\-NeXT\-13B42\.652\.991\.13×\\timesLLaVA\-NeXT\-13B164\.124\.651\.13×\\timesLLaVA\-NeXT\-34B14\.304\.731\.10×\\timesLLaVA\-NeXT\-34B168\.859\.731\.10×\\times

Zero\-shot evaluations on MM\-Vet and POPE—benchmarks unseen during training—provide evidence that CART’s constraint emission policies generalize beyond the training distribution\. The 13B model achieves 54\.8 on MM\-Vet and 89\.1 F1 on POPE, exceeding all baselines including external verification methods\. This out\-of\-distribution transfer confirms that the learned verification behavior is not dataset\-specific but reflects a general capability for detecting visual\-linguistic inconsistencies\.

### 5\.1\.Ablation Studies

We conducted subtractive and additive ablation studies on LLaVA\-NeXT\-13B, correlating end\-task accuracy with internal diagnostic metrics on a 2,000\-instance GQA\-testdev subset to isolate each component’s contribution\.

Removing any single component causes substantial degradation\. Disabling the backtrack controller \(CPM flags violations passively\) dropped accuracy to 65\.2% and spiked the snowball rate to 0\.52, demonstrating that detection alone is insufficient without the ability to re\-route generation\. Replacing Grounding DINO with internal cross\-attention maps inflated the constraint violation rate—Grounding DINO achieves0\.720\.72mean IoU on anchor entity regions versus0\.410\.41for cross\-attention—explaining the degraded verification precision\.

Additive build\-up confirmed the importance of emission design: a fixed\-frequency scheme inflated trace length to 23\.5 tokens with hallucinated vacuous constraints, while variable\-frequency emission restored it to 16\.1 tokens by allowing dynamic modulation via null tokens\.

Accuracy plateaued at retry budgetB=3B\{=\}3;B=10B\{=\}10yielded negligible gains with linearly increasing latency\. Thresholdτv=0\.85\\tau\_\{v\}\{=\}0\.85optimally filtered low\-confidence noise; atτv=0\.95\\tau\_\{v\}\{=\}0\.95, the false rejection rate doubled toα≈0\.11\\alpha\{\\approx\}0\.11, causing unnecessary backtracks on8\.2%8\.2\\%of correct traces\.

Under calibrated parameters, CART compressed the snowball rate from 0\.65 to 0\.14 on GQA \(similarly on VCR\), validating Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)\. Error attribution precision reached 0\.82, confirming that the backtrack controller correctly targets the earliest erroneous step in most corrections\.

Sensitivity to the entity grounder\.Replacing Grounding DINO with GLIP\(Liet al\.,[2022](https://arxiv.org/html/2607.16727#bib.bib38)\)\(δ≈0\.09\\delta\{\\approx\}0\.09\) or OWLv2\(Mindereret al\.,[2024](https://arxiv.org/html/2607.16727#bib.bib39)\)\(δ≈0\.12\\delta\{\\approx\}0\.12\) yields 68\.1% and 67\.5% on GQA, respectively \(vs\. 69\.4% with Grounding DINO,δ≈0\.07\\delta\{\\approx\}0\.07\)\. All configurations outperform the best non\-CART baseline \(64\.8%\), confirming graceful degradation with grounder quality as predicted by Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)\.

Predicate coverage ablation\.We evaluated CART with 7, 14 \(default\), and 18 predicates\. On GQA: 7 predicates yield 66\.9% \(γ≈0\.61\\gamma\{\\approx\}0\.61,𝒮=0\.21\\mathcal\{S\}\{=\}0\.21\); 14 yield 69\.4% \(γ≈0\.72\\gamma\{\\approx\}0\.72,𝒮=0\.14\\mathcal\{S\}\{=\}0\.14\); 18 yield 69\.8% \(γ≈0\.75\\gamma\{\\approx\}0\.75,𝒮=0\.13\\mathcal\{S\}\{=\}0\.13\)\. Diminishing returns beyond 14 predicates suggest the default coverage captures most error\-prone steps, while the 7\-predicate drop confirmsγ\\gammaas the primary driver of CART’s benefit \(Corollary[6](https://arxiv.org/html/2607.16727#A1.Thmtheorem6)\)\.

### 5\.2\.Scalability and Computational Efficiency

A common concern with runtime verification is inference overhead\. Table[3](https://arxiv.org/html/2607.16727#S5.T3)profiles wall\-clock latency across backbone scales and batch sizes on a single A100\-80GB GPU\.

Across all configurations, CART adds 10–18% overhead relative to base autoregressive generation, far below the multi\-fold penalties typical of iterative search methods\. The BCP module runs in sub\-millisecond time per check and scales linearly with constraint\-store size\. Notably, overheaddecreaseswith model scale: from1\.151\.15–1\.18×1\.18\\timeson Qwen2\-VL\-7B to1\.10×1\.10\\timeson LLaVA\-NeXT\-34B, because the fixed cost of the grounding head and BCP becomes a smaller fraction of the total compute as the base model grows\. This favorable scaling property ensures that CART remains practical as foundation models continue to increase in size\.

A per\-component breakdown reveals that Grounding DINO accounts for 60–65% of the CPM overhead, followed by the grounding head forward pass \(25–30%\) and BCP \(5–10%\)\. Crucially, the Grounding DINO features are computed once per image and cached across all anchors in the trace, amortizing the dominant cost\. The grounding head itself is a lightweight 2\-layer MLP \(∼3\.2\{\\sim\}3\.2M parameters for LLaVA\-NeXT /∼2\.9\{\\sim\}2\.9M for Qwen2\-VL, consistent with §3\.2\.3\), adding negligible memory: the peak GPU memory increase is<<0\.4 GB over the base model for all configurations, and CART introduces no additional KV\-cache overhead since constraint tokens are standard vocabulary items processed by the existing attention mechanism\.

Compared to multi\-pass inference\-time methods, CART’s single\-pass architecture provides a substantial efficiency advantage\. Self\-Consistency \(m=5m\{=\}5\) requires5×5\\timesthe base inference cost; Tree\-of\-Thoughts with 3 branches incurs33–4×4\\timesoverhead due to repeated forward passes and LLM\-based branch evaluation\. CART achieves comparable or superior accuracy gains \(Table[1](https://arxiv.org/html/2607.16727#S4.T1)\) at1\.101\.10–1\.18×1\.18\\timescost—an order of magnitude more efficient\. This difference is especially pronounced for long reasoning traces, where multi\-pass methods multiply cost per token while CART’s per\-anchor verification cost remains constant regardless of trace length\.

## 6\.Conclusions

We presented Constraint\-Anchored Reasoning Traces \(CART\), a neuro\-symbolic framework that interleaves natural language reasoning with verifiable symbolic constraint anchors, verified at runtime by a dual\-pronged Constraint Propagation Module \(neural grounding head \+ Boolean Constraint Propagation\) and corrected via a backtrack controller\. Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)establishes that CART reduces the snowball rate exponentially in the number of post\-error anchors; empirically, the snowball rate drops from 0\.65 to 0\.14 on GQA\. Across five benchmarks, CART consistently outperforms all baselines—reaching 69\.4% on GQA \(\+4\.6 over the anchor\-only ablation\), 86\.7% on CLEVR, and 89\.1 F1 on POPE with LLaVA\-NeXT\-13B, scaling further to 73\.2%, 90\.5%, and 91\.2 with LLaVA\-NeXT\-34B—while adding at most 18% inference overhead\. Ablation studies confirm every component is essential, and the three diagnostic metrics introduced \(snowball rate, constraint violation rate, error attribution precision\) offer new tools for evaluating error propagation in multimodal reasoning\.

## References

- J\. Andreas, M\. Rohrbach, T\. Darrell, and D\. Klein \(2016\)Neural module networks\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 39–48\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p2.1)\.
- R\. Dechter \(2003\)Constraint processing\.Elsevier\.Cited by:[§A\.5](https://arxiv.org/html/2607.16727#A1.SS5.1.p1.10)\.
- A\. Deng, Z\. Lu, Y\. Chen, Q\. Wu, Z\. Cao, L\. Wang, and J\. Liu \(2024\)Seeing is believing: mitigating hallucination in large vision\-language models via CLIP\-guided decoding\.arXiv preprint arXiv:2402\.15300\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p3.1),[4th item](https://arxiv.org/html/2607.16727#S4.I2.i4.p1.1)\.
- W\. F\. Dowling and J\. H\. Gallier \(1984\)Linear\-time algorithms for testing the satisfiability of propositional horn formulae\.The Journal of Logic Programming1\(3\),pp\. 267–284\.Cited by:[§A\.5](https://arxiv.org/html/2607.16727#A1.SS5.1.p1.10)\.
- C\. Guo, G\. Pleiss, Y\. Sun, and K\. Q\. Weinberger \(2017\)On calibration of modern neural networks\.InInternational Conference on Machine Learning,pp\. 1321–1330\.Cited by:[Appendix D](https://arxiv.org/html/2607.16727#A4.p15.2)\.
- T\. Gupta and A\. Kembhavi \(2023\)Visual programming: compositional visual reasoning without training\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 14953–14962\.Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p2.1),[§2](https://arxiv.org/html/2607.16727#S2.p2.1),[3rd item](https://arxiv.org/html/2607.16727#S4.I2.i3.p1.1)\.
- K\. He, G\. Gkioxari, P\. Dollár, and R\. Girshick \(2017\)Mask r\-cnn\.InProceedings of the IEEE international conference on computer vision,pp\. 2961–2969\.Cited by:[3rd item](https://arxiv.org/html/2607.16727#S3.I1.i3.p1.1)\.
- E\. J\. Hu, Y\. Shen, P\. Wallis, Z\. Allen\-Zhu, Y\. Li, S\. Wang, L\. Wang, and W\. Chen \(2022\)LoRA: low\-rank adaptation of large language models\.InInternational Conference on Learning Representations,Cited by:[§B\.1](https://arxiv.org/html/2607.16727#A2.SS1.p1.11)\.
- R\. Hu, J\. Andreas, M\. Rohrbach, T\. Darrell, and K\. Saenko \(2017\)Learning to reason: end\-to\-end module networks for visual question answering\.InProceedings of the IEEE International Conference on Computer Vision,pp\. 804–813\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p2.1)\.
- D\. A\. Hudson and C\. D\. Manning \(2019\)Gqa: a new dataset for real\-world visual reasoning and compositional question answering\.InProceedings of the CVPR,pp\. 6700–6709\.Cited by:[Appendix D](https://arxiv.org/html/2607.16727#A4.p2.1),[§1](https://arxiv.org/html/2607.16727#S1.p5.1),[1st item](https://arxiv.org/html/2607.16727#S4.I1.i1.p1.1)\.
- J\. Johnson, B\. Hariharan, L\. Van Der Maaten, L\. Fei\-Fei, C\. Lawrence Zitnick, and R\. Girshick \(2017\)Clevr: a diagnostic dataset for compositional language and elementary visual reasoning\.InProceedings of the IEEE conference on computer vision and pattern recognition,pp\. 2901–2910\.Cited by:[Appendix D](https://arxiv.org/html/2607.16727#A4.p2.1),[§1](https://arxiv.org/html/2607.16727#S1.p5.1),[2nd item](https://arxiv.org/html/2607.16727#S4.I1.i2.p1.1)\.
- T\. Kojima, S\. S\. Gu, M\. Reid, Y\. Matsuo, and Y\. Iwasawa \(2022\)Large language models are zero\-shot reasoners\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 22199–22213\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p1.1)\.
- L\. H\. Li, P\. Zhang, H\. Zhang, J\. Yang, C\. Li, Y\. Zhong, L\. Wang, L\. Yuan, L\. Zhang, J\. Hwang,et al\.\(2022\)Grounded language\-image pre\-training\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 10965–10975\.Cited by:[§5\.1](https://arxiv.org/html/2607.16727#S5.SS1.p6.3)\.
- Y\. Li, Y\. Du, K\. Zhou, J\. Wang, W\. X\. Zhao, and J\. Wen \(2023\)Evaluating object hallucination in large vision\-language models\.arXiv preprint arXiv:2305\.10355\.Cited by:[5th item](https://arxiv.org/html/2607.16727#S4.I1.i5.p1.1)\.
- H\. Liu, C\. Li, Y\. Li, B\. Li, Y\. Zhang, S\. Shen, and Y\. J\. Lee \(2024a\)LLaVA\-next: improved reasoning, ocr, and world knowledge\.External Links:[Link](https://llava-vl.github.io/blog/2024-01-30-llava-next/)Cited by:[Appendix B](https://arxiv.org/html/2607.16727#A2.p1.1),[Appendix D](https://arxiv.org/html/2607.16727#A4.p14.7),[§1](https://arxiv.org/html/2607.16727#S1.p5.1)\.
- S\. Liu, Z\. Zeng, T\. Ren, F\. Li, H\. Zhang, J\. Yang, Q\. Jiang, C\. Li, J\. Yang, H\. Su,et al\.\(2024b\)Grounding DINO: marrying dino with grounded pre\-training for open\-set object detection\.InECCV,pp\. 38–55\.Cited by:[Appendix B](https://arxiv.org/html/2607.16727#A2.p2.1),[§2](https://arxiv.org/html/2607.16727#S2.p3.1),[§3\.2\.2](https://arxiv.org/html/2607.16727#S3.SS2.SSS2.p1.1)\.
- Z\. Liu, Y\. Lin, Y\. Cao, H\. Hu, Y\. Wei, Z\. Zhang, S\. Lin, and B\. Guo \(2021\)Swin transformer: hierarchical vision transformer using shifted windows\.InICCV,pp\. 10012–10022\.Cited by:[Appendix B](https://arxiv.org/html/2607.16727#A2.p2.1)\.
- P\. Lu, S\. Mishra, T\. Xia, L\. Qiu, K\. Chang, S\. Zhu, O\. Tafjord, P\. Clark, and A\. Kalyan \(2022\)Learn to explain: multimodal reasoning via thought chains for science question answering\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 2507–2521\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p1.1)\.
- Q\. Lyu, S\. Havaldar, A\. Stein, L\. Zhang, D\. Rao, E\. Wong, M\. Apidianaki, and C\. Callison\-Burch \(2023\)Faithful chain\-of\-thought reasoning\.arXiv preprint arXiv:2301\.13379\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p2.1),[3rd item](https://arxiv.org/html/2607.16727#S4.I2.i3.p1.1)\.
- A\. Madaan, N\. Tandon, P\. Gupta, S\. Hallinan, L\. Gao, S\. Wiegreffe, U\. Alon, N\. Dziri, S\. Prabhumoye, Y\. Yang,et al\.\(2023\)Self\-refine: iterative refinement with self\-feedback\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p2.1),[§2](https://arxiv.org/html/2607.16727#S2.p3.1),[4th item](https://arxiv.org/html/2607.16727#S4.I2.i4.p1.1)\.
- M\. Minderer, A\. Gritsenko, and N\. Houlsby \(2024\)Scaling open\-vocabulary object detection\.Advances in Neural Information Processing Systems36\.Cited by:[§5\.1](https://arxiv.org/html/2607.16727#S5.SS1.p6.3)\.
- J\. Ren, S\. Rajbhandari, R\. Y\. Aminabadi, O\. Ruwase, S\. Yang, M\. Zhang, D\. Li, and Y\. He \(2021\)\{\\\{zero\-Offload\}\\\}: democratizing\{\\\{billion\-scale\}\\\}model training\.In2021 USENIX Annual Technical Conference \(USENIX ATC 21\),pp\. 551–564\.Cited by:[Appendix D](https://arxiv.org/html/2607.16727#A4.p14.7)\.
- N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. Yao \(2023\)Reflexion: language agents with verbal reinforcement learning\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p2.1),[§2](https://arxiv.org/html/2607.16727#S2.p3.1),[2nd item](https://arxiv.org/html/2607.16727#S4.I2.i2.p1.1)\.
- D\. Surís, S\. Menon, and C\. Vondrick \(2023\)Vipergpt: visual inference via python execution for reasoning\.InProceedings of the IEEE/CVF International Conference on Computer Vision,pp\. 11888–11898\.Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p2.1),[§2](https://arxiv.org/html/2607.16727#S2.p2.1)\.
- P\. Wang, S\. Bai, S\. Tan, S\. Wang, Z\. Fan, J\. Bai, K\. Chen, X\. Liu, J\. Wang, W\. Ge,et al\.\(2024\)Qwen2\-vl: enhancing vision\-language model’s perception of the world at any resolution\.arXiv preprint arXiv:2409\.12191\.Cited by:[Appendix B](https://arxiv.org/html/2607.16727#A2.p1.1),[§1](https://arxiv.org/html/2607.16727#S1.p5.1)\.
- X\. Wang, J\. Wei, D\. Schuurmans, Q\. V\. Le, E\. H\. Chi, S\. Narang, A\. Chowdhery, and D\. Zhou \(2023\)Self\-consistency improves chain of thought reasoning in language models\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p2.1),[§2](https://arxiv.org/html/2607.16727#S2.p1.1),[2nd item](https://arxiv.org/html/2607.16727#S4.I2.i2.p1.1),[Remark 3](https://arxiv.org/html/2607.16727#Thmremark3.p1.6.6)\.
- J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, B\. Ichter, F\. Xia, E\. Chi, Q\. V\. Le, and D\. Zhou \(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 24824–24837\.Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p1.1),[§2](https://arxiv.org/html/2607.16727#S2.p1.1)\.
- S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. Griffiths, Y\. Cao, and K\. Narasimhan \(2023\)Tree of thoughts: deliberate problem solving with large language models\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p2.1),[§2](https://arxiv.org/html/2607.16727#S2.p1.1),[2nd item](https://arxiv.org/html/2607.16727#S4.I2.i2.p1.1)\.
- K\. Yi, J\. Wu, C\. Gan, A\. Torralba, P\. Kohli, and J\. B\. Tenenbaum \(2018\)Neural\-symbolic VQA: disentangling reasoning from vision and language understanding\.InAdvances in Neural Information Processing Systems,Vol\.31\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p2.1)\.
- W\. Yu, Z\. Yao, D\. Luo, J\. Li, X\. Wang, J\. Park, and M\. Bansal \(2023\)MM\-vet: evaluating large multimodal models for integrated capabilities\.arXiv preprint arXiv:2308\.02490\.Cited by:[4th item](https://arxiv.org/html/2607.16727#S4.I1.i4.p1.1)\.
- R\. Zellers, Y\. Bisk, A\. Farhadi, and Y\. Choi \(2019\)From recognition to cognition: visual commonsense reasoning\.InProceedings of the CVPR,pp\. 6720–6731\.Cited by:[Appendix D](https://arxiv.org/html/2607.16727#A4.p2.1),[§1](https://arxiv.org/html/2607.16727#S1.p5.1),[3rd item](https://arxiv.org/html/2607.16727#S4.I1.i3.p1.1)\.
- Z\. Zhang, A\. Zhang, M\. Li, and A\. Smola \(2023a\)Language model cascades: token\-level uncertainty and beyond\.arXiv preprint arXiv:2404\.10136\.Cited by:[§1](https://arxiv.org/html/2607.16727#S1.p1.1)\.
- Z\. Zhang, A\. Zhang, M\. Li, H\. Zhao, G\. Karypis, and A\. Smola \(2023b\)Multimodal chain\-of\-thought reasoning in language models\.arXiv preprint arXiv:2302\.00923\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p1.1)\.
- G\. Zheng, B\. Yang, J\. Tang, H\. Zhou, and S\. Yang \(2023\)DDCoT: duty\-distinct chain\-of\-thought prompting for multimodal reasoning in language models\.Advances in Neural Information Processing Systems36\.Cited by:[§2](https://arxiv.org/html/2607.16727#S2.p1.1),[3rd item](https://arxiv.org/html/2607.16727#S4.I2.i3.p1.1)\.

## Appendix ATheoretical Analysis

We provide formal guarantees for CART’s error\-arresting mechanism\. The central challenges are that \(a\) an anchor beingcorrect\(sound\) does not by itself guarantee that itdetectsan upstream error, and \(b\) detecting an error via an anchor does not guarantee successful recovery\. We address both with explicit assumptions in §[A\.1](https://arxiv.org/html/2607.16727#A1.SS1), prove the main snowball\-rate reduction result in §[A\.2](https://arxiv.org/html/2607.16727#A1.SS2), derive end\-to\-end accuracy and no\-harm guarantees in §[A\.3](https://arxiv.org/html/2607.16727#A1.SS3), relax the independence assumption viaβ\\beta\-mixing in §[A\.4](https://arxiv.org/html/2607.16727#A1.SS4), establish computational complexity in §[A\.5](https://arxiv.org/html/2607.16727#A1.SS5), and discuss tightness and limitations in §[A\.6](https://arxiv.org/html/2607.16727#A1.SS6)\.

### A\.1\.Definitions and Assumptions

We begin by formalizing the reliability properties of the Constraint Propagation Module \(CPM\)\. Recall from §3\.2\.3 that the CPM accepts an anchorccif and only ifpvis​\(c∣I\)≥τvp\_\{\\text\{vis\}\}\(c\\mid I\)\\geq\\tau\_\{v\}andBCP​\(Σ∪\{c\}\)=SAT\\text\{BCP\}\(\\Sigma\\cup\\\{c\\\}\)=\\text\{SAT\}\.

###### Definition 0 \(CPM Verification Reliability\)\.

The CPM is\(δ,α\)\(\\delta,\\alpha\)\-reliableif the following two conditions hold for all anchorsc∈ℒcc\\in\\mathcal\{L\}\_\{c\}and imagesI∈ℐI\\in\\mathcal\{I\}:

- •Soundness\(false acceptance rate\): ℙ​\[CPM accepts​c∣c​is false w\.r\.t\.​I\]≤δ,\\mathbb\{P\}\[\\textit\{CPM accepts \}c\\mid c\\text\{ is false w\.r\.t\.\\ \}I\]\\leq\\delta,
- •Completeness\(false rejection rate\): ℙ​\[CPM rejects​c∣c​is true w\.r\.t\.​I\]≤α\.\\mathbb\{P\}\[\\textit\{CPM rejects \}c\\mid c\\text\{ is true w\.r\.t\.\\ \}I\]\\leq\\alpha\.

###### Definition 0 \(Snowball Event\)\.

Given a reasoning trace𝐫=\(r1,…,rT\)\\mathbf\{r\}=\(r\_\{1\},\\ldots,r\_\{T\}\)with first error at steptt\(i\.e\.,et=1e\_\{t\}=1andet′′=0e\_\{t^\{\\prime\\prime\}\}=0for allt′′<tt^\{\\prime\\prime\}<t\), thesnowball eventisSnow=⋂t′=t\+1T\{et′=1\}\\textup\{Snow\}=\\bigcap\_\{t^\{\\prime\}=t\+1\}^\{T\}\\\{e\_\{t^\{\\prime\}\}=1\\\}\. Thesnowball rateis𝒮=ℙ​\[Snow∣et=1,∀t′′<tet′′=0\]\\mathcal\{S\}=\\mathbb\{P\}\[\\textup\{Snow\}\\mid e\_\{t\}=1,\\;\\forall\_\{t^\{\\prime\\prime\}<t\}\\;e\_\{t^\{\\prime\\prime\}\}=0\]\.

We now state the assumptions required for our analysis\.

###### Assumption 1 \(CPM Soundness\)\.

Every emitted non\-null anchor is verified by a\(δ,α\)\(\\delta,\\alpha\)\-reliable CPM withδ∈\[0,1\)\\delta\\in\[0,1\)andα∈\[0,1\)\\alpha\\in\[0,1\)\.

Justification\.The grounding headgψg\_\{\\psi\}is trained on∼218\{\\sim\}218K instances with balanced positive/negative anchors \(§3\.5\), achieving empirical false acceptance ratesδ≈0\.07\\delta\\approx 0\.07\(GQA/CLEVR\) andδ≈0\.11\\delta\\approx 0\.11\(VCR\)\. The BCP component contributes additional rejection power for logical contradictions, which can only decreaseδ\\delta\. The completeness parameterα\\alphais estimated atα≈0\.05\\alpha\\approx 0\.05\(GQA\) andα≈0\.09\\alpha\\approx 0\.09\(VCR\)\.

###### Assumption 2 \(Conditional Independence of Anchor Verifications\)\.

Conditional on the imageIIand the error state sequence\(e1,…,eT\)\(e\_\{1\},\\ldots,e\_\{T\}\), the CPM verification outcomes\{Vt,j\}\(t,j\)∈𝒜\\\{V\_\{t,j\}\\\}\_\{\(t,j\)\\in\\mathcal\{A\}\}, whereVt,j=𝟙​\[CPM accepts​ct,j\]V\_\{t,j\}=\\mathbb\{1\}\[\\textup\{CPM accepts \}c\_\{t,j\}\], are mutually independent\.

Justification\.This is a simplifying idealization: in practice, all anchors share the visual feature bank𝐕\\mathbf\{V\}and are produced by the same autoregressive model, inducing correlation through shared hidden states\. We relax this assumption in §[A\.4](https://arxiv.org/html/2607.16727#A1.SS4)usingβ\\beta\-mixing coefficients\. Assumption[2](https://arxiv.org/html/2607.16727#Thmassumption2)provides a clean baseline bound and is approximately valid when anchors reference distinct spatial regions and non\-overlapping semantic content, which holds for∼78%\{\\sim\}78\\%of anchor pairs in our GQA traces \(measured by IoU<0\.1<0\.1between grounded regions\)\.

###### Assumption 3 \(Error–Anchor Coupling\)\.

If an error occurs at steptt\(i\.e\.,et=1e\_\{t\}=1\), then each subsequent non\-null anchorct′,jc\_\{t^\{\\prime\},j\}witht′\>tt^\{\\prime\}\>tis rendered false \(with respect to the ground\-truth scene\) with probability at leastγ∈\(0,1\]\\gamma\\in\(0,1\], independently across anchors:

ℙ​\[ct′,j​is false​\|et=1,\(t′,j\)∈𝒜,t′\>​t\]≥γ\.\\mathbb\{P\}\\big\[c\_\{t^\{\\prime\},j\}\\text\{ is false\}\\;\\big\|\\;e\_\{t\}=1,\\;\(t^\{\\prime\},j\)\\in\\mathcal\{A\},\\;t^\{\\prime\}\>t\\big\]\\geq\\gamma\.

Justification\.The coupling rateγ\\gammaquantifies how tightly the constraint languageℒc\\mathcal\{L\}\_\{c\}covers the error\-prone reasoning steps\. For compositional visual QA \(GQA, CLEVR\), anchors are directly derived from program steps and thus tightly coupled \(γ≈0\.72\\gamma\\approx 0\.72–0\.810\.81\)\. For free\-form reasoning \(VCR\),γ\\gammais lower \(≈0\.58\{\\approx\}0\.58\)\. In the extreme case where anchors are completely tangential to the error source \(γ=0\\gamma=0\), CART provides no benefit, and the bound in Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)reduces to𝒮0\\mathcal\{S\}\_\{0\}\.

###### Assumption 4 \(Backtrack Recovery\)\.

When the CPM detects a violation and the backtrack controller is triggered, the conditional probability that the error still snowballs \(due to retry budget exhaustion, re\-introduction of the same error, or a novel cascading error\) is bounded byεrec∈\[0,1\)\\varepsilon\_\{\\textup\{rec\}\}\\in\[0,1\):

ℙ​\[Snow\|error caught by some anchor\]≤εrec\.\\mathbb\{P\}\\big\[\\textup\{Snow\}\\;\\big\|\\;\\text\{error caught by some anchor\}\\big\]\\leq\\varepsilon\_\{\\textup\{rec\}\}\.

Justification\.This assumption explicitly acknowledges that detection does not guarantee recovery\. The parameterεrec\\varepsilon\_\{\\text\{rec\}\}encapsulates three failure modes: \(i\) retry budgetBBexhaustion, \(ii\) re\-introduction of a semantically equivalent error, and \(iii\) introduction of a novel cascading error\. Empirically,εrec∈\[0\.08,0\.19\]\\varepsilon\_\{\\text\{rec\}\}\\in\[0\.08,0\.19\]across our benchmarks\. WithB=3B=3retries, each producing an independent alternative continuation \(encouraged by the<RETRY\>token and diverse training in §3\.5\), the recovery failure probability decays geometrically: if each retry independently succeeds with probabilitypfixp\_\{\\text\{fix\}\}, thenεrec≤\(1−pfix\)B\\varepsilon\_\{\\text\{rec\}\}\\leq\(1\-p\_\{\\text\{fix\}\}\)^\{B\}, givingεrec≤0\.125\\varepsilon\_\{\\text\{rec\}\}\\leq 0\.125forpfix=0\.5p\_\{\\text\{fix\}\}=0\.5andB=3B=3\.

###### Assumption 5 \(Error\-Free Trace Integrity\)\.

If no reasoning error occurs \(et=0e\_\{t\}=0for alltt\), then the final answer is correct:ℙ​\[a=a∗∣∀tet=0\]=1\\mathbb\{P\}\[a=a^\{\*\}\\mid\\forall\_\{t\}\\;e\_\{t\}=0\]=1\. Conversely, if snowballing occurs, the answer is incorrect:ℙ​\[a≠a∗∣Snow\]=1\\mathbb\{P\}\[a\\neq a^\{\*\}\\mid\\textup\{Snow\}\]=1\.

Justification\.The first condition holds by definition when the CoT trace faithfully represents the reasoning path and the answer extractorfansf\_\{\\text\{ans\}\}is deterministic\. The second is a reasonable worst\-case assumption: when all steps following an error are themselves erroneous, the final answer is almost surely corrupted\. This is empirically validated: on our diagnostic subset,99\.2%99\.2\\%of snowball instances yield an incorrect answer\.

###### Assumption 6 \(Pass\-Through Snowball Rate\)\.

Let𝒮0PT\\mathcal\{S\}\_\{0\}^\{\\textup\{PT\}\}denote the snowball rate of the CART\-fine\-tuned modelℳθ\\mathcal\{M\}\_\{\\theta\}when the CPM does not intervene \(i\.e\., no backtracking is triggered, regardless of anchor verification outcomes\)\. We assume𝒮0PT≤𝒮0\\mathcal\{S\}\_\{0\}^\{\\textup\{PT\}\}\\leq\\mathcal\{S\}\_\{0\}, where𝒮0\\mathcal\{S\}\_\{0\}is the snowball rate of the pre\-fine\-tuning base model\.

Justification\.This assumption is needed because Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)’s Case 1 \(error not caught\) involves the CART\-fine\-tuned model continuing without CPM correction, not the original base model\. We expect𝒮0PT≤𝒮0\\mathcal\{S\}\_\{0\}^\{\\text\{PT\}\}\\leq\\mathcal\{S\}\_\{0\}because the constraint\-aware training provides auxiliary supervision that improves reasoning quality\. This is empirically validated: measuring the snowball rate of the CART model with CPM disabled yields𝒮0PT=0\.61\\mathcal\{S\}\_\{0\}^\{\\text\{PT\}\}=0\.61on GQA \(vs\.𝒮0=0\.68\\mathcal\{S\}\_\{0\}=0\.68for the base model\), confirming the bound holds with margin\.

### A\.2\.Snowball Rate Reduction

We first establish a useful per\-anchor detection probability\.

###### Lemma 3 \(Per\-Anchor Error Detection Probability\)\.

Under Assumptions[1](https://arxiv.org/html/2607.16727#Thmassumption1)and[3](https://arxiv.org/html/2607.16727#Thmassumption3), for any non\-null anchorct′,jc\_\{t^\{\\prime\},j\}emitted after the first error at steptt\(i\.e\.,\(t′,j\)∈𝒜\(t^\{\\prime\},j\)\\in\\mathcal\{A\}witht′\>tt^\{\\prime\}\>t\), the probability thatct′,jc\_\{t^\{\\prime\},j\}is both rendered false by the error and correctly rejected by the CPM is at leastγ​\(1−δ\)\\gamma\(1\-\\delta\):

ℙ​\[CPM rejects​ct′,j​\|et=1,t′\>​t\]≥γ​\(1−δ\)\.\\mathbb\{P\}\\big\[\\textup\{CPM rejects \}c\_\{t^\{\\prime\},j\}\\;\\big\|\\;e\_\{t\}=1,\\;t^\{\\prime\}\>t\\big\]\\geq\\gamma\(1\-\\delta\)\.

###### Proof\.

Decompose the rejection event by conditioning on whether the anchor is false:

\(2\)ℙ​\[CPM rejects​ct′,j∣et=1\]\\displaystyle\\mathbb\{P\}\[\\text\{CPM rejects \}c\_\{t^\{\\prime\},j\}\\mid e\_\{t\}=1\]≥ℙ​\[CPM rejects​ct′,j∣ct′,j​false,et=1\]\\displaystyle\\geq\\mathbb\{P\}\[\\text\{CPM rejects \}c\_\{t^\{\\prime\},j\}\\mid c\_\{t^\{\\prime\},j\}\\text\{ false\},\\,e\_\{t\}=1\]⋅ℙ​\[ct′,j​false∣et=1\]\\displaystyle\\cdot\\mathbb\{P\}\[c\_\{t^\{\\prime\},j\}\\text\{ false\}\\mid e\_\{t\}=1\]by the law of total probability \(dropping the non\-negative termℙ​\[reject∣ct′,j​true\]⋅ℙ​\[ct′,j​true\]≥0\\mathbb\{P\}\[\\text\{reject\}\\mid c\_\{t^\{\\prime\},j\}\\text\{ true\}\]\\cdot\\mathbb\{P\}\[c\_\{t^\{\\prime\},j\}\\text\{ true\}\]\\geq 0\)\.

By Assumption[3](https://arxiv.org/html/2607.16727#Thmassumption3),ℙ​\[ct′,j​false∣et=1\]≥γ\\mathbb\{P\}\[c\_\{t^\{\\prime\},j\}\\text\{ false\}\\mid e\_\{t\}=1\]\\geq\\gamma\. By the contrapositive of the soundness condition in Assumption[1](https://arxiv.org/html/2607.16727#Thmassumption1)\(Definition[1](https://arxiv.org/html/2607.16727#A1.Thmtheorem1)\):ℙ​\[CPM rejects​c∣c​false\]=1−ℙ​\[CPM accepts​c∣c​false\]≥1−δ\\mathbb\{P\}\[\\text\{CPM rejects \}c\\mid c\\text\{ false\}\]=1\-\\mathbb\{P\}\[\\text\{CPM accepts \}c\\mid c\\text\{ false\}\]\\geq 1\-\\delta\. Substituting:

ℙ​\[CPM rejects​ct′,j∣et=1\]≥\(1−δ\)⋅γ=γ​\(1−δ\)\.∎\\mathbb\{P\}\[\\text\{CPM rejects \}c\_\{t^\{\\prime\},j\}\\mid e\_\{t\}=1\]\\geq\(1\-\\delta\)\\cdot\\gamma=\\gamma\(1\-\\delta\)\.\\qed

We now state and prove the main result\.

###### Theorem 4 \(Snowball Rate Reduction\)\.

Let𝒮0\\mathcal\{S\}\_\{0\}be the snowball rate of the base model without CART \(or, more precisely, the pass\-through snowball rate𝒮0PT≤𝒮0\\mathcal\{S\}\_\{0\}^\{\\textup\{PT\}\}\\leq\\mathcal\{S\}\_\{0\}per Assumption[6](https://arxiv.org/html/2607.16727#Thmassumption6)\), and letK=\|\{\(t′,j\)∈𝒜:t′\>t\}\|K=\|\\\{\(t^\{\\prime\},j\)\\in\\mathcal\{A\}:t^\{\\prime\}\>t\\\}\|denote the number of non\-null anchors emitted after the first error at steptt\. Defineq≜1−γ​\(1−δ\)q\\triangleq 1\-\\gamma\(1\-\\delta\)\. Under Assumptions[1](https://arxiv.org/html/2607.16727#Thmassumption1)–[6](https://arxiv.org/html/2607.16727#Thmassumption6), the snowball rate of CART satisfies:

𝒮CART≤𝒮0⋅qK\+εrec⋅\(1−qK\)\.\\mathcal\{S\}\_\{\\textup\{CART\}\}\\leq\\mathcal\{S\}\_\{0\}\\cdot q^\{K\}\+\\varepsilon\_\{\\textup\{rec\}\}\\cdot\(1\-q^\{K\}\)\.Equivalently,

𝒮CART≤εrec\+\(𝒮0−εrec\)⋅qK\.\\mathcal\{S\}\_\{\\textup\{CART\}\}\\leq\\varepsilon\_\{\\textup\{rec\}\}\+\(\\mathcal\{S\}\_\{0\}\-\\varepsilon\_\{\\textup\{rec\}\}\)\\cdot q^\{K\}\.

###### Proof\.

We condition on the event that the first error occurs at steptt\. Define two complementary events over theKKpost\-error non\-null anchors:

\(3\)ℰcatch\\displaystyle\\mathcal\{E\}\_\{\\text\{catch\}\}=\{CPM rejects at least one anchor among​\{ct′,j:\(t′,j\)∈𝒜,t′\>t\}\},\\displaystyle=\\big\\\{\\text\{CPM rejects at least one anchor among \}\\\{c\_\{t^\{\\prime\},j\}:\(t^\{\\prime\},j\)\\in\\mathcal\{A\},\\;t^\{\\prime\}\>t\\\}\\big\\\},\(4\)ℰmiss\\displaystyle\\mathcal\{E\}\_\{\\text\{miss\}\}=ℰcatch¯=\{CPM accepts all​K​post\-error anchors\}\.\\displaystyle=\\overline\{\\mathcal\{E\}\_\{\\text\{catch\}\}\}=\\big\\\{\\text\{CPM accepts all \}K\\text\{ post\-error anchors\}\\big\\\}\.
Step 1: Boundℙ​\[ℰmiss\]\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{miss\}\}\]\.For each post\-error anchori∈\{1,…,K\}i\\in\\\{1,\\ldots,K\\\}, defineMi=\{anchor​i​does not reject\}M\_\{i\}=\\\{\\text\{anchor \}i\\text\{ does not reject\}\\\}\. Thenℰmiss=⋂i=1KMi\\mathcal\{E\}\_\{\\text\{miss\}\}=\\bigcap\_\{i=1\}^\{K\}M\_\{i\}\.

By Lemma[3](https://arxiv.org/html/2607.16727#A1.Thmtheorem3),ℙ​\[Mi∣et=1\]≤1−γ​\(1−δ\)=q\\mathbb\{P\}\[M\_\{i\}\\mid e\_\{t\}=1\]\\leq 1\-\\gamma\(1\-\\delta\)=q\. By Assumption[2](https://arxiv.org/html/2607.16727#Thmassumption2)\(conditional independence\), the events\{Mi\}i=1K\\\{M\_\{i\}\\\}\_\{i=1\}^\{K\}are conditionally independent givenIIand\(e1,…,eT\)\(e\_\{1\},\\ldots,e\_\{T\}\)\. Therefore:

\(5\)ℙ​\[ℰmiss∣et=1\]=∏i=1Kℙ​\[Mi∣et=1\]≤qK\.\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{miss\}\}\\mid e\_\{t\}=1\]=\\prod\_\{i=1\}^\{K\}\\mathbb\{P\}\[M\_\{i\}\\mid e\_\{t\}=1\]\\leq q^\{K\}\.
Step 2: Bound snowball probability conditional on each case\.

Case 1 \(ℰmiss\\mathcal\{E\}\_\{\\text\{miss\}\}\):When no anchor detects the error, the backtrack controller is never triggered\. By Assumption[6](https://arxiv.org/html/2607.16727#Thmassumption6), the pass\-through snowball rate satisfies𝒮0PT≤𝒮0\\mathcal\{S\}\_\{0\}^\{\\text\{PT\}\}\\leq\\mathcal\{S\}\_\{0\}:

\(6\)ℙ​\[Snow∣ℰmiss,et=1\]≤𝒮0PT≤𝒮0\.\\mathbb\{P\}\[\\text\{Snow\}\\mid\\mathcal\{E\}\_\{\\text\{miss\}\},\\;e\_\{t\}=1\]\\leq\\mathcal\{S\}\_\{0\}^\{\\text\{PT\}\}\\leq\\mathcal\{S\}\_\{0\}\.
Case 2 \(ℰcatch\\mathcal\{E\}\_\{\\text\{catch\}\}\):When at least one anchor detects the error, the backtrack controller is activated\. By Assumption[4](https://arxiv.org/html/2607.16727#Thmassumption4):

\(7\)ℙ​\[Snow∣ℰcatch,et=1\]≤εrec\.\\mathbb\{P\}\[\\text\{Snow\}\\mid\\mathcal\{E\}\_\{\\text\{catch\}\},\\;e\_\{t\}=1\]\\leq\\varepsilon\_\{\\text\{rec\}\}\.
Step 3: Combine via the law of total probability\.

𝒮CART\\displaystyle\\mathcal\{S\}\_\{\\text\{CART\}\}=ℙ​\[Snow∣et=1\]\\displaystyle=\\mathbb\{P\}\[\\text\{Snow\}\\mid e\_\{t\}=1\]=ℙ​\[Snow∣ℰmiss,et=1\]⋅ℙ​\[ℰmiss∣et=1\]\\displaystyle=\\mathbb\{P\}\[\\text\{Snow\}\\mid\\mathcal\{E\}\_\{\\text\{miss\}\},\\;e\_\{t\}=1\]\\cdot\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{miss\}\}\\mid e\_\{t\}=1\]\+ℙ​\[Snow∣ℰcatch,et=1\]⋅ℙ​\[ℰcatch∣et=1\]\\displaystyle\\quad\+\\mathbb\{P\}\[\\text\{Snow\}\\mid\\mathcal\{E\}\_\{\\text\{catch\}\},\\;e\_\{t\}=1\]\\cdot\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{catch\}\}\\mid e\_\{t\}=1\]\(8\)≤𝒮0⋅qK\+εrec⋅\(1−qK\),\\displaystyle\\leq\\mathcal\{S\}\_\{0\}\\cdot q^\{K\}\+\\varepsilon\_\{\\text\{rec\}\}\\cdot\(1\-q^\{K\}\),where we used \([5](https://arxiv.org/html/2607.16727#A1.E5)\), \([6](https://arxiv.org/html/2607.16727#A1.E6)\), \([7](https://arxiv.org/html/2607.16727#A1.E7)\), andℙ​\[ℰcatch∣et=1\]=1−ℙ​\[ℰmiss∣et=1\]\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{catch\}\}\\mid e\_\{t\}=1\]=1\-\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{miss\}\}\\mid e\_\{t\}=1\]\.∎∎

###### Corollary 0 \(Exponential Convergence\)\.

Forγ\>0\\gamma\>0,δ<1\\delta<1, andεrec<𝒮0\\varepsilon\_\{\\textup\{rec\}\}<\\mathcal\{S\}\_\{0\}:

limK→∞𝒮CART=εrec\.\\lim\_\{K\\to\\infty\}\\mathcal\{S\}\_\{\\textup\{CART\}\}=\\varepsilon\_\{\\textup\{rec\}\}\.The convergence is exponentially fast with rate−log⁡q=−log⁡\(1−γ​\(1−δ\)\)\-\\log q=\-\\log\(1\-\\gamma\(1\-\\delta\)\)\. Specifically,𝒮CART−εrec≤\(𝒮0−εrec\)⋅e−γ​\(1−δ\)​K\\mathcal\{S\}\_\{\\textup\{CART\}\}\-\\varepsilon\_\{\\textup\{rec\}\}\\leq\(\\mathcal\{S\}\_\{0\}\-\\varepsilon\_\{\\textup\{rec\}\}\)\\cdot e^\{\-\\gamma\(1\-\\delta\)K\}for allK≥1K\\geq 1\(usinglog⁡\(1−x\)≤−x\\log\(1\-x\)\\leq\-xforx∈\[0,1\)x\\in\[0,1\)\)\.

###### Corollary 0 \(Non\-Vacuousness Condition\)\.

The bound in Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)is strictly better than the trivial bound𝒮0\\mathcal\{S\}\_\{0\}\(i\.e\.,𝒮CART<𝒮0\\mathcal\{S\}\_\{\\textup\{CART\}\}<\\mathcal\{S\}\_\{0\}\) if and only if:

εrec<𝒮0andK≥1andγ​\(1−δ\)\>0\.\\varepsilon\_\{\\textup\{rec\}\}<\\mathcal\{S\}\_\{0\}\\quad\\text\{and\}\\quad K\\geq 1\\quad\\text\{and\}\\quad\\gamma\(1\-\\delta\)\>0\.The improvement over the base model is𝒮0−𝒮CART≥\(𝒮0−εrec\)​\(1−qK\)\\mathcal\{S\}\_\{0\}\-\\mathcal\{S\}\_\{\\textup\{CART\}\}\\geq\(\\mathcal\{S\}\_\{0\}\-\\varepsilon\_\{\\textup\{rec\}\}\)\(1\-q^\{K\}\)\.

###### Corollary 0 \(Concrete Numerical Bound\)\.

Using empirical parameter estimates from GQA:γ=0\.72\\gamma=0\.72,δ=0\.07\\delta=0\.07,εrec=0\.12\\varepsilon\_\{\\textup\{rec\}\}=0\.12,𝒮0=0\.68\\mathcal\{S\}\_\{0\}=0\.68, andK=3K=3post\-error anchors:

q=1−0\.72×0\.93=0\.3304,q3=0\.0361,q=1\-0\.72\\times 0\.93=0\.3304,\\quad q^\{3\}=0\.0361,𝒮CART≤0\.68×0\.0361\+0\.12×0\.9639=0\.0245\+0\.1157=0\.140\.\\mathcal\{S\}\_\{\\textup\{CART\}\}\\leq 0\.68\\times 0\.0361\+0\.12\\times 0\.9639=0\.0245\+0\.1157=0\.140\.This represents a79\.4%\\mathbf\{79\.4\\%\}reduction from𝒮0=0\.68\\mathcal\{S\}\_\{0\}=0\.68\. We caution that the agreement with the empirical measurement𝒮CART=0\.14\\mathcal\{S\}\_\{\\textup\{CART\}\}=0\.14is*not*out\-of\-sample validation: the bound is evaluated with parameters \(γ,δ,εrec,𝒮0\\gamma,\\delta,\\varepsilon\_\{\\textup\{rec\}\},\\mathcal\{S\}\_\{0\}\) estimated from the same diagnostic subset \(Appendix[C](https://arxiv.org/html/2607.16727#A3)\)\. It should therefore be read as an internal\-consistency check on the analysis rather than an independent confirmation of the empirical result\.

###### Corollary 0 \(Minimum Anchors for Target Snowball Rate\)\.

To achieve a target snowball rate𝒮∗∈\(εrec,𝒮0\)\\mathcal\{S\}^\{\*\}\\in\(\\varepsilon\_\{\\textup\{rec\}\},\\mathcal\{S\}\_\{0\}\), the minimum required number of post\-error non\-null anchors is:

K∗=⌈log⁡\(𝒮∗−εrec𝒮0−εrec\)log⁡q⌉\.K^\{\*\}=\\left\\lceil\\frac\{\\log\\\!\\left\(\\frac\{\\mathcal\{S\}^\{\*\}\-\\varepsilon\_\{\\textup\{rec\}\}\}\{\\mathcal\{S\}\_\{0\}\-\\varepsilon\_\{\\textup\{rec\}\}\}\\right\)\}\{\\log q\}\\right\\rceil\.For the GQA parameters and target𝒮∗=0\.20\\mathcal\{S\}^\{\*\}=0\.20:K∗=⌈log⁡\(0\.08/0\.56\)/log⁡\(0\.3304\)⌉=⌈1\.78⌉=2K^\{\*\}=\\lceil\\log\(0\.08/0\.56\)/\\log\(0\.3304\)\\rceil=\\lceil 1\.78\\rceil=2\.

### A\.3\.End\-to\-End Accuracy and No\-Harm Guarantees

We translate the snowball\-rate reduction into accuracy bounds\. Letp1=ℙ\[∃t:et=1\]p\_\{1\}=\\mathbb\{P\}\[\\exists\\,t:e\_\{t\}=1\]denote the probability that at least one reasoning error occurs in the initial \(pre\-backtrack\) generation attempt\.

###### Theorem 9 \(Accuracy Improvement\)\.

Letη=ℙ\[a=a∗∣∃t:et=1,Snow¯\]\\eta=\\mathbb\{P\}\[a=a^\{\*\}\\mid\\exists\\,t:e\_\{t\}=1,\\;\\overline\{\\textup\{Snow\}\}\]be the conditional accuracy when an error occurs but does not snowball\. Under Assumptions[1](https://arxiv.org/html/2607.16727#Thmassumption1)–[6](https://arxiv.org/html/2607.16727#Thmassumption6), the accuracy of CART satisfies:

AccCART≥1−p1​\[𝒮CART\+\(1−𝒮CART\)​\(1−ηCART\)\]−\(1−p1\)​ξFA,\\textup\{Acc\}\_\{\\textup\{CART\}\}\\geq 1\-p\_\{1\}\\Big\[\\mathcal\{S\}\_\{\\textup\{CART\}\}\+\(1\-\\mathcal\{S\}\_\{\\textup\{CART\}\}\)\(1\-\\eta\_\{\\textup\{CART\}\}\)\\Big\]\-\(1\-p\_\{1\}\)\\xi\_\{\\textup\{FA\}\},whereηCART\\eta\_\{\\textup\{CART\}\}is the non\-snowball recovery accuracy under CART, andξFA≤1−\(1−α\)K0\\xi\_\{\\textup\{FA\}\}\\leq 1\-\(1\-\\alpha\)^\{K\_\{0\}\}bounds the probability that a false alarm on an error\-free initial trace \(withK0K\_\{0\}non\-null anchors\) leads to an incorrect answer after unnecessary backtracking\.

Moreover, ifηCART≥η0\\eta\_\{\\textup\{CART\}\}\\geq\\eta\_\{0\}andξFA=0\\xi\_\{\\textup\{FA\}\}=0, the accuracy improvement over the base model satisfies:

AccCART−Acc0≥p1⋅η0⋅\(𝒮0−𝒮CART\)\.\\textup\{Acc\}\_\{\\textup\{CART\}\}\-\\textup\{Acc\}\_\{0\}\\geq p\_\{1\}\\cdot\\eta\_\{0\}\\cdot\(\\mathcal\{S\}\_\{0\}\-\\mathcal\{S\}\_\{\\textup\{CART\}\}\)\.

###### Proof\.

WriteE=\{∃t:et=1\}E=\\\{\\exists\\,t:e\_\{t\}=1\\\}andE¯=\{∀t:et=0\}\\bar\{E\}=\\\{\\forall\\,t:\\,e\_\{t\}=0\\\}\. Decompose:

\(9\)AccCART\\displaystyle\\text\{Acc\}\_\{\\text\{CART\}\}=ℙ​\[a=a∗∣E¯\]⋅\(1−p1\)\+ℙ​\[a=a∗∣E\]⋅p1\.\\displaystyle=\\mathbb\{P\}\[a=a^\{\*\}\\mid\\bar\{E\}\]\\cdot\(1\-p\_\{1\}\)\+\\mathbb\{P\}\[a=a^\{\*\}\\mid E\]\\cdot p\_\{1\}\.
Error\-free case \(E¯\\bar\{E\}\)\.Each of theK0K\_\{0\}true anchors independently survives without false rejection with probability≥1−α\\geq 1\-\\alpha\(Assumption[1](https://arxiv.org/html/2607.16727#Thmassumption1)\)\. When no false alarm occurs, the trace completes correctly \(Assumption[5](https://arxiv.org/html/2607.16727#Thmassumption5)\):

ℙ​\[a=a∗∣E¯\]≥\(1−α\)K0=1−ξFA′\.\\mathbb\{P\}\[a=a^\{\*\}\\mid\\bar\{E\}\]\\geq\(1\-\\alpha\)^\{K\_\{0\}\}=1\-\\xi\_\{\\text\{FA\}\}^\{\\prime\}\.
Error case \(EE\)\.Further decompose on the snowball event:

ℙ​\[a=a∗∣E\]=ℙ​\[a=a∗∣E,Snow\]⏟=0​by Asm\.[5](https://arxiv.org/html/2607.16727#Thmassumption5)⋅𝒮CART\+ηCART⋅\(1−𝒮CART\)\.\\mathbb\{P\}\[a=a^\{\*\}\\mid E\]=\\underbrace\{\\mathbb\{P\}\[a=a^\{\*\}\\mid E,\\text\{Snow\}\]\}\_\{=0\\text\{ by Asm\.~\\ref\{ass:integrity\}\}\}\\cdot\\mathcal\{S\}\_\{\\text\{CART\}\}\+\\eta\_\{\\text\{CART\}\}\\cdot\(1\-\\mathcal\{S\}\_\{\\text\{CART\}\}\)\.
Combining and settingξFA=0\\xi\_\{\\text\{FA\}\}=0,ηCART≥η0\\eta\_\{\\text\{CART\}\}\\geq\\eta\_\{0\}:

\(10\)AccCART−Acc0\\displaystyle\\text\{Acc\}\_\{\\text\{CART\}\}\-\\text\{Acc\}\_\{0\}≥p1​\[η0​\(1−𝒮CART\)−η0​\(1−𝒮0\)\]\\displaystyle\\geq p\_\{1\}\[\\eta\_\{0\}\(1\-\\mathcal\{S\}\_\{\\text\{CART\}\}\)\-\\eta\_\{0\}\(1\-\\mathcal\{S\}\_\{0\}\)\]=p1​η0​\(𝒮0−𝒮CART\)\.\\displaystyle=p\_\{1\}\\eta\_\{0\}\(\\mathcal\{S\}\_\{0\}\-\\mathcal\{S\}\_\{\\text\{CART\}\}\)\.∎

Practical interpretation\.For GQA withp1≈0\.42p\_\{1\}\\approx 0\.42,η0≈0\.55\\eta\_\{0\}\\approx 0\.55,𝒮0=0\.68\\mathcal\{S\}\_\{0\}=0\.68, and𝒮CART≤0\.14\\mathcal\{S\}\_\{\\text\{CART\}\}\\leq 0\.14:AccCART−Acc0≥0\.42×0\.55×0\.54=0\.125\\text\{Acc\}\_\{\\text\{CART\}\}\-\\text\{Acc\}\_\{0\}\\geq 0\.42\\times 0\.55\\times 0\.54=0\.125, i\.e\., at least12\.512\.5percentage points of accuracy improvement from snowball reduction alone\. The observed improvement is\+14\.2%\+14\.2\\%, suggesting that CART additionally improvesη\\etaor reducesp1p\_\{1\}through its constraint\-guided training\.

We consolidate the false\-alarm analysis into a single no\-harm guarantee\.

###### Theorem 10 \(No\-Harm Guarantee\)\.

Under Assumptions[1](https://arxiv.org/html/2607.16727#Thmassumption1)–[6](https://arxiv.org/html/2607.16727#Thmassumption6), the accuracy of CART satisfies:

AccCART≥Acc0−εharm,\\textup\{Acc\}\_\{\\textup\{CART\}\}\\geq\\textup\{Acc\}\_\{0\}\-\\varepsilon\_\{\\textup\{harm\}\},where the harm penalty is:

εharm=\(1−p1\)⋅ξFA⋅\(1−rFA\),\\varepsilon\_\{\\textup\{harm\}\}=\(1\-p\_\{1\}\)\\cdot\\xi\_\{\\textup\{FA\}\}\\cdot\(1\-r\_\{\\textup\{FA\}\}\),ξFA≤K0​α\\xi\_\{\\textup\{FA\}\}\\leq K\_\{0\}\\alphais the false\-alarm probability on error\-free traces, andrFA∈\[0,1\]r\_\{\\textup\{FA\}\}\\in\[0,1\]is the probability that a false\-alarm\-triggered backtrack recovers a correct answer\.

- •IfrFA=1r\_\{\\textup\{FA\}\}=1\(false alarms are always harmless\):εharm=0\\varepsilon\_\{\\textup\{harm\}\}=0andAccCART≥Acc0\\textup\{Acc\}\_\{\\textup\{CART\}\}\\geq\\textup\{Acc\}\_\{0\}\.
- •With empirical estimates \(K0=3\.1K\_\{0\}=3\.1,α=0\.05\\alpha=0\.05,rFA=0\.93r\_\{\\textup\{FA\}\}=0\.93\):εharm≤0\.58×0\.155×0\.07=0\.006\\varepsilon\_\{\\textup\{harm\}\}\\leq 0\.58\\times 0\.155\\times 0\.07=0\.006\.

Interpretation\.Theorem[10](https://arxiv.org/html/2607.16727#A1.Thmtheorem10)guarantees that CART’s accuracy is withinεharm≤0\.006\\varepsilon\_\{\\text\{harm\}\}\\leq 0\.006of the base model in the worst case, and is strictly better whenever the snowball reduction benefit exceeds this negligible false\-alarm cost\. This addresses the practical concern that constraint\-based checking might degrade performance on easy instances\.

### A\.4\.Analysis Under Dependent Anchors

Assumption[2](https://arxiv.org/html/2607.16727#Thmassumption2)is an idealization\. We relax it usingβ\\beta\-mixing\.

###### Definition 0 \(β\\beta\-Mixing Coefficient\)\.

For the sequence of CPM verification outcomes\{Vti,ji\}i=1K\\\{V\_\{t\_\{i\},j\_\{i\}\}\\\}\_\{i=1\}^\{K\}\(ordered by trace position\), theβ\\beta\-mixing coefficient at lagℓ≥1\\ell\\geq 1is:

β​\(ℓ\)=sup1≤i≤K−ℓsupA∈σ​\(V≤i\),B∈σ​\(V≥i\+ℓ\)\|ℙ​\[A∩B\]−ℙ​\[A\]​ℙ​\[B\]\|\.\\beta\(\\ell\)=\\sup\_\{1\\leq i\\leq K\-\\ell\}\\;\\sup\_\{A\\in\\sigma\(V\_\{\\leq i\}\),\\;B\\in\\sigma\(V\_\{\\geq i\+\\ell\}\)\}\|\\mathbb\{P\}\[A\\cap B\]\-\\mathbb\{P\}\[A\]\\mathbb\{P\}\[B\]\|\.

###### Theorem 12 \(Snowball Rate Underβ\\beta\-Mixing Dependence\)\.

Letβ¯=supℓ≥1β​\(ℓ\)\\bar\{\\beta\}=\\sup\_\{\\ell\\geq 1\}\\beta\(\\ell\)be the supremumβ\\beta\-mixing coefficient\. Under Assumptions[1](https://arxiv.org/html/2607.16727#Thmassumption1),[3](https://arxiv.org/html/2607.16727#Thmassumption3),[4](https://arxiv.org/html/2607.16727#Thmassumption4), and[6](https://arxiv.org/html/2607.16727#Thmassumption6)\(replacing Assumption[2](https://arxiv.org/html/2607.16727#Thmassumption2)withβ\\beta\-mixing\), the snowball rate satisfies:

𝒮CART≤εrec\+\(𝒮0−εrec\)⋅\[qK\+\(K−1\)​β¯\],\\mathcal\{S\}\_\{\\textup\{CART\}\}\\leq\\varepsilon\_\{\\textup\{rec\}\}\+\(\\mathcal\{S\}\_\{0\}\-\\varepsilon\_\{\\textup\{rec\}\}\)\\cdot\\big\[q^\{K\}\+\(K\-1\)\\bar\{\\beta\}\\big\],whereq=1−γ​\(1−δ\)q=1\-\\gamma\(1\-\\delta\)\. The bound is non\-vacuous \(strictly less than𝒮0\\mathcal\{S\}\_\{0\}\) provided\(K−1\)​β¯<1−qK\(K\-1\)\\bar\{\\beta\}<1\-q^\{K\}\.

###### Proof\.

We boundℙ​\[ℰmiss\]\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{miss\}\}\]under dependence using Berbee’s coupling inequality\.

Step 1: Coupling construction\.For the miss eventsM1,…,MKM\_\{1\},\\ldots,M\_\{K\}, construct an independent sequenceM1′,…,MK′M\_\{1\}^\{\\prime\},\\ldots,M\_\{K\}^\{\\prime\}such thatMi′∼MiM\_\{i\}^\{\\prime\}\\sim M\_\{i\}marginally andℙ​\[Mi≠Mi′\]≤β¯\\mathbb\{P\}\[M\_\{i\}\\neq M\_\{i\}^\{\\prime\}\]\\leq\\bar\{\\beta\}fori≥2i\\geq 2\(Berbee’s coupling lemma\)\.

Step 2: Relate miss probabilities\.Using\{⋂i=1KMi\}⊆\{⋂i=1KMi′\}∪⋃i=2K\{Mi≠Mi′\}\\\{\\bigcap\_\{i=1\}^\{K\}M\_\{i\}\\\}\\subseteq\\\{\\bigcap\_\{i=1\}^\{K\}M\_\{i\}^\{\\prime\}\\\}\\cup\\bigcup\_\{i=2\}^\{K\}\\\{M\_\{i\}\\neq M\_\{i\}^\{\\prime\}\\\}and the union bound:

ℙ​\[⋂i=1KMi\]\\displaystyle\\mathbb\{P\}\\left\[\\bigcap\_\{i=1\}^\{K\}M\_\{i\}\\right\]≤ℙ​\[⋂i=1KMi′\]\+∑i=2Kℙ​\[Mi≠Mi′\]\\displaystyle\\leq\\mathbb\{P\}\\left\[\\bigcap\_\{i=1\}^\{K\}M\_\{i\}^\{\\prime\}\\right\]\+\\sum\_\{i=2\}^\{K\}\\mathbb\{P\}\[M\_\{i\}\\neq M\_\{i\}^\{\\prime\}\]≤∏i=1Kℙ​\[Mi′\]\+\(K−1\)​β¯\(independence of​Mi′\)\\displaystyle\\leq\\prod\_\{i=1\}^\{K\}\\mathbb\{P\}\[M\_\{i\}^\{\\prime\}\]\+\(K\-1\)\\bar\{\\beta\}\\quad\(\\text\{independence of \}M\_\{i\}^\{\\prime\}\)=∏i=1Kℙ​\[Mi\]\+\(K−1\)​β¯\(marginal preservation\)\\displaystyle=\\prod\_\{i=1\}^\{K\}\\mathbb\{P\}\[M\_\{i\}\]\+\(K\-1\)\\bar\{\\beta\}\\quad\(\\text\{marginal preservation\}\)≤qK\+\(K−1\)​β¯\.\\displaystyle\\leq q^\{K\}\+\(K\-1\)\\bar\{\\beta\}\.
Step 3: Apply total\-probability argument\.From the proof of Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4):

𝒮CART=εrec\+\(𝒮0−εrec\)⋅ℙ​\[ℰmiss∣et=1\]\.\\mathcal\{S\}\_\{\\text\{CART\}\}=\\varepsilon\_\{\\text\{rec\}\}\+\(\\mathcal\{S\}\_\{0\}\-\\varepsilon\_\{\\text\{rec\}\}\)\\cdot\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{miss\}\}\\mid e\_\{t\}=1\]\.Since𝒮0≥εrec\\mathcal\{S\}\_\{0\}\\geq\\varepsilon\_\{\\text\{rec\}\}in the non\-trivial regime, this is monotonically increasing inℙ​\[ℰmiss\]\\mathbb\{P\}\[\\mathcal\{E\}\_\{\\text\{miss\}\}\]\. Substituting:

𝒮CART≤εrec\+\(𝒮0−εrec\)​\[qK\+\(K−1\)​β¯\]\.\\mathcal\{S\}\_\{\\text\{CART\}\}\\leq\\varepsilon\_\{\\text\{rec\}\}\+\(\\mathcal\{S\}\_\{0\}\-\\varepsilon\_\{\\text\{rec\}\}\)\\big\[q^\{K\}\+\(K\-1\)\\bar\{\\beta\}\\big\]\.
Non\-vacuousness:𝒮CART<𝒮0\\mathcal\{S\}\_\{\\text\{CART\}\}<\\mathcal\{S\}\_\{0\}iffqK\+\(K−1\)​β¯<1q^\{K\}\+\(K\-1\)\\bar\{\\beta\}<1\. ∎

Empirical mixing estimation\.We estimateβ¯\\bar\{\\beta\}on the GQA diagnostic subset \(1,000 instances\)\. Maximum absolute Pearson correlation between consecutive anchor verification outcomes yieldsr^max≈0\.08\\hat\{r\}\_\{\\max\}\\approx 0\.08, givingβ¯≥0\.04\\bar\{\\beta\}\\geq 0\.04\. Direct estimation ofTV​\(ℙ​\[Vi\+1∣V≤i\],ℙ​\[Vi\+1\]\)\\text\{TV\}\(\\mathbb\{P\}\[V\_\{i\+1\}\\mid V\_\{\\leq i\}\],\\;\\mathbb\{P\}\[V\_\{i\+1\}\]\)across all consecutive anchor pairs yieldsβ¯^TV≈0\.12\\hat\{\\bar\{\\beta\}\}\_\{\\text\{TV\}\}\\approx 0\.12\.

Usingβ¯^=0\.12\\hat\{\\bar\{\\beta\}\}=0\.12: the mixing penalty is\(3−1\)×0\.12=0\.24\(3\-1\)\\times 0\.12=0\.24forK=3K=3\. The adjusted bound is𝒮CART≤0\.12\+0\.56×\(0\.036\+0\.24\)=0\.275\\mathcal\{S\}\_\{\\text\{CART\}\}\\leq 0\.12\+0\.56\\times\(0\.036\+0\.24\)=0\.275, compared to0\.1400\.140under independence\. The empirical𝒮CART=0\.14\\mathcal\{S\}\_\{\\text\{CART\}\}=0\.14lies below both bounds, suggesting the actual dependence structure is more benign than the worst case\.

### A\.5\.Computational Complexity

###### Proposition 0 \(BCP Tractability\)\.

Suppose the constraint languageℒc\\mathcal\{L\}\_\{c\}has maximum variable domain sizeD=maxx⁡\|dom​\(x\)\|D=\\max\_\{x\}\|\\textup\{dom\}\(x\)\|\. Then:

1. \(i\)Checking satisfiability ofΣt∪\{c\}\\Sigma\_\{t\}\\cup\\\{c\\\}via Boolean Constraint Propagation runs inO​\(\|Σt\|⋅D\)O\(\|\\Sigma\_\{t\}\|\\cdot D\)time per anchor addition\.
2. \(ii\)The cumulative BCP cost over a full trace ofTTsteps with at mostTTanchors isO​\(T2​D\)O\(T^\{2\}D\)\.
3. \(iii\)For CART’s constraint language \(D≤20D\\leq 20\), this simplifies toO​\(\|Σt\|\)O\(\|\\Sigma\_\{t\}\|\)per step andO​\(T2\)O\(T^\{2\}\)cumulative\.

###### Proof\.

Each constraintc∈ℒcc\\in\\mathcal\{L\}\_\{c\}is a bounded\-arity predicate with arguments drawn from finite domains of size≤D\\leq D\. Convertingccto a propositional CNF clause produces at mostO​\(D\)O\(D\)literals\. Adding this clause to the existing CNFΣt\\Sigma\_\{t\}triggers unit propagation\. Each unit literal assignment triggers at most\|Σt\|\|\\Sigma\_\{t\}\|clause inspections, each examining at mostDDliterals\. The total propagation terminates after at most\|Σt\|⋅D\|\\Sigma\_\{t\}\|\\cdot Dliteral inspections \(standard result for unit propagation;Dechter \([2003](https://arxiv.org/html/2607.16727#bib.bib4)\); Dowling and Gallier \([1984](https://arxiv.org/html/2607.16727#bib.bib5)\)\)\. Summing overTTanchor additions:∑t=1TO​\(t⋅D\)=O​\(T2​D\)\\sum\_\{t=1\}^\{T\}O\(t\\cdot D\)=O\(T^\{2\}D\)\. ∎

### A\.6\.Tightness and Discussion

## Appendix BImplementation Details

Base MLLMs\.We instantiate CART on two open\-source MLLMs: LLaVA\-NeXT\-13B \(\(Liuet al\.,[2024a](https://arxiv.org/html/2607.16727#bib.bib7)\); LLaMA\-2\-13B backbone, CLIP ViT\-L/14 vision encoder\) and Qwen2\-VL\-7B\(Wanget al\.,[2024](https://arxiv.org/html/2607.16727#bib.bib11)\)\(ViT\-bigG vision encoder\)\. Vision encoders are frozen during fine\-tuning; only the language model layers \(via LoRA\) and the grounding headgψg\_\{\\psi\}are trained\.

Entity grounder\.We use Grounding DINO\(Liuet al\.,[2024b](https://arxiv.org/html/2607.16727#bib.bib9)\)\(Swin\-T backbone\(Liuet al\.,[2021](https://arxiv.org/html/2607.16727#bib.bib10)\), open\-vocabulary\) as a frozen module for mapping entity name strings in anchors to bounding boxes\. Its weights are not updated during CART training\.

Constraint languageℒc\\mathcal\{L\}\_\{c\}\.We define 14 predicate types covering standard scene\-graph ontologies:count,exists,color,shape,size,material,spatial\_rel\(left\_of,right\_of,above,below,in\_front\_of,behind\),action, andsame\_attribute\. Each predicate accepts 1\-3 typed arguments and returns a value from a known finite domain \(e\.g\., colors∈\\in\{red, blue, green,…\\ldots, 12 values\}, counts∈\{0,…,20\}\\in\\\{0,\\ldots,20\\\}, booleans∈\\in\{True, False\}\)\. The maximum domain size isD=20D=20, ensuring BCP tractability \(Proposition[13](https://arxiv.org/html/2607.16727#A1.Thmtheorem13)\)\.

### B\.1\.Hyperparameters

Visual grounding thresholdτv=0\.85\\tau\_\{v\}=0\.85, selected on a held\-out 5% split of GQA\-val by maximizingF1F\_\{1\}of violation detection\. Maximum retry budgetB=3B=3\(justified in§\\S3\.2\.4\)\. Loss weightsλc=0\.5\\lambda\_\{c\}=0\.5,λb=0\.3\\lambda\_\{b\}=0\.3, tuned via grid search over\{0\.1,0\.3,0\.5,1\.0\}2\\\{0\.1,0\.3,0\.5,1\.0\\\}^\{2\}on GQA\-val accuracy\.LoRA rankis set to 64, applied to all attention projections \(𝐖Q,𝐖K,𝐖V,𝐖O\\mathbf\{W\}\_\{Q\},\\mathbf\{W\}\_\{K\},\\mathbf\{W\}\_\{V\},\\mathbf\{W\}\_\{O\}\)\. We ablated ranks∈\{16,32,64,128\}\\in\\\{16,32,64,128\\\}and found accuracy saturates at rank 64 \(rank 32:−1\.1%\-1\.1\\%; rank 128:\+0\.2%\+0\.2\\%, within noise\)\. The relatively high rank \(compared to single\-task LoRA\) is warranted by the heterogeneous multi\-objective nature of our fine\-tuning, consistent with findings inHuet al\.\([2022](https://arxiv.org/html/2607.16727#bib.bib34)\)\.

Backtracking cost\.In the worst case, backtracking requires re\-generation of up toTTtokensBBtimes, yieldingO​\(B⋅T\)O\(B\\cdot T\)additional token generations\. In practice, the mean number of backtracks per trace is 0\.4, making amortized cost low\.

## Appendix CDetails of Experimental Setup

### C\.1\.Evaluation Metrics

Beyond standard end\-task accuracy, we introduce three diagnostic metrics motivated by our problem formulation:

- •Snowball Rate\(𝒮\\mathcal\{S\}; defined in§\\S[3\.1](https://arxiv.org/html/2607.16727#S3.SS1)\): estimated by comparing model traces against ground\-truth step annotations and computing the conditional cascading\-failure probability\. We manually annotate reasoning step correctness on a1,000\-instancediagnostic subset per benchmark, using3 independent annotatorsper instance with majority\-vote adjudication\.Inter\-annotator agreement: Cohen’sκ=0\.81\\kappa=0\.81for step\-correctness labels \(substantial agreement\)\. The annotation protocol requires each annotator to \(a\) align each model\-generated steprtr\_\{t\}to the closest ground\-truth steprt∗r\_\{t\}^\{\*\}and \(b\) label it ascorrect,partially correct, orincorrectbased on semantic equivalence of the core proposition; we binarize by treatingpartially correctasincorrect\.
- •Constraint Violation Rate\(CVR\): fraction of emitted non\-null anchors flagged by the CPM, measured asCVR=\|\{ct,j:pvis\(ct,j\|I\)<τv∨BCP fails\}\|/\|𝒜\|\\text\{CVR\}=\|\\\{c\_\{t,j\}:p\_\{\\text\{vis\}\}\(c\_\{t,j\}\|I\)<\\tau\_\{v\}\\;\\lor\\;\\text\{BCP fails\}\\\}\|\\;/\\;\|\\mathcal\{A\}\|\.
- •Error Attribution Precision\(EAP\): among all backtrack events triggered by the CPM, the fraction where the flagged anchor was indeed the earliest erroneous step \(verified against ground\-truth annotations\)\. Annotation uses the same pool and protocol as the snowball rate annotations, with inter\-annotatorκ=0\.76\\kappa=0\.76\(substantial agreement\)\.

Confidence intervals\.All diagnostic metrics are reported with 95% bootstrap confidence intervals computed via 10,000 resamples of the 1,000\-instance diagnostic subset\. For GQA \(LLaVA\-NeXT\-13B\):𝒮CART=0\.14±0\.02\\mathcal\{S\}\_\{\\text\{CART\}\}=0\.14\\pm 0\.02,CVR=0\.28±0\.01\\text\{CVR\}=0\.28\\pm 0\.01,EAP=0\.82±0\.03\\text\{EAP\}=0\.82\\pm 0\.03\. For VCR:𝒮CART=0\.22±0\.03\\mathcal\{S\}\_\{\\text\{CART\}\}=0\.22\\pm 0\.03,CVR=0\.35±0\.02\\text\{CVR\}=0\.35\\pm 0\.02,EAP=0\.71±0\.04\\text\{EAP\}=0\.71\\pm 0\.04\. The narrow CI widths \(≤0\.04\\leq 0\.04\) confirm that the reported reductions \(e\.g\.,𝒮0=0\.65→𝒮CART=0\.14\\mathcal\{S\}\_\{0\}=0\.65\\to\\mathcal\{S\}\_\{\\text\{CART\}\}=0\.14\) are statistically significant \(p<0\.001p<0\.001via permutation test\)\.

### C\.2\.Empirical Estimation of Theorem[4](https://arxiv.org/html/2607.16727#A1.Thmtheorem4)

On the 1,000\-instance diagnostic subsets, we estimateδ\\delta,γ\\gamma, andεrec\\varepsilon\_\{\\text\{rec\}\}empirically\.

- •Soundness errorδ\\delta: fraction of CPM\-accepted anchors that are factually false \(verified against scene graphs\)\. Importantly,δ\\deltais measured end\-to\-end: it reflects the full pipeline including Grounding DINO errors\. Specifically, when Grounding DINO fails to localize an entity \(the 6\.2% fallback\-to\-full\-image\-pooling cases, plus 4\.5% of cases with IoU<0\.5<0\.5but above the confidence threshold\), the degraded visual features fed togψg\_\{\\psi\}reduce its discriminative power, inflatingδ\\delta\. We estimateδ≈0\.07\\delta\\approx 0\.07on GQA/CLEVR \(where Grounding DINO is most reliable\) andδ≈0\.11\\delta\\approx 0\.11on VCR \(where the 17\.3% grounding failure rate at IoU≥0\.5\\geq 0\.5compounds with VCR’s noisier constraints\)\. These estimates include all such cascaded error sources\.
- •Coupling rateγ\\gamma: among instances with a first error at steptt, the fraction of subsequent anchors whose ground\-truth value is inconsistent with the erroneous step’s proposition\. Estimated atγ≈0\.72\\gamma\\approx 0\.72\(GQA\),γ≈0\.81\\gamma\\approx 0\.81\(CLEVR, where highly structured scenes create tight coupling\), andγ≈0\.58\\gamma\\approx 0\.58\(VCR, where free\-form reasoning reduces coupling\)\.
- •Recovery failure rateεrec\\varepsilon\_\{\\text\{rec\}\}: among instances where the CPM detected a violation and triggered backtracking, the fraction where the final answer was still incorrect due to cascading errors in the post\-backtrack continuation\. Estimated atεrec≈0\.12\\varepsilon\_\{\\text\{rec\}\}\\approx 0\.12\(GQA\),εrec≈0\.08\\varepsilon\_\{\\text\{rec\}\}\\approx 0\.08\(CLEVR\), andεrec≈0\.19\\varepsilon\_\{\\text\{rec\}\}\\approx 0\.19\(VCR\)\. The higher VCR value reflects both the greater difficulty of VCR reasoning and the noisier constraint quality\.

Decomposition ofεrec\\varepsilon\_\{\\text\{rec\}\}\.We disentangle the three failure modes contributing to recovery failure on GQA \(εrec=0\.12\\varepsilon\_\{\\text\{rec\}\}=0\.12,n=187n=187catch events\): \(i\)re\-introductionof a semantically equivalent error accounts forpreintro=0\.065p\_\{\\text\{reintro\}\}=0\.065\(15/23 failures\); \(ii\)retry budget exhaustionwithout finding any valid continuation accounts forpexhaust=0\.022p\_\{\\text\{exhaust\}\}=0\.022\(5/23\); and \(iii\)novel cascading errorintroduced in the post\-backtrack continuation accounts forpnovel=0\.013p\_\{\\text\{novel\}\}=0\.013\(3/23\)\. The per\-retry fix probability ispfix≈0\.51p\_\{\\text\{fix\}\}\\approx 0\.51, estimated from the fraction of first retries that produce a correct continuation conditional on a correct detection event\. This validates the geometric decay model in Assumption[4](https://arxiv.org/html/2607.16727#Thmassumption4):εrec≤\(1−pfix\)B=\(0\.49\)3=0\.118\\varepsilon\_\{\\text\{rec\}\}\\leq\(1\-p\_\{\\text\{fix\}\}\)^\{B\}=\(0\.49\)^\{3\}=0\.118, consistent with the observed value\.

## Appendix DTraining and Optimization Procedure

Training proceeds in three stages\.

Stage 1: Constraint\-Annotated Data Construction\.We derive ground\-truth constraint annotations from scene graphs and rationales available in GQA\(Hudson and Manning,[2019](https://arxiv.org/html/2607.16727#bib.bib2)\), CLEVR\-CoGenT\(Johnsonet al\.,[2017](https://arxiv.org/html/2607.16727#bib.bib1)\), and VCR\(Zellerset al\.,[2019](https://arxiv.org/html/2607.16727#bib.bib3)\)\. For each\(I,q,a∗\)\(I,q,a^\{\*\}\)triple, we construct mixed traces as follows\.

GQA and CLEVR\-CoGenT\.These datasets provide structured functional programs \(e\.g\.,filter\(scene, color=red\)→\\torelate\(\_, left\)→\\tocount\)\. We execute each program step to obtain intermediate results and map each step to a constraint inℒc\\mathcal\{L\}\_\{c\}using deterministic rule\-based templates\. For example, the program stepfilter\(scene, color=red\)produces the constraint exists\(red\_objects\) = True;relate\(obj\_3, left, obj\_7\)with attribute lookup producesspatial\_rel\(left\_of, dog, cat\) = True\. Object names are resolved from the scene graph’s attribute annotations\. Anchors are inserted into the linearized CoT trace at the position corresponding to each program step\.

VCR\.VCR rationales are free\-form natural language\. We employ a dedicatedNLP extraction pipeline:

1. \(1\)Dependency parsingvia spaCy \(en\_core\_web\_trf\) to extract subject\-verb\-object triples\.
2. \(2\)Semantic role labelingvia AllenNLP’s BERT\-based SRL model to identify agent, patient, and spatial/attribute arguments\.
3. \(3\)Template matching: extracted triples are matched againstℒc\\mathcal\{L\}\_\{c\}predicates using a hand\-crafted rule set \(78 rules\)\.
4. \(4\)Entity resolution: entity mentions in VCR use indexed tags \(e\.g\.,\[person1\]\); we resolve these to descriptive names using VCR’s metadata and scene\-graph overlap where available\.

We manually verified the quality of this pipeline on 500 randomly sampled VCR instances \(two annotators, adjudicated disagreements\)\. Measuredprecision: 78\.4%;recall:65\.1%\. Primary error modes: failed SRL on complex subordinate clauses \(14% of errors\), polysemous predicates mapped to wrongℒc\\mathcal\{L\}\_\{c\}type \(8%\), and entity co\-reference failures \(12%\)\. We filter VCR\-derived constraints by a confidence heuristic \(SRL confidence≥0\.7\\geq 0\.7and template\-match uniqueness\) and discard instances where fewer than two constraints survive, yielding28K VCR instances\.

Impact of VCR noise on grounding head training\.The≈21\.6%\\approx 21\.6\\%error rate in VCR\-derived constraints constitutesone\-sided label noise: incorrect constraints are false positives \(labeledyt,j=1y\_\{t,j\}=1but factually incorrect\), whereas synthetically generated negatives \(see Stage 2 below\) are always correctly labeledyt,j=0y\_\{t,j\}=0\. This asymmetry can biasgψg\_\{\\psi\}toward accepting certain false constraints, particularly those involving VCR’s more complex relational predicates \(e\.g\., ‘action‘\)\. To mitigate this, we applyper\-source loss weightinginℒcst\\mathcal\{L\}\_\{\\text\{cst\}\}: VCR\-derived constraint instances receive weightwVCR=0\.7w\_\{\\text\{VCR\}\}=0\.7while GQA/CLEVR instances receive weight1\.01\.0\.

Summary\.This procedure yields218Ktraining instances \(142K from GQA, 48K from CLEVR\-CoGenT, 28K from VCR\) after filtering for traces containing at least two non\-null constraints\. Variable anchor density is naturally induced: GQA traces average 3\.1 anchors per trace, CLEVR 4\.7, and VCR 2\.2\.

Stage 2: Joint Fine\-Tuning\.We fine\-tuneℳθ\\mathcal\{M\}\_\{\\theta\}\(via LoRA, rank 64, applied to𝐖Q,𝐖K,𝐖V,𝐖O\\mathbf\{W\}\_\{Q\},\\mathbf\{W\}\_\{K\},\\mathbf\{W\}\_\{V\},\\mathbf\{W\}\_\{O\}in all layers\) and traingψg\_\{\\psi\}from scratch, jointly optimizing:

\(11\)ℒ=ℒtask\+λc​ℒcst\+λb​ℒbt,\\mathcal\{L\}=\\mathcal\{L\}\_\{\\text\{task\}\}\+\\lambda\_\{c\}\\mathcal\{L\}\_\{\\text\{cst\}\}\+\\lambda\_\{b\}\\mathcal\{L\}\_\{\\text\{bt\}\},\(12\)ℒcst\\displaystyle\\mathcal\{L\}\_\{\\text\{cst\}\}=−∑\(t,j\)∈𝒜′ws\[yt,jloggψ\(ct,j,𝐕\)\\displaystyle=\-\\sum\_\{\(t,j\)\\in\\mathcal\{A\}^\{\\prime\}\}\\\!w\_\{s\}\\big\[y\_\{t,j\}\\log g\_\{\\psi\}\(c\_\{t,j\},\\mathbf\{V\}\)\+\(1−yt,j\)log\(1−gψ\(ct,j,𝐕\)\)\]\\displaystyle\+\(1\{\-\}y\_\{t,j\}\)\\log\(1\{\-\}g\_\{\\psi\}\(c\_\{t,j\},\\mathbf\{V\}\)\)\\big\]\(13\)ℒbt=−∑t∈ℬlog⁡pθ​\(<RETRY\>⋅rt∗,alt∣𝐫<terr,I,q\)\\mathcal\{L\}\_\{\\text\{bt\}\}=\-\\sum\_\{t\\in\\mathcal\{B\}\}\\log p\_\{\\theta\}\(\\texttt\{<RETRY\>\}\\cdot r\_\{t\}^\{\*,\\text\{alt\}\}\\mid\\mathbf\{r\}\_\{<t\}^\{\\text\{err\}\},I,q\)where:

- •ℒtask=−∑tlog⁡pθ​\(rt∗∣𝐫<t∗,I,q\)\\mathcal\{L\}\_\{\\text\{task\}\}=\-\\sum\_\{t\}\\log p\_\{\\theta\}\(r\_\{t\}^\{\*\}\\mid\\mathbf\{r\}\_\{<t\}^\{\*\},I,q\)is the standard autoregressive cross\-entropy over all tokens in the mixed trace \(reasoning tokens, delimiter tokens, anchor tokens, and<NULL\_CON/\>tokens\)\.
- •Equation[12](https://arxiv.org/html/2607.16727#A4.E12)is the binary cross\-entropy for the grounding head with per\-source weightwsw\_\{s\}\(ws=0\.7w\_\{s\}=0\.7for VCR,ws=1\.0w\_\{s\}=1\.0for GQA/CLEVR\), where𝒜′\\mathcal\{A\}^\{\\prime\}indexes all anchor positions \(including synthetically negated ones\) andyt,j∈\{0,1\}y\_\{t,j\}\\in\\\{0,1\\\}is the ground\-truth satisfaction label\. Negative anchors are constructed by perturbing ground\-truth constraints \(swapping entity arguments, changing attribute values, or negating relational predicates\) at a 1:1 positive\-to\-negative ratio\.
- •Equation[13](https://arxiv.org/html/2607.16727#A4.E13)is thebacktrack\-aware losscomputed over synthetically corrupted traces\. We create a setℬ\\mathcal\{B\}by replacing a randomly chosen correct anchor with an incorrect one and providing the model the prefix up to the last valid checkpoint, followed by<RETRY\>\.

Construction of alternative continuationsrt∗,altr\_\{t\}^\{\*,\\text\{alt\}\}\. We use a two\-source mixture\. For 70% of backtrack training instances,rt∗,altr\_\{t\}^\{\*,\\text\{alt\}\}is the original gold continuation from the last valid checkpoint onward\. For the remaining 30%,rt∗,altr\_\{t\}^\{\*,\\text\{alt\}\}is adiverse alternativegenerated by the base MLLM itself \(before CART fine\-tuning\) via nucleus sampling \(p=0\.9p=0\.9, temperature=0\.8=0\.8\) conditioned on the checkpoint prefix plus<RETRY\>token, filtered to retain only samples whose final answer matches the ground\-truth answera∗a^\{\*\}\. Among sampled candidates \(up to 5 per instance\), we select the one with lowest token\-level overlap with the gold continuation \(measured by BLEU\-4\) to maximize diversity\. If no valid alternative is found, the gold continuation is used as fallback\.

Handling of<RETRY\>in the base model\.The<RETRY\>token is a newly added special token whose embedding is randomly initialized \(drawn from𝒩​\(0,0\.022\)\\mathcal\{N\}\(0,0\.02^\{2\}\), matching the LLM’s embedding initialization scale\) in the base MLLM’s vocabulary\. When generating the 30% diverse alternative continuations using thepre\-fine\-tunedbase model, this randomly initialized embedding providesno semantically meaningful conditioning—the base model has never encountered this token during pretraining\. We treat this as an intentional design choice: the random embedding acts as astochastic perturbationon the prefix representation, encouraging the base model to explore a slightly different region of its output distribution compared to continuing from the same prefix without the token\. This is functionally analogous to adding a small noise injection before sampling, which promotes diversity\. In pilot experiments, we compared this approach against \(a\) omitting<RETRY\>entirely \(lower diversity: mean BLEU\-4 with gold = 0\.61 vs\. 0\.53 with<RETRY\>\) and \(b\) using a hand\-crafted natural\-language retry prompt \(”Try a different approach:”\), which yielded similar diversity but introduced systematic style shifts\. After CART fine\-tuning \(Stage 2\), the<RETRY\>embedding is trained and acquires the intended semantic meaning of ”explore an alternative reasoning path\.”

Optimization details\.We use AdamW \(β1=0\.9\\beta\_\{1\}=0\.9,β2=0\.95\\beta\_\{2\}=0\.95, weight decay0\.050\.05\) with a cosine learning\-rate schedule warming up over 500 steps to a peak of2×10−52\\times 10^\{\-5\}\(LLM LoRA parameters\) and5×10−45\\times 10^\{\-4\}\(grounding headgψg\_\{\\psi\}\)\. Training runs for 3 epochs on 8×\\timesA100\-80GB GPUs with DeepSpeed ZeRO\-2\(Renet al\.,[2021](https://arxiv.org/html/2607.16727#bib.bib6)\), effective batch size 128 \(gradient accumulation factor 4\)\. Total training time is approximately 18 hours for LLaVA\-NeXT\-13B\(Liuet al\.,[2024a](https://arxiv.org/html/2607.16727#bib.bib7)\)and 11 hours for Qwen2\-VL\-7B\.

Stage 3: Grounding Head Calibration\.After joint training, we calibrate the grounding head’s thresholdτv\\tau\_\{v\}using temperature scaling\(Guoet al\.,[2017](https://arxiv.org/html/2607.16727#bib.bib35)\)on the held\-out GQA\-val split, optimizing expected calibration error \(ECE\)\. This ensures thatτv=0\.85\\tau\_\{v\}=0\.85reliably separates satisfied from violated constraints in distribution\.

Data flow summary\.At training time, the forward pass processes a mixed trace through the LLM backbone; anchor tokens contribute to bothℒtask\\mathcal\{L\}\_\{\\text\{task\}\}\(via the LLM head\) andℒcst\\mathcal\{L\}\_\{\\text\{cst\}\}\(via the grounding headgψg\_\{\\psi\}, whose input features are extracted using frozen Grounding DINO boxes\)\. Corrupted\-trace samples contribute toℒbt\\mathcal\{L\}\_\{\\text\{bt\}\}\. All three losses are summed and a single backward pass updates LoRA weights andgψg\_\{\\psi\}parameters\. Gradients flow throughgψg\_\{\\psi\}normally;BCP never receives gradientsand is used only as a deterministic pre\-computation to produce binary consistency labels during training data construction\. At inference time, the CPM \(bothgψg\_\{\\psi\}forward pass and BCP\) acts as a hard gate \(Algorithm 1\) with no gradient flow; the backtrack controller is fully deterministic\.