mlsanityData to 7 Oct 2026

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

arXiv 2511.07368 ↗First posted 10 Nov 2025cs.LG cs.AIcited by 3

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

Foundation models exhibit broad knowledge but limited task-specific reasoning, motivating post-training strategies such as RL with verifiable rewards (RLVR) and test-time scaling (TTS). While recent work highlights the role of exploration in improving pass@K, empirical evidence points to a paradox: RLVR and ORM/PRM typically reinforce existing paths rather than expanding the reasoning scope, raising the question of why exploration helps if no new patterns emerge. To reconcile this paradox, we adopt the perspective of Kim et al. (2025), viewing easy (e.g., simplifying a fraction) versus hard (e.g., discovering the some symmetry) reasoning steps as low versus high probability Markov transitions. In this tractable model, pretraining corresponds to tree-graph discovering, while post-training corresponds to CoT reweighting. We provably show that, both RLVR and ORM/PRM would favor heavily to several high-probability paths, and thereby forget rare-but-crucial CoTs. Building on this, we further prove that exploration strategies such as rejecting easy instances and KL regularization help preserve rare CoTs. Empirical simulations corroborate our theoretical results.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 66 of its 103 references that are in the map. First posted on arXiv 10 Nov 2025.

Builds on

66 of 103 references.

Closest ancestors · 20

Same direction, newest first

  1. 2025Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMs17 Jun
  2. 2025SPEED-RL: Faster Training of Reasoning Models via Online Curriculum Learning10 Jun
  3. 2025Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoning7 Jun
  4. 2025Reshaping Reasoning in LLMs: A Theoretical Analysis of RL Training Dynamics through Pattern Selection5 Jun
  5. 2025Rewarding the Unlikely: Lifting GRPO Beyond Distribution Sharpening3 Jun
  6. 2025Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoning2 Jun
  7. 2025The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models28 May
  8. 2025Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning26 May
  9. 2025On the Effect of Negative Gradient in Group Relative Deep Reinforcement Optimization24 May
  10. 2025Reinforcement Learning for Reasoning in Large Language Models with One Training Example29 Apr
  11. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?18 Apr
  12. 2025A Minimalist Approach to LLM Reasoning: from Rejection Sampling to Reinforce15 Apr
8 more
  1. 2025Online Difficulty Filtering for Reasoning Oriented Reinforcement Learning4 Apr
  2. 2025DAPO: An Open-Source LLM Reinforcement Learning System at Scale18 Mar
  3. 2025Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs3 Mar
  4. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning22 Jan
  5. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations14 Dec
  6. 2023Let's Verify Step by Step31 May
  7. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Model29 May
  8. 2017Proximal Policy Optimization Algorithms20 Jul

Other references · 46

  1. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,084
  2. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  3. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  4. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  5. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
  6. 2023Training Diffusion Models with Reinforcement Learningcited by 939
  7. 2019Introduction to Online Convex Optimizationcited by 793
  8. 2017Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problemscited by 642
  9. 2018Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Reviewcited by 466
  10. 2023Directly Fine-Tuning Diffusion Models on Differentiable Rewardscited by 431
  11. 2023Scaling Relationship on Learning Mathematical Reasoning with Large Language Modelscited by 417
  12. 2023UltraFeedback: Boosting Language Models with Scaled AI Feedbackcited by 394
34 more
  1. 2024DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Searchcited by 189
  2. 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 180
  3. 2019What Can Neural Networks Reason About?cited by 155
  4. 2024Fine-Tuning of Continuous-Time Diffusion Models as Entropy-Regularized Controlcited by 136
  5. 2023Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMscited by 121
  6. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 114
  7. 2024RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Foldcited by 99
  8. 2024Learning Dynamics of LLM Finetuningcited by 93
  9. 2024DART-Math: Difficulty-Aware Rejection Tuning for Mathematical Problem-Solvingcited by 92
  10. 2025The Invisible Leash: Why RLVR May or May Not Escape Its Origincited by 92
  11. 2025Scaling Test-Time Compute Without Verification or RL is Suboptimalcited by 82
  12. 2018Risk and parameter convergence of logistic regressioncited by 81
  13. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  14. 2025Rethinking Reflection in Pre-Trainingcited by 43
  15. 2025Reinforcement Learning with Verifiable yet Noisy Rewards under Imperfect Verifierscited by 40
  16. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 39
  17. 2025LLMs are Greedy Agents: Effects of RL Fine-tuning on Decision-Making Abilitiescited by 36
  18. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 34
  19. 2024Large Language Models as Markov Chainscited by 33
  20. 2025Soft Best-of-n Sampling for Model Alignmentcited by 28
  21. 2025Evolution Strategies at Scale: LLM Fine-Tuning Beyond Reinforcement Learningcited by 28
  22. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  23. 2024Implicit Diffusion: Efficient Optimization through Stochastic Samplingcited by 22
  24. 2020Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learningcited by 18
  25. 2025Reasoning Models Hallucinate More: Factuality-Aware Reinforcement Learning for Large Reasoning Modelscited by 18
  26. 2025Representation-Based Exploration for Language Models: From Test-Time to Post-Trainingcited by 16
  27. 2025Error Classification of Large Language Models on Math Word Problems: A Dynamically Adaptive Frameworkcited by 10
  28. 2025On the Role of Temperature Sampling in Test-Time Scalingcited by 10
  29. 2025Right Is Not Enough: The Pitfalls of Outcome Supervision in Training LLMs for Math Reasoningcited by 9
  30. 2025Strategic Scaling of Test-Time Compute: A Bandit Learning Approachcited by 8
  31. 2025Reward Models Identify Consistency, Not Causalitycited by 6
  32. 2024Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Netscited by 5
  33. 2025Transformers Simulate MLE for Sequence Generation in Bayesian Networkscited by 5
  34. 2024Understanding the dynamics of the frequency bias in neural networkscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Leveraging Error Diversity in Group Rollouts for Reinforcement Learningcited by 2
  2. 2026DPRM: A Plug-in Doob h transform-induced Token-Ordering Module for Discrete Diffusion Modelscited by 1
  3. 2026Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficientlycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025On the Interplay of Pre-Training, Mid-Training, and RL on Reasoning Language Models
  2. 2026Select and Improve: Understanding the Mechanics of Post-Training for Reasoning
  3. 2026A Primer in Post-Training Reasoning Data: What We Know About How It Works
  4. 2026Reasoning Depth and Environment Complexity: A Controlled Study of RLVR Data Allocation across Logical Reasoning Tasks
  5. 2026Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching
  6. 2026Reasoning as State Transition: A Representational Analysis of Reasoning Evolution in Large Language Models
  7. 2025Rethinking Expert Trajectory Utilization in LLM Post-training for Mathematical Reasoning
  8. 2026New Skills or Sharper Primitives? A Probabilistic Perspective on the Emergence of Reasoning in RLVR