# RoT: Enhancing Large Language Models with
Reflection on Search Trees

Wenyang Hui1, Chengyue Jiang1, Yan Wang, Kewei Tu1
1School of Information Science and Technology, ShanghaiTech
1Shanghai Engineering Research Center of Intelligent Vision and Imaging
{huiwy, tukw<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding Author

###### Abstract

Large language models (LLMs) have demonstrated impressive capability in
reasoning and planning when integrated with tree-search-based prompting
methods. However, since these methods ignore the previous search experiences,
they often make the same mistakes in the search process. To address this
issue, we introduce Reflection on search Trees (RoT), an LLM reflection
framework designed to improve the performance of tree-search-based prompting
methods. It uses a strong LLM to summarize guidelines from previous tree
search experiences to enhance the ability of a weak LLM. The guidelines are
instructions about solving this task through tree search which can prevent the
weak LLMs from making similar mistakes in the past search process. In
addition, we proposed a novel state selection method, which identifies the
critical information from historical search processes to help RoT generate
more specific and meaningful guidelines. In our extensive experiments, we find
that RoT significantly improves the performance of LLMs in reasoning or
planning tasks with various tree-search-based prompting methods (e.g., BFS and
MCTS). Non-tree-search-based prompting methods such as Chain-of-Thought (CoT)
can also benefit from RoT guidelines since RoT can provide task-specific
knowledge collected from the search experience. The code is available at
https://github.com/huiwy/reflection-on-trees.

##  1 Introduction

Recent research highlighted that tree-search-based prompting methods
significantly improve the models’ capability of reasoning and planning in
tasks that require multiple steps of formal reasoning or planning, such as
embodied planning (Hao et al., 2023), mathematical reasoning (Yao et al.,
2023) and dialogue policy planning (Yu et al., 2023).

These methods decompose the problem into multiple steps to solve each step
sequentially. In each step they try an action, leading to a state transition,
gradually approaching the correct answer. For instance, as depicted in Figure
1(a), Blocksworld (Valmeekam et al., 2023) is a task to manipulate the blocks
from the initial state to the goal state. Following RAP’s (Hao et al., 2023)
formulation of Blocksworld, the actions are ways to manipulate the blocks and
states are the current block configuration. Then, they use tree search methods
such as breadth-first search (BFS) to search for an optimal path of states and
actions that leads to the solution, with the assistance of LLMs. They employ
LLMs to generate available actions, predict states after applying an action,
and evaluate the states or actions (Figure 5).

However, since these methods do not learn from past failures, they often make
repeated mistakes, including incorrectly evaluating the actions, generating
actions leading to low outcomes, and failing to predict the next state. These
issues result in low accuracy and poor search efficiency, leading to the over-
exploration of the wrong actions (Chen et al., 2024b). To empower tree-search-
based prompting methods to learn from their search experiences, we introduce
Refection on search Trees (RoT), a framework designed to improve search
efficiency and accuracy by reflecting on previous tree search experiences. RoT
employs a strong LLM to reflect on the previous search process of a weak LLM
to get a natural language task-level guideline. This guideline is then used to
enhance the weak LLM’s capability of making the right decisions and
estimations during the subsequent search processes. To generate a better
guideline, we designed a critical information extraction mechanism to select
the most crucial states that significantly impact the outcomes from the
previous search trees. With guidelines, models can avoid repeating mistakes
and make better decisions.

We evaluated RoT on a variety of complex reasoning and planning tasks
including embodied planning in Blocksworld (Valmeekam et al., 2023),
mathematical reasoning in GSM8k (Cobbe et al., 2021), and dialogue policy
planning in CraigsListBargain (He et al., 2018). In our experiments, RoT
significantly improves the performance of various strong LLMs in these tasks
when using tree-search-based prompting methods such as BFS and MCTS. RoT also
outperforms the recently proposed strong reflection method LEAP Zhang et al.
(2024a) designed for non-tree-search-based methods especially when the problem
is hard. Non-tree-search-based prompting methods such as Chain-of-Thought
(CoT) (Wei et al., 2022; Kojima et al., 2022) and Self-Consistency (Wang et
al., 2023b) can also benefit from the guidelines generated by RoT since they
can provide task knowledge collected from the search experience. We also find
that among all the tasks, RoT has the greatest benefit to tasks that models
are not familiar with.

Figure 1: An illustration about tree-search-based prompting method in
Blocksworld. $a_{i}$ and $s_{i}$ denotes action and state at depth $i$. $v$ is
the estimated value of an action by the tree search algorithm (value
estimation in BFS, and average estimated value of children in MCTS).

##  2 Background

###  2.1 Tree Search Methods

Tree search methods such as BFS, A* search (Hart et al., 1968), and Monte
Carlo Tree Search (Kocsis & Szepesvári, 2006; Coulom, 2006) are used to search
a tree for an optimal state. A search tree $\mathcal{T}$ consists of states
$s$, actions $a$, state value estimations $V$, and actions value estimations
$Q$. Actions are transitions between states. Each action within a state is
associated with a value $Q(s,a)$ which estimates the quality of action $a$ in
state $s$. Additionally, each state is assigned a value $V(s)$ estimating the
quality of state $s$. Since in the deterministic setting, the incoming action
of a state is unique, we set $V(s^{\prime})$ to $Q(s,a)$ if taking action $a$
in state $s$ transitions to $s^{\prime}$. Consequently, the primary objective
of tree search methods is to identify a sequence of actions a that leads to
the state $s^{*}$ with the highest value $V(s^{*})$.

###  2.2 Tree-Search-Based Prompting Methods

Integrating tree-search methods with LLMs presents an intriguing approach to
identifying a series of reasoning steps leading to the correct solution. As
depicted in Figure 1(b), throughout the tree search process, the LLM can be
prompted to (1) generate the available actions $\\{a\\}$ within a state $s$,
(2) assess the value $Q^{\prime}(s,a)$ of taking action $a$ within state $s$,
and (3) predict the next state $s^{\prime}$ after taking action $a$ in state
$s$. With insights from the LLM, tree-search methods can find an effective
sequence of actions leading to a favorable outcome.

Figure 2: The RoT framework

##  3 Reflection on Search Trees

The framework of RoT is depicted in Figure 2. We use tree-search-based
prompting methods to construct the search trees. Then, as explained in Section
3.1 the important states where making wise decisions can greatly improve
future outcomes are selected from the generated search trees. Finally, the
guidelines are summarized from these decisions to improve the future search
process according to Section 3.2.

###  3.1 Important State Selection from the Search Tree

Figure 3: Important State Selection ($\lambda=0.1$). States marked are
selected.

We extract the most informative experiences from previous tree search
experiences by important state selection. A state is important if taking an
action $a$ within state $s$ leads to a great increase or decrease in the state
value $V(s^{\prime})$. Intuitively, making wise decisions within such states
can vastly improve tree search performance. Then through reflection on such
experiences, the model can learn to make better decisions and attain better
performance. Specifically, as depicted in Figure 3, given the search tree
$\mathcal{T}$, we calculate the importance score of state $s$ based on the
values of their children in the following way:

$\text{Importance}(s)=\max_{s^{\prime}\in children(s)}|V(s^{\prime})-V(s)|$

Then, a state $s$ is called important when $\text{Importance}(s)>\lambda$,
where $\lambda$ is a threshold. RoT also saves relevant information in the
search tree about the important states for better reflection. Specifically,
apart from the important state itself, RoT collects information about the
available actions, the next state corresponding to each action, and the values
of the next states.

###  3.2 Guideline Summarization

Based on the information collected in important state selection, RoT
summarizes a guideline to enhance future search performance with the
assistance of LLM. As described in Figure 4.1, for each important state, we
ask a strong LLM to contrastively reflect on all the actions and the
consequences of taking action. We prompt this LLM first to analyze the impact
of each action on the value of the next states, and then summarize a guideline
based on its analysis. Finally, the weaker LLM is given this guideline to
improve the tree search efficiency.

However, when presenting LLMs with information about all the important states
simultaneously, LLM often gets overwhelmed and fails to capture the details in
summarization, resulting in overly general guidelines. Consequently, we
separately generate guidelines from a single important state and then prompt
LLM to merge the guidelines into one comprehensive guideline (Figure 4.2). To
improve the search efficiency and quality in the future search process, RoT
appends the generated guidelines to a predefined location in the prompt used
to generate action, states, or estimate values. With the enhanced prompts,
LLMs can attain better performance in tree searches. Beyond enhancing search
performance, the summarized guidelines can augment non-tree-search-based
methods such as Chain-of-Thought (CoT) by providing LLMs with prior knowledge
about the task.

Figure 4: Guideline Summarization.

###  3.3 Iterative Improvement

Inspired by expert iteration (Anthony et al., 2017), an approach to further
enhance search performance is applying the RoT iteratively. This uses
previously generated guidelines to generate improved search trees and
summarizes an enhanced guideline based on the improved search tree and past
guidelines to prevent the mistakes that are hard to avoid.

Figure 5: Examples of BFS and MCTS.

##  4 Experiments

In this section, we evaluate the effectiveness of RoT on complex reasoning and
planning tasks by integrating it with two tree-search-based methods, breadth-
first search (BFS) and (Monte Carlo Tree Search) MCTS Kocsis & Szepesvári
(2006), and two non-tree-search-based methods, Chain of Thoughts (CoT) (Wei et
al., 2022) and CoT with self-consistency (Wang et al., 2023b). We focus on
analyzing the performance improvement on these prompting methods after
applying RoT summarized guidelines. Meanwhile, we also compare RoT with the
recent non-tree-search-based reflection method, LEAP (Zhang et al., 2024a).

| Method | Step 4 | Step 6 | Step 8 | Step 10
---|---|---|---|---|---
| Base | RoT | LEAP | Base | RoT | LEAP | Base | RoT | LEAP | Base | RoT | LEAP
phi-2 | CoT | 1.3 |  3.9 (+200.0%) | 1.7 | 0.0 | 0.0 (+0.0%) | 0.0 | 0.0 | 0.0 (+0.0%) | 0.0 | 0.0 | 0.0 (+0.0%) | 0.0
CoT-Pass@10 | 5.3 |  15.8 (+198.1%) | 13.2 | 1.4 | 1.4 (+0.0%) | 2.1 | 0.0 |  0.7 (+0.0%) | 0.0 | 0.0 | 0.0 (+0.0%) | 0.0
BFS(5) | 61.8 |  69.7 (+12.8%) | 67.1 | 25.5 | 29.0 (+13.7%) | 33.1 | 11.2 |  16.1 (+43.8%) | 14.0 | 5.8 |  8.7 (+50.0%) | 5.8
MCTS(1) | 30.3 |  36.8 (+21.5%) | 28.9 | 17.9 | 18.6 (+3.9%) | 22.8 | 4.2 |  6.3 (+50.0%) | 4.2 | 1.9 |  1.9 (+0.0%) | 1.9
MCTS(10) | 84.2 |  85.5 (+1.5%) | 80.3 | 46.9 |  55.2 (+17.7%) | 53.1 | 11.2 |  17.5 (+56.2%) | 14.7 | 2.9 |  3.9 (+34.5%) | 2.9
mistral-7b | CoT | 5.3 | 10.5 (+98.1%) | 10.9 | 3.4 |  6.2 (+82.4%) | 3.8 | 0.0 | 0.0 (+0.0%) | 0.0 | 0.0 | 1.0 (+0.0%) | 1.2
CoT-Pass@10 | 40.8 | 48.7 (+19.4%) | 55.3 | 24.1 | 21.4 (-11.2%) | 26.9 | 4.9 |  10.5 (+114.3%) | 9.0 | 7.8 |  11.7 (+50.0%) | 10.7
BFS(5) | 86.8 |  89.5 (+3.1%) | 89.5 | 64.1 | 61.4 (-4.2%) | 62.1 | 42.0 |  42.7 (+1.7%) | 42.0 | 32.0 |  33.0 (+3.1%) | 33.0
MCTS(1) | 59.2 |  61.8 (+4.4%) | 61.8 | 40.0 |  43.4 (+8.5%) | 41.4 | 14.5 |  24.5 (+69.0%) | 21.0 | 12.6 |  21.4 (+69.8%) | 18.4
MCTS(10) | 89.5 | 92.1 (+2.9%) | 94.7 | 76.6 | 76.0 (-0.8%) | 77.2 | 55.2 |  59.4 (+7.6%) | 58.0 | 29.1 |  34.0 (+16.8%) | 30.1
mixtral-8x7b | CoT | 9.2 |  18.4 (+100.0%) | 13.0 | 11.0 |  11.7 (+6.4%) | 9.4 | 2.1 |  4.9 (+133.3%) | 2.8 | 2.9 |  3.9 (+34.5%) | 3.3
CoT-Pass@10 | 63.2 |  71.1 (+12.5%) | 61.8 | 54.5 |  54.5 (+0.0%) | 53.1 | 17.5 |  29.4 (+68.0%) | 21.7 | 20.4 |  27.2 (+33.3%) | 26.2
BFS(5) | 92.1 |  93.4 (+1.4%) | 92.1 | 60.7 | 57.2 (-5.8%) | 54.5 | 33.6 |  40.6 (+20.8%) | 39.2 | 29.1 |  33.0 (+13.4%) | 32.0
MCTS(1) | 64.5 |  69.7 (+8.1%) | 67.1 | 41.9 |  42.8 (+2.1%) | 42.1 | 17.5 |  21.7 (+24.0%) | 20.3 | 16.5 |  22.3 (+35.2%) | 15.5
MCTS(10) | 88.2 |  89.5 (+7.4%) | 86.8 | 76.6 | 75.2 (-1.8%) | 75.2 | 51.7 |  54.5 (+5.4%) | 50.3 | 32.0 |  34.0 (+6.2%) | 29.1

Table 1: Partial Blocksworld Results. CoT-Pass(n) is the rate that at least
one correct solution in $n$ CoT generations. BFS(b) means the number of beams
in BFS is $b$. MCTS(n) denotes $n$ iterations are performed. Steps $k$ is the
minimum number of actions to solve this problem. A higher number of steps
indicates a harder problem. The full table is shown in Table 6.

We will first introduce the baseline methods used in our experiments. After
that, we introduce the tasks, experiment settings, and their main results.
Finally, we did ablation studies about important state selection and iterative
improvement. Due to the limited space, we show the experiments about the
iterative improvement of RoT in Appendix B.4.

###  4.1 Baselines

BFS explores the search tree by depth. As depicted in Figure 5(a), BFS expands
all the actions in each state in each depth to generate states of the next
depth iteratively until a depth limit is reached. Since exploring all actions
leads to exponential computational costs, beam BFS is adopted. Only actions in
the $b$ best states are expanded, where $b$ is the number of beams. The scores
of states are obtained by prompting the LLM to predict the score once.

MCTS is an efficient tree search method. As shown in Figure 5(b), it first
selects a promising state and action that scores the highest in exploration
and exploitation. Then it takes this action to expand a new state. Then it
evaluates the quality of this state and backpropagates the evaluation for a
more precise quality estimation of its ancestors. The value estimations of a
state and action are determined by the LLM’s estimation of itself and the
estimations propagated from its descendants through backpropagation.

CoT and CoT-SC are two widely used non-tree-search-based prompting methods.
CoT requires the model to generate a reasoning chain to improve the reasoning
ability. CoT-SC samples multiple reasoning paths and conducts a majority vote
to select the best answer.

LEAP is a reflection method designed for CoT. It uses a strong LLM to generate
guidelines based on comparisons between generated wrong answers and gold
answers in the trainset to prevent the model from making similar mistakes in
reasoning in the future.

###  4.2 Blocksworld

Blocksworld requires the agent to have a strong ability to plan and awareness
of the future consequences. The task involves manipulating stacks of blocks
into a goal state where the blocks in the stacks satisfy the desired
configuration. At each step, the agent can pick up a block on top of a stack
when the hand is empty, place the held block onto a stack of blocks, or put
the block onto the ground.

Task setup. We follow RAP (Hao et al., 2023)’s setup in tree search and CoT.
The states are natural language descriptions of block configurations, and
actions are block manipulations. Rules are used to generate the actions
within. After an action is taken, we use rules to get the next state. The
initial value estimation of actions is computed by normalized log
probabilities of each action provided by LLMs conditioned on the current
state. A search tree of Blocksworld is in Figure 5. The sample LLM input and
output are in Appendix B.1.

When performing RoT and LEAP, we generate 20 samples and summarize the
guidelines on these samples with gpt4 (OpenAI, 2023). We perform MCTS for 20
iterations to generate search experiences and set the threshold $\lambda$ to
$0.1$.

We use the minimum required steps to partition the test set. As the number of
steps increases, the complexity of the samples correspondingly increases. This
allows us to analyze the performance of our system on tasks with different
difficulties. We evaluate RoT on three LLMs: phi-2 (Li et al., 2023b), a 2.7B
model, mistral-7b (Jiang et al., 2023), a 7B model, and mixtral-8x7b (Jiang et
al., 2024), a 8x7B mixture of experts model. The specific model names or URLs
are listed in Appendix C.2

Results. As shown in Table 1, RoT significantly improves the accuracy of tree-
search-based methods and non-tree-search-based methods over baseline. Notably,
RoT demonstrates consistent performance improvements across a range of models.
Compared to LEAP, RoT attains better performance on average, as it summarizes
the guidelines based on important states. By reflecting on states, the LLM can
generate more specific guidelines, while LEAP reflects on the whole solution,
making the guidelines less specific and thus less helpful. By comparing the
results from different steps, the relative improvement from RoT gets larger as
the number of required steps gets larger. For instance, the average relative
improvement to the baseline of MCTS increases from $+2.2\%$ at step 2 to
$+27.1\%$ at step 8. This indicates RoT gets more effective when the task gets
harder.

###  4.3 GSM8k

GSM8k (Cobbe et al., 2021) is a math word problem dataset, where each problem
consists of a description and a final question asks for the value of a
quantity. To solve the problems, the model should have a good ability for
mathematical reasoning and arithmetic calculations.

Task setup. Also following RAP, we solve the problems by recursively
decomposing them into subquestions and then answering them sequentially. After
the number of subquestions reaches the limit or the LLM thinks it can answer
the whole question, it derives the final answer based on all the subquestions
and subanswers. Therefore, we define the states as subanswers, and actions as
subquestions. When expanding a state, we ask LLMs to generate a few
subquestions as the actions of the current state. The initial value estimation
of actions is computed by the normalized probability that LLM answers “Yes”
compared to answering “No” when asked whether this subquestion is useful in
the current state.

Like RoT in Blocksworld, we perform MCTS for 20 iterations and BFS with beam
size $20$ on 40 samples in the train set, to generate the tree search
experiences. We set the threshold $\lambda$ to $0.1$, and still use gpt-4 for
guideline generation in both RoT and LEAP. The LLMs evaluated in GSM8k are the
same as those in Blocksworld: phi-2, mistral-7b, and mixtral-8x7b.

Method | phi-2 | mistral-7b | mixtral-8x7b
---|---|---|---
| Base | RoT | LEAP | Base | RoT | LEAP | Base | RoT | LEAP
CoT | 48.1 |  48.1 $(+0.0\%)$ | 44.4 | 31.2 | 31.8  $(+1.9\%)$ | 32.4 | 48.7 | 50.2  $(+3.1\%)$ | 51.4
CoT-SC(10) | 66.1 | 64.2  $(-2.9\%)$ | 66.2 | 49.4 |  50.3 $(+1.8\%)$ | 49.5 | 69.1 | 71.1  $(+2.9\%)$ | 72.7
BFS(5) | 54.4 |  55.8 $(+2.6\%)$ | 51.0 | 46.1 |  48.2 $(+4.6\%)$ | 46.4 | 68.0 | 66.7  $(-2.0\%)$ | 67.1
MCTS(1) | 51.1 |  53.5 $(+4.7\%)$ | 50.7 | 42.4 |  47.3 $(+11.6\%)$ | 44.8 | 65.4 |  66.6 $(+1.8\%)$ | 65.7
MCTS(10) | 61.9 |  62.4 $(+0.8\%)$ | 60.6 | 55.5 |  58.9 $(+6.1\%)$ | 56.0 | 77.4 |  79.2 $(+2.3\%)$ | 75.0

Table 2: GSM8K Results.

Model | Method | Encourage Profit | Encourage Agree.
---|---|---|---
Profit$\uparrow$ | Agree.$-$ | Utility$\uparrow$ | Profit$\uparrow$ | Agree.$\uparrow$ | Utility$\uparrow$
mixtral | CoT | -0.72 | 0.89 | -0.64 | -0.72 | 0.89 | -0.64
RoT-CoT | -0.19 | 1.0 | -0.19 | -0.24 | 1.0 | -0.24
2-8  | MCTS(8) | -0.15 | 1.0 | -0.15 | 0.11 | 1.0 | 0.11
|  RoT-MCTS(8) | 0.03 | 1.0 | 0.03 | -0.17 | 1.0 | -0.17
chatgpt | CoT | -0.06 | 0.83 | -0.05 | -0.06 | 0.83 | -0.06
RoT-CoT | 0.80 | 0.72 | 0.58 | 0.43 | 1.0 | 0.43
2-8  | MCTS(8) | 0.16 | 0.83 | 0.13 | 0.26 | 1.0 | 0.26
|  RoT-MCTS(8) | 0.75 | 0.94 | 0.71 | 0.52 | 1.0 | 0.52
gpt-4 | CoT | -0.46 | 1.0 | -0.46 | -0.46 | 1.0 | -0.46
RoT-CoT | 0.20 | 0.78 | 0.17 | 0.12 | 0.89 | 0.11
2-8  | MCTS(8) | 0.20 | 1.0 | 0.20 | -0.06 | 1.0 | -0.06
|  RoT-MCTS(8) | 0.67 | 0.56 | 0.38 | 0.59 | 1.0 | 0.59

Table 3: Results on CraigslistBargain

Results. As shown in Table 2, RoT improves the accuracy of various LLMs over
baselines. Compared to the non-tree-search-based reflection method, LEAP, RoT
can achieve similar performances in CoT and CoT-SC(10), and obtain much better
performance in tree-search-based methods. However, We found that the
improvement is less significant than in Blocksworld. One reason is that
performing arithmetic calculations accurately is also required to solve the
problem, while the guidelines cannot enhance such ability.

###  4.4 CraigslistBargain

CraigslistBargain (He et al., 2018) is about bargaining between a buyer and a
seller over an item. Each sample consists of the item’s description, the
buyer’s ideal price $p_{b}$, and the seller’s ideal deal price $p_{s}$. The
buyer aims to buy the item at a lower price, while the seller aims at the
opposite. However, they may also have a common goal of reaching an agreement.
To achieve higher benefits and agreement, a model should be able to compose a
good plan to persuade the opponent to adjust their prices. An example is in
Figure 7.

Task setup. We define the state as the dialogue history and the action as the
concept of the next response to the opponent. When expanding a state, the
actions are generated by LLMs. The values of actions are evaluated by roll-
out, which requires the current participant to complete the dialogue by both
acting as the seller and the buyer. The value of a roll-out is given based on
the deal’s success and the deal price. Unlike Blocksworld and GSM8k, where the
model has full control over transitions between states, the transition in
negotiation is also affected by the component. Running a tree search can only
get a good action within the current state, instead of a path to the best
state. Therefore, the negotiation needs to be finished by multiple rounds of
MCTS. Each round involves searching for effective persuasion and transitioning
to a new state based on the response from the counterpart.

For RoT, we perform MCTS for 16 iterations on 2 samples to get the experiences
and set the threshold $\lambda$ to $0.1$. We use gpt-4 to summarize the
guidelines. In CraigslistBargain, CoT inquires LLMs to determine an action and
generate the response given this action. We evaluate methods as the role of
the seller. Since dialogue does not contain a gold answer, we cannot evaluate
CoT-SC and LEAP. BFS is also not evaluated due to limited API resources.

We employ proft and utility to measure how good a successful deal is. Profit
from the seller’s perspective is defined as
$\text{Profit}(p)=2\cdot\frac{p-(p_{s}+p_{b})}{p_{s}-p_{b}},$ where $p$ is the
price of a successful deal. This metric provides a linear mapping of the deal
price $p$, yielding a value of $-1$ when $p=p_{b}$ and $1$ when $p=p_{s}$. In
our experimental results, the reported profit is the average profit of
successful deals, while the utility is the average profit of all deals, where
the profit of an unsuccessful deal is set to 0. Moreover, we use profit in the
reward of a dialogue. The reward is defined as $l_{penalty}$ if the deal is
not successful and Profit$(p)$ if the deal is successful.

In our prior experiments, we observed that without penalizing the seller for
unsuccessful deals, it tends to insist on a high price, which leads to high
profit but frequent failures in bargains. To address this, we introduce a
penalty term, $l_{penalty}$ to control the extent of punishment of an
unsuccessful deal. In experiments, we explore two settings, encouraging profit
and encouraging agreement, where $l_{penalty}$ is set to $0$ and $1$
respectively.

Similar to the findings from Fu et al. (2023), we observe that smaller LLMs,
such as phi-2 cannot bargain successfully, as they are unaware of the changing
prices. Therefore, we evaluate the framework with larger models including
mixtral-7x8b, chatgpt and gpt-4 (OpenAI, 2023). We use gpt-4 as the in all
experiments buyer. We evaluate 18 samples when using mixtral-8x7b or chatgpt
as the seller and 9 samples when using gpt-4 as the seller.

Results. The results displayed in Table 3 demonstrate that RoT significantly
improves the utilities across most settings. When encouraging the seller to
maximize its profit, RoT shows an average absolute profit improvement of
$0.55$ while potentially sacrificing some agreement. In settings where
agreement is also prioritized, RoT has an average absolute profit improvement
of $0.36$ without any compromise in agreement. We surprisingly observe that
RoT enables the performance of CoT to match or even surpass that of MCTS. This
could be attributed to the guidelines providing models with detailed
instructions about responding to the opponent’s behavior, reducing the
necessity to search for an optimal response. Notably, RoT demonstrates its
most impressive performance in CraigslistBargin compared to Blocksworld and
GSM8k. One explanation could be that LLMs are less familiar with bargaining,
as they are trained not to exhibit overly aggressive behavior, thus making
them more inclined to accommodate the opponent’s demands. With the guidelines,
models can learn to be aggressive and thus highlight the item’s value when the
opponent wants a lower price instead of directly lowering the price, which
leads to higher utility.

###  4.5 Search Efficiency Analysis

Model | Method | Step 2 | Step 4 | Step 6 | Step 8 | Step 10
---|---|---|---|---|---|---
phi-2 | MCTS | 75.6 | 55.8 | 27.2 | 6.0 | 1.9
RoT-MCTS | 74.7 | 59.1 | 33.1 | 9.7 | 2.0
(-1.1%) | (+5.9%) | (+21.7%) | (+61.7%) | (+5.3%)
mistral-7b | MCTS | 77.7 | 76.5 | 57.7 | 30.4 | 16.2
RoT-MCTS | 76.3 | 79.8 | 58.1 | 37.6 | 22.3
(-1.8%) | (+4.3%) | (+7.0%) | (+23.7%) | (+37.7%)
mixtral-8x7b | MCTS | 82.1 | 80.3 | 58.0 | 29.5 | 20.3
RoT-MCTS | 82.7 | 85.1 | 56.7 | 34.4 | 24.1
(+0.7%) | (+6.0%) | - (+3.3%) | (+16.6%) | (+18.7%)

Table 4: AUC of Blocksworld.

Figure 6: AUC on the step-6 split of Blocksworld using phi-2.

To demonstrate the efficacy of our framework in enhancing search efficiency,
we evaluate RoT by area under the iteration-accuracy curve (AUC) of MCTS. As
shown in Figure 6, we vary the number of MCTS iterations from 1 to 10 and
calculate the area within 10 iterations. A higher AUC indicates that the
method can achieve higher accuracy within fewer MCTS iterations. We access RoT
on Blocksworld and GSM8k, as we can evaluate MCTS with a single round of tree
search. As shown in Table 4, RoT can improve the value of AUC, which means
this framework can achieve a better trade-off between search efficiency and
accuracy. Results show that the improvement of RoT is more significant when
the task gets harder.

###  4.6 Important State Selection

To prove the efficacy of important state selection, we experiment with the
impact of reflection targets on the performance of tree searches in GSM8k. We
tried MCTS without guidelines, with guidelines summarized from problem-only
samples, all experiences, and random states in the search tree. We also change
the threshold $\lambda$ to adjust the quantity and quality of the selected
states to inspect its impact on tree search.

Method | No. States | Accuracy
---|---|---
MCTS(1) | - | 42.4
_\+ problem samples_ | - | 44.7
_\+ all experience_ | 538 | 45.0
_\+ random states_ | 219 | 44.2
_\+ imp. states ( $\lambda=-0.001$)_ | 340 | 46.2
_\+ imp. states ( $\lambda=0.5$)_ | 53 | 45.6
_\+ imp. states ( $\lambda=0.1$)_ | 242 | 47.3

Table 5: Number of selected decisions and performance of mistral-7b on GSM8k
when employing different selection mechanism for reflection.

As shown in Table 5, MCTS can benefit from guidelines summarized from the
problem samples, since an LLM can give a guideline based on its prior
knowledge. When reflecting on the important states, the performance of MCTS
can be further improved. We list part of the summarized guidelines in Table 8.
Through observation, we observe that with important state selection, LLMs can
summarize more specific guidelines which improve value estimation and next-
state prediction of future searches.

##  5 Related Works

###  5.1 Search-based LLM planning and reasoning

Planning and reasoning tasks typically require a model to make deliberate
decisions while considering future consequences. However, naive input-output-
based prompting methods cannot make decisions with consideration about the
future, leading to poor performance in complex tasks that require multiple
steps of reasoning and planning(Valmeekam et al., 2023; Li et al., 2023a;
Suzgun et al., 2023). Given that search methods can effectively consider
future outcomes by exploration and backtracking, they have become widely
adopted to enhance LLM’s planning and reasoning abilities. In an initial
effort, self-consistency (Wang et al., 2023b) conducts parallel searches
across multiple chains of thoughts and conveys a majority vote to determine
the final result. However, since each search process is done individually, the
same reasoning steps may be explored multiple times in the search process,
resulting in inefficiency. As tree searches can effectively avoid revisiting
the sample reasoning process, various tree-search-based prompting methods are
proposed to further enhance the model’s reasoning and planning ability. For
example, tree-of-thoughts (Yao et al., 2023) applies breadth-first search and
depth-first search in game planning and mathematical reasoning. Other methods
employ Monte Carlo Tree Search (MCTS) to enhance reasoning and planning in
various tasks including code generation (Zhang et al., 2023; Yang et al.,
2023a), dialogue policy planning (Yu et al., 2023), game planning (Yao et al.,
2023), and mathematical reasoning (Yao et al., 2023; Hao et al., 2023). Zhuang
et al. (2024) propose to use A* in tool agent and mathematical reasoning.
These methods usually rely on LLMs to generate the action, estimate the values
of actions, and predict the next state given an action, which controls the
exploration process of tree search. However, by investigating the above tree-
search-based prompting methods, Chen et al. (2024b) discovers that the
accuracy of value estimation is important to the tree search performance while
LLM-based value estimation is unreliable. In RoT, the reflected guidelines can
make the value estimation more accurate to achieve better tree searches.

###  5.2 Reflection

Reflection, as seen in methods such as Self-Refine (Madaan et al., 2023) is a
method for enhancing models’ ability at inference time by refining responses
based on feedback. Previous methods primarily focus on refining responses
based on a single feedback (Madaan et al., 2023; Chen et al., 2023) or
contrast between multiple models (Du et al., 2023; Zhang et al., 2024b).
Although effective, these methods typically concentrate on refining the
current sample while discarding the historical reflections, resulting in the
loss of past experiences. Consequently, the model cannot form a comprehensive
understanding of this task. To address this limitation, various studies
propose methods to enhance models’ ability by refining policy or prompt based
on task-level reflections. ProTeGi (Pryzant et al., 2023) and PromptAgent
(Wang et al., 2023a) optimize the prompt by search algorithms. TRAN (Yang et
al., 2023b), Grimoire (Chen et al., 2024a), and LEAP (Zhang et al., 2024a) use
guidelines summarized from good or bad generation results to guide the future
generation. In our proposed method, we enhance the models’ ability by refining
the LLM-assisted tree search process with reflection on tree search
experiences across various samples.

##  6 Conclusion

We propose a framework RoT, which prevents the model from making mistakes
repeatedly by reflecting on the previous tree search experiences. RoT improves
the accuracy and efficiency of LLM tree search by a guideline reflected from
previous search experiences. We show that RoT is also beneficial to non-tree-
search-based prompting methods including BFS and MCTS by providing models with
better knowledge prior. Experiments demonstrate that RoT can significantly
enhance the performance of LLM prompting methods, especially for tree-search-
based prompting methods.

## References

  * Anthony et al. (2017) Thomas Anthony, Zheng Tian, and David Barber.  Thinking fast and slow with deep learning and tree search.  _Advances in neural information processing systems_ , 30, 2017.
  * Chen et al. (2024a) Ding Chen, Shichao Song, Qingchen Yu, Zhiyu Li, Wenjin Wang, Feiyu Xiong, and Bo Tang.  Grimoire is all you need for enhancing large language models.  _CoRR_ , abs/2401.03385, 2024a.  doi: 10.48550/ARXIV.2401.03385.  URL https://doi.org/10.48550/arXiv.2401.03385.
  * Chen et al. (2023) Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou.  Teaching large language models to self-debug.  _CoRR_ , abs/2304.05128, 2023.  doi: 10.48550/ARXIV.2304.05128.  URL https://doi.org/10.48550/arXiv.2304.05128.
  * Chen et al. (2024b) Ziru Chen, Michael White, Raymond Mooney, Ali Payani, Yu Su, and Huan Sun.  When is tree search useful for llm planning? it depends on the discriminator.  2024b.  URL https://api.semanticscholar.org/CorpusID:267740392.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems.  _CoRR_ , abs/2110.14168, 2021.  URL https://arxiv.org/abs/2110.14168.
  * Coulom (2006) Rémi Coulom.  Efficient selectivity and backup operators in monte-carlo tree search.  In H. Jaap van den Herik, Paolo Ciancarini, and H. H. L. M. Donkers (eds.), _Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers_ , volume 4630 of _Lecture Notes in Computer Science_ , pp. 72–83. Springer, 2006.  doi: 10.1007/978-3-540-75538-8\\_7.  URL https://doi.org/10.1007/978-3-540-75538-8_7.
  * Du et al. (2023) Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch.  Improving factuality and reasoning in language models through multiagent debate.  _CoRR_ , abs/2305.14325, 2023.  doi: 10.48550/ARXIV.2305.14325.  URL https://doi.org/10.48550/arXiv.2305.14325.
  * Fu et al. (2023) Yao Fu, Hao Peng, Tushar Khot, and Mirella Lapata.  Improving language model negotiation with self-play and in-context learning from AI feedback.  _CoRR_ , abs/2305.10142, 2023.  doi: 10.48550/ARXIV.2305.10142.  URL https://doi.org/10.48550/arXiv.2305.10142.
  * Hao et al. (2023) Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu.  Reasoning with language model is planning with world model.  In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023_ , pp. 8154–8173. Association for Computational Linguistics, 2023.  URL https://aclanthology.org/2023.emnlp-main.507.
  * Hart et al. (1968) Peter E. Hart, Nils J. Nilsson, and Bertram Raphael.  A formal basis for the heuristic determination of minimum cost paths.  _IEEE Trans. Syst. Sci. Cybern._ , 4(2):100–107, 1968.  doi: 10.1109/TSSC.1968.300136.  URL https://doi.org/10.1109/TSSC.1968.300136.
  * He et al. (2018) He He, Derek Chen, Anusha Balakrishnan, and Percy Liang.  Decoupling strategy and generation in negotiation dialogues.  In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun’ichi Tsujii (eds.), _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018_ , pp. 2333–2343. Association for Computational Linguistics, 2018.  doi: 10.18653/V1/D18-1256.  URL https://doi.org/10.18653/v1/d18-1256.
  * Jiang et al. (2023) Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de Las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mistral 7b.  _CoRR_ , abs/2310.06825, 2023.  doi: 10.48550/ARXIV.2310.06825.  URL https://doi.org/10.48550/arXiv.2310.06825.
  * Jiang et al. (2024) Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de Las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mixtral of experts.  _CoRR_ , abs/2401.04088, 2024.  doi: 10.48550/ARXIV.2401.04088.  URL https://doi.org/10.48550/arXiv.2401.04088.
  * Kocsis & Szepesvári (2006) Levente Kocsis and Csaba Szepesvári.  Bandit based monte-carlo planning.  In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), _Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18-22, 2006, Proceedings_ , volume 4212 of _Lecture Notes in Computer Science_ , pp. 282–293. Springer, 2006.  doi: 10.1007/11871842\\_29.  URL https://doi.org/10.1007/11871842_29.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa.  Large language models are zero-shot reasoners.  In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022.  URL http://papers.nips.cc/paper_files/paper/2022/hash/8bb0d291acd4acf06ef112099c16f326-Abstract-Conference.html.
  * Li et al. (2023a) Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen.  Making language models better reasoners with step-aware verifier.  In Anna Rogers, Jordan L. Boyd-Graber, and Naoaki Okazaki (eds.), _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023_ , pp. 5315–5333. Association for Computational Linguistics, 2023a.  doi: 10.18653/V1/2023.ACL-LONG.291.  URL https://doi.org/10.18653/v1/2023.acl-long.291.
  * Li et al. (2023b) Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee.  Textbooks are all you need ii: phi-1.5 technical report.  _arXiv preprint arXiv:2309.05463_ , 2023b.
  * Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark.  Self-refine: Iterative refinement with self-feedback.  _CoRR_ , abs/2303.17651, 2023.  doi: 10.48550/ARXIV.2303.17651.  URL https://doi.org/10.48550/arXiv.2303.17651.
  * OpenAI (2023) OpenAI.  GPT-4 technical report.  _CoRR_ , abs/2303.08774, 2023.  doi: 10.48550/ARXIV.2303.08774.  URL https://doi.org/10.48550/arXiv.2303.08774.
  * Pryzant et al. (2023) Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng.  Automatic prompt optimization with "gradient descent" and beam search.  In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023_ , pp. 7957–7968. Association for Computational Linguistics, 2023.  URL https://aclanthology.org/2023.emnlp-main.494.
  * Suzgun et al. (2023) Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V. Le, Ed H. Chi, Denny Zhou, and Jason Wei.  Challenging big-bench tasks and whether chain-of-thought can solve them.  In Anna Rogers, Jordan L. Boyd-Graber, and Naoaki Okazaki (eds.), _Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, July 9-14, 2023_ , pp. 13003–13051. Association for Computational Linguistics, 2023.  doi: 10.18653/V1/2023.FINDINGS-ACL.824.  URL https://doi.org/10.18653/v1/2023.findings-acl.824.
  * Valmeekam et al. (2023) Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati.  On the planning abilities of large language models - a critical investigation.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=X6dEqXIsEW.
  * Wang et al. (2023a) Xinyuan Wang, Chenxi Li, Zhen Wang, Fan Bai, Haotian Luo, Jiayou Zhang, Nebojsa Jojic, Eric P. Xing, and Zhiting Hu.  Promptagent: Strategic planning with language models enables expert-level prompt optimization.  _CoRR_ , abs/2310.16427, 2023a.  doi: 10.48550/ARXIV.2310.16427.  URL https://doi.org/10.48550/arXiv.2310.16427.
  * Wang et al. (2023b) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.  Self-consistency improves chain of thought reasoning in language models.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023b.  URL https://openreview.net/pdf?id=1PL1NIMMrw.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou.  Chain-of-thought prompting elicits reasoning in large language models.  In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022.  URL http://papers.nips.cc/paper_files/paper/2022/hash/9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html.
  * Yang et al. (2023a) John Yang, Akshara Prabhakar, Karthik R Narasimhan, and Shunyu Yao.  Intercode: Standardizing and benchmarking interactive coding with execution feedback.  In _Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track_ , 2023a.  URL https://openreview.net/forum?id=fvKaLF1ns8.
  * Yang et al. (2023b) Zeyuan Yang, Peng Li, and Yang Liu.  Failures pave the way: Enhancing large language models through tuning-free rule accumulation.  In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023_ , pp. 1751–1777. Association for Computational Linguistics, 2023b.  URL https://aclanthology.org/2023.emnlp-main.109.
  * Yao et al. (2023) Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan.  Tree of thoughts: Deliberate problem solving with large language models.  _CoRR_ , abs/2305.10601, 2023.  doi: 10.48550/ARXIV.2305.10601.  URL https://doi.org/10.48550/arXiv.2305.10601.
  * Yu et al. (2023) Xiao Yu, Maximillian Chen, and Zhou Yu.  Prompt-based monte-carlo tree search for goal-oriented dialogue policy planning.  In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023_ , pp. 7101–7125. Association for Computational Linguistics, 2023.  URL https://aclanthology.org/2023.emnlp-main.439.
  * Zhang et al. (2023) Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan.  Planning with large language models for code generation.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.  URL https://openreview.net/pdf?id=Lr8cOOtYbfL.
  * Zhang et al. (2024a) Tianjun Zhang, Aman Madaan, Luyu Gao, Steven Zheng, Swaroop Mishra, Yiming Yang, Niket Tandon, and Uri Alon.  In-context principle learning from mistakes, 2024a.
  * Zhang et al. (2024b) Wenqi Zhang, Yongliang Shen, Linjuan Wu, Qiuying Peng, Jun Wang, Yueting Zhuang, and Weiming Lu.  Self-contrast: Better reflection through inconsistent solving perspectives.  _CoRR_ , abs/2401.02009, 2024b.  doi: 10.48550/ARXIV.2401.02009.  URL https://doi.org/10.48550/arXiv.2401.02009.
  * Zhuang et al. (2024) Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Mitra, Victor Bursztyn, Ryan A. Rossi, Somdeb Sarkhel, and Chao Zhang.  Toolchain*: Efficient action space navigation in large language models with a* search.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=B6pQxqUcT8.

