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:
- Action likelihood:动作在当前上下文下的生成概率,反映 agent 对该动作的先验偏好。
- State confidence:如果 next state 需要 world model 采样得到,例如 GSM8K 的子问题答案,则通过多次采样的一致性衡量置信度。
- Self-evaluation:把当前 reasoning step 喂给 LLM,让其判断 “Is this reasoning step correct?”,并取 token
Yes的概率作为奖励。 - 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 聚合回去更新 ”。
代码实现与论文高度一致,但有三点工程化修改值得单独记:
rap/mcts.py用prior=True时,会给未访问 child 一个基于当前 reward 的先验,而不是纯随机初始值。MCTS._simulate(...)中默认 rollout policy 是不断取find_one_child();而 task-specific node 会在 child generation 前先计算 reward,因此 simulation 实际上依赖各任务的局部 reward 设计。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, priorsdef 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, priorsdef 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_answersdef 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 Concept | Source File | Key Class/Function |
|---|---|---|
| Generic MCTS tree search | rap/mcts.py | MCTS, _uct, _select, _expand, _simulate, _back_propagate, max_mean_terminal |
| LLM wrapper / next-token yes-no scoring | rap/models.py | QueryLM, QueryLlama.query_LM, QueryLlama.query_next_token |
| Blocksworld task instantiation | rap/blocksworld_mcts.py | ReasoningMCTSNode, gen_fn, r1_fn, reward_fn, reasoning_mcts_search |
| Blocksworld experiment launcher | run_blocksworld.py | ReasoningTasks.run_mcts, CLI args --rollouts --max_depth --alpha |
| GSM8K task instantiation | rap/gsm8k_mcts.py | ReasoningMCTSNode, gen_fn, r0_fn, r1_fn, reward_fn, reasoning_mcts_search |
| GSM8K result aggregation | aggregate_gsm8k.py | aggregate, reward-weighted answer voting |
| GSM8K experiment launcher | run_gsm8k.py | main_mcts, prompt paths, --speedup-confidence-batch-size |
| ProntoQA task instantiation | rap/prontoqa_mcts.py | transit_fn, reward_fn, reasoning_mcts_search |
| ProntoQA experiment launcher | run_prontoqa.py | main_mcts, default rollouts/depth/temperature |
论文公式与 released code 实现差异:一是 GSM8K 代码中的 reward 变量命名与论文中的 含义并不完全同名,confidence 与 self-evaluation 的实现路径分别落在 r1_fn 与 r0_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 Acc和Proof 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.5,w_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。 - ProntoQA:
run_prontoqa.py默认llama_ckpt=.../13B、n_sample_subquestion=9、mcts_rollouts=20、temperature=0.5、max_depth=7、w_exp=1、max_batch_size=3、max_response_length=200。
需要注意,训练/推理数值以真实启动脚本为准,而不是 README 泛化描述。这里所有具体数字都来自 run_blocksworld.py、run_gsm8k.py、run_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 主表精确数值如下:
| Method | 2-step | 4-step | 6-step |
|---|---|---|---|
| CoT | 0.17 | 0.02 | 0.00 |
| CoT - pass@10 | 0.23 | 0.07 | 0.00 |
| CoT (GPT-4) | 0.50 | 0.63 | 0.40 |
| RAP(10) | 1.00 | 0.86 | 0.26 |
| RAP(20) | 1.00 | 0.88 | 0.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 主表精确数值如下:
| Method | Accuracy (%) |
|---|---|
| Chain-of-Thought | 29.4 |
| + SC(10) | 46.8 |
| Least-to-Most | 25.5 |
| + SC(10) | 42.5 |
| RAP(1) | 40.0 |
| RAP(10) | 48.6 |
| + aggr | 51.6 |

Figure Table 3 解读:ProntoQA 上,RAP 把 Pred Acc 提升到 94.2,Proof Acc 提升到 78.8,明显高于 CoT=87.8/64.8。这说明 RAP 不只是更会猜 final label,也更能构造正确的 proof chain。
ProntoQA 主表精确数值如下:
| Method | Pred Acc | Proof Acc |
|---|---|---|
| CoT | 87.8 | 64.8 |
| CoT + SC | 89.8 | - |
| RAP (Ours) | 94.2 | 78.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 精确数值如下:
| Setting | Method | 2-step | 4-step | 6-step | 8-step | 10-step | 12-step | All |
|---|---|---|---|---|---|---|---|---|
| Easy | CoT | 0.49 | 0.18 | 0.06 | 0.01 | 0.01 | 0.00 | 0.08 |
| Easy | RAP(10) | 1.00 | 0.99 | 0.75 | 0.61 | 0.32 | 0.32 | 0.65 |
| Hard | CoT | 0.22 | 0.14 | 0.02 | 0.02 | 0.00 | 0.00 | 0.05 |
| Hard | RAP(10) | 0.67 | 0.76 | 0.74 | 0.48 | 0.17 | 0.09 | 0.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 精确数值:
| R1 | R2 | R3 | Success |
|---|---|---|---|
| ✓ | ✓ | ✗ | 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):
| R1 | R2 | R3 | RAP(1) | RAP(10) | +aggr |
|---|---|---|---|---|---|
| ✓ | ✗ | ✓ | 0.410 | 0.450 | 0.503 |
| ✓ | ✗ | ✗ | 0.350 | 0.447 | 0.490 |
| ✓ | ✓ | ✗ | 0.373 | 0.423 | 0.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 工作的重要起点之一。