Reasoning with Language Model is Planning with World Model

Paper: arXiv:2305.14992 Code: Ber666/RAP Code reference: main @ 774817c2 (2023-08-25)

1. Motivation (研究动机)

已有 LLM reasoning 主要依赖 autoregressive decoding,例如 Chain-of-Thought (CoT) 或 Least-to-Most prompting;它们能生成看似合理的 reasoning trace,但本质上仍是在局部 token likelihood 下向前展开,而不是像人类那样显式维护环境状态、预演未来后果并基于长期收益做计划。论文指出这种范式在三类任务上尤其吃亏:需要合法动作序列的 plan generation、需要中间变量管理的 math reasoning、以及需要多跳规则应用的 logical inference。

作者要解决的具体问题不是“让 LLM 更会思考”这种泛目标,而是让 LLM 在给定当前状态时,能够生成动作、预测下一状态、评估该步是否值得继续,并在大搜索空间里平衡 exploration / exploitation。换句话说,论文把 reasoning 重新表述为一个 planning problem:状态是当前推理上下文,动作是下一步 reasoning operation,世界模型负责预测动作后果,reward 负责评估当前分支是否朝目标逼近。这个问题值得研究,因为它把“prompt engineering 式 reasoning”提升为“search over reasoning traces”。

一旦这个表述成立,LLM 就不再只能一条路走到黑,而是可以像 classical planning 或 model-based RL 那样回溯、试错、对比备选路径。论文在 Blocksworld、GSM8K、ProntoQA 上验证这一点,说明 deliberate planning 能给语言模型带来超出单路径 CoT 的能力增益。

2. Idea (核心思想)

RAP 的核心 insight 是:LLM 不仅可以当 action generator,也可以在 prompt 条件化下充当 world model,从而把多步推理过程变成一个可以被 MCTS 搜索的状态转移系统。 一旦状态、动作、reward 被明确定义,reasoning 就从“直接生成最终解答”变成“在 reasoning tree 上搜索高价值路径”。更具体地说,论文并没有另训一个专门 world model,而是把同一个 LLM 通过不同 prompt 复用成两种角色:agent 负责提出下一步 action,world model 负责根据当前 state 和 action 预测 next state。

然后再用 action likelihood、state confidence、self-evaluation 和 task heuristic 组成 reward,最后让 MCTS 在 reasoning tree 上迭代选择、扩展、模拟和回传。它与 CoT 的根本区别在于:CoT 每一步只关心“接下来最像什么”,RAP 关心“这个动作把我带到什么状态、这个状态是否值得继续、如果沿这条分支往下走,长期收益是否更高”。与 Least-to-Most 相比,RAP 也不是一次性生成全部 sub-questions,而是基于当前 state 动态决定下一步 action,因此更接近 closed-loop planning。

3. Method (方法)

3.1 Overall framework

RAP 将每个 reasoning problem 都写成一个 Markov decision process。当前 state 描述当前推理上下文,action 是下一步要执行的 reasoning step,world model 预测 ,reward 评估这一跳是否有价值。算法主体是 MCTS:在固定 rollout budget 下,不断从 root 沿 UCT 选择 promising node,扩展新动作,模拟未来,并将收益向上回传,最后选取得分最高的一条 reasoning trace。

Figure 1 解读:图 1 对比了普通 CoT 与 RAP。左侧 CoT 只有单条 autoregressive trace;右侧 RAP 显式加入了 world model、reward 与 planning。关键信息不是“多了一个搜索树”这么简单,而是 state 被单独建模后,LLM 可以在心智模拟意义上先预测后果,再决定是否继续扩展该分支。

Figure 2 解读:图 2 展示 RAP 在三类任务中的 state/action 具体化方式。Blocksworld 中,state 是 block configuration,action 是自然语言动作;GSM8K 中,state 是已知中间变量集合,action 是新子问题;ProntoQA 中,state 是当前关注的 claim/fact,action 是下一条 rule application。这个统一视角说明 RAP 的贡献不是某个任务特化 prompt,而是一种可迁移的 reasoning-as-planning 抽象。

从直觉上看,RAP 成功的关键不是“搜索”本身,而是把 LLM 的 implicit knowledge 重新拆成三个显式接口:生成候选动作、预测动作后果、评估该步质量。传统 CoT 把这三件事压缩到一个 next-token distribution 里;RAP 则把它们拆出来,用 planning algorithm 协调。这样做的好处是,局部上看起来高概率但长期走不通的分支可以被及早识别,而不是把整条错误链生成完才发现结论不对。

3.2 Language model as world model

论文把 world model 定义为条件转移分布: 这里的 不是新训练得到的 world model 参数,而是被 prompt 重新配置后的同一个 LLM。作者强调,state/action 定义依任务而变:

  • Blocksworld: 是当前 blocks 的自然语言状态描述,pick up / unstack / put down / stack 之一。
  • GSM8K: 是已知中间变量及其值, 是新的 sub-question。
  • ProntoQA: 是当前聚焦的 claim 或事实, 是选取下一条逻辑规则或 Finish.

released code 里这一点对应三套 task-specific transition implementation:

  • rap/blocksworld_mcts.py 通过 world_update_* prompts 让 LLaMA 输出 [CHANGE],再调用 apply_change(...) 把自然语言 change 应用到上一状态,得到新状态。
  • rap/gsm8k_mcts.py 用 world model 回答子问题,解析 "The answer is ..." 得到新的中间变量值。
  • rap/prontoqa_mcts.py 对 rule-based facts 做一步 transit,并对 Finish. 走单独 prompt。

这说明论文里的 “LM as world model” 不是抽象口号,而是具体的 prompt-conditioned transition operator。

3.3 Reward design

论文提出三类通用 reward,再允许每个任务增加 heuristic:

  1. Action likelihood:动作在当前上下文下的生成概率,反映 agent 对该动作的先验偏好。
  2. State confidence:如果 next state 需要 world model 采样得到,例如 GSM8K 的子问题答案,则通过多次采样的一致性衡量置信度。
  3. Self-evaluation:把当前 reasoning step 喂给 LLM,让其判断 “Is this reasoning step correct?”,并取 token Yes 的概率作为奖励。
  4. Task-specific heuristic:例如 Blocksworld 里根据当前状态与目标状态的匹配程度打分。

论文中的 UCT 选择公式为: 对于 GSM8K,论文给出 reward 组合形式: 其中 是 LLM 对子问题 helpfulness 的自评, 是 answer consistency / confidence。

released code 与论文公式有一处重要差异:在 rap/gsm8k_mcts.py 里,节点总 reward 实际实现为 其中 r0_fn(...)query_next_token(...) 直接读取 token Yes 概率,对应自评;r1_fn(...) 通过多次 world-model sampling 统计多数答案占比,对应 confidence。也就是说,代码中的符号命名顺序与 Table 6 标注相反:代码把 self-evaluation 记作 r0 / R2 路径,把 confidence 记作 r1 / R1 路径。方法语义一致,但读代码时必须注意变量名和论文表头不是同一个记号系统。

在 Blocksworld 中,代码的 task-specific heuristic 更具体:r1_fn(...) 从新状态里抽取目标关系,如 the orange block is on top of the red block,若全部满足则直接给 r1 = 100,否则给 sum(meetings) / len(meetings) + 0.5;与动作 likelihood 的 softmax 分数做几何平均。这个高奖励终止阈值也决定了 terminal condition。

3.4 Planning with MCTS

Figure 3 解读:图 3 对应 MCTS 的四个阶段。Selection 沿当前树选高 UCT 分支;Expansion 在叶子节点采样多个 action 并生成多个 child state;Simulation 用轻量策略向前 rollout;Back-propagation 将 terminal path 的累积价值回传。对 RAP 来说,树中的 node 不是环境状态向量,而是自然语言状态,因此每一步都要调用 LLM。

