CAST：把游戏求解器变成 LLM 智能体的回合级教师

关联论文：2607.25308
作者：spark
更新：2026-07-30

一句话结论

CAST 用「classical game solver 在 LLM 行动前后的 cost-to-go 变化」作为 turn-level 教师信号，无需求教师 logits，就能获得理论上等价于 on-policy distillation 的密集监督；在 Sokoban / Minesweeper / Rush Hour 三类游戏上全面超过 outcome-only RLVR 与 GiGPO，并零样本迁移到 ALFWorld 与 WebShop。

它在解决什么真问题

让 LLM 学会「在长 horizon 决策环境里持续推理并行动」，是 generalist agent 路线上的关键节点。RLVR（Reinforcement Learning with Verifiable Rewards）的成功集中在单轮 / 短链推理上 —— 在长程游戏 / 决策类任务里直接套用，会暴露两个老问题：

回报过于稀疏：终局赢 / 输的 0/1 标量没办法指明「trajectory 里的哪一步是关键」。
过程信号要么贵、要么不可靠：tree search（MCTS）、learned process reward model、cross-trajectory comparison（GiGPO）各有 trade-off。

同时还存在一类被忽视的资源——classical game solver：

它对任意中间状态都能给出 cost-to-go（即距离解还有多少步）；
它便宜（推理一次状态评估，常常比一次 LLM 决策还快）；
它准（Sokoban、Minesweeper、Rush Hour 等上能做到接近最优）。

但用 solver 做 SFT（即行为克隆）有个硬伤：只在 solver 到达过的状态上做监督，模型一偏离正轨，立刻失去引导——所以「on-policy 探索 + solver 引导每一步」才是闭环的。

CAST 的核心定位：把 solver 折成「turn-level 教师信号」注入 RLVR，不暴露全部 logits、不引入新模型、不跑树搜索。

核心方法

1. 把游戏建模成多轮 MDP

状态空间 S、动作空间 A，horizon H，单轮 return 仅有终态的 0/1 稀疏奖励。
让 LLM policy π_θ 在 on-policy 轨迹 τ = (s_0, a_0, …, s_T) 上优化。

2. GRPO 起点 & 它的瓶颈

CAST 直接套在 GRPO（DeepSeek 提出的 group-relative policy optimization）之上：

Â_i^outcome = (R_i - μ_R) / (σ_R + δ),   μ_R, σ_R over G group trajectories
J_GRPO(θ)  = E_q, {o_i}~π_θold [ (1/G) Σ_i (1/|o_i|) Σ_t
              ( min(ρ_t Â_i, clip(ρ_t, 1-ε, 1+ε) Â_i) - β_kl KL[π_θ‖π_ref] ) ]

问题：这里 Â_i 是整条 trajectory 共用的标量，每个 token / 每个 step 都拿同样分数——长 horizon 下信用归因彻底丢失。

3. 用 solver 给出「每步打分」：cost-to-go 差分

定义 solver 对每个状态的 cost-to-go：

Sokoban / Rush Hour：从当前 board 到解最少多少步；
Minesweeper：清除所有安全格最少需要的 reveal 数。

为 RL 化引入辅助最短路径目标（每步 −1，终点 0），把状态价值定为：

V^πSolver(s) = -N(s)
Q^πSolver(s, a) = -1 + E_{s'}[V^πSolver(s')]
A^πSolver(s, a) = -1 + N(s) - E_{s'}[N(s')]    # 即 N(s) - N(s') - 1

物理含义：这一步把 cost-to-go 推进了多少。

关键性质：只暴露 scalar，不暴露 logits——这是它和经典 KD / on-policy distillation 的最大区别。

4. 把 solver advantage 折进 RLVR

把 GRPO 的 outcome advantage 与 solver advantage 加性合并，作为 token / step 级额外监督信号：

最终训练目标本质上是 maximize 「在某状态下，solver 觉得好的 action 的对数似然」；
solver benefit 体现为对 GRPO 的 advantage shift：好的 action 拿到更高 advantage，差的 action 拿到更低。

5. 两个轻量稳定化技巧

solver value 跨不同游戏的尺度悬殊（Sokoban 数千步量级，Rush Hour 类似；Minesweeper 直接是 reveal 数），不归一化会训崩：

