Toward Self-Improvement of LLMs via Imagination, Searching, and Criticizing

Authors: ye  tian
baolin  peng
linfeng  song
jin  lifeng
dian  yu
lei  han
haitao  mi
dong  yu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:35:14

Abstract: Despite the impressive capabilities of Large Language Models (LLMs) on various tasks, they still struggle with scenarios that involves complex reasoning and planning. Self-correction and self-learning emerge as viable solutions, employing strategies that allow LLMs to refine their outputs and learn from self-assessed rewards. Yet, the efficacy of LLMs in self-refining its response, particularly in complex reasoning and planning task, remains dubious. In this paper, we introduce AlphaLLM for the self-improvements of LLMs, which integrates Monte Carlo Tree Search (MCTS) with LLMs to establish a self-improving loop, thereby enhancing the capabilities of LLMs without additional annotations. Drawing inspiration from the success of AlphaGo, AlphaLLM addresses the unique challenges of combining MCTS with LLM for self-improvement, including data scarcity, the vastness search spaces of language tasks, and the subjective nature of feedback in language tasks. AlphaLLM is comprised of prompt synthesis component, an efficient MCTS approach tailored for language tasks, and a trio of critic models for precise feedback. Our experimental results in mathematical reasoning tasks demonstrate that AlphaLLM significantly enhances the performance of LLMs without additional annotations, showing the potential for self-improvement in LLMs.

Main paper: 
 introduction: 
 LLMs, trained on trillions of tokens with billions of parameters have shown unparalleled capabilities in a wide range of natural language processing tasks (Touvron et al., 2023b; Team et al., 2023; OpenAI, 2023) . Nevertheless, they continue to face challenges in scenarios requiring complex reasoning and strategic planning (Valmeekam et al., 2022; Stechly et al., 2024) . While advanced prompting approaches such as Chain, Tree, Graph-of-Thought (Wei et al., 2022; Yao et al., 2024; Besta et al., 2024; Ding et al., 2023) , it remains essential to fine-tune LLMs using a substantial volume of high-quality, supervised data to fundamentally improve the model performance (Nye et al., 2021; Lewkowycz et al., 2022; Chung et al., 2022) . This methodology is inherently limited by the scope and quality of data that humans can provide.Considering these challenges, the concept of self-correction and self-learning have been proposed as promising solutions (Madaan et al., 2024; Saunders et al., 2022; Chen et al., 2024) . Within these framework, LLMs typically operate by employing two main strategies: 1) they continuously refine their responses based on the feedback of their past responses, and 2) they extensively sample responses then learn from preferences judged by itself as reward models with PPO or DPO (Yuan et al., 2024a,b; Chen et al., 2024) . However, it remains a matter of ongoing research whether LLMs can effectively critique their own outputs to either enhance response quality or apply a scalar reward to indicate the quality of responses, especially in contexts demanding intricate planning and reasoning (Valmeekam et al., 2022; Stechly et al., 2024; Huang et al., 2023; Hong et al., 2023) . On the other hand, advanced search algorithms such as MCTS, combined with reinforcement learning, have enabled models to learn from self-play and achieve human parity or even surpass human performance in complex tasks such as the game of Go (Silver et al., 2016 (Silver et al., , 2017)) . This naturally raises a question: is it viable to leverage the strengths of MCTS alongside LLMs to inaugurate a novel paradigm of self-improving? More precisely, could the assimilation of MCTS empower LLMs to more effectively explore better responses, guided by strategic signals, and subsequently optimize these responses to enhance overall performance?To answer this question, we begin with a systematic examination of AlphaGo, identifying three critical aspects for its success: (i) The large volume of data, including self-play data. (ii) The use of tree search, which facilitates the exploration of potential moves through statistical sampling of the large search space. (iii) Accurate and unambiguous environment feedback; the direct and accurate feedback (win or loss) provided by the game of Go offers a clear and unequivocal learning signal (Silver et al., 2017) . The integration of MCTS with LLMs for self-improvement has several challenges: (i) Limited Data: High-quality annotated data for LLMs is generally scarce. Furthermore, how to construct of synthetic data for LLMs training, similar to AlphaGo's self-play data, remains unclear. (ii) Search Efficiency: The vast number of potential token combinations in natural language tasks results in an exponentially large search space, posing a significant challenge to the efficiency of MCTS (Ramamurthy et al., 2022) . (iii) Imperfect Feedback: In contrast to the clear win/loss feedback in Go, feedback in natural language tasks is often subjective and nuanced, without a straightforward measure of success.In this paper, we introduce ALPHALLM, an imagination-searching-criticizing framework designed for the self-improvement of LLMs . ALPHALLM consists of three key components, as illustrated in Figure 1 . First, an imagination component is designed to synthesize prompts, alleviating the issues of data scarcity. Second, we propose ηMCTS tailored for efficient searching in language tasks. Particularly, it has been show that planning at multiple levels of temporal abstraction is critical for RL problems with a long horizon and large action space (Sutton et al., 1999b; Peng et al., 2017; Luketina et al., 2019) . As such, we propose formulating the text generation process as options over a Markov Decision Process (MDP) problem, where each option represents the generation of a collection of tokens for a specific subtask, similar to the concept of chains in chain-of-thought prompting. This formulation improves search efficiency by substantially reducing the search depth. Additionally, we propose the use of state merge and adaptive branching factors to further enhance search efficiency by balancing the trade-off between search width and depth. Lastly, since accurate feedback is crucial to the success of MCTS, we introduce a trio of critic models to guide ηMCTS, including a value function for estimating expected rewards, a process reward model for assessing node correctness, and an outcome reward model for evaluating the overall trajectory. For complex tasks with which LLMs struggle assessing such as arithmetic computation and code execution, to ensure the accuracy of feedback, we augment the critics with the capacity to make dynamic decisions on which tools to use, when to use them, and how to use them effectively. After ηMCTS stage, we collect the trajectory with the largest reward from the critic models as the training examples to improve LLMs.The experimental results on mathematical reasoning tasks demonstrate that ALPHALLM can efficiently search for better responses and use them to improve LLMs' performance, forming an effective self-improving loop. Notably, based on Llama-2-70b and WizardMath-70B-V1.0, ALPHALLM can improve its performance from 57.8 to 92.0 on GSM8K and from 20.7 to 51.0 on MATH, performing comparably to GPT-4. 
related work: 
 Search with LLM Effective search strategy has been shown crucial for tasks that involve complex reasoning and planning, such as go (Silver et al., 2016) and math reasoning (Cobbe et al., 2021; Hendrycks et al., 2021) . For math reasoning tasks, various search methods have been studied. One direction of research (Zhu et al., 2024; Xie et al., 2024) designed beam search with dynamic pruning, where beam items of low quality are pruned. Another line of work (Yao et al., 2024; Long, 2023; Besta et al., 2024; Hao et al., 2023; Feng et al., 2023) maintains a tree or a graph that represents the current progress of solving the input question where potential branches are iteratively expanded. Both our approach and Feng et al. (2023) are based on the MCTS algorithm, while one main difference is how to define a search step: Feng et al. (2023) fix a search step to be either a token or a sentence, while our approach is more flexible on deciding steps. We have also carefully designed the MCTS process, incorporating multiple critique signals to guide the search more effectively and introducing adaptive search parameters for improved state exploration. As the result, our approach achieves much better performances.LLM Self-improving Being a key to the success of scalable oversight (Bowman et al., 2022) , self-improving for LLM aims to align the LLM to human preference and values mainly using the supervision from the knowledge inside the LLM (Zelikman et al., 2022 (Zelikman et al., , 2024)) . One crucial part of self-improving is how to obtain reliable signal of critique to distinguish between good responses from the LLM and bad ones. Initial work (Bai et al., 2022; Wang et al., 2022) first asks the LLM to generate input queries of diverse tasks and the corresponding outputs. They then rely on hand-crafted heuristic rules to filter out redundant or low-quality data pairs (e.g. the query is too long or too short). Since it is non-trivial to compose effective heuristic rule, later work (Sun et al., 2023; Li et al., 2023; Guo et al., 2024) proposes a few general principles or judging criteria and ask the LLM itself to evaluate the quality its responses based on these guidance, hoping that LLMs can automatically designate these principles into each data point to better guide data filtering. However, this requires LLMs to have strong abilities to apply these principles for each specific case and make correct judgements. Different from previous work, we propose to leverage the supervision from MCTS for LLM self-improvement: taking the outputs of MCTS to continue train the LLM. This is because the outputs from MCTS are usually in much better quality then standard nucleus sampling, and the large gap ensure that the LLM can self improve. 
problem formulation: 
 In this paper, we consider a LLM characterized by probability p θ and denoted as policy π θ . It takes a sequencex = [x 1 , • • • , x n ]as input, which is typically referred as prompt, to generate the responsey = [y 1 , • • • , y m ].In the context of LLMs, each x i and y i represents a token from a pre-defined vocabulary. The policy π θ operates in an autoregressive manner, where each token is generated sequentially, relying solely on the context provided by the previously generated tokens. The policy therefore constitutes a Markov process in which the conditional probability distribution p θ (y|x) can be decomposed and expressed with the chain rule as p θ (y|x) = m i=1 p θ (y i |x, y <i ). With this property, the text generation task can be formulated as an Markov Decision Process (MDP) problem consisting of (S, A, T, R, γ) in which, s t ∈ S represents the context information of current trajectory, i.e., current status of the generation process, e.g., a partial response to a prompt; a t ∈ A denotes a single action or sampled token from the vocabulary, leading to a transition to a new state s t+1 , by concatenating s t and a t ; r t = R(s t , a t ) manifest the evaluation of the generation to the prompt, reflecting the desirability or preferences of each state-action pair.This MDP framework sets the stage for applying Reinforcement Learning (RL) methods to optimize the policy π θ aiming to maximize the expected cumulative reward R. Base on these setups, we describe the self-improving problem. Given a LLM π θ and an initial dataset D 0 , which consists of N expert-generated prompt-response pairs {(x 0 i , y 0 i ) | i ∈ [N ]}, the goal of self-improving is to iteratively refine π θ to maximize the reward. The refinement process includes learning from synthesized prompts and corresponding responses. These responses are obtained using an advanced search algorithm that navigates the space of possible responses to maximize the expected reward. The detailed process is described in Algorithm 1 in Appendix. The primary challenges in forming an effective self-improving loop lie in synthesizing suitable prompts, efficiently searching over a vast action space, and obtaining precise feedback, which will be discussed in §4.MCTS is a sampling-based search algorithm for policy optimization in decision-making problems. It would iteratively build a search tree, by repeating four phases: selection, expansion, evaluation, and backpropagation. In the selection phase, it would recursively select the children from the root node by Upper Confidence Bound (UCB) (Auer et al., 2002) , U CB(i) = w i + C * 2 * ln Ni ni , where n i and N i are the visit counts for the node i and its parent respectively, C represents a hyperparameter balancing exploration and exploitation, and the w i is the average value of all descendant nodes of i. 
