📊 statistics

Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

Dieser Artikel zeigt theoretisch, dass zwar sowohl Reinforcement Learning mit Prozessbelohnungen als auch supervised Fine-Tuning einlagigen Transformern ermöglichen, nachweislich sparse boolesche Funktionen mittels Chain-of-Thought-Argumentation zu erlernen, sie sich jedoch grundlegend in ihren Lern dynamiken unterscheiden, wobei RL die gesamte Argumentationskette simultan erwirbt, während SFT sie schrittweise lernt.

Ursprüngliche Autoren: Bochen Lyu, Yiyang Jia, Xiaohao Cai, Zhanxing Zhu

Veröffentlicht 2026-05-27

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Bochen Lyu, Yiyang Jia, Xiaohao Cai, Zhanxing Zhu

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 haben einen sehr intelligenten, aber leicht verwirrten Roboter (einen Transformer), der ein komplexes Rätsel lösen muss. Das Rätsel ist eine Boolesche Funktion, was einfach eine logische Aufgabe ist, bei der die Antwort entweder „Ja" (+1) oder „Nein" (-1) lautet. Konkret untersucht der Artikel „sparse" (spärliche) Rätsel, was bedeutet, dass die Antwort nur von wenigen spezifischen Informationen abhängt, die sich unter viel Rauschen verstecken.

Um diese Rätsel zu lösen, verwendet der Roboter eine Strategie namens Chain-of-Thought (CoT). Anstatt direkt zur Antwort zu springen, zerlegt er das Problem in eine Reihe kleiner, Zwischenschritte, ähnlich wie ein Mensch, der ein mathematisches Problem schrittweise auf einem Kladdepapier durchdenkt.

Der Artikel untersucht zwei verschiedene Wege, diesen Roboter im effektiven Einsatz von CoT zu unterrichten: Supervised Fine-Tuning (SFT) und Reinforcement Learning (RL). Die Autoren beweisen, dass beide Methoden funktionieren, aber den Roboter auf grundlegend unterschiedliche Weise unterrichten.

Hier ist die Aufschlüsselung mit einfachen Analogien:

1. Das Rätsel: Rekursive Zerlegung

Stellen Sie sich das Rätsel als einen riesigen Baum vor. Um die Antwort oben zu finden, müssen Sie unten kleine 2-teilige Logikprobleme lösen, dann diese Antworten kombinieren, um etwas größere 2-teilige Probleme zu lösen, und so weiter, bis Sie ganz nach oben gelangen.

