💬 NLP

Transformers Can Learn Connectivity in Some Graphs but Not Others

This study reveals that while transformer models can effectively learn and generalize transitive connectivity on low-dimensional grid-like graphs through scaling, they struggle to do so on complex graphs with many disconnected components or high-dimensional structures.

Original authors: Amit Roy, Abulhair Saparov

Published 2026-04-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Amit Roy, Abulhair Saparov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a very smart, but literal-minded robot (a Transformer model) how to understand how things are connected. You want it to learn a simple rule: If A leads to B, and B leads to C, then A must lead to C.

This is the same logic used in real life: "If it rains, the ground gets wet. If the ground gets wet, the grass grows. Therefore, if it rains, the grass grows." In the world of computer science, this is called transitive reasoning, and it's basically about figuring out if there is a path between two points on a map.

The paper you shared asks a big question: Can these AI robots learn this rule just by studying examples, and does making the robot "bigger" (more powerful) help it get better at it?

Here is what the researchers discovered, explained through some everyday analogies:

1. The "Neat City" vs. The "Messy Jungle"

The researchers tested the AI on two very different types of maps (graphs).

The Neat City (Grid Graphs): Imagine a city laid out in a perfect grid, like Manhattan. Every street runs straight North-South or East-West. If you know where you are and which way you are facing, you can easily guess where you'll end up.
- The Result: The AI loved this! It learned the rules very quickly. Because the city is so organized, the AI could find a simple "mental shortcut" (a low-dimensional embedding) to understand the connections. It's like the AI realized, "Oh, I just need to count the blocks North and East to know the path."
- The Catch: The more complex the city (e.g., a 3D city with skyscrapers and underground tunnels vs. a flat 2D city), the harder it was for the AI. But as long as the city was "grid-like," the AI could figure it out.
The Messy Jungle (Disconnected Components): Now, imagine a map that isn't a city at all. It's a bunch of isolated islands. Some islands have paths, but many are just floating alone with no bridges to anything else.
- The Result: The AI got completely lost. When the map was full of disconnected pieces, the AI couldn't find a pattern. It's like trying to teach someone the rules of a game where the board changes randomly every turn. No matter how many examples you show them, they can't guess the next move because there is no consistent logic to follow.

2. Does Bigger Mean Better?

The researchers also asked: "If we make the AI brain bigger and give it more computing power, does it get smarter?"

On the Neat City: Yes! The bigger the AI, the better it got at predicting paths. It was like giving a student a bigger library; the more resources they had, the better they could generalize the rules to new, unseen parts of the city.
On the Messy Jungle: No. Even a giant, super-powerful AI struggled here. If the underlying logic of the problem is broken (too many disconnected islands), making the AI smarter doesn't help. You can't teach a robot to find a path that doesn't exist.

The Big Takeaway

This paper tells us that AI isn't magic; it's pattern recognition.

If the world you are trying to understand is organized and logical (like a grid), AI can learn to navigate it perfectly, and bigger models will do even better.
If the world is chaotic and broken (full of dead ends and isolated islands), even the smartest AI will struggle to make sense of it.

So, before we expect AI to solve complex real-world problems (like predicting cause-and-effect in medicine or economics), we need to make sure the data we feed it has a clear, logical structure. If the data is a "messy jungle," the AI might just be guessing in the dark.

1. Problem Statement

The paper addresses a critical gap in understanding the reasoning capabilities of Transformer-based Large Language Models (LLMs), specifically regarding transitive relations and graph connectivity.

Context: Robust reasoning about transitive relations (e.g., if $A \to B$ and $B \to C$ , then $A \to C$ ) is fundamental for tasks like causal inference and ensuring factual correctness in LLM responses.
The Gap: While previous research has investigated whether Transformers can infer transitivity via in-context learning (using examples provided in the prompt), it remains unexplored whether Transformers can learn these relations through training on examples and how model scaling influences this ability.
Core Question: Can Transformers learn to infer connectivity in directed graphs from training data, and does this capability depend on the structural properties of the graphs?

2. Methodology

The authors employed a controlled experimental framework to isolate the effects of graph structure and model scale:

Task Formulation: The task was defined as inferring connectivity in directed graphs. The model must determine if a path exists between two nodes based on training examples of edges.
Data Generation: The researchers generated synthetic directed graphs to serve as training and evaluation datasets. These graphs were categorized into two primary types:
1. Grid-like Graphs: Structured graphs where nodes can be embedded into a low-dimensional subspace, making connectivity inferable from node embeddings.
2. Complex/Disconnected Graphs: Graphs containing many disconnected components and lacking a clear low-dimensional grid structure.
Model Variation: Transformer models of varying sizes (scaling up parameters) were trained on these datasets to evaluate the impact of model scale on generalization.
Evaluation: The models were tested on their ability to generalize connectivity inference across different graph sizes and structural complexities.

3. Key Contributions

Shift from In-Context to Training: The study moves beyond in-context learning to analyze how Transformers learn connectivity through standard training regimes.
Structural Sensitivity: It establishes that the ability of Transformers to learn connectivity is not uniform; it is highly dependent on the underlying topology of the graph.
Dimensionality as a Predictor: The paper identifies the dimensionality of the underlying grid graph as a strong predictor of learning success.
Scaling Laws for Reasoning: It provides empirical evidence on how increasing model scale correlates with improved generalization in specific structural contexts.

4. Key Results

Success on Grid-like Graphs: Transformers demonstrate a strong capability to learn connectivity on "grid-like" directed graphs. In these scenarios, nodes can be effectively embedded in a low-dimensional subspace, allowing the model to infer connectivity directly from these embeddings.
The Dimensionality Challenge: There is a clear inverse relationship between grid dimensionality and learning performance.
- Low-dimensional grids: Models learn connectivity easily.
- High-dimensional grids: Performance degrades significantly as the dimensionality of the grid increases, posing a greater challenge for the architecture.
Scaling Benefits: Increasing the model scale (parameter count) leads to progressively better generalization for connectivity tasks on grid graphs. Larger models handle the complexity of these structures more effectively than smaller ones.
Failure on Disconnected/Complex Graphs: Transformers struggle significantly when the graph is not a grid graph, particularly when the graph contains many disconnected components. As the number of disconnected components increases, the model's ability to learn the connectivity task diminishes, suggesting a fundamental limitation in handling sparse or highly fragmented topological structures.

5. Significance

This research provides crucial insights into the inductive biases of Transformer architectures:

Limitations of Reasoning: It highlights that Transformers are not universally capable of logical reasoning; their success is contingent on the data exhibiting specific structural regularities (like low-dimensional embeddings).
Implications for LLM Safety: Since causal inference and factual consistency rely on transitive reasoning, this study suggests that LLMs may fail in domains where relationships are complex, sparse, or lack clear geometric structure, even with increased scaling.
Future Directions: The findings suggest that improving reasoning capabilities may require architectural changes or training strategies specifically designed to handle high-dimensional or disconnected graph structures, rather than relying solely on scaling laws.