Figure Algorithm 1 解读:算法 1 给出了论文层面的 RAP-MCTS。输入包括初始状态 、转移函数 、reward 、动作生成器 、每次 expansion 采样的动作数 、深度上限 、rollout 次数 和 exploration weight 。核心流程是“已访问节点走 UCT,未访问叶子做 action/state expansion,然后用局部最大奖励动作做 rollout,最后把未来 reward 聚合回去更新 ”。

代码实现与论文高度一致,但有三点工程化修改值得单独记:

  1. rap/mcts.pyprior=True 时,会给未访问 child 一个基于当前 reward 的先验,而不是纯随机初始值。
  2. MCTS._simulate(...) 中默认 rollout policy 是不断取 find_one_child();而 task-specific node 会在 child generation 前先计算 reward,因此 simulation 实际上依赖各任务的局部 reward 设计。
  3. max_mean_terminal(...) / max_terminal(...) 决定最终选 trace 的方式。代码默认常用 max_mean_terminal(root),对应论文里“选择历史上得到最高 reward 的 path”而非“选择访问次数最多的 leaf”。

3.5 Task-specific instantiations

Blocksworld

Blocksworld 的 root state 是自然语言初始局面,action 由 generate_all_actions(last_state) 枚举所有合法操作,再用 LLaMA 对不同 action sequence 的 log-likelihood 做 softmax,得到动作先验 r0。随后 world model 通过 world_update_pickup/unstack/putdown/stack prompts 预测 [CHANGE],并用 apply_change(...) 生成 next state。

def blocksworld_expand(inp, depth, prompts, world_model):
    last_state = parse_state(inp, depth)
    raw_actions = generate_all_actions(last_state)
    candidate_prompts = [append_action(inp, depth + 1, a) for a in raw_actions]
    log_probs = world_model.llamamodel.get_ll(build_baseline(inp, depth), candidate_prompts)
    priors = softmax(log_probs)
    return candidate_prompts, priors
def blocksworld_transition_and_reward(inp, depth, prompts, world_model, alpha):
    last_state = parse_previous_state(inp, depth - 1)
    last_action = parse_last_action(inp, depth)
    change = world_model.query_LM(select_world_prompt(last_state, last_action), do_sample=False)[0]
    new_state = apply_change(extract_change(change), last_state)
    heuristic = goal_match_score(new_state)  # 100 if fully solved else overlap + 0.5
    action_prior = parse_local_prior(inp)
    reward = action_prior ** alpha * heuristic ** (1 - alpha)
    return append_state(inp, depth, new_state), reward

这里最重要的直觉是:Blocksworld 并不让 LLM 直接“写整份计划”,而是每一步都要求它显式维护可执行的 state。因此 RAP 的收益很大一部分来自于避免非法动作,而不是单纯多 sample。

GSM8K

GSM8K 中,action 是下一条 sub-question。若达到最大深度,则强制发出 "Now we can answer the question" 作为 terminal action;否则从 agent prompt 采样若干子问题。对于每个候选 sub-question,r0_fn(...) 会构造 “这个 sub-question 是否有帮助” 的 prompt,并直接读取 token Yes 的概率;r1_fn(...) 会让 world model 多次回答该 sub-question,统计多数答案占比作为 confidence。

def gsm8k_generate_subquestions(inp, q_inp, depth, max_depth, world_model):
    if depth == max_depth:
        actions = [force_final_question(inp, depth)]
    else:
        actions = deduplicate(world_model.query_LM(inp + subquestion_prefix(depth), num_return_sequences=n_sample))
    priors = yes_probability_for_helpfulness(q_inp, actions, depth)
    return actions, priors
def gsm8k_confidence_reward(inp, depth, world_model):
    world_input = inp + answer_prefix(depth - 1)
    sampled_answers = sample_many_answers(world_input, n_sample_confidence)
    answer_groups = group_by_normalized_numeric_answer(sampled_answers)
    best_answer, max_count = majority_answer(answer_groups)
    confidence = max_count / len(sampled_answers)
    return best_answer, confidence, sampled_answers
