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

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

URL: http://arxiv.org/abs/2601.17593v1
Date: Sat, 24 Jan 2026 21:11:51 GMT
Title: From Chains to DAGs: Probing the Graph Structure of Reasoning in LLMs
Authors: Tianjun Zhong, Linyang He, Nima Mesgarani,
Abstract summary: We introduce Reasoning DAG Probing, a framework that asks whether reasoning DAG geometry is encoded in model internals.<n>We use these probes to analyze the layerwise emergence of DAG structure and evaluate controls that disrupt reasoning-relevant structure.<n>Our results provide evidence that reasoning DAG geometry is meaningfully encoded in intermediate layers, with recoverability varying systematically by node depth and model scale.
Score: 14.863369207533966
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Recent progress in large language models has renewed interest in mechanistically characterizing how multi-step reasoning is represented and computed. While much prior work treats reasoning as a linear chain of steps, many reasoning problems are more naturally structured as directed acyclic graphs (DAGs), where intermediate conclusions may depend on multiple premises, branch into parallel sub-derivations, and later merge or be reused. Understanding whether such graph-structured reasoning is reflected in model internals remains an open question. In this work, we introduce Reasoning DAG Probing, a framework that directly asks whether LLM hidden states encode the geometry of a reasoning DAG in a linearly accessible form, and where this structure emerges across layers. Within this framework, we associate each reasoning node with a textual realization and train lightweight probes to predict two graph-theoretic properties from hidden states: node depth and pairwise node distance. We use these probes to analyze the layerwise emergence of DAG structure and evaluate controls that disrupt reasoning-relevant structure while preserving superficial textual properties. Our results provide evidence that reasoning DAG geometry is meaningfully encoded in intermediate layers, with recoverability varying systematically by node depth and model scale, suggesting that LLM reasoning is not only sequential but exhibits measurable internal graph structure.

Related papers

On Multi-Step Theorem Prediction via Non-Parametric Structural Priors [50.16583672681106]
In this work, we explore training-free theorem prediction through the lens of in-context learning (ICL)<n>We propose Theorem Precedence Graphs, which encode temporal dependencies from historical solution traces as directed graphs, and impose explicit topological constraints that effectively prune the search space during inference.<n>Experiments on the FormalGeo7k benchmark show that our method achieves 89.29% accuracy, substantially outperforming ICL baselines and matching state-of-the-art supervised models.
arXiv Detail & Related papers (2026-03-05T06:08:50Z)
Topology of Reasoning: Retrieved Cell Complex-Augmented Generation for Textual Graph Question Answering [13.616604189732262]
Topology-enhanced Retrieval-Augmented Generation (TopoRAG) is a novel framework for textual graph question answering.<n>TopoRAG first lifts textual graphs into cellular complexes to model multi-dimensional topological structures.<n>A multi-dimensional topological reasoning mechanism operates over these complexes to propagate relational information.
arXiv Detail & Related papers (2026-02-22T15:44:53Z)
From Chains to Graphs: Self-Structured Reasoning for General-Domain LLMs [52.0811904328273]
Real-world reasoning requires integrating multiple premises and solving subproblems in parallel.<n>Recent approaches rely on externally provided graphs and do not explore how LLMs can construct and use their own graph-structured reasoning.<n>We propose Self-Graph Reasoning (SGR), a framework that enables LLMs to explicitly represent their reasoning process as a structured graph before producing the final answer.
arXiv Detail & Related papers (2026-01-07T05:27:41Z)
DAG-Math: Graph-Guided Mathematical Reasoning in LLMs [54.231935013127206]
Large Language Models (LLMs) demonstrate strong performance on mathematical problems when prompted with Chain-of-Thought (CoT)<n>We propose modeling CoT as a certain rule-based process over directed acyclic graphs (DAGs)<n>We introduce logical closeness, a metric that quantifies how well a model's CoT trajectory adheres to the DAG structure.
arXiv Detail & Related papers (2025-10-19T21:05:17Z)
GraphGhost: Tracing Structures Behind Large Language Models [48.8586898059844]
We introduce GraphGhost, a unified framework that represents neuron activations and their signal propagation as graphs.<n>This graph-based perspective enables us to employ graph algorithms such as PageRank to characterize the properties of Large Language Models.<n>We show that edits to key neuron nodes can trigger reasoning collapse, altering both logical flow and semantic understanding.
arXiv Detail & Related papers (2025-10-07T20:28:19Z)
You Don't Need Pre-built Graphs for RAG: Retrieval Augmented Generation with Adaptive Reasoning Structures [16.867592142212203]
Large language models (LLMs) often suffer from hallucination, generating factually incorrect statements when handling questions beyond their knowledge.<n>Retrieval-augmented generation (RAG) addresses this by retrieving query-relevant contexts from knowledge bases to support LLM reasoning.<n>Existing Graph-based RAG methods rely on a costly process to transform the corpus into a graph, introducing overwhelming token cost and update latency.<n>We propose LogicRAG that dynamically extracts reasoning structures at inference time to guide adaptive retrieval without any pre-built graph.
arXiv Detail & Related papers (2025-08-08T08:07:40Z)
KisMATH: Do LLMs Have Knowledge of Implicit Structures in Mathematical Reasoning? [4.473915603131591]
Chain-of-thought traces have been shown to improve performance of large language models in a plethora of reasoning tasks.<n>We introduce Causal CoT Graphs (CCGs), which are directed acyclic graphs automatically extracted from reasoning traces.
arXiv Detail & Related papers (2025-07-15T15:28:37Z)
GRS-QA -- Graph Reasoning-Structured Question Answering Dataset [50.223851616680754]
We introduce the Graph Reasoning-Structured Question Answering dataset (GRS-QA), which includes both semantic contexts and reasoning structures for QA pairs. Unlike existing M-QA datasets, GRS-QA explicitly captures intricate reasoning pathways by constructing reasoning graphs. Our empirical analysis reveals that LLMs perform differently when handling questions with varying reasoning structures.
arXiv Detail & Related papers (2024-11-01T05:14:03Z)
Contextual Directed Acyclic Graphs [9.617105933121108]
Estimating the structure of directed acyclic graphs (DAGs) from observational data remains a significant challenge in machine learning. This paper considers an alternative setting where the graph structure varies across individuals based on available "contextual" features. We tackle this contextual DAG problem via a neural network that maps the contextual features to a DAG, represented as a weighted adjacency matrix.
arXiv Detail & Related papers (2023-10-24T08:52:04Z)
OrthoReg: Improving Graph-regularized MLPs via Orthogonality Regularization [66.30021126251725]
Graph Neural Networks (GNNs) are currently dominating in modeling graphstructure data. Graph-regularized networks (GR-MLPs) implicitly inject the graph structure information into model weights, while their performance can hardly match that of GNNs in most tasks. We show that GR-MLPs suffer from dimensional collapse, a phenomenon in which the largest a few eigenvalues dominate the embedding space. We propose OrthoReg, a novel GR-MLP model to mitigate the dimensional collapse issue.
arXiv Detail & Related papers (2023-01-31T21:20:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.