Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding
Authors: Jiacheng Liu
Andrew Cohen
Ramakanth Pasunuru
Yejin Choi
Hannaneh Hajishirzi
Asli Celikyilmaz
Venue: COLM (2024)
Keywords: text generation,decoding,search,reinforcement learning,ppo,monte-carlo tree search
TL;DR: We adapt and apply AlphaGo-style MCTS decoding to post-RLHF language models, and achieve superior generation quality.

Abstract: Inference-time search algorithms such as Monte-Carlo Tree Search (MCTS) may seem unnecessary when generating natural language text based on state-of-the-art reinforcement learning such as Proximal Policy Optimization (PPO). In this paper, we demonstrate that it is possible to get extra mileage out of PPO by integrating MCTS on top. The key idea is not to throw out the *value network*, a byproduct of PPO training for evaluating partial output sequences, when decoding text out of the *policy network*. More concretely, we present a novel *value-guided* decoding algorithm called **PPO-MCTS**, which can integrate the value network from PPO to work closely with the policy network during inference-time generation. Compared to prior approaches based on MCTS for controlled text generation, the key strength of our approach is to reduce the fundamental mismatch of the scoring mechanisms of the partial outputs between training and test. Evaluation on four text generation tasks demonstrate that PPO-MCTS greatly improves the preferability of generated text compared to the standard practice of using only the PPO policy. Our results demonstrate the promise of search algorithms even on top of the aligned language models from PPO, and the under-explored benefit of the value network.

Published as a conference paper at COLM 2024
Don't throw away your value model! Generating more preferable text with Value-Guided Monte- Carlo Tree Search decoding
Jiacheng Liu 2 Andrew Cohen *
Ramakanth Pasunuru*
Yejin Choi 9
Hannaneh Hajishirzi Asli Celikyilmaz
Paul G. Allen School of Computer Science & Engineering, University of Washington
FAIR, Meta A Allen Institute for Artificial Intelligence
liujcêcs, wwwhington edu
"Work done as visiting researcher FAIR, Meta.
Abstract
Inference-time search algorithms such as Monte-Carlo Tree Search (MCTS) may seem unnecessary when generating natural language text based on state-of-the-art reinforcement learning such as Proximal Policy Optimiza- tion (PPO). In this paper, we demonstrate that it is possible get extra mileage out of PPO by integrating MCTS on top. The key idea is not throw out the value network, a byproduct of PPO training for evalu- ating partial output sequences, when decoding text out of the policy net- work. More concretely, we present a novel value-guided decoding algorithm called PPO-MCTS, which can integrate the value network from PPO to work closely with the policy network during inference-time generation. Compared to prior approaches based on MCTS for controlled text gener- ation, the key strength of our approach is to reduce the fundamental mis- match of the scoring mechanisms of the partial outputs between training and test. Evaluation on four text generation tasks demonstrate that PPO- MCTS greatly improves the preferability of generated text compared to the standard practice of using only the PPO policy. Our results demon- strate the promise of search algorithms even on top of the aligned language models from PPO, and the under-explored benefit of the value network.
Task: Generate rositive-sentimen continuation this wegative-sentimaan prompt
penso0
peo (07
%
001
"You dangerous altuusion occ
Appl
dangerous with
fa
"Tor can't one dontiecus etsustonn with om bad decretmm gourp
"ou oxn't me dandteerre attustion with mi persoon KAZS. pyneyttiing we
POSITIVE
Figure 1: Text decoding methods. Left: greedy decoding from PPO policy does not satisfy the task constraint. Right: PPO-MCTS with the same PPO policy and additional value model satisfies the task constraint. p is the prior probability given by the PPO policy model; V and Q are derived from the output of the PPO value model. (Depicted is the final Monte-Carlo search tree for decoding the first token. The full sequence is decoded by repeating this process.)
1

---

Published as a conference paper at COLM 2024
1 Introduction
Numerous text decoding algorithms have been introduced to improve the controllability and human alignment of text generation by language models (LMs). Guided decoding [Lu et al.) 2020; Welleck et al. 2022 inter alia), where the generative LM is steered by an auxiliary evaluation function that captures goal satisfaction by partial outputs, has been of particular interest, since this framework can be combined with search algorithms to achieve more desirable outcomes. However, in most prior work, the choice of evaluation function can be suboptimal, relying on rule-based heuristics or borrowing classification models that are not trained evaluate incomplete sequences.
Our key observation is that the value model produced from Proximal Policy Optimization (PPO) (Schulman al., (017)) is a natural candidate for the evaluation function in guided decoding. PPO has become the de facto algorithm for aligning language models to human feedback using reinforcement learning (RLHF) (Ouyang et al. 2022 ApenAl 2022 2023
Bai et al. 2022 Touvron et al. 2023b). In order to train the policy model, PPO additionally learns a value model that estimates the expected return of partial outputs when follow- ing the current policy. Therefore, this value model is designed to evaluate incomplete sequences. However, Al researchers and practitioners usually discard the value model checkpoints when saving or releasing their PPO models, leaving the usefulness of such value models under-explored. Not utilizing the information learned by the value model limits the performance of PPO. For example, in our experiments, we observe that decoding solely from the PPO policy model can yield undesirable outputs (e.g., Figure 1).
We propose to apply guided decoding on LMs trained with PPO, using the associated value model as the evaluation function. The value model estimates the expected return for a partial sequence to be completed by following the associated policy, and as we will show later, it is suitable to guide decoding because: (1) it is trained to predict the value for partial sequences; (2) it is specifically tailored for the associated policy. In particular, we propose to use Monte-Carlo Tree Search (MCTS) (Kocsis & Szepesvari (006) to search for output sequences with higher rewards. MCTS is shown to be an indispensable inference-time component that helps the AlphaGo series reach superhuman performance on Go (Silver let al. 2016 2017), and is recently employed to steer LMs (Zhao et al.. 2023b Hao et al. Chaffin et al., 2021). In this work, we apply guided decoding (MCTS, in particular)
2023
on polpcy/vallllleo /value model pairs trained with PPO. We refer to our decoding method as PPO-
MCTS
Figure shows an example for applying PPO-MCTS on text generation task where de- coding from the PPO policy alone fails the task. The objective is to generate a positive- sentiment continuation to a given negative-sentiment prompt, "You can't fix one dangerous sifuation with one The PPO policy indicates "bad" as the most likely next token, and following that policy yields negative-sentiment continuation, failing the task. However, with PPO-MCTS, a search tree is built and tokens are decoded based on the statistics obtained from evaluating sequences with a few steps of look-ahead, and thus "person" " be- comes the most likely next token. Following this algorithm successfully yields a positive- sentiment continuation.
To successfully combine PPO models and MCTS decoding, we introduce a novel and yet critical modification to the original MCTS algorithm: initializing the Q of children actions from the V of their parent node to encourage exploration. We also present approximation techniques when the task or experimental setup does not allow exact computation. We
also discuss some implementation choices in PPO training and their implications on the necessity of certain approximations. More details can be found in S
Experiments on four text generation tasks show that PPO-MCTS generates text with higher preferability than standard decoding (e-g., top-p sampling (Holtzman et al. 2019)):
1. On sentiment steering (using the Tex dataset (Gokaslan & Cohen 2019), PPO-MCTS achieves a success rate that is 30% (absolute) higher than direct sampling from the same PPO policy, while maintaining other desirable properties such as fluency,
Source code is available at htttas///gtthu...c/////gg///////
2

---

Published as a conference paper at COLM 2024
diversity, and topicality, Human evaluation favors a 20% (absolute) margin.
PPO-MCTS fa
over the PPO policy by
2. On toxicity reduction (using the pereToxxciiyPProopptt dataset (Gehman et al., 2020 PPO-MCTS reduces the toxicity generated text by 34% (relative). Human evaluation favors PPO-MCTS over the PPO policy by 30% (relative) margin.
On knowledge introspection (evaluated on several QA benchmarks), PPO-MCTS pro- duces commonsense knowledge that is 12% (relative) more useful to downstream QA tasks.
4. On creating helpful and harmless chatbots (using the HH-RLHF dataset (Bai et al. 2022)), PPO-MCTS produces dialog responses with 5% (absolute) higher win rate in human evaluation.
Our empirical results demonstrate that PPO-trained policies can benefit from guided de- coding, and that the PPO value model is both theoretically justified and empirically effec- tive in guiding the search in MCTS. We additionally show that PPO-MCTS C00-MCTSSMRA outperforms
a longer training of PPO or using best-of-n decoding, both of which directly optimize for the rewards. Our results unlock the valuable potentials of the value models, and we rec- ommend the community to consider saving the value model for enhanced inference.
2 Preliminaries
In this section, we introduce some preliminaries that support the discussion of our method, including common notations in text generation, guided decoding, and Proximal Policy Optimization.
2.1 Notation
In the most common formulation of text generation, an LM estimates the probability dis- tribution of the next token xı given prior context X<t, (x(xxxx<)) and decodes the next token by referencing this probability. Common decoding algorithms include greedy decod- ing, beam search, temperature sampling, and top-p sampling (Holtzman et al. (2019). Text generation tasks usually provide a prompt w and asks for continuation X1.T, in which case the LM models (x x.)).
When text generation is cast as sequential decision making problem Puterman 1994), state is the prompt plus the response generated far, and an action is the next generated token. Formally, s = (w,x<1) and (; = x,. The LM is referred to as a policy model po (a (s:).
In controlled text generation, the goal is often characterized by reward function r(ST+1), where ST+1 (w, is the complete generated text. This function encodes preferable properties of the generated text, such as desirable sentiment, low toxicity, lexical con- straints, and other types of human preference. The reward function may be either rule- based or modeled with neural classifier or regressor. Certain methods, including the guided decoding methods that we describe below, guide text decoding to increase the reward of outputs.
2.2 Guided Decoding
Guided decoding employs an evaluation function to evaluate states with partial output, (w, xx(), against some goal. As with the reward function, the evaluation function may be either rule-based (e.g.,
al. 2020 Welleck al. 2022) or modeled with a neural classifier regressor (e.g., Chaftin et al. 2021: Yao et al. 2023 This evaluation function can be combined with the policy LM to guide the decoding, which is often complemented with some search algorithm to allow for some look-ahead and long-horizon planning (e.g., Lu et al. 2021 Chaffin et al.) 2021). Monte-Carlo Tree Search (MCTS) is among the most effective search algorithms (Silver et al. 2016).
3

---

Published as a conference paper at COLM 2024
Stage 1: select
Stage 2: expand
Stage 3: evaluate
Stage 4:
backup
Figure 2: The four stages of one simulation in MCTS. Note: we displayed the node visit count (ss) on its parenting edge as the number of "paws" (e.g., in the bad token in the backup stage).
2.3 Proximal Policy Optimization (PPO)
PPO (Schulman et al. 2017) is an RL algorithm for optimizing a policy against given reward function. PPO assumes a reward function that computes reward r($T+1) from the terminal state ST+1 (i.e., the complete sequence). This reward is assigned to the step- level reward of the last step, rT, while the step-level reward for non-terminal steps are zero-initialized. Further, each step-level reward is penalized with KI. divergence term,
- lBl Po(a)ss)) where do is the reference policy (usually the initialized policy of PPO train- Pay (#r]br)
ing), and B is hyperparameter. Therefore, the step-level reward is
Po(ar)s)) r(5T+1) (where t =T) Ptg [x)) Pa st)
-logg
rt =
(1)
Blog
(where f <)
Psy (s)
PPO simultaneously trains two models: a policy model po(ar]s)), and a value model Va (s),, both parameterized with neural networks. The PPO learning objective consists of two parts: policy objective and value objective. The policy objective attempts to maximize a surrogate objective containing an advantage function, and to compute the advantage we need the value function estimated by the value model. The value objective attempts to minimize the value estimation error against the empirical return,
G
Tp
(2)
where y is the discounting factor. For more details about the PPO learning objectives, see SA.2
Current practices of decoding from PPO models. After PPO training, most researchers and engineers deploy only the resulting policy model, and decode with simple methods such greedy decoding utilized, because its checkpoints are either unsaved or unreleased by model trainers. Our observation is that this value model is very suitable candidate for the evaluation function in guided decoding.
top-p sampling ($2.1). The associated value model cannot be
3 Method
Applying MCTS decoding on top of PPO-trained models allows for systematic search and look-ahead in the decoding space. This section describes how we practically apply MCTS decoding on PPO-trained policy and value models. We extend the standard MCTS algo- rithm to align with the text generation and PPO settings (this section), and in the Appendix, we discuss some approximation techniques when certain criteria are not met ($A.4) and some detailed implementation choices in PPO that may render these approximations essary (5..5). The goal of MCTS is to find high-reward output sequences, using the policy model and a evaluation function as guidance. The policy provides initial proposals on promising ac- tions, and the evaluation function scores partial sequences proposed by the policy. We
4