##  Appendix A Limitations

RoT has several limitations. It requires models to have good overall
capabilities. A strong model is required to summarize a meaningful guideline.
Furthermore, the model used to perform tree search should have good
instruction-following ability. Otherwise, it may not follow the guidelines and
thus the guidelines will be useless. To select important states and reflect
meaningful guidelines, RoT requires accurate value estimation of states in
trees. This requires a strong value estimation method or in MCTS, a large
number of iterations.

##  Appendix B Additional Experiments Details

###  B.1 LLM Input & Output Examples

We show the input & output examples in Blocksworld. For prompts in GSM8k and
CraigslistBargain, see our GitHub repository. We use prompts from RAP (Hao et
al., 2023) in blocksworld.

Action Evaluation

Input:I am playing with a set of blocks where I need to arrange the blocks
into stacks. Here are the actions I can doPick up a blockUnstack a block from
on top of another blockPut down a blockStack a block on top of another blockI
have the following restrictions on my actions:I can only pick up or unstack
one block at a time.I can only pick up or unstack a block if my hand is
empty....To effectively manage the BlocksWorld game environment and achieve
higher rewards, the following consolidated policy guideline should be applied
by the agent:
1\. The agent should focus on unstacking or picking up blocks that are
essential for constructing the goal configuration, especially if they are not
already positioned correctly. It should endeavor to clear blocks that are part
of the goal configuration by ensuring that no other blocks are stacked on top
of them and are thus free to be manipulated.
2\. When the agent’s hand is empty, it should prioritize picking up blocks
that will contribute to the immediate construction of a correct sub-
configuration which leads towards the overall goal configuration.
Preferentially, blocks should be picked up in an order that reflects their
final position in the goal state to minimize additional moves.
3\. If the agent is holding a block, it must assess whether placing it
immediately contributes to the goal configuration. If the action is valid and
moves closer to achieving the goal, it should place the block accordingly.
Otherwise, the agent should put it down on the table in a clear space to keep
options open for subsequent actions.
...Please evaluate whether the given action is a good one under certain
conditions.[STATEMENT]As initial conditions I have that, the red block is
clear, the yellow block is clear, the hand is empty, the red block is on top
of the blue block, the yellow block is on top of the orange block, the blue
block is on the table and the orange block is on the table.My goal is to have
that the orange block is on top of the red block.[ACTION]unstack the red block
from on top of the blue block[EVALUATION]bad...[STATEMENT]As initial
conditions I have that, the red block is clear, the yellow block is clear, the
hand is empty, the red block is on top of the blue block, the yellow block is
on top of the orange block, the blue block is on the table and the orange
block is on the table.My goal is to have that the red block is on top of the
orange block and the orange block is on top of the blue block.[ACTION]unstack
the yellow block from on top of the orange block[EVALUATION]Outputs:Normalized
probability of outputting good vs bad.The red part is the guideline, the blue
part is the description of the current state, and the green part is the action
to evaluate.

