🤖 machine learning

Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories

This paper resolves the paradox of exploration in post-training by modeling reasoning as Markov transitions, theoretically proving that standard methods like RLVR and ORM/PRM bias models toward high-probability paths and forget rare reasoning steps, while demonstrating that exploration strategies such as instance rejection and KL regularization help preserve these crucial trajectories.

Original authors: Dake Bu, Wei Huang, Andi Han, Atsushi Nitanda, Bo Xue, Qingfu Zhang, Hau-San Wong, Taiji Suzuki

Published 2026-06-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Dake Bu, Wei Huang, Andi Han, Atsushi Nitanda, Bo Xue, Qingfu Zhang, Hau-San Wong, Taiji Suzuki

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Core Problem: The "Lazy Student" Paradox

Imagine you have a very smart student (an AI model) who has read every book in the library (pre-training). This student knows a lot of facts and can solve many problems. However, when it comes to solving really hard, tricky math problems, the student tends to take the "easy way out."

Researchers noticed a strange paradox:

The Goal: We want to train the student to solve hard problems better. We use methods like Reinforcement Learning (RL)—basically giving the student gold stars for correct answers and no stars for wrong ones.
The Expectation: We expect this training to make the student explore new, creative ways to solve problems.
The Reality: Instead of getting more creative, the student becomes more rigid. They start ignoring rare, clever solutions that actually work for hard problems and only stick to the most common, "obvious" steps. They forget the "tricks" they knew before.

The paper asks: Why does trying to improve the student’s reasoning actually make them forget the hard stuff?

The Analogy: The Forest of Paths

To explain this, the authors imagine the student’s brain as a forest where every path is a way to solve a problem.

The Trees (Reasoning Paths): Some paths are wide, sunny, and easy to walk on. These are "Easy-to-Reason" paths. They work for simple problems (like "2+2").
The Thickets (Hard Paths): Some paths are narrow, overgrown, and hard to find. These are "Hard-to-Reason" paths. You need these for tricky problems (like complex algebra or logic puzzles).
The Base Model: Before any special training, the student knows both the wide paths and the narrow thickets. They might not use the thickets often, but they know they exist.

What Goes Wrong? (The "Squeezing Effect")

When we use standard training methods (like RLVR or PPO) to teach the student to be better at math, we are essentially telling them: "Walk the path that gets you the gold star most reliably."

The problem is that the "wide, sunny paths" are statistically more likely to be correct for most problems. So, the training algorithm pushes the student to walk those wide paths all the time.

The Squeeze: As the student focuses on the wide paths, the narrow thickets start to disappear from their memory. The probability of them choosing a hard path drops to near zero.
The Result: The student becomes a "specialist" in easy problems but loses the ability to solve hard ones because they’ve forgotten the narrow paths. This is called the "Simplicity Bias" or "Squeezing Effect."

Why Do "Smart" Scoring Systems Fail?

You might think, "Okay, let’s use a smart judge (a Reward Model) that gives points for every step of the reasoning, not just the final answer."

The paper shows that even these smart judges have a blind spot. They tend to reward consistency rather than correctness.

If a path looks like a standard, common pattern, the judge gives it a high score, even if it’s wrong for a specific hard problem.
If a path is rare and unusual (the thickets), the judge gives it a low score because it’s "unusual," even if it’s the only correct way to solve that specific hard problem.

So, both the training method and the scoring system conspire to make the student ignore the hard, rare paths.

The Solutions: How to Keep the Thickets Alive

The authors propose two main ways to stop the student from forgetting the hard paths:

1. Reject the Easy Questions (Curriculum Learning)

Imagine you are training the student. If you give them a question that they can already solve easily using the wide paths, don’t let them practice it.

Why? If they keep practicing easy questions, they just reinforce the wide paths and forget the thickets.
The Fix: Only show them questions where the easy paths fail. This forces them to look for and strengthen the narrow, hard paths. The paper proves that this "rejection" strategy helps the student learn the hard tricks without losing the easy ones.

2. Add a "Curiosity" Penalty (KL Regularization)

In the training process, add a rule that says: "Don’t change your mind too drastically from what you already knew."

The Analogy: This is like telling the student, "You can learn new things, but don’t forget the old maps you already have."
The Fix: By limiting how much the student can deviate from their original knowledge (the "Base Model"), we prevent them from completely erasing the narrow thickets. This preserves their ability to handle diverse, hard problems.

3. Better Scoring (DPRM)

The authors also propose a new way to score reasoning steps, called DPRM (Doob’s h-Transform-induced Process Reward Model).

Instead of just looking at how "common" a step is, this method looks at the potential of the path to lead to a correct answer, adjusted for how rare it is.
It’s like giving a bonus to the student for exploring a less-traveled path if that path has a good chance of working, rather than penalizing them just for being unusual.

Summary in a Nutshell

