🤖 machine learning

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete

Dieses Paper demonstriert, dass Positionskodierungen nicht zwingend erforderlich sind, damit Transformer Turing-Vollständigkeit erreichen, da der Sliding-Window-Mechanismus selbst die Permutationssymmetrie bricht und ausreichende Positionsinformationen bereitstellt, um universelle Berechenbarkeit zu simulieren.

Ursprüngliche Autoren: Qian Li, Xinyu Mao, Shang-Hua Teng

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Qian Li, Xinyu Mao, Shang-Hua Teng

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 Roboter beizubringen, eine Geschichte zu erzählen oder ein mathematisches Problem zu lösen. Lange Zeit glaubten Informatiker, dass der Roboter dafür ein spezielles „Adressbuch“ benötigt, das jedem Wort, das er liest, angehängt ist. Dieses Adressbuch, genannt Positional Encoding (PE), sagte dem Roboter genau, wo sich jedes Wort im Satz befand (1., 2., 3. usw.). Ohne es, so die Theorie, würde der Roboter verwirrt werden und nicht den Unterschied zwischen „Der Hund jagt die Katze“ und „Die Katze jagt den Hund“ erkennen können.

Dieses Paper argumentiert, dass Sie dieses „Adressbuch“ eigentlich nicht benötigen, wenn der Roboter mit einer bestimmten Art von Gedächtnis arbeitet: einem Sliding Window (einem gleitenden Fenster).

Hier ist die Kernidee, unterteilt mit alltäglichen Analogien:

1. Der alte Glaube: Das „statische Foto“

Betrachten Sie einen Standard-Transformer-Modell (die Art, die hinter vielen KI-Chatbots steckt) wie einen Fotografen, der ein Foto von einer ganzen Menge Menschen macht. Wenn Sie dem Fotografen einfach einen Haufen Gesichter übergeben, ohne ihm zu sagen, wer wo steht, kann er nicht zwischen einer Reihe von Menschen und einem zufälligen Haufen unterscheiden. Er braucht ein Etikett auf der Stirn jedes Menschen, um die Reihenfolge zu kennen (Positional Encoding).

2. Die neue Entdeckung: Der „fahrende Bus“

Die Autoren erkannten, dass eine KI, wenn sie komplexe, schrittweise Denkprozesse durchführt (wie das Lösen einer langen Matheaufgabe), nicht die gesamte Historie auf einmal betrachtet. Stattdessen nutzt sie ein Sliding Window.

Stellen Sie sich vor, die KI sitzt in einem Bus mit einem Fenster, das nur die letzten 10 Personen zeigt, die vorbeigekommen sind.

Die alte Sicht: Wenn Sie nur auf die 10 Personen schauen, die sich gerade im Fenster befinden, können Sie nicht sagen, wer zuerst vorbeikam oder wer zuletzt aus dem Fenster fiel. Es ist einfach eine Gruppe von 10 Personen.
Die neue Sicht: Die Autoren bemerkten, dass der Bus fährt.
- Jede Sekunde steigt eine neue Person in den Bus (tritt in das Fenster ein).
- Jede Sekunde fällt die älteste Person hinten aus dem Bus (verlässt das Fenster).
- Selbst wenn die KI nicht weiß, wer die „Straßenadressen“ der Leute im Bus hat, erzeugt der Akt des Bewegens des Busses ein Muster. Die KI kann sehen: „Oh, gerade ist eine neue Person eingestiegen, und ich weiß, wer gerade aus dem Fenster gefallen ist, weil sich die Gesamtzahl der Gruppe geändert hat.“

3. Das „Magische Histogramm“ (Das HIST-Modell)

Um dies zu beweisen, erfanden die Autoren einen theoretischen Roboter namens HIST-Modell.

Dieser Roboter ist blind für die Reihenfolge. Er kann nicht sagen: „Das rote Hemd ist an 3. Stelle.“
Er sieht nur eine Anzahl (ein Histogramm). Er weiß: „Es sind gerade 3 rote Hemden, 2 blaue Hemden und 1 grünes Hemd im Fenster.“
Er besitzt außerdem ein winziges Gedächtnis (einen „Kontrollzustand“), um sich an die letzten Ereignisse zu erinnern.