###  B.2 Full Blocksworld Results

| Method | Step 2 | Step 4 | Step 6 | Step 8 | Step 10
---|---|---|---|---|---|---
| Base | RoT | LEAP | Base | RoT | LEAP | Base | RoT | LEAP | Base | RoT | LEAP | Base | RoT | LEAP
phi-2 | CoT | 8.1 | 13.5 (+66.7%) | 15.4 | 1.3 | 3.9 (+200.0%) | 1.7 | 0.0 | 0.0 (+0.0%) | 0.0 | 0.0 | 0.0 (+0.0%) | 0.0 | 0.0 | 0.0 (+0.0%) | 0.0
CoT-Pass@10 | 43.2 | 54.1 (+25.2%) | 56.8 | 5.3 | 15.8 (+198.1%) | 13.2 | 1.4 | 1.4 (+0.0%) | 2.1 | 0.0 | 0.7 (+0.0%) | 0.0 | 0.0 | 0.0 (+0.0%) | 0.0
BFS(5) | 97.3 | 100.0 (+2.8%) | 100.0 | 61.8 | 69.7 (+12.8%) | 67.1 | 25.5 | 29.0 (+13.7%) | 33.1 | 11.2 | 16.1 (+43.8%) | 14.0 | 5.8 | 8.7 (+50.0%) | 5.8
MCTS(1) | 55.6 | 59.5 (+7.0%) | 59.5 | 30.3 | 36.8 (+21.5%) | 28.9 | 17.9 | 18.6 (+3.9%) | 22.8 | 4.2 | 6.3 (+50.0%) | 4.2 | 1.9 | 1.9 (+0.0%) | 1.9
MCTS(10) | 89.2 | 86.5 (-3.0%) | 89.2 | 84.2 | 85.5 (+1.5%) | 80.3 | 46.9 | 55.2 (+17.7%) | 53.1 | 11.2 | 17.5 (+56.2%) | 14.7 | 2.9 | 3.9 (+34.5%) | 2.9
mistral-7b | CoT | 35.1 | 43.2 (+23.1%) | 27.0 | 5.3 | 10.5 (+98.1%) | 10.9 | 3.4 | 6.2 (+82.4%) | 3.8 | 0.0 | 0.0 (+0.0%) | 0.0 | 0.0 | 1.0 (+0.0%) | 1.2
CoT-Pass@10 | 83.8 | 81.1 (-3.2%) | 81.1 | 40.8 | 48.7 (+19.4%) | 55.3 | 24.1 | 21.4 (-11.2%) | 26.9 | 4.9 | 10.5 (+114.3%) | 9.0 | 7.8 | 11.7 (+50.0%) | 10.7
BFS(5) | 100.0 | 100.0 (+0.0%) | 100.0 | 86.8 | 89.5 (+3.1%) | 89.5 | 64.1 | 61.4 (-4.2%) | 62.1 | 42.0 | 42.7 (+1.7%) | 42.0 | 32.0 | 33.0 (+3.1%) | 33.0
MCTS(1) | 64.9 | 67.6 (+4.2%) | 75.7 | 59.2 | 61.8 (+4.4%) | 61.8 | 40.0 | 43.4 (+8.5%) | 41.4 | 14.5 | 24.5 (+69.0%) | 21.0 | 12.6 | 21.4 (+69.8%) | 18.4
MCTS(10) | 78.4 | 83.8 (+6.9%) | 89.2 | 89.5 | 92.1 (+2.9%) | 94.7 | 76.6 | 76.0 (-0.8%) | 77.2 | 55.2 | 59.4 (+7.6%) | 58.0 | 29.1 | 34.0 (+16.8%) | 30.1
mixtral-8x7b | CoT | 29.7 | 45.9 (+54.5%) | 34.3 | 9.2 | 18.4 (+100.0%) | 13.0 | 11.0 | 11.7 (+6.4%) | 9.4 | 2.1 | 4.9 (+133.3%) | 2.8 | 2.9 | 3.9 (+34.5%) | 3.3
CoT-Pass@10 | 81.1 | 86.5 (+6.7%) | 89.2 | 63.2 | 71.1 (+12.5%) | 61.8 | 54.5 | 54.5 (+0.0%) | 53.1 | 17.5 | 29.4 (+68.0%) | 21.7 | 20.4 | 27.2 (+33.3%) | 26.2
BFS(5) | 100.0 | 100.0 (+0.0%) | 97.3 | 92.1 | 93.4 (+1.4%) | 92.3 | 60.7 | 57.2 (-5.8%) | 54.5 | 33.6 | 40.6 (+20.8%) | 39.2 | 29.1 | 33.0 (+13.4%) | 32.0
MCTS(1) | 62.2 | 59.5 (-4.3%) | 66.0 | 64.5 | 69.7 (+8.1%) | 67.1 | 41.9 | 42.8 (+2.1%) | 42.1 | 17.5 | 21.7 (+24.0%) | 20.3 | 16.5 | 22.3 (+35.2%) | 15.5
MCTS(10) | 91.9 | 94.6 (+2.9%) | 91.9 | 88.2 | 89.5 (+7.4%) | 86.8 | 76.6 | 75.2 (-1.8%) | 75.2 | 51.7 | 54.5 (+5.4%) | 50.3 | 32.0 | 34.0 (+6.2%) | 29.1

