🤖 machine learning

Indexing: the Beginning and the End

Dieses Paper führt das Konzept der kausalen Komplexität ein, um zu demonstrieren, dass maskierte Deep-Learning-Architekturen wie RNNs und Linear-Attention-Transformer fundamental darin limitiert sind, das Indexierungs-Primitiv zu lösen, wenn der Index am Ende der Eingabe erscheint, wohingegen Softmax- und nicht-maskierte Linear-Attention-Transformer dieses effizient lösen können, eine theoretische Trennung, die durch empirische Experimente untermauert wird.

Ursprüngliche Autoren: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

Veröffentlicht 2026-07-27

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

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, einen superintelligenten Roboter zu bauen, der eine Geschichte lesen und Fragen dazu beantworten kann. Dies ist die Welt der Künstlichen Intelligenz, speziell eines Feldes namens „Deep Learning“, in dem Computer Muster lernen, indem sie riesige Mengen an Daten betrachten. Lange Zeit waren die beliebtesten Roboter für diese Aufgabe sogenannte „Transformer“. Sie sind wie brillante Bibliothekare, die in der Lage sind, ein ganzes Buch augenblicklich zu durchblättern, um eine bestimmte Tatsache zu finden. Aber es gibt einen Haken: Je länger das Buch wird, desto langsamer wird der Bibliothekar, und der Bau von ihnen erfordert viel Energie und Geld.

Um dies zu beheben, erfanden Wissenschaftler neue Arten von Robotern, wie zum Beispiel „RNNs“ (die Geschichten Wort für Wort lesen, genau wie ein Mensch) und „SSMs“ (die versuchen, die ganze Geschichte auf einmal zu lesen, aber auf eine sehr gestraffte Weise). Die große Frage, die alle stellt, lautet: „Sind diese neuen, schnelleren Roboter genauso klug wie die alten, langsamen, oder haben sie versteckte Schwachstellen?“ Um die Antwort zu finden, geben Forscher diesen Robotern winzige, knifflige Rätsel. Diese Rätsel sind wie die „Hausaufgaben“ der KI-Welt. Wenn ein Roboter eine einfache Hausaufgabe nicht lösen kann, beweist das, dass das Gehirn des Roboters eine fundamentale Grenze hat, egal wie viel man ihn trainiert.

Diese Arbeit mit dem Titel „Indexing: the Beginning and the End“ nimmt ein sehr spezifisches, einfaches Rätsel namens „Indexing“ und nutzt es, um die Gehirne dieser verschiedenen Roboter-Architekturen zu testen. Das Rätsel ist täuschend einfach: Stellen Sie sich vor, Sie haben eine Liste von $n$ Bits (eine Zeichenfolge aus 0en und 1en) und eine Zahl $i$ , die Ihnen sagt, welches Bit Sie auswählen sollen. Das Ziel ist schlichtweg, den Wert dieses spezifischen Bits auszugeben. Es ist, als würde man einem Roboter eine Reihe von 64 Lichtschaltern übergeben und eine Zahl, sagen wir „17“, und fragen: „Ist Schalter 17 an oder aus?“

Die Forscher, Alexander Kozachinskiy, Vicente Opazo und Felipe Urrutia, entdeckten, dass die Reihenfolge, in der der Roboter die Informationen sieht, alles verändert. Sie fanden heraus, dass einige Roboter unglaublich schnell bei dieser Aufgabe sind, während andere gegen eine Wand prallen, die sie einfach nicht erklimmen können, egal wie viele Schichten des „Denkens“ sie besitzen.

Hier kommt die Wendung: Die Arbeit beweist, dass es für bestimmte Arten von Robotern (speziell jene, die Informationen auf eine „kausale“ oder „maskierte“ Weise verarbeiten, was bedeutet, dass sie nur auf das schauen können, was vor ihnen geschah, und nicht auf das, was nach ihnen kommt) mathematisch unmöglich ist, dieses Rätsel zu lösen, wenn die Liste der Bits lang ist und die Indexnummer ganz am Ende erscheint. Es ist, als würde man einem Roboter eine lange Schlange von Menschen geben, ihn bitten, sich jedes Gesicht zu merken, und ihm dann ganz am Ende zuflüstern: „Nenne mir den Namen von Person Nummer 42.“ Die Arbeit zeigt, dass Roboter wie RNNs, Mamba und maskierte Linear-Attention-Transformer einen „Gedächtnis-Engpass“ haben. Sie können nicht all diese Informationen in ein ausreichend kleines Paket komprimieren, um das spezifische Bit zu erinnern, wenn der Index schließlich eintrifft. Die Autoren haben dies unter Verwendung strenger Mathematik bewiesen, die auch dann gilt, wenn die Roboter über eine unendliche Präzision verfügen (das heißt, sie werden nicht durch Rundungsfehler verwirrt).

