Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing

• URL: http://arxiv.org/abs/2509.20336v1
• Date: Wed, 24 Sep 2025 17:25:05 GMT
• Title: Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing
• Authors: Xinnan Dai, Chung-Hsiang Lo, Kai Guo, Shenglai Zeng, Dongsheng Luo, Jiliang Tang,
• Abstract summary: We set the basic decoder-only transformers and explain them using the circuit-tracer framework.<n>We visualize reasoning traces and identify two core mechanisms in graph reasoning: token merging and structural memorization.<n>Our study provides a unified interpretability framework for understanding structural reasoning in decoder-only Transformers.
• Score: 44.121903032922376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformer-based LLMs demonstrate strong performance on graph reasoning tasks, yet their internal mechanisms remain underexplored. To uncover these reasoning process mechanisms in a fundamental and unified view, we set the basic decoder-only transformers and explain them using the circuit-tracer framework. Through this lens, we visualize reasoning traces and identify two core mechanisms in graph reasoning: token merging and structural memorization, which underlie both path reasoning and substructure extraction tasks. We further quantify these behaviors and analyze how they are influenced by graph density and model size. Our study provides a unified interpretability framework for understanding structural reasoning in decoder-only Transformers.

Related papers

• Attention as Binding: A Vector-Symbolic Perspective on Transformer Reasoning [0.0]
  Transformer-based language models display impressive reasoning-like behavior, yet remain brittle on tasks that require stable symbolic manipulation.<n>This paper develops a unified perspective on these phenomena by interpreting self-attention and residual streams as implementing an approximate Vector Symbolic Architecture (VSA)<n>In this view, queries and keys define role spaces, values encode fillers, attention weights perform soft unbinding, and residual connections realize superposition of many bound structures.
  arXiv  Detail & Related papers  (2025-12-08T05:38:24Z)
• 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)
• Selective Induction Heads: How Transformers Select Causal Structures In Context [50.09964990342878]
  We introduce a novel framework that showcases transformers' ability to handle causal structures.<n>Our framework varies the causal structure through interleaved Markov chains with different lags while keeping the transition probabilities fixed.<n>This setting unveils the formation of Selective Induction Heads, a new circuit that endows transformers with the ability to select the correct causal structure in-context.
  arXiv  Detail & Related papers  (2025-09-09T23:13:41Z)
• Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent [66.78052387054593]
  This work investigates how transformers learn to solve symbolic multi-step reasoning problems through chain-of-thought processes.<n>We analyze two intertwined tasks: a backward reasoning task, where the model outputs a path from a goal node to the root, and a more complex forward reasoning task.<n>We show that trained one-layer transformers can provably solve both tasks with generalization guarantees to unseen trees.
  arXiv  Detail & Related papers  (2025-08-11T17:40:47Z)
• From Sequence to Structure: Uncovering Substructure Reasoning in Transformers [35.80526987002848]
  We show how a decoder-only Transformer architecture can understand underlying graph structures.<n>We introduce the concept of thinking in substructures to efficiently extract complex composite patterns.<n>Our findings offer a new insight on how sequence-based Transformers perform the substructure extraction task over graph data.
  arXiv  Detail & Related papers  (2025-07-11T17:36:24Z)
• How do Transformers Learn Implicit Reasoning? [67.02072851088637]
  We study how implicit multi-hop reasoning emerges by training transformers from scratch in a controlled symbolic environment.<n>We find that training with atomic triples is not necessary but accelerates learning, and that second-hop generalization relies on query-level exposure to specific compositional structures.
  arXiv  Detail & Related papers  (2025-05-29T17:02:49Z)
• Mechanistic Unveiling of Transformer Circuits: Self-Influence as a Key to Model Reasoning [9.795934690403374]
  It is still unclear which multi-step reasoning mechanisms are used by language models to solve such tasks.<n>We employ circuit analysis and self-influence functions to evaluate the changing importance of each token throughout the reasoning process.<n>We demonstrate that the underlying circuits reveal a human-interpretable reasoning process used by the model.
  arXiv  Detail & Related papers  (2025-02-13T07:19:05Z)
• Enhancing Transformers for Generalizable First-Order Logical Entailment [51.04944136538266]
  This paper studies the generalizable first-order logical reasoning ability of transformers with their parameterized knowledge.<n>We propose TEGA, a logic-aware architecture that significantly improves the performance in first-order logical entailment.
  arXiv  Detail & Related papers  (2025-01-01T07:05:32Z)
• Understanding the Language Model to Solve the Symbolic Multi-Step Reasoning Problem from the Perspective of Buffer Mechanism [68.05754701230039]
  We construct a symbolic multi-step reasoning task to investigate the information propagation mechanisms in Transformer models.<n>We propose a random matrix-based algorithm to enhance the model's reasoning ability.
  arXiv  Detail & Related papers  (2024-05-24T07:41:26Z)
• How Transformers Learn Causal Structure with Gradient Descent [44.31729147722701]
  Self-attention allows transformers to encode causal structure. We introduce an in-context learning task that requires learning latent causal structure. We show that transformers trained on our in-context learning task are able to recover a wide variety of causal structures.
  arXiv  Detail & Related papers  (2024-02-22T17:47:03Z)
• A Mechanistic Analysis of a Transformer Trained on a Symbolic Multi-Step Reasoning Task [14.921790126851008]
  We present a comprehensive mechanistic analysis of a transformer trained on a synthetic reasoning task. We identify a set of interpretable mechanisms the model uses to solve the task, and validate our findings using correlational and causal evidence.
  arXiv  Detail & Related papers  (2024-02-19T08:04:25Z)
• Signal Propagation in Transformers: Theoretical Perspectives and the Role of Rank Collapse [11.486545294602697]
  We shed new light on the causes and effects of rank collapse in Transformers. We show that rank collapse of the tokens' representations hinders training by causing the gradients of the queries and keys to vanish.
  arXiv  Detail & Related papers  (2022-06-07T09:07:24Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.