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

Yurun Yuan; Tengyang Xie

Source-linked AI summary

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

Yurun Yuan, Tengyang Xie

arXiv:2603.19987v1Mar 20, 2026cs.LGcs.AIcs.CL

TL;DR

LLM post-training RL often remains tied to action histories and refines capabilities already reachable by the base model. The paper reintroduces estimated Markov states, proving sample-efficiency benefits and showing consistent gains across complex logic puzzles. It argues that structured Markovian representations may support more open-ended capability growth.

Problem
Current LLM RL often reweights latent reasoning patterns rather than creating genuinely novel capabilities, while action-sequence formulations use expanding histories instead of compact Markov states.
Method
The paper introduces explicit Markov-state estimation into LLM post-training and evaluates it theoretically and empirically against history-dependent formulations.
Results
Markov-state models consistently surpass traditional RL post-training on complex logic puzzles, with significantly lower sample complexity theoretically and stronger OOD generalization empirically.
Takeaways & Limitations
The findings suggest moving beyond history-as-state modeling toward structured Markovian representations for complex reasoning and more scalable capability growth.
Takeaways & Limitations
The reported additional Sokoban results use lower-complexity tasks because of base-model capability constraints, and one improvement incurs an additive bias term O.

Abstract

from arXiv · show

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.

1 Introduction

The paper identifies a capability ceiling in LLM post-training: current history-dependent RL often refines existing behaviors rather than discovering genuinely new strategies. It proposes explicit Markov states as a structural remedy, supported by theoretical sample-efficiency guarantees and logic-puzzle results.

Current evidence suggests RL mainly sharpens reasoning patterns already latent in base models instead of creating fundamentally novel capabilities.
The capability ceiling may arise from LLM–RL formulations rather than from RL itself, since classical systems have discovered strategies absent from their initial training.
LLM post-training represents state as an expanding history of tokens, whereas classical RL uses compact Markov states containing information needed for future decisions.
The paper revisits explicit Markov-state estimation and combines theoretical foundations with empirical evidence on complex logic puzzles.
Markov-state models consistently surpass traditional history-dependent RL on complex logic puzzles and show stronger out-of-distribution generalization.
The theoretical analysis reports significantly lower sample complexity for Markovian learning than for standard action-sequence formulations.

2 Preliminaries

The preliminaries formalize finite-horizon Markov decision processes, policies, rewards, value functions, and KL-regularized objectives. They then map language-model prompts and generated tokens onto states and actions, covering PPO and GRPO as standard post-training frameworks.

2.1 Markov Decision Process, Policies, and Value Functions: A finite-horizon MDP comprises layered states, actions, transition probabilities, rewards, and an initial-state distribution.
2.1 Markov Decision Process, Policies, and Value Functions: A policy maps states to action distributions and induces trajectories through repeated action selection, reward collection, and environment transitions.
2.1 Markov Decision Process, Policies, and Value Functions: The objective is to maximize expected cumulative reward, with value, Q-, and advantage functions characterizing policy performance and action benefits.
2.2 Reinforcement Learning for Language Models: For language models, the model is the policy, prompts map to initial states, and output tokens serve as sequential actions.
2.2 Reinforcement Learning for Language Models: KL regularization encourages the learned policy to remain close to a reference policy, controlled by β > 0.
2.2 Reinforcement Learning for Language Models: PPO and GRPO are primary post-training frameworks using clipped policy-update objectives; GRPO normalizes response-level rewards within prompt groups.

3 Reintroducing Markov States to LLM Post-Training

The paper argues that action-sequence formulations create a structural bottleneck for LLM post-training, whereas explicit Markov states provide compact inputs that support more efficient learning. A didactic task and logical reasoning experiments show Markov-based models outperform action-sequence models.

Didactic Example: In the Combination Lock task, the Markov agent stabilizes within 30k training steps, while the action-sequence agent fails to reach the goal after 800k steps.Both agents use MLPs and Deep Q-Learning, and evaluation measures final-goal success and furthest state reached.
Didactic Example: The Markov agent receives one of only H distinct state inputs, whereas the action-sequence agent operates over full action histories.This input-space difference is identified as essential for solving the Combination Lock task efficiently.
Markov State Estimation: Markovian models combine the current state sh with action ah, apply transition function P, and use the resulting state sh+1 for the next decision.The transition may be implemented by an environment, a rule-based mechanism, or a learned approximation of the dynamics.
Empirical Evidence: Across Sudoku, Sokoban, and Futoshiki, Markov models consistently outperform action-sequence counterparts when trained with the same RL algorithm.The experiments use synthetic, controllable tasks with well-defined Markov state representations.