overview: 
 The architecture of ALPHALLM is depicted in Figure 1 , comprising three key components. Firstly, the imagination component is tasked with synthesizing prompts as learning examples. Secondly, an efficient search component, named ηMCTS, is proposed to search high-quality trajectories for optimizing the policy. Lastly, the search process is guided by critics specifically designed to provide reliable signals.Let D 0 = {(x i , y i ) | i ∈ [N ]} denote the initial dataset consisting of N expert-generated promptresponse pairs. The data synthesizing process aims to expand this dataset by generating a set of synthesized promptsD 1 = {(x 1 i , • • • ) | i ∈ [N ]}.The generation of each synthesized prompt x 1 i can be mathematically described as a transformation g applied to one or more examples from D 0 ,x 1 i = g(x 0 i1 , • • • , x 0 im , π 0 ) where x 0 i1 , • • • , x 0 im are selected examples from D 0 .The transformation function g controls the synthesis process, which can be a learnable function, manually defined heuristic rules, a strong LLM or the policy model itself π 0 equipped with data synthesis instructions. The data synthesizing process aims to enrich the diversity and complexity presented for the training of the policy model. Among various strategies, such as Self-instruct (Wang et al., 2022) , Evol-instruct (Xu et al., 2023) , we opt for a method akin to that described in Yu et al. (2023) .When applying MCTS to LLMs, it is natural to perform token-level search, where each token is considered as an action (Liu et al., 2023) . However, the substantial vocabulary size typical of LLMs presents a significant challenge i.e., conducting a deep search in such a vast space becomes increasingly complex as the search space expands exponentially. To mitigate this, some efforts proposed a sentence-level search, treating each sentence or step as a search node (Feng et al., 2023) . While this method reduces the search space, it might compromise the flexibility and effectiveness of applying MCTS to LLMs, which is particularly true for tasks where subtle variations in token can dramatically impact the outcome, or where a more comprehensive search beyond a sentence is necessary.Example Termination Token-level y0 → y1 → y2 → y3 → y5 → y6 → y7 → y8 token Sentence-level y0y1y2 → y4y5y6 → y7y8y9y10 new line Option-level y0 → y1y2 → y4y5y6 y7y8y9 → y10 termination functionIn previous works related to option/sentence level tree search (Feng et al., 2023; Yao et al., 2024) , it was a common practice to assume that each node in the tree has the same predefined width, i.e., branching factor. This assumption was due to the fact that unlike token-level MCTS with a limited action space, the sample space at the option-level is exceedingly large, with an unlimited number of token combinations. As a result, it was necessary to set a predefined maximum width for each node. However, this predefined branching factor is hard to set, as an improper choice can lead to a search tree that is either too shallow or too thin, resulting in an inefficient exploration of the search space.To quantify the error induced by the branching factor limit, we defined the branching error E ϕ (t). For a node t with a branching factor of m t , it aims to use the m t child options o i t ∼ D children t (where i ∈ {1, . . . , m t }) to represent all possible options. Consequently, for a legal option o j t ∼ π(s t ) from the option space, we can calculate the minimal value difference between it and the m t existing options, which captures the error associated with representing other possible options using the m t available options. It can be formulated asE ϕ (t) = E o j t ∼π(st) [min o i t |v π ϕ ([s t , o j t ]) -v π ϕ ([s t , o i t ])|],where v π ϕ is the value function which will be detailed in §4.4. Here we define the importance of node s t asI(s t ) = max o i t |v π ϕ ([s t , o i t ]) -v π ϕ (s t )|.For simplicity, we assume that the value of the children nodes are uniformly distributed (a detailed analysis of the Gaussian distribution can be found in Appendix A.4). Under this assumption, we show in Appendix A.3 that E ϕ (t) ≤ I(st) mt-1 . While E ϕ is less than some ϵ, we aim to use a smaller total number of nodes for efficiency.Theorem 4.1. The optimal branching factor m t in a tree search is set such that m t -1 is proportional to the node importance I(s t ), under the condition I(st) mt-1 ≤ ϵ. Refer to Appendix A.3 for the detailed proof.A similar concept has also been proposed in Taylor et al. (2014); Clouse (1996) . Intuitively, I(s t ) captures the maximum value deviation from the current state. When this value is small, there is no need to explore further on this node, as there will not be a significant difference by rolling out on this node. Conversely, if the value is large, it is worth trying different children. We set the number of children allowed for a node n(s t ) (after extracting 1) to be linear with this importance, using a factor α. In practice, to avoid extreme cases of large variance of I(s t ) in the early stage, we bound the number of children by depth-dependent constants c min (t) and c max (t), n(s t ) = max (c min (t), min (⌊αI(s t )⌋ + 1, c max (t))) .With n(s t ) determined, another issue is that options under the same node may be very similar, leading to many unnecessary sub-trees. Since we cannot directly control the o t ∼ π(s t ), one strategy to mitigate this issue is to utilize the concept of move groups, as discussed in Van Eyck & Müller (2012) . By merging similar nodes into the same group, we can increase the diversity among groups, thereby covering a larger problem space with limited search rollouts and making the search process more efficient.Here, we adapt the definition of node predicate p vM from Abel et al. (2018) and Fu et al. (2024) to represent whether two nodes are extremely similar. In practice, each time we generate a new option from the policy, we use heuristic functions as p vM to check its similarity with all existing groups. The heuristic function can either be a faster rule-based measurement (e.g., edit distance) or a model-based method (e.g., prompting a language model). Based on this, we decide whether to merge this option with a previous one or create a new group.The simulation operation which employs a rollout policy to project future trajectories from a given state, is crucial for an effective MCTS. This process significantly improves the efficiency of exploration and exploitation, and enhances the accuracy of reward estimation2 . Estimations made at the end of trajectories tend to have lower bias but higher variance; thus, simulating multiple possible trajectories yields low-bias, low-variance estimates, enabling a more informed and effective search process. Ideally, π θ would serve as the rollout policy, yet its computational demands render it impractical for the rapid simulations required by MCTS. To address this challenge, we propose the use of a smaller, specialized LM as the fast rollout policy π fast . Given a state s t , the fast rollout policy π fast efficiently continues generation until it reaches a termination condition, denoted as π fast (s t ).In ALPHALLM, we design three types of critic models to guide the search process.Value Function The value function, denoted as v π (s), represents the expected return starting from state s and following policy π thereafter, given by v π (s) = Eτ∼π[R(τ )|s 0 = s] where R(τ ) represents the discounted return of trajectory τ . To train a parameterized value function v π ϕ (s), given the promptsD = {(x i , • • • ) | i ∈ [N ]}, for each prompt x i , we generate multiple trajectories τ j i = {x i , o j i1 , o j i2 , • • • , o jiT } by following policy π for J times. A final reward r j i is assigned to indicate whether τ j i aligns with y i -for example, rewarding trajectories that contain correct answers in mathematical tasks or closely follow instructions as ground truth. We then construct a datasetD value = {(s j it , v j it ) | i ∈ [N ], t ∈ [T ], j ∈ [J]} where s j it = [x i • o j <it ] and v j it = r j i . The value function v πϕ is optimized by minimizing the mean squared error: (Feng et al., 2023) , v π ϕ is a LLM with an MLP layer on top to output a scalar on each token, using the scalar prediction at the last token of each state as the value.L ϕ = -E (s,v)∼Dvalue (v π ϕ (s) -v) 2 . Similar toPRM The value function often struggles with credit assignment problem (Sutton, 1984) and its learning could be inefficient due to delayed and sparse rewards (Sutton & Barto, 2018) . Therefore, we propose to incorporate PRM that introduces process supervision (Lightman et al., 2023) for direct option assessment. PRM generates intrinsic rewards (Chentanez et al., 2004) to encourage explorations of advantageous options, effectively mitigating issues of reward sparsity by providing immediate, action-specific rewards. Given a state s t and an option o t at time t, the PRM aims to predict the immediate reward r PRM t that results from taking option o t in state s t . Formally, the PRM is a function R(s t , o t ) → r PRM t . While PRM ideally requires quality labels for each state (Uesato et al., 2022) , due to the high cost and time involved in obtaining these, MC estimation with prefix sampling (Wang et al., 2023) is used as a proxy, which aligns with the objective of the value function. Instead of adding a MLP layer on top of the policy model for outputting a scalar reward (Ouyang et al., 2022) , we formulate PRM as a text generation task to best leverage LLM's intrinsic knowledge for assessing the quality of an option. We adapt the dataset constructed for the value function asD PRM = {(s it , o t , r PRM t )|i ∈ [N ], t ∈ [T ]} where r PRM tis the textual description of the reward, e.g., an option can be regarded as good if v it is larger than certain threshold. To train PRM, we initialize it from the policy model π and use the following prompt templates and typical language model loss. The prompt template is shown in Appendix A.5.ORM In additional to the value function and PRM, ORM is also used to guide MCTS. ORM is designed to evaluate options sequences in their entirety, assessing the extent to which the complete trajectory aligns with the desired end goal (Uesato et al., 2022; Lightman et al., 2023; Wang et al., 2023; Feng et al., 2023) . The outcome evaluation complements value function and PRM by offering a comprehensive assessment of trajectories. Crucially, ORM plays a vital role in the simulation stage of MCTS by providing more accurate signals on the terminal state, which in turn facilitates a more balance between exploration and exploitation strategies. ORM is formulated as a text generation task, similar to PRM. We leverage the same dataset for the value function training and constructD ORM = {(x i , o i 1:T , r ORM i )|i ∈ [N ]},where each instance includes a initial state or prompt x i , a sequence of actions or options o i 1:T taken from that state, and a textual reward r ORM i indicating the sequence's success or quality. Similarly, ORM is initialized from the policy model π and the following prompt templates and language model loss are used for training. The prompt template is shown in Appendix A.5.The final score evaluation of a state s is a weighted sum of the value function, PRM, and ORM:s(s) = β value • v π ϕ (s) + β PRM • PRM(s) + β ORM • E τ ∼π fast (s) [ORM(τ )],where τ ∼ π fast (s) represents trajectories starting from s under π fast , and β value , β PRM , β ORM are hyperparameters. In practice, we found that the value function model has better precision and calibration, while PRM has superior recall (Appendix A.10). Although ORM with fast rollouts provides low-bias, low-variance estimates, it still inherits some bias from π fast . Thus, combining these critics yields a stronger evaluation signal.The policy improvement an iterative process with each iteration containing two main steps: data generation and policy finetuning.In this step, we assume to have the current policy π θ k and synthetic prompts D k = {x k 1 , . . . } at the k-th round, where each x k 1 represents a question. We obtain the corresponding training data D k for policy π θ k by firstly performing ηMCTS on D k ( §4.3) and then sampling a trajectory y k i from the corresponding tree for each question x k i . Here we choose the trajectory that yield the highest critic score on the leaf node for each input question. Next, we filter out instances where the corresponding trajectory is substandard formingD k = {(x k i , y k i ) | f (x k i , y k i )> γ} where f represents a function for quality scoring, and γ indicates a threshold. There can be several ways to implement the function, and here we simply use the ORM ( §4.4).Policy finetuning With the obtained training data D k , we organize the data into the prompt templates shown in Appendix A.5. Then the policy π θ k is finetuned using target-loss:L θ k = E (x k i ,y k i )∼D k log π θ k (y k i |x k i ), resulting in an updated policy π θ k+1 . We leave other training methods, such as DPO (Rafailov et al., 2023) or PPO (Schulman et al., 2017) in future work. 
