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

Sintesi Tecnica: I Transformer con RL o SFT Imparano Provabilmente Funzioni Booleane Sparse, Ma in Modo Diverso

Enunciato del Problema
I Large Language Models (LLM) basati sull'architettura Transformer hanno dimostrato capacità di ragionamento notevoli tramite il prompting Chain-of-Thought (CoT). Sebbene il Fine-Tuning Supervisionato (SFT) e l'Apprendimento per Rinforzo (RL) siano i metodi principali per potenziare tali capacità, i meccanismi teorici alla base delle loro dinamiche di apprendimento rimangono scarsamente compresi. Nello specifico, manca un'analisi rigorosa che confronti come l'RL (in particolare con ricompense di processo) e l'SFT (nello specifico senza teacher forcing) permettano ai Transformer di imparare funzioni booleane complesse e sparse, che altrimenti risultano difficili da apprendere in modo end-to-end. Questo lavoro colma tale lacuna investigando l'apprendibilità di funzioni booleane $k$-sparse—funzioni determinate da un piccolo sottoinsieme di $k$ bit di input—utilizzando un Transformer a un solo strato dotato di passaggi di ragionamento intermedi.

Metodologia
Gli autori propongono un quadro teorico unificato per analizzare le dinamiche di apprendimento sia dell'RL che dell'SFT su una specifica classe di funzioni booleane $k$-sparse. Queste funzioni sono decomponibili ricorsivamente in funzioni booleane fisse 2-sparse (ad esempio, parità, AND, OR), formando una catena di ragionamento analoga al CoT.

1. Architettura del Modello: Lo studio utilizza un Transformer semplificato a un solo strato composto da codifica posizionale, uno strato di auto-attenzione e uno strato feedforward. Il modello è progettato per generare iterativamente passaggi di ragionamento intermedi ($y^{(t)}$) prima di produrre una risposta finale.
2. Maschera "Pre-addestrata": Per garantire la trattabilità teorica e simulare i prior strutturali acquisiti dal pre-addestramento, gli autori impongono una specifica maschera "pre-addestrata" sui pesi dell'attenzione. Questa maschera limita l'attenzione dei token di ragionamento ai loro nodi figli pertinenti (come definito dalla decomposizione ricorsiva) e alla sequenza di input, controllando efficacemente la propagazione degli errori.
3. Paradigmi di Apprendimento:
   • RL con Ricompensa di Processo: Il Transformer è ottimizzato tramite gradiente di politica per massimizzare una funzione di ricompensa in cui le ricompense sono assegnate a ogni passaggio di ragionamento intermedio ($r_t$), anziché solo all'esito finale.
   • SFT senza Teacher Forcing: Il Transformer è addestrato per minimizzare una perdita (hinge loss) sulle catene di ragionamento generate rispetto alle etichette ground-truth. Crucialmente, il modello genera i propri passaggi intermedi durante l'addestramento (generazione autoregressiva) invece di ricevere prefissi ground-truth (teacher forcing), affrontando così il disallineamento tra addestramento e inferenza.
4. Strumento Analitico Centrale: Gli autori introducono un "componente critico del gradiente" ($\gamma$). Dimostrano che la separazione di questo componente—dove il segnale di gradiente per le posizioni pertinenti (nodi figli) è strettamente maggiore rispetto alle posizioni irrilevanti—costituisce una condizione sufficiente per l'apprendibilità provabile.

Contributi Chiave e Risultati
Il lavoro stabilisce le condizioni sufficienti sotto le quali un Transformer a un solo strato può provabilmente imparare funzioni booleane $k$-sparse sia tramite RL che SFT. Le principali scoperte sono:

1. Condizione Unificata di Apprendibilità: Sia l'RL che l'SFT hanno successo se il componente critico del gradiente separa le posizioni pertinenti da quelle irrilevanti. Questa condizione è verificata per tre esempi fondamentali: $k$-PARITÀ, $k$-AND e $k$-OR.
2. Dinamiche di Apprendimento Distinte:
   • RL (Ricompensa di Processo): Sotto la condizione di separazione, l'RL apprende l'intera catena di ragionamento CoT simultaneamente in un singolo aggiornamento del gradiente. La ricompensa di processo fornisce segnali informativi per tutti i passaggi indipendentemente dallo stato corrente degli altri passaggi, permettendo al modello di acquisire immediatamente l'intera capacità di ragionamento.
   • SFT (Nessun Teacher Forcing): Al contrario, l'SFT esibisce un comportamento di apprendimento passo dopo passo. A causa della natura autoregressiva della generazione, il modello non può imparare in modo affidabile il passaggio $t$ finché il passaggio $t-1$ non è generato correttamente. Di conseguenza, l'SFT richiede $T$ aggiornamenti del gradiente (dove $T$ è la lunghezza della catena) per imparare l'intera catena, risolvendo un passaggio per aggiornamento.
3. Difficoltà della Ricompensa Finale: Il lavoro dimostra che l'RL ottimizzato con una sola ricompensa finale (basata sull'esito) fallisce nell'imparare efficientemente queste funzioni. La varianza del gradiente di politica è esponenzialmente piccola, sommergendo il segnale nel rumore, il che spiega la necessità di ricompense di processo per compiti di ragionamento complessi.
4. Estensione al CoT Seriale: L'analisi è estesa oltre la decomposizione ad albero binario alle strutture CoT seriali (comuni negli LLM pratici), confermando che le stesse dinamiche di apprendimento (simultanea per l'RL, passo-passo per l'SFT) valgono sotto un'adeguata mascheratura.

Significato e Affermazioni
Gli autori affermano che questo lavoro fornisce la prima caratterizzazione teorica delle dinamiche di apprendimento dell'RL con ricompense di processo per i Transformer, colmando una lacuna critica nella letteratura. Rimuovendo il teacher forcing e le strategie di aumento dei dati spesso utilizzate in lavori teorici precedenti (ad esempio, Kim & Suzuki, 2025), lo studio offre un confronto più realistico tra RL e SFT.

Il significato risiede nel rivelare che, sebbene entrambi i metodi possano raggiungere l'apprendibilità, lo fanno attraverso meccanismi fondamentalmente diversi:

• L'RL con ricompense di processo imita l'efficienza dell'SFT con teacher forcing imparando l'intera catena simultaneamente.
• L'SFT senza teacher forcing induce naturalmente un curriculum passo-passo, una proprietà intrinseca dell'addestramento autoregressivo che non richiede curriculum learning esterno o filtraggio dei dati.

Il lavoro conclude che i confronti empirici tra RL e SFT devono controllare attentamente fattori come la progettazione della ricompensa (processo vs esito) e i regimi di addestramento (teacher forcing vs generazione autoregressiva), poiché questi fattori alterano significativamente le dinamiche di apprendimento e possono confondere il confronto dei metodi di ottimizzazione stessi.