---

Published as a conference paper at COLM 2024
want to evaluate more frequently partial sequences stemmed from more promising actions so as to obtain more accurate evaluations for these actions (i.e,, exploitation), while we also want to make sure to evaluate some less promising actions as to reduce the likelihood of missing out high-reward sequences (i.e., exploration). MCTS offers an effective exploration and evaluation heuristic based on tree search.
In PPO-MCTS, the MCTS decoding works with the policy and value model trained by PPO. To decode each token, MCTS builds a search tree while running a number S of simu- lations. In the search tree, each node represents a state s and each edge represents an action For each node s, we maintain two variables: a visit count N(s) (which is eventually used to decode the token) and a mean value (s);; for each edge (s,a), we keep track of the value of its Q-function Q(s, a). Each simulation consists of four stages (illustrated in Figure 2):
1. Select: Select an unexplored node in the tree. Since we decode tokens based on the visit counts, we would like to pay more visits to nodes that show promise of high values so that we can obtain more accurate value estimates for them, while we also want to make sure to explore under-visited nodes. We balance exploration and exploitation using the PUCT algorithm (Rosin| 2011): Starting from the root node, we choose an action and move to the child node, and repeat this until we reach an unexplored node. Say currently we are at node s. The action a" is chosen according to the following formula, which favors high Q-function values while discounting high visit counts:
(()) a" arg max [Q(s, + Cpuct Pe(a|s) 1+ 1+N(s))
(3)
where s' is the state after taking action a from node s, (o(s)) is the PPO policy prior; Q(s,a) = r(s,, a) + (s') is the Q-function for edge (s,a) and is derived from the outputs of the PPO value model (and is computed according to Equation 4 in the backup stage below), where r(s,a) is the step-level reward defined in [Equation aand (ss) is the mean value produced from evaluating nodes in the subtree of node s (inclusive) [seuaion 5 in the backup stage below); ((s) is the visit count of node s; Cpuct is hyperparameter. Note that in PPO, intermediate steps are penalized with KL term (Equation 1), and there is a discounting factor y when computing the return (Equation 2 We use the Q-function (instead of the (ss) as in Silver et (2017) in Equation 3 which is in line with the original formulation of MCTS (Kocsis & Szepesvari 2006).
To capture these,
2. Expand: The selected node s* is expanded and marked as explored. The prior policy distribution le( is computed for this node, and actions with the top-k priors are each linked to a new, unexplored child node. The V of child nodes are zero-initialized.
3. Evaluate: The value function of node s* is evaluated, using the PPO value model: V(s*) = Vø(s*). If s* is terminal state, the final reward r(sT+1) is used. We initial- ize the visit count s* s* as one, and the mean value of s* with this value model's output, i.e. N(s*) <- 1, (s*)== < V(s*). Following Silver et al. (217)) and Chaffin et al. 2022)) we do not do Monte
rollout due to efficiency considerations.
We also initialize the Q-function of the children edges of s* with this value model's out- put, i.e., Q(s*, .) + V(s*), ",*,,, Va. This contrasts with the standard MCTS algorithm where the V (or in our case, the Q) of the children of newly explored nodes are zero-initialized. We refer to this change as initializing Q with V. We made this change because with PPO models, the Q can have rather large scales (in the order of 10s), due to reasons that will be explained in $A.5) During early experiments, we found that this can severely suppress exploration in the tree search, making it degenerate to greedy decoding.
4. Backup: Update the visit count N-)) and mean value V--) for all nodes, and the Q- function . for all edges, on the path from node s* back to the root node s,, The update is carried out bottom-up, with the update rules:
Q(s,a) + r(s,a) + +V((s), ((s) < [((s))((s,a) EN(s'),
(4)
(5)
N(s) t N(s)+1
(6)
5

---

Published as a conference paper at COLM 2024
where is node the path and 5 is its child (also the path) after taking action i; s' is the child node of state s after taking an action a; r(s, a) is the step-level reward defined in Equation 1
Before the simulations, the root node s, is initialized with the expand and evaluate stages. After the simulations, an action decoded from the normalized visit counts of the children of the root node:
p(a & Nsst,
where Ta temperature hyperparameter. From this distribution, we can either sample (optionally with top-p sampling) or greedily decode (i.e., Ta -> 0).
Forbidding node expansion after terminal states. Text generation usually stops at ter- minal token, [EOS]. When the action is [EOS], the child node is called a terminal node. Node expansion after terminal states should be forbidden, because evaluation on states after a terminal node has undefined behavior. To maintain proper visit counts up to the terminal node, when encountering terminal node in the select stage, we should not stop the simulation early, but jump directly to the backup stage.
Experimental Setup
We apply our PPO-MCTS decoding method on four text generation tasks: sentiment steer- ing, toxicity reduction, knowledge introspection, and creating helpful and harmless chat- bots. Additional experiment details can be found in B
Task 1: sentiment steering. PPO has been previously employed to control LM toward generating text with a specified sentiment (positive or negative), and we apply MCTS de- coding on top of these PPO-trained models to further improve the success rate of sentiment steering (i.e., satisfying the goal). We follow the experimental setup in Lu et al. (2022), where the task is to generate positive-sentiment continuations for negative-sen timent prompts (and inversely, negative continuations for positive prompts) in the Open dataset (Gokaslan & Cohen 2019)
Task 2: toxicity reduction. PPO has been previously employed to steer LMs toward gen- erating less toxic text, and we apply MCTS decoding on top of these PPOO-triied models to further reduce toxicity. We follow the experimental setup in Lu et al. (2022), where the task is to generate less toxic, yet fluent and diverse, continuations to prompts the Real- ToxicityPromppe dataset (Gehman et al. 2020).
Task 3: knowledge introspection. For commonsense question answering (QA), previous work has found it helpful to first ask LMs to introspect for relevant commonsense knowl- edge and then ground the QA model's prediction in the introspected knowledge (Liu et al., 2021 2022). The knowledge introspection model takes the question as input and generates knowledge statement, and this model can be trained with PPO to maximize the utility of the generated knowledge on the downstream QA model (Liu et al., 2022). We apply MCTS decoding on the PPO-trained knowledge introspection models to further increase the utility of decoded knowledge and thus improve downstream QA performance.
Task 4: helpful and harmless chatbots. In this task, we investigate how effective PPO- MCTS is on aligning LMs to human preferences. We use the helpfulness and harmlessness data from Anthropic's HH-RLHF dataset (Bai et al. 2022).
Results
Across all four tasks, PPO-MCTS achieves superior performance compared to direct de- coding from the PPO policy. In $5.1 we conduct more ablations and analyses with the sentiment steering task, and show that our method outperforms other reward-improving strategies such as best-of-n decoding and longer PPO training.

---

Published as a conference paper at COLM 2024
Table 1: Results on sentiment steering. Upper: automatic evaluation. Lower: human eval-
uation. See Table 6 for more baselines and compared methods. t: We use our replica of the
PPO model, whuch is trained under a slightly different setting than Lu et al. 2022 (details in $B.1 and has similar performance.
Desired sentiment: POSITIVE
Desired sentiment: NEGATIVE
% Desired
Fluency output ppl (U) dist-2 (1) dist-3 (t)
Diversity
% Desired
Fluency
Diversity
(1)
(1)
output ppl (L) dist-2 (?) dist-3 (1)
PPO Lu et al. 2022
52.44
3.57
0.82
0.81
65.28
3.57
0.83
0.83
PPO best-of-1
51.47
3.56
0.83
0.82
65.62
3.57
0.83
0.83
PPO-MCTS (ours)
86.72
3.42
0.79
0.81
91.09
3.44
0.80
0.82
Desired sentiment: POSITIVE
Desired sentiment: NEGATIVE
PPO
PPO-MCTS
PPO"
PPO-MCTS
More Desired
27%
49%
29%
47%
More Fluent
37%
50%
44%
34%
More Topical
44%
37%
50%
30%
Baselines. We compare with direct decoding from the same PPO policy model, using nucleus sampling (p = 0.5 in knowledge introspection, and p 0.9 in other tasks). We also include best-of-n decoding as baseline, where each decoded continuation is selected from candidates produced by nucleus sampling, and the selection is done by the value model. For fair comparison with PPO-MCTS, in best-of-n we use n = 50 in sentiment steering, and 20 in toxicity reduction.
Task 1: sentiment steering. We evaluate on the test set of OpenWebleex. When steering for positive sentiment, we evaluate on the subset of negative-sentiment prompts; when steering for negative sentiment, we evaluate the subset of positive-sentiment prompts. Following Lu et al. (2022), we conduct both automatic and human evaluation. For auto- matic evaluation,
report the ratio of generated text with desirable sentiment (i.e., rate of goal satisfaction) over 25 samples for each prompt,fuency as measured by the perplexity of generated text according the off-the-shelf GPT2-x1 (Radford et al., 2019), and diversity as the percentage of distinct nt-grams in the generated text. For human evaluation, we do pairwise comparison on outputs from PPO-MCTS to the direct sampling baseline, based on the perceived level of sentiment fitirabiltt,flluenee and topicality. More details on human evaluation can be found in Appendix $C
As shown in Table 1. PPO-MCTS greatly increases the sentiment steering success rate com- pared to the direct sampling baseline from the policy (+34% absolute on positive sentiment and +26% absolute on negative sentiment), while maintaining comparable fluency and di- versity. Meanwhile, best-of-n only gives marginal or no improvement of success rate on either target sentiment. Human evaluation also shows that PPO-MCTS generates more preferable text than the direct sampling baseline (+22% on positive sentiment and +18% on negative sentiment).
Task 2: toxicity reduction. We evaluate on the test set of RealToxicityPrompts. Following Lu al. (2022), we conduct both automatic and human evaluation. For automatic evalua- tion, we report the maximum loxicity over 25 samples for each prompt, flunncf as measured by the perplexity of generated text according to the off-the-shelf GPT2-X1 (Radford et al.) 2019), and diversity as the percentage of distinct nt-grams in the generated text. For human evaluation, we do pairwise comparison on outputs from PPO-MCTS to the direct sam- pling baseline, based on the perceived level of foxicity, fluency, and topicality. More details on human evaluation are in Appendix $C
PPO-MCTS reduces max toxicity of the sampled text compared to the direct sampling baseline from the policy (-34% relative), while maintaining comparable fluency and diversity. Meanwhile, best-of-n only gives marginal reduction on toxicity (-5% relative). Human evaluation also shows that PPO-MCTS generates less toxic text than the direct sampling baseline (with margin of 30% relative), with comparable fluency and topicality.
As shown in Table 2
7

---

Published as a conference paper at COLM 2024
Table 2:
Results on toxicity reduction. Left: automatic evaluation. Right: human evalua- tion. t: We use our replica of the PPO model, which is trained under a slightly different setting than
Lu et al. 2022 (details in (B.2) and has similar performance.
Toxicity
Fluency
Diversity
avg. max. (1) output ppl (U) dist-2 (1) dist-3 (1)
PPO*
PPO-MCTS
PPO (Lu al. 2022
0.1880 0.1782
3.22
0.83
0.84
Less Toxxcc
19%
27%
PPO + best-of-
3.21
0.84
0.85
More Fluent
43%
43%
More Topical
37%
45%
PPO-MCTS (ours)
0.1241
3.07
0.83
0.85
Table 3:
Results on knowledge introspection. QA accuracy on Table 4: Results on helpful the dev set of each dataset is reported. our results on the PPO
and harmless chatbots
baseline are slightly different from Liu et al. (2022), possibly due to
discrepancy in compute environments and random variation.
Reward
PPL
PPO
1.7176
2.44
Dataset
CSQA
QASC PIQA
SIQA WG
Avg. (1) Usefulness
PPO + stepwise-value
0.8945
knnweldgge Introspccionn
43.09
53,84
53.35
55,07
PPO-MCTSIRI
1.7004
PTO Liu al. 2022
65.52
52.16
64.09
55.89
55.80
58.69
3.62
PPO-MCTS (ours)
1.7532
2.43
PPO-MCTS tours)
65.77
52.81
64.42
56.35
56.20
59.11
4.04
+12%
Task 3: knowledge introspection. We report the QA accuracy on the validation set of the same five datasets as in Rainier: CommonsenseeA (Talmor et al. 2019), QASC (Khot et all
2020 PIQA (Bisk et al. 2020), SIQA (Sap et al. 2019), and Winogrande (Sakaguchi et al.
2020 As shown in lable 3 using PPO-MCTS to decode the commonsense knowledge
from Rainier improves the downstream QA performance by 0.42% absolute, compared to
the direct decoding method, and the usefulness of knowledge increased by 12% relative.
Task 4: helpful and harmless chatbots. We evaluate on prompts in the test set of a mix-
ture of helpfulness and harmlessness data from HH-RLHF. We report the reward of the generated text, as evaluated by the reward model. We also conduct human evaluation and compare PPO-MCTS with the baseline decoding method. As reported in Table 4 PPO- MCTS increases the average reward of the output by 0.04 compared to the PPO policy baseline. In human evaluation, PPO-MCTS also has 5% (absolute) higher win rate than PPO.
5.1 Analyses and Ablations
In this section, we report additional ablation results and analyses of our PPO-MCTS method, using the sentiment steering task.
Do we need the value model? Ablation: using reward model in place of value model in MCTS. It is natural to ask whether the PPO value model is needed in the MCTS de- coding. An alternative is to directly use the reward model, which also predicts a scalar number for an input sequence. The reward model predicts the reward of the full sequence (r(ST+ 1)), whereas the value model predicts the expected return under the current policy (EEp, [ " "rl"r Theoretically, the value model has two advantages over the reward model: (1) the value model is trained to process partial sequences, while the reward model is usually not; (2) the value model is tailored for the policy model, whereas the reward model is off-the-shelf or trained prior to PPO. Empirically, we experiment with a version of PPO-MCTS where the value model is replaced by the reward model, and report the result in Table under PPO-MCTS[R]. This variation results in lower goal satisfaction rate and lower Hluecyy than our value-guided version of PPO-MCTS. Therefore, we have theoretically and empirically justified the necessity of the value model.
Do we need MCTS? Ablation: using stepwise-value in place of MCTS. We also study the necessity of the MCTS algorithm during decoding. To this end, we compare with simple baseline, stepwise-vulue to decode each token, we query the policy and keep the top- k tokens, use the value model to evaluate each, and sample from the distribution derived from the value logits. To keep fluency relatively high, we change the hyperparameters to = = 10 and T = 1.0 with linear annealing down to zero. As shown in Table 6 stepwise- value results in much lower goal satisfaction and much lower fluency compared to PPO-
8

---

Published as a conference paper at COLM 2024
MCTS. Alternatively, some other search algorithm can be conceivably applied (e.g,, beam search, A*). In this work we focus on MCTS due to its superior capability on informed search over the action space.
MCTS vs. more PPO? One could argue that higher rewards can be achieved by running PPO for more steps. However, over-doing PPO could result in higher divergence in the policy model, and we show that applying MCTS decoding is a more regularized way to get higher-rewarded generations. We continue training the PPO models of both sentiments up to 500 PPO steps, and apply the direct top-p sampling on the resulting policy, which is denoted as "PPO (4x more steps)" in Table 6 Experiments show that on the positive- sentiment model, this method results in inferior goal satisfaction with significantly worse PPL. compared to PPO-MCTS, while on the negative-sentiment model, if has comparable PPL and yet still lower goal satisfaction. These results suggest that MCTS decoding is more desirable way to achieve higher rewards than training PPO for longer.
How to get diversity out of MCTS? MCTS is known to search for the best sequence of actions. There are two places in MCTS where we can promote diversity: (a) when decod- ing the action from visit counts (Equation 7, we can apply non-zero temperature Ta so that we get stochastic results, and (b) in the expand stage, we can apply a higher temper- ature Te to the priors (a(s),, so as to encourage more exploration in the search tree. We report experiments with different T4 and Te in Table 5) (in Appendix SD). Increasing To can substantially improve goal satisfaction and diversity, yet at the expense of hurting fluency. On the other hand, increasing Tt can increase diversity, with relatively small penalty on fluency and goal satisfaction. To maintain comparable diversity while optimizing for goal satisfaction, we choose T2 = = 2.0 in our experiments.
Other hyperparameters. Two other hyperparameters are instrumental in MCTS: the number of simulations for each token (S), and the branching factor (k). We experiment with S 20, 50), and to prevent k from being a limiting factor in the tree search, we keep it the same as S. As reported in Table 5 (in Appendix $D), increasing S and k generally improves goal satisfaction and diversity, at the expense of hurting fluency. Based on these observations, we choose S = k = 50 in our experiments
Inference time overhead. PPO-MCTS does introduce an inference time overhead com- pared to direct sampling from policy models. Estimated naively, PPO-MCTS is 25 times slower due to the tree construction, where S is the number of simulations run before decod- ing each token, if we assume that the policy and value model share the same architecture and size. KV caching may be used to speed up standard decoding methods (e.g, top-p sampling), and it is also applicable and equally effective on PPO-MCTS, pact on the relative overhead. However, the subtree under the decoded token can be reused when constructing the search tree for the next token, and thus at least [//]] tree nodes do not need to be re-computed (and in practice, this number is usually much higher). This mitigates the large inference time overhead to some extent.
it has im-
6 Related Work
Guided decoding. Standard text decoding involves sampling from the next-token distri-
bution estimated by a generative LM. To achieve higher controllability or task success rate, guided decoding has been employed by numerous prior work. Among these, some use
token-level value functions to guide decoding (Dathathri et al. 2019 et al. 2020 Lu
et al. 2020 Chaffin et al. 20221, while others use leee- level verifier (Welleck et al. 2022
sato et al.
2022 Lightman et al. 2023 Krishna et al. 2022 Li al. 2022) Khalifa et al. 2023 Xie et al.
2023 Yao et al. 2023), and they are usually complemented with some search al- gorithms. Our method, P PCO-MCTS is a guided decoding method with token-level value functions, and our decoding is further empowered by Monte-Carlo Tree Search. Further- more, while the value functions in most prior work are based on either hand-crafted rules or separate discriminative models, the value model we use is specifically tailored for the generative LM, and more directly captures the desired target metric.

---

Published as a conference paper at COLM 2024
Monte-Carlo Tree Search for text generation. MCTS has been employed in various lan- guage tasks. LLM-MCTS (Zhao et al. 2023b) and RAP (Hao et al. 2023) applies MCTS to planning and logical reasoning tasks, where they use off-the-shelf LLMs as both policy and value models. PPL-MCTS (Chaffin et al. 2021) applies MCTS in a plug-and to control certain aspects of generated text (e. polarity, emotion), where the value models are off-the-shelf sequence classifiers (which are not meant to operate on partial sequences). Leblond al. (2021) applies MCTS to the machine translation task, where the value model trained to fit an already-trainee policy, similar to AlphaGo (Silver et al. 2016). To our best knowledge, we are the first to apply MCTS policy and value models trained jointly with PPO.
manner
Proximal Policy Optimization. PPO (Schulman et al. 2017) is an RL algorithm for opti- mizing a policy against a given reward function, and has found great success in language OpenAI 2022; 2023 Bai et al. 2022 Touvron et al. 2023b Liu et al. 2022 Wu et al. 2023). However, researchers and practitioners have been only making use of the PPO-trained policy for inference, while discarding the by-product value model during or after training. To our best knowledge, we are the first to make use of PPO's value model and combine it with the policy yield better text generation. After PPO, other RL algorithms for language has been proposed, including Quark (Lu et al. 2022), DPO (Rafailov et el. 2023), and SLiC (Zhao al. 2023a). Yet these methods not train an accompanying value model, and thus cannot directly benefit from value-guided MCTS.
tasks (Ouyang et al. 2022
7 Conclusion and Future Work
In this paper, we proposed an effective method to apply Monte-Carlo Tree Search (MCTS) decoding on top PPO-trained policy and value models, and demonstrated the usefulness of value models trained byproducts when aligning LMs to human preference.
Future work may consider using MCTS as a policy optimization operator (Silver et al. 2017 Grill et al. 2020) for language model training, yet several challenges may need to be
addressed: (1) constructing the Konte-Carlo search tree is less efficient than PPO policy rollout; (2) MCTS updates the policy distribution towards the visit counts, which may not have sufficient significance due to the large action space in language.
10

---

Published as a conference paper at COLM 2024
Limitations and Ethics Statement
While greatly improving the preferability of generated text, our method does introduce significant compute overhead at inference time. Our method does alter the behavior of generative LMs, and it is conceivably possible that it may divert the policy LM to generate harmful content that would not have been produced under direct decoding methods, espe- cially if the value model is ad adversarially tampered with. Discretion should be used when applying this method to existing LMs.
Acknowledgements
We thank Ximing Lu for sharing the code for training PPO models in the toxicity duction and sentiment steering tasks. Additionally, we thank members of the H2lab for their constructive feedback. This work was funded in part by the DARPA MCS program through NIWC Pacific (N66001-19-2-4031), DARPA ITM program (FA8650-23-C-73166 NSF IIS-2044660, and NSF DMS-2134012. The views, opinions and/or findings expressed are those of the author and should not be interpreted as representing the official views or poli- cies of the Department of Defense the U.S. Government. JL. is supported in part by the Meta AI Mentorship program.
References
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, T. J. Henighan, Nicholas Joseph, Saurav Kadavath, John Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield- Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom B. Brown, Jack Clark, Sam Mc- Candlish, Christopher Olah, Benjamin Mann, and Jared Kaplan. Training a helpful and harmless assistant with reinforcement learning from human feedback. ArXin, abs abs/2204.05862, 2022. URL
Yonatan Bisk, Rowan Zellers, Ronan LeBras, LeBras,Jianfeng Gao, and Yejin Choi. PIQA: reasoning about physical commonsense in natural language. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 7432-7439. AAAI Press, 2020. URL fttts::/aaai.orr
Antoine Chaffin, V. Claveau, and Ewa Kijak. Ppl-mcts: Constrained textual generation through discriminator-guider mcts decoding. In North American Chapter the Association for Computational Linguistics, 2021. URL https://app semanticscholar or wwwg//orrgs/D/0.
the
248512793.
Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. Plug and play language models: A simple ap- proach to controlled text generation. ArXiv, abs/1912.02164,, 2019. URL Inttps://api.
semanticscholar.cm det.aannisscsoolrrrrooo//ooooooo wttp//CoppuSDD:2861777999
Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. Real- toxicityprompts: Evaluating neural toxic degeneration in language models. In Findings, 2020. BtRLL/ttps::// //api. semanticscoolarr..mmmmomo wtt.sccoo.aa..or///oorruiii/iaaa
Aaron Gokaslan and Vanya Cohen. Openwebtext corpus. http://Skylion007. tiubb..............
thub. io/
@penWebTextCorpus 2019.
Jean-Bastien Grill, Florent Altch'e Yunhao Tang, Thomas Hubert, Michal Valko, Ioan- nis Antonoglou, and Rémi Munos. Monte-carlo tree search regularized policy op- timization. In International Conference on Machine Learning, 2020. URL httpps:/app..
11

---

Published as a conference paper at COLM 2024
Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philipp Schmid, Zachary Mueller, and Sourab Mangrulkar. Accelerate: Training and inference at scale made simple, efficient and adaptable. https://gi httpss//ggttuub.coo//uuggggg/g com/huugingfacee accelerate, 2022.
Shibo Hao, Yilan Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. ArXiv, 0t5p/2305.14999 2023. URL sttp://////p.ssmstiiiiiiieee :tw.:olaar.rgrooouSt:::::0 258865812
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. ArXio, abs/ 190/1990,,9751,, 2019. URL httpss//api. sem.aaii.ssmmmttccchhhoo..o
Trg/CorpusID:12796635
Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Ho Hin Lee, and
Lu Wang. Discrininator-uudder multi-step reasoning with language models. ArXiv,
abs/ 2305,230,,,434, 2023. URL https:://pppp.... htt.:/ppp...mmaaassscccoo..oeoee httprascocooooooooorrrrroooooSaa 2588655395
Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi. UNIFIEDQA: Crossing format boundaries with a single QA system. In Findings of the Association for Compulational Linguistics: EMNLP 2020, pp. 1896- 1907, Online, 2020. Association for Computational Linguistics. doi: 10.18653 / v2/2020.. findings-emmll.177 URL https:://ccaatthlloogtt/ org.orgg//222 2020. findings- 171
Tushar Khot, Peter Clark, Michal Guerquin, Peter Jansen, and Ashish Sabharwal. QASC: A dataset for question answering via sentence composition. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Seconil Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 8082-8090. AAAI Press, 2020. URL attps://aaai.. wtt.aaaii.rr//////ndeeeeeee http:///ooos/.me.e.pp/////////aa php//AAT//arriillee view/6319
Levente Kocsis and Csaba Szepesvari. Bandit based monte-carlo planning. In Euro- pean Conference on Machine Learning, 2006. URL hnttps://ap) www.sse ccsholarc .rg/
CorpusID:15184765
Ben Krause, Akhilesh Deepak Gotmare, Bryan McCann, Nitish Shirish Keskar, Shafiq R. Joty, Richard Socher, and Nazneen Rajani. Gedi: Generative discriminator guided se-
quence generation. In Conference on Empirical Methods in Natural Language Processing, 2020. Utt/ht //api. sttppppc...mmmiicccocoo..rrr
wttrg/CorpusID... 221 221655075
Kalpesh Krishna, Yapei Chang, John Wieting, and Mohit lyyer. Rankgen: Improving text generation with large ranking models. ArXiv, htss/2005.09725 2022. URL https::/app.
semanticscholar.c http:/oooooo.rrrrroooooo/o0::::.
Rémi Leblond, Jean-Baptiste Alayrac, L. Sifre, Miruna Pislar, Jean-Baptiste Lespiau, Ioannis Antonoglou, Karen Simonyan, and Oriol Vinyals. Machine translation decoding beyond beam search. In Conference on Empirical Methods in Natural Language Processing, 2021. URL https://app api wwwanti cscholarr.ccclrr...mm wrgp/orppsS1::233222 2333116333
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, B. Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Amnual Meeting of the Association for Computational Linguistics, 2022. URL sttps://aptt semanticscholar
org/CorpusID: (00ooppuuI::293788441 259370847
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. ArXiv, abs/ 20050 2023. URL https://app. htttp::/aai..smmaticcccchee www.nticscholleeeee.eee wtw.ricchooo.o.o/rrrsussssslle org/CorpusII: 258987659
Jiacheng Liu, Alisa Liu, Ximing Lu, Sean Welleck, Peter West, Ronan Le Bras, Yejin Choi, and Hannaneh Hajishiri. Generated knowledge prompting for commonsense rea- soning. In Annual Meeting of the Association for Computational Linguistics, 2021. URL https://api. www..h........rr/ooooo//00002111
12

---

Published as a conference paper at COLM 2024
Jiacheng Liu, Skyler Hallinan, Ximing Lu, Pengfei He, Sean Welleck, Hannaneh Hajishirzi, and Yejin Choi. Rainier: Reinforced knowledge introspector for commonsense ques- tion answering. ArXiv, abs/2220.03077,, 2022. URL CorpusID:252735191
Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Neurologic decoding: (un)supervised neural text generation with predicate logic constraints. ArXiv, htss/2000122884 2020. URL https: //ppi. semanticscholar org/
Corpus1D:225067900
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ro- nan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. Neurologic a'esque decoding: Constrained text generation with lookahead heuristics. In North American Chapter of the Association for Computational Linguistics, 2021. URL
https://api. semanticscholar.. wwwpaar/oo//o/oooo/o.//. 245218671
Ximing Lu, Sean Welleck, Liwei Jiang, Jack Jack Hessel, Lianhui Qin, Peter West, Prithviraj Am- manabrolu, and Yejin Choi. Quark: Controllable text generation with reinforced unlearn- ing. ArXiv, abs abs/2205.13636 2022. URL httpss//ppp...emmnnnccccooooorro http://cccccccaoooorro/rr/ooooo 249152301
OpenAl. Introducing chatgpt, November 2022.
OpenAL. Gpt-4 technical report. Technical report, OpenAI, 2023. URL https://cdn.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welin- der, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. Training language mod- els to follow instructions with human feedback. ArXiv, abs/2203.02155, 2022. URL https://api. semantiitttmtitcccccccooooeeaa wtw.oooarr.rggooouussi::o- /BB//CoppuIID:244425998 246426909
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmai- son, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Neural Information Process- ing Systems, 2019. URL https://api. wtw.:apiisemmannisschl.l.... wwwpsccholaarrgooooooorooo orgg/orppssI::22788777
Martin L. Puterman. Markoy decision processes: Discrete stochastic dynamic program- ming. 1994. URL
122678111
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. 2019. URL httpss//api. semanticscholar. wwaprriissscooaa..orrooooooooooe wwwp://orrpsS111160055555533
Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. ArXiv, 2bs./2305.8290 2023. URL https://app: wemanticscholar..oot
(GorpuSDD:259599221
Colin Raffel, Noam M. Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. ArXiv, abs/1910.10689 2019. / semanticscholar. httpriicsccccoaoooo/ooorrroooo wtt.:o///oorrs110224883338
Christopher D. Rosin. Multi-armed bandits with episode context. Annals of Mathemat- ics and Artificial Intelligence, 61:203-230, 2011. URL https: //api. semanticscholar org/
13

---

Published as a conference paper at COLM 2024
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Secone Innovative Applications of Artificial Intelligence Conference, AA 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAT 2020, New York, NY, USA, February 7-12, 2020, pp. 8732 8740. AAAI Press, 2020. URL https: ottp:i/r/goo///////oooo/oo (atjj//indx...o http://///nn...p//////aattttiiaa
Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi. Social IQa: Commonsense reasoning about social interactions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Confer- ence Natural Language Processing (EMNNLP-IJCNIP), pp. 4463-4473, Hong Kong, China, 2019. Association for Computational Linguistics. doi: 10.18653/v1. 1116633/11/D19-4554 URL https://acclaatiooooy......
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proxi- mal policy optimization algorithms. ArXiv, ///1/1070004447 2017. URL https://api.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, L. Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam,, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timo- thy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hass- abis. Mastering the game of go with deep neural networks and tree search. Nature, 529: 484-489, 2016. URL https: wwwanticschollaa.. httpps://ap..smmmmiicchhooollol wwt.eamw..ccccc.....oooooooooooo
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, L. Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550: 354-359, 2017. URLhhtpss://apt httttts://app.ssmmtticcchooooolo semanticscholar
Org/CorppsII: 2052610220900 0334
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseeA: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4149- 4158, Minneapolis, Minnesota, 2019. Association for Computational Linguistics. doi: (4.18633vv1// 11/1///111111112// URL https: //ccaato///c www.o/gy..rgg/1--11101
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. ArXiv, 230//223.11971 2023a. URL hatps://ppp semanticscholar. httpr//cccccooaooooor/oooooooooa 257219404
Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cristian Cantón Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel M. Kloumann, A. V. Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Moly- bog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, R. Subramanian, Xia Tan, Binh Tang, Ross Tay- lor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zhengxu Yan, lliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. ArXiv, abs/2307..099 ,09288, 2023b. URL https://api. s cscholarr .org//
CorpusID: 259950998
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, L. Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems
14

---

Published as a conference paper at COLM 2024
with process- and outcome-based feedback. ArXiv, abs/2211.14275, 2022. URL https:
seapstisaatics httpc/sschooaar.rrrrrrrroooo 254017497
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Natu- ralprover: Grounded mathematical proof generation with language models. ArXiv,
wwg/CorpussDD.C.. abs/2205.12910, 2022. URL httpp: www.nti ottp://iiiiiicoooooooooorrrrpopp :4:0000330 249063060
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, An- thony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface's s transformers: State-of-the-art natural language processing. ArXiv preprint, abs/ 199007777,,,,, 2019. URL h/ttpss//arxiv http:://aaaiv..ogaba//////s///// /rgg/bb//911..00
Zeqiu Wu, Yushi Hu, Weijia Shi, Nouha Dziri, Alane Suhr, Prithviraj Ammanabrolu, Noah A. Smith, Mari Ostendorf, and Hanna Hajishirzi. Fine-grained human feedback gives better rewards for language model training. ArXio, abs/2306.01693, 2023. URL
https://api. semanticscholar orgg/oorpu1D:225064000
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, MingSung Kan, Junxian He, and Qizhe Xie. Decomposition enhances reasoning via self-evaluation guided decoding. ArXiv, abs/2305.00633, 2023. URL Utthssss:///ppi sem.aiiiccommmiiccccccccooooaaae http:////.....oaaaaocoooooooooor wrwp/oorppSDD:2552225222 258426922
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large lan- guage models. ArXiv, Abs/2335.1066 2023. URL https:::: //ppi.pp...p semanticscholar. org/
2orpuss0:258762525
Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Saleh, and Peter J. Liu. Slic-hf: Sequence likelihood calibration with human feedback. ArXiv, abs/2305.10425, 2023a. URL https://app wwwanticschol.a. orgp/oorosSD: 2587410082
Zirui Neil Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense
knowledge for large-scale task planning. ArXiv, abs/2305.140777 2023b. URL https:
//pp.ssemanticcchooarr.orrr
258841057
Daniel M. Ziegler, Nisan Stiennon, Jeff Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human prefer- ences. ArXiv, abs/ 1101999990089,, 2019. URL httpht//s://pp semmantticcchollar.rrr////ooooro 202660943
15

---

Published as a conference paper at COLM 2024
A
Additional Technical Details
A.1 A note on implementation
We implement PPO-MCTS plugin that ready replace the "model.generate" Q) statement in existing codebases. Our plugin is written in Pylorch (Paszke et al., 2019 and is compatible with the HuggingFace Transformers and Accelerate lıbraries (Wolf et al. 2019
Gugger et al. 2022), which makes it easy to adapt to other tasks.
A.2 The PPO Training Objectives
For completeness, we review the PPO learning objective here, which consists of two parts: policy objective and a value objective.
Policy objective. First, a (per-step) estimated advantage function is computed:
Å at) = (t) + -
T
where Vp is the value model, and is the step-level reward defined in Eqqation 1 (In prac- tice, people usually use a fruncated version of this estimated advantage function.) Then, surrogate objective is defined as
(0) A, po(ailst) A,.
Pe, (a/15) (t)
The policy objective is the empirical mean of the clipped version of this surrogate objective:
ppllicy (0) = Ê, min(v; Å,, (l), e, + -A)]-
Value objective. MSE objective: The value model is trained to match the empirical return, G,, using
yvalue (() = f (Vp - G
The final objective a linear combination of the policy and value objectives: pro (0, Φ) spolicy (0) + vaaue (p).
A.3 The MCTS Backup Algorithm
Below is the formal algorithm for the backup stage of MCTS in PPO-MCTS.
Algorithm 1 The backup stage of MCTS in PPO-MCTS
Inputs; sy: the root node of the search tree; s": the node selected in the current simulation, the step-level reward a), and the current tree statistics N (s), (s), and Q(s.a).
procedure BACKUP(root,s")
+ s*
while a roof do x+s
+ s.parent, à +- Action(s 8)
Q(s,ā) + r(s,ā) 7V(
(s) < EaeAp=sschid(a)) N(s))Q(s,a)/ Eoe N(s')
N(s) + N(s)+1 +1
Output The new tree statistics N(s), (s), and @(s,a).
A.4 Approximations
When certain criteria not met (e.g., don't have access to the reward model at infer- ence time), we need to make some approximations in the PPO-MCTS algorithm. Below describe two potential approximations may need to make.
16

---

Published as a conference paper at COLM 2024
Approximating ((TT=1) with (ST+1))), when reward model is not available. At infer- ence time, the reward model may not be available to us due to various reasons, egg. the reward model is the final goal to optimize for rather than being proxy. In such cases, we cannot compute the reward for terminal states, r(sT 1), in the evaluate stage. We pro- pose to approximate this term with the value model output, ()) However, note that (1 is not trained to match r(sT-1) in PPO training, but this is a reasonable ap- proximation, especially considering that many implementations initialize the value model parameters from the trained reward model.
Approximating Q with V, when reference policy is not available. At inference time, the KL term may not be computable due to various reasons, e.g,, the reference policy model is not available. In such cases, we cannot compute the step-level rewards r, exactly, and thus cannot apply Equation applyEqqation 4 to compute the exact Qs,, We propose to approximate Q(s,a) with ((s') ). Note that this means dropping the KL regularization term, bringing more risk for reward hacking.
A.5 Implementation Choices in PPO and their Implications on MCTS
Certain variations in the implementation details of PPO may necessitate some approxi- mations we discussed above. Here we discuss some common PPO variations and their implications MCTS.
Reward normalization. Certain implementations of PPO normalizes the reward r($T so that it has a mean of 0 and standard deviation of 1:
r(ST+1) + r(ST+1) 140
The coefficients for this affine transformation, Hl and 0ū, are estimated with the training set and the initial policy before PPO, and are kept constant during PPO training, If reward normalization is used and the normalization coefficients are unknown, then we need to approximate r($7+1) with ((s++1).
Reward whitening. Certain implementations of PPO perform whitening step on the step-level rewards before using them to compute the returns and advantages (Ziegler et al., 2019). The whitening step scales all the ri's within a training batch so that they have standard deviation of 1. This introduces batch-specific scaling factor that is unknown to us at inference time. Since the value model learns to approximate the whitened returns, the value function carries an known scaling factor and thus cannot be directly added with the unwhitened, raw step-level reward to compute Q. Therefore, when reward whitening is used in PPO training, we need to approximate Q with V.
KL term clamping. In certain implementations of PPO, the KL term (in Equation 1) is clamped with minimum value of 0:
log Po(a)(s:) max (0, Pa, (ae St)
(a(a(ss))
po, (atls:)
If we do not know whether the KL term is clamped during PPO training, then we need to approximate Q with V.
Adaptive KL coefficient. Certain implementations of PPO uses an adaptive KL coeffi- cient that the KL penalty term can be kept close to target value. The final KL coefficient is often lost after training. If adaptive KL coefficient is used and the final KL. coefficient value is unknown, then need to approximate Q with V.
17

---

Published as a conference paper at COLM 2024
B Additional Experiment Details (...cont. from $
B.1 Task 1: Sentiment Steering
Models. We reproduce the PPO training in Lu et al. 2022), using GPT2-large (Radford et al. 2019) as the initial policy and an off-the-shelf sentiment classifier to provide reward. Compared to the original training settings in Lu et al. (2022), turn off reward whitening and adaptive KL coefficient, so that we do need to approximate Q with V. We train two sets of models, one for positive sentiment and one for negative sentiment, and we train for 100 PPO steps to match the performance reported in|Lu et al. (2022).
Decoding. We decode most 20 tokens per prompt. In MCTS decoding, we run 50 simulations per token with a branching factor k = 50. In the expand stage, we apply a lemperature Te 2.0 the policy prior to boost diversity. When finalizing the token decision, we use temperature sampling with more tokens are decoded. We use a fixed KL coefficient B 0.15, which is consistent with the training setup. We do not approximate Q with V, but do approximate r(ST+1) with (ST+1)), since the reward is the final objective and we do not assume access to this reward model at decoding time.
2.0 that linearly anneals down to 0.0 as
B.2 Task 2: Toxicity Reduction
Models. We reproduce the PPO training in Lu et al. 2022 using GPT2-large (Radford al. 2019) as the initial policy and I'erspectiveAPT to provide reward. P'erspectiveA'' re- turns toxicity score between 1 (non-toxic) and (toxic). Compared to the original training settings, we turn off reward whitening and adaptive KL coefficient, so that we do not need to approximate with V. We train for 500 PPO steps to match the performance reported
in Lu al. (002)).
Decoding. We decode most 20 tokens per prompt. In MCTS decoding, we run 20 simulations per token with branching factor k = 20. In the expand stage, we apply a temperature Te 2.0 the policy prior to boost diversity. When finalizing the token decision, we temperature sampling with = 2.0 that linearly anneals down to 0.0 as more tokens are decoded. We use a fixed KL coefficient B 0.15, which is consistent with the training setup. We do not approximate Q with V, but we do approximate r(ST+1) 1) with Vo ($T+1), since the reward is the final objective and we do not assume access to this reward model at decoding time.
B.3 Task 3: Knowledge Introspection
Models. We use the PPO-trained policy and value models in Rainier (Liu et al., and the corresponding reward model is derived from UnifiedQA (Khashabi et al. 2020 All these models are finetuned from T5-large (Raffel et al. 2019).
2022
Decoding. In MCTS decoding, we run = 10 simulations per token with a branching factor k 10. When finalizing the token decision, we use nucleus sampling with p 0.5. We use a fixed KL coefficient & 0.2, which is consistent with the training setup. We do not approximate Q with V, but we do approximate r(ST+1) with (ST++1), since compute (1) we need to know the ground truth answer of the question.
B.4 Task 4: Helpful and Harmless Chatbots
Models. We train reward model, SFT policy model, and the PPO policy and value models, all based on the pretrained LLaMA-7b (Touvron et al., 2023a). The reward model trained on mixture of helpfulness and harmlessness data for 1320 steps, and the SFT policy is trained on the helpfulness data for 3 epochs. The PPO policy is initialized from
18

---

Published as a conference paper at COLM 2024
the SFT policy, and the PPO value model is initialized from the reward model. We train PPO for 50 steps.
Decoding. We decode at most 256 tokens per prompt. In MCTS decoding, we run $ 20 simulations per token with a branching factor k 20. Since the evaluation does not require diversity, we apply a standard temperature T 1.0 the policy prior the expand stage, and when finalizing the token decision, we use greedy decoding (i.e., Pz + 0.0). We do approximate Q with V, since reward whitening and adaptive KL coefficient were turned on during PPO training.
C Human Evaluation Details
C.1 Sentiment Steering
We conduct human evaluation using crowdworkers, We randomly choose 100 positive prompts and 100 negative prompts. For each prompt, we randomly sample two genera- tions from each decoding method. In total we have 400 comparisons, and each comparison annotated by workers. The instructions and annotation interface are shown in Figure (borrowed from Lu et al. (2022)..
Following Lu et al. 2022 given comparison of generations, the annotators were asked three questions:
1. Positive/neeattiee sentiment: which has more positive/negative sentiment?
2. Fluency: which one more grammatically correct and coherent?
3. Topicality: which is natural, relevant, follows logically from the prompt, and maintains consistent tone, word choice, and structure?
Instructions
Phooee make read instructiono curctall before workdng lonk!
Inttcction
coey adlon poverta the tet yyeen coverer coee allnn dhe ser te putee
premee Why would conomner rak
continustion
Hellywood model KINNCEN
conttattoaa coloru pernec pletes quetica salcu
Rumey
On: Which of traatiinn poodiier
O continationn Clenttnartion Crequally
Retherroad
Cs Which of contrnationn
contruution Crantinaation Cheq
Mole
Moth
More
100%
Figure 3: Instructions and annotation interface for human evaluation on the sentiment steering task. Affiliation information redacted.
C.2 Toxicity Reduction
We conduct human evaluation using crowdworkers. We randomly choose 100 prompts. For each prompt, randomly sample two generations from each decoding method. In total we have 200 comparisons, and each comparison annotated by workers. The in- structions and annotation interface are shown in Figure (borrowed from Lu et al. [002
Following Lu et al. (2022), given a comparison of generations, the annotators were asked three questions:
19

---

Published as a conference paper at COLM 2024
1. Toxicity: which one is less rude, disrespectful or unreasonable?
2. Fluency: which one is more grammatically correct and coherent?
3. Topicality: which one is more natural, relevant, follows logically from the prompt, and maintains consistent tone, word choice, and structure?
Instructions
Summery
Orand wod.
Plaas buttoction careullly betore worling
Ther eu cuncisete canoyl seler ne with selccnn tes mender of ou endorm on woth eedicrett
cen cnille
at hosse clly nen erturiyg tess aurtonn
proepe hopek by uka too watk will lown howe
Tadklyy ban tusttal mare ludy you
thving sppicdee
contination unitone. viiue disnig intercatoo arile
contrnation leee salic?
rocee colegies peosee
Conmtrutiinn Coontmmation 5 Crrtulll solk booe
Beckgraadd
Conttrade Crontination Tuun
whs sontinadion aalor faainaly sllgge
A
Oo
Lik
Figure 4: Instructions and annotation interface for human evaluation the toxicity duction task. Affiliation information is redacted.
D Additional Analyses
Table 5: More analysis with sentiment steering. Q V: whether "initialize Q with V" (in the evaluate stage) is used; Cpuct: PUCT coefficient in Equation 3 S: number of simulations for each token; k: branching factor in the expand stage; Ty. temperature applied to the visit counts during action decoding; Te: temperature applied to the priors in the expand stage.
Hyperparams
% Desired
Fluency output ppl (L)
Diversity
Cpact
k
T2
T2
dist-2
dist-3 (t)
1.0
1.0
67.25
2.32
0.59
0.67
1.0
1.5
74.47
2.49
0.65
0.72
1.0
2.0
84.22
2.68
0.64
0.70
1.5
1.0
65.41
2.38
0.64
0.71
10
10
1.5
1.5
72.25
2.60
0.70
0.76
1.5
2.0
81.16
2.77
0.68
0.74
2.0
1.0
62.56
2.45
0.66
0.73
8.0
2.0
1.5
69.63
2,68
0.72
0.77
2.0
2.0
79.00
2.85
0.71
0.76
1
2.0
2.0
64.06
2.22
0.04
0.03
2
2.0
2.0
69.00
2.32
0.41
0.47
5
2.0
2.0
73.09
2.60
0.63
0.69
10
10
2.0
2.0
79.00
2.85
0.71
0.76
20
20
2.0
2.0
82.91
3.08
0.75
0.79
50
50
2.0
2.0
86.72
3.42
0.79
0.81
8.0
50
78.75
2.47
0.41
16.0
50
79.66
2.79
0.69
32.0
50
2.0
2.0
73.97
3.14
0.81
Table 6 is continuation of Table 1 and reports additional baselines and comparisons. ble reports ablations on the hyperparameters of PPO-MCTS, using sentiment steering as the task. Some of the results have been discussed in $5.1
Ta-
To complete this discussion,
20

---

Published as a conference paper at COLM 2024
Table Full automatic evaluation results for sentiment steering (continuation of Table upper). We use our replica of the PPO model, which is trained under a slightly different setting than Lu et al. (2022) (details in |B.1] and has similar performance.
Desired sentiment: PoSITIVE
Desired sentiment: NEGATIVE
Desired
Fluency output ppl (U) dist-2 (1) dist-3
Diversity
Desired
Fluency output ppl (1) dist-2 (f) dist-3 (f)
Diversity
(1)
(1)
PPO Lu et al. 1
52.44
3.57
0.82
0.81
65.28
3.57 3.57
0.83
0.83
PPO best-ot-
51.47
3.56
0.83
65.62
0.83
PPO + best-of-n[[]
72.16
3.58
0.82
0.82
PPO-MCTS[R]
81.00
3.80
0.85
0.84
+ stepwise-value
62.47
4.94
0.89
PPO
22.59
3.50
0,82
0.81
PPO best-of-n[[]
37.28
0.82
PPO(EX more steps)
75.50
3.87
0,83
0.82
83.63
3,37
0.82
0.83
PPO(sx mure steps)
86.34
4.12
0.82
PPO-MCTS (ours)
91.09
PRO(4X more MCCTS
96.16
3.72
0.81
0.83
PPO(9x more MCCS
we experimented with different values for Cpuct while turning off the "initialize Q with V" technique in the evaluate stage. We found that without "initialize Q with V", diver- sity is substantially lower, because exploration is greatly suppressed by the sheer scale of Q-function values (Equation 3). The diversity degeneracy may be mitigated by raising the value of Cpuct, yet the goal satisfaction rate starts decreasing when Cpuct is large. The best goal satisfaction rate yielded without "initialize Q with V" is lower than the standard setting of PPO-MCTS by 7 points.
21


Reviews:
[{"review_id": "31B67AnyXw", "reviewer": "Reviewer_wzou", "summary": "The PPO objective during the RLHF training simultaneously learn two models: a policy model and a value model. Often, the learned value models are ignored and only the policy model is used during inference. The paper proposes a novel guided decoding algorithm called PPO-MCTS which integrates the value model to work with the policy model during the inference time using Monte-Carlo Tree Search (MCTS). The paper is very well written and nice to read. The proposed method is thoroughly evaluated on four different controlled generation benchmarks. The results demonstrate the advantages of PPO-MCTS compared to PPO-only approaches, using both automatic and human evals.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for recognizing the importance of our studied problem and the effectiveness of our method. Below is our response to your concerns:\n\n**Comparison with using hand-crafted rules or separate discriminative models:** In our submission we experimented with using the reward model to guide MCTS. (For the tasks we evaluate on, the reward model would be the separate discriminative model.) This method is reported as “PPO-MCTS[R]” in Table 6, and it resulted in lower goal satisfaction and lower fluency than our PPO-MCTS. We did not try hand-crafted rules because it is unclear how to design rule-based classifiers for these tasks.\n\n**Inference cost comparison:** We mentioned the inference time of PPO-MCTS in the last paragraph of Sec 5.1. Naively, PPO-MCTS has a 2S times overhead compared to standard decoding from PPO models (S is the number of simulations), and this overhead can be mitigated by various techniques like caching and pruning. In some internal experiments, we have successfully generated sequences of 1k tokens with PPO-MCTS. We see PPO-MCTS as a method to boost quality with more compute at inference time.\n\n**Comparison with DPO and SLiC:** We did not compare with these methods because they do not produce a value model, which is required to apply MCTS. In addition, some recent work [[1](https://arxiv.org/pdf/2404.10719), [2](https://arxiv.org/pdf/2405.08448)] showed that online algorithms (like PPO) tend to produce stronger policy models than offline algorithms (like DPO).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The proposed approach is simple, yet very effective. The chosen text generation benchmarks are very relevant for the study and the results clearly show the advantages of PPO-MCTS compared to PPO-only approaches. The LLM community will find the paper very interesting. \n\nThe paper is well written. The authors have done a great job of clearly motivating the proposed approach.", "reasons_to_reject": "There are a couple of questions (see below) that were left unaddressed. It would be great to have the authors respond to them and also improve the paper accordingly. \n\n* I did not understand why the PPO-MCTS approach was not directly compared with prior guided decoding approaches using either hand-crafted rules or separate discriminative models as value functions. I feel the value functions specifically tailored for the generative LM (as used here) will work better than prior guided approaches, but it would be important to show this comparison.\n\n* It would be interesting to see the cost comparison between PPO and PPO-MCTS during inferences. Is it feasible to use  PPO-MCTS when generating a long sequence?\n\n* Additionally, the paper would benefit from comparison to DPO (https://arxiv.org/abs/2305.18290) or Slic (https://arxiv.org/abs/2210.00045) trained models. But these comparisons might be okay to skip in this paper.", "questions_to_authors": "Please see my three points/comments raised in 'Reasons to Reject'. It would be great to have you respond to them. I would be happy to reconsider my scores.", "extra_scores": {}}, {"review_id": "6qRdlIGkbW", "reviewer": "Reviewer_5Hxd", "summary": "This paper proposes using the value model to guide text generation from PPO policy, particularly in the form of Monte-Carlo Tree Search (MCTS). The experimental results demonstrate the effectiveness of value-guided MCTS in controlled text generation tasks. The idea is simple, but it is a good contribution to reminding people to use value models that have not been utilized in practice. The paper is clearly written and well-organized.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": true, "final_justification": "", "rebuttal": "Thanks for recognizing our contribution to the direction of guided decoding. Below is our response to your concerns:\n\n**Alternatives to MCTS:** First we would like to clarify that our “stepwise-value” baseline (used to compare with MCTS) uses not just values, but a combination of policy and values. It first selects top-k candidate tokens from policy model’s proposal, $p_\\theta(x_t | w, x_{<t})$, and then decide the token based on the values of these k candidates. It would be interesting to explore applying other search algorithms (e.g., FUDGE, beam search) to PPO models, and we leave it as future research.\n\n**MCTS cannot be applied to DPO models:** Indeed, DPO does not produce a value model required by MCTS, and MCTS can only be applied out-of-the-box to Actor-Critic methods like PPO. It is possible to post-hoc train a value model after the DPO model is trained, but that requires extra effort. Meanwhile, some recent work [[1](https://arxiv.org/pdf/2404.10719), [2](https://arxiv.org/pdf/2405.08448)] showed that online algorithms (like PPO) tend to produce better policy models than offline algorithms (like DPO). Building on such advocates for PPO, our proposed method can further boost the generation quality of PPO models.\n\n**Using reward model in MCTS:** In our submission we reported this ablation of using reward model instead of the value model for MCTS. The result is in Table 6 (under the name “PPO-MCTS[R]”) and we discussed this in the first paragraph of Sec 5.1. Using reward model for MCTS resulted in lower goal satisfaction and lower fluency. We offered two potential explanations: the reward model is not trained to process partial sequences, and the reward model is not adapted to the PPO policy model.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Guiding with the value model is simple but has been overlooked in practice. It is a good contribution to bring this direction to attention.\n* The experiments on four text generation datasets and the well-designed ablation studies demonstrate the effectiveness of the proposed decoding method.\n* The paper is clearly written and well-organized.", "reasons_to_reject": "* The advantage of MCTS itself is not verified enough. The ablation study \"Do we need MCTS?\" partially shows the effectiveness of MCTS but the baseline, which decodes based only on values, seems to be weak. Why not additionally use $p_{\\theta}(x_t|w, x_{<t})$, as in existing controllable text decoding methods, e.g., FUDGE [1]? In addition, I would like to see the value-model guiding combined with other search algorithms, such as beam search.\n* DPO, which is widely used these days, does not accompany a value model. This situation may reduce the utility of this method.\n\n[1] FUDGE: Controlled Text Generation With Future Discriminators. 2021. NAACL.", "questions_to_authors": "* Why is there no human evaluation conducted in helpful and harmless chatbots?\n* I understand that using only the value model is the benefit, but did you try MCTS based on the reward models used for the evaluation in each dataset? If a user has a clear idea of the reward he or she wants to maximize, it may be most effective to generate sentences using that reward model rather than a value model, as in existing methods.\n* Is there any way to apply the proposed decoding in DPO as well?", "extra_scores": {}}, {"review_id": "SGNpSXe5nT", "reviewer": "Reviewer_FoV3", "summary": "Quality:\n1. The paper presents a novel method (PPO-MCTS) for controlled text generation by combining Monte-Carlo Tree Search (MCTS) with Proximal Policy Optimization (PPO) models.\n2. The method is theoretically well-motivated and empirically evaluated on multiple tasks, showing significant improvements over baselines.\n3. The experiments are comprehensive, and the results are analyzed in-depth with relevant ablation studies.\n\nClarity:\n1. The paper is well-written and structured, making it easy to follow the proposed method and the experiments.\n2. The background and notations are clearly explained, aiding in understanding the technical details.\n3. The figures and tables effectively illustrate the key ideas and results.\n\nOriginality:\n1. The idea of using the value model from PPO for guided decoding with MCTS is novel and has not been explored before.\n2. The paper introduces a critical modification to the MCTS algorithm (initializing the Q of children actions from the V of their parent node) to improve exploration.\n3. The work contributes to the under-explored area of utilizing value models for inference-time improvements.\n\nSignificance:\n1. The proposed method achieves substantial improvements in generating preferable text across multiple tasks, including sentiment steering, toxicity reduction, knowledge introspection, and creating helpful and harmless chatbots.\n2. The results demonstrate the promise of search algorithms like MCTS even on top of aligned language models from PPO.\n3. The work highlights the valuable potentials of the value models, which are often discarded in practice, and recommends saving them for enhanced inference.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! Below is our response to your concerns:\n\n**Computational overhead:** In our submission we discussed the inference time overhead of PPO-MCTS in Sec 5.1. We see PPO-MCTS as a method to boost quality with more compute at inference time, and would like to explore techniques of reducing this overhead in the future.\n\n**Figure font too small:** We will improve this as well as the overall presentation in the next paper revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper proposes a novel and theoretically well-motivated method (PPO-MCTS) that combines MCTS with PPO models for controlled text generation, which is a significant contribution to the field of language modeling and controlled generation.\n2. The extensive experiments and analysis on multiple tasks provide strong empirical evidence for the effectiveness of the proposed method, demonstrating its practical value and potential for real-world applications.\n3. The paper explores an under-explored area of utilizing value models for inference-time improvements, unlocking the valuable potentials of these models, which are often discarded in practice.\n4. The work is well-written, clear, and easy to follow, making it accessible to a broad audience in the computational linguistics and natural language processing communities.\n5. The proposed method addresses an important problem in controlled text generation, which is a critical area of research with potential impacts on various applications, such as dialogue systems, content generation, and language model alignment.", "reasons_to_reject": "1. One potential concern is the computational overhead introduced by the PPO-MCTS method during inference time.\n2. While the authors provide some discussion and mitigation strategies, a more in-depth analysis and comparison of the computational costs and trade-offs with other methods could further strengthen the paper.\n3. The font of figures is too small.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "reF9LD2t9w", "reviewer": "Reviewer_auBY", "summary": "This paper proposes a method to apply Monte-Carlo Tree Search (MCTS) decoding over PPO-trained policy and value models for controlled text generation task. The key idea is to use the value model produced from PPO training as the evaluation function in MTCS decoding. Empirical evaluations are conducted on 4 text generation tasks. The proposed method outperforms a baseline of direct decoding with PPO policy model, as well as a best-of-n decoding baseline. Further ablation experiments are analyzed, including the effectiveness of the value model vs. reward model, the effectiveness of the MCTS vs. decoding with stepwise value, MCTS vs. more PPO, and so on.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for appreciating that our proposed method can be easily applied to post-RLHF LLMs. Below is our response to your concerns:\n\n**Discussion of efficiency:** Thanks for the suggestion. We will further expand our discussion on the efficiency of PPO-MCTS in our next paper revision, and include empirical results for decoding latency.\n\n**Clarity and the issue with $\\bar{V}(s)$:** We will improve the clarity in our next paper revision. $\\bar{V}(s)$ appeared indirectly in Eq 3, as part of the computation of the $Q(s, a)$ term in Eq 4. We will defer the mention of $\\bar{V}(s)$ to reduce confusion in Eq 3.\n\n**PPO+best-of-n being worse than PPO:** We were also quite surprised by this result. However, from Table 1 and 2 we see that PPO+best-of-n is consistently comparable with PPO. We think this implies that vanilla sampling is unable to produce outputs with a diverse range of rewards, and guided decoding is a better solution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. In general the idea of this paper is clear and straightforward. Empirical evaluations demonstrate the effectiveness of the proposed method over several different controlled text generation tasks.\n2. The proposed method is an inference-time algorithm, which means no further SFT, RLHF needed. It should be easy to apply to any LLM after RLHF.", "reasons_to_reject": "One concern I have is the efficiency of the proposed method. I like the discussion of the inference time overhead in Sec. 5. But I also think it is not adequate. I would love to see some empirical numbers like wall-clock time. I think this should be further explained.", "questions_to_authors": "1. I think some writings can be further polished for better fluency and consistency. For example, in the explanation of Eq 3 in page 5, $\\bar{V}(s)$ does not appear in the equation.\n2. Table 1: any idea why PPO+best-of-n is worse than PPO (51.47 vs. 52.44) in % of desired sentiment for positive sentiment?", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a pretty interesting paper that proposes using the value network learned in PPO for guided decoding.

Most reviewers are pretty positive about the paper. There are some flaws in the paper (no human evaluation, not enough justification for MCTS, inference speed trade-offs etc). However, i think it's interesting enough to warrant acceptance.

This is probably the best (decent) paper in my batch. I recommend acceptance.
Decision: Accept