Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States

1. Il Problema: Il "Tetto delle Capacità" nel Post-Training RL

Il paper identifica un limite fondamentale nell'attuale paradigma di addestramento per il Reinforcement Learning (RL) applicato ai Large Language Models (LLM). Sebbene il RL sia diventato lo standard per l'allineamento e il miglioramento delle capacità di ragionamento (es. DeepSeek-R1, OpenAI o1), le evidenze suggeriscono che spesso agisce solo come un "raffinatore" di pattern già latenti nei pesi pre-addestrati, piuttosto che come un motore per la scoperta di nuove strategie.

Il problema strutturale risiede nella formulazione dello stato nell'RL per LLM:

• Approccio attuale (History-as-State): Lo stato è definito come la concatenazione di tutte le azioni (token) precedenti. Questo crea uno spazio degli stati che cresce esponenzialmente con la lunghezza dell'orizzonte temporale ($H$), rendendo il problema intrattabile per l'esplorazione efficiente.
• Conseguenza: L'RL fatica a scoprire soluzioni che esulano dalla copertura del modello base (pass@k), poiché deve esplorare uno spazio di storia enorme. Questo porta a un "tetto delle capacità" (capability ceiling) dove l'RL non riesce a espandere significativamente lo spazio delle soluzioni oltre i limiti del pre-training.

2. Metodologia: Reintroduzione degli Stati Markoviani

Gli autori propongono di abbandonare la modellazione basata sulla storia completa a favore di stati Markoviani espliciti, un principio centrale nell'RL classico (es. AlphaZero, MuZero) ma assente nell'RL per LLM.

L'Approccio Proposto:
Invece di fornire al modello l'intera sequenza di azioni passate ($a_1, ..., a_{h-1}$), il sistema utilizza una funzione di transizione di stato (o un modello appreso) per calcolare lo stato corrente $s_h$ basato sullo stato precedente e l'azione corrente.

• Input del modello: Solo lo stato corrente $s_h$ (es. la configurazione attuale della scacchiera, il codice corrente, la prova matematica aggiornata).
• Output del modello: La prossima azione $a_h$.
• Transizione: $s_{h+1} = P(s_h, a_h)$.

Implementazione Sperimentale:

• Ambienti: Il lavoro utilizza tre giochi logici sintetici con stati Markoviani ben definiti: Sudoku, Sokoban e Futoshiki.
• Architettura: Vengono confrontati tre modelli:
  1. Action-Sequence (Baseline): Input = storia completa delle azioni.
  2. Markov (Proposta): Input = stato corrente estratto dall'ambiente (o stimato).
  3. State-Action-Sequence: Input = storia completa di stati e azioni (per isolare l'effetto della struttura Markoviana).
• Algoritmo: Utilizzo di GRPO (Group Relative Policy Optimization) e PPO su modelli Qwen (3B e 4B).

3. Contributi Chiave

1. Rottura del Tetto delle Capacità: Dimostrazione empirica che l'uso di stati Markoviani permette ai modelli di superare i limiti di performance dei modelli basati sulla storia, raggiungendo tassi di successo elevati in compiti dove le baseline falliscono completamente.
2. Garantire l'Efficienza Campionaria (Sample Efficiency): Fornisce garanzie teoriche rigorose che dimostrano come l'apprendimento Markoviano riduca drasticamente la complessità campionaria rispetto alle formulazioni basate sulla storia.
3. Generalizzazione Robusta (OOD): I modelli Markoviani mostrano una capacità superiore di generalizzare a compiti fuori distribuzione (OOD) con maggiore complessità strutturale e profondità di ricerca rispetto a quelli addestrati.

4. Risultati Sperimentali

I risultati sono presentati su task logici complessi (Sudoku, Sokoban, Futoshiki) con modelli Qwen3-4B e Qwen2.5-3B-It:

• Performance ID (In-Distribution):
  • Su Sokoban e Futoshiki, i modelli basati sulla storia (Action-Seq) hanno mostrato un'accuratezza vicina allo 0% (es. 2.5% su Sokoban).
  • I modelli Markov hanno raggiunto accurazioni elevate (es. 76.1% su Sokoban, 75.0% su Futoshiki), superando di gran lunga le baseline.
• Performance OOD (Out-of-Distribution):
  • I modelli Markov hanno generalizzato efficacemente a puzzle più difficili e profondi, mantenendo alte performance, mentre le baseline sono collassate.
• Efficienza di Addestramento:
  • Le curve di reward mostrano che i modelli Markov convergono più velocemente e raggiungono reward più alti con meno step di addestramento, confermando la minore complessità campionaria.
• Analisi Teorica:
  • Il paper dimostra che la complessità del rapporto di densità negli spazi di storia è esponenziale ($O(|A|^H)$), mentre negli spazi Markoviani è lineare ($O(H)$). Questo spiega perché l'RL basato sulla storia richiede una copertura esponenziale per trovare politiche ottimali.

5. Significato e Implicazioni

Il lavoro suggerisce che il "tetto delle capacità" osservato nell'RL per LLM non è un limite intrinseco dell'intelligenza artificiale, ma un artefatto strutturale della formulazione "storia come stato".

• Cambiamento di Paradigma: Per sbloccare capacità di ragionamento aperte e nuove scoperte, è necessario passare da una modellazione basata sulla sequenza di token a una basata su stati strutturati e Markoviani.
• Applicabilità Reale: Questo approccio è rilevante per scenari reali come il debug del codice (dove lo stato è lo snapshot del codice e dei log), il ragionamento matematico (dove lo stato è l'insieme dei lemmi provati) e la raffinazione iterativa delle risposte.
• Futuro dell'AGI: L'integrazione di stati Markoviani espliciti è presentata come un passo necessario verso un'Intelligenza Artificiale Generale (AGI) capace di crescita delle capacità continua e scoperta di nuove strategie, superando i limiti dell'esplorazione casuale su spazi di storia infiniti.

In sintesi, il paper sostiene che reintrodurre la struttura Markoviana, spesso trascurata nell'era dei LLM, è la chiave per trasformare l'RL da un semplice ottimizzatore di pattern a un vero motore di scoperta logica.