Markov States 打破 Post-training 天花板：第六个维度还是已有维度的特例？

0.2% → 75% — 只换了状态表示，训练效果从零变到可用

Qwen3-4B 在 Futoshiki（逻辑推理棋盘游戏）上，标准的 action-sequence RL 训练后准确率只有 0.2%。换成 Markov state 表示（每步输入当前棋盘状态而非全部历史动作），同样的 GRPO 训练达到 75.0%。Sokoban 上从 2.5% → 76.1%。这不是微调，是质变。

为什么这个结果令人困惑？

我之前整理了 Post-training 天花板的五个维度：验证器精度、分布匹配、训练格式、信号密度、初始行为 repertoire。这五个维度解释了"同样 base model，不同 pipeline 效果差 20 倍"的现象。

但 Markov States 论文 [ref] 展示的差距（0.2% vs 75%）不能被这五个维度中的任何一个解释：

验证器完全相同（规则验证，ground truth）
分布完全 on-policy（interactive environment）
训练格式相同（都是 GRPO + sparse terminal reward）
信号密度相同（都是 sparse）
初始行为 repertoire 也一样（同一个 base model）

唯一变化是：policy 的输入从 action history 变成了 Markov state。

论文的核心论点

Comparison of action-sequence and Markov models

论文的核心论点分三层：

1. 理论层：指数级样本复杂度差异

在 action-sequence 学习中，density ratio $d_h^{\pi^*}(s_1, a_{1:h}) / d_h^{\pi^{(t)}}(s_1, a_{1:h})$ 定义在完整动作历史上，空间随 horizon H 指数增长（ $|A|^H$ ）。而 Markov 学习的 density ratio 定义在 state-action 对上，只要 state space 紧凑（多项式级），就能指数级降低样本复杂度。

这和 Foster et al. (2025) [ref] 的 computational lower bound 形成对话：标准 RL for LLMs 要么依赖 base model 已经覆盖最优策略（ $C_{cov}$ 小），要么暴力搜索（ $e^{R_{max}/\beta}$ ）。引入 Markov states 绕过了这个二选一，把 coverage 需求从 action history 空间降低到 state 空间。

2. 实验层：三因素分解

论文巧妙地引入中间 baseline —— state-action-sequence model（看到完整 state + action history，但不强制 Markov 结构）—— 来分解两个因素：

模型	Sudoku	Sokoban	Futoshiki
Action-sequence + RL	93.5	2.3	0.1
State-action-sequence + RL	91.1	57.4	44.4
Markov + RL	97.1	76.1	75.0

两个独立增益：

Action-seq → State-action-seq：显式 state 条件化。模型不需要从 action history 隐式推断当前棋盘状态，卸载了 state tracking 的负担。
State-action-seq → Markov：Markov 性质。额外的历史信息是冗余的（在 Markov 假设下），反而引入伪相关，干扰学习。

3. 泛化层：Markov 的核心收益不是探索也不是 credit assignment

论文用一个精妙的控制实验隔离了 RL 的三大挑战（exploration, credit assignment, generalization）。用 ground-truth optimal advantage $A^*$ 替代估计值（消除 credit assignment），用固定温度 softmax 控制 exploration。剩下的差距 = 纯泛化差距。

结果：即使给了完美的 credit assignment 信号，action-sequence 模型仍然显著弱于 Markov 模型（Sokoban: 18.2% vs 33.0%，Qwen3-4B）。泛化是 Markov states 的核心收益。

原因直觉很清楚：Markov state 把不同的 action history 映射到同一个 state（只要它们导致相同棋盘配置），从而自动获得了一种等价类泛化。Action-sequence 模型必须自己学习这个等价关系，而这在指数级的 history 空间中极其困难。

这是第六个维度吗？

回到我的核心问题：这是否需要在我的五维度框架中加入第六个维度？

支持"第六个维度"的论据：

和其他五个维度完全正交——改变的不是训练信号、验证器、格式、数据，而是 policy 的输入表示
效果不是"优化"级别（20-30% 提升），而是"从零到可用"级别（0.2% → 75%）
有独立的理论基础（coverage requirement 从 $|A|^H$ 降到 $|S|$ ）

反对"第六个维度"的论据：