4 Experiments

The experiments compare Markov and action-sequence post-training across synthetic logic puzzles, evaluating in-distribution and harder out-of-distribution performance. Markov models improve accuracy, extend capability boundaries, converge faster, and benefit from both explicit states and Markovian policy structure.

Experimental Setup: Experiments use Sudoku, Sokoban, and Futoshiki, training Markov and action-sequence models with the same RL algorithm and separate state-transition estimation models.The models are evaluated on synthetic, controllable tasks with well-defined Markov state representations.
Evaluation: Models are evaluated on in-distribution tests and harder out-of-distribution benchmarks requiring more decision steps, using Avg@128 and Pass@128 from 128 sampled solutions.Avg@128 is mean success across samples; Pass@128 is the probability that at least one sample is correct.
Main Results: πmkv consistently improves one-shot accuracy and Pass@128 across both settings, outperforming action-sequence models on every OOD task.The largest gains occur on challenging tasks where πact-seq has near-zero performance, including Sokoban and Futoshiki for Qwen3-4B.
Main Results: Markov models extend Pass@k beyond base-model boundaries, whereas action-sequence models rarely improve or maintain SFT Pass@k on Qwen3-4B Futoshiki.The Futoshiki result is presented as an example of shifted capability boundaries.
Training Efficiency: Markov models reach higher rewards in fewer training steps, providing empirical evidence of lower sample complexity.Representative training curves use Sudoku with Qwen3-4B and Futoshiki with Qwen2.5-3B-Instruct.
Factors Behind the Success of Markov Models: Comparisons show that explicit Markov-state access improves performance, while enforcing a Markovian policy structure provides additional gains over state-action-sequence models.State-action-sequence models expose true state sequences but still condition on entire trajectories, isolating the effects of state access and Markov structure.
Additional Results: Additional analyses report faster convergence and higher rewards with fewer SFT initialization steps, while the Markov property has limited effect under supervised fine-tuning alone.The paper also examines Markov states in purely supervised settings.

5 Theoretical Analysis

The analysis compares action-sequence and approximate Markovian learning, showing that Markov states replace exponential history coverage with compact-state coverage at the cost of transition-model bias.

Assumptions and guarantees: Theoretical guarantees are derived under deterministic transitions, bounded rewards, optimization-error assumptions, advantage-estimation assumptions, and transition-model accuracy for Markovian learning.The guarantees are stated in Propositions 1 and 2, with proofs deferred to Appendix B.3.
Learning paradigms: Action-sequence learning conditions on the initial state and complete action history, whereas approximate Markovian learning conditions on learned states generated by an approximate transition function.The approximate state is updated recursively and can come from a learned world model or rule-based state extractor.
Action-sequence complexity: Full-history density ratios span a space growing exponentially with horizon H, requiring prohibitive sample complexity that essentially scales as |A|^H.The analysis links this requirement to worst-case coverage of an exponentially large history space.
Markovian complexity: Approximate Markovian bounds depend on density ratios over estimated states, yielding an exponential variance reduction when the true task has compact state structure.The compact-state condition may be polynomial in H, making the relevant ratio easier to bound.
Trade-off: Markovian learning trades the exponential history-coverage cost for an additive bias term O(·) controlled by transition-model accuracy.The paper characterizes this as a favorable trade-off between polynomial transition approximation and exponential exploration or coverage costs.

6 Conclusion

The conclusion positions explicit Markov states as a way to address the history-as-state bottleneck in LLM post-training, while distinguishing this focus from related reasoning and context-management approaches.

6 Conclusion: The paper reintroduces Markov states into LLM post-training and reports their potential to overcome contemporary post-training performance plateaus.It frames this direction as motivation for future work on Markovian structure in complex real-world tasks.
Context management: Existing context compression and memory methods shorten histories, but compression alone does not guarantee a sufficient statistic for optimal future control.The paper requires histories mapped to the same state to have identical conditional transition and reward distributions.
Related reasoning methods: Related Markovian reasoning methods decompose problems or constrain reasoning into fixed-size chunks, whereas this work studies Markov-state benefits without additional assumptions on state-generation methods.The comparison distinguishes the paper’s systematic analysis from specific mechanisms for producing textual states.
Policy optimization: The paper’s policy-optimization protocol updates policies using an approximated advantage function and encompasses multiple popular algorithms.The protocol initializes a policy, iterates advantage estimation and optimization, and returns the resulting policy sequence.
Theoretical framing: The analysis defines the essential state as the full action history for action-sequence learning and as the approximate state for Markovian learning.This notation supports the comparison of the two learning paradigms in the theoretical objectives and proofs.

