Awesome_MCTS_LLM

format:
- [title](paper link) [links]
  - 论文公布时间：
  - 投/录用会议:
  - 单位：
  - 贡献：
  - 任务：
  - code：

数学推理

• RAP: Reasoning with Language Model is Planning with World Model

  • 论文公布时间：2023年8月

  • 投/录用会议: EMNLP 2023 录用

  • 单位：加州大学圣迭戈分校，佛罗里达大学

  • 贡献：大模型作为世界模型，给出状态转移用于MCTS的Rollout simulation

  • 任务：Blocksworld，GSM8k，PrOntoQA

  • Code: Official

• ReST-MCTS∗: LLM Self-Training via Process Reward Guided Tree Search

  • 论文公布时间：2024年3月
  • 投/录用会议: NeurIPS 2024录用
  • 单位：清华，加利福尼亚大学
  • 贡献：在早期验证了policy model和PRM可以迭代自训练提升
  • 任务：MATH，CEval-Hard，SciBench
  • 可借鉴： PRM引导MCTS过程（使用reasoning distance $m_k$ 作为达到正确答案的最短距离，用于给PRM加权；）
  • Code: Official

• MCTS-DPO: Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning

  • 论文公布时间：2024年5月
  • 投/录用会议: NeurIPS 2024被拒
  • 单位：新加坡国立，Deepmind
  • 贡献：MCTS 迭代收集偏好数据，用于DPO更新policy model
  • 任务： GSM8K, MATH, and ARC-C
  • Code: Official

• AlphaMath Almost Zero: Process Supervision without Process

  • 论文公布时间：2024年5月
  • 投/录用会议: NeurPIS 2024录用
  • 单位：Tongyi Lab, 通义实验室
  • 贡献：正负例样本均用于拟合价值模型；将价值模型和策略模型结合并同时训练
  • 任务：GSM8K， MATH，GaoKao2023，OCWCourses
  • 可借鉴：类似AlphaZero, PRM和policy model共用一个backbone
  • Code: Official

• Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning

  • 论文公布时间：2024年7月
  • 投/录用会议: NeurIPS2024被拒，投稿ICLR 2025 正在review
  • 单位：Skywork AI，南洋理工大学
  • 贡献：MCTS 估计过程奖励，用于迭代训练Q model
  • 任务： GSM8K， MBPP
  • 可借鉴：用三种方法估计Optimal Q-value：offline RL，random rollout, 更强LLM估计。
  • Code: 未公布

• ALPHALLM-CPL: Towards Self-Improvement of LLMs via MCTS: Leveraging Stepwise Knowledge with Curriculum Preference Learning

  • 论文公布时间：2024年10月
  • 投/录用会议: 投稿ICLR 2025 正在review
  • 单位：马里兰大学，腾讯
  • 动机：MCTS蒸馏出来的策略性能匹配不上MCTS
  • 贡献：采用课程学习的方法训policy model，选样本的依据是external reward gap and policy prediction gap的加权求和
  • Code: 未公布

Agent

• LLM-MCTS: Large Language Models as Commonsense Knowledge for Large-Scale Task Planning
  • 论文公布时间：2023年5月
  • 投/录用会议:NIPS 2023录用
  • 单位：新加坡国立大学
  • 贡献： LLM不仅作为策略模型，还作为世界模型生成初始状态，引导MCTS的搜索
  • 任务：VirtualHome (具身智能)
  • Code: Official
• LATS: Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models
  • 论文公布时间：2023年10月
  • 投/录用会议: ICML 2024录用
  • 单位：伊利诺伊大学厄巴纳-香槟分校
  • 贡献：将MCTS用到agent的test time search中
  • 任务：HotPotQA, MBPP，HumanEval, WebShop
  • Code: Official
• Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents
  • 论文公布时间：2024年8月
  • 投/录用会议: 投稿ICLR 2025 正在review
  • 单位：AGI Company (MultiOn), 斯坦福大学
  • 贡献：
  • 借鉴：使用了PlanReAct的方法，在第一步的生成动作时给出了plan; 状态用的是之前的动作和当前的观测，大大减少了上下文长度； 模型使用的是xLAM-v0.1-r，在多个智能体任务上都微调过，prompt用的AgentLite；
  • 任务：Webshop, OpenTable
  • Code: 未公布