The Issue: AI models, when trained to be better at reasoning, tend to become "lazy." They forget rare, clever solutions (hard paths) and only stick to common, simple solutions (easy paths).
The Cause: Standard training rewards the most frequent patterns, which are usually the easy ones. This "squeezes" out the hard, rare patterns.
The Fix:
1. Stop training on easy questions where the model already knows the answer.
2. Add a constraint that prevents the model from forgetting its original, broad knowledge.
3. Use smarter scoring that values rare but correct reasoning paths.

The paper proves mathematically that without these fixes, AI models will lose their ability to solve hard, complex problems, even if they get better at easy ones.

Technical Summary: Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories

Problem Statement
The paper addresses a paradox in the post-training of foundation models for reasoning tasks. While strategies such as Reinforcement Learning with Verifiable Rewards (RLVR) and test-time scaling using Outcome/Process Reward Models (ORM/PRM) are designed to improve task-specific reasoning, empirical evidence suggests they often reinforce existing, high-probability reasoning paths rather than expanding the model’s reasoning scope. This creates a "simplicity bias," where models favor easy, common Chain-of-Thought (CoT) patterns and forget rare but crucial CoTs necessary for solving hard instances. The authors seek to theoretically reconcile why exploration helps improve performance (e.g., pass@K) even when post-training does not explore beyond the base model’s pre-existing tree-like reasoning scope.

Methodology
The authors propose a tractable theoretical framework based on a Tree-structured Markov Chain (TMC) to model multi-task reasoning.

Modeling Reasoning: Each reasoning step is modeled as a Markov state transition. Pretraining is framed as discovering a tree-graph structure, while post-training is modeled as reweighting CoTs within this structure.
Easy vs. Hard CoTs: The framework distinguishes between "easy-to-reason" CoTs (high-probability transitions, $\Theta(1/M)$ ) and "hard-to-reason" CoTs (low-probability or "sparse" transitions, $o(1/M^2)$ ). Hard instances are defined as those solvable only by these rare, hard-to-reason CoTs.
Base Model: The pretrained foundation model is approximated as a linear softmax predictor that accurately captures the TMC transition probabilities.
Analysis Targets: The paper analyzes the dynamics of standard RLVR algorithms (REINFORCE, RAFT, PPO, GRPO) and inference-scaling methods (ORM/PRM with Best-of-N or Beam Search) under this TMC setting.

Key Contributions

Theoretical Formalization of Phenomena: The paper rigorously proves three empirically observed phenomena:
- Squeezing Effect: RLVR implicitly reduces CoT entropy, concentrating probability mass on high-frequency, easy CoTs and causing the model to forget valid hard CoTs.
- Consistency Bias: Neural verifiers (ORM/PRM) tend to reward consistency with common patterns rather than true accuracy, favoring easy CoTs.
- Value of Rare CoTs: Hard instances rely on rare CoTs; preserving these is essential for broad capability.
Proof of Simplicity Bias in RLVR: The authors prove that standard RLVR objectives (REINFORCE, RAFT, PPO, GRPO without KL regularization) inherently favor easy CoTs due to an advantage gap. Specifically, the advantage for easy transitions is strictly higher than for hard transitions, leading to a compounding disparity that suppresses hard CoTs.
Justification for Exploration Strategies: The paper provides theoretical justification for techniques that mitigate this bias:
- Rejection of Easy Instances: Rejecting samples where the model is already confident (easy CoTs) forces the model to learn hard CoTs.
- KL Regularization: Adding KL regularization to GRPO/PPO induces a Gibbs distribution that preserves the base model’s broad capability, including hard CoTs and cross-task capabilities.
Analysis of Inference Scaling: The authors demonstrate that standard ORM/PRM-based inference (BoN/Beam Search) fails on hard instances because population-level rewards favor easy CoTs. They introduce Doob’s h-Transform-induced Process Reward Model (DPRM), showing it is asymptotically equivalent to Soft-BoN and can preserve meta-capabilities by adjusting the temperature parameter.

Results

Theoretical Bounds: The paper derives convergence rates and error bounds. For instance, it shows that without intervention, RLVR leads to a constant error in pass@K performance for hard instances. Conversely, RL-rejection and KL-regularized methods can achieve pass@K performance close to 1 for hard instances while preserving multi-task capability.
Empirical Simulations: Simulations on an abstract TMC with two tasks confirm the theoretical predictions. Standard RL methods (REINFORCE, RAFT, PPO) heavily favor easy CoTs and suffer from forgetting on secondary tasks. In contrast, diversity-promoting methods (RL-rej, GRPO-KL, Soft-BoN, DPRM-AS) balance easy and hard CoTs and maintain performance across tasks.

Significance and Claims
The paper claims to provide a first step toward reconciling the tension between exploration benefits and the lack of new pattern emergence in post-training. It argues that exploration’s value lies in preventing the model from entirely forgetting rare CoTs that are crucial for hard instances. The authors emphasize that their TMC framework is abstract and restrictive, serving to capture partial but crucial rationales for observed behaviors. They explicitly state they do not overclaim direct applicability to large-scale models like GPT due to unmodeled complexities (e.g., non-Markovianity, nonlinear transformers), but suggest the insights offer high-level justification for recent empirical efforts promoting reasoning diversity and rejecting overly easy instances.