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

CREATORMaya 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
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73087
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.22471

Browse the full library · About the Tower of Babel