B.4 Illustration of the Theoretical Analysis with Combination Lock

The Combination Lock illustration contrasts an exponentially growing history tree with a compact Markov state chain, explaining the resulting difference in coverage requirements.

History-tree representation: Action-sequence learning represents each unique move sequence as a distinct history-tree node, so its state space grows as O(|A|^H).Optimal-policy learning therefore requires exponential history coverage.
State-chain representation: Markovian learning maps different action histories to states in a linear chain of length H, so its state space grows as O(H).The paper states that linear coverage is sufficient for convergence in this representation.

B.5 Proofs for Supporting Lemmas

The supporting material includes an induction proof framework and empirical Pass@k comparisons showing that Markov models extend performance on harder logic tasks where action-sequence models plateau.

B.5 Proofs: The proof of the supporting performance-difference lemma proceeds by induction, beginning with the trivial H = 1 case and expanding the H = k + 1 return difference.The two resulting terms are bounded and summed to conclude the proof.
Pass@k Performance: On Sokoban and Futoshiki, action-sequence models fail to extend or maintain SFT Pass@k, while Markov models extend the base models’ Pass@k beyond their capability boundaries.The contrast is strongest on the more difficult tasks.

C.2 Training Success Rate

Training-time results show that Markov models generally learn faster and reach higher final success rates than action-sequence models. State-action-sequence models benefit from Markov states but still retain a performance gap.

Markov models converge faster and achieve higher final success rates than action-sequence models across nearly all tasks and model variants.
Introducing Markov states partially alleviates the slow-growth issue of state-action-sequence variants, but their performance remains below Markov models.
Figure 8 reports training-time success rates during RL post-training.
Figure 9 reports corresponding training dynamics for models with access to A⋆ in Section 4.3.

C.4 Ablation on the Degree of SFT Warm-up

The SFT warm-up ablation examines how initialization affects subsequent RL post-training. With more SFT, the state-action-sequence model gradually internalizes Markov structure and matches the Markov baseline, while Markov states also benefit supervised learning most on Sokoban.

As the SFT fraction increases, the state-action-sequence model gradually internalizes the environment’s Markov structure and matches the Markov baseline.
Action-sequence models consistently perform worse than Markov and state-action-sequence models in supervised learning, especially on Sokoban.
Explicit predicted states reduce the need to reconstruct current board configurations in latent space, offloading state tracking and prediction.
The Markov property is less critical in supervised learning because SFT uses fixed offline trajectories rather than exploratory discovery.

C.6 Evaluation Results of Models with Access to A⋆

This section evaluates models with access to A⋆ and illustrates their decision behavior on Sudoku. The examples contrast immediate-action prompting with reasoning traces that forecast future board states holistically.

The evaluation compares πA∗ mkv, πA∗ act-seq, and πA∗ st-act-seq to assess their generalization differences.
The Sudoku examples prompt models to output only the immediate next move in a specified row, column, and number format.
With thinking mode enabled, the model analyzes rows, columns, and subgrids to identify valid Sudoku placements in a reasoning trace.
The example characterizes enabled thinking as an implicit transition model that forecasts future board states and solves holistically rather than by decomposition.

D.1 Datasets

The appendix describes the datasets, training setup, task configurations, advantage calculations, and learned transition model used in the experiments. It combines SFT warm-up with RL datasets and task-specific state-transition procedures.

D.1 Datasets: SFT warm-up dataset sizes vary across models and tasks, with all models trained for one epoch except Qwen2.5-3B-It on Sudoku, trained for two.
D.1 Datasets: The RL post-training datasets contain 10,000 Sudoku samples, 6,000 Sokoban samples, and 6,000 Futoshiki samples, plus 100 synthesized test problems per task.
D.1 Datasets: Sokoban uses lower-complexity tasks: 2–4 minimal steps for in-distribution benchmarks and 4–6 for out-of-distribution benchmarks.
D.1 Datasets: For Sudoku and Futoshiki, A⋆ assigns advantage 0 to actions that can lead to a correct solution and −1 to invalid actions.
D.1 Datasets: For Sokoban, minimum step counts before and after an action determine the task-specific optimal values, computed in practice with breadth-first search.
D.1 Datasets: A learned state prediction model is trained from environment triplets and replaces the environment transition function at test time.