asinh 压缩：asinh(x) 把极大 / 极小值平滑压到线性区间附近——理论证明这一步相当于一个 robustified KL 上界；
batch-level RMS 归一化：以一个 batch 的 RMS 把不同 domain 的信号拉回可比量级。

加起来，让 solver advantage 几乎「免费」地成为 RLVR 里稳定、可移植的过程监督。

6. 核心定理：等价 on-policy distillation

CAST 给出的关键定理（论文 Thm 2.1）：

在「soft-optimal solver」假设下，最大化上面定义的 solver advantage 等价于 on-policy distillation（OPD），但只需要 scalar value，不需要 teacher 的完整 action 分布 / logits。

直觉：solver 的隐式 action distribution（在某状态下一步到达状态 s′ 的概率）对 log-prob 的梯度，与「N(s) − N(s′) − 1」对 log-prob 的梯度严格正比（差一个常数）。

这解锁了一件事：只要有 cost-to-go 这一个数，就能蒸馏一个 teacher——意味着将来在「没有显式 solver 但有 learned value network」的场景里（比如多智能体仿真 / 谈判 / 决策层级的助手），同样适用。

关键实验与数据

游戏三件套：

Sokoban：长程规划 / 死锁陷阱规避；
Minesweeper：partial-observation 推理（用信息状态化处理成 MDP）；
Rush Hour：约束型组合搜索。

主要结果：

CAST 在三个游戏的 in-domain 与 unseen-difficulty（更难的关卡）两种设定下，全部跑赢所有 trained baselines（论文摘要原文：原文未明确给出全部表格的具体数值，上口径「across Sokoban, Minesweeper, Rush Hour, CAST outperforms all trained baselines on every game under both in-domain and unseen-difficulty evaluation」）；
相对 outcome-only RLVR 的训练加速：达到 DAPO 的 peak validation 性能所需的 step 数显著更少（原文表述：「reaches DAPO's peak validation performance in substantially fewer training steps」）；
零样本外推到 ALFWorld 与 WebShop（不在这两个上微调），平均表现最高（摘要口径：「achieves the highest average zero-shot performance on ALFWorld and WebShop」）；
具体每局数值仍需查正文 Table / Appendix 为准——本文以摘要口径为准。

Sokoban / Minesweeper / Rush Hour 之外：

baseline 包括 outcome-only RLVR（DAPO 等）、process 级的 GiGPO；
消融实验验证 solver advantage 权重 + asinh + RMS 三件事各自不可少；
实验还测了「把 exact solver 替换成 learned value network」——「learned value network retains much of the benefit of exact solver guidance」，证明 CAST 不强依赖精确求解器，对工程落地友好；
solver 调用 overhead 论文表述为「negligible overhead」。

亮点与局限

亮点

Logit-free distillation：用 cost-to-go 差分这一标量，推导出与 OPD 等价的目标，避开 logits / action distribution 的传递与对齐成本。
理论 ↔ 工程一致性高：Thm 2.1 + asinh/RMS 稳定化两件套共同把「看起来粗暴的 scalar 信号」严格收敛到稳定训练轨迹上。
零样本跨域迁移：3 个游戏训出来，直接打到 ALFWorld / WebShop 平均最佳——说明它学到的是「state-value-driven decision-making」这一抽象，而不是特定游戏套路。
对 solver 类型友好：哪怕换成 learned value network 也跑得动；这意味着对无法用确切 solver 求解的现实任务，价值网络化的 CAST 是可行替代。

局限

依赖可用的 cost-to-go 估计：必须有一个能给出 N(s) 的近似（classical solver / value network / heuristic）。在 N(s) 极难估计（如开放式网页任务）时，需要先解决 cost-to-go learning 这一前置问题。
稀疏 reward 仍然主导：CAST 提供的是 dense process supervision，但最终目标仍是终态的 0/1。若任务根本没有清晰 termination / success 定义，需要另外构建 verifier。
跨域迁移的覆盖范围仍偏游戏 + ALFWorld / WebShop；更复杂的 long-horizon GUI / web agent、长程多步决策任务未在原 paper 提供对照表（原文未明确给出）。
推理时仍要调用 solver：哪怕是 learned value network，对实时性要求高的场景（<50 ms 决策闭环）会有挑战——虽然论文说 overhead negligible，但 premise 是 solver / value net 都很快。
soft-optimal solver 假设：当 solver 不是 soft-optimal 或与人类目标有偏差时，隐式 action distribution 的正比关系不再成立，需谨慎使用。

