🤖 machine learning

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

该论文通过重新引入显式马尔可夫状态来解决大语言模型后训练中的能力瓶颈，从理论和实验两方面证明了这种结构化表征能显著降低样本复杂度并突破现有强化学习在复杂逻辑推理任务中的性能上限。

原作者： Yurun Yuan, Tengyang Xie

发布于 2026-03-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Yurun Yuan, Tengyang Xie

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文提出了一种让大语言模型（LLM）变得更聪明的新方法。简单来说，作者发现现在的 AI 训练方式有一个“天花板”，而打破这个天花板的关键，是重新引入一个经典的概念：马尔可夫状态（Markov States）。

为了让你轻松理解，我们可以用几个生动的比喻来拆解这篇论文的核心思想。

1. 现在的困境：背着“历史包袱”的旅行者

想象一下，你正在教一个学生（AI 模型）玩一个复杂的迷宫游戏（比如数独或推箱子）。

目前的训练方式（Action-Sequence，动作序列）：
现在的 AI 就像是一个记忆力超群但有点混乱的旅行者。每走一步，它都要把之前走过的所有路都背在背上。
- 它想：“我刚才走了左边，然后走了右边，再走了左边，现在我要走哪里？”
- 问题在于： 随着步数增加，它背的“历史包袱”越来越重。它不需要知道“我现在在哪里”，它只需要知道“我刚才做了什么”。这就像你开车时，不看眼前的路况，只盯着后视镜里过去的路线。结果就是，一旦路稍微变长或变复杂，它就被过去的信息淹没了，根本学不会新的策略，只能在原地打转。这就是论文说的“能力天花板”。

2. 核心方案：扔掉包袱，只看“当前状态”

作者提出的新方法（Reintroducing Markov States），就是给这个旅行者配了一个智能导航仪。

新的训练方式（Markov States，马尔可夫状态）：
现在，AI 不再需要背诵过去的所有历史。每走一步，导航仪会直接告诉它：“你现在在地图的这个具体位置（状态），下一步该往哪走。”
- 它不需要知道“我是怎么走到这里的”，它只需要知道“我现在在哪里”。
- 比喻： 就像下围棋。高手看棋盘，只看当前的棋局形势（状态），而不是死记硬背“刚才下了第 100 手、第 101 手……"。只要知道当前局面，就能做出最优决策。

3. 为什么这样更有效？（三个关键点）

A. 打破“天花板”：从“背单词”到“学逻辑”

旧方法： 就像死记硬背。如果题目稍微变难一点（比如迷宫多绕几个弯），AI 就懵了，因为它背的“历史”里没有这种组合。
新方法： 就像理解逻辑。因为 AI 关注的是“当前状态”，它学会了通用的规则。哪怕迷宫变大了，只要它知道“我在 A 点，目标是 B 点”，它就能推导出怎么走。
实验结果： 在数独、推箱子等逻辑谜题中，新方法让 AI 的解题成功率从几乎为零飙升到了 70%-90% 以上，而旧方法完全卡死。

B. 样本效率：少走路，多思考

旧方法： 因为要记住所有历史，AI 需要尝试无数种“历史组合”才能找到正确答案。这就像为了学会走路，必须把地球上所有的路都走一遍。
新方法： 因为只看当前状态，AI 发现“只要走到这个位置，下一步怎么走”是通用的。它不需要重复学习，用更少的练习次数（样本） 就能学会复杂的任务。论文从数学上证明了这一点：新方法需要的数据量呈线性增长，而旧方法呈指数级爆炸。

C. 泛化能力：举一反三

旧方法： 换个稍微不同的迷宫，它就傻了，因为它的“历史包袱”里没遇到过这种情况。
新方法： 它学会了“状态”的本质。哪怕迷宫变大了、变难了，只要当前的“状态”逻辑相似，它就能立刻适应。这就像学会了骑自行车，换一辆不同颜色的自行车你也能骑，而不是非要骑过那辆特定的车。

4. 现实生活中的例子

想象你在写代码或修 Bug：

旧方式（历史序列）： AI 看着你之前改过的 100 行代码，试图从中找规律。它容易搞混，因为代码改来改去，历史太乱。
新方式（马尔可夫状态）： AI 直接看当前编译后的报错信息和当前的代码快照（状态）。它不需要管你之前怎么改的，它只根据“现在的错误”来决定“下一步怎么改”。这样它就能更精准、更快速地解决问题。

总结

这篇论文的核心观点是：大语言模型要想真正变聪明，不能只靠“死记硬背”过去的对话历史，而要学会“看清当下”的状态。

通过引入“马尔可夫状态”（即把复杂的过去压缩成简洁的当前状态），我们能让 AI 从“只会模仿的复读机”变成“真正理解逻辑的推理者”，从而突破现有的能力瓶颈，解决更复杂、更开放的问题。这不仅是技术的进步，更是让 AI 迈向“通用人工智能（AGI）”的关键一步。

这是一份关于论文《Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States》（通过重新引入马尔可夫状态打破大语言模型后训练的能力天花板）的详细技术总结。

1. 研究背景与问题定义 (Problem)

核心问题：大语言模型（LLM）后训练中的“能力天花板”
尽管强化学习（RL）已成为 LLM 后训练和对齐的标准范式，但近期证据表明，RL 在 LLM 上往往只能作为现有模式的“精炼器”，而无法像经典 RL 系统（如 AlphaZero）那样发现全新的策略或突破预训练模型的能力边界。这种现象被称为“能力天花板”。

根本原因：状态表示的结构性瓶颈