Table 6: Full Blocksworld Results. CoT-Pass(n) denotes the rate that at least
one correct solution in $n$ CoT generations. BFS(b) means the number of beams
in BFS is $b$. MCTS(n) denotes $n$ iterations are performed. Number of steps
is the minimum number of actions to solve this problem. A higher number of
steps indicates a harder problem.

###  B.3 CraigslistBargin Example

Figure 7: An example of bargaining. The profit of the seller in this deal is
$\frac{105-(125+95)/2}{125-95}=-0.17$

###  B.4 Iterative Improvement with RoT

We evaluate iterative improvement with RoT on the 6-step split of Blocksworld
using MCTS10 with phi-2. As shown in Figure 9 and Figure 9, the performance
does not improve significantly if we iteratively perform RoT. In Blocksword,
as the number of iterations of RoT increases, the accuracy tends to increase
when the number of RoT iterations is small and soon gets saturated. We can
also find that a longer guideline does not necessarily lead to better
performance.

Figure 8: Word count of summarized guidelines and accurate when iteratively
applying RoT to MCTS(10) on Blocksworld with step 6 with phi-2.

Figure 9: Word count of summarized guidelines and accurate when iteratively
applying RoT to MCTS(10) on GSM8k with phi-2.

Method | phi-2 | mistral-7b | mixtral-8x7b
---|---|---|---
MCTS | 57.3 | 51.9 | 68.1
RoT-MCTS | 57.7(+0.7%) | 52.7(+1.5%) | 69.7(+2.4%)

