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

Titel: Het Doorbreken van het Capaciiteitsplafond van LLM Post-Training door Herinvoering van Markov-toestanden

Auteurs: Yurun Yuan en Tengyang Xie (UW-Madison)
Datum: 23 maart 2026

1. Het Probleem: Het "Capaciiteitsplafond" van RL voor LLMs

Hoewel Versterkend Leren (Reinforcement Learning - RL) de standaardparadigma is geworden voor het post-trainen en aligneren van Large Language Models (LLMs), wijst toenemend bewijs op een persistent "capaciiteitsplafond".

• Huidige situatie: In plaats van dat RL nieuwe, fundamentele redeneerstrategieën ontdekt (zoals AlphaZero in bordspellen), fungeert RL voor LLMs voornamelijk als een verfijner van patronen die al latent aanwezig zijn in de vooraf getrainde gewichten.
• De oorzaak: De huidige formulering van RL voor LLMs is gebaseerd op een actie-sequentie (action-sequence). De "toestand" (state) wordt gedefinieerd als de opeenvolging van alle vorige tokens of acties. Dit leidt tot een exponentieel groeiende, ruisrijke geschiedenis die de agent moet verwerken.
• Gevolg: Dit "geschiedenis-als-toestand"-model beperkt de sample-efficiëntie en verhindert dat het model echt nieuwe oplossingsruimtes verkent, waardoor het vastloopt in de prestaties van het basismodel.

2. Methodologie: Herinvoering van expliciete Markov-toestanden

De auteurs stellen voor om een fundamenteel principe uit de klassieke RL-theorie opnieuw toe te passen: het gebruik van expliciete, compacte Markov-toestanden.

• Het Concept: In plaats van de volledige geschiedenis van acties als input te gebruiken, wordt een toestand $s_h$ gedefinieerd die alle informatie bevat die nodig is voor toekomstige beslissingen (de Markov-eigenschap).
• Implementatie:
  • Actie-sequentie model (Huidige standaard): De agent voert actie $a_h$ uit op basis van de geschiedenis $(s_1, a_1, ..., a_{h-1})$.
  • Markov-model (Nieuwe aanpak): De agent voert actie $a_h$ uit op basis van de huidige toestand $s_h$. Na de actie wordt een nieuwe toestand $s_{h+1}$ berekend via een overgangsfunctie $P(s_h, a_h)$.
  • Praktische uitvoering: Omdat LLMs van nature sequentieel werken, wordt een apart toestandsvoorspellingsmodel (een "world model" of state estimator) getraind. Dit model voorspelt de nieuwe toestand (bijv. het nieuwe bordspel-configuration) op basis van de huidige toestand en de uitgevoerde actie. De LLM-policy konditioneert vervolgens op deze voorspelde toestand in plaats van de ruwe tekstgeschiedenis.

3. Theoretische Onderbouwing

Het paper levert rigoureuze theoretische garanties dat deze aanpak de sample-complexiteit drastisch verlaagt:

• Actie-sequentie: De ruimte van mogelijke geschiedenissen groeit exponentieel met de horizon $H$ ($O(|A|^H)$). Om een optimale policy te vinden, moet de agent deze enorme ruimte afdekken, wat leidt tot een onhaalbare sample-complexiteit (bewezen door Foster et al., 2025).
• Markov-aanpak: De toestandruimte groeit lineair of polynomiëel ($O(H)$). Hoewel er een kleine bias wordt geïntroduceerd door het gebruik van een geschatte overgangsfunctie (in plaats van de ware dynamiek), is de winst in sample-efficiëntie exponentieel. De auteurs bewijzen dat de kosten van het afdekken van de toestandruimte veel lager zijn dan de kosten van het afdekken van de geschiedenisruimte.

4. Experimentele Resultaten

De auteurs testen hun methode op een reeks complexe logische puzzels (Sudoku, Sokoban, Futoshiki) met modellen zoals Qwen3-4B en Qwen2.5-3B.

• Prestaties: Markov-modellen overtreffen consistent actie-sequentie-modellen, vooral op moeilijke taken waar de traditionele modellen bijna 0% succes hebben.
  • Voorbeeld: Bij Sokoban steeg het succespercentage van 2,5% (actie-sequentie) naar 76,1% (Markov) voor Qwen3-4B.
• Generalisatie (OOD): Markov-modellen tonen superieure generalisatie naar taken met een hogere structurele complexiteit en diepere zoekdiepte dan tijdens het trainen. Actie-sequentie-modellen falen vaak bij deze uitdagingen.
• Sample-efficiëntie: De trainingscurves tonen aan dat Markov-modellen sneller convergeren en in minder stappen een hogere beloning bereiken.
• Pass@k: Markov-modellen breken het "capaciiteitsplafond" van het basismodel en verbeteren de Pass@k-metriek aanzienlijk, terwijl actie-sequentie-modellen hierin stagneren.

5. Belangrijkste Bijdragen

1. Doorbreken van het plafon: Demonstreert dat het herintroduceren van Markov-toestanden de prestatiegrenzen van standaard RL-post-training doorbreekt op complexe logische taken.
2. Robuuste Generalisatie: Toont aan dat Markov-modellen beter generaliseren naar onbekende, complexere problemen dan modellen die afhankelijk zijn van geschiedenis.
3. Theoretische Garantie: Biedt wiskundige bewijzen dat Markov-lering een exponentieel lagere sample-complexiteit heeft dan actie-sequentie-lering.
4. Praktische Validatie: Levert empirisch bewijs op synthetische benchmarks dat deze benadering werkt met bestaande LLM-architecturen en RL-algoritmen (zoals GRPO).

6. Significantie en Implicaties

Dit paper biedt een fundamentele verschuiving in hoe we RL voor LLMs benaderen:

• Van Geschiedenis naar Structuur: Het suggereert dat de beperkingen van huidige LLMs niet inherent zijn aan de modellen zelf, maar aan de "geschiedenis-als-toestand"-formulering.
• Open-ended Ontdekking: Door de ruis van de geschiedenis te verwijderen en te focussen op de huidige, informatieve toestand, kunnen modellen mogelijk echt nieuwe redeneerpaden ontdekken in plaats van alleen bestaande patronen te versterken.
• Toekomstige Toepassingen: De methode is toepasbaar op diverse domeinen zoals code-debugging (waar de toestand de codebase is), wiskundig redeneren (waar de toestand de gevestigde lemma's zijn), en iteratieve responsverbetering.

Conclusie: Het herintroduceren van Markov-toestanden is een cruciale stap om de "capability ceiling" van LLMs te doorbreken en de weg te effenen voor Artificial General Intelligence (AGI) met echte, open-ended leervermogens.