ArXiv: Standard-Transformer mit Chain-of-Thought können nicht über TC^0-Komplexität hinaus schlussfolgern — Signpost-Token ermöglichen längengeneralisierbare Turing-Simulation

Das Team aus Kraus, Sarrof, Yaa, Koller und Hahn veröffentlichte am 28. April 2026 das Preprint Barriers to Universal Reasoning With Transformers (And How to Overcome Them) — eine theoretische Arbeit mit direkten Implikationen für die Skalierung von Chain-of-Thought-Reasoning in LLMs der aktuellen Generation.

Was wurde bewiesen?

Die Hauptthese des Preprints: Obwohl aus der Literatur bekannt ist, dass CoT die Ausdrucksstärke von Transformern theoretisch auf Turing-Vollständigkeit erhöht, gilt diese Aussage nicht unter der strengeren Anforderung des längengeneralisierbaren Lernens (Fähigkeit, CoT-Traces zu lösen, die länger als die im Training gesehenen sind).

Zitat aus dem Abstract:

„Unter Standard-Positionskodierungen und einem endlichen Alphabet — können Transformer mit CoT keine Probleme jenseits TC^0 lösen, d. h. die Ausdrucksstärkevorteile gelten nicht unter der strengeren Anforderung der längengeneralisierbaren Erlernbarkeit.”

Praktische Implikation: Viele Reasoning-Probleme, die auf Trainingslängen gelöst zu werden scheinen, scheitern, wenn die Sequenzlänge zunimmt. Das erklärt, warum LLMs oft „das Zählen vergessen” oder bei langen arithmetischen/logischen Ketten an Genauigkeit verlieren.

Vorgeschlagene Lösungen

Die Autoren schlagen zwei komplementäre Mechanismen vor:

1. Dynamische Vokabularskalierung

Das Vokabular wächst mit der Problemgröße. Damit wird die Einschränkung des „endlichen Alphabets” aus dem Theorem umgangen.

2. Signpost-Token + Value-Change-Encoding

• Signpost-Token — eindeutige Identifikatoren, die jeder Position auf dem „Band” der simulierten Maschine zugewiesen werden
• Value-Change-Encoding — Protokollierung nur von Zustandsänderungen statt vollständiger Zustände, was die Rekonstruktion durch Zählung ermöglicht

Die Kombination erzielt das Hauptergebnis:

„Längengeneralisierbare Simulation von Turing-Maschinen, bei der die CoT-Trace-Länge linear zur simulierten Laufzeit ist — mit konstantem Faktor.”

Mit anderen Worten: Dieser Ansatz durchbricht die TC^0-Barriere mit minimalem Token-Overhead.

Empirische Validierung

Neben dem theoretischen Beweis liefern die Autoren eine empirische Validierung — Signpost-Token und Value-Change-Encodings zeigen „praktische Verbesserungen bei der Längengeneralisierungsleistung bei komplexen Problemen.” Spezifische Benchmarks sind im abgerufenen Abstract nicht enthalten, aber eine vollständigere Analyse soll im vollständigen Papier folgen.

Warum ist das wichtig?

Diese Arbeit hilft zu erklären, warum die Skalierung von Reasoning durch bloßes Hinzufügen weiterer CoT-Token nicht funktioniert — es gibt eine fundamentale theoretische Barriere, kein bloßes Trainingsdefizit. Implikationen für die nächste Generation von LLMs:

• Die Architektur von Anthropic Claude, OpenAI GPT und Gemini könnte strukturelle Ergänzungen für die Längengeneralisierung benötigen (Signpost-Token oder Äquivalent)
• Multiplizierte CoT-Chain-of-Tools-Ansätze (wie Mistral Vibe oder Anthropic Claude Code Sub-Agents) könnten bereits implizit etwas Ähnliches wie den Signpost-Mechanismus enthalten

Diese Arbeit sollte zusammen mit Branchen-Ankündigungen verfolgt werden — wenn eine zukünftige Flagship-Modell-Ankündigung „neue Positionskodierung” oder „dynamisches Vokabular” erwähnt, ist das wahrscheinlich eine Reaktion auf diese Klasse von theoretischen Problemen.