Table 7: AUC of GSM8k.

###  B.5 Guidelines in Prompising Decision Selection

Method |  Guideline | Accuracy
---|---|---
MCTS(1) |  - | 42.4
_\+ problem samples_ |  To effectively solve math word problems, it’s important to follow a structured approach. Here is a general guideline that can be applied to many types of math word problems:  1. Read the Problem Carefully: Understand what the problem is asking. Identify the key information and what the problem is asking you to find. 2. Identify the Variables: Determine what quantities the problem is dealing with and assign symbols if necessary. 3. Translate Words into Math: Convert the words into mathematical expressions or equations using the identified variables. 4. Develop a Plan: Decide on the steps you need to take to solve the problem using the information given. 5. Execute the Plan: Carry out the steps you have decided on to find the solution. 6. Check Your Work: Verify that your solution makes sense in the context of the problem and that you have answered what was asked. | 44.7
_\+ all states_ |  Comprehensive Policy for Solving Word Problems:  1. Initial Reading and Understanding: • Carefully read the entire word problem to fully understand the main question, the context, and all the relevant information needed for the solution. • Identify initial conditions, key details, and the end goal of the problem to ensure a comprehensive understanding before beginning to solve it. 2. Breaking Down the Problem into Subquestions: • Formulate subquestions that directly relate to and build upon the main question, ensuring each subquestion is a necessary step toward reaching the final answer. • Make sure all aspects of the problem are covered in the subquestions, including any conditions, contributions from different sources, rates, and sequences required for a complete solution. • Avoid redundancy in subquestions and exclude any that provide unnecessary calculations or information already known. 3. Calculations and Unit Conversions: • When dealing with time conversions or solving for rates, maintain high precision by using fractions or at least three decimal places to prevent rounding errors until the final calculation. • Double-check all arithmetic operations, especially additions, subtractions, and multiplications, for accuracy and ensure that they align with the broader context of the problem. • In context-appropriate situations, keep answers in fractional form to represent exact figures and avoid unnecessary rounding. 4. Approach and Logical Building: • Proceed logically through the subquestions, with each providing information and answers that build upon the previous ones, culminating in the solution to the main question. • Sequentially address each component of the problem, making sure not to miss any crucial step in between, such as additional money needed, contributions, or subsequent divisions. | 44.2

Table 8: Guideline samples and performance of mistral-7b on GSM8k when
employing different selection mechanism for reflection.

