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

Yurun Yuan; Tengyang Xie

cs.LGMar 20, 2026

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

Authors: Yurun Yuan, Tengyang Xie

Organizations: UW-Madison

Abstract

Reinforcement learning (RL) has become a standard paradigm for post-training and aligning Large Language Models (LLMs), yet recent evidence suggests it faces a persistent "capability ceiling": unlike classical RL systems that discover novel strategies, RL for LLMs often acts as a mere refiner of patterns already latent in pre-trained weights. In this work, we identify a fundamental structural bottleneck: while classical RL relies on compact, informative Markov states, current LLM post-training formulations are tethered to an ever-expanding history of actions. We revisit a classical principle long central to RL yet absent from LLM post-training: explicit Markov states. Theoretically, we provide rigorous guarantees demonstrating that leveraging estimated Markov states can significantly reduce sample complexity. Empirically, we show that introducing Markov states consistently breaks the performance boundaries of standard RL post-training across a suite of complex logic puzzles. Our findings suggest that moving beyond "history-as-state" modeling in favor of structured Markovian representations is essential for unlocking open-ended discovery and genuinely new reasoning capabilities in Generative AI.

Figures & tables

Figure 2

Panel of Figure 3 — Figure 3: Comparison of action-sequence-based models and our Markovian Models. For action-sequence models, the new action ( $a_{h}$ ) is appended to the existing action history and fed back into the model as the input for the subsequent prediction. For Markov models, the next action $a_{h}$ is combined with the current state $s_{h}$ and passed through a state transition function $\mathcal{P}$ to obtain the next state $s_{h+1}$ , which is the input for the subsequent prediction.

Approach	Sudoku	Sokoban	Futoshiki
Qwen3-4B
Action-seq.	92.3	2.5	0.2
Markov	97.1	76.1	75.0

Table 1: Comparison of action-sequence models and Markov models on logical reasoning tasks. Across all tasks, Markov models consistently outperform their action-sequence counterparts by a substantial margin.

Approach	In Distribution						Out Of Distribution
	Sudoku		Sokoban		Futoshiki		Sudoku		Sokoban		Futoshiki
	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass
Qwen3-4B
Action-sequence
+ SFT Warm-up	16.1	98.0	0.2	22.0	0.0	5.0	3.1	64.0	0.0	1.0	0.0	0.0
+ RL post-training	93.5	97.0	2.3	4.0	0.1	7.0	69.2	82.0	0.0	0.0	0.0	0.0

Table 2: Performance comparison of different approaches. We sample

128

solutions per question and report Avg@128 and Pass@128 .

Approach	Sudoku	Sokoban 1	Futoshiki
Qwen3-4B
Action-seq. w/ $A^{*}$	90.8	18.2	54.8
Markov w/ $A^{*}$	97.8	33.0	64.8
Qwen2.5-3B-It
Action-seq. w/ $A^{*}$	28.9	0.2	44.1
Markov w/ $A^{*}$	83.4	94.2	54.2

Table 3: Performance comparison of

\pi_{\mathsf{mkv}}^{A^{\star}}

\pi_{\mathsf{act\textsf{-}seq}}^{A^{\star}}

, and

\pi_{\mathsf{st\textsf{-}act\textsf{-}seq}}^{A^{\star}}

on in-distribution benchmarks.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Pass@

k

accuracy for Qwen3-4B-based models. While action-sequence models rarely improve SFT Pass@

k

, Markov models consistently surpass their base models’ limits.

Figure 8: Training-time success rate during RL post-training.

Figure 9: Training-time success rate during RL post-training for models with access to

A^{\star}

in Section 4.3 .

Approach	Sudoku	Sokoban	Futoshiki
Qwen3-4B
State-action-seq.	89.1	58.2	44.2
History-only	0.0	1.7	0.0
Last-state-only	39.2	3.1	26.6

Appendix

Table 4: Analysis of the focus of the state-action-sequence models. History-only : the model is restricted to previous states and actions without access to the current state. Last-state-only : the model observes only the most recent state. All evaluations are conducted with the ground-truth state transition

\mathcal{P}^{\star}

Figure 10: Ablation on the degree of SFT warm-up dataset. Experiments are conducted with Qwen2.5-3B-It on Sudoku.

Approach	In Distribution						Out Of Distribution
	Sudoku		Sokoban		Futoshiki		Sudoku		Sokoban		Futoshiki
	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass
Qwen3-4B
Action-seq.	76.0	100.0	2.2	79.0	57.9	100.0	35.8	98.0	0.1	10.0	13.0	100.0
Markov	82.4	100.0	56.2	94.0	62.5	100.0	45.1	99.0	13.0	66.0	15.5	99.0
State-Action-seq.	70.4	100.0	53.6	98.0	61.0	100.0	33.1	99.0	14.9	58.0	14.8	100.0