对工程落地的启发

游戏 / 仿真环境 RLHF 训练 pipeline：比起起一个 PRM，训练一个 cost-to-go value net 并跑 CAST 路线更轻、更稳。
决策类助手（数据库 agent、报表 agent、客服多步操作）：先在仿真里拟合 value net，再做 on-policy 蒸馏，是绕过 PG hallucination 的可执行路线。
多阶段交互评测：不要只评估 outcome 准确率，引入 N(s) 式的中间过程分，能让 RLVR 更细粒度——CAST 的稳定性技巧可直接复用。
跨任务迁移：solver advantage 信号本身就有抽象层含义，比起 SFT 路线更接近「学 skill」而非「背轨迹」，可直接套用到数据稀缺的工业场景。

与同方向工作的关系

GRPO / DAPO / PPO-family：CAST 是它的 additive extension，在 advantage 层叠加 solver shift，没有破坏原有 RLVR pipeline。
Process Reward Model (PRM) 系列：CAST 是 PRM 的极简替身——直接用 solver 状态评估取代 learned critic，理论上更稳、训练更便宜。
Tree-search guided RL（e.g., Hao et al., 2023 MCTS-in-RL）：CAST 主动避开搜索开销，把价值信息压成 scalar。
GiGPO（cross-trajectory comparison）：都是 dense signal 路线，但 GiGPO 在「同 prompt 多条 rollout 之间比」拿 credit；CAST 拿的是「同 state 上下一步决策的内生评分」，正交而非同质。
Distillation into LLM policy（e.g., Lu et al., 2025 KD 系列）：CAST 的最大创新是 logit-free OPD——传统 KD 必须拿 logits，CAST 只拿 scalar。
Solver-in-the-loop SFT（旧路线，模仿 solver 行为）：CAST 的关键差异在于 on-policy：模型自己探索，solver 即时纠偏，避免轨迹外状态失控。

适合谁读

LLM agent / RLHF 工程师：想把 RLVR 扩展到长 horizon 决策任务、但又不想训 PRM 或跑 MCTS；
博弈 / 决策类研究者：长期苦于「sparse reward + LLM」训练不稳的人；
agent infra 平台：评估引擎想提供 turn-level credit 接口的工程团队；
跨域迁移研究者：关心「在一个游戏训成后能不能零样本落到另一个」的人——CAST 给了一个验证点；
学生 / 学术 reviewer：做 process supervision、distillation、RL + LLM 交叉方向的人——Thm 2.1 + asinh/RMS 是直接可引用与可复现的小模块。

进一步上下文：为什么「solver」会迷 LLM agent

在 LLM agent 这个领域，「solver」是一个被低估的角色。传统 ML 里「teacher」几乎都意味着「另一个大模型」。CAST 点出一个看起来反直觉但实用的结论：在 reliable signal 中，an oracle on state（哪怕只是个 scalar）是比另一个 oracle on text 更好的老师。原因有三：

状态价值在 MDP 意义上是唯一充分的信号——而 teacher logits 只在不嫡上覆盖 action space。
signal 传递便宜：传一个标量 vs. 传 32k-token logits的不可比。
环上稳定：solver 的 value 在初始上下文里不会偏离、不会随训练漂移；teacher logits 会。

这条哲学可以在更广的 agent 选型里扩散：

代码 agent：CEGAR / uni-direction program analysis 作为 solver。
报表 agent：SPJ / formal schema checking 作为 solver。
检索 / RAG agent：independence score / known-item recall oracle 作为 value-only cost-to-go 近似。
内部远期转向多智能体代价估计：还存在可以拿一批 agent 完成同一个任务，徽 reciprocal value estimation 作为 cost-to-go估计。

在 LLM 训练过程中，从来不是「最准」重要，而是「最准不变」重要。 CAST 巧妙地将这个准则在 LLM agent 上重述了一遍。

与具体算法的等价位面（便于上手）

