今天分享一篇普林斯顿大学的一篇文章，Tree of Thoughts: Deliberate Problem Solving with Large Language Models[1]：思维之树:用大型语言模型解决复杂问题。
这篇工作还是非常有借鉴意义的，OpenAI的Andrej Karpathy（前Tesla AI高级总监、自动驾驶Autopilot负责人）在state of gpt[2]中也分享了这篇文章，其可以通过搜索多条解决路径，利用dfs以及bfs等算法，像人类一样利用回溯、剪枝等策略来思考和解决问题，可以让GPT-4解决一些更复杂的推理问题。
一、概述
Title：Tree of Thoughts: Deliberate Problem Solving with Large Language Models
论文地址：
论文代码：
非官方代码：
1 Motivation
2.1 Thought decomposition【thought分解】
目的：如何将中间过程分解成一个思维步骤【不同任务的thought steps怎么设计比较好】
方法：不同的任务，中间的思考过程thought可能不同，例如可能是几个words（Crosswords填字谜游戏），可能是一个equation（24点游戏），也可能是一个paragraph（创意文本生成），设计thoughts可以有几个原则：
2.2 Thought generator【thought生成】
背景：不同的任务Thought生成的原则也不太一样，可以根据任务的特点制定thought生成的原则。
【Mini Crosswords 填字游戏】是什么？：Mini Crosswords是一种简化版的填字游戏，适合在有限的空间和时间内进行。与传统的填字游戏不同，Mini Crosswords使用较小的网格，通常为5x5或6x6，且只包含较少的单词。每个单词都有一个提示，玩家需要根据提示填写正确的单词。
【Mini Crosswords 填字游戏】thought生成方法：直接根据当前节点已经填好的单词（限制条件），利用prompt方法生成5次，产生下一个词可能的5种填写方法。
2.3 State evaluator【状态评估】
定义：给定不同的当前state状态，state evalutor用于评估那个方法最有接近解决当前问题。通常是利用heuristis方法来解决，像deepBlue是用编程的方法来解决，AlphaGo是用学习的方法来解决，本文直接是用LM去评估和思考当前state解决问题的前景。同样的，针对不同的任务也有不同的评估方法。这里主要提出两种策略：
【24点游戏】评估方法：直接利用prompt LM去评估每个thoughts为sure、maybe、impossible几个选项
【Mini Crosswords 填字游戏】评估方法：直接利用prompt评估每个candidates的confidence（sure、impossible、maybe）
【创意文本生成】评估方法：直接利用LM投票从多个state中选择最好的一个，例如使用以下prompt：“analyze choices below，then conclude which is most promising for the instruction”
其他：对于每一种策略，都可以利用LM prompt多次集成多次的value分数或者vote投票提升其鲁棒性。
2.4 Search algorithm【搜索算法】
说明：对于树的结构，有很多中搜索算法，本文探索了两种简单的搜索算法BFS和DFS。
3 Conclusion
4 Limitation
二、详细内容
1三个实验的定义
2 搜索算法策略
特点：利用BFS，可以像人类一样，一直探索比较好的b个（宽度）实现方法。利用DFS方法，可以方便的进行剪枝，回溯，像人一样，当前路走不通，我退回上一个不走重新选择。相对于之前的COT等从左到右的思想策略，理论上感觉确实会有着比较大的提升空间。
3 Game of 24实验结果分析
4 Creative Writing results和Mini Crosswords results结果分析
自动评估（连贯性）：ToT (7.56) > CoT (6.93) > IO (6.19)
人工评估（GSB）：ToT vs COT G：S：B = (41：38 ：21)
iterative-refine（旧的thought -> refine -> 新的thought）：迭代优化还能继续提升，ToT (7.56 -> 7.91) ，IO (6.19 -> 7.17) ，这个提升也挺大的，可以作为一个新的方法
Letter（字母级别准确率）：ToT (78) > CoT (40.6) > IO (38.8)
Word（字级别准确率）：ToT (60） > CoT (15.6) > IO (14)
Game（游戏级别解决率）：ToT (20) > CoT (1) > IO (0)
消融实验：（1）+best state：利用更好的state评估器，可能得到更大的提升，Game级别解决率从20%->35%，说明本文提到的简单的启发式的评估算法还有比较大的空间。（2）剪枝：去掉剪枝，只能解决1个问题，另外3个都是通过启发式的剪枝找到的，说明这种方法对于解决问题是至关重要的。（3）回溯：去掉回溯算法后，效果表现比较差，说明有延续性的这种寻找答案的方法也是非常重要的。
5Related Work
三、总结
四、References
[1] Yao, Shunyu, et al. "Tree of thoughts: Deliberate problem solving with large language models." arXiv preprint arXiv:2305.10601 (2023).
[2] state of gpt: