💻 computer science

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

Dieser Artikel zeigt, dass die Wahl der Graph-Tokenisierung die Ausdrucksstärke und die Anforderungen an die Tiefe von Transformern grundlegend bestimmt, indem er unterschiedliche theoretische Zielkonflikte – wie etwa den Verlust von Informationen versus eine schlechte Konditionierung – zwischen spektralen, Zufallswege- und Adjazenz-Repräsentationen aufzeigt, während er gleichzeitig beweist, dass die Umwandlung zwischen diesen unvereinbaren Perspektiven für Modelle mit begrenzter Tiefe oft unmöglich ist.

Ursprüngliche Autoren: Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

Veröffentlicht 2026-05-22

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einem superschlauen Roboter (einem Transformer) beizubringen, eine Stadt zu verstehen. Die Stadt ist ein Graph: eine Karte von Straßen (Kanten), die Gebäude (Knoten) miteinander verbinden.

Der Roboter kann die Karte nicht direkt betrachten; er benötigt die Karte in einer Sprache übersetzt, die er versteht: eine Liste von Tokens (wie Wörter in einem Satz). Dieser Übersetzungsprozess wird Tokenisierung genannt.

Diese Arbeit argumentiert, dass wie Sie die Karte übersetzen, genauso wichtig ist wie das Gehirn des Roboters selbst. Je nachdem, welche Übersetzungsmethode Sie wählen, kann der Roboter ein Problem sofort lösen, oder er muss sehr lange nachdenken (viele Schichten der Tiefe hinzufügen), um es zu verstehen. In einigen Fällen kann der Roboter das Problem einfach nicht lösen, egal wie schlau oder tief er ist, weil die Übersetzung entscheidende Informationen verworfen hat.

Die Autoren testeten drei spezifische Möglichkeiten, die Stadtkarte zu übersetzen:

1. Die „Straßen-für-Straßen"-Liste (Adjazenz-Tokenisierung)

Die Analogie: Stellen Sie sich vor, Sie geben dem Roboter eine Liste, in der Sie für jedes Gebäude genau aufschreiben, welche anderen Gebäude direkt damit verbunden sind. „Gebäude A ist mit B, C und D verbunden."
Die gute Nachricht: Dies ist hervorragend für lokale Aufgaben. Wenn Sie fragen: „Ist Gebäude A mit Gebäude B verbunden?", sieht der Roboter es sofort. Es ist wie das Betrachten einer Straßenecke; Sie wissen genau, wer Ihre Nachbarn sind.
Die schlechte Nachricht: Wenn Sie fragen: „Ist die ganze Stadt verbunden?" (Können Sie von der Nordseite zur Südseite gehen, ohne sich zu verirren?), muss der Roboter viel Kopfrechnen betreiben. Er muss von Nachbar zu Nachbar springen, Schritt für Schritt, um einen Pfad über die ganze Stadt zu verfolgen. Die Arbeit beweist, dass diese Methode für große Städte den Roboter zwingt, sehr „tief" zu sein (viele Schichten zu denken), um globale Probleme zu lösen.

2. Der „Stadt-Grundriss" (Spektrale Tokenisierung)

Die Analogie: Anstatt Nachbarn aufzulisten, geben Sie dem Roboter einen mathematischen „Grundriss" der Form der Stadt. Dieser Grundriss beschreibt die Gesamtgeometrie der Stadt, wie ihre Schwingungen oder Frequenzen. Er erfasst das „große Bild" davon, wie die Stadt zusammengesetzt ist.
Die gute Nachricht: Der Roboter kann sofort erkennen, ob die ganze Stadt verbunden ist, oder ihre globale Form verstehen. Es ist wie das Betrachten eines Satellitenfotos; Sie sehen das gesamte Layout auf einen Blick.
Die schlechte Nachricht: Diese Methode ist schrecklich für lokale Details. Wenn Sie fragen: „Gibt es eine bestimmte Straße zwischen Gebäude A und B?", hat der Roboter Schwierigkeiten. Die Mathematik wird unübersichtlich und instabil (schlecht konditioniert), wenn man versucht, auf winzige Details zu zoomen. Es ist wie der Versuch, ein einzelnes Wort zu lesen, indem man auf ein unscharfes Satellitenfoto schielt. Außerdem, wenn Sie einen Teil des Grundrisses abschneiden, um Platz zu sparen (Trunkierung), könnten Sie versehentlich die Fähigkeit löschen, spezifische Formen zu zählen, wie Dreiecke von Straßen.

