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

1. Problem Statement

The paper addresses a persistent "capability ceiling" observed in Reinforcement Learning (RL) post-training for Large Language Models (LLMs). While classical RL systems (e.g., AlphaZero) act as discovery engines capable of finding novel strategies, RL for LLMs often functions merely as a refiner of patterns already latent in pre-trained weights, failing to expand the solution space significantly.

The authors identify the root cause as a structural bottleneck in current LLM formulations:

• Current Paradigm (History-as-State): LLMs are typically treated as agents where the "state" is defined by the concatenation of all preceding actions (tokens). This results in an ever-expanding, noisy history sequence.
• Theoretical Limitation: This formulation forces the agent to learn over an exponentially large action-history space. Theoretical analysis (referencing Foster et al., 2025) suggests that discovering novel capabilities in this space requires sample complexity that grows exponentially with the horizon, making it computationally intractable for complex reasoning tasks.
• Missing Component: Current LLM post-training lacks explicit Markov states—compact representations that encapsulate all necessary information for optimal future decision-making, discarding irrelevant history.

2. Methodology

The paper proposes reintroducing explicit Markov states into the LLM post-training pipeline, shifting from "history-as-state" to a structured Markovian representation.

Core Concept: Markov State Estimation

Instead of feeding the full history of actions $(a_1, \dots, a_{h-1})$ into the model, the proposed method maintains a state $s_h$ that summarizes the environment's current configuration.

• State Transition: A new state $s_{h+1}$ is generated by combining the current state $s_h$ and the action $a_h$ via a transition function $P(s_h, a_h)$.
• Implementation: The transition function $P$ can be realized by:
  1. An external environment with ground-truth dynamics (used in training).
  2. A rule-based mechanism.
  3. A learned State Prediction Model ($\hat{P}$) trained via Supervised Fine-Tuning (SFT) to predict the next state from the current state and action.

Experimental Setup

• Tasks: The authors evaluated the approach on three synthetic logical reasoning tasks with well-defined Markov structures: Sudoku, Sokoban, and Futoshiki.
• Models: They used Qwen3-4B and Qwen2.5-3B-Instruct.
• Algorithms:
  • Baseline (Action-Sequence): Standard RL where input is the full history of tokens.
  • Proposed (Markov): RL where input is the explicit state $s_h$ (updated by $\hat{P}$).
  • Intermediate Baseline (State-Action-Sequence): A model conditioned on the full history of states and actions to isolate the benefit of the Markov property vs. just having state access.
• Training: Models underwent an SFT warm-up followed by RL post-training using GRPO (Group Relative Policy Optimization).

3. Key Contributions

1. Breaking the Capability Ceiling:

   • The paper demonstrates that models using explicit Markov states consistently surpass the performance boundaries of traditional history-dependent RL.
   • On difficult tasks (e.g., Sokoban, Futoshiki), action-sequence models often plateau at near-zero accuracy, while Markov models achieve high success rates.

2. Robust Generalization (OOD):

   • Markov models exhibit superior Out-of-Distribution (OOD) generalization. They successfully solve puzzles with higher structural complexity and deeper search depths than those encountered during training, whereas history-based models fail to generalize beyond their training distribution.

3. Sample Efficiency Guarantees:

   • Theoretical Proof: The authors provide rigorous theoretical bounds showing that Markovian learning achieves significantly lower sample complexity.
   • Mechanism: In action-sequence learning, the state space grows exponentially ($O(|A|^H)$), requiring exponential coverage. In Markov learning, the state space grows linearly ($O(H)$), reducing the coverage requirement and variance exponentially.
   • Trade-off: The paper acknowledges a polynomial bias term ($O(H^3 \epsilon_P)$) introduced by approximate state transitions but argues this is a favorable trade-off compared to the exponential cost of history-based exploration.

4. Results

• Performance Metrics: Evaluated using Avg@128 (average success rate) and Pass@128 (probability of at least one correct solution in 128 samples).
• Quantitative Gains:
  • Sudoku: Markov models reached ~97.1% Pass@128 vs. 92.3% for Action-Seq.
  • Sokoban: Markov models achieved 76.1% vs. 2.5% for Action-Seq (a massive breakthrough).
  • Futoshiki: Markov models achieved 75.0% vs. 0.2% for Action-Seq.
• Training Dynamics: Markov models converged significantly faster, reaching higher rewards in fewer training steps (lower sample complexity).
• Ablation Studies:
  • State-Action-Sequence vs. Markov: Even when given access to the full history of states, models that do not enforce a Markovian policy structure (i.e., they still look at the whole history) perform worse than pure Markov models. This suggests that the extra historical context is often redundant noise that hinders learning.
  • SFT vs. RL: The benefits of Markov states are most pronounced in the RL phase. In pure SFT, the gap narrows, suggesting the Markov property is critical for the exploration and credit assignment aspects of RL.

5. Significance and Implications

• Paradigm Shift: The paper challenges the prevailing "history-as-state" assumption in LLM alignment. It argues that for open-ended discovery and complex reasoning, LLMs must move away from treating the entire generation history as the state.
• Path to AGI: The findings suggest that unlocking genuinely new reasoning capabilities and open-ended growth in Generative AI requires aligning the agent's representation with the underlying logic of the task (Markovian structure) rather than relying on raw token sequences.
• Practical Applicability: The approach is applicable to real-world domains like coding (where the state is the codebase snapshot), mathematical reasoning (state is the set of lemmas), and iterative refinement (state is the current draft), offering a blueprint for building more capable and efficient agentic systems.

In conclusion, the paper provides both theoretical justification and empirical evidence that reintroducing explicit Markov states is essential for overcoming the current limitations of RL in LLMs, enabling models to discover novel strategies rather than just refining existing ones.