现状（历史即状态）： 当前的 LLM 后训练通常将“动作序列的历史”（即所有之前的 Token）直接定义为状态。这种表示法导致状态空间随着序列长度呈指数级膨胀，且包含大量与当前决策无关的噪声。
理论限制： 根据 Foster 等人 (2025) 的理论，在基于动作序列的 RL 中，若要发现最优策略，其计算复杂度受限于基础模型对最优响应的覆盖系数（Coverage Coefficient）。如果基础模型覆盖不足，RL 需要付出指数级的探索成本，导致发现真正新颖解决方案在计算上不可行。
缺失的关键： 经典 RL 的核心在于马尔可夫状态（Markov States）——一种能够封装所有未来决策所需信息的紧凑表示。而 LLM 后训练长期缺失这一显式的马尔可夫状态机制。

2. 方法论 (Methodology)

本文提出了一种重新引入显式马尔可夫状态的 LLM 后训练新范式，旨在打破“历史即状态”的建模局限。

核心机制：马尔可夫状态估计与转换

状态定义： 不再将输入视为动作的历史序列 $(s_1, a_1, \dots, a_{h-1})$ ，而是维护一个显式的状态 $s_h$ 。
状态转移： 引入一个状态转移函数 $P$ $P$ （可以是环境规则、规则引擎或学习到的世界模型）。
- 在每一步，模型根据当前状态 $s_h$ 输出动作 $a_h$ 。
- 状态更新为 $s_{h+1} = P(s_h, a_h)$ 。
- 下一个决策步骤的输入是更新后的状态 $s_{h+1}$ ，而非累积的历史。
实现流程：
1. 状态预测模型 ( $\hat{P}$ )： 训练一个辅助模型（基于 SFT），根据当前状态和动作预测下一个状态。
2. 策略模型 ( $\pi$ )： 策略网络仅接收当前状态 $s_h$ 作为输入，输出动作 $a_h$ 。
3. 训练框架： 使用 GRPO（Group Relative Policy Optimization）算法进行 RL 后训练，但在交互过程中，代理通过 $\hat{P}$ 获取显式状态，而非依赖内部隐式推理历史。

对比基线：

Action-Sequence (传统)： 输入为 $(x, y_1, \dots, y_{h-1})$ ，即 Prompt + 历史生成 Token。
State-Action-Sequence (中间态)： 输入包含历史状态和动作序列，但保留了冗余信息。
Markov (本文方法)： 输入仅为当前状态 $s_h$ 。

3. 主要贡献 (Key Contributions)

打破能力天花板： 在一系列复杂的逻辑谜题（数独、Sokoban、Futoshiki）上，显式马尔可夫状态模型 consistently 超越了传统基于历史序列的 RL 模型的性能边界，在后者失败或停滞的任务上取得了高成功率。
鲁棒的泛化能力 (OOD)： 马尔可夫模型在分布外（Out-of-Distribution）测试中表现出卓越的泛化性，能够解决比训练集结构更复杂、搜索深度更深的谜题。
样本复杂度理论保证： 提供了严格的理论证明，表明基于马尔可夫状态的学习在样本复杂度上显著低于基于动作序列的学习。
- 理论核心： 动作序列方法需要覆盖指数级增长的历史空间（ $O(|A|^H)$ ），而马尔可夫方法仅需覆盖紧凑的状态空间（ $O(H)$ 或多项式级）。通过引入状态转移模型，用多项式代价（状态估计误差）换取了指数级的样本效率提升。

4. 实验结果 (Results)

实验在 Qwen3-4B 和 Qwen2.5-3B-Instruct 模型上，针对 Sudoku、Sokoban 和 Futoshiki 三个逻辑推理任务进行。

性能提升：
- 在 Sokoban 和 Futoshiki 等高难度任务上，传统 Action-Sequence 模型在 RL 后训练后表现极差（甚至接近 0% 成功率），而 Markov 模型取得了显著突破（例如 Sokoban 从 2.5% 提升至 76.1%）。
- Pass@k 分析： 随着采样数 $k$ 的增加，Action-Sequence 模型无法超越 SFT 基线的上限，而 Markov 模型能持续扩展 Pass@k 曲线，证明其真正拓展了能力边界。
训练效率：
- Markov 模型收敛速度更快，在更少的训练步数内达到更高的奖励值，验证了更低的样本复杂度。
消融实验：
- 状态依赖性： 即使 State-Action-Sequence 模型拥有完整历史，其性能仍不如仅依赖当前状态的 Markov 模型。实验表明，State-Action-Sequence 模型实际上主要依赖当前状态，历史信息的冗余反而引入了噪声。
- SFT 预热： Markov 模型对 SFT 预热的依赖更低，在较少 SFT 步骤下即可通过 RL 获得显著提升，而传统模型需要大量 SFT 才能起步。

5. 意义与影响 (Significance)

理论突破： 该工作揭示了 LLM 后训练中“能力天花板”并非 RL 算法本身的缺陷，而是状态表示（State Representation）的结构性错误。重新引入马尔可夫假设是解决长程推理和复杂规划问题的关键。
范式转变： 呼吁从“历史即状态”（History-as-State）的建模方式转向结构化的马尔可夫表示。这对于实现真正的开放-ended 能力增长（Open-ended Capability Growth）和通用人工智能（AGI）至关重要。
应用前景： 该方法不仅适用于合成逻辑任务，还广泛适用于代码调试（状态为代码库快照）、数学证明（状态为已证明引理集）和迭代式响应优化等现实场景，其中状态转移逻辑清晰可定义。

总结：
这篇论文通过理论分析和实证研究证明，显式地引入马尔可夫状态是解锁 LLM 在复杂推理任务中真正新能力的关键。它解决了传统 RL 后训练中因状态空间爆炸导致的样本效率低下和探索困难问题，为下一代具备更强推理和规划能力的 AI 系统提供了新的架构方向。