💻 computer science

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

This paper demonstrates that the choice of graph tokenization fundamentally dictates transformer expressivity and depth requirements by establishing distinct theoretical trade-offs—such as lossiness versus ill-conditioning—among spectral, random-walk, and adjacency representations, while proving that converting between these incompatible views is often impossible for limited-depth models.

Original authors: Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

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 trying to teach a super-smart robot (a Transformer) how to understand a city. The city is a graph: a map of streets (edges) connecting buildings (nodes).

The robot can't look at a map directly; it needs the map translated into a language it understands: a list of tokens (like words in a sentence). This translation process is called Tokenization.

This paper argues that how you translate the map is just as important as the robot's brain itself. Depending on which translation method you choose, the robot might solve a problem instantly, or it might need to think for a very long time (add many layers of depth) to figure it out. In some cases, no matter how smart or deep the robot is, it simply cannot solve the problem because the translation threw away crucial information.

The authors tested three specific ways to translate the city map:

1. The "Street-by-Street" List (Adjacency Tokenization)

The Analogy: Imagine giving the robot a list where, for every building, you write down exactly which other buildings are directly connected to it. "Building A is connected to B, C, and D."
The Good News: This is great for local tasks. If you ask, "Is Building A connected to Building B?" the robot sees it immediately. It's like looking at a street corner; you know exactly who your neighbors are.
The Bad News: If you ask, "Is the whole city connected?" (Can you walk from the North side to the South side without getting lost?), the robot has to do a lot of mental math. It has to hop from neighbor to neighbor, step-by-step, to trace a path across the whole city. The paper proves that for large cities, this method forces the robot to be very "deep" (think many layers) to solve global problems.

2. The "City Blueprint" (Spectral Tokenization)

The Analogy: Instead of listing neighbors, you give the robot a mathematical "blueprint" of the city's shape. This blueprint describes the city's overall geometry, like its vibrations or frequencies. It captures the "big picture" of how the city is put together.
The Good News: The robot can instantly see if the whole city is connected or understand its global shape. It's like looking at a satellite photo; you see the whole layout at once.
The Bad News: This method is terrible for local details. If you ask, "Is there a specific street between Building A and B?", the robot struggles. The math gets messy and unstable (ill-conditioned) when trying to zoom in on tiny details. It's like trying to read a single word by squinting at a blurry satellite photo. Also, if you cut off part of the blueprint to save space (truncation), you might accidentally erase the ability to count specific shapes, like triangles of streets.

3. The "Tourist's Walk" (Random-Walk Tokenization)

The Analogy: Imagine a tourist starting at a building and wandering around randomly. You give the robot a report on how likely the tourist is to return to the starting building after 1 step, 2 steps, 3 steps, etc.
The Good News: This is amazing for spotting loops. If you ask, "Can you walk in a circle and come back to the start?" the robot sees the answer immediately because the report literally lists the return probabilities.
The Bad News: This method is lossy. It throws away information. The paper proves that two completely different city layouts (one that can be drawn on a flat map, and one that cannot) can produce the exact same tourist report. No matter how smart the robot is, it cannot tell the difference between these two cities because the translation erased the crucial detail. It's like trying to identify a person only by their shoe size; many different people have the same shoe size.

The Big Takeaways

1. You Can't Just "Fix" a Bad Translation
You might think, "If I give the robot the 'Street-by-Street' list, can't it just learn to turn it into the 'City Blueprint' inside its brain?"
The paper says no. If the robot is limited in size (depth), it cannot convert one translation style into another. If you start with a "Tourist's Walk" report, the robot can never recover the full map, no matter how much it thinks. The information is gone forever.

2. Different Jobs Need Different Maps

Need to find a specific neighbor? Use the Street-by-Street list.
Need to understand the whole city's shape? Use the City Blueprint.
Need to find loops? Use the Tourist's Walk.
Trying to use one map for everything makes the robot inefficient or unable to solve the problem.

