HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Authors: Runquan Gui
Zhihai Wang
Jie Wang
Chi Ma
Huiling Zhen
Mingxuan Yuan
Jianye HAO
Defu Lian
Enhong Chen
Feng Wu
Venue: ICML 2025 poster (2025)
Keywords: LLM Reasoning
Planning
Hierarchical Thinking
Primary area: deep_learning->large_language_models

Abstract: Recent advancements have significantly enhanced the performance of large language models (LLMs) in tackling complex reasoning tasks, achieving notable success in domains like mathematical and logical reasoning.
However, these methods encounter challenges with complex planning tasks, primarily due to extended reasoning steps, diverse constraints, and the challenge of handling multiple distinct sub-tasks.
To address these challenges, we propose HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree-structured planning outlines for effective planning.
The hypertree structure enables LLMs to engage in hierarchical thinking by flexibly employing the divide-and-conquer strategy, effectively breaking down intricate reasoning steps, accommodating diverse constraints, and managing multiple distinct sub-tasks in a well-organized manner.
We further introduce an autonomous planning framework that completes the planning process by iteratively refining and expanding the hypertree-structured planning outlines.
Experiments demonstrate the effectiveness of HTP, achieving state-of-the-art accuracy on the TravelPlanner benchmark with Gemini-1.5-Pro, resulting in a 3.6$\times$ performance improvement over o1-preview.

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Runquan Gui 12
Zhihai Wang"
Jie Wang'
Ma' Huiling Zhen Mingxuan Yuan Jianye Hao
Defu Lian
Enhong Chen Feng Wu
Abstract
Query: Plan a 5-day top from SJ to and with budger of $900. hotels must be pet-friondly and offer entire rooms. I prefer to travel by plane during the trip.
Recent advancements have significantly enhanced the performance of large language models (LLMs) in tackling complex reasoning tasks, achieving no- table success in domains like mathematical and logical reasoning. However, these methods en- counter challenges with complex planning tasks, primarily due to extended reasoning steps, diverse constraints, and the challenge of handling multi- ple distinct sub-tasks. To address these challenges, we propose HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree- structured planning outlines for effective planning. The hypertree structure enables LLMs to engage in hierarchical thinking by flexibly employing the divide-and-come annnquur strategy, effectively breaking down intricate reasoning steps, accommodating diverse constraints, and managing multiple dis- tinct sub-tasks in a well-organized manner. We further introduce autonomous planning frame- work that completes the planning process by it- eratively refining and expanding the hypertree- structured planning outlines. Experiments demon- strate the effectiveness HTP, achieving state-of- the-art accuracy on the TravelPlanner benchmark with Gemini- P.r-Pr,, resulting in a 3.6x perfor- mance improvement over 01 or-preview.
pet-friendly
entire room
Hotel Name:...
cost.
D
hutel
botel SD
Other sub-Lasis
PLAN
availabiiity prefer ence
transport
sell-driving
of transport:
lower cost.
flight
Hlerarchical Reasaning Constrainl Separation Sub-task Sohring Plan Generation
Figure 1. An example of hierarchical thinking, demonstrating its ability to decompose complex reasoning chains into manageable components, effectively handle diverse constraints, and systemati- cally manage multiple distinct sub-tasks.
2022; Shum et al., 2023). Unlike mathematical or logical reasoning tasks, which have clear, definitive answers (like numbers or specific nouns), planning tasks require a feasible plan consisting of multiple interdependent components. For example, travel plan involves selecting hotels, booking flights, choosing restaurants, and deciding on attractions, each of which can be further broken down with various con- straints. Hotel selection, for instance, may involve factors like house rules, room types, budget limitations, and more. Therefore, completing complex planning tasks typically requires reasoning over extended steps, decision -maiing under diverse complex constraints, and generating com- prehensive and feasible solutions, which presents unique challenges for existing LLMs (Ju et al., 2024; Xie al., 2024; Huang al., 2023; Valmeekam al., 2024b).
1. Introduction
Planning has long been recognized as a core skill for intelli- gent agents and a key benchmark for evaluating the cognitive capabilities of large language models (LLMs) (Zhu et al.,
A series of works have been proposed to enhance the plan- ning capabilities of LLMs. In-context learning approaches, by providing curated demonstration examples before in- ference, enable models to improve their planning ability through analogical reasoning (Sprague et al., 2024; Chen Li, 2024). An innovative breakthrough is Chain-of- (CoTT) prompting (Wei et al., 2022; Kojima et al., 2022), which extends the reasoning process from a simple input- output format into multi-step chain of reasoning, enabling models to think step-by-step. Building on this, Tree-of- Thought (ToT) prompting (Yao al., 2024) takes it a step
'MoE Key Laboratory of Brain-inspired Intelligent Perception and Cognition, University Science and Technology of China <rqgui@ @ mai. ustt.edu.cc'>> 'Noah's 's Ark Lab, Huawei Technolo- gies 'College of Intelligence and Computing. Tianjin University State Key Laboratory of Cognitive Intelligence & University of Science and Technology of China. Correspondence to: Jie Wang <jiewangx edt..ed
Proceedings of the 4dnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

HyperTree Planning:
Enhancing LLM Reasoning via Hierarchical Thinking
further by transforming the linear reasoning process into branching structure, allowing LLMS reason along multi- ple paths and systematically explore the search space. Re- cent planning methods have increasingly explored innova- tions in agent systems, where specialized agents collaborate through structured processes to tackle complex planning tasks, further extending the scope and effectiveness of plan- ning solutions ( (Yuan et al., 2024; Zhang et al., 2024a).
hypertree structure. Next, we introduce the top-down hyper- tree construction algorithm, which systematically applies these strategies to build the hyperfree-strructreed planning outline. Following this, we refine and expand the planning outline iteratively, ultimately generating the final plan. Ex- perimental results demonstrate that HTP, leveraging GPT-4 or Gemini 1.5-Prr as its backbone, achieves significant per- formance improvements across multiple complex planning benchmarks, outperforming state-of-the-ar agent methods, planning strategies, and closed-source models. The core contributions are summarized as follows:
Despite these advances, existing planning methods exhibit several limitations. First, existing reasoning paradigms pri- marily focus on mathematical or logical reasoning tasks, making them ill-suited for planning problems and their unique challenges. Second, the performance of LLMs re- lying on in-context learning is highly dependent on the quality of the provided examples, requiring significant hu- man expertise and constraining generalization ability (Dong et al., 2022; Zhao et al., 2021; Lu et al., 2021). Although various methods have been proposed to address these lim- itations (Liu et al., 2021; Tanwar et al., 2023; Qin et al., 2023), the discrepancy between the example and the ac- tual query remains a fundamentally unresolved challenge. Third, current autonomous agent methods consistently rely on desinnde interventions, such requiring the man- ual creation of distinct personas and task-specific descrip- tions for each agent, which hinders generalization across diverse tasks (Hong et al., 2023; Liang et al., 2023).
We propose HTP, a novel hypertree reasoning paradigm, which, to the best of our knowledge, is the first to use hypertree structure model the reasoning process, empowering LLMs to perform hierarchical thinking.
HyperTree Reasoning Paradigm:
Novel Planning Framework: We present a fully autonomous planning framework that leverages task- specific planning outlines to self-guide the planning process, generalizing effectively to diverse tasks with- out relying on manually crafted examples.
Superior Performance: HTP significantly outper- forms existing methods on complex planning bench- marks, achieving 36.1% accuracy on TraveIPlanner with Gemini- 1.5-Pro, substantially outperforming ol- preview (10.0%).
To address these challenges, this paper proposes HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree-strructure planning outlines for effective plan- ning! ! We observe that humans naturally approach planning tasks by flexibly and hicrarchically employing the divide- and-conquer strategy. They continuously break down task into smaller, more manageable subtasks, address each com- ponent individually, and synthesize the results to create the final plan. This cognitive process, known as hierarchical thinking, is illustrated in Figure 1. Inspired by this, HTP extends the ToT framework by incorporating the hypertree structure proposed in (Lample et al., 2022). In this enhanced framework, each edge connects a parent node to a set of child nodes, providing an intuitive structural foundation for the divide-and-conque mechanism. By flexibly applying this strategy across multiple layers, our planning outline effectively implements hierarchical thinking tailored to the original query. Furthermore, we design an autonomous planning framework that seamlessly integrates these plan- ning outlines into self-guided planning and plan generation processes, ultimately producing high-quality plans.
2. Related Work
Reasoning Paradigms ture, the prompting paradigm has garnered significant atten- tion and emerged as a promising approach to unlocking the reasoning potential of LLMs (Zhou et al., 2024; Edelman et al., 2024; Jeon et al., 2024; Lin & Lee, 2024). Few-shot prompting, in particular, provides curated demonstration examples before inference, enabling LLMS to perform rea- soning tasks by leveraging analogical examples (Wei et al., 2022; Sprague et al., 2024; Chen & Li, 2024). However, their reasoning performance heavily depends on the quality of the provided examples, requiring substantial human ex- pertise and limiting their generalization ability (Dong et al., 2022; Zhao et al., 2021; Lu et al., 2021). In response to this limitation, HIAR-ICL (Wu et al., 2024) proposes replacing demonstration examples with reasoning patterns formed by permutations of five fixed actions. However, the guidance from fixed elements is quite limited, and due to the chain- like structure of the patterns, they cannot fully support the hierarchical thinking needed for planning.
Owing to its parameter-free na-
Specifically, we begin by modeling step-by-step reasoning, multi-path inference, and the aedide--nd-conquee within the
Starting from -houugh (CoT) (Wei et al., 2022), a series of techniques have been developed to improve the reasoning capabilities of LLMs by introducing novel rea- soning paradigms. Zero-shot-Col (Kojima et al., 2022)
'A hypergraph is a graph where an edge leads to a set of nodes. A hypertree is a hypergraph without cycles. More formal definitions can be found in Scction 3.1.
2

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
enables reasoning step generation without the need for exam- ples. Departing from the linear, left-to-right chain-like struc- ture, a significant body of work, exemplified by ToT (Yao et al.. 2024), has extended reasoning paradigms into tree- based frameworks to broaden potential search spaces, subse- quently employing diverse tree search algorithms to improve reasoning precision (Hao et al., 2023; Wang et al., 2024c; Qi et al., 2024; Zhang et al., 2024b; Feng et al., 2023: Putta et al., 2024). However, these tree search-based methods focus on optimizing the CoT path through trials, lacking fun- damental innovations in the reasoning process itself (Zhang et al., 2024c). Plan-and-Solee (Wang et al., 2023a) requires LLMs to devise a plan that breaks the task into smaller sub- tasks, and then carry out the subtasks according to the plan. Similarly, Ekeleton-of-Thougeee (Ning et al., 2024) first gen- erates a skeleton answer outline, and then completes content in parallel to reduce generation latency. These methods demonstrate some sivide-and-conquee capability, but they lack technical innovation in constructing the outline and are limited to a single level of task decomposition due to insufficient support from reasoning structures.
3.1. Problem Statement
Given planning query q and a pre-trained LLM va, the problem-solving process can typically be divided into two phases: planning and plan generation. The planning phase involves generating intermediate reasoning results, formal- ized as C = Ta ($()), where & denotes the predefined instructions. Building on this, the plan generation phase re- fines C' into the final solution, expressed as P = (C)).
In the planning phase, a common approach is to frame it as multi-step thinking process. Specifically, we guide the large model to generate sequence of reasoning steps starting from q. which results in C that completes the phase. In detail, suppose there are N intermediate reasoning steps Su....N = [so. $1, $2, sN], where 50 = q and aN = C. At each time step n, the model receives a state Sn-1, which consists of the original input q and the preceding reasoning steps ($1, 82, 122,--..nn11 8n-1), and generates the cur- rent reasoning step 8n = To (T(((Sn))) The sequence $1...N = [$1, .... sN] forms complete chain-like struc- ture of step-by-step reasoning (Wei et al., 2022).
Building on the ciain-like structure, ToT (Yao et al., 2024) extends a tree structure to explore different choices and their outcomes. Given the current state Sn-1, 1. the LLM generates multiple feasible steps ( ...., .8 ((m)) = To (((Sn))),, each of which remains independent in subsequent expan- sions. This branching allows the model to explore the search space and results in a tree T, from which a single leaf is ultimately selected as the result C.
Planning Agents Autonomous agents are systems de- signed to execute diverse tasks through self-directed ac- tions (Wang et al., 2024b), with planning serving as a funda- mental function (Valmeekam et al., 2024a; Xie et al., 2024; Zheng et al., 2024; Zhang et al., 2024a). Methods such as ReAct (Yao et al., 2022) and RAP (Hao et al., 2023) for- malize planning as Markov decision process, allowing agents to dynamically reason and act by evaluating interme- diate states and iteratively making decisions. Recent studies have leveraged multi-agent systems to improve the planning capabilities in specific tasks (Chen et al., 2023a;c; Zhang et al., 2024a). However, these approaches often rely heavily on human-designed interventions, including the creation of tailored personas and task-specific descriptions for each agent. EvoAgeet (Yuan et al., 2024) utilizes evolutionary algorithms to automate agent role generation, but its abil- ity to address diverse constraints remains limited. Another promising direction entails integrating LLMs with external planning tools (Dagan et al., 2023; Guan et al., 2023; Yang et al., 2023; Ju et al., 2024; Lee et al., 2025). While these hybrid approaches can achieve high accuracy, the construc- tion of feasible solvers evaluators remains challenging, with high engineering overhead, design costs, and a lack of generalization across different datasets.
3.2. HyperTree Definition
Formally, let G represent a set of nodes, and R a set of rules. A hypertree library is defined where G serves the root node. Each rule E R is function r + C, where g E G is referred to as the start node, and e C G represents the corresponding set of child nodes. Here, P(G) denotes the power set of G. To ensure acyclicity, no sequence go: I1......! 9t = 90 (L > 0) is allowed, where 9-+1 is a child of g; for all 0 < f. The set of divisible nodes is defined as:
tuple I, (G, q, R),
D = {d E G 3r E R such that d is the start node of r).
Using the hypertree library I,, a generating hypertree H defined as a hypertree satisfying the following properties:
1. Every leaf node of H belongs to G.
2. Every non-leaf node of H belongs to D.
3. For any non-leaf node g with a branch of child nodes there exists rule E R such that r g + c.
3. Preliminary
In this section, we first illustrate the problem statement in Section 3.1, and subsequently define the concepts related to hypertrees in Section 3.2, drawing from the definitions of hypertree proof search (Lample et al., 2022).
A special case of H. referred to as a hyperchain C, is a hypertree with no branching. In a hyperchain, each non-leaf node 9: E C generates its child nodes using the same rule r. Examples of I, can be found Appendix E.I.
3

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Tree Planning
Hyper'Tree Tree Planning (HTP)
Algorithm Top-down HyperTree Construction Algorithm
Input: rules R. query q. LLM TT. reasoning depth K, expansion width W
Rullss
LLM
Convert divisible set: D +- Convert(R)
Initialize hypertree: H 4- for d 4 1 to K do
52
Extract hyperchains: (C1,...,, Cm] Map(H) if m W then Filter hyperchains: {CI,..., Cw} + no (H) end
for i 1 min(W, m) do
AAD
Extract divisible nodes: 91.... In, t xo (C, D) Select node: g < Te(g, H, 91, 9n,)) ))
Figure 2. An overview of HyperTree Planning (HTP). Compared to previous tree planning methods such as ToT (Yao et al., 2024) and RAP (Hao et al., 2023), HTP introduces structural innovations that enable each edge to connect multiple child nodes, making it suitable for a divide-and-aa and-conquer strategy.
Retrieve rules: T1...., TP t Tol R. g.)
for p < 1 to P do
Expand nodes: { To(g; Ci, g rp)) H + AttachNodes (6,)). H,
p - -+1
4. Methodology
end + i+1
Overview of HTP In this section, we introduce HTP in detail and illustrate the entire process in Figure 3. We begin by modeling the reasoning path as a hypertree and, based on this framework, introduce top-down hypertree construction algorithm. This algorithm generates hypertree--trructured planning outline O tailored to the specific query q. Guided by O the self-guided planning process systematically solves the corresponding sub-tasks, completes the planning pro- cess, and derives C. Finally, the plan generation process integrates the results into a comprehensive final plan P.
end
d t d+1 end Select the optimal hyperchain: C* <- no (H) return Planning Outline O + C
the structure inherently reflects a divide-and-conquer strat- egy. Additionally, due to the inherent flexibility of the hypertree structure, any divisible child node 8n (i.) gener-
ated from Sn-1 can be further expanded through succes- sive divide-and-conquer steps. While the chain structure equips LLMs with step-by-step reasoning and the tree struc- ture enables exploration across multiple paths, the hyper- tree structure uniquely introduces a capability we term as hierarchical thinking multi-level approach that facilitates deeper and more organized reason- ing. Through hierarchical thinking, each path ultimately evolves to address distinct subtasks, with the final outcomes {s (1)) s ......yy spective subtasks.
4.1. From Tree Planning to HyperTree Planning
Building on the concept of hypertrees, HTP introduces a hypertree-structured reasoning paradigm. For a real-world planning dataset, 1ct R denote a fixed set of rules derived from the descriptions of the dataset, while G' represents reasoming steps expressed in natural language. As shown in Figure 2, given the current state 1,, suppose divisible leaf node - is selected. By definition of a hypertree, the next reasoning steps following Sn-1 can be represented as:
(4) representing the solutions to the re-
s,
(1.1) ....,,
1 (1.k1)) }, (8/
(m.1)
(m, }}
4.2. Top-down Hypertree Construction Algorithm
where represents the number of branches, and k; denotes the number of child nodes within the i-th branch. Similar to tree planning methods, since the branches are independent of one another, we ultimately select hyperchain C from H, which contains no branches. Once the hyperchain C is fully expanded, the set of all leaf nodes collectively serves as the outcome C of the planning phase, in contrast previous methods that select only single leaf node.
The core of HTP is to generate a hypertree-structured plan- ning outline based on the given rules R. To the best of our knowledge, no existing hypertree construction algorithm has been designed for reasoning tasks. In this context, we pro- pose a top-down hypertree construction algorithm that starts from the root node and progressively builds a hypertree. Specifically, the algorithm unfolds in four stages: selection, expansion, construction, and decision.
Similar to tree planning, we continue to use edges to rep- resent the connections underlying sequential reasoning in the hypertree structure. Since all child nodes within the same branch share the same edge with the parent node,
(1) Selection. Suppose the current hypertree is H. which can naturally be mapped to a series of hyperchains (C)...., Cm based on its distinct branches, where m represents the total number of hyperchains. This phase aims to identify
4

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Qe Plan 5-day trip from SJ LA and SD with busget of 5500, The hotels must be pet friendly and offer entir moms. I prefer to trarel plane dustng map.
Self-Guided Planning
Plan G Gemeration
availability
preference
lower cost
Flight Number F3956409
Day
Curmen City: from SJ LA
Transpotation: F3956409
HyperTree Construction
Nlghht
F30GIA00: 5327
Restarrat
F3978451: $547
A Attractonn
av availibillity
pa preference
Knum ledge
Hotel Artist Loft
sell-driving
information
Day
City
Artist Laft: pet-iriendly. entire room, $259...
Cucy Room: pet fhenfeedyyy shaned SI1X... Charman Room. pet Biendly entire room, $566....
T Transportation
Plansing Outline
Planning Outline
Restourants:
Fan
pet-friendly
entire room
lower
Hotel Name: Artist Loft
A Altectioon: ...
Hotel: Artist l.fft
Tilter
hotel LA
Figure 3. Flowchart of HTP, which consists of three parts: (1) HyperTree Construction; (2) Self-Guides Planning; (3) Plan Generation.
the appropriate leaf nodes of H for subsequent expansion, which involves two main steps: first, selecting the optimal hyperchains from H, and then determining the most suitable leaf node within each chosen hyperchain.
branch and added C as part of the expansion for node g.
(3) Construction. The construction process for single hyperchain C involves iteratively performing selection and expansion, starting from the root q. until either all leaf nodes become indivisible or the iteration limit is reached.
To effectively select the optimal hyperchains from H and manage their number, inspired by the tree-structured meth- ods for limiting width, we adopt three strategies: a width- based pruning method, which restricts the total number of branches; a probability-
(4) Decision. Once the hypertree H is fully constructed, the decision-make makinng process takes place. During this phase, LLMs are prompted to identify the optimal hyperchain within H. which will then serve as the final planning outline O for the hypertree construction algorithm.
pruning method, where hy- perchains with low confidence probabilities- geeeerated by are eliminated; and an LLM- guided evaluation method, which leverages the LLM to filter and assess candidate hyperchains.
the LLM during branching are
The algorithm generates a hypertree-strrucured planning outline automatically for any query, requiring no human intervention. With features such as task decomposition, multi-pati exploration, and self-evaluation, adapts seam- lessly to diverse planning frameworks without prerequisites. The entire process is illustrated in Figure 3, and the details of our algorithm are provided in Algorithm 1.
Given a selected hyperchain C, the next step is to identify the most suitable leaf node. Since only divisible nodes can be expanded further, we start by extracting the divisible leaf nodes from C. Determining whether a node is divisible is straightforward, as the starting nodes under the given rules R typically follow a specific format, which is detailed in Appendix E. When selecting a leaf node from the divis- ible leaf nodes, traditional methods like UCT (Kocsis & Szepesvári, 2006), PUCT (Silver al., 2017), and Regu- larized Policy (Grill al., 2020) are not suitable. These methods are designed for scenarios where paths perform the same task, balancing exploration and exploitation. How- ever, in our setting, paths are to address distinct subtasks, making these approaches ineffective. Furthermore, simple heuristics fail to capture the broader context of the entire hyperchain, which critical for making appropriate node selections. Therefore, we turn to LLMs, which can analyze the rules R and the structure of the current hyperchain C to identify the most promising leaf node for expansion.
4.3. Self-guided Planning and Plan Generation
A After executing the top-down hypertree construction algo- rithm, we obtain a planning outline O for the query q. While this outline is structurally clear and comprehensive, it lacks the detailed content required for fully developed plan. This limitation arises from two main factors. First, certain planning tasks like TravelPlanner rely on external knowl- edge-such as a list of tourist attractions-to create a com- plcte plan, and the knowledge base is not included during the hypertree construction process. Second, the leaf nodes of the planning outline generally break the task down into subtasks, but further in-depth reasoning is needed to address these subtasks and generate their corresponding solutions.
(2) Expansion. During the expansion phase, given the se- lected node g. we first retrieve the set S = (r E R g is the start node of r), which includes all the rules where g serves as the starting node. We then sample P' rules TIp...,pp from the set S. For each sampled rule rp. we gen- erate the corresponding child nodes (s(p.1) ..... 5(0+5,))= (g, C, g. g,))), which are collectively treated as a single
To address these gaps, we provide the planning outline O along with any available knowledge base IC, to the LLM Tg. The self-guided process expands and enriches the out- line with detailed content while maintaining its hierarchical structure. Specifically, for non-leaf nodes in O we leverage K to refine them. For leaf nodes in O, we facilitate further growth of the hypertree by iteratively expanding the nodes
5

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Table Main results of different I. and planning strategies across three planning benchmarks. DR, CPR, HCPR, and SR represent the Delivery Rate, Commonsense Pass Rate, Hard Constraint Pass Rate, and Success Rate, respectively, while Blocks., Mys. and Trip. denote the Blocksworld, Mystery Blocksworld and Trip Planning tasks, respectively. The best results are bolded, and the second hest ones are underlined. Our method, HTP consistently achieves the best performance across models and datasets.
TravelPlanner
Blocks.
Mys.
Trip.
MODEL
SETTING
CPR
HCPR
DR
SR
SR
SR
SR
Micro
Macro
Micro
Macro
CoT
100
80.4
18.9
46.9
22.2
4.4
35.5
0.0
15.6
ToT
100
75.8
16.7
44.0
21.1
3.9
37.5
0.67
18.1
LATS
100
78.3
16.7
44.8
21.1
3.9
40.2
1.7
20.6
One-shot
100
76.4
17.2
43.3
20.6
3.9
28.2
0.67
3.7
GPT-4o
HiAR-ICL
100
81.2
20.6
47.4
22.8
6.7
36.5
1.8
12.8
RAP
100
81.0
20.6
50.5
25.6
6.7
41.2
1.8
12.5
EvoAgent
100
81.5
21.1
31.2
18.9
7.2
34.0
0.17
13.4
HTP
100
87.2
37.8
44.3
32.2
20.0
54.7
8.7
36.9
CoT
100
81.4
17.2
44.5
20.5
5,6
26.7
0,0
34.7
ToT
100
79.0
18.9
46.7
21.7
31.0
0.0
LATS
100
78.8
17.8
44.3
21.7
6.1
38.2
2.2
37.2
One-shot
100
80.3
18.9
47.1
22.2
4.4
16.8
0.67
32.2
Semini-1.5-PP
HiAR-ICI.
100
81.9
20.6
50.7
26.0
7.2
24.0
1.8
34.4
RAP
100
80.7
21.7
$1.9
26.7
7.9
37.7
4.2
35.1
EvoAgent
100
82.6
21.7
34.5
20.5
8.9
25.3
0.68
35.6
HTP
100
91.1
55.0
62.6
49.1
36.1
67.2
19.2
42.8
CoT
100
61.0
2.8
10.0
3.3
0.0
6.7
0.0
ToT
100
57.7
2.8
8.3
2.7
0.0
13.2
0.0
10.0
LATS
99.4
64.4
1.7
3.1
2.7
0.0
14.2
0.0
12.5
One-shot
100
57.8
3.9
8.6
3.3
0.0
7.8
0.0
7.2
GPT-3,5-turbo
HiAR-ICL
100
62.8
1.7
1.1
16.5
0.16
RAP
100
66.3
6.7
10.7
3.3
1.1
16.7
0.16
8.8
EvoAgent
100
64.2
7.8
11.0
4.4
1.1
12.2
0.0
7.5
HTP
100
55.0
6.7
6.2
3.3
1.7
27.2
0.67
19.7
to address the corresponding subtasks, shown in Figure 3. Through this self-guided approach, receives precise guid- ance tailored to the specific query, empowering it to generate comprehensive and detailed planning outcomes C that ad- here to the specific constraints. Finally, we execute the plan generation process, converting the planning outcomes into the required final solution P no (C)).
2) PlanBench is benchmark suite that includes domains from the International Planning Competition (IPC, 1998). In this study, we focus on Blocksworld, a commonsense domain centered around stacking blocks on a table, and Mystery Blocksworld, an obfuscated version the same domain. Each task contains 600 instances.
3) Natural Plan realistic natural language planning benchmark designed for itinerary creation under specific constraints, simulating real-world planning challenges. In this study, we focus on the Trip Planning task within the benchmark, which evaluates the ability to generate itincraries based on varying requirements. The dataset con- tains 1,600 queries, divided into eight difficulty levels based the number of cities involved, ranging from 10.
5. Experiments
S.1.Sttups
Benchmarks To evaluate the effectiveness of our method, we select three of the most challenging planning datasets: Travel Planner (Xie et al., 2024), PeanBench (Valmeekam et al., 2024a) and Natural Plan (Zheng et al., 2024).
Baselines We evaluate HTP against four strong bascline categories: (1) planning strategies, including CoT (Kojima et al., 2022), ToT (Yao et al., 2024) and LATS (Zhou et al., 2023): (2) in-context learning methods, including one-shot learning and HiAR-ICL (Wu et al., 2024); (3) agent methods, including EvoAgent (Yuan al., 2024), RAP (Hao al.,
1) TravelPlanner a planning benchmark focused on travel planning, aiming to find an itinerary that satisfies diverse constraints regarding flights, accommodations, and other travel arrangements. In this study, select the validation set for evaluation, which contains 180 queries and is divided into 9 groups based on difficulty levels (easy, medium and hard) and trip durations (3, 5, and 7 days).
6

