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 [1], [2]. 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 [3], [4] generate multiple candidate chains and select answers by majority vote or heuristic scoring, but provide no mechanism to identify which step failed or why—they merely hope that the correct chain appears among the samples. Post-hoc self-verification [5], [6] 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 [7], [8] 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 a principled middle ground: a framework that preserves the flexibility of natural language reasoning while injecting verifiable symbolic checkpoints that can catch errors as they occur and trigger corrective action before they propagate. To this end, we propose Constraint-Anchored Reasoning Traces (CART), a framework that trains MLLMs to interleave standard reasoning steps with symbolic constraint assertions—lightweight, machine-checkable statements about visual content (e.g., count(red_objects) = 3, left_of(dog, cat) = True). A dedicated Constraint 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 a backtrack controller reverts the trace to the last consistent checkpoint, preventing error propagation.

A key design insight of CART is variable-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 [9], CLEVR-CoGenT [10], VCR [11]) 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 [12], Qwen2-VL [13]), 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 1).

• 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 [2] and its variants have become the de facto approach for eliciting multi-step reasoning from large language models. Zero-shot CoT [14] and few-shot prompting strategies improve performance on arithmetic and commonsense benchmarks, while multimodal extensions [15], [16] adapt these techniques to vision-language tasks. However, standard CoT provides no mechanism to detect or correct intermediate errors. Tree-of-Thoughts [4] 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 [3] marginalizes over sampled chains by majority voting, improving robustness statistically but offering no per-chain error correction. DDCoT [17] 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 introducing externally verifiable symbolic 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 [18], [19] compose differentiable modules according to syntactic parses of questions, while NS-VQA [20] uses a scene parser to construct symbolic representations for program execution. More recently, VisProg [7] and ViperGPT [8] leverage LLMs to generate executable Python programs that invoke specialized vision modules. Faithful CoT [21] 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 [5] maintains an episodic memory of verbal self-reflections to improve subsequent attempts, while Self-Refine [6] iterates between generation and self-critique within a single inference pass. In the visual domain, visual verification approaches [22] 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 a partially external verification loop: the neural grounding head is anchored to independently extracted visual evidence (region features from a frozen Grounding DINO [23] 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)—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.

3 Methodology↩︎

We present Constraint-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 \(\theta\) produces, given an image \(I \in \mathcal{I}\) and question \(q \in \mathcal{Q}\), an answer \(a\) via an autoregressive chain-of-thought (CoT) trace \(\mathbf{r} = (r_1, r_2, \ldots, r_T)\), where each \(r_t\) is a reasoning step (a span of tokens). The final answer \(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 \(\mathbf{V} = \phi(I) \in \mathbb{R}^{N \times d_v}\), where \(N\) is the number of spatial tokens and \(d_v\) is the per-token feature dimension.

Error snowballing. We define an error event at step \(t\) as \(e_t = \mathbb{1}[\text{sem}(r_t) \neq \text{sem}(r_t^*)]\), where \(\text{sem}(\cdot)\) extracts the semantic proposition of a step and \(r_t^*\) is the ground-truth counterpart. The snowball rate \(\mathcal{S}\) is the conditional probability that all subsequent steps are erroneous given a first error: \[\mathcal{S} = \mathbb{P}\!\Big[\bigcap_{t'=t+1}^{T} \{e_{t'}=1\} \;\Big|\; e_t = 1,\; \forall_{t''<t}\; e_{t''}=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}\):