experiment setups: 
 ALPHALLM is generally applicable to a wide spectrum tasks. As an early exploration, in this paper, we conduct experiments on mathematical reasoning problems where the learning signals are clear to define i.e., , final answer is correct or wrong. We choose to evaluate on two widely used datasets GSM8K (Cobbe et al., 2021) and MATH (Hendrycks et al., 2021) . For GSM8K, we utilize the whole test set while for MATH, due to computation constraints, we utilize a subset following the same procedure of Lightman et al. (2023) . We evaluate the performance of predicting answers correctly for policy models. In addition, we calculate the average rollouts, represented by the number of nodes in the tree, as a measure of computational efficiency. We compare the performance of ALPHALLM with a suite of proprietary model, including OpenAI's GPT-4 and GPT-3.5, Anthropic's Claude-2, as well as Google's PaLM-2 and the gemini model family. To ensure a fair and consistent evaluation, we employ CoT as our primary prompting method. Additionally, we conduct comparisons with strong open-source models, including Llama-2-70b (Touvron et al., 2023a) and WizardMath-70B-V1.0 (Luo et al., 2023) .We select Llama-2-70b as the policy model for the GSM8K dataset and WizardMath-70B-V1.0 for the MATH dataset. To construct the training dataset for the value function, PRM and ORM, we generate 50 trajectories for each prompt and construct the training target following Section 4.4. Both PRM and ORM are initialized using the weights from the policy model, while the value function uses a smaller Llama-2-13b model, as we observed no performance gains from increasing the value function model size. In the design of ORM, tool usage is not incorporated for GSM8K. However, for MATH, we enhance ORM by incorporating tools like python sympy to assess the quality of a trajectory, in a manner similar to that described by Gou et al. (2023) . The training employ a learning rate of 1e-6 and are trained for one epoch. For the fast rollout policy model, we opt for the Abel-002-7B model (Chern et al., 2023) for both the GSM8K and MATH tasks for its high efficiency and superior performance. For the MCTS parameters, they are configured at different scales, as shown in Appendix A.6. We set β value , β PRM , and β ORM all to 1.0.For policy self-improving ( §4.5), we train the policy model up to 3 epochs, setting batch size to 128, learning rate to 5 × 10 -6 and minimal learning rate to 1 × 10 -6 . Linear warm-up and decay is used with warm-up percent to be 10%. We perform early stopping based on a devset held out from the training instances. For GSM8K experiments, we perform two rounds of self-improving, synthesizing 6.4k and 7.9k prompts (Yu et al., 2023) respectively to obtain the corresponding MCTS outputs for training. For MATH experiments, we only perform one round of self-improving due to limited computation resources, and 5.9k prompts are synthesized.The termination function for options can be either be learned or rule-based. In practice, for the GSM8K dataset, the termination condition occurs at the end of each line. This is based on the typical structure of this dataset, where each line represents a distinct step or point. For the MATH dataset, due to its complexity and the base model's tendency to generate many \n\n line breaks with some less meaningful content between them, termination occurs at the end of a line if a formula pattern is detected. During inference, if \n\n is encountered, we perform a rule-based check for formula patterns. It terminates if a pattern is found or continues generating until the next \n\n.Table 2 lists the performance comparisons of various methods on the GSM8K and MATH datasets. Our findings reveal that ALPHALLM, based on Llama-2-70B and WizardMath-70B-V1.0, utilizes only final answer annotations and continues to improve through training on responses from ηMCTS. This comparison underscores the efficacy and broad applicability of our imagination-searchingcriticizing self-improving framework. Moreover, when our model is augmented with ηMCTS decoding strategy, its performance markedly improves, achieving scores of 88.9 and 48.7 on the GSM8K and MATH datasets, respectively. Following two iterations of self-improvement using synthetic prompts, ALPHALLM demonstrates performance comparable to that of GPT-4. This suggests a viable approach to improving LLMs' capabilities in complex problem-solving tasks in a self-improving fashion, leveraging a minimal amount of labeled data. We also analyze the performance of various search methods in Appendix A.8.We assess the effectiveness of each component in ALPHALLM and report the results on GSM8K in Table 3 (a). Vanilla MCTS, configured with only the value function and a fixed number of children per node, achieves an accuracy of 79.5%. This serves as a reference point for evaluating the incremental benefits introduced by each additional component. The use of adaptive branching increae the accuracy to 84.9%. The addition of PRM improves the accuracy modestly to 85.9%, showing the effectivenss of process supervision for searching. A more significant improvement is observed with the introduction of ORM with fast rollout, which boosts the accuracy to 86.5%. Integrating state merging results in AB PRM FR-ORM SM LG-#Rollout Acc × × × × × 79.5 ✓ × × × × 84.9 ✓ ✓ × × × 85.9 ✓ ✓ ✓ × × 86.5 ✓ ✓ ✓ ✓ × 87.0 ✓ ✓ ✓ ✓ ✓ 88.9(a) Ablation study on GSM8K a further increase in accuracy, reaching 87.0%. Finally the combined of increasing the number of rollouts with the other components yields the best performance on this task.Table 3 (b) presents the ablation study of option formulation and the tool-augmented critic on the MATH dataset. Our proposed ηMCTS achieves an accuracy of 45.4 with 148 rollouts. When options are excluded, reverting to essentially sentence-level MCTS, the performance decreases to 44.1 with a noticeable increase in the number of rollouts to 198. This demonstrates that option formulation introduces enhanced flexibility to MCTS, enabling better performance with fewer search efforts. Furthermore, the most significant decrease in performance is observed when only intrinsic knowledge is utilized for ORM, which drops to an accuracy of 38.8. This suggests that the absence of an external tool critically impedes the ORM's capability to effectively assess challenging math problems.Figure 2 depicts a comparative results on GSM8K of two rounds of self-improving trained on trajectories collected using reranking and ηMCTS. We report the performance of greedy decoding, ηMCTS with a relatively small number of rollouts (50-60), and ηMCTS with a larger number of rollouts (200-300) for each model. We observe that 1) Models trained on the trajectories from reranking or ηMCTS outperform the initial policy by a significant margin. In addition, the performance can be iteratively improved with training suggesting that self-improving has the potential to achieve continual performance gain. 2) While both reranking and ηMCTS can generate high-quality trajectories for self-improving , ηMCTS is performant with high efficiency and better accuracy. Models trained on trajectories generated by it not only exceed the performance of those trained on reranked trajectories but also, when decoded with ηMCTS, demonstrate on par performance with GPT-4, revealing that ALPHALLM is an effective self-improving framework. We further analyze the impact of different hyperparameters and design choices for each component. Table 4 (a) shows that varying heuristic functions (with hyperparameters) for state merge has limited impact on performance. Table 4 (b) shows that, as the number of fast-rollouts increases, there is a corresponding improvement in performance. This is due to the reduction in the variance of the estimates. We used n = 4 in our experiments for better trade-off between performance and efficiency. Additional ablations on the choice of fast-rollout models, are provided in Appendix A.7. 