---

HyperTree Planning:
Enhancing LLM Reasoning via Hierarchical Thinking
2023) and MTP (Zhang et al., 2024a) 2; (4) powerful LLMs, including ol ol-preview (OpenAI, 2024b), ol-mini, LLaMA- 3.1-405B (AI, 2024), 10MMA-3.11-0R (Dubey et al., 2024),
Table 2. Comparison with leading L.MMs across three tasks. The best results are holded, and the second hest ones underlined. SR represents the Success Rate. The cost is calculated based on
GPT-4 (Achiam et al., 2023), GPT-4o (OpenAI, 2024a), Gemini-1.5-PP (DeepMind, 2024), Claude 3.5 (Anthropic, 2024a) and Claude 3 (Anthropic, 2024b). We provide de- tailed descriptions of the baseline methods in Appendix B.
the API cost for a single instance.
Benchmark
Model
SR
Cost(in $)
GPT-4o
4.4
0.025
GPT-4
4.4
0.025
Evaluation Metrics For all benchmarks, we follow the eval- uation metries specified in the original settings. Specifically, for the TravelPlanner task, we report the delivery rate, com- monsense rate, hard constraint rate and success rate. For both the Blocksworld and Mystery Blocksworld tasks, we utilize a plan executor to execute the plans, verify their cor- rectness, and report the success rate. In the Trip Planning task, since the correct plan is unique, we calculate the suc- cess rate based on the number of matching plans. More evaluation details are given in Appendix C.I.
ol-preview
10.0
0,380
TraveIPlanner
ol-mini
1.67
0,067
Gemini-1.5-Pro
5.6
0.035
GPT-4o+HTP
20.0
0,071
Gemini-
36.1
0. 102
GPT-4o
35.5
0.007
GPT-4
34.6
0.018
GPT-4-Turbo
40.1
0.012
ol-preview
97.8
0.420
ol-mini
56.6
0.037
Gemini- 1.S-Po
23.8
0.003
Blocksworld
Claude 3. 3.5(Sonnet)
54.8
0,004
5.2. Main Results
Claude ((pus))
59.3
0.017
As shown in Table I, we evaluate HTP's effectiveness across these benchmarks. We can get the following key results:
LLaMA-3. 1--05BB-
62.6
LLaMA-3.1-700
34.4
GPT-40+HTP
54.8
0.032
1) HTP consistently achieves the best success rate across all tasks, regardless of the backbone model. For exam- ple, the success rate of Gemini-1.5-P P.o on TravelPlannerr increased from 8.9% (EvoAgent) to 36.1% with HTP, repre- senting a 4.06x performance improvement. This highlights HTP's effectiveness, strong generalization across diverse benchmarks, and adaptability to different backbone models.
Gemini-I.5-Pro-IITP
67.2
0.023
GPT-4o
3.7
0.003
GPT-4
31.1
0,009
ol-preview
36.2
0.530
Trip Planning
Gemini- 1.5
34.8
0.005
LLaMA-3.1-70B
32.5
GPT-4o+HTP
36.9
0.046
42.8
0.069
2) HTP demonstrates more significant performance im- provements on tasks with longer reasoning chains. As shown in Appendix E.3, a single inference on the TravelPlan- ner and Mystery Blocksworld dataset typically requires over 60 reasoning steps, much longer than the approximately 30 steps needed for datasets like Blocksworld and Trip Plan- ning. As result, HTP achieves a 2.8x and a 4.8x per- formance improvement on the TravelPlanner and Mystery Blocksworld respectively, far surpassing the 1.3x and 1.8x improvements observed on the other two datasets based on GPT-4o. This improvement is attributed to the ability of HTP to flexibly implement divide-and-on anndou-anddcooquur strategy, effectively reducing the length of reasoning chains while maintaining the integrity of the planning process.
hundred billions of parameters across three datasets. In addition, HTP significantly reduces token cost. Notably, HTP based on Gemini-1 achieves 42.8% accuracy on the Natural Plan benchmark, exceeding the performance of ol op-reeeeww while requiring only 13% of its cost. Similarly, HTP based on GPT-4o attains performance equivalent to ol oprrevve with the cost reduced to just 8.7%
5.4. Ablation Study and Additional Analysis
Ablations To assess the impact of individual HTP modules overall performance, conduct an ablation study us- ing GPT-4o and Gemini-1.5-Pro as the backbone models. Specifically, we evaluate five ablated versions of HTP, each omitting a distinct module. Detailed descriptions of these variants are provided in Appendix C.3. As shown in Table 3, removing any module consistently leads to a notable decline in performance. In particular:
5.3. Comparison with powerful SOTA LLMs
To comprehensively demonstrate the effectiveness of our method, we compare our approach with current SOTA closed-source models and prominent open-source models. As shown in Table 2, HTP outperforms the majority of pow- erful closed-source and open-source models with several
1) The hierarchical thinking mechanism plays crucial role in enhancing LLM performance for planning prob- lems. The removal of the division module, which supports hierarchical thinking, results in a significant drop in success rates. This suggests that LLMs with hierarchical thinking ca- pabilities achieve substantial improvements across various
2 Due to the unconventional experimental setups of MTP, we present the comparison results in the Appendix C.2.
7

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
reasoning steps, constraints, and subtasks in the itinerary. Figure 4 shows the success rates for four methods across various trip durations based on Gemini-1 1.5-pro. The re- sults reveal a noticeable decline for HiAR-ICL, Evoagent, and LATS as trip duration increases, while HTP maintains a more consistent performance trend. These findings highlight HTP's superior adaptability to more challenging planning tasks, demonstrating its robustness and scalability in scenar- ios with increasing planning complexity.
Ablation studies for key components of HTgtttent hased on GPT-4o and Gemini-1.5-Pro, evaluating the success rate (SR) across TravelPlanner (Travel.), Blocksworld (Blocks.), and Trip Planning (Trip.).
Table
Travel.
Blocks.
Trip.
Model
Method
SR
SR
SR
HTP
20.0
54.7
36.9
w/o selection
18.9
42.0
21.1
w/o division
6.1
37.2
18.8
GPT-4o
w/o decision
17.8
48.5
15.3
Pruning Strategies To determine the optimal hyperchain pruning strategy, we evaluate three selection methods: (1) Width- Width-based,;; prune branches exceeding a maximum width of n. (2) Probability : retain only the top n branches with the highest confidence probabilities. (3) I.-M-baseda: use a LLM to select up to branches considered most promising. As shown in Table both the selection and the decision module have a minimal impact on the Trav- elPlanner benchmark, which indicates that the TravelPlanner benchmark is less sensitive to pruning strategies. Therefore, we focus on the Blocksworld and Trip Planning datasets, with Demini-1.5-Prre as the backbone model and GPT-4o employed for confidence scoring in the Probability-based, method and decision-making in the LLM-based, method.
w/o outline
14.4
43.3
30.7
w/o self-guided
8.3
42.2
36.6
HTP
36.1
67.2
42.8
w/o selection
34.4
55.8
36.6
w/o division
7.2
27.8
38.4
Gemini-1..5Prr
w/o decision
33.9
57.2
35.0
w/o outline
30.6
56.0
37.2
w/o self-guided
18.9
46.5
42.5
aspects of the solution process.
2) The planning outline, in comparison to demonstration examples, significantly boosts the potential of LLMs. For instance, GPT-4o-based HTP achieves a success rate of 54.7% on Blocksworld, whereas substituting the planning outline with fixed typertree-structuree example reduces the success rate 43.3%.
Blocksworld
Trip Planning
70
50
3) The self-guided planning process markedly improves the performance of HTP on both the TravelPlanner and Blocksworld datasets. For example, GPT-4o-basee based HTP achieves a success rate of 20.0 on the TravelPlanner dataset, which drops sharply to 8.3 when the self- planning process is removed. This highlights the importance of in- depth reasoning for solving subtasks. The self-guided plan- ning process has a lesser effect on Trip Planning, primarily due to the simplicity of its subtasks.
Sunsass FaneAN
Sussess Rate(()))
80
60
55
35
Widt-based
Probabilky-based
LiM-based
2
Number HyperChaina
Number of Hyporthaina
Figure 5. Success rates the Blocksworld and Trip Planning benchmarks, categorized by different pruning strategies.
HTP((uurs)
HiAR-ICL
EvaAgent
LATS
80
Suecess Raret%)
80
Figure 5 presents a detailed comparison of the strategies across the two tasks. Notably, in the Blocksworld task, peak performance is achieved at = 2, with a slight de- cline as n increases. In contrast, performance in the Trip Planning task improves steadily as n increases, suggest- ing that Blocksworld is more likely to find an optimal path with fewer attempts, while Trip Planning benefits from ex- ploring a larger number of branches. Additionally, when is small, the LLM- and babbability-busedd strate- gies perform similarly, both outperforming the Width-based strategy. However, as increases, the LLM-based strat- egy outperforms the others, while the Probability- approach shows a decline in performance. This discrepancy is likely due to biases in the confidence scores, which may accumulate inaccuracies at deeper levels of reasoning.
20
Easyy
Easy
Easy
Madium
Modium Modium
Hard
Hard
Hard 7-day
3-day
5-day
7-day
3 3-day
5 5-day
7-day
3-day
B-day
Figure Success rates on the TravelPlanner benchmark catego- rized by problem instance difficulty and trip durations. Circles
indicate instances with a success rate 0 for clearer identification.
Reasoning Difficulty To evaluate the impact of planning difficulty on the success rates of different planning methods, we conducted a detailed analysis using the TravelPlanner benchmark. As outlined in Section 5.1, TravelPlanner can be categorized by trip durations. With every two-day increase in trip duration, there is a significant rise in the required
8

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
6. Limitations and Future Work
Limitations While our approach consistently improves performance on complex planning tasks, several key limi- tations remain when compared to human planning. LLMs struggle with complex single-step reasoning, lack human prior knowledge (e.g., budgeting strategies), are vulnera- ble to long-hone hong-horizon errors, and lack mechanisms for self- reflection and backtracking.
Future Work Looking ahead, our work offers several promising directions for future research. First, HTP inte- grates naturally with self-reflection and backtracking, mak- ing well-suited for real-world tasks such as meeting plan- ning and calendar scheduling. Its hierarchical hyperchain structure enables more accurate error correction by avoiding redundant reasoning over unrelated paths. Second, HTP's scalability and adaptability make it a strong candidate for autonomous agent decision-making. Future work may ex- plore equipping end-to-end agents with hierarchical rea- soning abilities using HTP. Third, combining HTP with LLM-based heuristic reward functions presents promising path for improving decision quality and learning efficiency.
7. Conclusion
In this work, we introduce HTP, a novel planning paradigm that utilizes hypertree construction for hierarchical thinking. By iteratively expanding the hypertree through top-down process, HTP enables multi-level divide-and-conquee strat- egy to create effective planning outline. In our evaluation across three benchmarks, HTP consistently outperforms all models. Its ability to transform extensive inference chains into hypertree structures led to significant perfor- mance improvements, especially on datasets with long in- ference chains. These results highlight the effectiveness of HTP in tackling complex planning challenges.

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Acknowledgements
reasoning. 2024. URL hRl.htss///aaiiv.orrr 2412.09078.
This work was supported in part by National Key R&D Program of China under contract 2022ZD01 19801, National Nature Science Foundations of China grants U23A20388, 62021001. This work was supported in part by Huawei as well. We would like to thank all the anonymous reviewers for their insightful comments.
Chen, D., Youssef, A., Pendse, R., Schleife, A., Clark, B. K., Hamann, H., Hc, J., Laino, T., Varshney, L., Wang. Y., et al. Transforming the hybrid cloud for emerging ai workloads. arXiv preprint arXiv:2411.13239 2024.
Chen, G., Dong, S., Shu, Y., Zhang, G., Sesay, J., Karls- son, B. F,, Fu, J., and Shi, Y. Autoagents: A frame- work for automatic agent generation. arXiv preprint arXiv:2309. 17288, 2023a.
Impact Statement
The HTP paradigm marks major breakthrough in the rea- soning field, especially for complex planning tasks. As the first method model the reasoning process with hypertree structure, it enables hierarchical thinking in LLMs, address- ing key reasoning challenges and providing a solid structural basis for future research. The top-down hypertree construc- tion algorithm offers LLMs structural guidance for solving complex problems, enhancing decision-making accuracy and efficiency.
Chen, S. and Li, B. Toward adaptive reasoning in large language models with thought rollback. In Forty-first International Conference on Machine Learning, 2024.
Chen, W., Ma, X., Wang, X., and Cohen, W. W. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks, 2023b. URL 12588.
arxiv. https: happs://axxiv.. org/
Chen, W., Su, Y., Zuo, J., Yang, C., Yuan, C.,, Chan, C.-M., Yu, H., Lu, Y., Hung, Y.-H., Qian, C., et al. Agentverse: Facilitating multi-agent collaboration and exploring emer- gent behaviors. In The Twelfth International Conference on Learning Representations, 2023c.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L.,, Akkaya, I., Aleman, F. L.,, Almeida, D., Altenschmidt, J., Altman, S.,
Anadkat, S., al. Gpt-4 technical report. arXiv preprint arXiv:2303.08874,. 2023.
Dagan, G., Keller, F., and Lascarides, Dynamic planning with 11m. arXiv preprint arXiv:2308.0639) 2023.
AI, M. Introducing llama 3.1. https: / //ai//aa.../// meta.
3-1/,
DeepMind, G. http:://deepmindl.oggg///eee goggle/eeeeeeeeeeogoeeeee gemini/ 2024.
Gemini models.
URL
Anthropic. Introducing claude 3.5 sonnet. https: /www.
claee//caaaaaeaeeeeeeeeee anthropic cww/co/////oooo. www/neww//eecccccccccccccwww.c cll aude- 1oidee--5--ee sonnett, 2024a.
Dong, Q., Li, L., Dai, D., Zheng, C., Ma, J., Li, R., Xia, H., Xu, J., Wu, Z., Liu, T., et al. A survey in-context learning, arXiv preprint
Anthropic. Introducing the next generation of claude. https:/ /tww//wwwwww. anthropic www/nww////////oocooooommo/o/. claude-33 3- fami ly, 2024b.
2022.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang. A., Fan, A., al. The llama 3 herd of models. arXiv preprint 247. 2024.
Bai, Y., Wang, J., Chen, L., Wang, Z., Kuang, Y., Yuan, M.. Hao, J., and Wu, F. graph enhanced symbolic discovery framework for efficient circuit synthesis. In The Thirteenth International Conference on Learning Representations, 2025.
Edelman, B. L.., Edelman, E., Goel, S., Malach, E., and Tsilivis, N. The evolution of statistical induction heads: In-context learning markov chains. arXiv preprint arXiv:2402.1 11004, 2024.
Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Pod- stawski, M., Gianinazzi, L., Gajda, J., Lehmann, T., Niewiadomski, H., Nyczyk, P., and Hoefler, T. Graph of thoughts: Solving elaborate problems with large lan- guage models. Proceedings of (he AAAI Conference March on Artificial Intelligence, doi: 10.1609/aaai.v88166 2024. ISSN 2159-5399,
Feng, X., Wan, Z., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang, J. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309. 17179, 2023.
Grill, J.-B., Altché, F. Tang, Y., Hubert, T., Valko, M., Antonoglou, L., and Munos, R. Monte-carlo tree search as regularized policy optimization. In International Con- ference on Machine Learning, pp. 3769-3778. PMLR, 2020.
29720. URL http:// //tp:/dxx// aaai. v3811 297220.
dx. doi. ott/oo.gg.....
Bi, Z., Han, K., Liu, C., Tang, Y., and Wang. Y. Forest- of-thought: Scaling test-time compute for enhancing lim
10

---

IPC. International planning competition. https:// wttpccomeettiions....ooo HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Guan, L., Valmeekam, K., Sreedharan, S., and Kambham- pati, S. Leveraging pre-trained large language models to construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, (1479081-790944 2023.
Lin, Z. and Lee, K. Dual operating modes of in-context learning. arXiv preprint arXiv:2402./88/9 2024.
Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L.,, and Chen, W. What makes good in-context examples for gpt-3? arXiv preprint arXiv:2101 htt.::2011.080000 100000000044,.0 2021.
Hao, S., Gu, Y., Ma, H., Hong, J. J., Wang, Z., Wang. D. Z and Hu, Z. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305. 14992, 2023.
Lu, Y., Bartolo, M., Moore, A.. Riedel, S., and Stenetorp, P. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08758 2021.
Hong, S., Zheng, X., Chen, J., Cheng, Y., Wang, J., Zhang, C.. Wang, Z., Yau, S. K. S., Lin, Z., Zhou, L.. et al. Metagpt: Meta programming for multi-agent collabora- tive framework. arXiv preprint arXiv:2308. 00352, 2023.
Ning, X., Lin, Z., Zhou, Z., Wang, Z., Yang, H., and Wang, Y. Skeleton-of-tee of-thought: Prompting Ilms for efficient par- allel generation. In The Twelfth International Conference Learning Representations, 2024.
Huang, J., Chen, X., Mishra, S., Zheng, H. S., Yu, A. W., Song, X., and Zhou, D. Large language mod- els cannot self-correct reasoning yet. arXiv preprint arXiv:2310.01798, 2023.
OpenAL. Hello gpt-4o. URL URI https:// owwpaa..co//ideeeee.e.oo...oo gpt-4o/, 2024a.
OpenAI. Openai ol system card. preprint, 2024b.
Putta, P., Mills, E., Garg, N., Motwani, S., Finn, C., Garg, D., and Rafailov, R. Agent q: Advanced reasoning and learning for autonomous ai agents. arXiv preprint arXiv:2408.077 2024.
www. 1998.
Jeon, H. J., Lee, J. D., Lei, Q. and Van Roy, B. An information-theoredt analysis of in-context learning. arXiv preprint arXiv:2401./5530 2024.
Qi, Z., Ma, M., Xu, J., Zhang, L. L., Yang, F., and Yang, M. Mutual reasoning makes smaller Ilms stronger problem- solvers. arXiv preprint arXiv:2408.06/95 2024.
Ju, D., Jiang, S., Cohen, A., Foss, A., Mitts, S., Zharmagam- betov, A., Amos, B., Li, X., Kao, J. T., Fazel-Zarandi, M., et al. To the globe (ttg):: Towards language-driver guar- anteed travel planning. arXiv preprint arXiv:2410. 16456 2024.
Qin, C.,, Zhang, A.,
Chen, C., Dagar, A., and Ye, W. In- context learning with iterative demonstration selection. arXiv preprint arXiv:2310.0980 2023.
Sel, B., Al-Tawaha, A.. Khattar, V., Jia, R., and Jin, M. Algorithm of thoughts: Enhancing exploration of ideas in large language models, 2024. URL https::///ee //axivv.
Kocsis, L. and Szepesvári, C. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
org/ abs//ba33 22002/30..00 10379.
Shum, K., Diao, S., and Zhang, T. Automatic prompt aug- mentation and selection with -ffuin----houugle from la- beled data. arXiv preprint arXiv:2302. /2822, 2023.
Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Ad- vances in neural information processing systems, 35: 22199 22213, 2022.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Grae- pel, T., et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv:171 2017.
Lample, G., Lacroix, T., Lachaux, M.-A., Rodriguez, A., Hayat, A., Lavril, T., Ebner, G., and Martinet, X. Hyper- tree proof search for neural theorem proving. Advances in neural information processing systems, 35:26337-26349, 2022.
Sprague, Z., Yin, F., Rodriguez, D., Jiang, D., Wadhwa, M., Singhal, P., Zhao, X., Ye, X., Mahowald, K., and Durrett, G. To cot or not to cot? sfain-of-thoughe helps mainly math and symbolic reasoning. arXiv preprint arXiv:2409. 12183, 2024.
Lee, K.-H., Fischer, I., Wu, Y.-H., Marwood, D., Baluja, S., Schuurmans, D., and Chen, X. Evolving deeper I1m thinking. arXiv preprint arXiv:2501.0989), 2025.
Liang, T., He, Z., Jiao, W., Wang. X., Wang, Y.. Wang. R., Yang, Y., Shi, S., and Tu, Z. Encouraging divergent thinking in large language models through multi-agent debate. arXiv preprint arXiv:2305. 18/ 2023.
Tanwar, E., Dutta, S., Borthakur, M., and Chakraborty, T. Multilingual llms are better cross-lingual in-context learn ers with alignment. arXiv preprint arXiv:2305.059M. 2023.