3. Der „Touristen-Weg" (Random-Walk-Tokenisierung)

Die Analogie: Stellen Sie sich einen Touristen vor, der an einem Gebäude startet und zufällig herumwandert. Sie geben dem Roboter einen Bericht darüber, wie wahrscheinlich es ist, dass der Tourist nach 1 Schritt, 2 Schritten, 3 Schritten usw. zum Startgebäude zurückkehrt.
Die gute Nachricht: Dies ist erstaunlich zum Aufspüren von Schleifen. Wenn Sie fragen: „Können Sie in einem Kreis gehen und zum Start zurückkehren?", sieht der Roboter die Antwort sofort, weil der Bericht die Rückkehrwahrscheinlichkeiten buchstäblich auflistet.
Die schlechte Nachricht: Diese Methode ist verlustbehaftet. Sie wirft Informationen weg. Die Arbeit beweist, dass zwei völlig unterschiedliche Stadtlayouts (eines, das auf eine flache Karte gezeichnet werden kann, und eines, das nicht kann) denselben genauen Touristenbericht produzieren können. Egal wie schlau der Roboter ist, er kann den Unterschied zwischen diesen beiden Städten nicht erkennen, weil die Übersetzung das entscheidende Detail verwischt hat. Es ist wie der Versuch, eine Person nur an ihrer Schuhgröße zu identifizieren; viele verschiedene Personen haben die gleiche Schuhgröße.

Die wichtigsten Erkenntnisse

1. Man kann eine schlechte Übersetzung nicht einfach „reparieren"
Sie könnten denken: „Wenn ich dem Roboter die ‚Straßen-für-Straßen'-Liste gebe, kann er dann nicht einfach lernen, sie in seinem Gehirn in den ‚Stadt-Grundriss' umzuwandeln?"
Die Arbeit sagt nein. Wenn der Roboter in seiner Größe (Tiefe) begrenzt ist, kann er einen Übersetzungsstil nicht in einen anderen umwandeln. Wenn Sie mit einem „Touristen-Weg"-Bericht beginnen, kann der Roboter die vollständige Karte niemals wiederherstellen, egal wie sehr er nachdenkt. Die Information ist für immer verloren.

2. Unterschiedliche Aufgaben benötigen unterschiedliche Karten

Müssen Sie einen bestimmten Nachbarn finden? Verwenden Sie die „Straßen-für-Straßen"-Liste.
Müssen Sie die Form der ganzen Stadt verstehen? Verwenden Sie den „Stadt-Grundriss".
Müssen Sie Schleifen finden? Verwenden Sie den „Touristen-Weg".
Der Versuch, eine einzige Karte für alles zu verwenden, macht den Roboter ineffizient oder unfähig, das Problem zu lösen.

3. Die „beste" Lösung ist eine Mischung
In ihren Experimenten stellten die Autoren fest, dass der Roboter am besten performte, wenn sie ihm alle drei Übersetzungen gleichzeitig gaben. Er konnte die „Straßen"-Liste für lokale Details und den „Grundriss" für die globale Form nutzen und die Stärken jeder Sichtweise kombinieren.

Zusammenfassung

Die Arbeit kommt zu dem Schluss, dass Tokenisierung nicht nur ein langweiliger erster Schritt ist; sie ist ein fundamentaler Teil der Intelligenz des Roboters. Die Wahl der falschen Übersetzungsmethode erzeugt einen „Flaschenhals", den keine Menge zusätzlicher Rechenleistung leicht beheben kann. Um die beste Graphen-lernende KI zu bauen, müssen Sie die Übersetzungsmethode wählen, die zur spezifischen Frage passt, die Sie stellen.

Technische Zusammenfassung: Verloren in der Tokenisierung: Fundamentale Zielkonflikte bei der Graph-Tokenisierung für Transformer

Problemstellung

Transformer haben sich als leistungsfähige Architektur für das Graphenlernen etabliert, doch ihre Anwendung auf graphenstrukturierte Daten erfordert einen vorbereitenden Schritt: die Tokenisierung. Im Gegensatz zu Sequenzen oder Gittern fehlt Graphen ein kanonisches kontinuierliches Eingabeformat. Folglich muss eine Graph-zu-Token-Mapping-Strategie gewählt werden, um zu bestimmen, welche strukturellen Informationen der Eingabeschicht des Modells zugänglich gemacht werden.

Obwohl verschiedene Tokenisierungsstrategien existieren (z. B. spektral, Random-Walk, Adjazenz), werden sie oft als empirische Designentscheidungen oder Vorverarbeitungsdetails behandelt. Diese Arbeit geht davon aus, dass die Wahl der Tokenisierung eine fundamentale Komponente der Expressivität von Transformer darstellt. Das zentrale Problem, das adressiert wird, ist, ob verschiedene Tokenisierungen austauschbar sind oder ob sie unterschiedliche Rechenregime induzieren, insbesondere hinsichtlich der Tiefe, die zur Lösung von Graphenaufgaben erforderlich ist, und der Fähigkeit, strukturelle Informationen wiederherzustellen.

Methodik

Die Autoren formalisieren die Graph-Tokenisierung als integralen Bestandteil des Rechenmodells und analysieren die Expressivität von Transformer mit endlicher Tiefe ( $L$ ), Breite ( $m$ ) und Präzision ( $p$ ) unter drei primären Tokenisierungsfamilien:

Adjazenz-Tokenisierung: Kodiert die lokale Konnektivität jedes Knotens über seine Adjazenzzeile. Sie ist verlustfrei, exponiert jedoch nur lokale Strukturen.
Spektrale (Laplace-)Tokenisierung: Leitet Token aus der Eigenzerlegung des Graph-Laplace-Operators ( $L = D - A$ ) ab. Sie erfasst globale topologische Eigenschaften, ist jedoch permutationsäquivariant.
Random-Walk-Tokenisierung: Kodiert Rückkehrwahrscheinlichkeiten von Random Walks der Länge $1$ bis $t(n)$ . Sie erfasst Diffusionsmuster, ist jedoch inhärent verlustbehaftet.

Die Methodik kombiniert eine komplexitätstheoretische Analyse mit kontrollierten Experimenten.

Theoretische Analyse: Die Autoren leiten untere Schranken und Unmöglichkeitsergebnisse her, indem sie Graphenaufgaben auf Komplexitätsklassen abbilden (z. B. $TC^0$ , $NC^1$ , $L$ ). Sie analysieren, wie sich spezifische Aufgaben (z. B. Erkennung von $k$ -geschlossenen Wegen, Konnektivität, Zählen von Dreiecken, Planarität) unter verschiedenen Tokenisierungen verhalten, unter Berücksichtigung der Beschränkungen endlicher Tiefe und der mathematischen Eigenschaften der Token-Repräsentationen (z. B. Konditionszahlen, Informationsverlust).
Empirische Validierung: Experimente werden an synthetischen Aufgaben (Validierung von Tiefenseparationen) und realen Benchmarks (GraphBench, Open Graph Benchmark, ZINC) durchgeführt. Die Studie bewertet Transformer unter Verwendung vollständiger und gekürzter Versionen jeder Tokenisierung sowie kombinierter Tokenisierungen und vergleicht die Leistung mit DeepSet- und GIN-Baselines.

Hauptbeiträge

1. Formalisierung der Tokenisierung als Rechenbeschränkung

Die Arbeit formalisiert, wie die Eingabedarstellung die Transformer-Expressivität bei endlicher Tiefe einschränkt. Sie zeigt, dass Tokenisierung nicht lediglich ein Schritt des Feature-Engineerings ist, sondern ein Determinant dafür, welche strukturellen Abhängigkeiten dem Modell zugänglich sind.

