Everything of Thoughts: Defying the Law of Penrose Triangle for Thought Generation (2024)

Abstract: This paper introduce a novel thought prompting approach called ”Everything of Thoughts” (XoT) for Large Language Models (LLMs) to defy the law of ”Penrose triangle” of existing thought paradigms, to achieve three key perspectives in thought generation simultaneously: performance, efficiency, and flexibility. XoT leverages pretrained reinforcement learning and Monte Carlo Tree Search (MCTS) to incorporate external domain knowledge and planning capability into thoughts, thereby enhancing LLMs’ decision-making capabilities. Through the MCTS-LLM collaborative thought revision framework, XoT autonomously produces high-quality comprehensive cognitive mappings with minimal LLM interactions. Additionally, XoT empowers LLMs to utilize flexible cognitive mappings for solving problems with multiple solutions.We evaluate XoT on several challenging problem-solving tasks, including Game of 24, 8-Puzzle, and Pocket Cube. Our results demonstrate that XoT significantly outperforms existing approaches in various dimensions, showcasing its remarkable proficiency in addressing complex problems across diverse domains. The data and code are available at https://github.com/microsoft/Everything-of-Thoughts-XoT.

## introduction recent advancements in large language models (llms) have greatly advanced problem solving in diverse domains such as mathematical reasoning @xcite , knowledge reasoning @xcite , root cause analysis @xcite and causal inference @xcite , etc.. this progress can be largely attributed to the technique of decomposing intricate problems into smaller language sequences referred to as "thoughts". through a step-by-step inference process involving the use of prompts, each thought functions as an intermediate stage, contributing to the simplification of tackling complex problems to fulfill the problem's ultimate objective. effective design of thought toward complex problem-solving, whether for humans or llms, should prioritize three crucial aspects, namely: there exist several thought paradigms, such as chain-of-thought (cot) @xcite , treeof-thought (tot) @xcite , and graph-of-thought (got) @xcite , etc.. however, these paradigms each have their limitations and cannot simultaneously achieve all the three desired attributes, as illustrated in we propose a novel solution called "everything of thoughts" (xot) to address the limitations of conventional thought frameworks, enhancing essential attributes of thought generation, including performance, efficiency, and flexibility for llm inference. xot leverages reinforcement learning (rl) @xcite and mcts @xcite , in conjunction with lightweight policy and value networks, to pretrain on specific tasks for thought searching and generalize to new problems. this pretraining effectively integrates external domain knowledge and planning capability into the "thoughts" provided to llms, expanding their problem-solving capabilities, and thereby significantly improving performance. once trained, xot efficiently performs thought searching using mcts with cost-effective policy and value networks for exploration and autonomously generates complete cognitive mappings and inject external knowledge to llms. it then employs a mcts-llm collaborative thought revision process to further improve the thought quality while minimizing llm interactions, as will be illustrated in sec. 3.4 and fig. 3 . this eliminates the need for llms to explore and evaluate thoughts themselves, as required by tot and got, enhancing xot's efficiency. furthermore, mcts demonstrates remarkable flexibility as it can explore various thought topologies akin to those employed in human mind mapping processes @xcite . this enables diverse and creative thinking for llms, making it particularly valuable when dealing with complex thought structures or tasks featuring multiple potential solutions. by concurrently achieving superior performance, efficiency, and flexibility, xot challenges the constraints posed by the "penrose triangle " law, significantly surpassing the capabilities of other thought generation paradigms. we evaluate xot across three challenging problem-solving tasks, namely game of 24, 8-puzzle, and pocket cube. our experimental results consistently show xot's superior performance, and its capacity to provide multiple solutions to problems efficiently with just a few llm calls. these establish xot as an effective thought generation approach, paving the way for new avenues in llms' problem-solving capabilities. ## xot: everything of thoughts xot serves as an llm-mcts collaborative framework designed to enhance the thought generation process, thereby assisting llms in resolving complex problems. it leverages mcts for proficient and efficient thought exploration while harnessing the capabilities of llms to refine and amend the thoughts derived from mcts. this synergistic interaction creates a mutually beneficial arrangement, ultimately enabling the successful resolution of intricate problems characterized by high levels of performance, efficiency, and flexibility. ## computational training costs of mcts the number of training and testing policy/value model calls for xot are listed in ## case study in multi-solution scenarios in fig. 4 , we provide examples of thought structures generated by xot for all three tasks in the multi-solution scenario. owing to the multiple solutions required, the generated thoughts intertwine during intermediate steps and converge towards the final goal state. this results in a naturally woven thought structure resembling a graph, showcasing the remarkable flexibility achieved by xot. upon closer examination of each example, in the case of the game of 24, there are multiple solutions to reach the goal of 24. xot effectively predicts these trajectories, indicating its ability to grasp complex thought structures. in the 8-puzzle example, we observe instances of reflection in the thought structure, with back-and-forth recurrent state transitions. this demonstrates xot's capacity for self-reflection, a crucial attribute for llms, as discussed in @xcite . in the case of the pocket cube, xot identifies four distinct pathways to reach the goal state, leading to successful problem-solving across multiple solutions. ## related work decision making & planning with llms. the utilization of llms for decision-making and planning has become a prominent area of research. similar to human problem-solving, the process involves breaking down complex problems into sub-tasks. various frameworks, such as cot @xcite , tot @xcite , and got @xcite , have been designed to facilitate problem decomposition in different structural forms, leading to enhanced solutions derived from llms. extensions of these frameworks have also been explored across different domains and modalities @xcite @xcite @xcite . our approach xot distinguishes itself from the aforementioned work by concurrently achieving superior performance, efficiency, and flexibility, embodying the concept of comprehensive thought generation. augmenting llms with mcts. mcts is integrated with llms to enhance both training and inference processes. hao et al., propose "reasoning via planning", utilizing llms as a world model and reasoning agent, while combining mcts as a strategic explorer to enhance llms' reasoning and planning abilities (hao et al., 2023). liu et al., incorporate mcts and ppo @xcite to devise a value-guided decoding algorithm, thereby enhancing the preferability of generated text by llms @xcite . additionally, feng et al., employ mcts to augment llms' decoding and, consequently, their reasoning and planning capabilities @xcite . these studies underscore the significant potential of integrating mcts with llms to improve their overall capabilities. ## conclusion the xot framework presented in this paper signifies a significant progression in thought generation for llms aimed at solving complex tasks. it challenges the constraints of the "penrose triangle " by concurrently achieving performance, efficiency, and flexibility, a feat unattainable by existing prompting paradigms. this is achieved through the integration of mcts with pretrained low-cost policy and value networks, by injecting domain knowledge and planning capability into llms, offloading thought searching, and facilitating unconstrained free-style thought exploration. the collaborative thought revision framework involving mcts and llm further enhances the quality of thought generation. experimental evaluations conducted across three real-world problems, namely the game of 24, 8-puzzle, and pocket cube, show that our xot framework significantly outperforms existing prompting paradigms, particularly in scenarios involving multi-solution problems.