_\+ random states_ |  This policy serves as a guideline for framing subquestions and responses in a precise and logical manner to solve complex problems, ensuring maximum accuracy and reward attainment.  1. Understanding the Problem Context: • Ensure you have a deep understanding of the given problem, including initial conditions, mathematical concepts required (e.g., percentages, multiplication), and the main question’s objectives. • Accurately account for starting conditions or states, incorporating all relevant variables that influence the problem’s outcome. 2. Formulating Subquestions: • Subquestions must be directly relevant and contribute meaningfully towards solving the main question. Validate this relevance carefully. • Keep subquestions simple, clear, and precise, using concise language to avoid confusion and misinterpretation. • Avoid redundant or unnecessary subquestions and eliminate any that do not bring us closer to the final solution. • Follow a logical progression where each subquestion builds upon previous answers, leading incrementally to the final answer. • Subquestions should be asked in the appropriate order that aligns with the problem-solving process. • Restate relevant information from previous steps when answering subquestions to prevent misunderstanding. 3. Calculations and Computations: • Carefully perform calculations required for each subquestion, double-checking arithmetic and using tools like calculators when necessary. • Confirm that multiplication factors and percentage increases are correctly applied; convert percentages to decimals for easier computation. • Accumulate values correctly according to the problem statement. For instance, apply the correct operations for totals (addition) and increases (multiplication). • When integrating intermediate answers, ensure full and correct incorporation into subsequent problem-solving steps. 4. Review and Validation: • Review each calculation and logical flow at every step to verify accuracy before proceeding. • Synthesize all subanswers thoroughly to construct an accurate final answer to the main question. • Consistently check the logic and mathematical rationale behind each step to ascertain that the path from subanswers to final solutions is logical. • After providing responses, review the mathematical correctness and ensure that intermediate steps logically lead to the final answer. • Any time a reward is marked as false, carefully analyze the actions and responses that led to the error. Adjust future strategies based on this analysis. 5. Consistency in Rewards: • Maintain a consistent reward system where correct answers are indicated with the appropriate numerical value (e.g., 1.0) and incorrect answers are clearly marked with ’False’ or a reduced reward. | 45.0
---|---|---

Table 9: Guideline samples and performance continue.

_\+ prom. states ( $\lambda=0.5$)_ |  1. Thorough Understanding and Problem Statement: • Read the problem statement thoroughly to fully understand the context and what is specifically being asked. • Identify and recognize essential data that directly affects the calculation needed for the main question’s answer. 2. Formulation of Subquestions: • Develop relevant subquestions that address individual components of the problem and lead toward the solution, ensuring each one progresses logically toward solving the main problem. • Frame subquestions to provide necessary intermediate values required in later steps, without introducing extraneous information. • Ensure subquestions are structured to answer the main question in a logical sequence, providing clear, step-by-step reasoning within subanswers. 3. Calculation Precision and Accuracy: • Always be as precise as possible in calculations, maintaining exactness in intermediate values and avoiding premature rounding, especially when dealing with fractions or divisions. • When addressing percentages, use the correct mathematical operations to calculate increases or other quantities, ensuring the correct base value is used. • Validate subanswers by re-confirming calculations if results seem unlikely or to rectify simplistic errors, double-checking for accuracy and consistency in units. 4. Simplification and Rounding Conventions: • Provide simplified fractions that maintain the same level of accuracy as their decimal form when possible. • Final answers must reflect proper rounding conventions, especially involving currency, rounding off to the nearest cent for financial accuracy. 5. Consistency and Coherence: • Maintain consistency in units throughout the problem, ensuring all units are converted and used consistently. • Check if subanswers are logically consistent, mathematically correct, and coherent when assembled to solve the overall problem. 6. Verification and Review: • Perform a final check of the subanswer against the question to validate that it addresses the subquestion fully and revisit steps when necessary. • Verify the completeness of the solution, ensuring all steps are covered and no intermediate values are missing. • Prior to finalizing the answer, verify if it answers the main question sensibly and accurately. 7. Learning from Rewards and Feedback: • Use rewards as feedback to identify successful problem-solving strategies and reinforce approaches that yield higher accuracy. • Reflect on and learn from any mistakes made in previous problems, understanding why certain responses received lower rewards to improve future outcomes. | 45.6
---|---|---

Table 10: Guideline samples and performance continue.

_\+ prom. states ( $\lambda=0.1$)_ |  To solve math word problems effectively and minimize errors, integrate the various suggested policies into the following comprehensive approach:  1. Clarify the quantities involved, distinguishing between total amounts, unit costs, and multiplicative factors. Use correct mathematical operations based on these relationships. 2. When necessary, accurately convert between units (e.g., minutes to hours) using proper mathematical operations, and maintain consistency in units throughout the problem. 3. Directly translate the word problem’s conditions into mathematical equations or expressions, and apply correct mathematical operations. 4. Address each sub-question in a logical order, one at a time, methodically performing operations and maintaining at least three decimal places of precision for operations with hourly rates or similar calculations. 5. When dealing with ratios or relational costs, ensure the correct base amounts are used for calculations. 6. Sequentially solve the sub-questions, constantly cross-referencing with the problem’s conditions, and checking that each sub-answer is logical and consistent with the overall scenario. 7. Refrain from rounding intermediate results to maintain accuracy, and only round the final result if necessary, ensuring the level of precision matches that of the given variables. 8. Regularly ensure that all units and logical consistencies are maintained throughout the solution process, avoiding impossible situations (such as fractions of indivisible items). 9. Double-check each step against the provided information and common sense narrative to avoid repetition of errors or misinterpretation. 10. Before finalizing the answer, confirm that each part of the problem has been addressed and that the math operations have been applied correctly. Validate each sub-answer and the final answer, ensuring that they make sense and address the question accurately and fully. 11. After combining sub-answers for the final solution, question its reasonableness in the context of the problem, verifying if quantities add up correctly and whether the overall solution is plausible. | 47.3
---|---|---

Table 11: Guideline samples and performance continue.

##  Appendix C Experiment Settings

###  C.1 Hyperparameter settings.

In Blocksworld, we provide the model with 4 in-context demonstrations when
performing value estimation and next-state prediction. In GSM8k, we provide
the model with 4 in-context demonstrations when performing action generation,
value estimation, and response generation. In all experiments, we set the
decoding to sample with temperature $t=0.7$. Due to limited computational
resources, for phi-2 models, we get the results by averaging 3 runs, and for
the other models, we get the result by a single run.

###  C.2 Model Details

phi-2: https://huggingface.co/microsoft/phi-2

mistral-7b: https://huggingface.co/mistralai/mistral-7b-v0.1

mixtral-8x7b: https://huggingface.co/mistralai/mixtral-8x7b-v0.1

gpt-4: gpt-4-1106

chatgpt: gpt-3.5-turbo-1106

###  C.3 Computational Resources

We run all our experiments on 4$\times$A800 with 80G memory.


#  Integer partitions with large Dyson rank

Colin Albert, Olivia Beckwith, Irfan Demetoglu,
Robert Dicks, John H. Smith, Jasmine Wang

###### Abstract.

The Dyson rank of an integer partition is the difference between its largest
part and the number of parts it contains. Using Fine-Dyson symmetry, we study
counts of partitions whose rank lies in fixed residue classes and has large
absolute value. We prove formulas relating these counts for partitions of
different sizes.

##  1\. Introduction

A partition of an integer $n$ is a nonincreasing sequence of positive integers
whose sum is $n$. The partition function $p(n)$ is defined as the number of
partitions of $n$ for $n\geq 1$, and $p(0)=1$. Throughout we let $P(n)$ denote
the set of partitions of $n$, so that $p(n)=|P(n)|$ for integers $n\geq 1$,
and $P(n)=\emptyset$ if $n$ is not a positive integer.

The arithmetic properties of the partition function have fascinated number
theorists since Srinivasa Ramanujan [Ram21] discovered the Ramanujan
congruences:

$\displaystyle p(5k+4)$ $\displaystyle\equiv 0\pmod{5},$ $\displaystyle
p(7k+5)$ $\displaystyle\equiv 0\pmod{7},$ $\displaystyle p(11k+6)$
$\displaystyle\equiv 0\pmod{11}.$

Ramanujan’s proof of the Ramanujan congruences used properties of the
generating function of $p(n)$. Freeman Dyson [Dys44] conjectured that the
first two Ramanujan congruences could be interpreted combinatorially using the
_rank statistic_ , which he defined to be the difference between the largest
element of the sequence and the number of elements of the sequence. He also
conjectured that the third congruence could be explained combinatorially using
a similar statistic called the _crank_ , which he did not claim to know how to
define. His conjectures about the rank were proved by Atkin and Swinnerton-
Dyer [ASD54], and his conjectured crank function was discovered by Andrews and
Garvan [AG88].

To state Dyson’s conjectures about the rank more precisely, we let
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ denote a partition of
$n$, with $\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{k}\geq 1$. The
rank of $\lambda$ is defined to be:

$\operatorname{rank}(\lambda):=\lambda_{1}-k$

For example,

$\operatorname{rank}((6,3,3,2))=6-4=2.$

Dyson conjectured that the rank function divides the partitions of $5n+4$
(resp., $7n+5$) into $5$ (resp., $7$) different sets of equal size. More
specifically, if we let $N(r,m,n)$ denote the number of partitions of $n$
whose rank is congruent to $r$ modulo $m$, then Dyson conjectured that for any
$a,n\in\mathbb{Z}$,

$N(a,5,5n+4)=\frac{p(5n+4)}{5}$

and similarly,

$N(a,7,7n+5)=\frac{p(7n+5)}{7},$

and since $N(a,5,5n+4)$ and $N(a,7,7n+5)$ are integers, these two claims imply
the first and second Ramanujan congruences.

Dyson also conjectured several relations between counts of partitions with
specific ranks, all of which were shown in [ASD54]. These relations are all of
the form $N(a,p,pn+b)=N(c,p,pn+b)$ for $p\in\\{5,7\\}$, except for the
following (see (19) of [Dys44]):

(1.1) $N(0,7,7n+6)+N(1,7,7n+6)=N(2,7,7n+6)+N(3,7,7n+6).$

A few examples of relations similar to (1.1) for ranks in residue classes
modulo 8,9, and 12 are known by the work of Lewis [Lew92] and Santa-Gadea
[SG90]. We show that restricting to partitions such that the absolute value of
the rank is larger than $\frac{n}{2}$, one obtains many identities resembling
(1.1).

For any $n\in\mathbb{Z}$ we define $N^{+}(r,m,n)$ as follows:

$N^{+}(r,m,n):=\\#\left\\{\lambda\in P(n):\operatorname{rank}(\lambda)\equiv
r\pmod{m},|\operatorname{rank}(\lambda)|\geq\frac{n}{2}\right\\}.$

Then we obtain the following family of identities:

######  Theorem 1.

Let $r_{1},...r_{4}$, $a_{1},...,a_{4},m\in\mathbb{Z}$ be such that
$a_{1},...,a_{4},m$ are positive and we have:

(1.2) $\displaystyle
a_{1}-r_{1}-m\Bigl{\lceil}\frac{a_{1}-2r_{1}}{2m}\Bigr{\rceil}$
$\displaystyle=a_{3}-r_{3}-m\Bigl{\lceil}\frac{a_{3}-2r_{3}}{2m}\Bigr{\rceil},$
(1.3) $\displaystyle
a_{1}+r_{1}-m\Bigl{\lceil}\frac{a_{1}+2r_{1}}{2m}\Bigr{\rceil}$
$\displaystyle=a_{4}-r_{4}-m\Bigl{\lceil}\frac{a_{4}-2r_{4}}{2m}\Bigr{\rceil},$
(1.4) $\displaystyle
a_{2}-r_{2}-m\Bigl{\lceil}\frac{a_{2}-2r_{2}}{2m}\Bigr{\rceil}$
$\displaystyle=a_{4}+r_{4}-m\Bigl{\lceil}\frac{a_{4}+2r_{4}}{2m}\Bigr{\rceil},$
(1.5) $\displaystyle
a_{2}+r_{2}-m\Bigl{\lceil}\frac{a_{2}+2r_{2}}{2m}\Bigr{\rceil}$
$\displaystyle=a_{3}+r_{3}-m\Bigl{\lceil}\frac{a_{3}+2r_{3}}{2m}\Bigr{\rceil}.$

Then for $n\geq 0$, we have:

$N^{+}(r_{1},m,2mn+a_{1})+N^{+}(r_{2},m,2mn+a_{2})=N^{+}(r_{3},m,2mn+a_{3})+N^{+}(r_{4},m,2mn+a_{4}).$

Note that if the $a_{i}$ are all equal, one has $r_{1}\equiv r_{3}\equiv-
r_{4}\equiv-r_{2}\equiv-r_{3}\pmod{m}$, and the statement is not interesting.
However, when the $a_{i}$ are distinct, one obtains relations between counts
of partitions of different numbers with rank that have large absolute values
and lie in given residue classes. Comparing counts of partitions of different
numbers with prescribed rank properties is significantly different than (1.1).

######  Example.

Theorem 1 implies that for $n\geq 0$,

$\displaystyle N^{+}(2,19,38n+20)+N^{+}(5,19,38n+22)$
$\displaystyle=N^{+}(14,19,38n+32)+N^{+}(7,19,38n+29)$ $\displaystyle
N^{+}(1,21,42n+43)+N^{+}(19,21,42n+50)$
$\displaystyle=N^{+}(3,21,42n+45)+N^{+}(4,21,42n+27)$ $\displaystyle
N^{+}(1,23,46n+47)+N^{+}(-2,23,46n+54)$
$\displaystyle=N^{+}(3,23,46n+49)+N^{+}(4,23,46n+29).$

It is not difficult in practice to find $m,r_{i},a_{i}$ satisfying
(1.2)-(1.5). Given a choice of $a_{1},\cdots,a_{4}$ and $r_{1},\cdots,r_{4}$
for which (1.2)-(1.5) hold modulo $m$, it is usually (although not always)
possible to shift the $a_{i}$ modulo $2m$, thereby shifting each side of
(1.2)-(1.5) by a multiple of $m$, to produce a solution of (1.2)-(1.5). More
examples can be found in the Mathematica [Wol] code on the second author’s
homepage.

Theorem 1 is proved using Fine-Dyson symmetry (see [Fin48], [Fin88], [Dys69],
and the survey [Pak06]), which relates the partitions of $n$ with rank at most
$r$ to partitions of $n+r-1$ with rank at most $2-r$ using a bijective
argument on Young diagrams. As a consequence, if one lets $N(m,n)$ denote the
number of partitions of $n$ with rank $m$, then one can show that the
inequality

(1.6) $N(m,n)\leq p(n-1-|m|)-p(n-2-|m|),$

holds, with equality if $|m|\geq\frac{n}{2}-2$.

In Section 2 we give an alternative proof of this fact. Our proof involves the
set of partitions for which the number of parts is a part. We let $g(k)$
denote the number of partitions of $k$ satisfying this property.

######  Proposition 2.

For all $m,n\in\mathbb{Z}$, we have

$N(m,n)\leq g(n-|m|)=p(n-1-|m|)-p(n-2-|m|),$

with equality if $|m|\geq\frac{n}{2}-2$.

Here we use the convention that $p(x)=0$ if $x$ is not a non-negative integer.

Considering the partitions of $n$ with large rank was partly inspired by
asymptotic formulas for the number of partitions of $n$ with rank or crank
equal to $m$, where $|m|\leq\frac{\sqrt{n}\log{n}}{\pi\sqrt{6}}$. These
formulas were conjectured by Dyson [Dys89] and proved using the circle method
by Bringmann and Dousse [BD16] for cranks and by Dousse and Mertens [DM15] for
ranks. In contrast to the partitions with small rank, the partitions
considered in this paper are easy to count: Proposition 2 implies that the
number of partitions of $n$ with rank at least $\frac{n}{2}$ is
$p(\lfloor\frac{n}{2}\rfloor-1)$. By the Hardy-Ramanujan asymptotic [HR00], we
have

$p(n)\sim\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{\frac{2n}{3}}}$

Thus, the portion of the partitions that have rank at least $n/2$ is
exponentially decreasing with $n$:

$\frac{\\#\\{\lambda\in
P(n):\operatorname{rank}(\lambda)\geq\frac{n}{2}\\}}{p(n)}=\frac{p(\lfloor\frac{n}{2}\rfloor-1)}{p(n)}\sim
2e^{\pi(1-\sqrt{2})\sqrt{\frac{n}{3}}}.$

For example, there are 37338 partitions of 40 (shown in the histogram), but
only 490 have rank greater than or equal to 20, a portion of about 1.31%.

Figure 1. Ranks of partitions $\lambda\in P(40)$

In Section 2 we review some standard facts about partitions and prove
Proposition 2. The proof of Theorem 1 is given in Section 3. Section 4
mentions a few questions for future work.

## Acknowledgements

The authors are grateful to the anonymous referee for a thorough report
offering several valuable suggestions that have improved the manuscript. The
authors also thank the Illinois Geometry Lab, which is supported by the
Department of Mathematics at the University of Illinois at Urbana-Champaign.
This material is based upon work supported by the National Science Foundation
under Grant No. DMS-1449269. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the authors and do not
necessarily reflect the views of the National Science Foundation.

##  2\. Fine-Dyson Symmetry

Throughout, we let $\lambda=(\lambda_{1},\ldots,\lambda_{b})$ and
$\mu=(\mu_{1},\ldots,\mu_{c})$ denote partitions, with the $\lambda_{i}$ and
$\mu_{i}$ positive integers satisfying
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{b}$ and
$\mu_{1}\geq\mu_{2}\geq\ldots\geq\mu_{c}$. The $\lambda_{i}$ are called the
_parts_ of $\lambda$. We let
$|\lambda|=\lambda_{1}+\lambda_{2}+\ldots+\lambda_{b}$, and we let
$\lambda\cup\mu$ be the partition of $|\lambda|+|\mu|$ consisting of the union
of the parts of both $\lambda$ and $\mu$, e.g.

$(4,2,2,1)\cup(7,4,2)=(7,4,4,2,2,2,1).$

Partitions are naturally visualized using Young diagrams. The Young diagram of
a partition $\lambda$ is an array of squares such that the top row has
$\lambda_{1}$ squares, the second row has $\lambda_{2}$ squares, and so on.
For example, the Young diagram for $\lambda=(3,2,2,1)$ is

&

Reflecting the Young diagram across the $y=-x$ line, where the top left corner
is the origin $(0,0)$, produces a Young diagram for another partition, called
the _conjugate_ of $\lambda$. For example, the conjugate of
$\lambda=(3,2,2,1)$ is $(4,3,1)$:

&

The rank of the conjugate of a partition $\lambda$ is
$-\operatorname{rank}(\lambda)$, and it follows that $N(m,n)=N(-m,n)$.

###  2.1. Proof of Proposition 2

The claim (1.6) follows from work of Fine and Dyson ([Fin48], [Fin88],
[Dys69]), and we’ll briefly summarize their techniques before presenting our
alternative proof.

Let $h(n,r)$ denote the number of partitions of $n$ with rank at most $r$,
thus,

$h(n,r)=\sum_{m=-(n-1)}^{r}N(m,n).$

Fine and Dyson define a bijection between the set of partitions of $n$ of rank
at most $r$ and the set of partitions of $n+r-1$ of rank at least $r-2$, in
which one adds $r-1$ squares to the leftmost column of a Young diagram of a
partition of $n$ and then moves it to the top row. Conjugating the partitions
of $n+r-1$ with rank at least $r-2$, one obtains

(2.1) $h(n,r)=h(n+r-1,2-r).$

Then (1.6) can be derived from (2.1) and $N(m,n)=h(n,m)-h(n,m-1)$.

###### Proof.

First we will show that $N(m,n)\leq g(n-|m|)$, with equality if
$m\geq\frac{n}{2}-2$.

From the rank symmetry $N(m,n)=N(-m,n)$, we may assume that $m$ is non-
negative without loss of generality.

We will define a map $f$ from the partitions of $n$ with rank $m$ to the
partitions of $n-m$ such that the number of parts is a part. Take a partition
$\lambda$ of $n$ with rank $m$. Then it is of the form:

$\lambda=(m+c)\cup\mu$

where $m+c$ is the largest part of $\lambda$ and $c$ is the number of parts of
$\lambda$, with $\mu$ a partition of $n-m-c$. Then we define $f(\lambda)$ to
be $f(\lambda):=(c)\cup\mu.$ We note that $f(\lambda)$ is a partition of $n-m$
with $c$ parts, and with $c$ present as a part.

Suppose $\lambda=(m+c,\lambda_{2},\ldots,\lambda_{c})$ and
$\lambda^{\prime}=(m+c^{\prime},\lambda_{2}^{\prime},\ldots,\lambda_{c^{\prime}}^{\prime})$
are such that

$f(\lambda)=\mu=f(\lambda^{\prime}),$

where $\mu$ is a partition of $n-m$. Then $c$ and $c^{\prime}$ both equal the
number of parts of $\mu$, and hence $c^{\prime}=c$. It then follows from
$f(\lambda)=f(\lambda^{\prime})$ that $\lambda_{i}=\lambda_{i}^{\prime}$ for
each $1\leq i\leq c$, so that $\lambda=\lambda^{\prime}$. Thus the map $f$ is
injective, which proves the first part of the claim, that $N(m,n)\leq
g(n-|m|)$.