2. Tiefenseparationen zwischen Tokenisierungen

Die Autoren beweisen, dass dieselbe Graphenberechnung je nach Tokenisierung völlig unterschiedliche Tiefen erfordern kann:

Random-Walk vs. Adjazenz: Die Erkennung eines $k$ -geschlossenen Weges ist mit Random-Walk-Tokenisierung in $O(1)$ Tiefe lösbar (da Statistiken explizit vorliegen), erfordert jedoch $\Omega(\log k)$ Tiefe mit Adjazenz-Tokenisierung. Dies wird durch eine Reduktion vom Wortproblem in der Permutationsgruppe $S_5$ (ein $NC^1$ -vollständiges Problem) auf Graphentopologie bewiesen, was zeigt, dass Transformer mit konstanter Tiefe ( $TC^0$ ) die sequenzielle Pfad traversal nicht simulieren können, die durch Adjazenz-Token erforderlich ist.
Adjazenz vs. Spektral: Die Lösung der globalen Graph-Konnektivität erfordert $\Omega(\log n)$ Tiefe mit Adjazenz-Tokenisierung, während Spektral-Tokenisierung dies in $O(1)$ Tiefe löst.

3. Inhärente Limitierungen und Verlustbehaftetheit

Random-Walk ist beweisbar verlustbehaftet: Unabhängig von der Weglänge kann Random-Walk-Tokenisierung die Planarität von Graphen nicht bestimmen. Die Autoren konstruieren planare und nicht-planare Graphen mit identischen Random-Walk-Verteilungen unter Verwendung von Godsil-McKay (GM)-Switching und beweisen, dass keine Transformer-Tiefe oder -Breite die topologische Unterscheidung wiederherstellen kann.
Spektrale Kürzung ist brüchig: Das Kürzen des Laplace-Spektrums (selbst um einen einzelnen Eigenwert) kann das Zählen von Dreiecken unmöglich machen. Die Autoren zeigen, dass das Hinzufügen einer Kante zwischen symmetrischen Knoten nur einen Eigenwert ändert; wird dieser Eigenwert gekürzt, kann der Transformer die Graphen nicht unterscheiden.
Adjazenz-Kürzung: Das Kürzen der Dimension von Adjazenz-Token (durch zufällige Projektion) zerstört die Fähigkeit, Aufgaben wie das Zählen von Dreiecken zu lösen, wie durch untere Schranken der Kommunikationskomplexität (Set Disjointness) bewiesen wird.

4. Schlechte Konditionierung der Spektralen Tokenisierung für lokale Aufgaben

Während Spektral-Tokenisierung globale Topologie erfasst, ist sie mathematisch schlecht konditioniert für lokale Aufgaben wie die Kantenvorhersage. Die Arbeit leitet eine untere Schranke her, die zeigt, dass die für die Dekodierung einer lokalen Kante aus einem globalen Spektrum erforderlichen Parameter-Normen mit dem maximalen Grad ( $d_{max}$ ) skalieren. Dies erzwingt einen Zielkonflikt: Entweder leidet das Modell unter Softmax-Sättigung (verschwindende Gradienten) oder es erfordert explodierende Gewichte, was die Optimierung erschwert.

5. Unmöglichkeit der Konvertierung bei begrenzter Tiefe

Die Arbeit stellt fest, dass die Konvertierung zwischen Tokenisierungsfamilien bei begrenzter Tiefe im Allgemeinen unmöglich ist.

Ein Transformer kann Adjazenz-Token nicht effizient in Random-Walk-Statistiken umwandeln (erfordert $\Omega(\log k)$ Tiefe).
Ein Transformer kann keine vollständigen Adjazenz- oder Laplace-Repräsentationen aus Random-Walk-Token wiederherstellen (aufgrund von Informationsverlust).
Die Konvertierung zwischen globalen (Spektral-) und lokalen (Adjazenz-)Ansichten führt zu schweren Rechenengpässen oder Optimierungsinstabilität.