Doch die Geschichte ändert sich, wenn man das Skript umdreht. Wenn die Indexnummer am Anfang der Liste erscheint (und dem Roboter sagt: „Merke dir Person 42, bevor du überhaupt die Schlange der Menschen siehst“), werden die RNNs zu Superhelden. Sie können dies in einem einzigen Schritt lösen, während die anderen Roboter (einschließlich der berühmten Transformer) mindestens zwei Schritte benötigen, um es herauszufinden.

Die Autoren haben nicht nur die Mathematik betrieben; sie haben auch Experimente mit echten Modellen durchgeführt. Sie trainierten diese Roboter auf Listen von bis zu 64 Bits. Die Ergebnisse stimmten perfekt mit ihrer Theorie überein. Die Roboter, von denen die Mathematik sagte, dass sie scheitern sollten (die kausalen Modelle, die versuchen, das Bit am Ende einer langen Liste zu finden), gaben konsequent auf, wenn die Listen länger wurden. Unterdessen lernten die Roboter, von denen die Mathematik sagte, dass sie Erfolg haben sollten, die Aufgabe mühelos.

Was ist also die Lehre daraus? Es ist nicht so, dass ein Roboter in jeder Hinsicht „besser“ ist als der andere. Stattdessen offenbart die Arbeit, dass verschiedene Architekturen unterschiedliche „Superkräfte“ und unterschiedliche „Kryptonite“ haben. Die Art und Weise, wie ein Roboter Informationen verarbeitet – ob er von links nach rechts liest, alles auf einmal betrachtet oder versucht, die Vergangenheit zusammenzufassen – bestimmt genau, welche Rätsel er lösen kann und welche ihn für immer stoppen werden. Dies hilft Wissenschaftlern, die fundamentalen Grenzen der KI zu verstehen, um sicherzustellen, dass wir, wenn wir die nächste Generation intelligenter Maschinen bauen, genau wissen, was sie können und was nicht.

Technisches Resümee: Indexing: Der Anfang und das Ende

Problemstellung

Dieses Paper untersucht die Expressivität und die Informationsengpässe moderner Deep-Learning-Architekturen – spezifisch Rekurrente Neuronale Netze (RNNs), Softmax-Transformer, Linear-Attention-Transformer und State-Space-Modelle (SSMs) – durch die Linse des Indexing-Primitivs.

Die Indexing-Aufgabe ist wie folgt definiert: Gegeben sei eine Sequenz von $n$ Bits $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ und ein Index $i \in \{1, \dots, n\}$ . Das Modell muss den Wert des $i$ -ten Bits, $\sigma_i$ , ausgeben. Die Autoren analysieren zwei spezifische Variationen dieser Aufgabe, um unterschiedliche architektonische Einschränkungen zu untersuchen:

Right-Hand Indexing (RHI): Der Index $i$ erscheint am Ende der Eingangssequenz (nach den Bits). Das Modell muss $\sigma_i$ basierend auf der Information extrahieren, die aus den vorangegangenen $n$ Bits verarbeitet wurde.
Left-Hand Indexing (LHI): Der Index $i$ erscheint am Anfang der Eingangssequenz (vor den Bits). Das Modell muss die Index-Information durch die Sequenz tragen, um $\sigma_i$ am Ende abzurufen.

Die Studie konzentriert sich auf „kleine“ Architekturen, definiert als solche mit $o(1)$ Parametern (eine konstante Anzahl an Parametern relativ zur Sequenzlänge $n$ ) und potenziell unendlich präziser reeller Arithmetik.

Methodik

Die Autoren verwenden einen theoretischen Rahmen basierend auf kausaler Komplexität und VC-Dimension, um unbedingte untere Schranken abzuleiten.

Kausale Komplexität

Für kausale (maskierte) Architekturen, bei denen die Ausgabe an Position $k$ nur von den Eingaben $1$ bis $k$ abhängt, führen die Autoren den Begriff der kausalen Komplexität ein. Diese misst die minimale Dimension $s$ , auf die die Historie der Eingaben ( $x_1, \dots, x_{k-1}$ ) komprimiert werden kann (mittels einer „Fingerabdruck“-Funktion), sodass die $k$ -te Ausgabe aus dieser komprimierten Repräsentation und der aktuellen Eingabe $x_k$ mit geringer arithmetischer Komplexität berechnet werden kann.

Kerneinsicht: Wenn eine Architektur eine geringe kausale Komplexität aufweist (speziell $o(1)$ ), kann sie die notwendige Historie nicht komprimieren, um Aufgaben zu lösen, die den Abruf spezifischer vergangener Informationen erfordern, wenn diese Information nicht unmittelbar zugänglich ist.

Theoretische Werkzeuge

VC-Dimension: Die Autoren adaptieren die Technik von Kozachinskiy et al. (2025), um zu zeigen, dass die assoziierte Konzeptklasse eine VC-Dimension von mindestens $n$ haben muss, falls das Modell die Indexing-Aufgabe löst.
Arithmetische Komplexität: Sie nutzen die arithmetische Komplexität der von den Schichten berechneten Funktionen (einschließlich Exponentialfunktionen, arithmetischer Operationen und Konditionals), um die VC-Dimension zu begrenzen.
Unbedingte Schranken: Im Gegensatz zu früheren Arbeiten, die auf Annahmen über begrenzte Präzision beruhten, gelten diese Ergebnisse auch für Modelle, die reelle Zahlen mit unendlicher Präzision verwenden.

Experimentelle Validierung

Die theoretischen Befunde werden durch Experimente zu binären Indexing-Aufgaben für Sequenzlängen $n \in \{8, 16, 32, 64\}$ validiert. Die Autoren vergleichen:

Volle und kausale Varianten von Softmax- und Linear-Attention-Transformern.
RNNs (speziell GRUs).
SSMs (speziell Mamba).
Alle Modelle werden von Grund auf mit festen Hyperparametern trainiert, um die Lern-Dynamik bei steigendem $n$ zu beobachten.

Zentrale Beiträge und Ergebnisse

1. Right-Hand Indexing (Index am Ende)

In diesem Szenario verarbeitet das Modell alle $n$ Bits, bevor es den Index sieht. Um die Aufgabe zu lösen, muss das Modell die gesamte $n$ -Bit-Zeichenfolge in einen Zustand komprimieren, der klein genug ist, um vom Index-Token verarbeitet zu werden.

Unmöglichkeit für Architekturen mit geringer kausaler Komplexität: Die Autoren beweisen, dass keine konstante Anzahl ( $O(1)$ $O (1)$ ) von Schichten mit $o(1)$ $o (1)$ kausaler Komplexität RHI lösen kann.
- Betroffene Architekturen: Kleine RNNs, SSMs (z. B. Mamba) und maskierte Linear-Attention-Transformer besitzen alle eine $o(1)$ kausale Komplexität. Folglich können sie RHI nicht in einer konstanten Anzahl von Schichten lösen, selbst mit unendlicher Präzision.
- Experimentelle Bestätigung: Modelle dieser Kategorie (1-Schicht- und Multi-Schicht-kausale Linear-Attention, GRUs, Mamba) scheitern konsistent am Erlernen von RHI, wenn $n$ wächst, und erreichen bei $n=64$ eine Erfolgsquote von 0 %.
Möglichkeit für Architekturen mit hoher kausaler Komplexität:
- Softmax-Transformer: Ein einziger Layer mit $O(1)$ Parametern kann RHI lösen. Dies wird auf ihre hohe kausale Komplexität zurückgeführt (durch den Softmax-Mechanismus, der globale Attention ermöglicht).
- Volle Linear-Attention: Zwei Layer mit $O(1)$ Parametern können RHI lösen.
- Experimentelle Bestätigung: Diese Konfigurationen lernen die Aufgabe problemlos mit hohen Erfolgsraten, selbst bei $n=64$ .

2. Left-Hand Indexing (Index am Anfang)

In diesem Szenario wird der Index zuerst verarbeitet und muss durch die Sequenz bis zur relevanten Bit-Position getragen werden.

