Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
Maya Bechler-SpeicherMeta [email protected], Gilad YehudaiCourant Institute of Mathematical Sciences,New York UniversityGil HarariJohn A. Paulson School of Engineering and Applied Sciences,Harvard UniversityClayton SanfordGoogle ResearchAmir GlobersonGoogle ResearchTel-Aviv UniversityJoan BrunaCourant Institute of Mathematical Sciences,New York University · 2026
Read Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers by Maya Bechler-SpeicherMeta [email protected], Gilad YehudaiCourant Institute of Mathematical Sciences,New York UniversityGil HarariJohn A. Paulson School of Engineering and Applied Sciences,Harvard UniversityClayton SanfordGoogle ResearchAmir GlobersonGoogle ResearchTel-Aviv UniversityJoan BrunaCourant Institute of Mathematical Sciences,New York University (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22471.txt.
Description
Bechler-Speicher and colleagues show that tokenization choice shapes transformer power. Three choices serve as building blocks: spectral, random-walk and adjacency. Different choices induce distinct depth regimes: one computation may need a shallow transformer under one and far greater depth under another. Random-walk tokenization is lossy for any walk length, so the graph cannot be recovered from it. Spectral tokenization is lossless but ill-conditioned locally. Limited-depth transformers cannot convert between families. Experiments confirm the separations, and combining choices uses distinct signals from each view.
Catalog record
| CREATOR | Maya Bechler-SpeicherMeta [email protected], Gilad YehudaiCourant Institute of Mathematical Sciences,New York UniversityGil HarariJohn A. Paulson School of Engineering and Applied Sciences,Harvard UniversityClayton SanfordGoogle ResearchAmir GlobersonGoogle ResearchTel-Aviv UniversityJoan BrunaCourant Institute of Mathematical Sciences,New York University |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73087 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22471