Der magische Trick ist dieser: Durch den Vergleich der Anzahl vor dem Eintritt einer neuen Person und der Anzahl nach dem Eintritt kann der Roboter genau herausfinden, wer gerade aus dem Bus gefallen ist, selbst ohne deren Namensschild zu sehen.

Vorher: 3 Rot, 2 Blau.
Neue Person tritt ein (Blau).
Nachher: 3 Rot, 3 Blau.
Warte, die Fenstergröße ist fix! Wenn eine neue Blaue Person eintritt, muss ein Rotes gegangen sein.
Schlussfolgerung: Der Robot weiß, dass ein rotes Hemd gerade hinten aus dem Bus gefallen ist, obwohl er nie die Position des roten Hemdes gesehen hat.

4. Das große Ergebnis: Turing-Vollständigkeit

In der Informatik bedeutet „Turing-Vollständig“, dass eine Maschine theoretisch jedes Problem lösen kann, das ein Computer lösen kann, sofern man ihr genug Zeit und Speicher gibt.

Bisherige Überzeugung: Transformer benötigen Positional Encodings, um Turing-vollständig zu sein.
Der Beweis dieses Papers: Ein Transformer mit einem Sliding Window benötigt keine Positional Encodings, um Turing-vollständig zu sein. Die Bewegung des Fensters selbst liefert genügend „sequenzielle Information“, um einen universellen Computer zu simulieren.

Die Autoren bauten eine mathematische Brücke, die zeigt:

Eine Maschine, die nur Token-Typen zählt (das HIST-Modell), kann einen universellen Computer simulieren (speziell eine „Post-Maschine“, die einer Warteschlange ähnelt).
Ein Standard-Transformer (oh sich Positional Encodings) kann diese Zählmaschine perfekt imitieren.

5. Was das bedeutet (und was es nicht bedeutet)

Die guten Nachrichten:
Es stellt sich heraus, dass die „Bewegung“ der schrittweisen Datenverarbeitung ausreicht, um Ordnung zu schaffen. Man braucht keine manuellen Markierungen für jedes Wort mit einer Nummer, um zur universellen Berechnung fähig zu sein. Die „Gleitbewegung“ bricht die Symmetrie von selbst auf.

Die Einschränkungen (Was das Paper nicht sagt):

Es geht nicht um Geschwindigkeit: Dies ist ein Beweis der Möglichkeit, nicht der Effizienz. Nur weil ein Roboter ein Problem ohne das Adressbuch lösen kann, bedeutet das nicht, dass er es im wirklichen Leben schnell oder einfach tun wird.
Es liest keine exakten Positionen: Der Roboter kann immer noch nicht sagen: „Das 5. Wort ist 'Apfel'“. Er kann nur schlussfolgern: „Jemand hat die Gruppe verlassen.“ Es ist ein cleverer Trick der Deduktion, keine direkte Abbildung.
Es braucht ein wenig mathematische Magie: Der Beweis beruht darauf, dass der Roboter sehr präzise zählen kann (Paritätsprüfungen), um genau zu wissen, wer das Fenster verlassen hat. In der realen Welt könnte dies eine sehr hohe mathematische Präzision erfordern, ein technisches Detail, das die Autoren anerkennen.

Zusammenfassung

Betrachten Sie das Positional Encoding als eine GPS-Koordinate für jedes Wort. Dieses Paper sagt: „Sie brauchen kein GPS, wenn Sie eine Straße entlanggehen und beobachten, wie Menschen in einen Laden hinein- und wieder herausgehen. Der Fluss der Menschen rein und raus erzählt Ihnen die Geschichte, selbst wenn Sie nicht deren genaue Straßenadressen kennen.“

Das Sliding Window selbst ist das „GPS“ für die KI und macht das externe Adressbuch überflüssig, damit die Maschine zur universellen Berechnung fähig ist.

Technisches Resümee: Überdenken der Rolle von Positional Encoding in Sliding-Window-Transformern

1. Problemstellung