conclusion: 
 In this paper, we introduce ALPHALLM, an imagination-searching-criticizing framework designed for the self-improvement of LLMs without the necessity of additional annotations. At the heart of it is the integration of MCTS with LLMs. To tackle the inherent challenges associated with this integration, including data scarcity, the vastness of search spaces, and the subjective nature of feedback in language tasks, we introduce a data synthesizer for strategic prompt synthesis, an optimized MCTS tailored for efficient search in language tasks, and a trio of critic models to provide precise feedback. Our experimental findings on mathematical reasoning tasks reveal that ALPHALLM significantly boosts the performance of LLMs without requiring extra data annotations. Moreover, when decoded with ηMCTS, ALPHALLM performs comparably to GPT-4, highlighting the potential for self-improvement in LLMs. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Yes training and test details are mentioned.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: Error bars are not included in our experiment results due to the high computational cost.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We provide the information of the compute resources we used in the Appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Yes the research conform NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This work primarily focuses on foundational research in algorithm improvement and, as such, does not have a direct societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper has no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The datasets and models used in this paper are properly cited.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: A.1 Imagination, Searching, Criticizing and Learning Loop Algorithm 1: LLM self-improving loopInput Initial dataset D 0 = {(x 0 i , y 0 i ) | i ∈ [N ]}, policy model π 0 θ , reward model R, number of self-improving training loop K Output θ k for k ← 1, . . . , K do Generate synthetic prompts [x k ] = SYN(π k-1 θ , D k-1) Collect trajectories with search algorithm, e.g., MCTS guided by R.[ ŷk ] = MCTS(πk-1 θ , [x k ]) Construct dataset D k = {(x k , ŷk )} Update policy θ k = arg min θ L(π k-1 θ , D k ) endThe algorithm is shown in Algorithm 1.As illustrated in Figure 3 , option-level MCTS consists of the following operations:• Selection Starting from the root node, we iteratively select the child node based on Equation ??.• Expansion Once an expandable leaf node is selected, a new node is generated by starting with the previous state of the parent node as the initial option state. The option is then sampled using the policy π, and its completion is determined by the termination function β. • Simulation The scaled reward of the newly expanded node, as well as some simulated future trajectories are evaluated using the feedback functions, which is discussed in §4.4. • Backpropagation The average value of the newly generated node and all its ancestors is updated using the scaled reward from the evaluation step. Meanwhile, the visit counts for these nodes are also increased by one.Let V = {v π ϕ (s t , o 1 t ), v π ϕ (s t , o 2 t ), ..., v π ϕ (s t , o mt t )} be a set of m t values that are uniformly distributed. If the maximum and minimum values from V are v max and v min , the average gap between two consecutive values is given by vmax-vmin mt-1 . The upper bound of expected minimum distances from a new value v new to any value from V is achieved when v new is consistently positioned at the midpoint between two consecutive values, and it is given by vmax-vmin 2(mt-1) .Since v max -v min = 2I(s t ) for a uniform distribution, we can conclude that E ϕ (t) ≤ I(st) mt-1 . Theorem 4.1. The optimal branching factor m t in a tree search is set such that m t -1 is proportional to the node importance I(s t ), under the condition I(st) mt-1 ≤ ϵ.Proof. We can have the optimization problem as: minimize: m t subject to:I(s t ) m t -1 ≤ ϵIntroduce the Lagrange multiplier λ t for each constraint:L(m t , λ t ) = m t + λ t (ϵ(m t -1) -I(s t ))Now, let's find the gradient of the Lagrangian with respect to m t and λ t and set them to zero:∇ mt L = 1 + ϵλ t = 0 ∇ λt L = ϵ(m t -1) -I(s t ) = 0From the first equation, we get:λ t = - 1 ϵSubstitute this value of λ t into the second equation:ϵ(m t -1) -I(s t ) = 0Solving for m t , we get:m t = I(s t ) ϵ + 1Thus, m t -1 is proportional to the node importance I(s t ).A.4 Importance-Based Adaptive Branching Under Gaussian DistributionIf we assume that v π ϕ ([s t , o j t ]) and v π ϕ ([s t , o i t ]) are independent and identically distributed Gaussian random variables:v π ϕ ([s t , o j t ]), v π ϕ ([s t , o i t ]) ∼ N (µ, σ 2 ) The difference D ij = v π ϕ ([s t , o j t ]) -v π ϕ ([s t , o i t ]) will follow a normal distribution with:D ij ∼ N (0, 2σ 2 )To find the expected minimum absolute difference between v π ϕ ([s t , o j t ]) and the closest v π ϕ ([s t , o i t ]), we need to consider the distribution of the minimum of m t Gaussian differences.The expected minimum value of m t absolute differences can be approximated using properties of order statistics for Gaussian distributions.For a set of m t independent normal random variables with variance 2σ 2 , the expected minimum absolute difference, E[min i |D ij |], can be approximated by:E ϕ (t) ≈ σ √ 2 √ m tThis approximation arises from the fact that the expected minimum value of the absolute deviations of normally distributed random variables scales with the inverse of the square root of the number of samples.Then, assume the range of the m t samples areR m = max(v π ϕ ([s t , o i t ]) -min(v π ϕ ([s t , o i t ]), the the expected range E[R m ] of m t samples from a normal distribution can be approximated using properties of extreme values of Gaussian distributions. The range R m can be approximated as: R m ≈ σ(z 0.9995 -z 0.0005 )where z p is the p-th percentile of the standard normal distribution. It can converge toR m ≈ σ 2 ln(m t ) 2 - ln(ln(m t ))4 ln(m t ) For simplicity, we can approximate the range using the primary term, which captures the dominant behavior:R m ≈ σ 2 ln(m t ) Then we haveE ϕ (t) ≈ √ 2 √ m t R m2 ln(m t ) Knowing that for all distributions,I(s t ) ≥ R m 2 We have E ϕ (t) ≤ I(s t )m t ln(m t ) Then to find the optimal m t , the optimization problem is minimize:m t subject to: I(s t ) m t ln(m t ) ≤ ϵTo solve this optimization problem, we can first rewrite the constraint in terms of m t .m t ln(m t ) ≥ I 2 (s t ) ϵ 2Now, let's define a new function g(m t ) = m t ln(m t ). We want to find the minimum m t such that g(m t ) ≥ I 2 (st) ϵ 2 . To do this, we can find the derivative of g(m t ) and set it to zero to find the critical points.g ′ (m t ) = d dm t (m t ln(m t )) = ln(m t ) + 1Setting the derivative to zero:ln(m t ) = -1 m t = e -1However, this critical point corresponds to a minimum of the function g(m t ), and we are interested in the minimum m t that satisfies the constraint g(m t ) ≥ I 2 (st) ϵ 2 . Since the function g(m t ) is increasing for m t > e -1 , we can find the minimum m t by setting g(m t ) = I 2 (st)ϵ 2and solving for m t : m t ln(m t ) = I 2 (s t ) ϵ 2 This can not be solved directly, but we can still observe that there is a positive correlation between m t and I(s t ). For MATH experiments that take a WizardMath V1.0 70B as the policy, we adopt their proposed system prompt for self-improving. For GSM8K experiments taking Llama2 70B pretrain as the policy, we use the following system prompt.A chat between a curious user and an artificial intelligence assistant.\n The assistant gives helpful, detailed, and polite answers to the user's questions.\n User: x i \n Assistant: y iWe set the MCTS parameters in Table 5 .Fast-rollout model Using Llama-2-70b instead of Abel-7B-002 improves performance by reducing bias from a smaller model, but Abel-002-7B is faster with similar computational resources due to higher concurrency and quicker processing. The details can be found in Table 6 . Although ALPHALLM demonstrates improvements over base models, its performance in greedy sampling is substantially inferior to that observed when decoded with ηMCTS. This indicates that the full potential of MCTS for self-improvement in LLMs has not yet been fully realized. Two potential factors contributing to this issue have been identified: a) the self-improvement loop may not be leveraging sufficient data; and b) the base model may be limited in its capacity for rapid learning. Addressing these concerns could lead to more significant improvemens. (iii) In our existing framework, the critic models remain static. We will explore mechanisms to continually update critic models to adapt to new policy models. This will help ensure the discriminator-generator gap and improve the overall training dynamics. (iv) The evaluation of ALPHALLM has been limited to mathematical reasoning tasks. To verify the generalizability and broader applicability of the framework, future research will need to extend its application to other domains.Justification: The code is available at https://github.com/YeTianJHU/AlphaLLM.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Typically, the closer the simulation is to the termination state, the more accurate the reward estimation becomes. 