Appendix

Table 5: Performance comparison of different approaches for SFT.

Approach	In Distribution						Out Of Distribution
	Sudoku		Sokoban 1		Futoshiki		Sudoku		Sokoban 1		Futoshiki
	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass	Avg	Pass
Qwen3-4B
Action-seq. w/ $A^{*}$	90.8	93.0	18.2	23.0	54.8	71.0	61.0	78.0	2.7	8.0	11.7	21.0
Markov w/ $A^{*}$	97.8	100.0	33.0	33.0	64.8	73.0	80.9	85.0	4.0	4.0	25.2	35.0
State-Action-seq. w/ $A^{*}$	94.0	98.0	19.8	25.0	51.6	69.0	73.7	83.0	3.9	8.0	14.4	32.0

Appendix

Table 6: Performance comparison of

\pi_{\mathsf{mkv}}^{A^{*}}

\pi_{\mathsf{act\textsf{-}seq}}^{A^{*}}

, and

\pi_{\mathsf{st\textsf{-}act\textsf{-}seq}}^{A^{*}}

to show the difference of their generalization.

Model	Sudoku	Sokoban	Futoshiki
Qwen3-4B	4,000	4,000	4,000
Qwen2.5-3B-It	7,000	6,000	10,000

Appendix

Table 7: SFT warm-up dataset sizes for each model on various tasks.

Model	Sudoku	Sokoban	Futoshiki
Qwen3-4B	18,000	20,000	24,000
Qwen2.5-3B-It	18,000 $\times$ 2	24,000	32,000

Appendix

Table 8: SFT dataset sizes for each model on various tasks used in Section C.5 .

Benchmark	Sudoku	Sokoban	Futoshiki
Train set & ID Tests	Board size: $9\times 9$ Number of blanks: 6	Board size: $9\times 9$ Minimal number of steps: 6–10	Board size: $5\times 5$ Number of blanks: 8–10
OOD Tests	Board size: $9\times 9$ Number of blanks: 10	Board size: $9\times 9$ Minimal number of steps: 12–14	Board size: $5\times 5$ Number of blanks: 12–14

Appendix

Table 9: Configurations of different tasks used in training and testing.

RL for Language Model Reasoning

Reinforcement learning for language model reasoning uses reward-driven training to improve multi-step problem solving, tool use, and reliable answers.

See all 1,094 papers

Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening
Jan 29, 2026Xiaotong Ji, Rasul Tutunov, Matthieu Zimmer +1Efficient Language Model Inference RL for Language Model Reasoning
Huawei Noah’s Ark Lab · UCL Centre for Artificial Intelligence
Understanding Reasoning from Pretraining to Post-Training
Jul 17, 2026Jingyan Shen, Ang Li, Salman Rahman +4Language Model Pretraining RL for Language Model Reasoning
New York University · Columbia University · University of California, Los Angeles +2
Demystifying Reinforcement Learning Post-Training of Language Models
Aug 24, 2026Donovan Clay, Saket Gollapudi, Sankar Harilal +4RL for Language Models RL Post-Training
University of Washington · Allen Institute for AI

Jan 29, 2026J/K move · Enter open · S save

Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening

Xiaotong Ji, Rasul Tutunov, Matthieu Zimmer, Haitham Bou Ammar

Huawei Noah’s Ark Lab · UCL Centre for Artificial Intelligence

Efficient Language Model Inference RL for Language Model Reasoning

Open paper AskPDF arXiv

Reinforcement learning (RL) post-training is a dominant approach for improving the reasoning performance of large language models (LLMs), yet growing evidence suggests that its gains arise primarily from distribution sharpening rather than the acquisition of new capabilities. Recent work has shown that sampling from the power distribution of LLMs using Markov chain Monte Carlo (MCMC) can recover performance comparable to RL post-training without relying on external rewards; however, the high computational cost of MCMC makes such approaches impractical for widespread adoption. In this work, we propose a theoretically grounded alternative that eliminates the need for iterative MCMC. We derive a token-level decomposition of the autoregressive power distribution, showing that the global power distribution can be approximated by a token-level scaled low-temperature one, where the scaling factor captures future trajectory quality. Leveraging this insight, we introduce a training-free and verifier-free algorithm that sharpens the base model's generative distribution autoregressively. Empirically, we evaluate our method on math, QA, and code tasks, and show that our method matches or surpasses one-shot GRPO without relying on any external rewards, while reducing inference latency by over

10\times

compared to MCMC-based sampling.

Abstract

RL for Language Model Reasoning

Explore similar work

Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening

Understanding Reasoning from Pretraining to Post-Training

Demystifying Reinforcement Learning Post-Training of Language Models