of TOT Thought Tree

当蠢才享一篇普林斯顿大学的一篇文章，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:​