通过重新引入马尔可夫状态突破大语言模型后训练的能力上限 Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States
将经典RL的马尔可夫状态引入LLM后训练，突破能力天花板，实现指数级样本效率提升
前置知识
马尔可夫决策过程（MDP）
马尔可夫决策过程是强化学习的理论基础，由状态空间 $\mathcal{S}$、动作空间 $\mathcal{A}$、转移函数 $P: \mathcal{S} \times \mathcal{A} \rightarrow \Delta(\mathcal{S})$、奖励函数 $r: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ 和初始状态分布 $\rho$ 组成。MDP的核心性质是马尔可夫性：下一个状态只依赖于当前状态和动作，与历史无关。这种结构性质使得智能体可以通过紧凑的状态表示来做出最优决策，而无需记住整个交互历史。
本文的核心论点是当前LLM后训练违背了MDP的马尔可夫性，使用不断膨胀的动作历史作为状态，导致能力天花板。理解MDP是理解本文技术贡献的基础。
RL后训练（RL Post-Training）
RL后训练是指在大语言模型预训练完成后，使用强化学习方法进一步微调模型的过程。常见算法包括PPO（近端策略优化）和GRPO（群体相对策略优化）。在这一范式中，LLM被视为策略 $\pi$，输入token序列对应状态，输出token对应动作。通过与环境交互获取奖励信号，模型学习生成更符合人类偏好或任务要求的输出。
本文发现RL后训练存在结构性瓶颈——它主要是在预训练已有的能力空间内进行精炼，而非真正扩展能力边界。这是本文要解决的核心问题。
马尔可夫状态（Markov State）
马尔可夫状态是一个紧凑的信息表示，它包含了做出最优未来决策所需的全部信息，同时丢弃了历史中不相关的噪声。形式上，状态 $s_{h+1}$ 通过转移函数 $P(s_h, a_h)$ 从当前状态和动作生成，保留了所有与未来决策相关的信息。在经典RL应用（如围棋AlphaGo、机器人控制）中，马尔可夫状态是核心组件，使得智能体能够在紧凑的状态空间中高效学习。
本文的核心创新就是将马尔可夫状态重新引入LLM后训练，替代当前的'动作历史即状态'范式，这是突破能力天花板的关键机制。
能力天花板（Capability Ceiling）
能力天花板是指RL后训练在提升LLM推理能力时遇到的性能上限。现有证据表明，RL主要是在预训练模型已有能力的范围内进行搜索精炼，而非真正扩展模型的解空间。Foster等人（2025）从理论上证明，在KL正则化RL目标下，找到近优策略的计算复杂度下界为 $\Omega(\min(C_{\text{cov}}(\pi_\beta^\star), \exp(R_{\max}/\beta)))$，其中 $C_{\text{cov}}(\pi_\beta^\star)$ 是基模型的覆盖系数。
理解能力天花板的概念是理解本文动机的关键。本文的目标就是通过引入马尔可夫状态来打破这一天花板。
GRPO（群体相对策略优化）
GRPO是DeepSeek-R1等模型采用的策略优化算法，是PPO的简化替代方案。GRPO对每个提示 $x$ 采样 $G$ 个响应 $o^{(1)}, \ldots, o^{(G)}$，通过在提示组内归一化奖励来计算优势估计 $\hat{A}^{(i)}$，然后用这个响应级优势替代PPO目标中的逐步优势函数。GRPO不需要训练单独的critic网络，实现更简单，适合LLM后训练场景。
本文的实验使用GRPO作为RL算法，比较马尔可夫模型和动作序列模型在同一算法下的表现差异。
研究动机
当前LLM后训练的RL范式面临一个根本性的结构性瓶颈：它将LLM的'状态'定义为所有先前动作的拼接序列，即 $s_h := (x, y_1, \ldots, y_{h-1})$。这种'动作历史即状态'的建模方式导致状态空间随推理深度指数级膨胀，引入大量噪声信息。具体表现为：在Sudoku任务上，Qwen3-4B的动作序列模型RL后训练只能达到93.5%的平均准确率；在Sokoban上仅为2.3%；在Futoshiki上几乎为零（0.1%）。更关键的是，Yue等人（2025）的发现表明，动作序列模型的RL后训练甚至无法维持SFT模型的Pass@k性能，说明RL主要是在预训练能力范围内进行精炼而非扩展。Foster等人（2025）从理论上证明了这种范式的计算复杂度下界，揭示了'发现'瓶颈：要么依赖基模型已覆盖最优响应（此时Pass@k已不错），要么付出指数级探索代价。
本文的目标是本文的具体目标是：(1) 从理论和实验证明，将经典RL中的马尔可夫状态概念重新引入LLM后训练可以显著降低样本复杂度；(2) 在一系列复杂逻辑谜题上展示马尔可夫模型能够突破标准RL后训练的性能边界；(3) 证明马尔可夫模型具有优越的分布外泛化能力，能够解决比训练时更复杂的任务。最终目标是为LLM后训练提供一个更有效的范式，推动开放式的、无止境的能力增长。
与已有工作不同的是，本文的独特切入角度在于回归经典RL的核心原则——显式马尔可夫状态估计，但将其应用于LLM后训练这一新兴领域。与现有工作不同，本文不是通过更复杂的奖励设计、更大的模型或更多的数据来突破能力天花板，而是从状态表示的根本层面进行改革。作者识别出当前LLM-RL范式与经典RL的关键区别：经典RL（如AlphaGo、MuZero）使用紧凑的马尔可夫状态，而LLM后训练使用不断膨胀的动作历史。这一视角的转换揭示了能力天花板本质上是'动作历史即状态'建模方式的产物，而非RL本身的局限。这种从第一性原理出发的分析方法，为LLM能力提升提供了一条全新且理论上更有保证的路径。
核心方法
本文方法的核心直觉是：在经典RL中，智能体依赖紧凑的马尔可夫状态进行决策，这使得学习高效且可泛化；而当前LLM后训练将整个动作历史作为'状态'，导致状态空间指数膨胀且充满噪声。技术路线是：在LLM后训练流程中引入显式的马尔可夫状态估计。具体来说，新生成的动作 $a_h$ 不再简单追加到历史序列中，而是与当前状态 $s_h$ 一起通过状态转移函数 $P$ 生成下一个状态 $s_{h+1}$。这个状态 $s_{h+1}$ 保留了未来决策所需的全部信息，同时丢弃了不相关的历史噪声。在实际实现中，状态转移函数可以由环境内部维护（训练时）、规则机制实现，或通过学习的世界模型近似（测试时）。
本文的核心创新在于识别并解决了LLM后训练与经典RL之间的结构性脱节。本质区别在于：动作序列模型在步骤 $h$ 的策略为 $\pi(\cdot | s_1, a_1, \ldots, a_{h-1})$，输入空间大小为 $|\mathcal{A}|^H$（指数级）；而马尔可夫模型的策略为 $\pi(\cdot | s_h)$，输入空间仅为状态空间大小 $|\mathcal{S}|$（通常多项式级）。这种从指数级到多项式级的状态空间压缩带来了两个关键优势：(1) 样本复杂度指数级降低——密度比 $\frac{d_h^{\pi^\star}(s_1, a_{1:h})}{d_h^{\pi^{(t)}}(s_1, a_{1:h})}$ 难以界定，而 $\frac{d_h^{\pi^\star}(s_h, a_h)}{d_h^{\pi^{(t)}}(s_h, a_h)}$ 更易控制；(2) 泛化能力提升——不同的动作历史若诱导相同状态则被视为等价，避免了过拟合到特定历史模式。
方法步骤详情
本文方法分为三个阶段：第一阶段是SFT热身（SFT Warm-up），对每个任务进行简短的任务特定监督微调，建立任务理解和输出格式规范。第二阶段是RL后训练，在交互式环境中使用GRPO算法进行训练，智能体在真实环境（具有真实转移动力学 $P^\star$）中行动，接收稀疏终端奖励（解决实例得1分，否则0分）。此时策略条件于显式的马尔可夫状态 $s_h$。第三阶段是训练状态预测模型 $\hat{P}$，基于Qwen2.5-3B-Instruct通过SFT训练一个模型，从当前状态和动作预测下一个状态 $\hat{s}_{h+1}$。测试时，$\hat{P}$ 替代环境 $P^\star$，实现无需环境访问的部署。特别地，模型被要求仅输出下一个动作而不使用链式思维，因为基模型本身会将棋盘状态预测内化到推理链中，这会破坏逐步分解问题的目标。
技术新颖性
本文的技术新颖性体现在多个层面。首先，在概念层面，作者首次将'能力天花板'这一现象归因于LLM后训练中缺失马尔可夫状态这一结构性问题，而非RL算法本身的局限。其次，在方法层面，引入了中间基线 $\pi_{\text{st-act-seq}}$（状态-动作序列模型），它条件于完整的状态和动作历史 $({(s_i, a_i)}_{i=1}^{h-1}, s_h)$，从而能够精确分离'显式状态访问'和'马尔可夫性质'两个因素的贡献。第三，在理论层面，本文严格证明了在近似马尔可夫学习框架下，性能保证的上界包含一个多项式偏差项 $O(H^3 \epsilon_P)$ 和一个方差项（依赖于状态空间而非动作历史空间），相比动作序列学习的指数级复杂度有本质改进。第四，引入了诊断变体 $\pi_{A^\star}^{\text{mkv}}$ 和 $\pi_{A^\star}^{\text{act-seq}}$，通过提供真实最优优势 $A^\star$ 来消除信用分配和探索的干扰，纯粹隔离泛化能力的差异。
实验结果
本文在三个逻辑推理任务（Sudoku、Sokoban、Futoshiki）上对Qwen3-4B和Qwen2.5-3B-Instruct进行了全面实验。核心发现如下：(1) 马尔可夫模型在所有任务上一致且显著地超越动作序列模型。以Qwen3-4B为例，马尔可夫模型在Sudoku上达到97.1%平均准确率（动作序列为93.5%），Sokoban上76.1%（vs 2.3%），Futoshiki上75.0%（vs 0.1%）。(2) 分离实验表明，显式状态访问和马尔可夫性质都有贡献：状态-动作序列模型在Sokoban上达到57.4%（vs 动作序列的2.3%），而纯马尔可夫模型进一步提升到76.1%。(3) 马尔可夫模型展现出优越的分布外泛化能力：在OOD Sudoku上，Qwen2.5-3B的马尔可夫模型达到56.4%（vs 动作序列的0.0%）。(4) Pass@k分析显示，动作序列模型无法扩展甚至无法维持SFT的Pass@k，而马尔可夫模型显著突破基模型的能力边界。(5) 训练收敛速度更快：马尔可夫模型在更少的训练步数内达到更高的奖励。(6) 使用真实优势 $A^\star$ 的诊断实验进一步确认，即使在消除了信用分配和探索因素后，马尔可夫模型的泛化能力仍然显著优于动作序列模型。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| Sudoku (ID, Qwen3-4B) | Avg@128 / Pass@128 | 97.1 / 98.0 | 93.5 / 97.0 (动作序列) | +3.6 / +1.0 百分点 |
| Sokoban (ID, Qwen3-4B) | Avg@128 / Pass@128 | 76.1 / 81.0 | 2.3 / 4.0 (动作序列) | +73.8 / +77.0 百分点 |
| Futoshiki (ID, Qwen3-4B) | Avg@128 / Pass@128 | 75.0 / 85.0 | 0.1 / 7.0 (动作序列) | +74.9 / +78.0 百分点 |
| Sudoku (ID, Qwen2.5-3B) | Avg@128 / Pass@128 | 86.0 / 94.0 | 0.0 / 0.0 (动作序列) | +86.0 / +94.0 百分点 |
| Sokoban (ID, Qwen2.5-3B) | Avg@128 / Pass@128 | 89.7 / 93.0 | 1.0 / 1.0 (动作序列) | +88.7 / +92.0 百分点 |
| Futoshiki (OOD, Qwen3-4B) | Avg@128 / Pass@128 | 77.8 / 82.0 | 69.2 / 82.0 (动作序列) | +8.6 / +0.0 百分点 |
| Sokoban (OOD, Qwen2.5-3B) | Avg@128 / Pass@128 | 66.9 / 72.0 | 0.0 / 0.0 (动作序列) | +66.9 / +72.0 百分点 |
局限与改进
本文存在几个明显的局限性。首先，实验仅在三个合成逻辑谜题（Sudoku、Sokoban、Futoshiki）上进行，这些任务具有明确的、可精确获取的马尔可夫状态（棋盘配置），但现实世界的LLM应用场景（如开放域对话、创意写作）的状态定义远不如此清晰。其次，实验规模相对较小，仅使用了3B和4B参数的模型，未在更大规模模型上验证方法的有效性。第三，训练过程中需要访问真实环境的转移动力学来获取马尔可夫状态，这在许多实际场景中不可行；虽然测试时使用了学习的状态预测模型，但训练时的环境依赖限制了方法的适用范围。第四，论文明确要求模型不使用链式思维，只输出下一个动作，这与当前主流的推理增强范式存在冲突。第五，状态预测模型的训练本身需要额外的数据和计算资源，增加了系统复杂度。第六，论文未讨论在多轮对话、代码生成、数学证明等作者声称适用的场景中的实际效果。
独立分析的弱点
本文的弱点主要集中在以下几个方面。(1) 状态定义的泛化性不足：在Sudoku等任务中，马尔可夫状态就是棋盘配置，但在自然语言任务中，如何定义和提取马尔可夫状态是一个开放问题。建议未来工作探索自动化的状态表示学习方法，例如通过变分自编码器或对比学习来发现任务中的潜在马尔可夫结构。(2) 状态预测模型的误差累积：在长推理链中，学习的转移模型的预测误差会逐步累积，可能导致状态偏离真实值。论文中的理论分析包含 $O(H^3 \epsilon_P)$ 的偏差项，但在实际应用中这个误差可能更大。建议引入状态校正机制或不确定性估计来缓解这一问题。(3) 与链式思维的兼容性：论文强制模型只输出动作，但这限制了模型的推理能力。建议探索将马尔可夫状态与结构化思维链结合的方法，例如在每个状态转换点插入推理步骤。(4) 缺乏与更强基线的比较：未与Process Reward Model、Monte Carlo Tree Search等推理增强方法进行比较。
未来方向
作者提出的未来方向包括将马尔可夫范式扩展到更广泛的现实世界任务。基于本文成果，可以延伸出多个研究方向：(1) 自动马尔可夫状态发现——开发能够从任务描述或少量演示中自动识别马尔可夫状态结构的方法，降低人工设计成本。(2) 连续状态空间的马尔可夫表示——当前方法假设离散状态，需要扩展到连续状态空间以处理机器人控制、科学计算等任务。(3) 与搜索算法结合——将马尔可夫状态与MCTS等树搜索方法结合，在推理时进行更高效的探索。(4) 多任务马尔可夫表示学习——学习跨任务共享的马尔可夫状态表示，提升迁移学习能力。(5) 马尔可夫状态的可解释性——利用状态表示的紧凑性来提升推理过程的可解释性，例如通过状态轨迹可视化来理解模型的推理路径。(6) 在真实编码和数学推理任务上的验证——在代码调试、定理证明等作者声称适用但未实验验证的场景中进行大规模实验。
复现评估
本文的复现条件相对友好。作者使用了开源模型（Qwen3-4B和Qwen2.5-3B-Instruct）和开源框架（rLLM），实验任务来自Reasoning-Gym数据集。论文提供了详细的超参数设置和实现细节。然而，完整复现需要：(1) 训练多个模型（每个任务乘以每个模型乘以每种方法），计算成本较高；(2) 训练状态预测模型需要额外的SFT数据和计算；(3) 三个任务的环境实现需要从Reasoning-Gym获取或自行实现。论文未明确说明是否开源代码，但技术细节描述充分，有经验的研究者应该能够复现主要结果。需要注意的是，论文使用了相对较小的模型（3B-4B），这使得在消费级硬件上的复现成为可能，但扩展到更大模型的成本会显著增加。
论文图表