To show the second half of the claim, we assume $m\geq\frac{n}{2}-2$ . We will
show that $f$ is also surjective: first, if $m=n-1$, then the only partition
of $n$ with rank $m$ is the partition $(n)$, and this corresponds to the only
partition of $n-m=1$, for which the number of parts is equal to one, and is
the size of the only part. Now suppose $m\leq n-2$, and let $\mu$ be a
partition of $n-m$ whose number of parts is a part. Then $\mu$ is of the form
$(c)\cup\mu^{\prime}$, where $\mu^{\prime}$ is a partition of $n-m-c$ with
$c-1$ parts. Note that $c\geq 2$, since $n-m\geq 2$. We observe that
$\delta:=(c+m)\cup\mu^{\prime}$ is a partition of $n$ with $c$ parts. The
largest part of $\delta$ must be $c+m$, since

$c+m\geq m+2\geq\frac{n}{2}\geq n-m-c=|\mu^{\prime}|.$

Finally, we have

(2.2) $g(k)=p(k-1)-p(k-2)$

for all $k\geq 1$ (see the sequence A002865 [oei]). For completeness, we
provide a brief proof. Clearly, $p(k-1)-p(k-2)$ is the number of partitions of
$k-1$ for which one is not a part. Given such a partition
$\lambda=(\lambda_{1},\ldots,\lambda_{b})$, we can construct a partition
$\gamma=(\lambda_{1}-1,\lambda_{2}-1,\ldots,\lambda_{b}-1)\cup(b+1)$, which is
partition of $k$ with $b+1$ parts. On the other hand, if
$\mu=(\mu_{1},\ldots,\mu_{b})$ is a partition of $k$ such that $b$ is a part,
then $(\mu_{1}+1,\ldots,\mu_{b}+1)\backslash(b+1)$ is a partition of $k-1$
which contains no ones as parts. We have given a bijection between the
partitions of $k-1$ containing no parts equal to one and the partitions of $k$
for which the number of parts is a part, which proves (2.2).

Thus we have shown that

$N(m,n)\leq g(n-|m|)=p(n-|m|-1)-p(n-|m|-2),$

with equality if $|m|\geq\frac{n}{2}-2$. ∎

##  3\. Proof of Theorem 1

Assume that $m,a_{1},\cdots,a_{4},r_{1},\cdots,r_{4}$ satisfy the assumptions
of Theorem 1. By definition,

$N^{+}(r_{j},m,2mn+a_{j})=\sum_{|r_{j}+mk|\geq\frac{2mn+a_{j}}{2}}N(r_{j}+mk,2mn+a_{j}).$

Applying Proposition 2, we obtain

$\displaystyle N^{+}(r_{j},m,2mn+a_{j})$
$\displaystyle=\sum_{r_{j}+mk\geq\frac{2mn+a_{j}}{2}}N(r_{j}+mk,2mn+a_{j})$
$\displaystyle\quad\quad+\sum_{r_{j}+mk\leq\frac{-(2mn+a_{j})}{2}}N(r_{j}+mk,2mn+a_{j})$
$\displaystyle=\sum_{k\geq
n+\lceil\frac{a_{j}-2r_{j}}{2m}\rceil}g(a_{j}-r_{j}+m(2n-k))$
$\displaystyle\quad\quad+\sum_{k\geq
n+\lceil\frac{a_{j}+2r_{j}}{2m}\rceil}g(a_{j}+r_{j}+m(2n-k))$
$\displaystyle=S_{j}^{-}+S_{j}^{+},$

where

(3.1) $S_{j}^{-}:=\sum_{k\geq
n+\lceil\frac{a_{j}-2r_{j}}{2m}\rceil}g(a_{j}-r_{j}+m(2n-k))$

and

(3.2) $S_{j}^{+}:=\sum_{k\geq
n+\lceil\frac{a_{j}+2r_{j}}{2m}\rceil}g(a_{j}+r_{j}+m(2n-k)).$

With this notation, our goal is to show

$S_{1}^{+}+S_{1}^{-}+S_{2}^{+}+S_{2}^{-}=S_{3}^{+}+S_{3}^{-}+S_{4}^{+}+S_{4}^{-}.$

We will prove this by showing the following equalities:

$\displaystyle S_{1}^{-}$ $\displaystyle=S_{3}^{-},$ $\displaystyle S_{1}^{+}$
$\displaystyle=S_{4}^{-},$ $\displaystyle S_{2}^{-}$
$\displaystyle=S_{4}^{+},$ $\displaystyle S_{2}^{+}$
$\displaystyle=S_{3}^{+}.$

Let $t_{ij}:=\frac{a_{i}-r_{i}-(a_{j}-r_{j})}{m}$, then we have:

$S_{i}^{-}=\sum_{k\geq
n+\lceil\frac{a_{i}-2r_{i}}{2m}\rceil}g(a_{j}-r_{j}+m(2n-k+t_{ij})).$

Next we make the substitution $v=k-t_{ij}$ and obtain:

$S_{i}^{-}=\sum_{v\geq
n-t_{ij}+\lceil\frac{a_{i}-2r_{i}}{2m}\rceil}g(a_{j}-r_{j}+m(2n-v)).$

This is equal to $S_{j}^{-}$ if

$n-t_{ij}+\left\lceil\frac{a_{i}-2r_{i}}{2m}\right\rceil=n+\left\lceil\frac{a_{j}-2r_{j}}{2m}\right\rceil.$

Using (1.2), it follows that $S_{1}^{-}=S_{3}^{-}.$

Let $s_{ij}:=\frac{a_{i}-r_{i}-(a_{j}+r_{j})}{m}$, then we have:

$S_{i}^{-}=\sum_{k\geq
n+\lceil\frac{a_{i}-2r_{i}}{2m}\rceil}g(a_{j}+r_{j}+m(2n-k+s_{ij})).$

Next we make the substitution $v=k-s_{ij}$ and obtain:

$S_{i}^{-}=\sum_{v\geq n+\lceil\frac{a_{i}-2r_{i}}{2m}\rceil-
s_{ij}}g(a_{j}+r_{j}+m(2n-v)).$

This is equal to $S_{j}^{+}$ if $\lceil\frac{a_{i}-2r_{i}}{2m}\rceil-
s_{ij}=n+\lceil\frac{a_{j}+2r_{j}}{2m}\rceil$. Therefore $S_{1}^{+}=S_{4}^{-}$
and $S_{2}^{-}=S_{4}^{+}$ follow from (1.3)-(1.4).

The last equation, $S_{2}^{+}=S_{3}^{+}$ follows almost identically: setting
$w=\frac{a_{2}+r_{2}-(a_{3}+r_{3})}{m}$, we have

$S_{2}^{+}=\sum_{k\geq
n+\lceil\frac{a_{2}+2r_{2}}{2m}\rceil}g(a_{3}+r_{3}+m(2n-k+w))=\sum_{v\geq
n-w+\lceil\frac{a_{2}+2r_{2}}{2m}\rceil}g(a_{3}+r_{3}+m(2n-v)).$

This is equal to $S_{3}^{+}$ if

$n-w+\left\lceil\frac{a_{2}+2r_{2}}{2m}\right\rceil=n+\left\lceil\frac{a_{3}+2r_{3}}{2m}\right\rceil$

which follows from (1.5).

##  4\. Future work

The combinatorial nature of the identities in Theorem 1 raises the question of
whether a combinatorial proof could be found that directly relates the
partitions of the $a_{i}+2mn$, as opposed to relying on the connection Fine-
Dyson symmetry provides between the partitions of $n$ with rank $m$ and the
partitions of $n-|m|$.

In a separate direction, it would be interesting to find analogues of Theorem
1 for other partition statistics, such as the crank.

Finally, it is natural to wonder what more can be said about the distribution
of ranks. As mentioned in the introduction, an immediate consequence of (1.6)
is that the number of partitions with rank at least $\frac{n}{2}$ is
$p(\lfloor\frac{n}{2}\rfloor-1)$. More generally, (1.6) implies a formula for
the number of partitions with rank in intervals contained in $[n/2,n]$: if
$b\geq a\geq\frac{n}{2}-2$, then

$\left|\\{\lambda\in
P(n):\operatorname{rank}(\lambda)\in[a,b]\\}\right|=p(n-\lceil
a\rceil-1)-p(n-\lfloor b\rfloor-2).$

Using completely different techniques (the circle method), a few
aforementioned works ([Dys89], [BD16], [DM15]) provide asymptotic formulas for
$N(m,n)$ with $|m|\leq\frac{\sqrt{n}\log{n}}{\pi\sqrt{6}}$. Little is known,
to our knowledge, about the number of partitions with rank in ranges between
$\frac{\sqrt{n}\log{n}}{\pi\sqrt{6}}$ and $n/2$, and it would be very
interesting to obtain formulas for these counts.

## References

  * [AG88] G. E. Andrews and F. G. Garvan.  Dyson’s crank of a partition.  Bull. Amer. Math. Soc. (N.S.), 18(2):167–171, 1988.
  * [ASD54] A.O.L. Atkin and P. Swinnerton-Dyer.  Some properties of partitions.  Proc. London Math. Soc. (3), 4(2), 1954.
  * [BD16] K. Bringmann and J. Dousse.  On Dyson’s crank conjecture and the uniform asymptotic behavior of certain inverse theta functions.  Trans. Amer. Math. Soc., 368(5):3141–3155, 2016.
  * [DM15] J. Dousse and M. H. Mertens.  Asymptotic formulae for partition ranks.  Acta Arith., 168(1):83–100, 2015.
  * [Dys44] F.J. Dyson.  Some guesses in the theory of partitions.  Eureka (Cambridge), 8, 1944.
  * [Dys69] F. J. Dyson.  A new symmetry of partitions.  J. Combinatorial Theory, 7:56–61, 1969.
  * [Dys89] F. J. Dyson.  Mappings and symmetries of partitions.  J. Combin. Theory Ser. A, 51(2):169–180, 1989.
  * [Fin48] N. J. Fine.  Some new results on partitions.  Proc. Nat. Acad. Sci. U.S.A., 34:616–618, 1948.
  * [Fin88] N. J. Fine.  Basic hypergeometric series and applications, volume 27 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 1988.  With a foreword by George E. Andrews.
  * [HR00] G. H. Hardy and S. Ramanujan.  Asymptotic formulæin combinatory analysis [Proc. London Math. Soc. (2) 16 (1917), Records for 1 March 1917].  In Collected papers of Srinivasa Ramanujan, page 244. AMS Chelsea Publ., Providence, RI, 2000.
  * [Lew92] R. Lewis.  On some relations between the rank and the crank.  J. Combin. Theory Ser. A, 59(1):104–110, 1992.
  * [oei] Oeis foundation inc. (2021), the on-line encyclopedia of integer sequences, https://oeis.org/.
  * [Pak06] I. Pak.  Partition bijections, a survey.  Ramanujan J., 12(1):5–75, 2006.
  * [Ram21] S. Ramanujan.  Congruence properties of partitions.  Math. Z., 9(1-2):147–153, 1921.
  * [SG90] N. A. Santa Gadea.  On the rank and the crank moduli 8, 9 and 12.  ProQuest LLC, Ann Arbor, MI, 1990.  Thesis (Ph.D.)–The Pennsylvania State University.
  * [Wol] Wolfram Research, Inc.  Mathematica 8.0.