3. The "Best" Solution is a Mix
In their experiments, the authors found that when they gave the robot all three translations at once, it performed the best. It could use the "Street" list for local details and the "Blueprint" for global shape, combining the strengths of each view.

Summary

The paper concludes that Tokenization is not just a boring first step; it is a fundamental part of the robot's intelligence. Choosing the wrong translation method creates a "bottleneck" that no amount of extra computing power can easily fix. To build the best graph-learning AI, you must choose the translation method that matches the specific question you are asking.

Technical Summary: Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Problem Statement

Transformers have emerged as a powerful architecture for graph learning, yet their application to graph-structured data requires a preliminary step: tokenization. Unlike sequences or grids, graphs lack a canonical continuous input format. Consequently, a graph-to-token map must be chosen to determine which structural information is exposed to the model at the input layer.

While various tokenization strategies exist (e.g., spectral, random-walk, adjacency), they are often treated as empirical design choices or preprocessing details. This paper posits that the choice of tokenization is a fundamental component of transformer expressivity. The central problem addressed is whether different tokenizations are interchangeable or if they induce distinct computational regimes, specifically regarding the depth required to solve graph tasks and the ability to recover structural information.

Methodology

The authors formalize graph tokenization as an integral part of the computational model, analyzing the expressivity of Transformers with finite depth ( $L$ ), width ( $m$ ), and precision ( $p$ ) under three primary tokenization families:

Adjacency Tokenization: Encodes the local connectivity of each node via its adjacency row. It is lossless but exposes only local structure.
Spectral (Laplacian) Tokenization: Derives tokens from the eigendecomposition of the graph Laplacian ( $L = D - A$ ). It captures global topological properties but is permutation-equivariant.
Random-Walk Tokenization: Encodes return probabilities of random walks of length $1$ to $t(n)$ . It captures diffusion patterns but is inherently lossy.

The methodology combines complexity-theoretic analysis with controlled experiments.

Theoretical Analysis: The authors establish lower bounds and impossibility results by mapping graph tasks to complexity classes (e.g., $TC^0$ , $NC^1$ , $L$ ). They analyze how specific tasks (e.g., $k$ -closed-walk detection, connectivity, triangle counting, planarity) behave under different tokenizations, considering the constraints of finite depth and the mathematical properties of the token representations (e.g., condition numbers, information loss).
Empirical Validation: Experiments are conducted on synthetic tasks (validating depth separations) and real-world benchmarks (GraphBench, Open Graph Benchmark, ZINC). The study evaluates Transformers using full and truncated versions of each tokenization, as well as combined tokenizations, comparing performance against DeepSet and GIN baselines.

Key Contributions

1. Formalization of Tokenization as a Computational Constraint

The paper formalizes how the input representation constrains transformer expressivity at finite depth. It demonstrates that tokenization is not merely a feature engineering step but a determinant of which structural dependencies are accessible to the model.

2. Depth Separations Between Tokenizations

The authors prove that the same graph computation may require vastly different depths depending on the tokenization:

Random-Walk vs. Adjacency: Detecting a $k$ -closed-walk is solvable in $O(1)$ depth with Random-Walk tokenization (as statistics are explicit) but requires $\Omega(\log k)$ depth with Adjacency tokenization. This is proven via a reduction from the word problem on the permutation group $S_5$ (an $NC^1$ -complete problem) to graph topology, showing that constant-depth Transformers ( $TC^0$ ) cannot simulate the sequential path traversal required by Adjacency tokens.
Adjacency vs. Spectral: Solving global graph connectivity requires $\Omega(\log n)$ depth with Adjacency tokenization, whereas Spectral tokenization solves it in $O(1)$ depth.

3. Intrinsic Limitations and Lossiness