---

HyperTree Planning:
Enhancing LLM Reasoning via Hierarchical Thinking
Valmeekam, K., Marquez, M., Olmo, A., Sreedharan, S., and Kambhampati, S. Planbench: An extensible bench- mark for evaluating large language models on planning and reasoning about change. Advances in Neural Infor- mation Processing Systems, 36, 2024a.
Wang, Z.,, Chen, L., Wang, J., Bai, Y., Li, X., Li, X., Yuan, M., Hao, J., Zhang, Y., and Wu, F. A circuit domain generalization framework for efficient logic synthesis in chip design. In Forty-first International Conference on Machine Learning. PMLR, 2024d.
Valmeekam, K., Stechly, K., Gundawar, A., and Kambham- pati, S. Planning in strawberry fields: Evaluating and improving the planning and scheduling capabilities of Irm ol. arXiv preprint
Wang. Z., Wang. J., Zuo, D., Ji, Y., Xia, X., Ma, Y., Hao, J., Yuan, M., Zhang, Y., and Wu, F, A hierarchical adaptive multi-task reinforcement learning framework for multi- plier circuit design. In Forty-first International Confer- ence on Machine Learning. PMLR, 2024e.
2024b.
Wang, J. W., Yang, Q., Bai, Y., Li, X., Chen, L., HAO, J.. Yuan, M., Li, B., Zhang, Y., and Wu, F. Towards next eext-generation logic synthesis: A scalable neural cir- cuit generation framework. In The eiihty- Annual Conference on Neural Information Processing Systems, 2024a. URL https: http:://ppeerevveeeee .ette/eweeeeeeeeeeeeeeeeeeeee forum? 1d=2YNYhhSoch.
Wang, Z., Wang, J., Xia, X., Zuo, D., Chen, L., Ma, Y., Hao, J., Yuan, M., and Wu, F. Computing eircuits optimiza- tion via model- based circuit genetic evolution. In The Thirteenth International Conference on Learning Repre- sentations, 2025.
Wei, J., Wang. X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thouge prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24833 2022.
Wang, L., Xu, W., Lan, Y., Hu, Z., Lan, Y., Lee, R. K.W.W, and Lim, E.PP. Plan-and-solve prompting: Improving zero-shot chain-of- of-tuuught reasoning by large language models. arXiv preprint arXiv:2305.0400 2023a.
Wang, I.., Ma, C., Feng, X., Zhang, Z., Yang, H., Zhang, Chen, Z., Tang, J., Chen, X., Lin, Y., et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6): 166):1 2024b.
Wu, J., Feng, M., Zhang, S., Che, F., Wen, Z., and Tao, J. Beyond examples: High-level automated reasoning paradigm in in-context learning via mets. arXiv preprint urXiv:2411.1888 2024.
Wang, P., Li, L.,, Shao, Z., Xu, R., Dai, D., Li, Y., Chen, D., Wu, Y., and Sui, Z. Math-shepherd: Verify and reinforce Ilms see-by-step without human annotations. In Proceed- ings of the 62nd Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), pp. 9426-9439, 2024c..
Xie, J., Zhang, K., Chen, J., Zhu, T., Lou, R., Tian, Y., Xiao, Y., and Su, Y. Travelplanner: A benchmark for real-world planning with language agents. arXiv preprint arXiv:2402.01622, 2024.
Yang, Z., Ishay. A.. and Lee. J. Coupling large language models with logic programming for robust and general reasoning from text. arXiv preprint arXiv:2307.0760 2023.
Wang, Z., Wang, J., Zhou, Q. Li, B., and Li, H. Sample-efficient reinforcement learning via conserva- tive model-based actor-critic. Proceedings of the
AAAI Conference on Artificial Intelligence. 36(8):
0612-8620. Jun. 2022. doi: 10.1609/aaii. 20839. URL. https://ojss aaaiia.... iacii.rrg org/ index.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:22 10.03629 2022.
Wang, Z., Li, X., Wang, J., Kuang, Y., Yuan, M., Zeng. J.. Zhang, Y., and Wu, F. Learning cut selection for mixed-integer linear programming via hierarchical se- quence model. In The Eleventh International Confer- ence on Learning Representations, 2023b. URL https: //openreview net/ forum wiw.mmmiidddooooo 4P Pob.r 9bRNcK.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Yuan, S., Song, K., Chen, J., Tan, X., Li, D., and Yang, D. Evoagent: Towards automatic multi-agent generation via evolutionary algorithms, 2024.
Wang, Z., Pan, T., Zhou, Q., and Wang, J. Efficient ploration in resturee-restricted reinforcement learning. Proceedings of the AAAI Conference on Artificial Intel- ligence, 1eet10029-1220 Jun. 2023c. doi: 10.1609/ vaai.v37i8,220 26224. URL httph: oar..oo....a.../////////oo.. index. hmdex..ph//aaa/aaatiieeeee///e/s
Zhang, C., Deik, D. G. D. G., Li, D., Zhang, H.,, and Liu, Y. Meta-task planning for language agents. arXiv preprint arXiv:2405. 16510, 2024a.
12

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Zhang, D., Zhoubian, S., Hu, Z., Yue, Y., Dong, Y., and Tang, J. Rest-mets*: Llm self-training via process reward guided tree search. arXiv preprint arXiv2446.038166 2024b.
Zhang, X., Du, C., Pang, T., Liu, Q. Gao, W., and Lin, M. Chain of preference optimization: Improv- ing chain-of-thought reasoning in 1lms. arXiv preprint OrXiv:2406.09158 2024c.
Zhao, Z., Wallace, E., Feng, S., Klein, D., and Singh, S. Calibrate before Improving few-shot performance of language models. In International conference machine learning, pp. 12697-12706. PMLR, 2021.
Zheng, H. S., Mishra, S., Zhang, H., Chen, X., Chen, M., Nova, A., Hou, L., Cheng, H.-T., Le, Q. V., Chi, E, H., et al. Natural plan: Benchmarking Ilms natural lan- guage planning. arXiv preprint arXiv:2406.0444 04520, 2024.
Zhou, A., Yan, K., Shlapentokh -othhttonhhRoRaaa,nn M., Wang, H., and Wang, Y.-X. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint 233 23..:23313.4400000 2023.
Zhou, Y., Li, J., Xiang, Y., Yan, H., Gui, L., and He, Y. The mystery of in-context learning: comprehensive survey interpretation and analysis. In Proceedings the 2024 Conference Empirical Methods in Natural Language Processing, pp. 14365-14378, 2024.
Zhu, X., Wang. J., Zhang, L., Zhang, Y., Gan, R., Zhang, J., and Yang, Y. Solving math word problems via coopera- tive reasoning induced language models. arXiv preprint arXiv:2210.16257, 2022.
13