Decision: The paper draws from AlphaGo to introduce AlphaLLM, a combination of search, simulation, and critic for the self-improvements of LLMs. AlphaLLM uses Monte Carlo Tree Search (MCTS) in a self-improving loop to improve the performance of LLMs. Results on MATHS and GSM8K seem promising. In spite of the interesting results, the reviewers have been concerned with the clarity of the paper, and the presentation of methods, details of how the approach works in the main paper. We recommend the paper for acceptance as a poster conditional on the implementation of the following:
- bring appendix 6 to the main paper
- include responses to Reviewer PPNk in the main paper, including the relevant citations and the clarificaitons
- all reviewers requested the authors include more implementation details, evaluation, and the code
Thank you

Reviews: review: paper_summary: paper_summary: The paper introduces a method for self-imporvement of LLMs called AlphaLLM. The method consists of three components: 
Generation of expert trajectories
Effective Monte-Carlo-Tree-Search over the LLM outputs (nablda-MCTS)
A series of critics for evaluating reliable reward signal (value function, Process Reward Model, Outcome Reward Models)

The method can be used as a rollout mechanism to generate high quality outputs. To help deal with the large branching factor, the authors propose three subcomponents:
State space is set to Options, which is neither token space nor sentence space, but a variable length sequence which terminates based on an auxiliary heuristic beta.
States are merged using another auxiliary function p_vM
Fast rollouts are used with a smaller LLM to help estimate. 