\[\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 \(\lambda_c, \lambda_b > 0\) are balancing coefficients. Each loss term is defined in Appendix 10.

3.2 Constraint-Anchored Reasoning Traces↩︎

CART introduces three interlocking components: (i) variable-frequency anchor-interleaved generation, (ii) a constraint propagation module (CPM), and (iii) a backtrack 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 of constraint anchors. Formally, an anchor \(c\) is a symbolic assertion drawn from a domain-specific constraint language \(\mathcal{L}_c\):

\[c \;=\; \texttt{pred}(\texttt{arg}_1, \ldots, \texttt{arg}_k) \bowtie v, \quad \bowtie \;\in\; \{=, \neq, <, >, \leq, \geq\},\] where \(\texttt{pred}\) is a visual predicate (e.g., count, color, spatial_rel), \(\texttt{arg}_i\) are grounded entity references, and \(v\) is a value. Examples include count(red_objects) = 3 and left_of(dog, cat) = True. The language \(\mathcal{L}_c\) is intentionally kept lightweight—propositional with bounded-arity predicates and finite domains—so that checking is efficient (see Proposition 1).

Variable-frequency emission. Rather than enforcing a rigid one-to-one alternation between reasoning steps and anchors, we allow the model to emit zero, one, or multiple anchors 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: \[\mathbf{r} = \big(r_1, \mathbf{c}_1, \; r_2, \mathbf{c}_2, \; \ldots, \; r_T, \mathbf{c}_T\big),\] where \(\mathbf{c}_t \in \mathcal{L}_c^{*} \cup \{\texttt{<NULL\_CON/>}\}\) denotes a possibly-empty sequence of anchors following step \(r_t\). Let \(\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 [23] as a frozen, off-the-shelf entity grounding module. Specifically:

• For each anchor \(c_{t,j}\) with entity arguments \((\texttt{arg}_1, \ldots, \texttt{arg}_k)\), each argument string is passed to Grounding DINO along with the image \(I\), producing a set of candidate bounding boxes with confidence scores.

• The top-1 box per argument (confidence threshold \(\geq 0.3\)) is projected onto the spatial token grid of the vision encoder, yielding a subset of spatial token indices \(\mathcal{R}_i \subseteq \{1, \ldots, N\}\) for each \(\texttt{arg}_i\).

• RoI-Align [24] extracts region-level visual features \(\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 to full-image mean pooling \(\mathbf{v}_i = \text{MeanPool}(\mathbf{V}) \in \mathbb{R}^{d_v}\) and flag the anchor as weakly 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 \(\geq 0.5\), grounding accuracy is 89.3% (GQA/CLEVR entities) and 82.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.

3.2.3 Constraint Propagation Module↩︎

The CPM acts as an external verifier. Its neural component (\(g_\psi\)) is trained end-to-end while its symbolic 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 2). The CPM maintains a constraint store \(\Sigma_t = \{c_{t',j} : (t',j) \in \mathcal{A},\; t' \leq t\}\) that grows as non-null anchors are emitted.

Visual grounding check. Each non-null anchor \(c_{t,j}\) is verified against the visual feature bank \(\mathbf{V}\) via a lightweight grounding head \(g_\psi\). The input to \(g_\psi\) is the concatenation of (i) the region-level visual feature \(\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), and (ii) a text embedding \(\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_\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 \(\mathbf{W}_1 \in \mathbb{R}^{512 \times (d_v + d_t)}\), \(\mathbf{W}_2 \in \mathbb{R}^{1 \times 512}\), layer normalization (LN), and sigmoid output \(\sigma\). Concretely, for LLaVA-NeXT-13B: \(d_v = 1024\) (CLIP ViT-L/14), \(d_t = 5120\) (LLaMA-2-13B), so the input dimension is \(6144\); for Qwen2-VL-7B: \(d_v = 1408\) (ViT-bigG), \(d_t = 4096\) (Qwen-7B), input dimension \(5504\). Total grounding head parameters:  3.2M (LLaVA-NeXT) /  2.9M (Qwen-VL).

The grounding head outputs \(p_{\text{vis}}(c_{t,j} \mid I) = g_\psi(c_{t,j}, \mathbf{V}) \in [0,1]\). If \(p_{\text{vis}}(c_{t,j} \mid I) < \tau_v\), the anchor is flagged as visually violated.

Mutual consistency check. We additionally perform Boolean Constraint Propagation (BCP) over \(\Sigma_t \cup \{c_{t,j}\}\). Because \(\mathcal{L}_c\) is propositional with finite domains, checking satisfiability of the accumulated constraint set is tractable. We convert \(\Sigma_t \cup \{c_{t,j}\}\) into a conjunction of literals and apply unit propagation; if the empty clause is derived, a logical contradiction is 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 anchor \(c_{t,j}\), the backtrack controller halts autoregressive generation and reverts the trace to the most recent consistent checkpoint. Formally, since all anchors currently in \(\Sigma_t\) were individually verified when admitted (and removing constraints from a satisfiable set preserves satisfiability), the checkpoint is simply the most recent anchor in \(\Sigma_t\) in trace order—i.e., the anchor \((t',j')\) with the largest trace position such that \((t',j') < (t,j)\) and \(c_{t',j'} \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 budget \(B = 3\) prevents infinite loops.

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

Retry budget exhaustion (\(\text{retries} > B\)). If the retry budget \(B\) is 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 extractor \(f_{\text{ans}}\). In this fallback mode, \(f_{\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)\) 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 for \(B = 3\). A pilot ablation over \(B \in \{1, 2, 3, 5, 10\}\) on GQA-val (1K instances) showed accuracy gains plateauing at \(B = 3\) (+0.2% from \(B=3\) to \(B=5\), within noise) while mean inference latency grows linearly with \(B\).

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 [9]: compositional visual question answering over real-world images with functional program annotations. We use the balanced testdev split (12,578 questions).

• CLEVR-CoGenT [10]: synthetic geometric reasoning requiring counting, spatial relation, and attribute comparison over rendered scenes. We evaluate on Condition A (15,000 questions).

• VCR [11]: 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 [25]: 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 [26]: a polling-based benchmark for evaluating object hallucination in MLLMs. We report F1 score on the random, popular, and adversarial splits (averaged).

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 [4], which explores multiple reasoning branches via LLM-based evaluation; Reflexion [5], which uses verbal self-critique for iterative refinement; and Self-Consistency [3], which marginalizes over sampled chains by majority voting.

• Program synthesis: VisProg [7], which generates executable visual programs; Faithful CoT [21], which interleaves natural language with symbolic reasoning; and DDCoT [17], which decomposes questions into sub-problems.

• Fine-tuned self-correction: DDCoT (LoRA-FT), Visual Verification (FT), Self-Consistency (FT), and Self-Refine [6] (FT), all fine-tuned on the same 218K training instances using identical LoRA configuration (rank 64) for a fair comparison. Visual Verification [22] 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 report CART-Anchors, which uses constraint-annotated training data but disables CPM and backtracking at inference, isolating runtime verification’s effect.

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 9. Hyperparameters and training details are also provided in Appendix 9.

Reproducibility. All fine-tuned results in Table 1 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 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.

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 achieves \(0.72\) mean IoU on anchor entity regions versus \(0.41\) for 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 budget \(B{=}3\); \(B{=}10\) yielded negligible gains with linearly increasing latency. Threshold \(\tau_v{=}0.85\) optimally filtered low-confidence noise; at \(\tau_v{=}0.95\), the false rejection rate doubled to \(\alpha{\approx}0.11\), causing unnecessary backtracks on \(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 1. 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 [27] (\(\delta{\approx}0.09\)) or OWLv2 [28] (\(\delta{\approx}0.12\)) yields 68.1% and 67.5% on GQA, respectively (vs.% with Grounding DINO, \(\delta{\approx}0.07\)). All configurations outperform the best non-CART baseline (64.8%), confirming graceful degradation with grounder quality as predicted by Theorem 1.

Predicate coverage ablation. We evaluated CART with 7, 14 (default), and 18 predicates. On GQA: 7 predicates yield 66.9% (\(\gamma{\approx}0.61\), \(\mathcal{S}{=}0.21\)); 14 yield 69.4% (\(\gamma{\approx}0.72\), \(\mathcal{S}{=}0.14\)); 18 yield 69.8% (\(\gamma{\approx}0.75\), \(\mathcal{S}{=}0.13\)). Diminishing returns beyond 14 predicates suggest the default coverage captures most error-prone steps, while the 7-predicate drop confirms \(\gamma\) as the primary driver of CART’s benefit (Corollary 2).

5.2 Scalability and Computational Efficiency↩︎

A common concern with runtime verification is inference overhead. Table 3 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, overhead decreases with model scale: from \(1.15\)–\(1.18\times\) on Qwen2-VL-7B to \(1.10\times\) on 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 (\({\sim}3.2\)M parameters for LLaVA-NeXT / \({\sim}2.9\)M 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{=}5\)) requires \(5\times\) the base inference cost; Tree-of-Thoughts with 3 branches incurs \(3\)–\(4\times\) overhead due to repeated forward passes and LLM-based branch evaluation. CART achieves comparable or superior accuracy gains (Table 1) at \(1.10\)–\(1.18\times\) cost—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 1 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.

7 Theoretical Analysis↩︎

We provide formal guarantees for CART’s error-arresting mechanism. The central challenges are that (a) an anchor being correct (sound) does not by itself guarantee that it detects an upstream error, and (b) detecting an error via an anchor does not guarantee successful recovery. We address both with explicit assumptions in §7.1, prove the main snowball-rate reduction result in §7.2, derive end-to-end accuracy and no-harm guarantees in §7.3, relax the independence assumption via \(\beta\)-mixing in §7.4, establish computational complexity in §7.5, and discuss tightness and limitations in §7.6.

7.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 anchor \(c\) if and only if \(p_{\text{vis}}(c \mid I) \geq \tau_v\) and \(\text{BCP}(\Sigma \cup \{c\}) = \text{SAT}\).

We now state the assumptions required for our analysis.

Justification. The grounding head \(g_\psi\) is trained on \({\sim}218\)K instances with balanced positive/negative anchors (§3.5), achieving empirical false acceptance rates \(\delta \approx 0.07\) (GQA/CLEVR) and \(\delta \approx 0.11\) (VCR). The BCP component contributes additional rejection power for logical contradictions, which can only decrease \(\delta\). The completeness parameter \(\alpha\) is estimated at \(\alpha \approx 0.05\) (GQA) and \(\alpha \approx 0.09\) (VCR).

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 §7.4 using \(\beta\)-mixing coefficients. Assumption 2 provides a clean baseline bound and is approximately valid when anchors reference distinct spatial regions and non-overlapping semantic content, which holds for \({\sim}78\%\) of anchor pairs in our GQA traces (measured by IoU \(< 0.1\) between grounded regions).

Justification. The coupling rate \(\gamma\) quantifies how tightly the constraint language \(\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 (\(\gamma \approx 0.72\)–\(0.81\)). For free-form reasoning (VCR), \(\gamma\) is lower (\({\approx}0.58\)). In the extreme case where anchors are completely tangential to the error source (\(\gamma = 0\)), CART provides no benefit, and the bound in Theorem 1 reduces to \(\mathcal{S}_0\).

Justification. This assumption explicitly acknowledges that detection does not guarantee recovery. The parameter \(\varepsilon_{\text{rec}}\) encapsulates three failure modes: (i) retry budget \(B\) exhaustion, (ii) re-introduction of a semantically equivalent error, and (iii) introduction of a novel cascading error. Empirically, \(\varepsilon_{\text{rec}} \in [0.08, 0.19]\) across our benchmarks. With \(B = 3\) retries, 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 probability \(p_{\text{fix}}\), then \(\varepsilon_{\text{rec}} \leq (1 - p_{\text{fix}})^B\), giving \(\varepsilon_{\text{rec}} \leq 0.125\) for \(p_{\text{fix}} = 0.5\) and \(B = 3\).

Justification. The first condition holds by definition when the CoT trace faithfully represents the reasoning path and the answer extractor \(f_{\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\%\) of snowball instances yield an incorrect answer.

Justification. This assumption is needed because Theorem 1’s Case 1 (error not caught) involves the CART-fine-tuned model continuing without CPM correction, not the original base model. We expect \(\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 \(\mathcal{S}_0^{\text{PT}} = 0.61\) on GQA (vs.\(\mathcal{S}_0 = 0.68\) for the base model), confirming the bound holds with margin.

7.2 Snowball Rate Reduction↩︎

We first establish a useful per-anchor detection probability.

We now state and prove the main result.

7.3 End-to-End Accuracy and No-Harm Guarantees↩︎

We translate the snowball-rate reduction into accuracy bounds. Let \(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.

Practical interpretation. For GQA with \(p_1 \approx 0.42\), \(\eta_0 \approx 0.55\), \(\mathcal{S}_0 = 0.68\), and \(\mathcal{S}_{\text{CART}} \leq 0.14\): \(\text{Acc}_{\text{CART}} - \text{Acc}_0 \geq 0.42 \times 0.55 \times 0.54 = 0.125\), i.e., at least \(12.5\) percentage points of accuracy improvement from snowball reduction alone. The observed improvement is \(+14.2\%\), suggesting that CART additionally improves \(\eta\) or reduces \(p_1\) through its constraint-guided training.

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

Interpretation. Theorem 3 guarantees that CART’s accuracy is within \(\varepsilon_{\text{harm}} \leq 0.006\) of 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.

7.4 Analysis Under Dependent Anchors↩︎

Assumption 2 is an idealization. We relax it using \(\beta\)-mixing.

Empirical mixing estimation. We estimate \(\bar{\beta}\) on the GQA diagnostic subset (1,000 instances). Maximum absolute Pearson correlation between consecutive anchor verification outcomes yields \(\hat{r}_{\max} \approx 0.08\), giving \(\bar{\beta} \geq 0.04\). Direct estimation of \(\text{TV}(\mathbb{P}[V_{i+1} \mid V_{\leq i}],\; \mathbb{P}[V_{i+1}])\) across all consecutive anchor pairs yields \(\hat{\bar{\beta}}_{\text{TV}} \approx 0.12\).

Using \(\hat{\bar{\beta}} = 0.12\): the mixing penalty is \((3-1) \times 0.12 = 0.24\) for \(K = 3\). The adjusted bound is \(\mathcal{S}_{\text{CART}} \leq 0.12 + 0.56 \times (0.036 + 0.24) = 0.275\), compared to \(0.140\) under independence. The empirical \(\mathcal{S}_{\text{CART}} = 0.14\) lies below both bounds, suggesting the actual dependence structure is more benign than the worst case.

7.5 Computational Complexity↩︎

7.6 Tightness and Discussion↩︎

8 Implementation Details↩︎

Base MLLMs. We instantiate CART on two open-source MLLMs: LLaVA-NeXT-13B ([12]; LLaMA-2-13B backbone, CLIP ViT-L/14 vision encoder) and Qwen2-VL-7B [13] (ViT-bigG vision encoder). Vision encoders are frozen during fine-tuning; only the language model layers (via LoRA) and the grounding head \(g_\psi\) are trained.

Entity grounder. We use Grounding DINO [23] (Swin-T backbone [31], 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 \(\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, and same_attribute. Each predicate accepts 1-3 typed arguments and returns a value from a known finite domain (e.g., colors \(\in\) , counts \(\in \{0,\ldots,20\}\), booleans \(\in\) ). The maximum domain size is \(D = 20\), ensuring BCP tractability (Proposition 1).

8.1 Hyperparameters↩︎

Visual grounding threshold \(\tau_v = 0.85\), selected on a held-out 5% split of GQA-val by maximizing \(F_1\) of violation detection. Maximum retry budget \(B = 3\) (justified in \(\S\) 3.2.4). Loss weights \(\lambda_c = 0.5\), \(\lambda_b = 0.3\), tuned via grid search over \(\{0.1, 0.3, 0.5, 1.0\}^2\) on GQA-val accuracy. LoRA rank is set to 64, applied to all attention projections (\(\mathbf{W}_Q, \mathbf{W}_K, \mathbf{W}_V, \mathbf{W}_O\)). We ablated ranks \(\in \{16, 32, 64, 128\}\) and found accuracy saturates at rank 64 (rank 32: \(-1.1\%\); rank 128: \(+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 in [32].

Backtracking cost. In the worst case, backtracking requires re-generation of up to \(T\) tokens \(B\) times, yielding \(O(B \cdot T)\) additional token generations. In practice, the mean number of backtracks per trace is 0.4, making amortized cost low.

9 Details of Experimental Setup↩︎

9.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): estimated by comparing model traces against ground-truth step annotations and computing the conditional cascading-failure probability. We manually annotate reasoning step correctness on a 1,000-instance diagnostic subset per benchmark, using 3 independent annotators per instance with majority-vote adjudication. Inter-annotator agreement: Cohen’s \(\kappa = 0.81\) for step-correctness labels (substantial agreement). The annotation protocol requires each annotator to (a) align each model-generated step \(r_t\) to the closest ground-truth step \(r_t^*\) and (b) label it as correct, partially correct, or incorrect based on semantic equivalence of the core proposition; we binarize by treating partially correct as incorrect.

• Constraint Violation Rate (CVR): fraction of emitted non-null anchors flagged by the CPM, measured as \(\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 \(\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): \(\mathcal{S}_{\text{CART}} = 0.14 \pm 0.02\), \(\text{CVR} = 0.28 \pm 0.01\), \(\text{EAP} = 0.82 \pm 0.03\). For VCR: \(\mathcal{S}_{\text{CART}} = 0.22 \pm 0.03\), \(\text{CVR} = 0.35 \pm 0.02\), \(\text{EAP} = 0.71 \pm 0.04\). The narrow CI widths (\(\leq 0.04\)) confirm that the reported reductions (e.g., \(\mathcal{S}_0 = 0.65 \to \mathcal{S}_{\text{CART}} = 0.14\)) are statistically significant (\(p < 0.001\) via permutation test).

9.2 Empirical Estimation of Theorem 1↩︎

On the 1,000-instance diagnostic subsets, we estimate \(\delta\), \(\gamma\), and \(\varepsilon_{\text{rec}}\) empirically.

• Soundness error \(\delta\): fraction of CPM-accepted anchors that are factually false (verified against scene graphs). Importantly, \(\delta\) is 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\) but above the confidence threshold), the degraded visual features fed to \(g_\psi\) reduce its discriminative power, inflating \(\delta\). We estimate \(\delta \approx 0.07\) on GQA/CLEVR (where Grounding DINO is most reliable) and \(\delta \approx 0.11\) on VCR (where the  17.3% grounding failure rate at IoU \(\geq 0.5\) compounds with VCR’s noisier constraints). These estimates include all such cascaded error sources.

• Coupling rate \(\gamma\): among instances with a first error at step \(t\), the fraction of subsequent anchors whose ground-truth value is inconsistent with the erroneous step’s proposition. Estimated at \(\gamma \approx 0.72\) (GQA), \(\gamma \approx 0.81\) (CLEVR, where highly structured scenes create tight coupling), and \(\gamma \approx 0.58\) (VCR, where free-form reasoning reduces coupling).

• Recovery failure rate \(\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 \(\varepsilon_{\text{rec}} \approx 0.12\) (GQA), \(\varepsilon_{\text{rec}} \approx 0.08\) (CLEVR), and \(\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 \(\varepsilon_{\text{rec}}\). We disentangle the three failure modes contributing to recovery failure on GQA (\(\varepsilon_{\text{rec}} = 0.12\), \(n = 187\) catch events): (i) re-introduction of a semantically equivalent error accounts for \(p_{\text{reintro}} = 0.065\) (15/23 failures); (ii) retry budget exhaustion without finding any valid continuation accounts for \(p_{\text{exhaust}} = 0.022\) (5/23); and (iii) novel cascading error introduced in the post-backtrack continuation accounts for \(p_{\text{novel}} = 0.013\) (3/23). The per-retry fix probability is \(p_{\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: \(\varepsilon_{\text{rec}} \leq (1 - p_{\text{fix}})^B = (0.49)^3 = 0.118\), consistent with the observed value.

10 Training 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 [9], CLEVR-CoGenT [10], and VCR [11]. For each \((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)\(\to\)relate(_, left)\(\to\)count). We execute each program step to obtain intermediate results and map each step to a constraint in \(\mathcal{L}_c\) using deterministic rule-based templates. For example, the program step filter(scene, color=red) produces the constraint
exists(red_objects) = True; relate(obj_3, left, obj_7) with attribute lookup produces spatial_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 dedicated NLP extraction pipeline:

1. Dependency parsing via spaCy (en_core_web_trf) to extract subject-verb-object triples.

2. Semantic role labeling via AllenNLP’s BERT-based SRL model to identify agent, patient, and spatial/attribute arguments.

3. Template matching: extracted triples are matched against \(\mathcal{L}_c\) predicates using a hand-crafted rule set (78 rules).

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). Measured precision: 78.4%; recall: 65.1%. Primary error modes: failed SRL on complex subordinate clauses (14% of errors), polysemous predicates mapped to wrong \(\mathcal{L}_c\) type (8%), and entity co-reference failures (12%). We filter VCR-derived constraints by a confidence heuristic (SRL confidence \(\geq 0.7\) and template-match uniqueness) and discard instances where fewer than two constraints survive, yielding 28K VCR instances.

Impact of VCR noise on grounding head training. The \(\approx 21.6\%\) error rate in VCR-derived constraints constitutes one-sided label noise: incorrect constraints are false positives (labeled \(y_{t,j} = 1\) but factually incorrect), whereas synthetically generated negatives (see Stage 2 below) are always correctly labeled \(y_{t,j} = 0\). This asymmetry can bias \(g_\psi\) toward accepting certain false constraints, particularly those involving VCR’s more complex relational predicates (e.g., ‘action’). To mitigate this, we apply per-source loss weighting in \(\mathcal{L}_{\text{cst}}\): VCR-derived constraint instances receive weight \(w_{\text{VCR}} = 0.7\) while GQA/CLEVR instances receive weight \(1.0\).

Summary. This procedure yields 218K training 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 \(\mathbf{W}_Q, \mathbf{W}_K, \mathbf{W}_V, \mathbf{W}_O\) in all layers) and train \(g_\psi\) from scratch, jointly optimizing:

\[\mathcal{L} = \mathcal{L}_{\text{task}} + \lambda_c \mathcal{L}_{\text{cst}} + \lambda_b \mathcal{L}_{\text{bt}},\] \[\label{eq:bce-grounding-head} \begin{align} \mathcal{L}_{\text{cst}} &= -\sum_{(t,j) \in \mathcal{A}'}\! w_s \big[y_{t,j} \log g_\psi(c_{t,j}, \mathbf{V})\\ &+ (1{-}y_{t,j})\log(1 {-} g_\psi(c_{t,j}, \mathbf{V}))\big] \end{align}\tag{5}\] \[\label{eq:backtrack-aware-loss} \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)\tag{6}\] where:

• \(\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 5 is the binary cross-entropy for the grounding head with per-source weight \(w_s\) (\(w_s = 0.7\) for VCR, \(w_s = 1.0\) for GQA/CLEVR), where \(\mathcal{A}'\) indexes all anchor positions (including synthetically negated ones) and \(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 6 is the backtrack-aware loss computed 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 continuations \(r_t^{*,\text{alt}}\). We use a two-source mixture. For 70% of backtrack training instances, \(r_t^{*,\text{alt}}\) is the original gold continuation from the last valid checkpoint onward. For the remaining 30%, \(r_t^{*,\text{alt}}\) is a diverse alternative generated by the base MLLM itself (before CART fine-tuning) via nucleus sampling (\(p = 0.9\), temperature \(= 0.8\)) conditioned on the checkpoint prefix plus <RETRY> token, filtered to retain only samples whose final answer matches the ground-truth answer \(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 \(\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 the pre-fine-tuned base model, this randomly initialized embedding provides no 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 a stochastic perturbation on 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 (\(\beta_1=0.9\), \(\beta_2=0.95\), weight decay \(0.05\)) with a cosine learning-rate schedule warming up over 500 steps to a peak of \(2 \times 10^{-5}\) (LLM LoRA parameters) and \(5 \times 10^{-4}\) (grounding head \(g_\psi\)). Training runs for 3 epochs on 8\(\times\)A100-80GB GPUs with DeepSpeed ZeRO-2 [33], effective batch size 128 (gradient accumulation factor 4). Total training time is approximately 18 hours for LLaVA-NeXT-13B [12] and 11 hours for Qwen2-VL-7B.

Stage 3: Grounding Head Calibration. After joint training, we calibrate the grounding head’s threshold \(\tau_v\) using temperature scaling [34] on the held-out GQA-val split, optimizing expected calibration error (ECE). This ensures that \(\tau_v = 0.85\) reliably 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 \(\mathcal{L}_{\text{task}}\) (via the LLM head) and \(\mathcal{L}_{\text{cst}}\) (via the grounding head \(g_\psi\), whose input features are extracted using frozen Grounding DINO boxes). Corrupted-trace samples contribute to \(\mathcal{L}_{\text{bt}}\). All three losses are summed and a single backward pass updates LoRA weights and \(g_\psi\) parameters. Gradients flow through \(g_\psi\) normally; BCP never receives gradients and is used only as a deterministic pre-computation to produce binary consistency labels during training data construction. At inference time, the CPM (both \(g_\psi\) forward pass and BCP) acts as a hard gate (Algorithm 1) with no gradient flow; the backtrack controller is fully deterministic.

References↩︎