Towards an Understanding of Stepwise Inference in Transformers: A Synthetic Graph Navigation Model
Mikail Khona, Maya Okawa, Jan Hula, Rahul Ramesh, Kento Nishi, Robert P. Dick, Ekdeep Singh Lubana, Hidenori Tanaka
Abstract
Stepwise inference protocols, such as scratchpads and chain-of-thought, help language models solve complex problems by decomposing them into a sequence of simpler subproblems. Despite the significant gain in performance achieved via these protocols, the underlying mechanisms of stepwise inference have remained elusive. To address this, we propose to study autoregressive Transformer models on a synthetic task that embodies the multi-step nature of problems where stepwise inference is generally most useful. Specifically, we define a graph navigation problem wherein a model is tasked with traversing a path from a start to a goal node on the graph. Despite is simplicity, we find we can empirically reproduce and analyze several phenomena observed at scale: (i) the stepwise inference reasoning gap, the cause of which we find in the structure of the training data; (ii) a diversity-accuracy tradeoff in model generations as sampling temperature varies; (iii) a simplicity bias in the model's output; and (iv) compositional generalization and a primacy bias with in-context exemplars. Overall, our work introduces a grounded, synthetic framework for studying stepwise inference and offers mechanistic hypotheses that can lay the foundation for a deeper understanding of this phenomenon.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
10 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
- Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Language Models are Few-Shot Learners
- Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Measuring Massive Multitask Language Understanding cites Language Models are Few-Shot Learners
- Deep sequence models tend to memorize geometrically; it is unclear why cites Representation Shattering in Transformers: A Synthetic Study with Knowledge Editing
- Deep sequence models tend to memorize geometrically; it is unclear why cites How do Transformers Learn Implicit Reasoning?
- How do Transformers Learn Implicit Reasoning? cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
- How do Transformers Learn Implicit Reasoning? cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Masked Thought: Simply Masking Partial Reasoning Steps Can Improve Mathematical Reasoning Learning of Language Models cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
- Masked Thought: Simply Masking Partial Reasoning Steps Can Improve Mathematical Reasoning Learning of Language Models cites Measuring Massive Multitask Language Understanding
- Masked Thought: Simply Masking Partial Reasoning Steps Can Improve Mathematical Reasoning Learning of Language Models cites Large Language Models are Zero-Shot Reasoners
- Masked Thought: Simply Masking Partial Reasoning Steps Can Improve Mathematical Reasoning Learning of Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Large Language Models are Zero-Shot Reasoners cites Language Models are Few-Shot Learners
- Large Language Models are Zero-Shot Reasoners cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Cited by top-tier papers10
- How do Transformers Learn Implicit Reasoning?Jiaran Ye, Zijun Yao, Zhidian Huang, Liangming Pan et al.NeurIPS 2025 · 17 citations
- Deep sequence models tend to memorize geometrically; it is unclear whyShahriar Noroozizadeh, Vaishnavh Nagarajan, Elan Rosenfeld, Sanjiv KumarICML 2026 · 11 citations
- Masked Thought: Simply Masking Partial Reasoning Steps Can Improve Mathematical Reasoning Learning of Language ModelsChangyu Chen, Xiting Wang, Ting-En Lin, Ang Lv et al.ACL 2024 · 3 citations
- Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack EfficientlyStanley Wei, Juno KimICML 2026
- Representation Shattering in Transformers: A Synthetic Study with Knowledge EditingKento Nishi, Rahul Ramesh, Maya Okawa, Mikail Khona et al.ICML 2025
Builds on22
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
- Large Language Models are Zero-Shot ReasonersTakeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo et al.NeurIPS 2022 · 8,168 citations
- Measuring Massive Multitask Language UnderstandingDan Hendrycks, Collin Burns, Steven Basart, Andy Zou et al.ICLR 2021 · 7,905 citations
- Tree of Thoughts: Deliberate Problem Solving with Large Language ModelsShunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran et al.NeurIPS 2023 · 5,068 citations
Related papers
- The Expressive Power of Transformers with Chain of ThoughtWilliam Merrill, Ashish SabharwalICLR 2024 · 243 citations
- Faith and Fate: Limits of Transformers on CompositionalityNouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li et al.NeurIPS 2023 · 728 citations
- Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient DescentTong Yang, Yu Huang, Yingbin Liang, Yuejie ChiNeurIPS 2025 · 8 citations
- Exploring Length Generalization in Large Language ModelsCem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz et al.NeurIPS 2022 · 267 citations
- Transformers Learn to Implement Multi-step Gradient Descent with Chain of ThoughtJianhao Huang, Zixuan Wang, Jason D. LeeICLR 2025