适用范围可能很窄——论文只在有显式 Markov state 的环境（棋盘游戏）上验证
对大多数 LLM post-training 场景（数学推理、代码生成、对话），“Markov state” 的定义模糊
论文自己也承认：需要额外训练一个 state prediction model（ $\hat{P}$ ），这是额外成本

我的判断：这不是一个独立的"第六维度"，而是对维度五（初始行为 repertoire）的深化。

理由：Markov state 的核心作用是简化 RL 的搜索空间。在 action-sequence 模型中，模型需要同时学两件事：(1) 从 history 推断当前 state，(2) 基于 state 做决策。而 Markov 模型把 (1) 外包给了 state transition model，让 RL 只关注 (2)。

这和维度五的逻辑一致：如果 base model 已经"会"推断 state（即 action-sequence 模型隐式地学会了 state tracking），那 Markov 的优势就小了。论文在 Sudoku 上的数据也支持这一点：Sudoku 是最"结构化"的任务（state 相对容易推断），action-sequence 模型已经 93.5%，Markov 只提升到 97.1%。差距最大的是 state 推断最困难的任务（Sokoban 的空间规划、Futoshiki 的约束传播）。

但这个"深化"足够重要，值得在五维度框架中加一个注释：维度五不只是"行为 repertoire"，还包括"state representation 的合理性"。当 RL 的输入表示导致搜索空间指数膨胀时，即使其他维度完美，训练也会失败。

ALP 论文：维度二的工程解法

顺便提一下同天的 ALP 论文 [ref]：Adaptive Layerwise Perturbation（自适应逐层扰动），通过在模型隐藏层注入可学习的高斯噪声来平滑策略分布，统一解决了 training-inference mismatch 和 policy staleness 两个问题。

核心想法简洁：off-policy 不稳定的根源不只是"用了错的 importance ratio"，更是几何问题——策略在 sharp region 时，小的分布偏移就导致 importance ratio 爆炸。ALP 通过扰动让策略变平滑，从而抑制 heavy-tailed ratio。

方法	Math500	AIME24	AIME25	平均
GRPO	75.91	16.77	10.94	35.77
Token-MIS	77.84	17.40	10.83	36.41
Token-ALP	78.10	21.46	11.77	37.87

在 multi-turn TIR 上差距更大：Seq-ALP 平均 50.53 vs 最强 baseline Token-MIS 48.74。

ALP 本质上是维度二（分布匹配）的工程优化——让 training policy 自动适应 inference engine 的分布偏差。有理论支撑（KL bound 依赖 $\sigma^2 / \|\zeta\|^2$ ），也有实验验证（KL 保持稳定，entropy 不崩溃）。不改变五维度框架的结构，但提供了一个优雅的维度二解法。

对五维度框架的修改建议

维度五需要扩展：从"初始行为 repertoire"扩展为"初始能力 + 状态表示"。Markov states 论文表明，即使 base model 有行为，如果 RL 的输入表示导致搜索空间指数膨胀，训练也会失败。
或者保留五维度，新增"适用边界条件"注释：明确五维度框架的隐含假设——policy 的输入表示不会导致搜索空间指数膨胀。在多步推理/多 turn agent 场景中，这个假设可能不成立。

暂时倾向选项 2，因为 Markov states 论文的实验环境（完美 state transition function）和一般 LLM RL 环境差距太大。等看到更多在自然语言推理任务上的验证后再决定。

一个有趣的联系

论文提到的 “thinking mode hinders multi-step solving”（Section C.8）很值得注意：当允许 CoT 时，模型倾向于在 reasoning trace 中隐式预测未来棋盘状态，这实际上是在做 internal state prediction。但这和用外部 transition model 做 state prediction 的效果完全不同——内部预测可能不准确且不可验证，而外部 model 提供的是一个 explicit, checkable state。

这和我之前关于约束满足需要成对交互的发现有联系：显式的 Markov state 提供了一个中间检查点，让约束传播可以在每一步发生，而不是在最终答案时才验证。

核心论文：Yuan & Xie (2026), “Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States” [ref]
辅助论文：Ye et al. (2026), “Adaptive Layerwise Perturbation: Unifying Off-Policy Corrections for LLM RL” [ref]