Dominanz von RNNs: Kleine RNNs können LHI in einem einzigen Layer mit $O(1)$ Parametern lösen. Sie halten natürlich einen verborgenen Zustand bereit, der den Index $i$ tragen und eine spezifische Koordinate aktualisieren kann, wenn auf das $i$ -te Bit gestoßen wird.
Einschränkungen anderer Architekturen:
- SSMs und Linear-Attention: Weder 1-Schicht-SSMs noch 1-Schicht-Linear-Attention (maskiert oder voll) können LHI mit $o(1)$ Parametern lösen. Die Linearität der SSM-Updates verhindert, dass sie das Bit-Werte selektiv an eine durch den Index bestimmte Position schreiben, ohne Informationen so zu vermischen, dass der Abruf verhindert wird.
- Softmax-Transformer: 1-Schicht-Softmax-Transformer scheitern ebenfalls an LHI mit $o(1)$ Parametern.
Lösung durch Tiefe: Alle Architekturen (einschließlich SSMs, Linear-Attention und Softmax-Transformer) können LHI lösen, wenn sie über 2 Layer mit $O(1)$ Parametern verfügen. Der erste Layer kann den Index propagieren, und der zweite kann das Bit abrufen.
Experimentelle Bestätigung: 1-Schicht-GRUs sind erfolgreich bei allen Längen. 1-Schicht-Mamba- und Linear-Attention-Modelle scheitern für $n \ge 16$ . 2-Schicht-Versionen aller Architekturen sind erfolgreich.

Zusammenfassende Tabelle der erforderlichen Mindestanzahl an Layern

Architektur	Left-Hand Indexing (LHI)	Right-Hand Indexing (RHI)
Full Softmax	2	1
Causal Softmax	2	1
Full Linear-Attention	2	2
Current Causal Linear-Attention	2	$\omega(1)$ (Unmöglich)
SSM (z. B. Mamba)	2	$\omega(1)$ (Unmöglich)
RNN	1	$\omega(1)$ (Unmöglich)

(Hinweis: $\omega(1)$ bedeutet, dass die erforderliche Anzahl an Layern nicht durch eine Konstante begrenzt ist, d. h. sie wächst mit $n$ .)

Bedeutung und Behauptungen

Das Paper beansprucht, die ersten Multi-Layer, unendliche-Präzision-unteren Schranken für eine Klasse von Architekturen mit geringer kausaler Komplexität geliefert zu haben, einschließlich SSMs, RNNs und maskierten Linear-Attention-Transformern.

Architektonische Trennung: Das Indexing-Primitiv offenbart eine fundamentale Trennung zwischen den Architekturen. Während Softmax-Transformer und volle Linear-Attention-Modelle RHI effizient lösen können, scheitern maskierte Varianten und SSMs daran. Dies hebt die spezifische Rolle globaler Attention-Mechanismen hervor, um Informationsengpässe zu überwinden.
Rolle der Linearität: Die Ergebnisse legen nahe, dass die linearen Update-Regeln von SSMs, die oft für ihre Effizienz gelobt werden, in LHI-Aufgaben zu einem Nachteil werden, in denen ein nicht-lineares selektives Schreiben in einem einzigen Schritt erforderlich ist.
Übereinstimmung von Theorie und Praxis: Die Experimente zeigen, dass die theoretischen Unmöglichkeitsresultate (asymptotische untere Schranken) sich qualitativ in endlichen Trainingssettings manifestieren. Konfigurationen mit theoretischen Lösungen lernen die Aufgabe robust, während jene ohne diese bei steigender Sequenzlänge Schwierigkeiten haben, selbst wenn sie bei kleinen $n$ erfolgreich waren.
Bescheidenheit: Die Autoren geben explizit an, dass das Scheitern beim Training kein Beweis für Unmöglichkeit ist und dass Erfolg bei kleinen $n$ nicht im Widerspruch zu asymptotischen unteren Schranken steht. Die starke Korrelation zwischen ihren theoretischen Schranken und der empirischen Leistung deutet jedoch darauf hin, dass die kausale Komplexität ein robuster Prädiktor für die Lernbarkeit von Retrieval-Aufgaben ist.

Die Arbeit erweitert die Analyse der Transformer-Expressivität (die zuvor auf Funktionskomposition und Induction-Heads fokussiert war) auf moderne, effiziente Alternativen und liefert eine rigorose mathematische Begründung für deren Limitationen in spezifischen Informationsabruf-Szenarien.