Das Ziel: Der Roboter muss lernen, bei jedem Schritt nur auf die zwei spezifischen Informationen (die „relevanten" Blätter) zu achten, die für diesen Schritt benötigt werden, und den Rest des Rauschens zu ignorieren.

2. Die zwei Lehrer

Lehrer A: Der strenge Drill instructor (SFT)

Supervised Fine-Tuning (SFT) ist wie ein Lehrer, der dem Roboter den perfekten Lösungsschlüssel für jeden einzelnen Schritt des Rätsels gibt.

Wie es funktioniert: Der Lehrer sagt: „Für Schritt 1 ist die Antwort X. Für Schritt 2 ist die Antwort Y."
Der Haken: Der Roboter muss die Antwort für Schritt 2 basierend auf dem, was er gerade für Schritt 1 geschrieben hat, generieren.
Das Ergebnis (Schritt-für-Schritt-Lernen): Der Artikel beweist, dass dieser Roboter einen Schritt nach dem anderen lernt.
- Analogie: Stellen Sie sich vor, Sie versuchen, eine Tanzroutine zu lernen. Wenn Sie den ersten Move vermasseln, können Sie den zweiten Move nicht lernen, weil Ihre Ausgangsposition falsch ist. Der Roboter muss Schritt 1 perfekt beherrschen, bevor er überhaupt beginnen kann, Schritt 2 zu lernen. Es dauert eine Trainingseinheit, um Schritt 1 zu korrigieren, dann eine weitere Sitzung für Schritt 2, und so weiter. Es ist ein langsamer, linearer Prozess.

Lehrer B: Der Prozess-Trainer (RL mit Prozess-Belohnungen)

Reinforcement Learning (RL) ist wie ein Trainer, der nicht nur auf das Endergebnis schaut, sondern Feedback zu jedem einzelnen Move gibt, den der Roboter macht.

Wie es funktioniert: Der Roboter versucht, das Rätsel zu lösen. Wenn er einen kleinen Schritt richtig macht, erhält er sofort eine „gut gemacht"-Belohnung vom Trainer. Wenn er es falsch macht, erhält er eine Strafe.
Das Ergebnis (Simultanes Lernen): Der Artikel beweist, dass dieser Roboter die gesamte Kette von Schritten auf einmal lernt.
- Analogie: Stellen Sie sich einen Trainer vor, der gleichzeitig ruft: „Gute Fußarbeit bei Move 1! Gute Handposition bei Move 5! Schlechter Ellbogen bei Move 3!" Weil der Roboter spezifisches Feedback für jeden einzelnen Schritt erhält, unabhängig davon, ob die vorherigen Schritte perfekt waren, kann er seine gesamte Routine in einer einzigen Trainingseinheit anpassen. Er lernt den ganzen Tanz gleichzeitig.

3. Die große Entdeckung: „Prozess" vs. „Ergebnis"

Der Artikel hebt einen entscheidenden Unterschied hervor, wie diese Lehrer Feedback geben:

SFT verlässt sich auf die eigene vorherige Ausgabe des Roboters. Wenn der Roboter am Anfang falsch liegt, wird die „Wahrheit" (Ground Truth) für den nächsten Schritt zu verwirrendem Rauschen. Dies erzwingt das schrittweise Lernen.
RL (speziell mit Prozess-Belohnungen) gibt dem Roboter die korrekte „Wahrheit" für jeden Schritt unabhängig. Es spielt keine Rolle, ob der Roboter Schritt 1 vermasselt hat; der Trainer weiß immer noch, was Schritt 2 hätte sein sollen, und belohnt/bestraft entsprechend. Dies ermöglicht das „alles-auf-einmal"-Lernen.

4. Was ist mit den „schwierigen" Rätseln?

Der Artikel testete dies an drei spezifischen Arten von Logikrätseln:

k-PARITY: Wie das Prüfen, ob eine Gruppe von Schaltern eine gerade oder ungerade Anzahl von „eingeschalteten" Positionen hat. (Dies ist für KI ohne Hilfe berüchtigt schwer zu lernen).
k-AND: Prüfen, ob alle spezifischen Schalter „eingeschaltet" sind.
k-OR: Prüfen, ob mindestens einer spezifische Schalter „eingeschaltet" ist.

Der Artikel beweist mathematisch, dass für alle drei dieser Rätsel beide Unterrichtsmethoden funktionieren, vorausgesetzt, der Roboter kann zwischen den „wichtigen" Informationen und dem „Rauschen" unterscheiden.

Zusammenfassung der Ergebnisse

Beide funktionieren: Sie können einen Transformer entweder mit SFT oder RL komplexes logisches Denken beibringen.
Sie sind unterschiedlich:
- SFT ist wie ein Schüler, der die Grundlagen beherrschen muss, bevor er weitergeht. Es lernt schrittweise.
- RL (mit Prozess-Belohnungen) ist wie ein Schüler, der sofortiges Feedback zu jedem einzelnen Teil des Problems erhält. Es lernt die gesamte Kette gleichzeitig.
Die Warnung: Wenn Sie SFT und RL im echten Leben vergleichen, müssen Sie vorsichtig sein. Wenn Sie ändern, wie der Lehrer Feedback gibt (z. B. nur eine „Endbelohnung" am Ende statt „Prozess-Belohnungen" bei jedem Schritt), ändert sich das Lernverhalten völlig. Der Artikel schlägt vor, dass der Vergleich dieser beiden Methoden erfordert, die Art und Weise, wie die Belohnungen gestaltet sind, zu kontrollieren, nicht nur die Methode selbst.

Kurz gesagt zeigt der Artikel, dass zwar beide Methoden einem Roboter beibringen können, logisch zu denken, sie dies jedoch mit unterschiedlichen „Lerngeschwindigkeiten" und „Unterrichtsstilen" tun, und das Verständnis dieser Unterschiede ist der Schlüssel zum Aufbau besserer KI.

Technische Zusammenfassung: Transformer mit RL oder SFT lernen nachweislich sparse boolesche Funktionen, aber auf unterschiedliche Weise

Problemstellung
Large Language Models (LLMs), die auf der Transformer-Architektur basieren, haben durch Chain-of-Thought (CoT)-Prompting bemerkenswerte Schlussfolgerungsfähigkeiten unter Beweis gestellt. Während Supervised Fine-Tuning (SFT) und Reinforcement Learning (RL) die primären Methoden zur Verbesserung dieser Fähigkeiten sind, bleiben die theoretischen Mechanismen, die ihren Lernverhalten zugrunde liegen, weitgehend unverstanden. Insbesondere fehlt es an einer rigorosen Analyse, die vergleicht, wie RL (insbesondere mit Prozessbelohnungen) und SFT (speziell ohne Teacher Forcing) Transformer befähigen, komplexe, sparse boolesche Funktionen zu lernen, die andernfalls schwer end-to-end zu erlernen sind. Diese Arbeit schließt diese Lücke, indem sie die Lernbarkeit von $k$ -sparse booleschen Funktionen untersucht – Funktionen, die durch eine kleine Teilmenge von $k$ Eingabebits bestimmt werden – unter Verwendung eines einlagigen Transformers mit intermediären Schlussfolgerungsschritten.

Methodik
Die Autoren schlagen einen einheitlichen theoretischen Rahmen vor, um die Lernverhalten von RL und SFT an einer spezifischen Klasse von $k$ -sparse booleschen Funktionen zu analysieren. Diese Funktionen lassen sich rekursiv in feste 2-sparse boolesche Funktionen (z. B. Parität, UND, ODER) zerlegen und bilden eine Schlussfolgerungskette, die CoT ähnelt.

Modellarchitektur: Die Studie nutzt einen vereinfachten einlagigen Transformer, bestehend aus Positionskodierung, einer Self-Attention-Schicht und einer Feedforward-Schicht. Das Modell ist so konzipiert, dass es iterativ intermediäre Schlussfolgerungsschritte ( $y^{(t)}$ ) generiert, bevor es eine endgültige Antwort liefert.
„Vortrainierte" Maske: Um die theoretische Handhabbarkeit zu gewährleisten und die durch Vortraining gewonnenen strukturellen Priors zu simulieren, legen die Autoren eine spezifische „vortrainierte" Maske auf die Attention-Gewichte auf. Diese Maske beschränkt die Aufmerksamkeit von Schlussfolgerungstokens auf ihre relevanten Kindknoten (wie durch die rekursive Zerlegung definiert) und die Eingabesequenz, wodurch die Fehlerausbreitung effektiv kontrolliert wird.
Lernparadigmen:
- RL mit Prozessbelohnung: Der Transformer wird mittels Policy Gradient optimiert, um eine Belohnungsfunktion zu maximieren, bei der Belohnungen jedem intermediären Schlussfolgerungsschritt ( $r_t$ ) zugewiesen werden, nicht nur dem Endergebnis.
- SFT ohne Teacher Forcing: Der Transformer wird trainiert, einen Verlust (Hinge-Verlust) über generierte Schlussfolgerungsketten im Vergleich zu Ground-Truth-Labels zu minimieren. Entscheidend ist, dass das Modell während des Trainings eigene intermediäre Schritte generiert (autoregressive Generierung), anstatt Ground-Truth-Präfixe zu erhalten (Teacher Forcing), wodurch die Diskrepanz zwischen Training und Inferenz adressiert wird.
Kernanalytisches Werkzeug: Die Autoren führen eine „kritische Gradientenkomponente" ( $\gamma$ ) ein. Sie zeigen, dass die Trennung dieser Komponente – wobei das Gradientensignal für relevante Positionen (Kindknoten) strikt größer ist als für irrelevante Positionen – als hinreichende Bedingung für nachweisbare Lernbarkeit dient.

Hauptbeiträge und Ergebnisse
Die Arbeit stellt hinreichende Bedingungen auf, unter denen ein einlagiger Transformer $k$ -sparse boolesche Funktionen sowohl über RL als auch über SFT nachweislich lernen kann. Die wichtigsten Erkenntnisse sind:

Einheitliche Lernbarkeitsbedingung: Sowohl RL als auch SFT sind erfolgreich, wenn die kritische Gradientenkomponente relevante von irrelevanten Positionen trennt. Diese Bedingung wird für drei grundlegende Beispiele verifiziert: $k$ -PARITY, $k$ -UND und $k$ -ODER.
Unterschiedliche Lernverhalten:
- RL (Prozessbelohnung): Unter der Trennungsbedingung lernt RL die gesamte CoT-Schlussfolgerungskette gleichzeitig in einem einzigen Gradientenupdate. Die Prozessbelohnung liefert informative Signale für alle Schritte, unabhängig vom aktuellen Zustand anderer Schritte, was dem Modell ermöglicht, die gesamte Schlussfolgerungsfähigkeit sofort zu erwerben.
- SFT (ohne Teacher Forcing): Im Gegensatz dazu zeigt SFT ein schrittweises Lernverhalten. Aufgrund der autoregressiven Natur der Generierung kann das Modell Schritt $t$ nicht zuverlässig lernen, bis Schritt $t-1$ korrekt generiert wurde. Folglich erfordert SFT $T$ Gradientenupdates (wobei $T$ die Kettenlänge ist), um die gesamte Kette zu lernen, und löst dabei pro Update einen Schritt.
Schwierigkeit der finalen Belohnung: Die Arbeit beweist, dass RL, das nur mit einer finalen (ergebnisbasierten) Belohnung optimiert wird, diese Funktionen nicht effizient lernen kann. Die Varianz des Policy Gradienten ist exponentiell klein und ertränkt das Signal im Rauschen, was die Notwendigkeit von Prozessbelohnungen für komplexe Schlussfolgerungsaufgaben erklärt.
Erweiterung auf serielle CoT: Die Analyse wird über die Binärbaum-Zerlegung hinaus auf serielle CoT-Strukturen (häufig in praktischen LLMs) erweitert und bestätigt, dass dieselben Lernverhalten (gleichzeitig für RL, schrittweise für SFT) unter geeigneter Maskierung gelten.

Bedeutung und Behauptungen
Die Autoren behaupten, dass diese Arbeit die erste theoretische Charakterisierung der Lernverhalten von RL mit Prozessbelohnungen für Transformer liefert und eine kritische Lücke in der Literatur schließt. Durch den Verzicht auf Teacher Forcing und Daten-Augmentierungsstrategien, die in früheren theoretischen Arbeiten häufig verwendet wurden (z. B. Kim & Suzuki, 2025), bietet die Studie einen realistischeren Vergleich zwischen RL und SFT.

Die Bedeutung liegt darin, aufzudecken, dass beide Methoden zwar Lernbarkeit erreichen können, dies jedoch durch grundlegend unterschiedliche Mechanismen tun:

RL mit Prozessbelohnung imitiert die Effizienz von SFT mit Teacher Forcing, indem es die gesamte Kette gleichzeitig lernt.
SFT ohne Teacher Forcing induziert natürlicherweise ein schrittweises Curriculum, eine inhärente Eigenschaft des autoregressiven Trainings, die kein externes Curriculum-Learning oder Datenfiltern erfordert.

Die Arbeit schließt, dass empirische Vergleiche zwischen RL und SFT Faktoren wie Belohnungsdesign (Prozess vs. Ergebnis) und Trainingsregime (Teacher Forcing vs. autoregressive Generierung) sorgfältig kontrollieren müssen, da diese Faktoren die Lernverhalten erheblich verändern und den Vergleich der Optimierungsmethoden selbst verfälschen können.