def aggregate_gsm8k_paths(pickle_info, gold_answer):
    answer_dict = defaultdict(float)
    for node in pickle_info:
        output, correct, depths = parse_terminal_answer(node, gold_answer)
        answer_dict[(output, correct)] += node.reward * len(depths) / sum(depths)
    return max(answer_dict.items(), key=lambda x: x[1])

论文中的 RAP-Aggregation 对应 aggregate_gsm8k.py:不同迭代得到的 terminal answer 不是简单多数投票,而是按 reward 累计加权,因此 reward 既用于 search,也用于最终集成。

ProntoQA

ProntoQA 中,state 是当前 claim/fact,action 是下一步 rule application 或 Finish.。代码把多个采样动作按 resulting next_state 合并,对每个 next_state 保留出现次数最多的 action,然后让 world model 用 query_next_token(...) 对 “这一步有效吗” 取 Yes 概率,作为 reward。MCTS 配置为 prior=True, aggr_reward='mean', aggr_child='max'

def prontoqa_step(state, agent_prompts, world_model):
    sampled_actions = world_model.query_LM(build_agent_prompt(state), num_return_sequences=n_sample_subquestion)
    next_state_dict = merge_actions_by_transit_state(sampled_actions)
    dedup_actions, dedup_states = choose_most_frequent_action_per_state(next_state_dict)
    rewards = yes_probability_of_validity(state, dedup_actions, dedup_states, world_model)
    return list(zip(dedup_actions, dedup_states, rewards))

ProntoQA 这一任务很能体现 RAP 的“可回溯性”价值:如果某条逻辑链走到 dead end,MCTS 可以把负信号传播回更早层,迫使搜索转向别的 rule application;单路径 CoT 则经常一路把错误 premise 展开到底。

3.6 Paper-to-code mapping

Code reference: main @ 774817c2 (2023-08-25) — pseudocode and mapping based on this commit

Paper ConceptSource FileKey Class/Function
Generic MCTS tree searchrap/mcts.pyMCTS, _uct, _select, _expand, _simulate, _back_propagate, max_mean_terminal
LLM wrapper / next-token yes-no scoringrap/models.pyQueryLM, QueryLlama.query_LM, QueryLlama.query_next_token
Blocksworld task instantiationrap/blocksworld_mcts.pyReasoningMCTSNode, gen_fn, r1_fn, reward_fn, reasoning_mcts_search
Blocksworld experiment launcherrun_blocksworld.pyReasoningTasks.run_mcts, CLI args --rollouts --max_depth --alpha
GSM8K task instantiationrap/gsm8k_mcts.pyReasoningMCTSNode, gen_fn, r0_fn, r1_fn, reward_fn, reasoning_mcts_search
GSM8K result aggregationaggregate_gsm8k.pyaggregate, reward-weighted answer voting
GSM8K experiment launcherrun_gsm8k.pymain_mcts, prompt paths, --speedup-confidence-batch-size
ProntoQA task instantiationrap/prontoqa_mcts.pytransit_fn, reward_fn, reasoning_mcts_search
ProntoQA experiment launcherrun_prontoqa.pymain_mcts, default rollouts/depth/temperature

论文公式与 released code 实现差异:一是 GSM8K 代码中的 reward 变量命名与论文中的 含义并不完全同名,confidence 与 self-evaluation 的实现路径分别落在 r1_fnr0_fn;二是论文首页脚注和后续版本更强调 Ber666/llm-reasoners 作为较新的统一库,但当前可复现实验仓库是 Ber666/RAP,本笔记的 pseudocode / mapping 全部锚定在后者的 main@774817c2

4. Experimental Setup (实验设置)

4.1 Datasets and task scale

  • Blocksworld (step-limited split):按需要的最少动作数分为 2-step、4-step、6-step 三组,论文主表报告这三组成功率。
  • GSM8K:grade-school math word problems,主实验报告准确率;Table 6 的 ablation 使用前 300 个 examples。
  • ProntoQA:logical reasoning benchmark,主指标分为 Pred AccProof Acc
  • Full Blocksworld:602 个 test cases,按最小动作步数分组为 2/4/6/8/10/12-step,并分 Easy / Hard 两种 demonstration setting。

