# Transformers Can Learn Connectivity in Some Graphs but Not Others

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

## 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.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [Causal Parrots: Large Language Models May Talk Causality But Are Not Causal](https://mlsanity.com/paper/2308.13067/) (2023)
- [Can Large Language Models Infer Causation from Correlation?](https://mlsanity.com/paper/2306.05836/) (2023)
- [CLadder: Assessing Causal Reasoning in Language Models](https://mlsanity.com/paper/2312.04350/) (2023)
- [Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning](https://mlsanity.com/paper/2406.09170/) (2024)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [Can LLM Graph Reasoning Generalize beyond Pattern Memorization?](https://mlsanity.com/paper/2406.15992/) (2024)
- [Scaling Laws of Synthetic Data for Language Models](https://mlsanity.com/paper/2503.19551/) (2025)
- [Entropy Law: The Story Behind Data Compression and LLM Performance](https://mlsanity.com/paper/2407.06645/) (2024)
- [Transformers are Graph Neural Networks](https://mlsanity.com/paper/2506.22084/) (2025)
- [LLMs Are Prone to Fallacies in Causal Inference](https://mlsanity.com/paper/2406.12158/) (2024)
- [Transformers Struggle to Learn to Search](https://mlsanity.com/paper/2412.04703/) (2024)
- [Reasoning in Large Language Models Through Symbolic Math Word Problems](https://mlsanity.com/paper/2308.01906/) (2023)
- [gzip Predicts Data-dependent Scaling Laws](https://mlsanity.com/paper/2405.16684/) (2024)
- [Teaching Transformers Causal Reasoning through Axiomatic Training](https://mlsanity.com/paper/2407.07612/) (2024)
- [CausalGraph2LLM: Evaluating LLMs for Causal Queries](https://mlsanity.com/paper/2410.15939/) (2024)
- [Compute Optimal Scaling of Skills: Knowledge vs Reasoning](https://mlsanity.com/paper/2503.10061/) (2025)
- [Can Large Language Models Act as Symbolic Reasoners?](https://mlsanity.com/paper/2410.21490/) (2024)
- [Investigating the Robustness of Deductive Reasoning with Large Language Models](https://mlsanity.com/paper/2502.04352/) (2025)
- [Compute-Optimal LLMs Provably Generalize Better With Scale](https://mlsanity.com/paper/2504.15208/) (2025)
- [Code Reasoning for Software Engineering Tasks: A Survey and A Call to Action](https://mlsanity.com/paper/2506.13932/) (2025)
- [An Analysis of Decoding Methods for LLM-based Agents for Faithful Multi-Hop Question Answering](https://mlsanity.com/paper/2503.23415/) (2025)

## 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.