Ergebnisse

Theoretische Befunde:

Tiefenseparationen: Die empirische Validierung bestätigt, dass Spektral-Tokenisierung Konnektivitätsaufgaben mit $L=1$ über alle Graphengrößen hinweg löst, während Adjazenz-Tokenisierung bei größeren Graphen ( $n \ge 128$ ) auf Zufallsleistung kollabiert.
Wiederherstellungsgrenzen: Wenn ein Transformer trainiert wird, um Random-Walk-Rückkehrwahrscheinlichkeiten aus Adjazenz-Token vorherzusagen, wächst der Fehler mit der Weglänge $k$ , was mit der $\Omega(\log k)$ -Tiefenanforderung konsistent ist.
Planarität: Modelle, die Random-Walk-Token verwenden, scheitern daran, planare von nicht-planaren Graphen zu unterscheiden, selbst bei erhöhter Tiefe, was das theoretische Unmöglichkeitsergebnis bestätigt.

Empirische Befunde:

Aufgabenabhängigkeit: Keine einzelne Tokenisierung dominiert.
- Lokale Aufgaben: Adjazenz-Tokenisierung erzielt bei Aufgaben, die durch explizite lokale Beschränkungen bestimmt werden (z. B. Max Clique, Topologische Sortierung), die besten Ergebnisse.
- Globale Aufgaben: Spektrale (Laplace-)Tokenisierung erzielt bei Aufgaben, die von globaler Geometrie abhängen (z. B. Vorhersage molekularer Eigenschaften bei Tox21), die besten Ergebnisse.
- Kombinierter Ansatz: Die Kombination komplementärer Tokenisierungen (Adjazenz + Spektral + Random-Walk) liefert oft die beste Leistung, indem sie dem Modell ermöglicht, unterschiedliche strukturelle Signale zu nutzen.
Effekte der Kürzung: Gekürzte Tokenisierungen verschlechtern im Allgemeinen die Leistung, insbesondere für Aufgaben, die eine exakte strukturelle Wiederherstellung erfordern (z. B. Zählen von Dreiecken), und validieren die theoretische „Brüchigkeit" der Kürzung.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass Graph-Tokenisierung ein fundamentaler Zielkonflikt und kein Vorverarbeitungsdetail ist. Die Wahl der Tokenisierung diktiert die „Sicht" des Graphen, die der Transformer erhält, und schränkt dadurch die Klasse der strukturellen Abhängigkeiten ein, die das Modell bei endlicher Tiefe ausdrücken kann.

Wichtige Erkenntnisse, die von den Autoren hervorgehoben werden, umfassen:

Nicht-Austauschbarkeit: Adjazenz-, Spektral- und Random-Walk-Tokenisierungen sind nicht austauschbar; sie induzieren unterschiedliche Tiefenregime und Grenzen der Expressivität.
Inhärente Limitierungen: Spezifische Tokenisierungen haben beweisbare Blindstellen (z. B. kann Random-Walk Planarität nicht erkennen; Spektral ist für lokale Kanten schlecht konditioniert).
Konvertierungsbarrieren: Transformer können diese Repräsentationen nicht einfach „lernen", effizient ineinander umzuwandeln, wenn die initiale Tokenisierung ungünstig ist; die Tiefe, die erforderlich ist, um diese Lücken zu überbrücken, kann prohibitiv sein.
Praktische Implikation: Die optimale Tokenisierung hängt von der strukturellen Natur der nachgelagerten Aufgabe ab. Die Kombination komplementärer Ansichten ist eine robuste Strategie, um die Limitierungen einer einzelnen Repräsentation zu überwinden.

Die Autoren schließen, dass ihre Analyse zwar auf Knoten-Ebenen-Tokenisierungen fokussiert ist, die Ergebnisse jedoch ein breiteres Prinzip nahelegen: Die Eingabedarstellung ist eine kritische Achse der Komplexität im Graphenlernen, und zukünftige Arbeiten sollten Optimierungs-Herausforderungen und Kanten-Ebenen-Tokenisierungen untersuchen.