VeryTrace: Verifying Reasoning Traces through Compilable Formalism and Structured Verification

Computer Science > Artificial Intelligence [Submitted on 23 Jun 2026] VeryTrace: Verifying Reasoning Traces through Compilable Formalism and Structured Verification Ninghan Zhong, Ahmet Ege Tanriverdi, Kaan Kale, Sriram Vishwanath Multi-step reasoning with Chain-of-Thought (CoT) prompting remains fragile: logical errors or hallucinations in early steps silently propagate, producing confident but incorrect conclusions. This paper presents VeryTrace, a zero-shot verification-and-repair framework that formalizes natural-language reasoning traces into a structured, compilable representation. VeryTrace introduces a Domain-Specific Language (DSL) that (i) makes step dependencies explicit, (ii) mechanizes quantitative content as executable expressions, and (iii) structures semantic inferences via deduction schemas. Our hybrid verifier combines deterministic checks for computational correctness, dependency resolution, and constraint satisfaction with targeted LLM audits for non-mechanizable semantic judgments, enabling step-level error localization and repair. Across three diverse domains-competition mathematics (AIME 2025), robotics planning (LLM-BabyBench), and kinship reasoning (CLUTRR), VeryTrace improves accuracy over zero-shot baselines on state-of-the-art LLMs without requiring domain-specific training or in-context examples, demonstrating that formalized trace verification achieves both precision and generalization. Comments: Accepted at LM4Plan Workshop @ ICML 2026 Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2606.24124 [cs.AI]   (or arXiv:2606.24124v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2606.24124 Focus to learn more Submission history From: Ninghan Zhong [view email] [v1] Tue, 23 Jun 2026 04:15:48 UTC (584 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)