4.2 Baselines

  • Chain-of-Thought (CoT),以及在部分任务中的 CoT + Self-Consistency
  • Least-to-Most prompting,以及 Least-to-Most + Self-Consistency
  • GPT-4:用于 Blocksworld 对比。
  • 对 Full Blocksworld,baseline 是 CoT,RAP 使用 10 次 iteration 的 improved prompting 版本。

4.3 Evaluation metrics

  • Blocksworld / Full Blocksworld:success rate。对主表而言,RAP 只评估单条选中 plan;pass@10 表示采 10 条计划,只要一条正确就记成功。
  • GSM8K:Accuracy(最终数值答案正确率)。
  • ProntoQA
    • Pred Acc:最终 true/false 结论是否正确。
    • Proof Acc:给出的 proof chain 是否正确。

4.4 Training / inference config

论文明确说明是 frozen LLM inference-time framework,不是新训练一个 world model。主实验默认 base model 为 LLaMA-33B,temperature 为 0.8。Appendix B.1 还说明 generation 截断在 2048 tokens 或 newline token。Appendix B.2 与公开运行脚本一致,实验运行在 4 张 GPU 上;但论文正文没有在我们核对到的位置明确写出 GPU 型号,因此这里不虚构型号。

开源脚本给出更具体的可复现实验参数:

  • Blocksworld:README 命令是 torch.distributed.run --nproc_per_node 4 run_blocksworld.py --ckpt_path $LLAMA_CKPTS/30B --max_depth 4 --rollouts 10;CLI 默认 --rollouts=10 --max_depth=4 --alpha=0.5,代码里 r1_default=0.5w_exp=1
  • GSM8K:README 命令是 torchrun --nproc_per_node 4 run_gsm8k.py --llama-ckpt $LLAMA_CKPTS/30B --speedup-confidence-batch-size 2;代码里 MCTS 也是 prior=True,并使用 confidence sampling 与 aggregation 脚本 aggregate_gsm8k.py
  • ProntoQArun_prontoqa.py 默认 llama_ckpt=.../13Bn_sample_subquestion=9mcts_rollouts=20temperature=0.5max_depth=7w_exp=1max_batch_size=3max_response_length=200

需要注意,训练/推理数值以真实启动脚本为准,而不是 README 泛化描述。这里所有具体数字都来自 run_blocksworld.pyrun_gsm8k.pyrun_prontoqa.py 或 README 的实际 launch command。

5. Experimental Results (实验结果)

5.1 Main results

Figure Table 1 解读:Blocksworld 上,CoT 在简单 2-step case 上也只有 0.17,到了 4-step / 6-step 基本失效;GPT-4 虽然更强,但在 6-step 也只有 0.40。RAP(20) 在 2-step=1.00, 4-step=0.88, 6-step=0.42,平均成功率约 0.64,相对 GPT-4 的平均约 0.51 有约 33% relative gain。这里最关键的结论不是“RAP 比 CoT 高”,而是搜索在 combinatorial planning 场景里带来了从几乎不可用到可用的跃迁

Blocksworld 主表精确数值如下:

Method2-step4-step6-step
CoT0.170.020.00
CoT - pass@100.230.070.00
CoT (GPT-4)0.500.630.40
RAP(10)1.000.860.26
RAP(20)1.000.880.42

Figure 4 解读:图 4 的 case study 说明 RAP 优势来自三件事:第一,state tracking 使它能识别非法动作;第二,MCTS 允许 backtracking,而 CoT 一旦先做错关键决策就会把整条错误链继续写下去;第三,reward 计算时把当前 state 重新当作“新的初始问题”,降低了后半段决策难度,把预算更多留给前期关键分叉。

Figure Table 2 解读:GSM8K 上,RAP 即便只选单条 best trace,RAP(10)=48.6% 也超过了 CoT+SC(10)=46.8%Least-to-Most+SC(10)=42.5%;再做 RAP-Aggregation 后达到 51.6%。这说明 reward-guided search 找到的 candidate traces 本身质量更高,而不是单纯因为 sample 更多。