---

HyperTree Planning:
Enhancing LLM Reasoning via Hierarchical Thinking
A. More Background
Reasoning path modeling LLMs are increasingly used for inference, with reasoning path modeling methods evolving beyond traditional CoT and ToT to decompose complex problems into simpler tasks. Program of Thought (PoT) (Chen al., 2023b) structures reasoning as programmatic steps, using variable names for semantic clarity, Algorithm of Thought (AoT) (Sel et al., 2024) compacts these steps into a single prompt, reducing token consumption while improving efficiency. Graph of Thought (GoT) (Besta et al., 2024) models inference as a graph, enabling dynamic path selection and backtracking. Forest of Thought (FoT) (Bi et al.. 2024) builds an ensemble of inference trees, leveraging sparse activation for more efficient decision-making. These methods enhance LLMs' ability to handle complex problems with greater flexibility and accuracy. Meanwhile, complex reasoning has also been widely explored in circuit design (Wang et al., 2024e; 2025). logic synthesis (Bai et al., 2025; Wang et al., 2024d;a), and optimization (Wang et al., 2023b), demonstrating its potential in guiding structured and efficient Recision-making Notably, hierarchical and sample-efficient frameworks (Wang et al., 2022; 2023c) have shown success in these domains, motivating their extension hierarchical reasoning with LLMs.
B. Experiment Settings
B.1. Implementation Details of the Baselines
Below, we provide short descriptions of the five planning strategy baseline methods and two agent methods.
CoT: CoT (Chain-of- -fhoughh- (Kojima et al., 2022) facilitates efficient and effective step-by-step reasoning by appending the phrase "Let's think step by step" to the prompt, guiding the model through a structured reasoning process.
ToT: ToT Srre-oof-Thoughy (Yao et al., 2024) enables multi-path reasoning by guiding large models to generate multiple feasible parallel reasoning paths simultancously. In our setup, the pruning strategy of ToT is always aligned with the HTP method.
LATS: LATS refers to Language Agent Tree Search (Zhou al., 2023), a general framework that harnesses the reasoning, acting, and planning capabilities of language models while integrating Monte Carlo Tree Search to explore the search space. It has demonstrated exceptional performance in planning tasks (Chen et al., 2024).
The ohe-shot approach enhances the reasoning ability of large models by providing a fixed example, guiding them learn through analogy. For specific examples, please refer to Appendix E.4.
One shot:
HiAR-ICL: HiAR-ICL stands for High-level Automated Reasoning Paradigm in In- In-Context Learning (Wu et al., 2024), a powerful ICL method that shifts the focus from specific examples to abstract thinking patterns, thereby enhancing the generalization ability of LLMs.
RAP: RAP (Reasoning via Planning) (Hao et al., 2023) repurposes the LLM as both world model and reasoning agent, integrating a principled planning algorithm based on Monte Carlo Tree Search to enable strategic exploration within the vast reasoning space.
EvoAgent: EVOAGENT (Yuan et al., 2024) is generic method to automatically extend expert agents multi-agent systems via the evolutionary algorithm, thereby improving the effectiveness of LLM- agents in solving tasks.
MTP(meta-task planner) (Zhang et al., 2024a) is a zero-shot methodology for collaborative M-beed multi- agent systems that simplifies complex task planning by decomposing it into a hierarchy of subordinate tasks.
MTP:
B.2. Backbone Model Selection
For OpenAl models, we use gpt-3.5-turbo- 1106 and opt-4o-2024-08 For Semini--15--Pie we use Google Gemini-1.5-1 APIs to obtain results. We set the temperature for all models.
14

---

HyperTree Planning:
Enhancing LLM Reasoning via Hierarchical Thinking
C. Additional Results
C.1. Evaluation Details of TravelPlanner
Grounding to travel planning, a real-world use-case that inherently involves various constraints like user preferences and commonsense rules, TravelPlanner evaluates whether agents can formulate flexible travel plans using gathered information meet these constraints. We test EVOAGENT and all baselines the TravelPlanner validation set, which consists of 180 user queries with the collected information. To evaluate the travel plans generated by agents, TravelPlanner adopts the following evaluation metrics:
1. Delivery Rate: Assesses if agents can complete plan within limited number of steps (30 in our experimental setting). Failures are due dead loops, numerous failed attempts, exceeding the step limit.
2. Commonsense Constraint Pass Rate: Evaluates agent can incorporate commonsense into their plan.
3. Hard Constraint Pass Rate: Measures if a plan meets all explicit hard constraints the query, testing the agent's ' ability to adapt to diverse user preferences.
4. Success rate: Indicates the proportion of viable plans that meet all criteria, reflecting the agent's proficiency in creating practical plans.
Furthermore, TravelPlanner uses micro and macro strategies to assess the Commonsense and Hard Constraint Pass Rates. The micro strategy calculates the ratio of met constraints the total. The macro strategy measures the proportion plans that meet all commonsense or hard constraints. Together, these strategies assess an agent's 's ability satisfy individual constraints and all constraints comprehensively.
C.2. Comparision with MTP
In this part, we compare our HyperTree Planning (HTP) method with the Meta-task Planner (MTP) (Zhang et al., 2024a) approach. As MTP reports its results exclusively 3-day trip durations within the TravelPlanner benchmarks, adopt the same evaluation setting to ensure consistency. Furthermore, we introduce three additional bascline methods for comparison: React (Yao et al., 2022), Direct, and CoT (Wei et al., 2022). Importantly, both the React and MTP methods employ two-stage mode, while the Direct, CoT, and HTP methods utilize sole-planning mode, bypassing the intommationggahheiinn step for a more streamlined process.
From Table 4, 5, and 6, is clear that HTP consistently achieves the highest success rate across tasks of varying difficulty levels: easy. medium, and hard. This superiority is even more evident the detailed metrics of Commonsense and Hard Constraint, underscoring the effectiveness of our approach in comprehensively addressing complex problems.
Table 4. The Success Rates (%) on Easy Instances. The highest success rates are highlighted in bold blue.
Methods
GPT-4 + React
GPT-+
GPT- + Direct
GPT-4 CoT CoT GPT-4 + HTP((Our))
Delivery
95.00
100.00
100.00
100.00
100.00
Common-
Micro
75.00
95.63
95.00
89.38
95.63
Validation
sense
Macro
5.00
70.00
65.00
55.00
65.00
Set
Hard
Micro
15.00
55.00
60.00
55.00
60.00
Constraint
Macro
15.00
55.00
60.00
55.00
60.00
Success
Rate
5.00
55.00
35.00
40.00
55,00
Table 5. The Success Rates (%) Medium Instances. The highest success rates highlighted in bold blue.
Methods
GPT-4 Renct
GPT44 MTP
GPT44 + Direct
GPT-4 CoT
GPT-4 HTP((Ours)
Delivery Rate
100.00
95.00
100.00
100.00
100.00
Common-
Micro
83.75
82.50
91.88
84.38
96.88
Validation
sense
Set
Hard
Micro
7.50
55.00
55.00
55.00
80.00
Success Raie
0.00
15.00
5.00
10.00
55.00
15

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Table The Success Rates (%) on Hard Instances. The highest success are highlighted in bold blue.
Methods
GPT-4 Renct
G MTP
GPT4 Direct
+ CoT
GPT-4 HTP((Ous)
Delivery Rate
100.00
95.00
100.00
100.00
100.00
Common-
Micro
79.38
83.75
88.75
94.38
Validation
Scnse
Macro
10.00
40.00
35.00
45.00
60.00
Set
Hard
Micro
5.00
41.25
50.00
55,00
75.00)
Constraint
Macro
0.00
30.00
5,00
5.00
45.00
Success Rate
0.00
30.00
0.00
0.00
35,00
C.3. Details of Ablations
We evaluate five ablated versions of HTP using GPT-4 as the backbone model, where each version omits one specific design principle:
1/ selection: The selection module is replaced with strategy that always chooses the leftmost leaf node.
2)w/o division: The decomposition module is removed. The hypertree-struacture planning outline degenerates into tree- structure.
w/o decision: The decision module is removed, and during expansion, a single branch is always maintained for each non-leaf node.
4)w/o outline
The planning outline is replaced with a fixed hypertree planning example instead of being dynamically generated for each query.
5) self-guideds The hypertree results are directly used as the complete planning content, but all necessary external information provided during the construction of the hypertree.
D. Analysis of Computational Cost
To address concerns regarding the efficiency of our proposed method, provide a comprehensive analysis of computational cost across different reasoning paradigms, including CoT (Wei et al., 2022), RAP (Hao et al., 2023), and our method HTP, using the TravelPlanner dataset. Due to the suboptimal performance of open-source models on this task, we adopt GPT-4o as the backbone model for all evaluations.
We assess computational efficiency from three perspectives: inference speed, token cost, and computational complexity. Let be the number of branches expanded at each step (with n S 2 in TravelPlanner), / the average number of reasoning steps per chain, and l the number of sampled trajectories in MCCTS-bseed methods.
Model CoT
Inference Speed (s)
Token Cost (in/out)
Computational Complexity
6.92
4328 641
O()
RAP 41.94
5440 3374
Onkll)
HTP
25.27
5562 / 963
O
Table 7. Comparison of computational cost across different reasoning methods on TravelPlanner.
The results clearly demonstrate that HTP significantly reduces computational cost compared to RAP across all three metrics. This is attributed the elimination of MCTS in HTP, which avoids costly sampling and value estimation procedures, thereby improving efficiency.
Additionally, although HTP employs hyperchain reasoning structure to support hierarchical planning, this does not increase its overall computational complexity. The higher dimensionality of reasoning is counterbalanced by shorter average reasoning paths, resulting in computational efficiency that remains on par with non-hicrarchical approaches.
Additional Analysis and Potential Improvements. We note that the inference cost of HTP can sometimes exceed that of conventional single-path backbone models, primarily due two factors:
1. Multi-path reasoning overhead, resulting from the expansion of multiple candidate paths (e.g., tree search).
16

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
2. Hierarchical decomposition, where the original task is divided into finer-grained subproblems, requiring more detailed reasoning.
The impact of these factors varies across tasks. In the TraveIPlanner task, the overhead mainly stems from the need for constraint-aware reasoning (factor 2), whereas in NaturalPlan, the major cost associated with the search process needed to identify a feasible solution via trial-and-error (factor 1).
Despite these additional sources of cost, HTP remains substantially more efficient than MCTS- baseed methods, as it avoids repeated simulations and value estimation.
To further improve efficiency, we propose two directions for future work:
Using smaller fine-tuned models (instead of large backbone models) for intermediate reasoning steps during hypertree construction.
Adopting meta-learning techniques to predict task complexity and dynamically adjust hypertree parameters (e.g.. depth and width), allowing for adaptive and efficient reasoning based on task demands.
E. Case Study
This includes examples of different states on the four task sets of TravelPlanner, Blocksworld, Mystery Blocksworld, and Trip Planning. E.1 include examples of the HyperTree library (rules and nodes). E.2 include examples of the Htpuurrre-stuuturre planning outline. E.3 include examples of the planning process. E.4 include examples of the final plan.
E.1. Examples of the HyperTrre Library (Rules and Nodes)
TravelPlanner:
Rules:
1. [Plan] -> [Taassportttion] [Accommddation] [Attraction] [Dining] The plan can be divided
into four aspects.
2. [Transportation] -> [[Specific segments of transportation # Break transportation down into specific transportation choices for each segment of the trip. The transportation mode for each segment can be choose from self-driving, taxi, and flights.
3. itransportation from A to B] -> [Self-driving] [Fiigh]
4. [Self feriving -> [transportation availabilityl [transportation preference] [cost] [non= [aaalaabittyy]rraapprrtttt conflicting] # Fer each mode of transportation, you should consider tranaportation availability, transportation preference, cost and con-conflicting.
[Taxi] -> [transportation availability] [transportation preference [cost] [non-
conflictingl
[Flight] -> [transportation availability] (transportation preference] [cost] ] [non-
conflicting]
5. [Accommodatien] -> [Speciiic accomnodation for each city)) $ Break accommodation down into specific accommodation options for each city.
6. [Accomnddation for A] -> [cost] [house rule] [room type] [minimum stayl # For accommodation in each city, consider the cost, house rules, room type, and minimun stay reqeite
7. [Attracticn] -> Hspecific attraction for each city | Break accommodation down into specific attraction options for each city.
10
8. [Dining] -> 11Specific dining for each city)) Break dining down into specific dining options for each city.
11
9. [Dining for A] [cost] [cuisine] For dining in each city, consides the cost and cuisine.
13
Divisible Nodes: [Plan]; [Transportation); [Taxi]; [Self-driving] [Flight]; [Accommodation]) [Attraction] ; [Dining];
([Specific segment of transportatien)) # (Note: This placeholder represents the specific
16
modes of transpertation for one segment of the trip, such as (transportation from A to B))
(Speci fic accommdattion for one city]) # (Note: This placeholder represents the specific fic accommodatio options for one city in the trip, such as [Accommodation on for A]);
17

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
(Speccific dining for one city?} (Note: This placeholder represents the specific dining options for one city in the trip, such as [Dining for Al);
19
Leaf Nodes (Example):
(transportaticn availabilityl; (transportation preference]; [transportation cost]; [house rule]; [room type]; (accommodation cost]; [minimum stayl; [cuisine]; [dining cost]; Hsspecffic attraction for one citył} # (Note: This placcholder represents the specific attraction optiens for one city in the trip, such as [attraction for Al).
22
Blocksworld:
Rules:
[Plan] -> ([[(())cck) on the table] (((lock)) the table] [((lock))
top of ([Block
111 [[[B]ock]] en top [(block]11)} (Note: The quantity and types of symbols are indefinite. The plan is divided into different floors, and if the target state requires multiple blocks on the same floor, there will result in multiple symbois s in parallel relationship);
[[[Blcc)]] the table] on the table]]] # (Note: The quantity and types symbols are indefinite. The general approach is to break down the task into atomized, specific actions, and there can be multiple symbols in parallel relaticnships);
[to get ([Block)) clear] [to get hand empty] [to get ((Block))
[[(Block)) on top of ([Block)]] -> ([[to get [[Block)] clear] [to get hand emptyl [to get [(Block)) clear] [to get hand emptyl [to get [[Block]]
top [[Block)]1]] (Note: The quantity and types of symbols are indefinite. The general approach is to break down the task into atomized, specific actions, and there can be multiple symbols in paraliel relationships);
Divisible Nodes: [Plan];
[[(Block)] on the table] I (Note: This placeholder represents the speci fic blocks); [[[Block]] top of [[Block)]] # (Note: This placeholder represents the desired
arrangement of the blocks);
10
Leaf Nodes (Example): [to get ((Block)) clear] # (Note: This placeholder represents the specifle blocks); Ito get hand emptyl; [to get [(Block)) the tablel; [te get [[Hlock)] on top of ([Rlock) (Note: Unlike non-terminals which refer to broad directions, here it refers to atom zed speci tasks.)
11
12
Mystery Blocksworld:
Rules:
[Plan] -> [[Pllaet [10bject]]] (Planet [10bject] }] [[ [Object]] Craves :(0bject]] ||] [[O0bject }) Craves ((bbject))))) І (Note: The quantity and types of symbols are indefinite. The plan is divided into different crave-relationship,, and if the target state zequires
multiple objects on similar Crave-relationshipp there will result in muitiple symbols in parallel relaticnships);
[Planet [[Object)]] -> [to get Prevince [[0bject]] becomes True] [to get Harmony becomes True] [to get Planet [[Object)] beccmes True]]] + (Note: The quantity and types symbols are indefinite. The general approach to break down the task into atonized, specific actioos, and there can be multiple symbols in parallel relationstips);
ll [Obbjett)) Craves [[0bject))] -> [llto get Frovince [[0bject]] becones Truel Ito get rmony becomes True] [to get Province ([Object]] becomes True] [to get Harmony becomes True [to get ([Object)) craves [[Object]]l])
(Note: The quantity and types of symbols are indefinite. The general approach is to break down the task into atomized, specific actions and there can be multiple symbols in parallel relationships);
Divisible Nodes: [Plan];
[Planct [[0bject]]] # (Note: This placeholder represents specific objects on a planet, such as (Planct object Al); [(Objetct] Craves [[0bject]]] & (Note: This placeholder represents the desired arrangement where object craves another);
10
18

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Leaf Nodes (Example):
[to get Province { ((0bject)) becomes True] (Note: This placeholder represents specific objects that need to be cleared);
12
[to get Harmeny becomes Truel; [to get Planet [[0bject)] becomes Truel; [to get (10bject]] ) [[Object)]] # (Note: Unlike non-terminals which refer to broad directions, here it refers to atemized specific tasks.);
13
Trip Planning:
Rules:
[Plan] [Cities with determine dates] [Cities with undetermine dates] (Note: Translate the travel plan into cities with specific dates and cities with unspecific dates, and consider them separately);
# (Note: The quantity of symbols are indefinite. The cities here those where the activities explicitly specified in the query);
(Cities with determine dates] -> [
(Note: the quantity and types of symbols are indefinite. The cities here are the remaining cities in the query); [[ [[City)]] => [from day {{i}} to day (i)] (Note: further expand the city into specific dates).
[Cities with undetermine dates] -> ((I(Citt))
Devisible Nodes:
[Plan]; [Cities with determine dates]; [Cities with undetermine dates];
[[City)]]] (Nete: This placcholder represents the city in the query, such [London]);
leaf Nodes (Example): [from day ((i}} to day {i)] + (Note: This placeholder represents speci fic date in one city 12 );
E.2. Examples of the HyperTrre--tuuttured Planning Outline
TravelPlanner:
[Plan]
[Transportation]
(Transpertation from Fort Lauderdale City in Georgia] [Self-driving]
[transportation availability)
[transportation preference]
(transportation cost]
Taxil
/transportation availability)
ttransportation preference]
(transportation cost]
[Flight]
12
(transportation availability)
13
(transportation preference]
14
(transportation cost]
[Transpertation from City in Georgia to City 2 in Georgia] [Seif-driving]
17
Itransportation availability)
18
ttansppotttionn preference] ttransportatinn cost]
19
20
[Taxi]
21
(transportation availabilityl
22
[transportation preference]
25
(transportation cost]
24
[Flight]
25
[transportation availability]
26
(transportation preference]
27
(transportation cost]
28
[Transportation from City in Georgia to City 3 in Georgia]
[Self-driving]
(transportation availability)
51
19

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Itransportation preference]
32
(transportation cost] [Taxi]
33
34
[transportation availability)
[transportation preference]
(transportation cost.
57
[Flight]
38
[transportation availability]
39
(transportation preference]
Itransportation cest]
41
[Transportation from City in Georgia to Port Lauderdales 1e] [Se1 [Self-driving]
42
43
[transportation availability)
44
[transportation preference] [transportation cost
46
[aaxi]
47
[transportation availability]
48
[transportation preference]
Itransportation cost]
50
[Flight]
51
[transportation availability]
52
(transportation preference] (transportation cost]
53
[Accomeedatien]
55
|Accommodation for City 1 in Georgia] [minimum stay]
56
57
[hcuse rule]
[roem type]
[acconndattion cost]
[Accomoddation for City 2 in Georgia]
61
[minimum stay]
[hcuse rule]
[roem type]
64
(accommodation cost]
65
[Accommodation for City 3 in Georgia]
66
[minimum stay]
[house rule]
Ireem typel laccomoodation cost
69
70
|Attraction|
71
[Attraction for city in Georgia] [Attraction for City in Georgia] [Dining)
72
73
[Attraction for City 3 in Georgia]
74
75
[Dining for City 1 in Georgia] [cuisine]
76
77
[dining cost]
78
[Dining for City 2 in Georgia] [cuisine] [dining cost]
79
80
[Dining for City 3 Georgia] [cuisine] [dining cost:]
84
Blocksworld:
[Plan]
Blue block on the table]
[te get the blue block clear]
[to get the blue block on the table]
[Orange block on the table]
[to get the orange block clear]
[tc get the orange block the table]
[Orange black top of Blue black]
[to get the blue block clear]
20

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
[to get the orange block clear]
[to get the orange block on top of the blue block] [Red block on top of Orange block]
11
12
[to get the red block clear] [to get the orange block clear]
[to get the red block on tep the orange block]
15
Mystery Blocksworid:
[Plan]
[Planet object b]
[to get Province object b becores True] [to get Planet object beccmes True] [ooject d Craves Object b]
Ito get Province opject d becones True] Ito get Province onject b becones True] [to get object Crave object b]
[Object с Craves Object d]
[to get Province object с becores True] [to get Province object d becones True]
10
[to get object Crave object d]
Trip Planning:
[Plan]
[Cities with determine dates]
[Valencia]
[from day to day 3] [Stockhelm]
[from day 6 to day 10] [Madrid]
[from day 20 to day 21] [cities with undetermine dates] [Seville]
10
[from day 3 to day 4] [Bucharest]
11
[from day 21 day 22] [Nice]
14
[from day 17 to day 20] [Manchester]
15
16
[from day to day 6] [Krakow]
[from day to day 11] [Vilnius]
19
20
[frem day 11 to day 14]
21
[Zurich]
[frem day to day 171
23
E.3. Examples of the Planning Process
TravelPlanner:
Break down the travel planning into four parts: transportation, attract' ons, dining, and accommodation.
For the transportation part:
The transportation I need to consider involves four parts: from Houston to Nashville 2022-03-21, from Nashville to Knoxville 2022-03-23, from Knoxville to Chattanooga 2022-03-25, from Chattanoogs For the transportation from Houston Nashville: I observe that flights, self-driving, and taxis are all available. The user prefer no sclf-driving, so I can only choose between Flight or taxi for transportation. I should choose the one that costs less.
Houston 2022-03-27.
New calculate the cest of choosing the flight option: the loweat-pricnt flight $145, and there are travelers, making the total cost $145
$290.
21

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
New calculate the cest of choosing the taxi option: there are travelers, we need 1 taxi, the price is $1253 * $1253.
Sc will choose the flight option. I will submit: "Flight Number: F3956409, from Houston to Nashville, Departure Time: 17:36, Arrival Tine: 19:12". For the transportation from Nashville to Knoxville 2022-03-23: observed that there is no flight from Nashville to Knoxville on 2022-03-23, but sclf-driving and taxis are available.
11
The user prefer no self-driving, so I can only choose taxi. will submit: "taxi, from Nashville to Knoxville, duration: 2 hours 42 mins".
12
For the transportation from Knoxville to Chattanooga on 2022-03-25: observed that there is no flight from Knoxville to Chattanooge on 2022-03-25, but self-driving and taxis are available. The user prefer no self-driving, "taxi, from Knoxville to Chattanocga, duration: hour 41 mins".
13
can only choose taxi. will submit:
For the transportation from Chattanooga to Houston on 2022-03-27:
16
I observed that there is no flight Chattanooga to Houston on 2022-03-27,
17
but self-driving and taxis are available.
The user prefer no self-driving, "taxi, from Chattanooga to Houston, duration: 11 hours mins".
can only choose taxi. will submit:
18
For the attractions part: The attractions I need to consider involves three parts: attractions in Nashville, Knoxville, Chattanooga.
19
20
For the attractions in Nashville: I am in Nashville from 2022-03-21 to 2022-03-22, so should choose two aatractionn in Nashville. I will submit: "Country Music Hall of Fame and Museum, Nashville for day 1 and "Nashville 7oo at Grassmere, Nashville" for day 2. For the attractions in Knoxville:
22
in Knoxville from 2022-03-23 to 2022-03-24, so should choose two aattractions in Knoxville, will submit: "World's Fair Park, Knoxville" for day and Knoxville Museum of Art, Knoxville" for day 4.
For the attractions in Chattanooga:
I in Chattanooga from 2022-03-25 2022-03-27, I have chosen three 26
aattrccioons in Chattanooga, I will submit: "The Chattanooga Zoo at Warner Park, Chattanooga" for day 5, "Rock city Gardens, Chattanooga" for day and "Teanessee Aquarium Chattanocga" for day 7.
For the dining part:
The dining need consider involves three parts: dining in Nashville from 2022-03-24 to 2022-03-22, 2022-03-25 to 2022-03-27.
Knexville from 2022-03-23 to 2022-03-24, in Chattanooga from
For the dining in Nashville from 2022-03-21 to 2022-03-22:
Since breakfast and lunch on the first day do not need to be considered, I 30 need to account for 4 meals.
The user requests French cuisine, and the French restaurant with the 31 lowest price is: Twigly.
The user requests Mexican cuisine, and the Mexican restaurant with the lowest price is: Bablu Fast Food.
still need to find 2 more restaurants, and the 2 with the lowest prices are: Kitchen King, Govinda's Confectionery.
33
To sum up, I will submit: "Twigly, Nashville" for day : and "Bablu Fast Food, Nashville", "Kitchen King, Nashville", "Govinda's Confectionery Nashville" for day
34
2.
For the dining in Knoxville from 2022-03-23 to 2022-03-24:
35
I need to select 6 different restaurants.
56
The user requests French cuisine, and the French restaurant with the
37
Lowest price is: Biryani By Kilo.
The user requests Mexican cuisine, and the Mexican restaurant with the lowest price is: Open Kitchen.
38
I still need to find 6 - 2 = more restaurants, and the 4 with the lowest prices are: Chit Chat, Mamagoto, La-Nawaab, Tandoori Tadka.
59
To sum up, will submit: "Biryani By Kilo, Knoxville", "Open Kitchen, Knoxville", "Chit Chat, Knoxville" for day 3 and "Mamagoto, Knoxville", "La-Nawaab, Knoxville", "Tandcori Tadka, Knoxville" for day 4.
For the dining in Chattanooga from 2322-03-25 to 2022-03-27: Since lunch and dinner on the last day do not need to be considered, I need to select 2 different restaurants.
41
22

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
The user requests French cuisine, and the French restaurant with the Tpot.
lowest price is:
The user requests Mexican cuisine, and the Mexican restaurant with the 44
lowest price is: Liquid.
reataurants, and the with the lowest prices are: Muradabadi, Burger's a King, Basil Tree, Sardar A Pure Meat Shop, Pizza Hut Delivery.
I still need to find
To sum up, I will submit: "Tpot, Chattanocge", "Liquid, Chattanooga", Muradabadi, Chattanooga" for day 5, "Burger's King, Chattanooga", "Basil Tree, Chattanooga "Sardar Pure Meat Shop, Chattanooga" for day 6, and "Pizza Eut Delivery, Chattanooga" for day 7.
For the accommddation part: The accommodation need to consider involves three parts: accommodation in Nashville from 2022-03-21 to 2022-03-22, in Knoxville from 2022-03-23 to 2022-03-24, in Chattanooga from 2022-03-25 to 2022-03-27. For the accommodation in Nashville from 2022-03-21 to 2022-03-22: The user requests private room, the accommodations filtered based on the eriterion are: Clean and large bedreom. in private house, Lovely room in heart of Williamsburg, FiDi Cozy room overlecking East River, Cozy bedroom close to Manhattan.
49
50
The user requests house that allow smoking, the accomnodations further Filtered based en the criterion are: Lovely room in heart of williamsburg, FiDi Cozy room overlooking East River, Cozy bedroom close to Manhattan. Since the stay is enly for two nights, the minimum nights for accommocttinn should be limited to Less than 3, and the accommodations further #iltered based on the criterion are: Lovely room in heart of Rilliamsburg, FiDi Cozy room
51
overlooking East River, Cozy bedroom close to Manhattan.
Among the filtered accomrodations, I should choose the with the lowest
price:
Lovely room in heart of Williamsburg has a maxinum occupancy of people and is priced at $61. Since we are 2 people, we need 1 room, the total price is $61 = $61.
54
FiDi Cozy reom overlooking East River has maximum occupancy of 5 people and is priced at $870. since we are people, we need 1 room, the total price is $870 $870.
Cozy bedroom close to Manhattan has maximum occupancy of 3 people and is priced at $576. Since we are 2 people, we need room, the total price is $576 $576.
56
Based on the calculations above, will submit: "Lovely room in heart of Williamsburg, Nashville".
57
For the accommodatien in Knoxville from 2022-03-23 to 2022-03-24:
58
The user requests private room, the accommodations that meet the criteria are: Cozy Private Room in Chinatown/ Lower East Side, The Diamond Roon, Light-filled Room in Renovated Apt, Private Room, Beautiful & Private Manhattan Room, Brooklyn sunny room 5 min to subway, Private 1 Bdrm Suite in Historic Brownstone, Charming bedroom with huge terrace in Greenpoint, Private large room near LGA airport with queen bed.
The user requests house that allow smoking, the accomnodations further filtered based en this criterion are: Cozy Private Room Chinatown/ Lower East Side, The Diamond Room, Light-filled Room in Renovated Apt, Private Room, Brooklyn Sunny room 5 min to subway, Private 1 Bdrm Suite in Historic Brownstone, Charming bedroom with huge terrace in Greenpoint, Private 1arge room near LGA ai airport with queen bed.
Since the stay is only for two nights, the minimum nights for further filtered
accommodati on should be limited to less than 3, and the accommodation Room in kenovated Apt, Private
based on the criterion are: The Diamond Room, highhtfflles Room, Brooklyn Sunny room 5 min to subway, Private 1 3drm Suite in Historic Brownstone, Charming bedroom with huge terrace in Greenpoint, Private large room near LGA airport with queen bed.
Among the filtered accomnodations. I should choose the one with the lowest
62
price:
The Diamond Room has maximam occupancy of people and is priced at $1008. Since are 2 people, we need room, the total price is $1008 2 $2016. Light-fille filled Room in Renovated Apt has a maximun occupancy of 64
people and is priced at $310. Since we are 2 people, we need 1 room, the total price is $310 * - = $310.
Private Room has maximum occupancy of people and is priced at $922. Since we are people, we need room, the total price is $922 $1844.
23

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Brooklyn sunny room min to subway has maximum occupancy of people and is priced at $793. Since we are 2 people, we need room, the total price is :793 = $793.
66
Private 1 Bdrr Suite in Historic Brownstone has maximum occupancy 2 people and is priced $479. Since are 2 people, need room, the $479.
cotal price is $479 Charming bedroom with huge terrace in Greenpoint has a maximum
68
occupancy of 1 people and is priced at $712. Since we are 2 people, we need 2 room, the total price is $712
$1424.
Private large room near LGA airport with queen bed has a maximum pocupancy of 1 people and is priced at $552. Since we are 2 people, we need room, the total price is $552 * 2 - $1104.
Based on the calculations above, will submit: "hight-filled Room in Renovated Apt, Knoxville", For the accommodation in Chattanooga from 2022-03-25 to 2022-03-27: The user requests private room, the accommodations filtered based on the eriterion are: Affordable Private Spacious Room in Brooklyn, Sunny roon-Pvte office in huge loft, Extra Cozy Room in Center of killiamsburg, Fort Greene Room, Cozy room in Bushwick- min to the city, Modern apartment w/ gorgeous view, Artsy Private in Fort Wyndham Midtown 45.
71
72
Greene Cumberland, Studio Deluxe
The user requests house that allow smoking, the accomnodations further filtered based on the criterion are: Affordable Private Spacious Room in Brooklyn, Sunny room+Pvte office in huge loft, Extra Cozy Room in Center of williamsburg, Fort Greene Room Cozy room in Bushwick- 15 min to the city, Modern apartment w/ gorgeous view, Artsy Private BR in Fort Greene Cumberland.
73
Since the stay is only for two nights, the minimum nighta for accommodation should be limited to less than 3, and the accommodations further filtered based on the criterion are: Affordable Private Spacious Room in Brooklyn, Extra Cozy Room in Center of Williamsburg, Fort Greene Room, Cozy room in Bushwick- 15 min to the city, Anong the filtered accomodaations, I should choose the one with the lowest 75
74
price:
Affordable Private Spacious Room in Brooklyn has maximum occupancy of 2 people and priced at $790. Since we are 2 people, we need room, the cotal price is $790 + 1 $790.
Extra Cozy Room in Center of Williamsburg has a maximum occupancy of people and is priced at $1033. Since we are people, we need 2 room, the total price is $1033 2 $2066.
77
Fort Greene Roem has maximum occupancy of people and is priced at $/22. Since we are 2 people, we need 2 room, the total price is $122 * 2 $1444. Cozy roem in Bushwick- 15 min to the city has a maximun occupancy of people and is priced at $933. Since are 2 people, we need 1 roon, the total price is $933 $933.
Based on the calculations above, will submit: "Affordable Private Spacious Room in Brooklyn, Chattanooga".
80
Blocksworld:
[Plan]
[tc get the blue block clear] can unstack the yellow block from top of the blue block The current state is: the orange block is on the table and not clear, the red block is en top of the orange block and not clear, the blue block is on top of the red block and clear, the yellow block is in hand and not clear. [to get the blue block on the table]
can put down the yellow block.
The current state is: the orange block is on the table and not clear, the
red block is en top of the orange block and not clear, the blue block is on top of the red block and clear, the yellow block is on the table and clear. I
unstack the blue block from on top of the red block. The current state is: the orange block is on the table and not clear, the
red block is on top of the orange block and clear, the blue block is in my hand and not clear, the yellew block is on the table and clear. I can put down the blue block.
The current state is: the orange block is on the table and not clear, the red block is on top of the orange block and clear, the blue block on the table and clear,
24

---

HyperTree Planning:
Enhancing LLM Reasoning via Hierarchical Thinking
the yellow block is on the table and clear.
[to get the orange block clear]
12
I can unstack the red block from on top of the orange block.
13
The current state is: the orange block is on the table and clear, the red block is in my hand and not clear, the blue block the table and clear, the yellow block is on the table and clear.
14
[to get the orange block en top of the blue block]
15
I can put down the red block.
16
The current state is: the orange block is the table and clear, the red block on the table and clear, the blue block on the table and clear, the yellow block is on the table and clear.
can pick up the crange block.
18
The current state is: the orange bloct is in my hand and not clear, the red block is the table and clear, the blue block the table and clear, the yellow block on the table and clear.
I can stack the orange block on top of the blue block. The current state is: the orange block is on top of the blue block and clear, the red block is the table and clear, the blue block the table and not clear, the yellow block on the table and clear. [to get the red block on top the orange block] I can pick up the red block.
20
21
22
23
The current state is: the orange block is on top of the blue block and clear, the red block is in my hand and not clear, the blue block the table and not elear, the yellew block is on the table and clear.
24
I can stack the red block on top of the orange block.
25
The current state is: the orange block is on top of the blue block and not clear, the red block is top of the orange block and clear, the blue block on the table and clear, the yellow block on the table and clear.
26
Mystery Blocksworld:
[Plan]
[to get Province object b becores True]
Since Harmony is True, Province object a is True, object a Craves object b is True, I can Feast object from object b. Province object Hamony becomes False
object Craves object b becomes False
Pain object a, Province object b becomes True. Harmony is False, the Pain object is a Province object b is True, object b Craves object object Craves object d Planet object is True. The subtask is achieved. Planet object beceres True] Since Harmony is False, the Pain object is succumb object Planet object a, Prevince object becomes True Harmony becomes Truc Pain object a becomes False.
10
11
[to get
12
14
15
16
Planet object a, Prevince object is True Province object b is True, object b Craves object c Province object e False Planet object is True.
19
20
Since Harmony is True, Province object b is True, object b Craves object Feast object b from object Province object b, object Craves object e becomes False
21
is True, can
22
Hamony becomes False
23
Pain object b, Province object a becomes True. Planet object a, Prevince object is True Province object a is True, object Craves object d Planet object is True.
24
25
27
Since Harmony is False, the Pain object is b, I can succumb objoct b. Planet object b, Prevince object b becomes True
28
29
Harmony becomes True Pain object b becomes False.
Harmony is True
52
25

---

HyperTree Planning:
Enhancing LLM Reasoning via Hierarchical Thinking
Planet object a, Prevince object is True Planet object b, Province object is True Province object с is True, object Craves object d Planet object is True.
33
34
35
36
The subtask is achieved.
[to get Province object d becores True]
58
Since Harmony is Truc, Province object с is Truc, object с craves object d is Truc, I can Feast object с from object d.
39
Province object
object Craves object d becomes False Hamony becomes False
41
Pain object e, Province object d becomes True. Planet object a, Prevince object is True Planet object b, Prevince object is True Planet object d, Prevince object is True. The subtask is achieved.
42
43
44
45
46
[to get Province object b becones True]
47
The subtask is achieved.
48
[to get
object d Crave object b] Since Harmony Planet object e, Prevince object becomes True Harmony becomes True
False,
Pain object c, can succumb object c.
50
51
52
Pain object c beccmes False.
Planet object a, Prevince object is True Planet object b, Prevince object is True Planet object c, Province object с is True Province object d, Planet object is True. Since Harmony is True, Province object d, Planet object is True, can
55
56
57
Attack object d.
Province object d, Planet object becomes False Harmony becomes False Pain object d beccmes True.
59
60
Planet object a, Prevince object is True
Planet object b, Prevince object is True
63
Planet object c, Province object с is True. since Harmony is False, the Pain object is d, Province object b is True, I can Overcome object d from object b.
64
65
object Craves object b becomes True Harmony becomes True Province object b, Pain object d becomes False. Planet object a, Prevince object is True Planet object is True
Province object
67
68
89
70
Planet object c, Prevince object is True Province object d is True, object d Craves object b. The subtask is achieved.
71
72
75
[tc get Province object a becores True]
74
The subtask is achieved.
75
[to get
Province object d becones True]
76
The subtask is achieved,
77
[to get
object Crave object d]
78
Since Harmony is True, Province object Planet object is True, can
Attack object
Province object c, Planet object becomes False Harmony becomes False Pain object a becones True.
80
81
Planet object a, Prevince object is True Planet object is True
84
Province object d is True, object d Craves object b. By [3.2], since Harmony is False, the Pain object is c, Province object d is Truc, I can Overcome object from. object d.
85
86
Province object c, object Craves object becomes True Harmony becomes True
88
Province object d, Pain object a becomes False. Planet object a, Prevince object is True Planet object is True
89
90
Province opject e True, object Craves object d
92
26

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
ject Craves object The subtask is achieved.
94
Trip Planning:
Plan|
For the Venice part:
I need to consider two parts: the dates for staying in Venice, and the
cransportation to the next city.
To consider the dates for staying in Venice:
The rest of the time is from day to day 7.
The required stay duration is days, and it is recessary to be Venice from day 5 to day 7.
So will submit: "**Day 5-7:** Visit Venice for 3 days".
To consider the transportation to plan for next:
According the flight information, Venice can lead to Berlin, so next we
will think about Herlin.
Since the stay in Berlin should be connected to the stay in Venice, it should either end day 5 or start day 7.
10
Since the rest of the time is from day 1 to day 5, the stay in Berlin
should end en day 5.
So the transportaicn I will submit is: "**Day Si** Fly from Berlin to
12
Venice."
For the Berlin part:
need to consider two parts: the dates for staying Berlin, and the cransportation to the next city.
14
To consider the dates for staying in Berlin:
15
The rest of the time is from day to day 5.
The required stay duration is days, and the stay in Berlin should end day 5, so necessary to be in Berlin from day to day 5.
So will submit: "++Day 2-5:** Visit Berlin for 4 days". To consider the transportation to plan for next: According to the flight information, Berlin Because Venice has already discussed it, so next we will talk about Tallinn next.
18
19
lead to Venice and Tallinn
20
Since the stay in Tallinn should be connected to the stay in Berlin, it should either end on day 2 or start on day 5.
21
Since the rest of the time is from day 1 to day 2, the stay in Tallinn
22
should end day 2. Berlin."
So the transportaicn will submit "** 2:** Fly from Tallinn to
23
For the Tallinn part:
24
I need to consider two parts: the dates for staying in Tallinn, and the transportation the next city.
Tо consider the dates for staying in Tallinn: The rest of the time is from day to day 2.
26
27
The required stay duration is 2 days, and the stay in Callian should end on day 2, it is necessary to be in Tallinn from day 1 to day 2.
28
Notice that day 1 arrive in Tallinn and visit. days".
the dates for staying in Tallinn, so need to
I will submit: "*.Day 1-2:4* Arriving in Tallinn and visit Tallinn for
30
To consider the transportation to plan for next:
Since the rest of the time is empty, the trip plan has been completed. Based on the above plan, I need to sort them in time, and use flights to connect these cities for trip plan.
52
33
According Herlin, and day 5 to day is Venice.
the chronological order, day 1 to day 2 is Tallinn, day 2 day 5 is
34
So will fly from Tallinn to Herlin day2, and fly from Berlin to Venice in
35
day5.
E.4. Examples of the Final Plan
TravelPlanner:
27

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Travel Plan:
Day 1:
Current City: from Houston to Nashville
Transportation: Flight Number: F3956409, from Houston to Nashville, Departure Time: 17:36,
Arrival Time: 19:12
Breakfast:
Attraction: Country Music Hall of Fanc and Museum, Nashville
Lunch:
Dinner: Twigly, Nashville
Accommodation: Lovely room in heart Williamsburg, Nashville
10
pay 2:
11
Current City: Nashville
Transportation:
Breakfast: Bablu Fast Food, Nashville
14
Attraction: Nashville Zoo at Grassmere, Nashville
15
Lunch: Kitchen King, Nashville
16
Dinner: Govinda's s Confectionery, Nashville
Accommodation: Lovely room in heart of williamsburg, Nashville
18
19
Day 3:
20
Current City: from Nashville to Xnexville
21
Transportation: taxi, from Nashville Knoxville, duration: hours 42 mins Breakfast: Biryani By Kilo, Knoxville
22
23
Attraction: World's Fair Park, Kacxville.
24
lunch: Open Kitchen, Knoxville Dinner: Chit Chat, Knoxville Accommodation: Light-filled
25
26
Renovated Apt, Knoxville
27
28
Day 4:
29
Current City: Knexville
Transportation:
Breakfast: Mamageto, Knoxville
32
Attraction: Knexville Muscum of Art, Knoxville
33
Lunch: La-Nawaab, Knoxville
54
Dinner:
Tandcori Tadka, Knoxville
Accommodation: Light-filled Room Renovated Apt, Knoxville
37
Day 5:
38
Current City: frem Knoxville to Chattanooga
39
Transportation: taxi, from Knoxville to Chattanooga, duration: 1 hour 41 mins Breakfast: Tpot, Chattanooga
41
Attraction: The Chattanooga Zoo at Warner Park, Chattanooga. Lunch: Liquid, Chattanooga
42
45
Dinner: Muradabadi, Chattanooga
44
Accommodation:
Affordable Private Spacious Room in Brooklyn, Chattanooga
45
46
Day 6:
47
Current City: Chattanooga
48
Transportation:
Breakfast: Burger's King, Chattancoga
Attraction: Rock City Gardens, Chattanooge. lunch: Basil Tree, Chattanooga
51
52
Dinner: Sardar A Pure Meat Shop, Chattanoogs Accommodation: Affordable Private Spacious Room in Brooklyn, Chattanooga
53
55
Day 7:
56
Current City: from Chattanooga to Houston
57
Transportation: taxi, from Chattanecga to Houston, duration: 11 hours 47 mins Breakfast: Pizza Aut Delivery, Chattanoogs
Attraction: Tennessee Aquarium, Chattanooga.
60
lunch:
61
Dinner:
62
Accommocation:
28

---

HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking
Blocksworld:
[PIAN]
unstack the yellow block from on top of the blue block
put down the yellow block
unstack the blue block from top of the red block
put down the blue block
unstack the red block from on top of the orange block put down the red block
pick up the crange block
stack the orange block on top of the blue block pick up the red block
stack the red block on top of the orange block [PLAN END]
11
12
Mystery Blocksworld:
[PLAN]
feast object from object b succumb object
feast object b from object succumb object b
feast object с from object d succumb object
attack object
overcome object d from object attack object
10
overcome object from object [PLAN END
Trip Planning:
Trip Plan:
++Day 1-2:** Arriving Tallinn and visit Tallinn for days.
Day 21** Fly from Tallinn to Berlin.
D*Da 2-5:** Visit Berlin for days.
Day 5:** Fly from Berlin to Venice.
Daya 5-7xxx Visit Venice for days.
29


Reviews:
[{"review_id": "77jBvBTHpr", "reviewer": "Reviewer_X7uh", "summary": "This paper proposes an autonomous planning framework called HyperTree Planning that involves (a) HyperTree Constrution, (b) Self-Guided Planning and (c) Plan Generation. It tackes the limitation of exisiting chain-of-thought and tree-of-thought on planning problems, for example, they focus on mathematical and logical reasoning. The main contribution comes from its HyperTree planning on top of existing Tree-of-though, with four steps: (1) Selection (2) Expansion (3) Construction and (4) Decision. Through experiments on travel planning benchmarks, it achieves state-of-the-art performanc and shows compatibility with multiple backbone LLMs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful, valuable, and positive comments. We address the concerns in detail as follows. We sincerely hope that our response could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n### Weakness 1\n>The novelty of the paper seems to be limited as a combination of ToT and HyperTree structured proposed in (Lample et al., 2022)\n\nThe novelty compared to \"ToT+HyperTree\":\n- **Different Motivation**: ToT focuses on exploring the search space through tree search strategies, addressing problems that require extensive trial and error to reach a solution. HyperTree Proof (Lample et al., 2022) is designed for an entirely different domain, aiming to find valid proof pathways by selecting appropriate proof methods. **In contrast, HTP is motivated by the key challenges in complex planning tasks**, such as **a lack of hierarchy, unmet constraints, and missing components**. We take inspiration from human problem-solving strategies and leverage the hypertree structure to structurally enable LLMs to perform hierarchical reasoning. Neither ToT nor HyperTree Proof can effectively address complex planning tasks.\n- **Innovative Usage of HyperTree Structure**: In HyperTree Proof, the hypertree structure is primarily used to **select the correct edges**, as each edge represents a different proof method, and the key goal is to complete the proof process by making the right selections at each layer. In contrast, HTP leverages the hypertree structure to **generate nodes**, enabling a divide-and-conquer strategy that decomposes complex planning tasks into hierarchical subtasks. **While both methods utilize hypertree structures, the modeling and usage are fundamentally different**. Therefore, HTP is not a simple adaptation or combination of existing methods.\n- **Explainability**: We explain **why HTP is particularly well-suited for solving complex planning tasks**, providing a solid rationale for its superior experimental performance. For more details, please refer to **Question 1 of reviewer rT6H**.\n- **Novel Planning Framework**: We innovatively model planning process using the hypertree structure, introducing the first hypertree-based reasoning algorithm and a corresponding fully autonomous planning framework.\n- **Flexibility and Scalability**: Our HTP framework is highly flexible and can be seamlessly integrated with mechanisms such as **self-reflection** and **process reward modeling**. We have conducted **supplementary experiments** on these mechanisms, as detailed in **Weakness 5 of reviewer zPJM** and **Question 1 of reviewer uus3**. This adaptability is crucial for the future development of **autonomous LLM agents**, highlighting HTP’s strong scalability and generalization capabilities.\n### Question 1\n>How is the probability pruning implemented?\n\nThe probabilities in this context refer to **confidence scores outputted by LLMs**, a technique adopted in several recent LLM-based works like RAP (Hao et al., 2023) and Self-DC (Wang et al., 2024). Specifically, to select hyperchains, we enumerate candidates and present them to the LLM in a dictionary format. **The LLM selects a hyperchain by outputting its index along with the corresponding logit, which we exponentiate to obtain the confidence probability**. Since our hypertree structure involves multi-layer selections, the probabilities for different layers within the same hyperchain follow the multiplication rule, ensuring that the total probability sum across all hyperchains remains normalized. This approach enables us to **select the top-n hyperchains with the highest probabilities efficiently while pruning lower-probability candidates**.\n### Question 2\n>Can HTP be used in Agent tasks? Especially with the function calling capability.\n\nWe will supplement **experiments on agent tasks** in the revised version of our paper, as detailed below.\n\nSpecifically, we select two widely adopted agent benchmarks, **WebShop and WebArena**, to evaluate HTP’s capability in function calling. As baselines, we choose ReAct, Reflexion, and LATS, which represent SOTA methods without incorporating prior knowledge. To ensure consistency with the baselines, we use GPT-4o and Gemini-1.5-Pro as the backbone models for WebShop and WebArena, respectively. Both datasets are evaluated using **Success Rate (SR)** as the metric.\n|Method|WebShop|WebArena|\n|-|:-:|:-:|\n|React|33.2|17.9|\n|Reflexion|39.8|20.2|\n|LATS|41.0|21.0|\n|**HTP**|**44.2**|**23.4**|\n\n**The results show that HTP outperforms SOTA methods on both datasets, demonstrating its strong performance in function calling scenarios**. Additionally, we provide an extended experiment of **HTP’s function calling performance on the TravelPlanner dataset**; please refer to **Question 2 of Reviewer rT6H**.", "claims_and_evidence": "HyperTree Reasoning shows superior performance on complex planning benchmarks, this claim could be questionable on whether it can be applied to other planning/agent tasks.", "methods_and_evaluation_criteria": "I think HyperTree Planning shows promising performance on trip planning tasks. While it is a concern whether this framework generalize to other agent tasks such as webArena. HyperTree Reasoning Paradigm:", "theoretical_claims": "There is no theory in the paper.", "experimental_designs_or_analyses": "Yes, I read the main experiment and ablation designs.", "relation_to_broader_scientific_literature": "This work might be applicable to other Agent datasets such as VisualAgent and WebArena.", "essential_references_not_discussed": "Not a concern.", "other_strengths_and_weaknesses": "The novelty of the paper seems to be limited as a combination of ToT and HyperTree structured proposed in (Lample et al., 2022)", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. How is the probability pruning implemented? I assume no probability is generated during the hypertree construction stage. \n\n2. Can HyperPlanning be used in Agent tasks? Especially with the function calling capablity.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g2FolOoXIA", "reviewer": "Reviewer_rT6H", "summary": "This paper introduces HyperTree Planning (HTP), a reasoning paradigm designed to improve complex planning tasks using hierarchical hypertree-structure.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful, valuable, and positive comments. We address the concerns in detail as follows. We sincerely hope that our response could properly address your concerns.\n### Weaknesses 1\n>It is beneficial to include further analyses in terms of efficiency metrics.\n\nWe will incorporate **an analysis of computational cost** in the revised version of our paper, as detailed below. Specifically, we evaluate the computational cost of CoT, RAP, and our HTP on the TravelPlanner dataset. Since open-source models currently exhibit suboptimal performance on TravelPlanner, we adopt GPT-4o as the backbone model. Our evaluation focuses on three commonly used efficiency metrics: **inference speed, token cost, and computational complexity**. Let $n$ denote the number of branches expanded at each step ($n\\leq 2$ in TravelPlanner), $l$ the average number of reasoning steps per chain, and $k$ the sampling trajectories in MCTS-based methods.\n|Model|Inference Speed (s)|Token Cost (in/out)|Computational Complexity|\n|:-:|:-:|:-:|:-:|\n|CoT|6.92|4328/641|$O(l)$|\n|RAP|41.94|5440/3374|$O(nkl)$|\n|**HTP**|**25.27**|**5562/963**|$O(nl)$|\n\nThe results indicate that **HTP achieves significantly lower computational costs across all three metrics compared to RAP**. This is because our top-down approach eliminates the need for MCTS, reducing the associated overhead.\n\nMoreover, **HTP does not introduce additional computational complexity in hierarchical reasoning** within the hyperchain structure. While the hyperchain structure increases the dimensionality of reasoning, it simultaneously shortens the average path length, allowing the overall computational efficiency to remain at the same level. Additionally, we provide **a comparison of API costs in Table 2 of our paper** for reference.\n\nBesides the experiments, we provide **additional discussions on computational cost**; please refer to **Weakness 1 of Reviewer uus3**.\n### Question 1\n>Why HTP excels existing tree-based methods in principle?\n\nAs illustrated in Figure 2, existing tree-based reasoning methods, such as ToT and RAP, fundamentally select a single reasoning chain from multiple candidate thought chains. **This single-chain structure inherently limits their ability to address complex, long-horizon planning tasks, as it lacks hierarchy and fails to handle multiple subtasks independently.** As a result, these methods often suffer from issues such as **unmet constraints and missing components**.\n\nIn contrast, **HTP replaces the single-chain structure with hyperchains, enabling hierarchical reasoning by allowing a single edge to connect multiple nodes**. In travel planning, where about 15 different constraints should be considered, this structure enables the model to clearly identify which subtask needs to be handled along each path, thereby guiding it to **reason about relevant constraints while avoiding unnecessary ones**. Furthermore, **by explicitly decomposing subtasks across multiple layers, each sub-task is represented as an independent node from the outset**. This ensures that **HTP enforces completeness**, preventing essential sub-goals from being omitted.\n### Question 2\n>Why the authors did not compare with ReAct in the main result of Table 1?\n\nAs mentioned in Appendix C.2, the TravelPlanner dataset consists of a two-stage mode (TS) and a sole-planning mode (SP). The TS mode retrieves target information via tool calls before reasoning (similar to ReAct), whereas the SP mode provides all information upfront, requiring the model to filter relevant details during reasoning. **As Table 1 reports baseline results under the SP mode, ReAct is not included**.\n\nTo provide a clearer comparison with ReAct, we have conducted **additional experiments evaluating HTP in the TS mode**, and these results will be included in the revised version of our paper. In HTP’s Self-Guided Planning module, instead of retrieving information from context, we modified it to retrieve information via tool calls. All methods use GPT-4o as the backbone model, and the evaluation metrics remain the same as in Table 1. **The results indicate that HTP in the TS mode is comparable to its performance in the SP mode and significantly outperforms ReAct.**\n||CPR (Micro)|CPR (Macro)|HCPR (Micro)|HCPR (Macro)|SR|\n|-|:-:|:-:|:-:|:-:|:-:|\n|React|79.4|8.33|7.14|5.00|1.67|\n|**HTP(TS)**|83.7|**33.9**|39.5|**28.9**|**18.3**|\n|**HTP(SP)**|87.2|**37.8**|44.3|**32.2**|**20.0**|\n> Why HyperTree Planning can work better than ReAct?\n\nReAct indeed follows an iterative decision-making process and performs decomposition implicitly through step-by-step reasoning. However, similar to ToT and RAP, **ReAct still follows a single-chain reasoning structure, leading to a lack of hierarchy, unmet constraints, and missing components**. In contrast, HTP overcomes these challenges by leveraging hyperchains to enable structured, hierarchical reasoning, ensuring comprehensive and constraint-aware planning.", "claims_and_evidence": "The core motivation is that existing reasoning methods (e.g., CoT, ToT) struggle with long-horizon, multi-constraint planning problems, such as travel planning, which require handling interdependent sub-tasks. The proposed framework aims to overcome the limitations of intensive human interventions as in existing planning agents. Key contributions in methodology:\n* HyperTree Reasoning Paradigm: it adopts a hypertree structure to model the reasoning process to perform hierarchical thinking. The proposed hypertree construction algorithm aligns well with the structured nature of planning problems.\n* Autonomous Planning Framework: leverages task-specific planning outlines to self-guide the planning process dynamically, reducing reliance on manually crafted in-context learning examples.", "methods_and_evaluation_criteria": "The proposed HTP framework introduced in this paper utilizes the divide-and-conquer strategy to construct and refine hypertree-based planning outlines and thus organize sub-tasks in a structured manner. It naturally models complex planning tasks. The iterative refinement strategy is also reasonable.", "theoretical_claims": "This is an empirical work, no theory results.", "experimental_designs_or_analyses": "Overall, the empirical studies show promising performance improvement on benchmark datasets compared to different baseline planning algorithms. \n\nHere are some questions:\n1. While a comparison with ReAct is provided in Appendice C.2, why the authors did not compare with ReAct in the main result of Table 1?", "relation_to_broader_scientific_literature": "Authors provide a hypertree-based planning framework for complex planning tasks. It can be helpful for LLM reasoning and agentic frameworks in practice.", "essential_references_not_discussed": "Main related work has been included.", "other_strengths_and_weaknesses": "While hypertree reasoning is conceptually appealing, its computational cost relative to existing planning strategies is unclear. It is beneficial to include further analyses in terms of efficiency metrics, e.g. inference speed, memory usage, computational complexity etc.", "other_comments_or_suggestions": "Please see above.", "questions_for_authors": "1. While I understand that HyperTree Planning differs from Tree of Thought and RAP by the fact that it constructs hypertree, I cannot fully grasp why the proposed HyperTree Planning excels existing tree-based methods in principle. Say, is it because hypertree structure can better handle planning constraints while ToT and RAP cannot etc. Can authors further comment and compare?\n\n2. Methodologically, why HyperTree Planning can work better than ReAct? ReAct is also able to break tasks into subtasks and iteratively making decisions based on evaluation results.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8wcy7xQpZz", "reviewer": "Reviewer_zPJM", "summary": "This paper concentrates on complex planning tasks, for instance, mathematical and logical reasoning. To alleviate the multiple challenges, extended reasoning steps, diverse constraints, and multiple distinct sub-tasks, they propose a HyperTree Planning (HTP) that is based on the divide-and-conquer strategy to split tasks into multiple distinct sub-tasks. Extensive experiments demonstrated the proposed method improved the accuracy of the TravelPlanner benchmark.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful, valuable, and positive comments. We address the concerns in detail as follows. We sincerely hope that our response could properly address your concerns.\n### Weakness 1\n>Do humans almost never make errors across multiple complex tasks?\n\nIn **TravelPlanner**, humans can achieve **near-perfect accuracy**. For PlanBench and Natural Plan, human performance data is unavailable. We estimate that humans can achieve **near-perfect accuracy in PlanBench**, as stacking blocks aligns well with human capabilities. In **Natural Plan**, we expect an overall success rate of **approximately 80%**, with errors occurring mainly on the most difficult tasks.\n### Weakness 2 & Weakness 4\n>provide some failure cases to analyze the limitations of current methods\n\nWe will incorporate **an analysis of bad cases** in our revised paper, as detailed below:\n- **LLMs struggle with complex single-step reasoning**. In TravelPlanner, given a table of candidate hotels (including hotel name, room type, etc.), the model is required to identify 'entire room' options. However, it often fails by missing correct options or selecting incorrect ones.\n- **LLMs lack human prior knowledge**. In TravelPlanner, humans naturally use strategies to stay within budget, such as choosing self-driving over flights, selecting the cheapest hotels and restaurants. However, models struggle to leverage such prior knowledge, resulting in **plans that exceed the budget**.\n- **HTP remains vulnerable to long-horizon errors**. In PlanBench, the model must track and update the environment state after each action. However, any mistake in state updating can propagate errors, leading to incorrect subsequent reasoning and actions.\n- **HTP lacks the capability for self-reflection and backtracking**. In Natural Plan, the model must determine a feasible multi-city route. While HTP outperforms baselines, it may struggle with constraint violations, like selecting consecutive cities without a direct connection. Humans typically backtrack and revise their decisions in such cases, whereas HTP lacks an inherent mechanism for such adjustments.\n>If existing methods remain a great gap between humans, why attributes to this pattern?\n\nA considerable gap remains between HTP and human-level planning, which can be mainly attributed to:\n- **Humans are adept at planning and adapting to complex constraints**, such as effortlessly filtering hotels based on multiple conditions.\n- **Humans leverage extensive prior knowledge beyond what is provided in the prompt**, which helps them make more informed, practical decisions (e.g., cost-saving strategies in travel planning).\n- **Humans are less prone to hallucinations**, making them more reliable for long-horizon planning.\n- **Humans can self-reflect and backtrack when necessary**, adjusting their decisions in the face of contradictions.\n### Weakness 3\n>Why HTP improve the performance compared to related works?\n\nPlease refer to **Question 1 of Reviewer rT6H**.\n### Weakness 5\n>How the future works utilize this work and any potential value in multiple real-world tasks?\n\nWe will incorporate **a discussion on future work and potential applications** in our revised paper, as detailed below:\n\n**First, HTP naturally integrates with self-reflection and backtracking techniques, making it particularly valuable for real-world tasks like meeting planning and calendar scheduling**. By replacing single-chain reasoning with a hierarchical hyperchain structure, HTP enhances reflection accuracy by **directly identifying and correcting errors without revisiting unrelated paths**. We conduct **a preliminary experiment** on the TravelPlanner dataset, using GPT-4o as the backbone model. We use a heuristic oracle to generate reflection signals and employ the simple cosine similarity metric to pinpoint specific erroneous paths, limiting reflections to 3 per plan. **Results show significant improvements with reflection, highlighting HTP's strong potential when integrated with reflection-based methods**. Future work can explore two directions: **(1) replacing the heuristic oracle with an LLM-powered self-reflection mechanism to enhance adaptability, and (2) refining the accuracy of error localization to further improve efficiency**.\n||CPR (Micro)|CPR (Macro)|HCPR (Micro)|HCPR (Macro)|SR|\n|-|:-:|:-:|:-:|:-:|:-:|\n|HTP|87.2|37.8|44.3|32.2|20.0|\n|**HTP+reflection**|**93.6**|**66.7**|**60.7**|**48.9**|**44.4**|\n\n**Second, HTP shows great potential in autonomous agent decision-making due to its scalability and adaptability**. To further explore this, we have added **two agent experiments**; please refer to **Question 2 of Reviewer X7uh**. Future work can explore how to **empower end-to-end agents with autonomous hierarchical thinking using HTP**.\n\n**Third, combining HTP with LLM-based heuristic process reward functions is a promising direction**. We have added **an experiment on this aspect**; please refer to **Question 1 of Reviewer uus3**.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. The method has comparatively less proof and no potential questions.", "experimental_designs_or_analyses": "Yes. They develop multiple experiments and adopt multiple baselines, planning strategies, in-context learning methods, and powerful LLMs to support the effectiveness of the proposed HTP.", "relation_to_broader_scientific_literature": "The earliest works begin with analogical reasoning, including CoT, and ToT. \nMost recently, the agent systems collaborate through structured processes to combat planning tasks. \nThe author proposes the existing limitations in complex task reasoning include concentrating on mathematical and logical reasoning that is ill-suited for planning questions, the performance depends on human-designed prompts, and the generalization across tasks hindered by human-designed intervention in autonomous agent methods. They then devise methods that combine ToT and HyperChain to solve these challenges.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths**\n\nThe paper is the first work to combine hypertree structure into a reasoning process.\n\nTo alleviate the fluctuation of human-designed prompts, they design an autonomous planning framework that self-guide the planning process without manual design.\n\nThey conduct amount of experiments to support the effectiveness of proposed methods.\n\n**Weakness**\n\nI am interested how the ability of humans in these involved benchmarks, Travel Planner, PlanBench, and Natural Plan. Whether humans almost not make errors across multiple complexity tasks?\n\nThese should provide some failure cases to analyze the limitations of current methods.\n\nThough they conduct a number of experiments to investigate the capability of proposed methods, the analysis mainly includes describing the result with explicit performance. There lack of deep analysis of why these methods improve the performance compared to related works. Furthermore, if existing methods remain a great gap between humans, why attributes to this pattern?\n\nThe author should discuss how the future works utilize this work and any potential value in multiple real-world tasks.\n\nIf the author provides a reasonable response, I will reconsider my ranking.", "other_comments_or_suggestions": "There lack of limitations and future work.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bSOqaycots", "reviewer": "Reviewer_uus3", "summary": "This paper proposes a tree-based planning strategy, called **HyperTree Planning (HTP)**, which utilizes a hypertree-structured planning framework. HTP adopts a divide-and-conquer approach, decomposing a complex goal into several sub-goals in a top-down manner. These sub-goals are further decomposed iteratively until they are indivisible. The authors define this process in four stages: selection, expansion, construction, and decision, which together form a hyper-tree structure for further planning. During the plan generation stage, HTP accesses knowledge bases to refine the plan outline, aiming to generate a comprehensive and detailed plan rather than just an outline. The experiments, covering three fundamental models and three widely-used planning benchmarks, demonstrate the effectiveness of HTP. Additionally, ablation studies further validate the proposed strategies.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful, valuable, and positive comments. We address the concerns in detail as follows. We sincerely hope that our response could properly address your concerns.\n### Weakness 1\n>discussion on cost concern and potential improvements.\n\nWe will incorporate **a discussion of computational cost** in the revised version of our paper, as detailed below:\n\n- The inference cost of HTP can be higher than conventional backbone models, primarily due to two factors: (1) **the computational cost introduced by multi-path reasoning** (i.e., tree search) and (2) **the hierarchical reasoning mechanism, which decomposes the original task into subproblems, leading to more detailed reasoning**.\n- **The impact of these factors varies across tasks**. In TravelPlanner, the additional cost mainly comes from the need for detailed reasoning to satisfy constraints (factor 2). In Natural Plan, where we need to find a unique solution through trial and error, tree search (factor 1) is the primary source of overhead.\n- Despite these additional costs, **HTP remains more computationally efficient than MCTS-based methods**. We have added additional experimental results and explanations on this aspect; please refer to **Weaknesses 1 of Reviewer rT6H**.\n- We propose two potential improvements: (1) **Using fine-tuned small models instead of large models during the hypertree construction stage**, which could reduce the computational burden; (2) **Predicting task complexity through meta-learning and dynamically adjusting hypertree parameters** (e.g., depth, width) during hypertree construction, allowing for more efficient resource allocation.\n### Weakness 2\n>Lack of bad case studies for future work\n\nWe will incorporate **an analysis of bad cases** in our revised paper, as detailed below:\n- **LLMs struggle with complex single-step reasoning**. In TravelPlanner, given a table of candidate hotels (including hotel name, room type, etc.), the model is required to identify 'entire room' options. However, it often fails by missing correct options or selecting incorrect ones.\n- **LLMs lack human prior knowledge**. In TravelPlanner, humans naturally use strategies to stay within budget, such as choosing self-driving over flights, selecting the cheapest hotels and restaurants. However, models struggle to leverage such prior knowledge, resulting in **plans that exceed the budget**.\n- **HTP remains vulnerable to long-horizon errors**. In PlanBench, the model must track and update the environment state after each action. However, any mistake in state updating can propagate errors, leading to incorrect subsequent reasoning and actions.\n- **HTP lacks the capability for self-reflection and backtracking**. In Natural Plan, the model must determine a feasible multi-city route. While HTP outperforms baselines, it may struggle with constraint violations, such as selecting consecutive cities without a direct connection. Humans typically backtrack and revise their decisions in such cases, whereas HTP lacks an inherent mechanism for such adjustments.\n\nBased on the analysis, we have added **a discussion on future work**; please refer to **Weakness 5 of Reviewer zPJM**.\n### Question 1\n>In the \"Selection\" stage, would it be more effective to use training-based process reward models or other model-based evaluators?\n\nWe absolutely agree that incorporating a reward-based approach could enhance decision accuracy, though it comes at the cost of some generalizability. To investigate this, **we conduct experiments on the Blocksworld task** from the PlanBench dataset, which is particularly challenging because it requires selecting the correct actions, making the **selection stage highly influential on overall performance**. We design two types of reward functions, and all methods use GPT-4o as the backbone model:\n- **Rule-based rewards**: Rewards explicitly defined based on predefined heuristics, providing structured guidance for action selection.\n- **LLM-based rewards**: Rewards generated dynamically by prompting LLMs to formulate heuristic functions, reducing the reliance on manual reward design. The rewards are further refined through an evolutionary algorithm, iteratively improving the effectiveness.\n\nOur results show that **even simple rule-based rewards can significantly improve model performance**. Moreover, the **LLM-generated heuristic rewards offer more fine-grained guidance while reducing the burden of manual reward engineering**. We believe this is a promising direction for future research.\n|Method|HTP|+Rule-based|+LLM-based|\n|-|:-:|:-:|:-:|\n|**Success Rate**|**54.7**|**59.7**|**71.2**|", "claims_and_evidence": "Yes, all the claims made in the submission are supported by experiments.", "methods_and_evaluation_criteria": "The proposed method makes sense, and the evaluation criteria are adopted from the official benchmarks' criteria.", "theoretical_claims": "There is no proof for a theoretical claim in this paper.", "experimental_designs_or_analyses": "I believe the experimental design is comprehensive and convincing. The authors validate the effectiveness of their proposed methodology across three foundational models and three planning benchmarks, comparing it to seven previous works. All the experiments demonstrate the superiority of their proposed method. Overall, the soundness and validity of the experiments in this paper are strong.", "relation_to_broader_scientific_literature": "This paper introduces a novel hypertree-based planning strategy that enhances the performance of LLMs on planning tasks. Both the comprehensive studies and additional analyses demonstrate the effectiveness of the proposed methodology. Furthermore, the authors show that the proposed HTP yields more significant performance improvements on tasks with longer reasoning chains, which is particularly impressive and strongly validates its promising future potential.", "essential_references_not_discussed": "The discussion of related work is sufficient, and the experiments cover the necessary baselines.", "other_strengths_and_weaknesses": "In my opinion, this paper is strong, and I have highlighted the strengths in the above parts. However, I do have some concerns regarding the strategy:\n\n1. **Cost concerns**: As shown in Table 2, the cost for TravelPlanner is nearly 3x higher compared to vanilla GPT-4 and Gemini-1.5-Pro, with the issue becoming even more prominent in PlanBench (\\~8x) and Natural Plan (\\~14x). While these costs are still lower than those of the o1-preview, the large cost disparity on the same foundation model remains a concern. I acknowledge that this is a common issue with all tree-based methodologies because of the huge search space, and I encourage the authors to include more discussion on this matter, as well as potential improvements.\n\n2. **Lack of bad case studies**: Another concern is the apparent lack of bad case studies. There is still a significant gap compared to the saturated performance on the three planning benchmarks. I wonder which stage(s) primarily contribute to the failure cases and why. Are these failures due to the current LLMs' inability to identify potential errors, or is it something else? A detailed analysis of these issues would benefit future work.\n\nBy the way, I believe the current version meets the standard for ICML, and I consider this a strong paper. However, it would benefit greatly from addressing the aforementioned concerns.", "other_comments_or_suggestions": "Please refer to the weaknesses mentioned in the last part.", "questions_for_authors": "1. In the \"Selection\" stage, the authors mention that they primarily rely on LLM-based evaluation, both for the selection of hyperchains and leaf nodes. Would it be more effective to use training-based process reward models or other model-based evaluators? While the current strategy is certainly more generalizable, could it be improved by incorporating such methods?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper reports a study on LLM planning, and in particular, it proposes to apply the hypertree structure to guide complex planning tasks for LLMs. This is a very important research area, and the proposed solution of hypertree planning provides a reasonable solution choice to the community. The reviewers acknowledge the importance and the contribution of the paper, and are satisfied by the authors' replies. Therefore, I would like to recommend acceptance to the paper.
Decision: Accept (poster)