Reproduce “Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States” on OpenResearch

About this paper

Yurun Yuan, Tengyang Xie

Large Language Model (LLM) post-training can achieve expanded reasoning capabilities and enhanced generalization by reintroducing explicit Markov states, moving beyond the "history-as-state" paradigm. This approach, developed at UW-Madison, led to superior performance and sample efficiency on logical reasoning tasks like Sudoku, Sokoban, and Futoshiki, with one model achieving 75.0% Avg@128 on Futoshiki.

Key insights

• The "history-as-state" paradigm imposes an exponential increase in sample complexity, fundamentally limiting an LLM's ability to expand its solution space during post-training.
• Explicit Markov state representations drastically reduce sample complexity and variance, enabling LLMs to learn more efficiently and generalize more robustly to unseen problems.
• Markov states allow LLMs to overcome the observed "capability ceiling" by fostering genuine discovery and new reasoning capabilities, rather than just refining existing ones.

Summary by alphaXiv.