GSM8K 主表精确数值如下:

MethodAccuracy (%)
Chain-of-Thought29.4
+ SC(10)46.8
Least-to-Most25.5
+ SC(10)42.5
RAP(1)40.0
RAP(10)48.6
+ aggr51.6

Figure Table 3 解读:ProntoQA 上,RAP 把 Pred Acc 提升到 94.2Proof Acc 提升到 78.8,明显高于 CoT=87.8/64.8。这说明 RAP 不只是更会猜 final label,也更能构造正确的 proof chain。

ProntoQA 主表精确数值如下:

MethodPred AccProof Acc
CoT87.864.8
CoT + SC89.8-
RAP (Ours)94.278.8

Figure 5 解读:图 5 展示不同 sample / iteration budget 下的 GSM8K 曲线。论文结论是 RAP-Aggregation 在所有 budget 下都持续优于 baseline,尤其在预算很小时更明显,说明 reward 能把有限探索预算集中到更可靠的 reasoning path 上。

Figure Table 4 解读:Full Blocksworld + Llama-2 70B 证明 RAP 不是只对弱模型有用。尤其是步数增加到 8-step 以上后,CoT success rate 急剧下降,而 RAP 仍保持可观成功率,说明 planning 提升的是 reasoning strategy,而不仅仅是模型规模。

Full Blocksworld 精确数值如下:

SettingMethod2-step4-step6-step8-step10-step12-stepAll
EasyCoT0.490.180.060.010.010.000.08
EasyRAP(10)1.000.990.750.610.320.320.65
HardCoT0.220.140.020.020.000.000.05
HardRAP(10)0.670.760.740.480.170.090.51

5.2 Ablation findings

Figure Table 5 解读:Blocksworld ablation 显示多 reward 组合最优。R1=action likelihood, R2=task-specific reward, R3=self-evaluation reward。三者都开时 success 为 0.91;去掉 R3 仍有 0.88,说明 action likelihood + task heuristic 是核心;只保留单一 reward 时效果显著退化,尤其只留 self-evaluation 只有 0.14

Blocksworld ablation 精确数值:

R1R2R3Success
0.88
0.91
0.46
0.21
0.14
0.02

Figure Table 6 解读:GSM8K ablation 与 Blocksworld 不同。这里 R1=state transition confidence, R2=action likelihood, R3=self-evaluation。去掉 action likelihood (R2=✗) 影响相对较小,而 confidence + self-evaluation 的组合最关键;说明数学题里“这个子问题答案是否稳定”“这一步是否真的有帮助”比语言先验本身更重要。

GSM8K ablation 精确数值(first 300 examples):

R1R2R3RAP(1)RAP(10)+aggr
0.4100.4500.503
0.3500.4470.490
0.3730.4230.443

5.3 Limitations

论文明确承认三点限制。第一,RAP 依赖 frozen LLM,本身 reasoning / world-model capability 受预训练能力上限约束。第二,它主要提升 inference-time search,并没有解决如何把更强 world-model ability 学进模型参数。第三,方法计算成本较高,因为每次 expansion / simulation / reward computation 都可能触发额外的 LLM 调用。

代码层面还能看到一个现实限制:公开仓库主要支持 LLaMA-1 与 prompt-based reproduction,工程实现偏研究原型,很多 task-specific reward / transition 都是 prompt templates + regex parsing,这使其很难直接迁移到更复杂、更噪声的真实环境。

5.4 Overall conclusions

这篇论文最重要的贡献不是把 MCTS 套到 LLM 上,而是给出一个统一而可执行的分解:LLM action generator + LLM world model + task-aware reward + tree search。实验表明,这种分解在 planning、math、logical reasoning 三类任务上都有效,并且收益会随着 task 的 combinatorial complexity 增大而更加明显。RAP 因而成为后续 agentic reasoning / search-based inference 工作的重要起点之一。