mlsanityData to 14 Oct 2026

Transformers Can Learn Connectivity in Some Graphs but Not Others

arXiv 2509.22343 ↗First posted 26 Sep 2025cs.CL cs.AI cs.LGcited by 0

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Reasoning capability is essential to ensure the factual correctness of the responses of transformer-based Large Language Models (LLMs), and robust reasoning about transitive relations is instrumental in many settings, such as causal inference. Hence, it is essential to investigate the capability of transformers in the task of inferring transitive relations (e.g., knowing A causes B and B causes C, then A causes C). The task of inferring transitive relations is equivalent to the task of connectivity in directed graphs (e.g., knowing there is a path from A to B, and there is a path from B to C, then there is a path from A to C). Past research focused on whether transformers can learn to infer transitivity from in-context examples provided in the input prompt. However, transformers' capability to infer transitive relations from training examples and how scaling affects the ability is unexplored. In this study, we seek to answer this question by generating directed graphs to train transformer models of varying sizes and evaluate their ability to infer transitive relations for various graph sizes. Our findings suggest that transformers are capable of learning connectivity on "grid-like'' directed graphs where each node can be embedded in a low-dimensional subspace, and connectivity is easily inferable from the embeddings of the nodes. We find that the dimensionality of the underlying grid graph is a strong predictor of transformers' ability to learn the connectivity task, where higher-dimensional grid graphs pose a greater challenge than low-dimensional grid graphs. In addition, we observe that increasing the model scale leads to increasingly better generalization to infer connectivity over grid graphs. However, if the graph is not a grid graph and contains many disconnected components, transformers struggle to learn the connectivity task, especially when the number of components is large.

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 25 of its 28 references that are in the map. First posted on arXiv 26 Sep 2025.

Builds on

25 of 28 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithms28 May

Other references · 24

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Scaling Laws for Neural Language Modelscited by 6,586
  3. 2020On Layer Normalization in the Transformer Architecturecited by 922
  4. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 176
  5. 2023Causal Parrots: Large Language Models May Talk Causality But Are Not Causalcited by 150
  6. 2023Can Large Language Models Infer Causation from Correlation?cited by 146
  7. 2023CLadder: Assessing Causal Reasoning in Language Modelscited by 107
  8. 2024Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoningcited by 88
  9. 2024Can LLM Graph Reasoning Generalize beyond Pattern Memorization?cited by 47
  10. 2025Scaling Laws of Synthetic Data for Language Modelscited by 46
  11. 2024Entropy Law: The Story Behind Data Compression and LLM Performancecited by 44
  12. 2025Transformers are Graph Neural Networkscited by 29
12 more
  1. 2024LLMs Are Prone to Fallacies in Causal Inferencecited by 23
  2. 2024Transformers Struggle to Learn to Searchcited by 19
  3. 2023Reasoning in Large Language Models Through Symbolic Math Word Problemscited by 16
  4. 2024gzip Predicts Data-dependent Scaling Lawscited by 16
  5. 2024Teaching Transformers Causal Reasoning through Axiomatic Trainingcited by 12
  6. 2024CausalGraph2LLM: Evaluating LLMs for Causal Queriescited by 12
  7. 2025Compute Optimal Scaling of Skills: Knowledge vs Reasoningcited by 11
  8. 2024Can Large Language Models Act as Symbolic Reasoners?cited by 8
  9. 2025Investigating the Robustness of Deductive Reasoning with Large Language Modelscited by 8
  10. 2025Compute-Optimal LLMs Provably Generalize Better With Scalecited by 5
  11. 2025Code Reasoning for Software Engineering Tasks: A Survey and A Call to Actioncited by 4
  12. 2025An Analysis of Decoding Methods for LLM-based Agents for Faithful Multi-Hop Question Answeringcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Relational reasoning and inductive bias in transformers and large language models
  2. 2025Are Transformers Able to Reason by Connecting Separated Knowledge in Training Data?
  3. 2024Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization
  4. 2026What Structural Inductive Bias Helps Transformers Reason Over Knowledge Graphs? A Study with Tabula RASA
  5. 2024Towards an Understanding of Stepwise Inference in Transformers: A Synthetic Graph Navigation Model
  6. 2024Reasoning in Transformers -- Mitigating Spurious Correlations and Reasoning Shortcuts
  7. 2025Hierarchical Reasoning Models: Perspectives and Misconceptions
  8. 2026Invariant Learning Dynamics of Transformers in Inductive Reasoning Tasks