GRPO：CAST = GRPO + solver advantage shift。在实现上只需要在 advantage 计算处加一个 branch，把 solver N(s)−N(s′)−1 通过 asinh + RMS 后叠加即可。
DAPO：开源 DAPO 训练器（Yu et al., 2026a）支持 plug-in process term；CAST 可以作为 DAPO 的 dense supervisor 变种接入。
GiGPO：同属 dense 信用族；GiGPO 解决的是「同 prompt / 多 rollout 间」的比较，CAST 解决的是「同一 state 下的 step 内」评分——两者在数据稀疏时可叠用。
PRM (Process Reward Model)：PRM 在 cost-to-go 难估计时是兜底；CAST 是 PRM 在「能拿 N(s)」时的严格简化形式。

与落地栈的对接点

RLHF 框架：veRL / TRL / OpenRLHF 等的 advantage 计算函数加一个 solver branch 即可；不依赖 logits / teacher model，部署上不需要并行 teacher forward。
游戏 / 仿真 pipeline：Sokoban / Rush Hour / 24-puzzle 等都有现成 A* solver，可直接调用 N(s)；Minesweeper 的 cost-to-go 用 reveal-minimum 数即可；paper 给出 learned value net 兜底，工业上可接 light DQN（少于 1 ms / call）。
客服 / 助手 agent：先在仿真里收集状态价值数据；再在生产用 value net 替代；可作为「长程会话 RLHF」的入门项目。

实现伪代码 / 对接入伀

# in advantage computation hook
for traj τ_i in group_of_G:
    # outcome term (same as GRPO):
    A_i^outcome = (R_i - mean(R)) / (std(R) + eps)

    # solver term (new branch in CAST):
    A_i^solver = 0
    for (s_t, a_t, s_{t+1}) in τ_i:
        N_t   = cost_to_go_solver(s_t)        # e.g., A* on Sokoban board
        N_tp1 = cost_to_go_solver(s_{t+1})
        raw   = N_t - N_tp1 - 1               # N(s) - N(s') - 1
        A_i^solver += asinh(raw)               # robust compression
    A_i^solver /= max(1, len(τ_i))            # per-step mean
    A_i^solver /= (rms_over_batch + eps)      # batch-level RMS normalization

    # combined shift onto outcome advantage:
    Â_i = A_i^outcome + λ_solve * A_i^solver

# then run standard PPO/GRPO update with Â_i

几个工程点：

λ_solve 是需要 tune 的「solver 强度」。过高会退化为模仿 solver；过低回到 outcome-only。论文未明确披露（原文未明确）。
在胜者-败者资信区分不清晰的场景中，可以仅在胜者上叠上 solver advantage、败者不叠。
value net 可以冷启动从 imitation learning 学到一个「近似 N(s)」后与 LLM 联合训练，逐步逼近 exact solver。

soft-optimal solver 假设的具体含义

CAST 定理 2.1 依赖「soft-optimal」条件：solver 的隐式动作分布可以写成 Boltzmann 形式（与 value 有可微动作）。

经典 A* 在求 optimal 1 个解时不是 soft-optimal，但可以拿「最短路长度」重新抽样成 soft action distribution 实现「宁可走几乎一样短的路径」；
这个假设不严格时就退化为「启发式动量辅助 RLVR」而非「严格 OPD」，但论文表明这一点不太敏感（原文未明确给出饱和点）。
工业可妥协：哪怕一个「次优但可微」的启发式，都能作为信号源使用。

推理与训练开销总体估计

以 Sokoban 6×6 / 10×10 为例：

exact A*：单调用几十到几百微秒；
LLM 单 token decode：几到几十毫秒；
solver overhead 远低于 forward；采取「金世界」工业使用没压力。
难场景（围棋 / 围棋变体等）：可换成「蒙特卡洛 cost-to-go」以避免 exact solver 不存在，代价是查询变慢但仍优于 MCTS-level RL。

关于论文公开资源的提醒

代码：https://github.com/Wloner0809/CAST（论文明确给出）。
数据集：3 游戏环境都是开源版本，Sokoban FB / Minesweeper Gym / Rush Hour GitHub 仓库均可复用。
模型 checkpoint：未在论文中明确是否随代码一并发布（原文未明确）。

