# Structural Chain-of-Thought: Reasoning with Executable Computational Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 26 references that are in the map.
- First posted on arXiv 10 Oct 2026.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [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)
- [Towards Faithfully Interpretable NLP Systems: How should we define and evaluate faithfulness?](https://mlsanity.com/paper/2004.03685/) (2020)
- [Monitoring Reasoning Models for Misbehavior and the Risks of Promoting Obfuscation](https://mlsanity.com/paper/2503.11926/) (2025)
- [ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language](https://mlsanity.com/paper/2012.13048/) (2020)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters](https://mlsanity.com/paper/2212.10001/) (2022)
- [Explaining Answers with Entailment Trees](https://mlsanity.com/paper/2104.08661/) (2021)
- [What do we need to build explainable AI systems for the medical domain?](https://mlsanity.com/paper/1712.09923/) (2017)
- [Measuring Chain of Thought Faithfulness by Unlearning Reasoning Steps](https://mlsanity.com/paper/2502.14829/) (2025)
- [Learning to Generate Structured Output with Schema Reinforcement Learning](https://mlsanity.com/paper/2502.18878/) (2025)
- [Natural Language Inference from Multiple Premises](https://mlsanity.com/paper/1710.02925/) (2017)
- [RFEval: Benchmarking Reasoning Faithfulness under Counterfactual Reasoning Intervention in Large Reasoning Models](https://mlsanity.com/paper/2602.17053/) (2026)
- [Detecting Data Contamination in LLMs via In-Context Learning](https://mlsanity.com/paper/2510.27055/) (2025)
- [Breaking the Chain: A Causal Analysis of LLM Faithfulness to Intermediate Structures](https://mlsanity.com/paper/2603.16475/) (2026)
- [RL-Struct: A Lightweight Reinforcement Learning Framework for Reliable Structured Output in LLMs](https://mlsanity.com/paper/2512.00319/) (2025)

## Abstract (arXiv)

Chain-of-thought prompting enables reasoning in large language models but produces explanations that are difficult to verify, expensive to generate, and not always faithful. We introduce a Structural Chain-of-Thought framework where models generate executable computational graphs instead of free-form reasoning. The final answer is obtained by deterministically executing the graph. The model is trained using graph-based reinforcement learning that rewards structural validity, answer correctness, and node overlap with reference graphs. Experiments across five benchmarks and four model families show that our method consistently improves accuracy over supervised graph training and can reduce generation length by up to 5-6x compared with standard GRPO and chain-of-thought supervised training. Our faithfulness experiments reveal that models trained with our approach tend to rely on deriving their answers from the generated graphs rather than producing post-hoc rationalizations as usually in chain-of-thought reasoning.