方法梗概汇总（时间顺序）

方法	时间	MCTS用法；用途	策略模型	奖励模型	训练方法	创新点	不足
LLM-MCTS	2305	常规；search	在专家数据集上微调	无	无	使用世界模型生成先验知识进行指导（prompt），引导MCTS的搜索
RAP	2308	常规；search	不训练	无	无	大模型作为世界模型，提供状态转移用于MCTS evaluation
LATS	2310	(1) a self-generated LM score and (2) a self-consistency score用于value估计；search	不训练	无	无	首次将LATS引入智能体任务，并配合self-reflection等agent方法	不涉及训练，推理时还要求环境可回溯
ReST-MCTS∗	2403	PRM Guided Search, Self-Critic用于提前终止检索，剪枝未完成叶子节点; 收集偏好数据	正样本微调	正负样本+MSE	策略和PRM都迭代多轮	PRM Guided Search	为了得到绝对的value值，抽取流程很复杂
AlphaMath Almost Zero	2405	使用当前策略做PUCT，使用PRM做rollout时的value估计；构建偏好数据	正样本微调	正负样本+MSE	策略&奖励同时训练并迭代多轮	价值模型和策略模型结合，用多任务损失函数同时训练
MCTS-DPO	2405	使用当前策略做PUCT；收集偏好数据	MCTS收集的数据使用DPO训练	无	策略迭代多轮	首次用DPO训练MCTS构建得到的偏好对
Q *	2406	A*而非MCTS, 使用策略做rollout；构建Q-value标签	在专家数据集上微调	MCTS收集的数据训练Q model拟合标签(MSE)	一轮Q-value Model	Inference时将Q value model加入启发式函数进行规划
Agent Q	2408	常规；收集偏好数据和search	正负样本，使用DPO训练	无	一轮策略迭代	将MCTS收集偏好数据训练policy的方法引入智能体任务；有真实booking场景
LLM Agent with Q	2409	常规；收集偏好数据	不训练	正负样本+step-level DPO训练	一轮Q-value model	将MCTS收集偏好数据训练PRM的方法引入智能体任务	由于没训练policy model，MCTS是upper bound
ALPHALLM-CPL	2410	vanilla	正负样本，使用课程学习DPO训练	无	一轮策略迭代	引入课程学习思路去挑选MCTS样本，提高对MCTS数据集的利用效率	解决动机的方法并不直接，挑样本放到哪都能讲；挑样本的metrics有点拍脑袋

可关注的点

• 趋势是越来越关注PRM；但用MSE拟合需要估计optimal Q-value，使用Preference-learning的方法不存在这个问题，但样本利用率很低且没有实验结果支撑其优越性（LLM Agent with Q的AAAI审稿人问了）；还有没有更好的适用MCTS收集到的数据的PRM训练方法？
• MCTS收集到的数据哪些该训policy model，哪些该训外部Q model？ 我理解前者要是通用的推理能力，后者要场景特定的专用能力，如何从数据层面把这两者区分开？ 这样就可以面向多个agent场景收集数据，彼此之间有迁移作用而不是相互影响。
• MCTS还有哪些高级用法可以被LLM场景借鉴？参考awesomeMCTS；比如由于大模型采样很贵，且动作空间巨大，如何进一步提高mcts探索效率？比如生成的时候用conditional方法
• AgentLite给WebShop和HotPotQA场景做了PlanReAct，借鉴CPL: Critical Planning Step Learning Boosts LLM Generalization in Reasoning Tasks，但生成固定的静态plan一般会起反作用。我们是不是可以根据Feedback做一个动态的plan？（具体怎么做还没想好）;Plan是不是更多的是通用的规划能力，可以在任务之间迁移？

TODO list ⏳✅

• ⏳ MCTS的Expansion时，生成动作使用conditional