The authors then demonstrate incredibly strong empirical results on both MATHS and GSM8K. Training with the proposed method on LLAMA-2-70b is able to achieve 51% on the MATH dataset.
strength_weakness: strength_weakness: Lots of experimental details are missing. There is very little discussion of how AlphaLLM is trained or what base model it is (it's only mentioned in the introduction!). In particular, no information is given about the actual training of either the policy (LLM), the Critics, or the heuristic functions p_vM.

The explanation of the options is lacking - even looking at A.2 the explanation of options is unclear. Is Beta learnt as a function or generated in some other way? Are the set of options I, learnt before a rollout or generated on the fly?

Ablations are missing - in particular using different state methods, removing the Importance-Based Adaptive Branching, State Merge or Option-Level MCTS.

The prompts in the appendix are reduced so we can’t replicate.

No Code provided.

Weird choice of baselines - surely to keep evaluations consistent with other LLMs, you should allow models to generate the same amount of output tokens with access to the PRM or ORM? I find it hard to believe COT on Claude-2 is a fair comparison, when the amount of optimisation pressure applied to multiple components of the method (including gradient updates).


There is no example of a rollout provided.
questions: questions: - What policy was used in the end for the fast rollout?
- The prompt templates are missing key parts - [A detailed rubric that specifies how to evaluate a step of a task] would be helpful if shared. - In particular when comparing to GPT-4 or other model perform was an equally informative prompt used? (Or at least a prompt of equal input tokens).
- If the synthetic data generated is used few-shot by llama2, how does your model perform?
- I think the related work is missing some key papers such as: [https://arxiv.org/abs/2203.14465] (the STAR family of papers)
limitations: limitations: The paper in its current form is not replicable.
paper_summary: paper_summary: The paper proposes AlphaLLM, a tree-search enhanced framework with a few improvements over Data Synthesizing, option-level MCTS, Importance-Based Adaptive Branching, state merging, fast rollout, critic function and policy improvement process. Experimental results verify the framework's effectiveness on GSM8k and MATH.
strength_weakness: strength_weakness: 1. The writing is not clear enough. It is not that clear to me how the option-level is implemented to separate sentences (how the Termination function is determined).
2. There are many different components in the pipeline design but the ablation studies are not enough to validate them one by one. For example, It at least need to involve:
2.1 Comparison with other heuristic search methods, for example: (1) the beam-search + value function described in [1, 2]) (2) majority-vote or reranking with ORM.
2.2 Wall time or token consumption comparison between different methods.
2.3 The ablation studies seem to be too simple to present how different components can really influence the performance. Pure with/without results seem to be too simple. More experiments like how to control the hyperparameter for these things are required. For example, how different heuristic functions can influence the State Merge, how different fast rollout model can influence the effiency, how the thresold in ORM in the process of data generation can influence the improvement process, etc.


Reference
[1] Feng, Xidong, et al. "Alphazero-like tree-search can guide large language model decoding and training." arXiv preprint arXiv:2309.17179 (2023).
[2] Yu, Fei, Anningzhe Gao, and Benyou Wang. "Outcome-supervised verifiers for planning in mathematical reasoning." arXiv preprint arXiv:2311.09724 (2023).
questions: questions: 1. What is the difference between value function training and PRM training? From the description it seems that the PRM's training is exactly the same as value function training in Monte-Carlo estimation (except you tend to take more simulations starting from a fixed state). 

Also, it seems that the technique described in the critic section has almost been described in many previous works: value function training in [1], PRM training in [2, 3], and ORM in [4], the author needs to clarify more on their own contributions and make proper citations.

2. One difference between your work and [1] is that they leverage the value function itself to backward (like AlphaZero) while you are using the fast model to rollout to reach the terminal state, which is like the initial version of AlphaGo (where they have a fast-move network) and [5]. What do you think of these differences and why do you make this design choices?


Reference
[1] Feng, Xidong, et al. "Alphazero-like tree-search can guide large language model decoding and training." arXiv preprint arXiv:2309.17179 (2023).
[2] Wang, Peiyi, et al. "Math-shepherd: A label-free step-by-step verifier for llms in mathematical reasoning." arXiv preprint arXiv:2312.08935 (2023).
[3] Lightman, Hunter, et al. "Let's verify step by step." arXiv preprint arXiv:2305.20050 (2023).
[4] Uesato, Jonathan, et al. "Solving math word problems with process-and outcome-based feedback." arXiv preprint arXiv:2211.14275 (2022).
[5] Hao, Shibo, et al. "Reasoning with language model is planning with world model." arXiv preprint arXiv:2305.14992 (2023).
limitations: limitations: See questions and weaknesses.
paper_summary: paper_summary: This paper proposes an imagination-searching-criticizing approach called ALPHALLM to enhance the capabilities of large language models (LLMs). ALPHALLM integrates Monte Carlo Tree Search (MCTS) with LLMs to establish a self-improving framework.
strength_weakness: strength_weakness: - Given only final math answer annotations, ALPHALLM essentially performs the final-label (reward) classification problem and tree search based on the predicted reward to generate rationales for each final answer. It is still unclear how ALPHALLM could outperform other LLM-SFTs that utilize both rationale annotations and final answer annotations.
- ALPHALLM is a general framework. The authors should apply ALPHALLM to other tasks where learning signals are clear to demonstrate the overall effectiveness of this self-improvement framework.
questions: questions: - Have you ever tried using your value/reward function to perform RL fine-tuning with PPO?
limitations: limitations: None.
paper_summary: paper_summary: This paper introduces ALPHALLM, which is an imagination-searching-criticizing framework designed for self-improvement. Inspired by AlphaGo, authors integrate MCTS and LLMs to establish the self-improvement loop. Additionally, authors proposed eta-MCTS, which is a decoding method used to reduce the search space. The experiments show that ALPHALLM can increase LLMs’ reasoning ability obviously, especially combined with eta-MCTS decoding.
strength_weakness: strength_weakness: 1. It could be more clear in some parts and including some examples would be helpful. For example, in the part of 4.2 data synthesizing, I’m curious about how the synthesized data looks like. 
2. Authors identify that one of the challenges in working on LLMs’ self-improvement is the difficulty to get clear evaluations, and they proposed some method to get the evaluations, i.e. value function, PRM, ORM. But they do not discuss whether these methods are reliable to get perfect feedback.
questions: questions: Please refer to the part of weaknesses.
limitations: limitations: Limitations are sufficiently discussed.

Comments: title: Thank you for your feedback
Thank you for your feedback
Thank you for your feedback
Thank you for your feedback
Thank you for your feedback
Thank you for your comments.
Rebuttal Supplement: References
Rebuttal Supplement: Templates, Examples and References
comment: Thank you and we appreciate your feedback.
Thank you for the constructive feedback! We agree that a specific analysis between human-annotated rationales with those generated by ALPHALLM is valuable. Indeed, we have already provided evidence in the fine-tuning results. For instance, in Table 2 (around line 313), we show that ALPHALLM, trained with self-generated rationales, outperforms LLaMA-2 70B SFT, which uses human-annotated rationales. This empirical evidence could support the hypothesis that the rationales generated by ALPHALLM are more effective. We also agree that providing additional examples of these rationales and analyze the differences could provide deep insights. We will definitely include this analysis in the appendix in the next version. 

Regarding the implementation details, we have included additional ablations and details in our response to Reviewer PPNK and Reviewer SX7Z. We kindly ask you to review those additional results to see if they address your concerns. We understand that some details (e.g. Appendix A.6) might be overlooked without a thorough review of the appendix. To further ensure the reproducibility of our results and to facilitate the verification of each component of our method, we are also committed to providing the codebase associated with ALPHALLM. Thank you for your understanding!
Thank you for your positive feedback. We will ensure that these explanations are included in the main paper to enhance clarity.
I am satisfied by the response, but do remember to include these explanation to make things more clear in the main paper. I will raise my score to 6.
Thank you for your insightful comment! We agree that the training objective of the MC proxy is indeed the same as that of the value function, and both the estimated values should tend to be the same as long as the MC samples and data used for training the value function go to infinity. The reason we adopted this approach is due to the high cost and time involved in obtaining quality labels like [1] for each state. Therefore, we adapted the PRM used in [2,3] as a proxy .

In practice, this approach has proven to be useful. The value function exhibits better precision and calibration, while PRM has superior recall. By integrating these models, we observed an overall performance improvement from 84.9% to 85.9% on GSM8K.

In future work, we plan to explore additional methods to obtain more accurate estimations of the quality of the current step. We appreciate your valuable feedback and thank you once again for your contribution to our research.


[1] Lightman, Hunter, et al. "Let's verify step by step." arXiv preprint arXiv:2305.20050 (2023). 
[2] Wang, Peiyi, et al. "Math-shepherd: A label-free step-by-step verifier for llms in mathematical reasoning." arXiv preprint arXiv:2312.08935 (2023).
[3] Jiao, Fangkai, et al. "Learning planning-based reasoning by trajectories collection and process reward synthesizing." arXiv preprint arXiv:2402.00658 (2024).
Thank you for your response. Below is my feedback:

- To support the hypothesis that the rationales generated by ALPHALLM are more robust and aligned, the author should provide additional examples of these rationales and analyze the differences between human-annotated rationales and those generated by ALPHALLM. Without this, the theoretical strength of ALPHALLM remains unclear.
- After reading comments from Reviewers SX7Z and PPNK, I agree with their concerns about the implementation details. I also believe that the code should be provided to allow for verification of each component of your method.

Due to the main concerns raised above, I have decided to lower my score. However, given that the experimental results are indeed remarkable, I still support the acceptance of this paper.
Thanks for the reply and these address some of the questions. I will maintain my score.
Despite the difference on architecture and training loss, the clarification on formulation difference makes me still confused:

"Value function training focuses on estimating the expected FUTURE return of a given state or state-action pair. In contrast, PRM evaluates the quality of the current state or node. While PRM ideally requires quality labels for each state, due to the high cost and time involved in obtaining these, MC estimation is used as a proxy."

Since you are using MC estimation, then this PRM is exactly the same for estimating the expected future return of a given state or state-action pair, so it should fall back to value function training.
Thank you for your constructive suggestions! We truly appreciate your feedback and will work on improving the writing to make the paper clearer and more accessible.

Regarding the ablations, could you please specify any particular ablations you feel may be missing? In addition to the ablations we included in our submission (with and without certain components), we have also provided more detailed ablations, including hyperparameter controls, in our response to Reviewer PPNk. We would be happy to consider incorporating any additional specific ablations you might suggest.

As for the baselines, we have included a similar discussion in Section 5.3 and Figure 2. The result demonstrates that, in self-improving, using \etaMCTS for data collection outperforms Reranking (BoN) in various aspects, including the improved policy itself, as well as when combined with reranking and \etaMCTS in both iterations 1 and 2. We believe this evidence shows that our method generates more informative data points.

Thank you again for your valuable feedback. We will keep refining our paper to enhance its clarity and overall presentation.
I thank the authors for these comments and apologise for not seeing the training section earlier. 

My concerns about the writing and lack of correct ablations have been re-enforced by the other reviewers, I believe stand.

I still think your baselines are wrong, you want to show your method relative to other methods either generates more informative datapoints (similar to compare to Lightman's Process-based supervision) or that this is just a method for boostrapping from a weak learner (in which case i imagine using BoN with these new value functions should get a similar result). 

The paper is still of weak quality in my opinion but the results are truly exciting. I think if the authors can make a deliberate effort to tidy up writing and compare to baselines with their base models. 

I'm updating my score to an accept because the result is really good but this paper still really lacks clear communication or generating knowledge on whats happening here.
Due to the word limit, we included the references used in the rebuttal for reviewer PPNk in this comment.

We would also like to greatly thank the reviewer PPNk for the valuable feedback and insightful questions. We appreciate the recognition of our technical contributions and the potential of our algorithm. The reviewer's questions and suggestions have been crucial in improving the clarity of our work.

## Reference

[1] Feng, Xidong, et al. "Alphazero-like tree-search can guide large language model decoding and training." arXiv preprint arXiv:2309.17179 (2023). 
[2] Wang, Peiyi, et al. "Math-shepherd: A label-free step-by-step verifier for llms in mathematical reasoning." arXiv preprint arXiv:2312.08935 (2023).
[3] Lightman, Hunter, et al. "Let's verify step by step." arXiv preprint arXiv:2305.20050 (2023). 
[4] Uesato, Jonathan, et al. "Solving math word problems with process-and outcome-based feedback." arXiv preprint arXiv:2211.14275 (2022).
Due to the word limit, I am providing the prompts, examples, and references used in our rebuttal for reviewer SX7Z in this comment.

## A. Rubrics in Prompt Templates
As mentioned in our response to **[W5]**, the prompt templates for PRM and ORM are detailed in Appendix A.5 , with specific rubrics for PRM and ORM are

- PRM:
```
You are given a math problem, followed by a step-by-step reasoning process. Your task is to read the problem carefully, understand the solving steps, and check the correctness of the last reasoning step. Output 'True' if the last step is correct, and 'False' otherwise.
```
- ORM:
```
Assess a solution including final answer to a given math problem by following below steps.\n- Evaluate the method used for solving the problem.\n- Review each calculation step for accuracy. Check for computational errors, incorrect formula applications, or arithmetic mistakes.\n- The solution should use all the information provided in the question.\n- Examine the final answer for correctness, considering the calculations and method used.\n.
```

## B. Rollout Example
Here's a detailed rollout example addressing **[W7]**:

Consider the following GSM-like question:

```
Question: Sandy's monthly phone bill expense is equal to ten times her age now. In two years, Sandy will be three times as old as Kim. If Kim is currently x years old, calculate Sandy's monthly phone bill expense.\nIf we know the answer to the above question is 340, what is the value of the unknown variable x?\n
```

A node in the second layer could have the following content:

```
Answer: We know that Sandy's monthly phone bill is 10 times her age. In two years, Sandy will be 3 times as old as Kim. The sum of Sandy's age now and 2 years is 3 times the sum of Kim's age now and two years.\nSandy's age now is 340/10 = <<340/10=34>>34. In two years, Sandy's age will be 34 + 2 = <<34+2=36>>36.\n
```

The parent of this node has the content:

```
Answer: We know that Sandy's monthly phone bill is 10 times her age. In two years, Sandy will be 3 times as old as Kim. The sum of Sandy's age now and 2 years is 3 times the sum of Kim's age now and two years.\n
```

And one of its fast-rollout paths could be:

```
The sum of Sandy's age now and 2 years is 36. The sum of Kim's age now and two years is x + 2.\n36 = 3(x + 2)\n36 = 3x + 6\n3x = 30\nx = 10\n#### 10
```

## C. Reference
[1]. Zhang, Dan, et al. "ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search." arXiv preprint arXiv:2406.03816 (2024).
[2]. Yu, Longhui, et al. "Metamath: Bootstrap your own mathematical questions for large language models." arXiv preprint arXiv:2309.12284 (2023).
[3]. Li, Xian, et al. "Self-alignment with instruction backtranslation." arXiv preprint arXiv:2308.06259 (2023).
[4]. Guo, Hongyi, et al. "Human-instruction-free llm self-alignment with limited samples." arXiv preprint arXiv:2401.06785 (2024).