Random-Walk is Provably Lossy: Regardless of walk length, Random-Walk tokenization cannot determine graph planarity. The authors construct planar and non-planar graphs with identical Random-Walk distributions using Godsil-McKay (GM) switching, proving that no Transformer depth or width can recover the topological distinction.
Spectral Truncation is Brittle: Truncating the Laplacian spectrum (even by a single eigenvalue) can render triangle counting impossible. The authors show that adding an edge between symmetric nodes changes only one eigenvalue; if this eigenvalue is truncated, the transformer cannot distinguish the graphs.
Adjacency Truncation: Truncating the dimension of adjacency tokens (via random projection) destroys the capacity to solve tasks like triangle counting, as proven via communication complexity lower bounds (Set Disjointness).

4. Ill-Conditioning of Spectral Tokenization for Local Tasks

While Spectral tokenization captures global topology, it is mathematically ill-conditioned for local tasks like edge prediction. The paper derives a lower bound showing that the parameter norms required to decode a local edge from a global spectrum scale with the maximum degree ( $d_{max}$ ). This forces a trade-off: either the model suffers from Softmax saturation (vanishing gradients) or requires exploding weights, making optimization difficult.

5. Impossibility of Conversion at Limited Depth

The paper establishes that converting between tokenization families is generally impossible at limited depth.

A Transformer cannot efficiently convert Adjacency tokens to Random-Walk statistics (requires $\Omega(\log k)$ depth).
A Transformer cannot recover full Adjacency or Laplacian representations from Random-Walk tokens (due to information loss).
Converting between global (Spectral) and local (Adjacency) views incurs severe computational bottlenecks or optimization instability.

Results

Theoretical Findings:

Depth Separations: Empirical validation confirms that Spectral tokenization solves connectivity tasks with $L=1$ across all graph sizes, while Adjacency tokenization collapses to chance performance for larger graphs ( $n \ge 128$ ).
Recovery Limits: When training a Transformer to predict Random-Walk return probabilities from Adjacency tokens, the error grows with walk length $k$ , consistent with the $\Omega(\log k)$ depth requirement.
Planarity: Models using Random-Walk tokens fail to distinguish planar from non-planar graphs, even with increased depth, confirming the theoretical impossibility result.

Empirical Findings:

Task Dependency: No single tokenization dominates.
- Local Tasks: Adjacency tokenization performs best on tasks governed by explicit local constraints (e.g., Max Clique, Topological Ordering).
- Global Tasks: Spectral (Laplacian) tokenization performs best on tasks dependent on global geometry (e.g., Tox21 molecular property prediction).
- Combined Approach: Combining complementary tokenizations (Adjacency + Spectral + Random-Walk) often yields the best performance, allowing the model to leverage distinct structural signals.
Truncation Effects: Truncated tokenizations generally degrade performance, particularly for tasks requiring exact structural recovery (e.g., triangle counting), validating the theoretical "brittleness" of truncation.

Significance and Claims

The paper claims that graph tokenization is a fundamental trade-off rather than a preprocessing detail. The choice of tokenization dictates the "view" of the graph the transformer receives, thereby constraining the class of structural dependencies the model can express at finite depth.

Key takeaways emphasized by the authors include:

Non-Interchangeability: Adjacency, Spectral, and Random-Walk tokenizations are not interchangeable; they induce distinct depth regimes and expressivity limits.
Inherent Limitations: Specific tokenizations have provable blind spots (e.g., Random-Walk cannot see planarity; Spectral is ill-conditioned for local edges).
Conversion Barriers: Transformers cannot simply "learn" to convert between these representations efficiently if the initial tokenization is unfavorable; the depth required to bridge these gaps may be prohibitive.
Practical Implication: The optimal tokenization depends on the structural nature of the downstream task. Combining complementary views is a robust strategy to overcome the limitations of any single representation.

The authors conclude that while their analysis focuses on node-level tokenizations, the findings suggest a broader principle: the input representation is a critical axis of complexity in graph learning, and future work should explore optimization challenges and edge-level tokenizations.