Tree of Problems: Improving structured problem solving with compositionality (2024)

Abstract: Large Language Models (LLMs) have demonstrated remarkable performance across multipletasks through in-context learning. For complex reasoning tasks that require step-by-step thinking, Chain-of-Thought (CoT) prompting has given impressive results, especially when combined with self-consistency. Nonetheless, some tasks remain particularly difficult for LLMs to solve. Tree of Thoughts (ToT) and Graph of Thoughts (GoT) emerged as alternatives, dividing the complex problem into paths of subproblems. In this paper, we propose Tree of Problems (ToP), a simpler version of ToT, which we hypothesise can work better for complex tasks that can be divided into identical subtasks. Our empirical results show that our approach outperforms ToT and GoT, and in addition per forms better than CoT on complex reasoning tasks. All code for this paper will be made available.

## introduction in-context learning (icl) @xcite is the ability of large language models (llms) to perform a task with the help of a few demonstrations within their context. it is widely used to evaluate llms on various tasks. these models, whose number of parameters and training corpus size has increased massively over recent years, keep pushing the state of the art on a wide range of natural language tasks @xcite @xcite . however, they still struggle to perform complex tasks, notably those requiring multiple reasoning steps @xcite . recently, chain-of-thought (cot) prompting @xcite has greatly helped to enhance reasoning abilities of llms by helping them to mimic step-by-step reasoning. however, cot implicitly requires the model to generalize beyond the cases seen in its prompt, which often leads to poor out-of-domain performance @xcite . applying cot with self-consistency @xcite drives the model to explore multiple reasoning paths and to choose the most consistent answer, usually yielding better performance, but helping only marginally with out-of-distribution generalization. moreover, solving complex problems involves understanding their underlying structure; this can help to avoid lengthy cots that are prone to reasoning errors. in this paper, we propose to tackle complex problem-solving and out-of-distribution generalization by dividing complex tasks into a series of simpler sub-tasks. we draw inspiration from techniques such as dynamic programming and divide and conquer in order to efficiently guide llms through complex problem solving. such problems have previously been tackled using approaches adding structure to cot, such as tree of thoughts (tot) @xcite and graph of thoughts (got) @xcite , which consist in sampling diverse reasoning paths (where path states represent subproblems) and finding the optimal path. we argue that for a subset of complex reasoning problems, where an instance can be decomposed into multiple analogous subinstances, tot and got are overly complex, and the tasks can be better solved by a simpler approach. this simpler approach, which we name tree of problems (top) consists in building a tree structure, where each node represents a problem instance similar to the main instance. the deepest instances, which correspond to atomic problems, are solved first with cot prompting and the internal nodes are recursively solved by merging their children's solutions. figure 1 illustrates our method on the tasks of last letter concatenation and navigate from the big-bench hard benchmark @xcite . we conduct a comprehensive evaluation on several llms, including gpt-3.5, on multiple hard figure 1 : overview of the tree of problems (top) framework for two tasks. on the left (a canonical task consisting of independent subproblems organised in a tree structure), the task is to concatenate the last letters of a list of names, accomplished by breaking the list in two, finding their solutions, and recombining them. on the right (an extension of the canonical structure to handle sequential tasks), the task is to determine the final position of an object after a series of steps. we first find its position after half of the steps, and then determine the final position by tracing the object through the remaining steps. see section 3 for a description of top. ## related work cot prompting was proposed to enhance reasoning by incorporating step-by-step logic into fewshot prompt demonstrations @xcite . it showed significant improvement over standard input-output (io) prompting across various mathematical and symbolic reasoning benchmarks. building on this, @xcite and @xcite inter alia demonstrated that zeroshot cot could be achieved by using reasoninginducing words at the end of the zero-shot prompt. other works showed that wisely designing the cot demonstrations could yield further improvements @xcite . cot self-consistency (cot-sc; wang et al. 2023b) improved on cot by sampling diverse reasoning steps and selecting the most consistent answer after marginalizing over the reasoning paths. our research also builds on the body of work addressing problem-solving through compositionality, which involves teaching llms to tackle complex problems by breaking them down into a series of subproblems and recursively solving them to derive the final answer, e.g. @xcite , decomposed @xcite and successive @xcite prompting. while these works align with our approach through their use of problem decomposition, we focus on breaking a main task into multiple similar subtasks, solvable using the same prompt. moreover, our approach uses a tree structure that allows for greater flexibility and coverage in problem solving. the most closely related approaches are tree of thoughts (tot) @xcite and graph of thoughts (got) @xcite . tot builds on the idea of sampling diverse reasoning paths but redefines problem solving as a search over a thought space, where states represent partial solutions. got extends tot by including thought aggregation, which is analogous to our merge operation and by allowing refining @xcite . while a "thought" represents a general reasoning step in their approach, we focus on reasoning through subproblems. we do not perform a search over a tree of thoughts, nor do we score or refine (improve) our tree nodes. instead, each node in the tree of problems is directly relevant to solving the problem, and their bottom-up recombination produces the final solution. top is therefore a simpler and more cost-effective alternative to tot and got. ## our method solving a complex problem often requires reasoning, partly explaining the success of cot prompting for such problems. reasoning involves understanding a problem's structure and design. this aspect is frequently overlooked in cot because incorporating it can be challenging. our method addresses this by constructing a tree of simpler, closely related subproblems to solve a more complex problem. we hypothesize that the capability of an llm to solve simple instances can be extended to more complex ones. the ability of an llm to solve a complex instance therefore lies in how accurately it can solve simpler ones and then combine their answers. the main class of problems we aim to tackle are complex problems that are divisible into independent subproblems resembling the initial one (we refer to these as canonical tasks). however, we also experiment with relaxing the independency constraint in order to tackle sequential tasks, which require finding the final state of a system after a series of independent processing steps (see the right of figure 1 ). our method relies on the following components: in addition to canonical tasks with a classic tree structure (see the left of figure 1 ), top can also be used for sequential tasks, where a given subproblem needs the result of a previous subproblem as an input (see the right of figure 1 ). our standard top paradigm described above can be used to solve such problems by setting the breadth to 1. this has the effect that the problem is decomposed into a sequence of n subproblems organised as hierarchy of depth n. when solving the (k + 1)-th subproblem, the solver will have access to its child subproblem's result, i.e. the result of subproblem k, thereby accounting for the sequentiality of the decomposition. the llm is no longer required to merge subproblems' solutions; it is directly fed with a new problem formulation automatically computed using the corresponding child's solution. the final solution is obtained by solving the last subproblem, and so the main problem instance (root node) does not influence the inference cost. for both tasks, all problems at the same level of the tree are solved in parallel to promote efficiency. we further detail the method with more examples in appendix a. ## experiments we first compare top to tot and got to test our hypothesis that our simpler approach is more adapted to canonical tasks. we do this using the got tasks proposed by @xcite . we then show that top is more effective in comparison to io (direct input-output) and cot prompting across a wider ranger of canonical tasks, namely last letter concatenation @xcite and 5 big-bench hard @xcite tasks fitting the description. finally, we test top on sequential tasks.