# From Chains to DAGs: Probing the Graph Structure of Reasoning in LLMs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 38 of its 55 references that are in the map.
- First posted on arXiv 24 Jan 2026.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 38)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small](https://mlsanity.com/paper/2211.00593/) (2022)
- [Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting](https://mlsanity.com/paper/2305.04388/) (2023)
- [BERT Rediscovers the Classical NLP Pipeline](https://mlsanity.com/paper/1905.05950/) (2019)
- [OpenAI GPT-5 System Card](https://mlsanity.com/paper/2601.03267/) (2025)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Probing Classifiers: Promises, Shortcomings, and Advances](https://mlsanity.com/paper/2102.12452/) (2021)
- [Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned](https://mlsanity.com/paper/1905.09418/) (2019)
- [Discovering Latent Knowledge in Language Models Without Supervision](https://mlsanity.com/paper/2212.03827/) (2022)
- [Measuring Faithfulness in Chain-of-Thought Reasoning](https://mlsanity.com/paper/2307.13702/) (2023)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language](https://mlsanity.com/paper/2012.13048/) (2020)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Analysis Methods in Neural Language Processing: A Survey](https://mlsanity.com/paper/1812.08951/) (2018)
- [LLMs Know More Than They Show: On the Intrinsic Representation of LLM Hallucinations](https://mlsanity.com/paper/2410.02707/) (2024)
- [How does GPT-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model](https://mlsanity.com/paper/2305.00586/) (2023)
- [TACO: Topics in Algorithmic COde generation dataset](https://mlsanity.com/paper/2312.14852/) (2023)
- [Explaining Answers with Entailment Trees](https://mlsanity.com/paper/2104.08661/) (2021)
- [Phi-4-reasoning Technical Report](https://mlsanity.com/paper/2504.21318/) (2025)
- [Why think step by step? Reasoning emerges from the locality of experience](https://mlsanity.com/paper/2304.03843/) (2023)
- [Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization](https://mlsanity.com/paper/2405.15071/) (2024)
- [Iteratively Prompt Pre-trained Language Models for Chain of Thought](https://mlsanity.com/paper/2203.08383/) (2022)
- [Decoding Probing: Revealing Internal Linguistic Structures in Neural Language Models using Minimal Pairs](https://mlsanity.com/paper/2403.17299/) (2024)
- [Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation](https://mlsanity.com/paper/2402.03268/) (2024)

## Built on by (most cited first, 2 of 2)

- [ReasoningFlow: Discourse Structures for Understanding LLM Reasoning Traces](https://mlsanity.com/paper/2606.05402/) (2026)
- [SliceGraph: Mapping Process Isomers in Multi-Run Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.14619/) (2026)

## Abstract (arXiv)

Recent progress in large language models has renewed interest in how multi-step reasoning is represented internally. While prior work often treats reasoning as a linear chain, many reasoning problems can be more naturally modeled as directed acyclic graphs (DAGs), where intermediate conclusions branch, merge, and are reused. Whether such graph structure is reflected in model internals remains unclear. We introduce Reasoning DAG Probing, a framework for testing whether LLM hidden states linearly encode properties of an underlying reasoning DAG. We formalize each premise, intermediate conclusion, and final answer as a DAG node, and train lightweight probes to predict node depth, pairwise distance, and adjacency from hidden states. Using these probes, we analyze the layerwise emergence of DAG structure, reconstruct approximate reasoning graphs, and evaluate controls that disrupt reasoning-relevant structure. Across logical, mathematical, and code reasoning benchmarks, we find that DAG structure is meaningfully encoded in LLM representations: recoverability peaks in intermediate layers; later layers preferentially recover deeper nodes and longer-range dependencies; larger models exhibit stronger DAG recoverability. During autoregressive generation, post-trained models exhibit clearer, progressively strengthening DAG structure, which broadly anticipates answer correctness trends. These findings suggest that LLM reasoning is not purely sequential, but exhibits measurable internal graph structure.