Positional Encoding (PE) gilt seit langem als eine notwendige Komponente für Transformer-Architekturen, um geordnete Sequenzen zu verarbeiten. Die vorherrschende Intuition ist, dass der Self-Attention-Mechanismus ohne explizite Positionsinformationen permutationsinvariant ist, was es dem Modell unmöglich macht, zwischen verschiedenen Anordnungen derselben Kontext-Token zu unterscheiden. Diese Annahme bildet die Grundlage für frühere theoretische Ergebnisse, die die Turing-Vollständigkeit von Transformern mit Chain-of-Thought (CoT)-Reasoning etablieren, welche stark auf PE angewiesen sind, um sequenzielle Berechnungen zu simulieren.

Diese Universalitätsresultate gehen jedoch oft davon aus, dass das Modell auf die gesamte Historie zugreift. In praktischen Szenarien der langfristigen Argumentation operieren Modelle mit einem endlichen Sliding Context Window (gleitendes Kontextfenster). Während das Fenster vorwärts gleitet, treten Token ein und aus, was eine temporale Asymmetrie einführt. Die zentrale Frage, die diese Arbeit adressiert, lautet: Sind Positional Encodings wirklich notwendig für universelle Berechnungen in Sliding-Window-Transformern? Die Autoren untersuchen, ob der Sliding-Window-Mechanismus selbst eine ausreichende sequentielle Struktur bereitstellt, um Turing-Vollständigkeit ohne explizites PE zu erreichen.

2. Methodik und Framework

Das HIST-Modell

Um die aus dem Sliding Window resultierende Rechenleistung zu isolieren, führen die Autoren ein abstraktes autoregressives Modell namens HIST-Modell ein.

Definition: Eine HIST-Maschine generiert das nächste Token ausschließlich basierend auf einem endlichen Kontrollzustand und dem Token-Count-Histogramm des aktuellen Fensters (dem Vektor der Token-Frequenzen, indiziert durch das Alphabet).
Einschränkung: Das Modell hat keinen Zugriff auf die spezifischen Positionen der einzelnen Token innerhalb des Fensters; seine Übergangsfunktion ist bezüglich des Inhalts des Fensters permutationsinvariant.
Parity-HIST-Variante: Eine eingeschränkte Version, bei der die Übergangsfunktion nur von der Parität des Histogramms abhängt (d. h. davon, ob die Anzahl jedes Token-Typs gerade oder ungerade ist).

Theoretische Strategie

Der Beweis der Turing-Vollständigkeit erfolgt in zwei Hauptstadien:

Simulation von Post-Maschinen: Die Autoren beweisen, dass eine Parity-HIST-Maschine eine Post-Maschine (einen warteschlangenbasierten Automaten, der als Turing-vollständig bekannt ist) simulieren kann.
- Zentrale Erkenntnis: Obwohl die Parity-HIST-Maschine nur die Parität des Fensters beobachtet, ermöglicht die FIFO-Natur (First-In-First-Out) des Sliding Windows der Maschine, das Token zu inferieren, das gerade das Fenster verlassen hat. Durch den Vergleich des Paritäts-Histogramms vor und nach einer Fensteraktualisierung (und unter Nutzung des endlichen Kontrollzustands zur Speicherung des neu eingetretenen Tokens) kann die Maschine die Identität des „verlorenen“ Front-Tokens ableiten. Dies simuliert effektiv eine Dequeue-Operation einer Warteschlange ohne explizite Positionsadressierung.
Simulation von Parity-HIST mit Transformern: Die Autoren konstruieren einen Sliding-Window-Transformer ohne PE, der das Parity-HIST-Modell simulieren kann.
- Mechanismus: Der Transformer verwendet ein konstantes Token-Alphabet und ein adaptives Update-Bit. Um die Roh-Token-Zählungen (und damit deren Parität) aus dem Attention-Mechanismus wiederherzustellen, führt die Konstruktion ein spezielles Marker-Symbol (#) ein.
- Attention-Dynamik: Durch die Verwendung von Uniform Attention (erreicht durch Null-Matrizen für Query und Key) werden die Attention-Gewichte zu $1/m$ (wobei $m$ die Fenstergröße ist). Die Anwesenheit eines einzelnen Markers ermöglicht es dem Modell, die Fenstergröße $m$ zu inferieren und die normalisierten Attention-Massen zurück in Roh-Ganzzahlen zu konvertieren.
- Paritäts-Extraktion: Mit ausreichender arithmetischer Präzision (logarithmisch in der Fenstergröße) berechnet der MLP-Layer die Parität der Token-Zählungen und repliziert damit effektiv die Parity-HIST-Übergangsfunktion.

3. Zentrale Beiträge und Ergebnisse

Theorem 1 (High Level): Das Parity-HIST-Modell ist Turing-vollständig. Die Autoren zeigen, dass die zeitliche Entwicklung eines Sliding Windows, kombiniert mit einer permutationsinvarianten Zusammenfassung (Histogramm-Parität) und einem endlichen Zustand, ausreicht, um Post-Maschinen zu simulieren.
Theorem 2 (High Level): Jede Parity-HIST-Maschine kann durch einen Sliding-Window-Transformer ohne Positional Encodings simuliert werden.
Korollar: Sliding-Window-Transformer ohne PE sind Turing-vollständig.
Konstruktionsdetails:
- Die Konstruktion verwendet ein konstantes Vokabular und eine konstante Anzahl lernbarer Parameter.
- Sie verwendet einen adaptiven Window-Update-Mechanismus, bei dem Token ein Kontroll-Bit tragen, um entweder das Fenster zu verschieben (Standard) oder es zu erweitern (das älteste Token beibehalten), wodurch die Notwendigkeit entfällt, eine Worst-Case-Fenstergröße vorzugehen.
- Die Simulation erfordert eine logarithmische Präzision ( $O(\log S)$ ) für arithmetische Operationen, um Paritäten zu berechnen, wobei $S$ die maximale Fensterlänge ist.

4. Bedeutung und Behauptungen

Das Paper behauptet, die Konzepte von Positional Encoding und sequentieller Struktur im Kontext universeller Berechnung grundlegend voneinander zu trennen.

PE ist nicht unverzichtbar: Die Ergebnisse zeigen, dass explizite Positional Encodings keine Voraussetzung dafür sind, dass Transformer universelle Berechnungen durchführen können. Die „FIFO-ähnliche Bewegung“ des Sliding Windows selbst bricht die Permutationssymmetrie und liefert das notwendige sequentielle Signal.
Verfeinerung der Universalität: Die Arbeit klärt, dass universelle Berechnung zwar irgendeine Quelle sequentieller Struktur erfordert, diese Struktur jedoch nicht durch ein externes Positionsadresssystem bereitgestellt werden muss. Sie kann natürlich aus der temporalen Dynamik des Generierungsprozesses entstehen.
Abgrenzung zu vorangegangenen Arbeiten: Im Gegensatz zu früheren Universalitätsbeweisen, die PE nutzen, um Schaltkreisstrukturen zu speichern oder spezifische Token zu identifizieren, leitet diese Konstruktion die Simulation über ein permutationsinvariantes Fenster-Zusammenfassungsmodell.
Grenzen und Umfang:
- Die Konstruktion ist ein Expressivitätsresultat, kein Anspruch auf Lernbarkeit oder praktische Effizienz. Es impliziert nicht, dass Standard-Transformer diese Algorithmen natürlich lernen werden.
- Das Modell gewinnt nicht die exakten Token-Positionen innerhalb des Fensters zurück; es kann lediglich die Identität der eintretenden und austretenden Tokens inferieren.
- Die Konstruktion stützt sich auf ein spezifisches Paritäts-Primitiv, das eine logarithmische Präzision erfordert, welche als numerische Anforderung und nicht als fundamentale architektonische Einschränkung der Reduktion isoliert wird.

Zusammenfassend lässt sich sagen, dass das Paper etabliert, dass der Sliding-Window-Mechanismus allein – selbst in Abwesenheit von Positional Encodings – dem Transformer durch die Nutzung der temporalen Asymmetrie von Token-Eintritt und -Austritt die Kapazität zur universellen Berechnung verleiht.