备注：本文中所有性能声明（in-domain / unseen / 零样本迁移 / 训练步数加速）均直接来自 paper Abstract；具体 per-game / per-baseline 的表格数字需查正文与 Appendix，原文摘要口径以「outperforms all trained baselines on every game」「highest average zero-shot performance on ALFWorld and WebShop」为准。

工程落地与核查（Jay）

核查：存疑处

零样本迁移 ALFWorld / WebShop 的实际数字：摘要仅用「highest average zero-shot performance」定性，未给具体数字；ALFWorld 与 WebShop 与训练游戏（Sokoban / Minesweeper / Rush Hour）的 domain gap 极大，读者应保留预期——表格数字差 1~2 pp 即可能逆转名次。
Thm 2.1 等价 OPD 的前提：依赖 soft-optimal solver 假设；A* exact solver 并非 soft-optimal（输出单解），需额外 softmax 化方能严格满足「正比」条件。论文对该假设的敏感性未做 ablation，落地时建议用不同温度参数探查。
λ_solve 超参数未披露：过高的 solver advantage weight 会导致 policy 退化为 solver 的行为克隆；当前无公开 ranges。建议从 0.1~0.3 开始 grid search，以 validation outcome reward 不下降为前提。
solver overhead 声称「negligible」的前提：Sokoban 的 A 在死亡格局下可能深度搜索，单次可达秒级；「negligible」是在「大部分状态 A 能快速返回」的假设下成立。生产接入前务必打 p99 延迟。
learned value network 作为 exact solver 替代的保真度：论文仅报告「retains much of the benefit」——未量化「much」对应多少百分点；工程替换时需自行 benchmark。

工程落地要点

接入障碍与坑：

状态序列化是主要工程成本：每步需把 LLM 生成的 board state 转为 solver 可读的格式（Sokoban 的 box/player coordinates、Minesweeper 的 reveal/bitmask）。不同游戏需独立实现 parser；若 LLM 输出格式漂移，solver 会静默失败。建议在 env wrapper 层加 schema 校验。
asinh 压缩的梯度方向：asinh 在 |x|>10 时近似 sign(x)·log(2|x|)，会压缩大幅值但保留符号和梯度方向——这对负值（cost-to-go 倒退）同样生效，意味着 solver 认为是倒退的一步也会有梯度，不会被静默抹平。
batch-level RMS 的分布偏置：若一个 batch 内混合了 Sokoban（cost-to-go 千位数）和 Minesweeper（个位数），归一化后的信号会偏向大尺度域。可考虑 domain 分桶归一化而非全 batch 统一 RMS。
推理时 solver 的 p99 延迟：在 Rush Hour 的深层搜索格（深度 >30），A* 节点数爆炸；生产 pipeline 应给 solver 加 timeout（建议 ≤100 ms），超时则 fallback 到上一个 best action 或跳过 solver advantage。
continuous task 不存在终态 0/1：CAST 的推导依赖终态稀疏 reward；开放式 agent 任务（如网页操作、多轮对话）若无清晰 termination，需先构建 binary/numeric verifier，再用 CAST。

冷启动路线（无需 exact solver）：

1. 用少量专家轨迹（human demo）做 imitation learning，学一个 V_θ(s) 作为 N(s) 的初始近似
2. V_θ 与 LLM π_θ 联合训练，V_θ 逐步逼近「真实」cost-to-go
3. 替换 exact solver 后验证：V_θ-advantage 与 exact-solver-advantage 的 token-level KL 不超过 0.5

实际系统怎么集成：

Env wrapper：在现有 gym-style env 的 step() 返回值里追加 info['cost_to_go'] = solver.estimate(state)；advantage hook 统一读取此字段。
无需改 GRPO 主体：仅在 advantage 计算处插入 solver 分支；原有 KL constraint、clipping 全部保留。
多游戏混合训练：建议先按游戏分 domain 做 RMS 归一化，再 cross-game 混合——避免单一大 batch RMS 抹平游戏间尺度差异。

资源估算（单卡 A100 80G）：

Sokoban 6×6：每 batch 8 trajectories × 128 steps，solver call 总计 < 5 ms（全部并行）；overhead 可忽略
Rush Hour 9×9：深度搜索格可能出现 >100 ms 单次调用；建议加 solver timeout + async queue
LLM decode：每 step ~50 ms（vllm batch inference）；solver 需 < 10 ms 才能保持 pipeline 不拖尾