# Generating Verifiable Chain of Thoughts from Exection-Traces

arXiv: https://arxiv.org/abs/2512.00127 · HTML: https://mlsanity.com/paper/2512.00127/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 26 of its 32 references that are in the map.
- First posted on arXiv 28 Nov 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 26 of 26)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting](https://mlsanity.com/paper/2305.04388/) (2023)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [StarCoder: may the source be with you!](https://mlsanity.com/paper/2305.06161/) (2023)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [Magicoder: Empowering Code Generation with OSS-Instruct](https://mlsanity.com/paper/2312.02120/) (2023)
- [Granite Code Models: A Family of Open Foundation Models for Code Intelligence](https://mlsanity.com/paper/2405.04324/) (2024)
- [NExT: Teaching Large Language Models to Reason about Code Execution](https://mlsanity.com/paper/2404.14662/) (2024)
- [CodeI/O: Condensing Reasoning Patterns via Code Input-Output Prediction](https://mlsanity.com/paper/2502.07316/) (2025)
- [rStar-Coder: Scaling Competitive Code Reasoning with a Large-Scale Verified Dataset](https://mlsanity.com/paper/2505.21297/) (2025)
- [Forward-Backward Reasoning in Large Language Models for Mathematical Verification](https://mlsanity.com/paper/2308.07758/) (2023)
- [Reverse Thinking Makes LLMs Stronger Reasoners](https://mlsanity.com/paper/2411.19865/) (2024)
- [TRACED: Execution-aware Pre-training for Source Code](https://mlsanity.com/paper/2306.07487/) (2023)
- [SemCoder: Training Code Language Models with Comprehensive Semantics Reasoning](https://mlsanity.com/paper/2406.01006/) (2024)
- [What I cannot execute, I do not understand: Training and Evaluating LLMs on Program Execution Traces](https://mlsanity.com/paper/2503.05703/) (2025)
- [Code Execution as Grounded Supervision for LLM Reasoning](https://mlsanity.com/paper/2506.10343/) (2025)

## Abstract (arXiv)

Getting language models to reason correctly about code requires training on data where each reasoning step can be checked. Current synthetic Chain-of-Thought (CoT) training data often consists of plausible-sounding explanations generated by teacher models, and not verifiable accounts of actual program behavior. Models trained on such data learn logically flawed reasoning patterns despite syntactic correctness. To address this, we build a pipeline that generates execution-trace-verified CoT rationales by instrumenting code to capture traces, narrating them into natural language, and cross-checking each narration against the original trace. We systematically create 54,000 verified, bi-directional rationales that teach models to reason both forward (inputrightarrowoutput) and backward (outputrightarrowinput). Models fine-tuned on our verified data achieve substantial improvements, with a peak gain of +26.6 on LiveCodeBench-Exec, +22.2 on CruxEval, and +19.5 on HumanEval across our fine-tuned models, demonstrating that verification quality directly determines both reasoning and code generation capabilities. Complete synthesis pipeline is avilable as open-source: https://github.com/IBM/verified-code-cot/