Language Models as Implicit Tree Search
Authors: Ziliang Chen
Zhao-Rong Lai
Yufeng Yang
Liangda Fang
ZHANFU YANG
Liang Lin
Venue: ICML 2025 poster (2025)
Keywords: RL-free preference optimization; LLM based MCTS; LLM alignment;LLM reasoning
Primary area: deep_learning->large_language_models
TL;DR: RL-free preference optimization with asymptotic equivalence to approximate MCTS by language model learning stochastic policy.

Abstract: Despite advancing language model (LM) alignment, direct preference optimization (DPO) falls short in LM reasoning with the free lunch from reinforcement learning (RL). As the breakthrough, this work proposes a new RL-free preference optimization method aiming to achieve DPO along with learning another LM, whose response generation policy holds the asymptotic equivalence with AlphaZero-like search, the apex of algorithms for complex reasoning missions like chess Go. While circumventing explicit value and reward modeling, the neural implicit tree search executed by the extra LM remains seeking to equip DPO with reasoning procedure technically akin to AlphaZero. Our experiments demonstrate that our methodology outperforms both regular DPO variants in human preference alignment, and MCTS-based LMs in mathematical reasoning and planning tasks.

Language Models as Implicit Tree Search
Ziliang Chen
Zhao-Rong Lai²
Yufeng Yang
Liangda Fang? 2 Zhanfu Yang* 4
Liang Lin
Abstract
replicated by RLHF and DPO alone: the emulation often ne- cessitates synergistic integration with other techniques, i.e., meticulous prompt engineering (Wei et al., 2022), process- based reward modeling (Lightman et al., 2023), and Monte Carlo Tree Search (MCTS) (Xie et al., 2024a). Among these complementary approaches, MCTS stands out as essentially promising. due to its exploration of complex decision spaces in achieving high-level reasoning tasks such as game Go (Sil- ver et al., 2017b). Massive leading research were proposed to combine MCTS with preference optimization, whereas their MCTS procedures inevitably require the value func- tion learned by RI. for executing the search principles of Upper Confidence Bound (UCB). It is noteworthy that the critical advantage DPO to skip the value learning to achieve faster and more stable preference optimization than RLHF. The standard MCTS's reliance an RL-learned value function directly confficts with DPO's core strength of hypassing RI. entirely, showing a significant hurdle for their seamless integration. It implies the necessity to reconcile MCTS methodologies with the RL-free nature behind DPO.
Despite advancing language model (LM) align- ment, direct preference optimization (DPO) falls short in LM reasoning with the free lunch from re- inforcement learning (RL). As the breakthrough. this work proposes a new RI.-free preference op- timization method aiming achieve DPO along with learning another LM, whose response genera- tion policy holds the asymptotic equivalence with AlphaZero-like search, the apex of algorithms for complex reasoning missions like chess Go. While circumventing explicit value and reward model- ing, the neural implicit tree search executed by the extra LM remains seeking to equip DPO with rea- soning procedure technically akin to AlphaZero. Our experiments demonstrate that our methodol- ogy outperforms both regular DPO variants in hu- man preference alignment, and MCTS-based LMs in mathematical reasoning and planning tasks.
Rather than the regular MCTS, this paper started from its theoretical variant derived from (Grill et al., 2020b), where AlphaZero- -ikke MCTS can be treated as stochastic policy solved by the state-specific local optimization regularized by the reverse KL-divergence. With this regard, each state- specific local tree search decision asymtotically converges to AlphaZero- MCTS decision with the gap bounded by the empirical visit counts, thus, lifting the expressiveness of MCTS limited by the integer-count probability and sparse tree width. Regretfully, the local solution of this stochastic policy involves the parameter only solvable by dichotomic search per state. In terms of the exponentially complex state space in token-level language generation, this implicit tree search (ITS) is hardly applied in MCTS-based L.M research.
1. Introduction
Preference optimization paradigms, notably Reinforcement Learning from Human Feedback (RLHF) (Bai et al., 2022) and Direct Preference Optimization (DPO) (Rafailov et al., 2024b), are foundational to modern Language Model (LM) alignment, aiming to imbue these models with human's 's be- havioral characteristics, inclination, and value. In particular, DPO circumvent reward modeling so to directly optimize LMS with preferential response pairs, thereby reinforcement learning (RL)'s 's complexities and instability avoided to yield more efficiently and stably aligned models.
Distinct from preference alignment, sophisticated reason- ing capabilities underlying human brains are not typically
Contributions. We propose new RL-free preference op- timization paradigm aiming to approximate ITS by LMs. Specifically,
'Rescarch Institute of Multiple Agents and Embodicd Intel- ligence, Peng Cheng Laboratory: "Jinan University. Guangzhou, China; 'School of Computer Science and Engineering, Sun Yat- University, Guangzhou, China; "Department of Computer Science, Rutgers University. Correspondence to: Liang Lin <lining www..llyss..uuucc...
Beyond the original token-selection policy in DPO, we propose another LM to learn the global policy of ITS with regards to neural universal approximation. The preference optimization built on top of DPO, without dichotomic search and any other RL elements, inherits the critical advantages of the DPO family.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Language Models as Implicit Tree Search
In terms of the gradient analysis to the preference op- timization with ITS, learning its global policy yields the response generation with diverse and better aligned preference, therefore, simultaneously benefits Al align- ment and reasoning tasks.
trade off. DPO (Rafailov et al., 2024b) reconsiders the optimization from a interpretation of R(a, y) represented as R(x, y) = 3 log se(y]a) Eq.2 is equivalent with
Tur(yla) + 8 log ((x). With such regards,
LDPO (To; (eet) - p(
Self-improved preference policy augmentation and de- coding strategy are proposed for our ITS-baser prefer- ence optimization approaches, in order to align with the MCTS- LLM decoding. The connection between the decoding strategies and group-relative policy opti- mization (Shao al., 2024) has also been presented.
log a (8log TT lxr)
$ log Te (1(()120)
(4)
therefore the reward modeling phase is skipped to directly optimize the token-selection policy Tg..
Token-level Interpretation of LM Alignments. The afore- mentioned LM alignments focus on a complete response y. yet Ty is executed in each MDP step using token-level re-
Our experiments included the evaluation across human pref- erence alignment, mathematical reasoning, and mathemati- cal planning, where our approach concurrently reaped the optima against DPO variants and MCTS-derived baselines.
wards r(*,, ae) with / log Tarl (=.) (Rafailov et al., 2024a) re-formulates Eq.3 via the token- level interpretation
Ta(sk [=-yee)) =8 log Far(a, [xr]"
(a(a.
2. Preliminaries
no ra(ailss r(0,, a1)-3log n (a. (s))
For language generation, language models (LM) serve as a token-level Markov decision process (MDP) (S,AA.P,R.7) where the state 8, = (ar, y<c)) in S consists of a prompt æ followed by sequence of response tokens x< generated at the previous (-1 steps, and the action a, = yt in A de- notes the token selected at the current t step. Given this, the transition kernel P: (S,,A)>> S holds the deterministic mapping from (8,, az) to the next state 8 = (ax, ((--) with y-++1 = (y ye). The reward R: (S,A) - R quan- tifies the preference of selecting tokens, and T denotes the step cease the generation when ar is the end-of- sequence (EoS) token. The goal is to learn the sequential token-selection policy Ty that maximizes the accumulated reward (,,, y)= V r(Sr, dt). Vr E R.
max E. AaaammeD.aaaa (x))
T
Ty
max Eaj= Da
[r(2,, at) ar)+ ma
+ +
(5) So given (Mt, (:)=r(s;, az) log F RLHF with the reframed reward is maximum-entropp RL (Ziebart, 2010) whose fixed point solution leads to the optimal pol- icy тh that satisfies T& (ax(s;)=cxp) (2'(x.a,)-V (mx) with respect (s:) = 3og EPEA exp (Q"(s;, //333).
3
is noteworthy that the optimal state-action value function holds the initial value Q"((o,, ao) = R(x, y) = V*((s) +
3 Σ log Tadi s.) with V*(8o) = Vxx).. henceforth we have the objective similarly derived from DPO
RLHF and DPO. Token-level MDP needs R(x, y) to re- flects human preferences. RLHF (Bai et al., 2022) captures this from prompt x with its response pairs y (w) > ()) where > identifies (w) more preferable than ()) The com- parison is made by Bradley-Terry (BT) model (Bradley & Terry, 1952) in the contextual bandit setting
CT.DPO (Toi - -Bm
To
log Ta(a;" (s(") Trer (a." (s!")
33 T:
To
To (st)
log a (3)
log
exp(R(æz, (
Par (w) > 11)) exp(N(ax, ( ())) exp(R(a, (0))
(6)
where a,", of indicate the t-th token of the responses y" y": and 8e" = (ze, v..l. of [x) v'rcl respectively.
where R(E, y) can be learned through
MCTS and Alpha Tree Search. Given the state- action value treated as feedback from a contextual bandit, MCTS (Browne et al., 2012) builds an online search tree incrementally for decision making. (More details refers to (Silver al., 201 2017b)) (7))).CC)MSS) algorithms are famous in massive researches, among which the most successful case is Alpha Zero (Silver et al., 2017b (b) and its variants (Silver et al., 2017b; Schrittwieser et al., 2020). The MCTS vari- ant underlying these methods remarked as AlphaZero- tree search, compute a policy at the root of the search tree improved from the distribution predicted by the prior policy
min EE . (0) (R(x, y (())) - R(x, y () R
(2)
with the human preference dataset D. It serves RLHF as a KL-constraint RL objective
max P.eeD..yrrotte R(xx y) (an))3DDkii (T0 (x))]
(3) where the reference policy Tee is initialized by supervised fine-tuning (SFT) LM to learn the generation policy अe via PPO (Schulman et al., 2017), and B > 0 controls their
2

---

Language Models as Implicit Tree Search
R, which is updated by distilling back the tree-search policy to update the prior. The significant difference from other MCTS is AiphaZero-like tree incorporating as the prior during the search procedure. It leads to the heuristic search principle inspired from UCB:
searched least once by the previous simulation whereas those with n(s, a)=0 would be dominated by 0. In terms of the large action space in language and the deterministic policy in E it may cause a large simulation budget to improve actions never visited.
Recognizing that these limitations are intrinsic to the use of online visit counts in conventional MCTS algorithms, we supersedes the online tree-search strategy with stochastic policy optimization established in (Grill et al., 2020b) (de- picted in Figure.1.b), named Implicil Tree Search since the optimized policy is provably equivalent with the AlphaZero- like tree search exploration defined in Eq.7
Σ n(ssaa) A'E.ACTTS
a" A arg max (", (c)((s(s)) aEANNTS
1 #n
(7) where e > is a balance factor between exploration and exploitation in the MCTS search space AMCTS- The four- stage procedure of Eq.7 is shown in Appendix.A.
3.1. MCTS as Regularized Policy Optimization
3. Implicit Tree Search: Warm-Up
More specifically, for any state, the action selection formula in E holds the identical interpretation
AlphaZero-like MCTS variants have been intensively ex- plored in leading researches for LM training (Feng et al., 2023; Zhang al., 2024a) and alignment (Xie et al., 2024b; Chen et al., 2024a), in order to mitigate their downsides of reasoning and long-form generation ability captured in post- training. In spite of different algorithm designs, the method- ologies are consistent with MCTS in the data-generation manner: merges with the decoding strategy to generate responses for training data augmentation, then the token- selection policy Te and visit counts updated along with these data, further renew the decoding by Eq.7. Despite sig- nificantly advancing LM alignments, the decision-making pipeline relies on the online state-action visit count n(s, a. per state-action pair. In terms of the integer-count probabil- ity and the sparse tree width in the initial training iters, it inevitably suffers from two critical problems.
=(ass)
(s) A arg max
(T AN(ss)
(8)
*(als)
aEAAMETS
where #{aas)
| W "(a.a') represents
1+n(a,a)
the empirical visit distribution and AN(8)
VEriCAACTT n(s,a')
AMMETS Ee'' AMETS n(s,a') denotes the state-specific multi- plier. Notice that for any sES, the empirical visit distribu- tion f-1ss) is the only way that search algorithm influences the optimal action of tree search. In language generation context, we set π= so for any sES, +--ss) holds a corre- sponding predominant policy T(-(s) as
Theorem 3.3. (Asymptotic equivalence between ITS and MCTS policies) Vs E S, let (( be the solution of
Cold-start exploration expressiveness. VENEA n(x,a') l+nleaa) is the key to differentiate मे and x, so AlphaZero-like tree
7(-18) 2 arg max Q Th (8) y(s)
search typically employs its empirical visit distribution 1+n(e.a)
y(a)E5
AMCTs|+ + AE n(e,a') its exponential generalization 1+ (+(e,aa'))
Ax(())DK(TT(((s)
2o/ (m((s.a))) to explore the tree structure. Whereas the discrete nature of visit counts limit the expres- siveness of exploration strategy.
where 3 denotes the |McTTT diierss-iimessoonlll simplex, and TTa (s) = (Q a1), (** (s,a),, az),..., QT (s, alAwers)) is the Q-value vector with respect to the state s. Then the visit counts increase, the empirical visit distribution (-1s)) in Eq.8 converges to (--ss) with the upper bound
Proposition 3.1. Given a fixed (E)/ the action selec- tion probability by the exponential empirical visit distribu- tion holds its value with the equal cardinality of Z.
(((())==((1)))
AMCTS +
(10)
Proposition 3.2. Given a learnable rER, the action selec- tion probability by the exponential empirical visit distribu- tion holds the value in the range
|MMTSS + N
where N indicates the total rounds of simulation.
[ACTTT
Theorem.3.3 is concluded from the definition. and proposi- 1,5 in (Grill et al., 2020b). The theoretical result verifies that, given sufficient simulation steps, there exists an asymp- totic equivalence between the exploration of AlphaZero- tree search (-[ss) and the stochstic-samplinn policy (-Is). Note that the policy optimization in a simplex allows the
The problem is cold-start because early decisions heavily influences the tree growth yet the ratios of integers are more unstable when the visit counts are small. It may drive the language generation into bias or sub-optima.
Sparse-action improvement. á solely improved for actions
3

---

Language Models as Implicit Tree Search
P
dg ...
so(-le.)
Ay((1)
(((r))
-
Language
Model +
p
F(-lo2)
P
simdate
Axx(#z) a(s2) (r2(
the stochaste
oepen upeneotl (olo, Alloneed 3artaoo
Og
(c). Language Model as Implicit
(o). Explicit Tree by MCTS
(b). Implicit Search
Tree Search
Figure 1. Comparison between the diagrams of (a).MCTS (regular MCTS and AlphaZero-like tree search), (b). Implicit Tree Search (ITS) (Grill al., 2020b), and our IT-PO algorithm.
continuous value change in k--ss) that prevents the risk of cold-start expressiveness. Besides, the reversed KL di- vergence is smooth on (-) ensuring the sparse-action improvement resolved.
The vital problem roots in the exponentially increase size of the valid state space. As demonstrated in token-level MDP, texts are generated by sequential token selection with the state 8, = (ar, yec) deterministically transmitted as ((s,, a.) + 8:+1 = (x, y 22++1). It implies that for each prompt x. the valid state space holds the size [V|* (V) indicates the size of token vocabulary V) exponentially increase with t. Given such challenge, Lemma.3.4 .44 solely promises the local policy so that the actor-critic modeling is required to obtain MCTS
Accordingly, the expand and backup stages along with the MCTS procedure require the state-specific stochastic policy optimization formulated as follows
Lemma 3.4. (Solution of ITS policy (Grill et al., 2020b))
vs E S, the solution (-|s) of Eq.9 9 holds
and QT* simultancously, as leading approaches do. What's worse, the local policy also relies on (x(8;) inferred by dichotomic search per state, implying the computation and buffer also exponentially increasing. This problem even more severe when the action space AMCTS become sentence-level.
Tol To( (t)
va, E AMCTS, ((a = (s()
a(8:) F (8c, ar)
(11)
where (8)) is defined as
(s,) & max a E R, s.t.
Σ T(a|s;)= =
4. Preference Optimization with Implicit Tree Search
aEAucTs
2).a(s:) 2 a(s))min
max aEAANCTS
(Q(s), a) + +NNTo(als))
In the previous section, demonstrated the advantages of т over the empirical visit exploration employed by regular MCTS methods, while its solution of Lemma.3.4 .44 is hardly implemented in the LM realm due to the state-specific non- differentiable hyper-parameters (s;)). In this section, we derive the new RI.-free preference optimization paradigm to approximate without either Q function or (s;)), yielding the response generation MCTS without value modeling.
3).)(s:) S a((s
max Q(s,, a) +AN
aEAANcTS
(12)
Lemma.3.4 is derived from Appendix.BB B.3 3.3 in the paper.
3.2. Challenges of Combing Implicit Tree and LMs
Observed that AacAN (a|s;) monotonically decreases on (((s))))n:(((() maax) the theoretical result guarantees the state-specific param--ar a((:)) uniquely identi- fied using dichotomic search over (a(s) )min; a< max)) max). In other words, म can not be universally optimized by gradi- ent descent and even for each state, (-|[s))ss solution solutio in 11 is not exactly closed-form. To this end, can not be flexibly used as explicit search like regular MCTS algo- rithms and instead, only applicable for policy distillation to update the Q function in AlphaZero- MCTS. However, is hardly applied for L.M --ased preference optimization.
4.1. Language Models as ITS Policy
Specifically, we chase for the universal approximator of based the extra policy network n. parameterized by the other language model yo (Figure. 1.c). It supports the instant inference of π (-[ss;) (i.e., no dichotomic search required to obtain ((s))), no matter was visited or not.
Thought consistent with ne in the reversed KL constraint, т is essentially stochastic strategy generalized from de- terministic policy in the AlphaZero-like tree search (Theo-

---

Language Models as Implicit Tree Search
3.m.3.3). It motivates us to initialize its universal approxima- tor F by supervised fine-tuning. Specifically, we fine-tune pre-trained LM to obtain Taf. whose parameters initialize the reference policy Tref, the token selection policy ke, and our ITS policy approximator T. Then we applied the DPO variant algorithm, i.e,, conservative DPO (cDPO) (Mitchell, 2023b) to update Tg:
The lemma demonstrates that we may construct the accu- mulated reward of preference prompt-response pair by the ITS exploration starts from each state of the preferred and dispreferred sequences (i.e., root or intermediate node). As demonstrated in (Rafailov et al., 2024a), DPO-like meth- ods hold the dense reward re- re-parameterized as r(8; a.) = 3 log To (o(ar(s)) - 8 log Tror (arl)). Combine this with Lemma.4.1 leading to Theorem 4.2. Stte-Syynchoonus IT-PO) A prompt x drawn from D has a response pairs y (w) > y 1 Given A= ~ Th (-10 (1) )[= and A= ~ (- (9) )
(0) = ((ag)()))))))) D [[1- loglot (uo(1r (d y ) lug v² y [())))
(13)
it holds
where u(-) indicates the preference logit derived from BT
model, c E [0, 0.2) denotes the margin then when 0,
U2( y (w) .y ") = R(ar, (0)) - R(æx, (aaz,11') (0)) (p, 0) m1(p, 0) + 5(0),
cDPO degenerates into DPO.
After training with ming (e: f), the parameters of ma. Tref are frozen to update the parameter of o.. This manner provides the stable wy to derive the optimization of so i.e. Implicit-Tree Tree Preference Optimization (IT-PO).
To
Tu Ta(a lo (ofm))
To To (a.((s)!
Σ AN(s! (w)
s.t.
(
(("))
(ār (m))
Ti m1
To To( (1)
Σ (x))
(
To (ār(())) (1))
t=1
4.2. Implicit Tree Preference Optimization (IT-PO)
Tw
(a
(2))
T
To(a! (1) (1)
5(0)=3
log
log
IT-PO seeks for learning मे to substitute ने without either reward or value functions. It is noteworthy that x (-1ss) in- herently contains ( 8,) from Lemma.3.4, which serves as the implicit policy evaluation for गे with the lower values implying increased exploration and vice versa. Therefore if To approximate गे well enough, ITS can implicitly derive the value function from क without explicit modeling Q
(a)
(w) (()))
(aa
(15)
then the step-synchronous IT-PO is proposed by
LSs-T-PO(Pp 0) (m "0 (00 D. ANTT, -I(1-) log or (z, vnm) yd 1) +e oogo v",
"))) (16)
For simplicity, we first consider step-synchronous ITS with the policy Ty. wherein the MCTS action node is token-level, ie.. AMCTS = A. Specifically, given fixed and rounds of simulation (i.e., (s)):) is also fixed), the ITS policy (11ss), ES can be uniquely determined according to Lemma.3.4. 4. Suppose that achieve the optimal parameter such that u (a.) = x (a)(ss)), it holds the observation
Theorem 4.2 establishes that optimal approximation be- tween π and Tip must preserve their stochastic search strategies' conformity to the BT preference model. The minimization of Eq.13 is also derived from cDPO that incor- porates the margin to tolerate the preference noises possibly introduced by Á, Á drawn from Re.. benefits Te to gen- erate the high-quality responses that exceed the old data.
Lemma 4.1. Suppose (x, (r)) denotes a pair of prompt and its preferred response. For each state st -xx y (w)) the action selects either the preferred token a, (w)) = Vt (w) or a random token âr sampled from (-1s (!")))) ); and each state (1) = (xx. (1)
Step-Asynchronous ITS. MCTS algorithms significantly improve the LM's 's' reasoning ability where the action space of each node focuses on sentence. It holds the asynchronous step between मे and Tg. i.e., AMCTS = U A", where A is the sentence-level action space with n-length tokens and N indicates the maximum length of sentences. Observe that the token-level MDP could be also identified into the sentence level, where म. Te. Tref take their sentence-level ac- tions by generating token sequences ended by "[/n]" token (Definition B.3 in Appendix). We re-frame their sentence- level policy as S T T so that given the state 8; E Ss
y,), the action selects either the dispre- ferred token at = vi or random token os sampled from To- (-15()). It holds
R(x, y (w)) =
Tw
r(s(
(1))
(a)) - (x))
aa(a (w) (w)
No ra.1s ग.. ( |s (w)
and the sentence-leve action A, = (a ) E As (Nr indicates the token number in the t-th sentence action and ag
(ap
18
(w))
R(x, y (1))
(5) indicates the i-th token in the 1-th sentence), and the
sentence-level reward rs(st, A,) = Σi r(s;, (()).
Ti
no (aa
no a (000
r(s (1)
a.) ->x(s(")
(a,")) (1) (s)))
मे गे (0))
Given this, we derive the sentence-level ITS optimized by step-asynchronous variant of Fq.4.2:
(14)
5

---

Language Models as Implicit Tree Search
Theorem 4.3. (SterAAyyicrroouus-PPO))) A prompt æ drawn from D has a response pairs y (w) > y com- posed of Ts. T sentences, rexpectively. A Al de- notes the t-th sentence in y y,,, respectively. Sup-
improved dataset D They join with D to refine the token- selection policy via learning 0 with cDPO. We elaborate the IT-PO algorithm pipelines of its step-synchronous and step- asynchronous cases in our implementation in Appendix.C. C.
(*)) (1) transmits along sentence-level MDP pose the state St st
Self- Leff-Imprvement in Gradient Analysis. Through analyz- ing the TI-PO loss function's gradients with respect to y, we demonstrate how T.p facilitates the generated responses both diverse and better aligned with ground-truth pref- erences. For clarity, our analysis is derived from the step- synchronous ITS using Us for preference alignment and focuses on the positive preference logit in log[o (U=))
(Definition. B.3), at (10.3) /a!k.)) indicates the i-th token in the (d))
(wm,3) /st (1.)) denotes the sequential context ahead in /y"")/y")) Suppose that the sentence- level policies Teet. Tū. b. are identified by I.M-based
St /A!"
of a (165)
/a. /a
policies Tref, To, Teg. respectively; A.
(a.") a ((
(-1s
(1m)
3.3) 00) = 8, .3t (1+1)
- log(a y (w)))) v0)
P(o ai ):A, (a.
(1)
(N)) ~ (-10 ((.s))))ss"
),8( (0)
a
(VpHu V
V Van( - log (AR))
li+1) = P((()) .i
(1) (8)) It holds
higher when roward estimate is wrong
Usla, " )) niz, , Riw, v ))
Tx
( a
(w))
V log (a,
(w) (w)
1 12 (0,0)- 6 (0))
s.t. V oolli
Jop (a
(1)) 18, (m))
1=1
st. st.p (), 8)=
Σ (x(
II (a (m (mi))
II
tuta 2 (af 2/9)
Tel la!
Vi Tog(T
(2u1)s) (10)
(a
Fp (0)))
He (9.00
rala
10 (00
Ax AN (8( (- To To(a! (1) |s
(1)
V (o 4
Typ (a. 10
Tp(a
-Vom==
(a 10) 18/
ma(a )
8 log
log
To (ā (s()) V loglT ( (ārl=(()) (3))
Pa
(a." (
(17)
TTp (āclo
then the step-synchronous IT-PO is proposed by (o 0) = E -((1-) logoo (Ue((, y (m),
(19)
Compared with DPO, the second multiplier observed from the decomposed formula achieves the identical gradient ef-
(w (m.v
, yd 1e log a (Us(,, 19
fects. V log(T (w)) |s {("))] and - V log[T (a. (")" | ]]
(18)
similarly exist in the first term yet they take the likelihood ma(a (w)) (a
increase and decrease effects with coefficients
4.3. Self-Improved Training and Decoding
In Sec.4.1, 4.2 LM yp serves as a universal approximator of the ITS policy across the state space. Since behaves as the stochastic variant of AlphaZero-like tree search, we turn to discuss their common purpose, i.e., distilling मeP back into the policy my to enhance both their performances.
and ta(a & (1 It implies that when 7.p <To to the ground- truth preference pairs, IT-PO takes the aggressive likelihood influence to align के and To while the conservative likeli- hood influence if 7.p >Tg. More importantly, the implicit tree sampled from the ground-trun trunhdhtruthhhh preference nodes, i.e., à, (-p(-11 (")), ā. (-)(
Preference Policy Augmentation. Regular MCTS algo- rithms used to sample recision-makingg trajectory to refine the original policy ny, which is recently treated as type of generalized policy improvement. Instead, (Grill et al., 2020b) used to distill their ITS policy by DD (T, тO). It eases the sampling process but also sacrifices the benefits derived from the high-quality response trajectories.
(f) also influence the like- lihood: - log[[,, (")) )] and V Log ((a ls (")] demonstrates that on account of the ground-truth preference nodes, Tे learns to search lower preference child nodes from s (w) yet higher preference child nodes from s with the same ganservative-aggeesee ates certain responses from the preferred context yet explore more diverse responses when the context is not preferred.
strategy. Hence मे gener-
With this regards, we propose preference policy augmenta- tion by resampling M responses {y generated from each prompt x ~ D by a.. H are then constructed into pairs with their preference relations evaluated by Uss or Un. thus, (y, > y, holds if either (at, Vo: D;, ,1,) > 0 at the token level or (x,( y, ,,) > 0 at the sentence level. After ranking their value by Us or Uas. the tMp-M prefer- ence pairs are selected for each prompt x in D. Then we collect them across all prompts in D to construct the ITS
ITS- -TSdgdd Decoding. Beyond self-enhanced training, re- cent study on LLM-based MCTS (Feng et al., 2023) demon- strates promising results in improving the decoding process by MCTS. Motivated from this, we propose the stochastic- tree variant decoding from the spirits of their MCTS-a and MCTS- rollout strategies.
1). ITS-a. For each initial state Troots the original MCTS-a
6

---

Language Models as Implicit Tree Search
decoding strategy applied Alpha-like tree search for policy evaluation then backup the visit count ni(s, a) of the expo-
0.63
0.8
_(* nential visit distribution En "("",."')77 to guide decoding. Since Tp is the universal approximator of ,. the stochastic variant of Alpha-like tree search. It is straightfoward to exp(loy/F (ales)))
0.55
0.6
0.45
0.4
0.35
use the exponential version of Tip Ea (
exp(log] (a/s))/>)
0.5
(step-synchronous IT-PO) or E., exp(log] | (a") (e)]//>) (step- asynchronous IT-PO) in our decoding strategy.
0.2
0.5
0.15
0.1
2). ITS-rollout. When the root Tooot and the intermediate state nodes sufficiently differ from the states visited in train- ing, the simulation rounds N behaves more closely zero to fail the approximation between र and I in Theorem.3.3. In this case, F need to be updated to adapt the state Froot as the backup process in MCTS. Due to no value function avail- able, we employ Th to implicitly evaluate arbitrary pairs of responses y 1/2 generated by (-)x), then the sampled
0.25
0.5
0.75
1
0.45
Reference
DPO
RTO
T-ora1
T-DPO2
IT-PO
ITT-PO0
WITT-PO
-T-PPPp
(a) Win rate
(b) Win across alternative policy improvement
across temperature
scaling
Figure 2. Win rate measured by GPT-4 via the consistent prompts in previous studies: (a) Win rate of haselines decoding with differ- ent temperatures; (b) Win rate of me and n across the alternative phases of their preference policy distillation.
responses with preferences evaluated by 0 would join the meta-update of o the state x
x-p- 44 Va Lea.
5. Experiments
(20)
s.t. v1 > U2 if us (2z, V1 y2) 0,
In this section, we demonstrate the superiority of IT-PO from the step-synchronous (Theorem.442) and step-asynchronous (Theorem perspectives. In the ttep-synchronous cases, IT-PO trains mip perform token-level ITS in order pro- vide the fine-grained human preference alignment; in the step-asynchronous scenarios, we evaluate Thp trained by IT- PO to perform sentence-level search in step-asynchronous scenarios, i.e., mathematical reasoning and planning tasks where LLM-based MCTS algorithms are extensively used.
which refreshes En (xp to facilitate our decoding strategy. ITS-rollout can be treated as test-time- training version of ITS-a. Its implementation first updates 'p' by (20), then use ITS-a with ş to facilitate the decoding process. In our experiment, 8 responses for each test prompt were generated to achieve self-training resulting the extra 0.5~1 hour as the decoding warm-up stage.
Provided the decoding probabilities obtained by ITS- the BF-S strategy (Breath-first Search) can be applied based on the implicit advantage function solely approximated by Th and no. More specifically,
5.1. Experiments on Token-level Preference Alignment
Anthropic HH dataset (Bai et al., 2022)! consists of 170k di- alogues between a human and an automated assistant, each of which presents as a history with alternative responses with respect to different preferences annotated by humans. We conduct the conventional evaluation setup using Pythia 2.8 (Biderman et al., 2023) the base model, then each dialogue with its preferred completion in Anthropic HH training set is incorporated for supervised fine-tuning to derive three LMs: the parameter-frozen Tee and parameter- initialized Ty, Tg- In terms of preference alignment on token-level MDP, SS-IT-PO with respect to the LMs 0, y are alternatively trained, then the IT-PO variants both com- pared with token-level DPO-family baselines, i.e., DPO (Rafailov et al., 2024a), RTO (Zhong et al., 2024a), TDPO, and TDPO, (Zeng et al., 2024a).
A (a, 8) (a, 8) "IQ"' (a', salaa no{-|s)]
2 8) N
1
Σ (a))
a' (1~
= (a(s) (s) To(a(s)
F(a|s)
(a(s) (x ro(al18))
Σ
{(als))
a' (1
(a(s))
Te(a'l (s) 7(a' $)
= -x)
T(aas) 8)
N
(a(s))
ne (a'
())
x AN(a) (a)a)
N
(a
(21) where N indicates how many responses drawn from my to approximate the advantage function. Such decoding strategy is closely related with wisdom of group-relative policy opti- mization (GRPO), a well-known value-free RL algorithm employed to train Deepseek (Shao et al., 2024).
The experiment primarily aims for three evaluation metrics: 1). Accuracy: we adopt the evaluation split in (Zeng et al., 2024a) to train all models then evaluate their performance
7

---

Language Models as Implicit Tree Search
Table 1. Comparison in terms of the trade-off between Alignment (accuracy) and Diversity (entropy) on the Anthropic HH dataset. The indicates higher values are preferable.
Table 2. Performance comparison of different methods on GSM8k and Game24 datasets
Performance (%) / Tokens
Setting
Method
Method
Alignment Diversity
GSM8K
Game24
Acc (%)
Ent t
CoT-greedy
41.4 98
12.7
76
DPO
59,43
3,196
BFS-V
52.5 485
64.8
369
RTO
61,43
3.314
Path @
MCTS-o
51.9 561
63.3
412
TDPO, 60.08
4,727
MCTS-Rollout
47.8 3.4k
71.3
670
TDPO2 67.33
4.915
ITS-a (ours)
53.2 561
67.6
380
IT-PO 0 (ours)
67.75
4.564
ITS-Rollout (ours)
51.6 3.8k
73.2
646
IT-PO & (ours)
69.12
5.315
COT-SCMAI
46.8 500
14.6
684
in terms of the accuracy on the generated responses relative to chosen completions in the test dataset; 2). Diversity: Nucleus sampling with p = 0.95 to generate 25 responses then the predictive entropy across the responses indicates the generation diversity. Win rate: all baseline approaches evaluated through GPT-4 against the chosen responses in the test set, so that > 50% implies the human preference alignment achieved in their performances.
CoT-SCORM
52.3 500
50.6
684
BFS- BOR-
70.90
1.6k
Equal-Token
MCTSORM
69.34
649
ITS-a (ours)
70.64
1.6k
ITS-Rollon (ours)
71.42
698
5.2. Experiments Mathematical Tasks
Both LMs and y utilize I to enhance the decoding strategy. The exponential rate ? =1 consistently across the evaluation of three metries. This choice aligns with MCTS- o, which employs token-level tree search in alignment tasks. Accuracy and Diversity across the baselines are presented in Table 5. TDPO, demonstrates competitive performance, achieving alignment accuracy comparable to IT-PO 0, even exhibiting superior diversity. On the other hand, IT-PO yp, trained as the stochastic tree policy, outperforms TDPO₂ by a significant margin in both alignment and diversity metrics. It is because that LM 0 in our framework performs more likely as policy evaluator trained to boost the evolution of stochastic tree policy T.
Our second experimental suite includes the tasks of mathe- matical reasoning on GSM8K (Cobbe et al., 2021), MATH (Hendrycks et al., 2021) and mathematical planning on Game24 (Cobbe et al., 2021). Although the benchmarks are famous in evaluating LLM's s reasoning capability by PRM (process reward model) (Lightman et al., 2023) and MCTS- based methods (Feng et al., 2023), they are nontrivial for DPO family since explicit value function can not be skipped to execute MCTS reasoning strategies.
Baselines and Evaluation. Since most DPO-based ap- proaches can not adapt to LLM reasoning without explicit value modeling, we are more interested in the comparison between TI-PO and state-of-the-art tree-search (TS) LLM and Chain-of- of-Thugght (CoT) (Wei et al., 2022) baselines in (Feng al., 2023). More specifically, the evaluated base- lines for GSM8K and Game24 are derived from LLAMA-7b base model, specifically include CoT- CoT-greedy (greedy value search by CoT), BFV (Breath- -irst search with their learned value function), MCTS-a (AlphaZero-like tree search with their learned value function), MCTS-rollout (MCTS-a vari- ant that allows the backup process happen in the interme- diate step). As a counterpart, we incorporate the policies To and T with their LMs fine-tuned by cDPO (Eq.13) and step-asynchronous IT-PO objective (Eq.17). respectively, then achieve their alternative post-training via preference policy augmentation. After five iterations, the policy models jointly facilitate the decoding processes via ITS-a and ITS- rollout strategies. All baselines are evaluated in the single path setup via Path @ I and Equal-Token, the latter try to
To verify our assumption, we further observe their Win rate illustrated in Figure.2(a). Through scaling the temperature during inference, T-DPOs are found quite sensitive to the temperature, with lower performance than most baselines when the temperature value are extreme. Instead, both IT- PO 0 and IT-PO yp consistently performs with robust value over 50% in 7 out of 10 cases where the other baselines underperform or even fail in the qualified Win rate level. In Figure.2 (b), we further observe the Win rate progress when IT-PO and IT-PO & by through their alternative pol- icy distillation. When no alternative strategy used (iter 1), the win rate of IT-PO and IT-PO oo are solely on par with the win rates of DPO and RTO, respectively, which largely underperform T-DPO variants. While after five iterations of alternative preference policy distillation, Win rates in IT- PO 9 and IT- o are both incredibly improved to exceed their early, even their teachers' performances. These obser- vations are consistent with our analysis to s's gradients.
hhtps:/hhuggingfccecocmmm co/me///......eectttaeaaee /laaa/a.amaaaa
8

---

Language Models as Implicit Tree Search
Table Path@1 I metric on Game24 with different node size.
Table 4. The experimental results in MATH. All baselines em- ployed Qwen1.5-325 as their base models.
Performance($)) / Tokens
Method
width=6 width=20 width=50
Baselines/Decodingg
greedy CoT -a -rollout
MCTS-a
41.6 243 63.3 412 74.5 573
Qwen 1,5-32B
36.1
MCTS-Rollout
43.8 401 71.3 670 80.7 833
MCTS- (Qwenl.5-32B)
36.0
36.7
BFS-V
43.2 206 64.8 370 74.6 528
ITS- (p=Qwenl.5533)
39.8
40.2
ITS-a (ours)
46.1 267 67.6 380 75.0 647
ITS- (u= (p==wennl.-33BB)
37.9
38.2
ITS-Rollout (ours) 48.9 489 73.2 646 81.8 954
compare the results with the similar scale computation con- sumption. For the evaluation on MATH, we construct the training set integrated with the training splits of GSM8K and MATH, then consider Sowen1.5-32F (Team, 2024) as our base model. Beyond this, we also introduced LLAMA3.1- 1- 8B as an alternative of yp to verify whether yp can be re- placed by a smaller LLM. To this, we have the evaluated LLMs (0.4) defined by (Qwen1 1.5-32B.ween..... (Qwen1
complete reasoning path) from preferred/disprefeered con- texts (as defined by A, and A, in Eq. 4.3). This enables faster search and backup operations compared to standard MCTS. As a result, even with bounded search width and depth during inference, the stochastic policy demonstrates robust performance due effective training simulation. In order to support our claim, we further ablate the maximum tree width and node size during inference to observe the performance variation across different baselines. As shown in Table.3,4, expanding the node size and tree width sig- nificantly boosts regular TS-LLM performances. While ITS-a a and ITS-Rollow have already achieved impressive results with the small node size and and tree width. Beyond this, they also enjoy the performance growth along with the increasing exploration space.
and respectively, We also em- ployed greedy CoT (3 shots), MCTS-a, and MCTS-rollout for their comparison.
Implementation. Distinct from human preference data with pairwise responses, reasoning tasks only consist of question prompts and its correct solution responses. It motivates us to reconfigure their data to adapt our preference optimiza- tion regime. Beyond this, since our "tree-search" strategy is indeed stochastic policy, the search depth and breadth for training LLM &p were not limited in all datasets, while their decoding procedures i.e., ITS-a and ITSlrollout, inherited the pruning setup derived from the MCTS baselines to ad- dress the heavy computation while the tree search runs for reasoning-oriented inference. Details refer to Appendix.C.
In Table.5, we presented the evaluation in MATH that con- tains more difficult mathematical reasoning tasks. In terms of the greedy CoT results in LLAMA3-8B (20.5), some observations can be found in the table. First, we note that the MCTS strategy derived from GSM8K is unreliable in MATH, probably due to the conflict between the problem complexity and limited search width and depth during train- ing, while ITTS- and ITTS TTS-rollout did not suffer from this problem. Second, with a weaker model (LLAMA3-8B) to implement LLM sp, IT-PO still enabled the improvement of LLM-based reasoning. implics the feasibility of IT- PO. Specifically, despite avoiding value modeling, IT-PO introduces the extra LM yo instead of the single LM 0 in stan- dard DPO variants, leading to the increased computational and memory requirement. While the evidences in Table.5 demonstrated that using LM & with the significantly smaller and weaker base model than LM 0, ITS-((0 =Qwen @.Qwen..-32BB. 15-32B, I = LLAMA3-8B) still yields the results very competitive with ITS-(0 @wwnl.5-320 y = Qwenl.5-32B),
Results. According to the GSM8k results (Table 2), when examining @ath@1 performance across all baseline methods, tree-search algorithms (excluding our proposed methods) don't show significant advantages over standard CoT ap- proaches. MCTS variants actually perform worse than BFV, despite their higher computational requirements. However, the 24me24 results tell different story. In this task, CoT approaches perform poorly, largely because Game24's struc- ture allows for wider and deeper search trees, which better showcases the strengths of tree-search algorithms (Table B.5). But interestingly, ITS-a and ITS-rollout consistently outperform other approaches, regardless of the default tree width and depth limits during inference.
6. Concluding Remark
This superior performance be attributed our IT-PO training regime. Unlike traditional approaches that slowly build sparse trees based on visit counts, our approximated म encourages broader exploration across the entire action space. This approach is computationally efficient since IT- PO only needs to sample the next sentence (rather than the
This paper presents new RL-ffree methodology to equip DPO with MCTS interpreted as stochastic policy to better align LMs with human preferences, and simultancously outperforms MCTS- based LLM reasoning baseline methods in both mathematical reasoning and planning tasks.

---

Language Models as Implicit Tree Search
Acknowledgement
In International Conference on Machine Learning, pp. 2397-2430. PMIR, 2023.
The research was supported in part by Guangdong S&T Pro- gramme (Grant No. 2024B0101010003); in part by The Ma- jor Key Project of PCL (No. PCL2024A04, PCL2025A02): in part by National Natural Science Foundation of China (NSFC) under Grant No.622061 10, 62176103, 62377208,
Bradley, R. A. and Terry, M. E. Rank analysis of incom- plete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-345, 1952.
and 622761 14; in part by the Science and Technology Plan- ning Project of Guangzhou under grants 2024A04J9896, 2025A0313565.
Browne, C. C.B Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. A survey of monte carlo tree search methods. IEEE Transactions on Computa- tional Intelligence and Al in games, 4(1):1-43, 2012.
In particular, we thank all the reviewers for their constructive suggestions that help improve this work.
Chen, G., Liao, M., Li, C., and Fan, K. Step-level value pref- erence optimization for mathematical reasoning. arXiv preprint arXiv:2406. 10858, 2024a.
Impact Statement
This work advances preference-based learning for large lan- guage models through improved exploration mechanism, which has implications for AI alignment and safer deploy- ment of language technologies. By enhancing LLMs' rea- soning and long-form generation capabilities through more principled exploration and preference learning, our approach could lead to more reliable and controllable language mod- els. However, improved reasoning capabilities could also en- able more sophisticated text generation that may be misused. The integration of MCTS with preference learning repre- sents a step toward more transparent optimization of lan- guage model behavior, though careful consideration should be given to the selection of preference data to avoid encod- ing harmful biases. We believe the technical advances pre- sented here can contribute positively to the development of more capable and aligned language models when deployed thoughtfully with appropriate safeguards and oversight.
Chen, G., Liao, M., Li, C., and Fan, K. Step-level value pref- erence optimization for mathematical reasoning, 2024b. URL https: / aaxiv. org/ /as//aa///// /abb//240..000
Chen, Z., Wang, K., Wang. X., Peng, P., Izquierdo, E., and Lin, L. Deep co-space: Sample mining across feature transformation for semi-supervised learning. IEEE Trans- actions on Circuits and Systems for Video Technology. 28 (10):2677-2678, 2017.
Chen, Z., Huang, X., Guan, Q., Lin, L.,, and Luo, W. A retrospect to multi-prompt learning across vision and language. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 22190 22201,, 2023.
Chen, Z.,, Zheng, Y., Lai, Z.-R., Guan, Q., and Lin, L.. Diag- nosing and rectifying fake ood invariance: restructured causal approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 1 11471-11479, 2024c.
References
Abdulhai, M., White, I., Snell, C., Sun, C., Hong, J., Zhai, Y., Xu, K., and Levine, Lmrl gym: Benchmarks for multi-turn reinforcement learning with language models. arXiv preprint ar arXiv:2311.182.3 2023.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems, 2021. URI. https://arxiv.. org/abs/2 10.14 2021.
Amini, A., Vieira, T,, and Cotterell, R. Direct prefer- ence optimization with offset, 2024. URL https: //arxiv..ao///////// org/ abs/ 2202. 10571.
Coulom, R. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., Das- Sarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. Training helpful and harmless assistant with rein- forcement learning from human feedback. arXiv preprint arXiv:2204.05862. 2022.
Dong, H., Xiong, W., Goyal, D., Zhang, Y., Chow, W.. Pan, R., Diao, S., Zhang, J., Shum, K., and Zhang, Raft: Reward ranked finetuning for generative foundation model aligmment, 2023. URL https: aawii..rgg/.//////......... abs 220330066777
Biderman, S., Schoelkopf, H., Anthony, Q G., Bradley, H., O' Brien, K., Hallahan, E., Khan, M. A., Purohit, S., Prashanth, U. S., Raff, E., et al. Pythia: A suite for ana- lyzing large language models across training and scaling.
Dong, H., Xiong, W., Pang, B., Wang, H., Zhao, H., Zhou, Y., Jiang, N., Sahoo, D., Xiong, C., and Zhang, T. Rlhf workflow: From reward modeling to online rlhf. arXiv preprint arXiv:2405.0786. 2024.
10

---

Language Models as Implicit Tree Search
Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L.,, and Madry, A. Implementation matters in deep policy gradients: A case study on ppo and trpo, 2020. URL https: / arxiv. org/ abs/ 2005 12729.
Liu, Z., Lu, M., Zhang, S., Liu, B., Guo, H., Yang, Y., Blanchet, J., and Wang. Z. Provably mitigating overop- timization in rlhf: Your sft loss is implicity an adversar- ial regularizer, 2024b. URL abs/2405.0 6436.
Feng, X., Wan, Z., Wen, M., McAleer, S. M., Wen, Y.,
Zhang, W., and Wang, J. Alphazero- tree-search can guide large language model decoding and training. arXiv preprint ar arviv:2309.1 17179, 2023.
Mitchell, E. A note on dpo with noisy preferences & rela- tionship to ipo. arXiv preprint arXiv:2304. 12345, 2023a.
Mitchell, E. A note on dpo with noisy preferences & rela- tionship to ipo, 2023b.
Feng, X., Wan, Z., Wen, M., McAleer, S. M., Wen, Y., Zhang. W., and Wang, J. Alphazero-like like tree-search can guide large language model decoding and training, 2024. URL https::///// / / /aaxiviiiv..///...///aaa////aivv org/ abs 2309 171799.
Ouyang. Y., Wang, L., Yang, F., Zhao, P., Huang, C., Liu, J., Pang, B., Yang, Y., Zhan, Y.. Sun, H., Lin, Q., Ra- jmohan, S., Deng, W., Zhang, D., Sun, F., and Zhang, Q. Token-level proximal policy optimization for query generation, 2024. URL https: htt////xxvvv.r////// 2411.00722
Grill, J.-B., Altché, F., Tang, Y., Hubert, T., Valko, M.,
Antonogiou, I., and Munos, Monte-carlo tree search as regularized policy optimization. pp. 3769-3778, 2020a.
Pan, L.,, Albalak, A., Wang, X., and Wang, W. Y. Logic- Im: Empowering large language models with symbolic solvers for faithful logical reasoning. In The 2023 Con- ference on Empirical Methods in Natural Language Pro- cessing.
Grill, J.-B., Altché, F,, Tang, Y., Hubert, T., Valko, M., Antonoglou, I., and Munos, R. Monte-carlo tree search as regularized policy optimization. In International Con- ference on Machine Learning, pp. 3769-3778. PMLR, 2020b.
Rafailov, R., Hejna, J., Park, R., and Finn, C. Your lan- guage model is secretly a q-function. arXiv preprint arXiv:2404. 12358, 2024a.
Hao, S., Gu, Y., Ma, H., al. Reasoning with language models is planning with world model. arXiv preprint arXiv:2305. 14992, 2023.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Ad- vances in Neural Information Processing Systems, 36, 2024b.
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang. E., Song. D., and Steinhardt, J. Mcasuring math- ematical problem solving with the math dataset. arXiv 2021.
preprint arXiv:2203.00
Kirk, R., Mediratta, I., Nalmpantis, C., Luketina, J., Ham- bro, E., Grefenstette, E., and Raileanu, R. Understanding the effects of rlhf on I1m generalisation and diversity. arXiv preprint arXiv:2310.06452 2023.
Rafailov, R., Sharma, A., Mitchell, E., Manning, D., Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Ad- vances in Neural Information Processing Systems, 36, 2024c.
Kocsis, L. and Szepesvári, C. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
Rosin, C. D. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61)) 203 213-230,10 2011.
Liao, W. Chu, X., and Wang, Y. Tpo: Aligning large lan- guage models with multi-branch & multi-step preference trees. arXiv preprint arXiv:2410. 12854, 2024.
Schritwieserr, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L.. Schmitt, S., Guez, A., Lockhart, E., Hassabis, D.,, Graepel, T., al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839); 604 609, 2020.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. arXiv preprint arXiv:2305.200550 2023.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Liu, A., Bai, H., Lu, Z., Sun, Y., Kong, X., Wang. S., Shan, J. Jose, A. M., Liu, X., Wen, L., Yu, P. S., and Cao, M. Tis-dpo: Token-level importance sampling for direct preference optimization with estimated weights, 2024a. URL mtttss://arxis .rgg 2210/2410.0 04350.
Shao, Z., Wang, P., Zhu, Q. Xu, R., Song. J., Bi, X., Zhang, H., Zhang, M., Li, Y., Wu, Y., et al. Deepseekmath: Push- ing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.035 030000330 2024.

---

Language Models Implicit Tree Search
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, I.., Kumaran, D., Grae- pel, T., et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint urXiv:/712.0/8// 2017a.
boosts reasoning via iterative preference learning. 2024c. URL htt.sttss:/aaxxiv.coo wwwp/////////a/o/ooooo./.../ss 2400. 24451
00451.
Yao, S., Yu, D., Zhao, J., et al. Tree of thoughts: Deliber- ate problem-sol with large language models, arXiv preprint arXiv:2305.1060) 2023.
Silver, D., Schritwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676):354-359 2017b.
Yuan, W., Pang, R. Y., Cho, K., Li, X., Sukhbaatar, S., Xu, J., and Weston, J. rewf-rew language models, 2024. URL https:tpp///ot. arxiivvvvv www.wwv..rroooooooooooo.ooooooo. orgg/as////eeeeoooere//rooreeeer abs/ htabs/441.. 2401 10020.
org/
Yuan, Z., Yuan, H., Tan, C.,, Wang. W., Huang. S., and Huang, F. Rrhf: Rank responses to align language models with human feedback without tears, 2023, URL https: // //arxiv. org/ abs 2304 05302.
Tafjord, O., Mishra, B. D., and Clark, P. Proofwriter: Gen- crating implications, proofs, and abductive statements over natural language. arXiv preprint wrxiv:2012.13045 2020.
Zeng, Y., Liu, G., Ma, W. Yang, N., Zhang, H., and Wang, J. Token-level direct preference optimization. arXiv preprint arXiv:2404. /9990, 1999, 2024a.
Team, Q. Introducing qwenl.5, February 2024. URL https: www.wewww..........eeeeeeeem. http:/..//oo/////////eeee// qwenl. 5/.
Zeng, Y., Liu, G., Ma. W. Yang. N., Zhang, H., and Wang. J. Token-level direct preference optimization, 2024b. URL
Uesato, J., Kushman, N., Kumar, R., al. Solving math word problems with process-and outcome-based feed- back. arXiv preprint arXiv:2211.142733 2022.
http:://acxvv.orr/
https://arxivv.vo wrg.iiiorrgaeo 224p://abb/244..... 119999.
Zhang, D., Zhoubian, S., Hu, Z., Yue, Y., Dong, Y. and Tang, J. Rest-mets*: Lim self self-training via process reward guided tree search. arXiv preprint arXiv:2406.03816 2024a.
Wang, X., Song, L., Tian, Y., Yu, D., Peng, B., Mi, H., Huang, F. and Yu, Towards self-improvement of Ilms via mets: Leveraging stepwise knowledge with curriculum preference learning, 2024a. URL https: //arxiv. org/ abs/ / 2410.. 06508.
Zhang, X., Du, C., Pang, T., Liu, Q. Gao, W., and Lin, M. Chain of preference optimization: Improving chain- of-thought reasoning in llms, 2024b. URL https:// arxiv. org/ orggabs/////ooooooooeo..../....r 2406.09133
Wang, X., Song, L., Tian, Y., Yu, D., Peng, B., Mi, H., Huang. F. and Yu, D. Towards self celf-improvement of lims via mets: Leveraging stepwise knowledge with curriculum preference learning, 2024b. URL https: //arxiv. org/ abs/ /21///21100 06508.
Zhong, H., Feng, G., Xiong, W., Cheng, X., Zhao, L., He, D., Bian, J., and Wang, L. Dpo meets ppo: Reinforced token optimization for rlhf. arXiv preprint arXiv:2404. 18922,, 2024a
Wang, Y., Liu, Q., and Jin, C. rlhf more difficult than standard rI? theoretical perspective. Advances in Neural Information Processing Systems, (16776006-760322 2023.
Zhong. H., Feng. G., Xiong, W., Cheng, X., Zhao, L., He, D., Bian, J., and Wang, L. Dpo meets ppo: Reinforeed token optimization for rlhf, 2024b. URL https:// a arxiv. oraoorgg/ee abss//ab//aa abs/ 2404 18922.
Wei. J., Wang, X., Schuurmans, D.,, Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., al. Chain-of thain-of-thoughhe thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24877, 2022.
Zhou, W., Zhang, S., Zhao, L., and Meng, T-reg: Pref- erence optimization with token-level reward regulariza- tion, 2024. URL htttttts///aaae org/ a4s/2412. 02685.
Xie, Y., Goyal, A., Zheng, W., Kan, M.-Y., Lillicrap, T. Kawaguchi, K., and Shieh, M. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint (xX.::4455000551 2024a.
Ziebart, B. D. Modeling purposeful adaptive behavior with the principle maximum causal entropy. Carnegie Mel- lon University, 2010.
Xie, Y., Goyal, A., Zheng, W., Kan, M.-Y., Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint ar arXiv:2405.0045/ 2024b.
Xie, Y., Goyal, A., Zheng. W., Kan, M.-Y. Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte carlo tree search
12

---

Language Models as Implicit Tree Search
A. Related Work
The integration of search-based optimization techniques in language model alignment has significantly advanced Al aligmment, with Reinforcement Learning with Human Feedback (RLHF)(Bi et al., 2022; Wang et al., 2023; Kirk et al., 2023; Dong et al., 2024) being a widely used approach. RLHF employs reward models trained from human feedback to optimize model behavior through reinforcement learning, typically using Proximal Policy Optimization (PPO) (Zhong et al., 2024b). However, RLHF has been criticized for instability, sample inefficiency, and over-optimization issues (Engstrom et al., 2020; Liu et al., 2024b; Chen et al., 2023; 2017; 2024c). To address these challenges, methods like Reward Ranked FineTTunin (RAFT) (Dong et al., 2023) and Rank Responses to align Human Feedback (RRHF) (Yuan et al., 2023) have been proposed to refine ranking- based optimization without explicit reinforcement learning. More recently, Direct Preference Optimization (DPO) (Rafailov et al., 2024c; Amini et al., 2024) has emerged as an alternative, allowing language models to be aligned directly from human preference data without requiring reward model.
Unlike PPO, which operates within reinforcement learning framework by optimizing policies through reward feedback, DPO reformulates the alignment problem as a supervised learning task, making policy updates more stable while maintaining alignment with human preferences. Further refinements, such as processing the paragraph at token level with methods such as TDPO (Zeng et al., 2024b), T-REG (Zhou et al., 2024), TPPO (Ouyang et al., 2024), and TIS-DPO (Liu et al., 2024a), improve efficiency by incorporating voken-wise adjustments, improving preference alignment in a manner that contrasts with RLHF's reliance on policy gradient updates.
Monte Carlo Tree Search (MCTS) has been extensively applied in decision-making tasks, particularly in game-playing AI, as demonstrated by its success in AlphaGo (Silver et al., 2017b), AlphaZero (Silver et al., 2017a), and MuZero (Schrittwieser et al., 2020). Recent advancements have expanded its application to large language models (LLMs) for structured text generation, such as in AlphaZero-like Tree-Search for LLMs (TS-LLM) (Feng et al., 2023). Similarly, Xie et al. (Xie et al., 2024c) propose an iterative preference learning approach, using MCTS to refine step-wise reasoning capabilities in L.LMs. Further developments by Wang et al. (Wang et al., 2024b) introduce self-improvement techniques where LLMs leverage MCTS for preference-guides reinforcement learning, while Chen et al. (Chen et al., 2024b) focus on step-level value preference optimization, allowing fine-grained preference learning intermediate steps. Zhang et al. (Zhang et al., 2024b) extend this concept with chain preference optimization, improving long-range decision- makinn for complex reasoning tasks, Lastly, Liao et al. (Liao et al., 2024) introduce Tree-based Preference Optimization (TPO), which integrates MCTS with preference alignment techniques to refine LLM outputs progressively. Despite these advancements, key challenge remains: these approaches still require learning an explicit reward value function, which is critical for optimizing the search process and improving the efficiency of LLM training and inference.
Our work proposes Implicit Tree Search (ITS), which integrates stochastic policy optimization with AlphaZero- search principles while eliminating explicit tree structures. ITS leverages reversed KL-divergence constraints and a stochastic sampling policy to enhance exploration expressiveness, addressing cold-start issues common in MCTS- methods. Similar ideas have been explored in Monte Carlo-based regularized policy optimization (Grill et al., 2020a), (Wang et al., 2024a) they use pairwise training framework that enables LLMs to self-improve through MCTS behavior but ITS extends these principles to preference learning in language models.
Furthermore, our approach aligns with broader research on Al safety and preference-based learning (Yuan et al., 2024; Xie et al., 2024a; Chen al., 2024a; Mitchell, 2023a). ITS represents novel search-and-learn paradigm that improves structured reasoning in language models without relying on explicit tree expansion, bridging the gap between MCTS and modern alignment techniques.
C.1. Fundamentals of Monte Carlo Tree-Search Methods
Monte Carlo Tree Search (MCTS) has been widely adopted an effective strategy for solving problems requiring sequential decision-making and planning. Traditional MCTS operations, as introduced by (Koesis & Szepesvári, 2006) and (Coulom, 2006), include four key steps: selection, expansion, simulation, and backpropagation. However, these operations can be adapted for more advanced frameworks like AlphaZero (Silver et al., 2017b) which incorporates a learned value function and policy network to guide the search process.
To address challenges in balaneing exploration and exploitation, we utilize a variant of MCTS with modified Predictor Upper Confidence Tree (PUCT) algorithm (Rosin, 2011). The algorithm selects actions o each node s; as follows:
Gp = arg max (Q(s), a) + U (s),
13

---

Language Models Implicit Tree Search
where U81 a) is calculated using the formula:
V N
(ss a) = Spuct To(s,a)
1 N(s.a)
Here, (ss, a) represents the visit count action a at node s, and Cpuct is constant controlling exploration, as defined by:
Es Ex N (s. b) + Obase +
Cpuct log
+
Cinit
Obase
Node Expansion and Assessment: Upon reaching leaf node sL. if it is not terminal, the tree is expanded by generating possible successor nodes. The value of the leaf node is then estimated using neural network. For terminal nodes, a reward function R(st) is used, or an Outcome Reward Model (ORM) serves as an approximation (Uesato et al., 2022).
Value Propagation: Once leaf node is assessed, the computed values are propagated back through the path sp, $1.... SL. For each node, the visit count updated as:
a(s, N +1,
and the cumulative action value is updated as:
W(st, ((s,, v(s))
The mean action value is then computed as:
a))
Q(sr, a) a)
This combination of learned value functions and search-based methods enables efficient exploration of large decision spaces, as demonstrated in AlphaZero (Silver et al., 2017b) and its applications to tree-seacch-uuide language models (Yao et al., 2023; Hao et al., 2023).
B. Proofs.
B.1. Proof of Proposition 3.1
Proof. Given E IR and Va' AMCTs/ (a}, n(s, a') are fixed, the probability of empirical visit distribution to the action holds
denotes as AmCTs]+ AMCTT "(
1+n(s,a)
1 a))
1 (IAMCTS) + Ew Amce///cs// n(ss a')") a')" AMMTS + Ee'EAAcss/(ad (a) n(s, a') + n(s, a)"
(22)
AMCTS| + E'' "
Since |AMCTs! + Eves/////((a)) n2(s, a') is constant, the exponential empirical visit distribution only changes along with o(s,a') changes. Due to AMers! 1 as "tree" definition, |AMCTs| + E''EAmeTs/ta o(s.a')" Note that f(x) = l-c is bijective with respect to e >> 1 and when r + 0, (n" n E Z U (0}} holds the consistent cardinality ctr
with Z. The proposition has been proved.
B.2. Proof of Proposition 3.2
Proof. To prove the proposition, we only need to prove the following lemma:
Lemma B.I. Given positive integers a, b, and {e define
1 1+ b
f(r) a+1+ Ei cf b"
We claim that for all real r, the value of f() lies strictly within the open interval ( 1)
14

---

Language Models Implicit Tree Search
Proof. 1. Asr -oot Since o' 0 and cf for each i, we have
1+b r- a + 21=1 C -
1+0 a a+ a+1+0+0 a+1
lim f(r) lim 00
Thus f(r) never goes below 1/(a + 1).
2. As too: Let M max (b, c1, c2 c2...., ca). For sufficiently large r, M dominates b" and each c, so the numeratir and denominator in (r) asymptotically proportional to M giving
lim f(r) = 1. +
Since b" and of increase with r, one can show f(r) itself is strictly increasing in r. Consequently, its image over r E R is precisely
a+1 1).
Counterexample.
Because f(r) bounded below by a+1 any real æ with
0< 1
+
cannot be realized by f(r). For instance, choose
1
2(a + 1)
We observe
2(a + 1)
a-
but there is no real for which f(r) zo. Hence, values in (0, _
are not attainable.
Set a |AMTTs| 1, = n(ss, a), and 6; n(8, a.), Va, E AMCTS/ (a), the proposition has been proved.
B.3. Proof Lemma 4.1
Proof. As discussed in Lemma.3.4,
m0(a; 5 r(ss, az) = a(si) - V** - Ax((s)) To Ro(ar(s))
(a(al))))= = (N(ss)) a(si) QT (st, a.)
(23)
T. (a st)
where QTa ax) = r(8,, a²) + (st). Provided (æ, (w)) denoting pair of prompt and its preferred response, we construct the preferred state-action trajectory along with the token-level MDP, i.e., {(s{ .a (")))]T w.r.t s (x, y (w))
and a, (w)) (mr) Then based on the definition, for the 1-th state in the preferred state-action trajectory, we sample another yt
action à; from the parameterized ITS exploration policy He i.e., â ~ ( For the preferred state-action trajectory,
E3.23 holds at each step so that
Te Σ a (ar)
To aass( (w0) - (=0 (s(")) To To(a, (wx) ((n) Tt (a, (wr) (wr) 8t
R(x, yd
r(s)
(w)
=
(24)
1=1
1=1
and Vt E Tu..
r(s) (w) a.) a(s)"o)) (=( Av(s(()) To(ārls!
(25)
न (ā, s
(w)
15

---

Language Models as Implicit Tree Search
Therefore
Tw a1)
a(st (w)) - (=) (1) -x((s( To(a, |s! (mu)
R(x, y (w)) )
r(s (w)
T (a. (1e)
(uu)
1=1
t=1
Tu
TO TT(āilss) (
a($) (10))
(5 (1)) ( (
(26)
Te. (ag (w))
To(a, 10 10 (w)
To no(@ollp (w))
-
TTp (a, (w)
(()))
Tे. (ār T (8, (w))
Therefore R(x (w)) = Et= r(s) (1c)
aNx( (
No (ā.
(a
The (a.la
The dispreferred state-action trajectory from (x,, y²) can be also constructed in the same routine, i.e., {(s , .a, ( w.E. - (x, ( and ( = ( For the i-th state the dispreferred state-action trajectory, we sample another action a, from Ti ie.. à (-1s ()) For the dispreferred state-action trajectory, it holds the mirror formulations of Eq.24-26, then from the same deduction, R(x (0) Σin Ein āe) ->x(s())
(r(o))) ;ā))
maia! " (el ma (!
is hold.
(a 1 (a.))))
B.4. Proof of Theorem 4.2
Proof. Let's introduce the dense reward reparameterzation theory in (Rafailov et al., 2024a):
Lemma B.2. (Reparameterzed dense reward) (Rafailov et al., 2024a) Given a reference policy Hyet and a parameter B > 0 all reward classes consistent with the Plackett-Luce (and Tradley-Terry models, the step-wise reward r(st, as) can be represented with the a re-parumeterization
r(8r, at) = -Blog ((a))))) - 3 log Tree (ar))))
(27)
within the token MDP where V*(+:) = 0 for all terminal state.
Here combine Lemma.4.1 1 and Lemma.B.2 to certify theorem. Specifically, V** V*(ss) = 0 for all terminal state given any sequence, since 0 is optimized from DPO-like algorithms. By Lemma.B.2, we have the dense reward decomposition
To To s (11))
r()) ā.) = log (o(ā)ls(")) - log Feat (ā, (a]])/"))== 3 log
VI E [Tw)-
(28)
Troe (a, (8 (w))
The decomposition holds in the dispreferred states such that
T (1)
(()))) ā.) = 33 log no (ārls;)) 3 Blgg ne (ā. = Bllog
AI E [7i]-
(29)
Teat (ū 1s
where the dispreferred state-action trajectory along with the token-level MDP, iee, {(8) (1) a ) is constructed by
16

---

Language Models as Implicit Tree Search
a (a, ( and a. = yt 11 [7i]- Given this, we have
Uss ()) ) =R(x,, 2 (w)) R(x, y ())
= R(x, (m))
Tw
To
T
71
Σ
r(s)
(w)
a.))
+
r(8 (w) a+)
- Σ
r(
+ 11) ,a.)
Σ
r(s (1) ;,,)))) a.s - R((x, y 20))
1=1
1=1
Tw
Ax(()
To
(wc)
56
(ur)
To Ta (s (wc))
Ax(o(")
Ta (1)
To
1s(
To (((
T (a)
(ar)
bे (ār 18 (wc)
т T 10())
(p:())0)
pc(p:0))
To ne(ārls( (10))
7i
To To( (
3 log
3 log
Teel (a. (8 (w))
Trof (ār(8) 18/
(30)
The theorem has been proved.
B.5. Proof of Theorem.4.3
Here we provide the formal proofs to the sentence-level version of Lemma.4.1 and Theorem.3.3. They are based on the definition of Sentence-level MDP:
Definition B.3, (Sentence-level MDP) Suppose that M = (S, A, T) denotes the token-level MDP. It identifies the
sentence-level MDP Mg PPS... as
N
Ss U As = AMCTS U A As + Ss; : Ss x As 7 R; TT n=1
(31)
where S" indicates the sequence composed of n sentences ended by "nn" in order and obviously, S C. S. A" is the sentence-level action space with n-length tokens and N indicates the maximum length of sentences. The transition kernel Ps and reward space Rg holds PsCS x As + S and R&CS x As R. To this, if we consider the policies hold the decomposition πT (A)(s)) -I π (a, (1)
(a 1s (i) (A, = (a 1 E As denotes the sentence-level action, N;
indicates the token number in the selected sentence action, (i) indicates the i-th token in the t-th sentence, and sti) (s, a,
(1)) ...
.a (((1)))) Rs C x As + R, to this, we define S (A,, 8) E Rs such that r (st,, = Σ. No r(s, ai (0))
Lemma B.4. Given the prompt æ with its preference response pair y ((w), y composed of TS T sentences, A(").
(1) denotes the t-th sentence in y " y
respectively, Suppose the state (mi) st transmits along sentence-level MDP,
a (w,i) /a! (1,5)
(1,6) indicates the i-th token in the A(""//A st /s;
(w,)] (l.)) denotes the sequential context ahead of a, (.w.))) /a in
(1.i)
// (9. Suppose that the sentence-level policies S no. T are identified by I.M-based token-selection policies Tref
Te. T.. respectively; A, = (a (1)
a (N)) ~ (-1s (-)) ) ).3. (.)))) = = g((+1) = P(s)) a. y: = (a a (Ne))
T (-18/) (1)
, ((+1)) P(s a (0)) holds
T
N
To (a (wx)) (w.))
N
R(x,y (w))
Σ
r(8(1)
(1)
a
(1)
-)N(( (10)
II 1=1
ग. (a.
(w,()
18
(ur,o)
क. sp (a,
(1) 18(
(32)
N
|
To (1:1)
(1.5)
N.
no (a
(0)
r(5
)
(1)
-xx(s!
(1)
II 1=1
(a
(1.1)
(1,))
T. (a.
Proof. Suppose that T (st.)) denotes the state-action value function on the sentence-level policy g. with respect to LM 9. Due to gड defined with the action space As = AMCTS, it results in
T (A,ls)
T (A, ss)
(Arls)) = (N())) a(s:) 2 (81, Ar)
= r (st, = a(s:) Vză (st) AN(s))
(33)
[A, (s)
17

---

Language Models as Implicit Tree Search
where A, = (at )= E As denotes the sentence-level action, N₂ indicates the token number in the selected sentence action, and (6) indicates the i-th token in the (-th sentence. It holds Q (8:, A.) (8,, A.) + V (8.) -i: r(si di y (8:).
(i)
(8)
+
Provided (z, () denoting a pair of prompt and its preferred response, we construct the preferred state-action trajectory along with the sentence-level MDP. In particular, suppose The denotes the number of sentences included in the preferred response ( which can be uniquely identified through the location of "\n" tokens. We denote them as sequence of
sentence-level actions {A, JEE
(w) ) Vt E T. and make the decomposition such that {(s} a)())) with respect to
A [w) (w)
(w) LS
+1"
3
wg( +
(a (w.1)
(on,
(34)
at
81
(w)
(2x A
(w))
A (11)
Then for each (s} (")) )
(w,,3) St
(m) a
1n,.1)
a ( Vi [NV
(35)
where a (mm.)) denotes the response token y
(w))
in (w)
2g N/
Then we provide the derivation
T N(W) R(x, y (w))
Tg
r r( c a4 = Σ
(8)
p (s) (w) Ae)
T (A (w) 18 (w))
axs; (w)) - (s} (w)) (s (w)
(A(( (1m) 1s (ar)
(36)
(a, (11
|s ((w))))
a(s) (w)) (s! (N((s (wn)
I Tेe (a, (w.))) (())))))
N(W)
Ny("))
(a (w)))) (s ((n.)))
(((s(w)) (s( AN(S (wo))
II
( (1n.)))
(a,
Beyond this, for the 1-th state in the preferred state-action trajectory, we sample another action A, from the parameterized
ITS exploration policy T iee,, A = (ā.. a
(Na) (-1s It can be telescoped into (a (0) ~ (- No
), with
respect to a) = (x. ((T) 1 ai , ... ai (a-1)] 1). Therefore VT E [T.], it holds
T (A (w)
, (s( A.) Σ r(a, (t) {(()) =a(s ((w))) v= (s(()) AN(S (w))
T (Acls) ((0))
N no (a
=a(s( (w)) v (s/_0)) AN (w))
(37)
N
( (()))) o (a:
i=
M.
(1) (s()
=a(s( (w))
vng (s!
-
x (a
(a, (1) (1()))
Derived from the similar routine in 2q, we combine Eq.36, 37 to obtain
T-5
Ny(w))
(wsi)
(an
N:
To a (2) (()
R(x, (())
r8 (6)
a(
-x (
II
a
(38)
(w:))
(w.t)
1=1
ग. a
(1)
3
18

---

Language Models as Implicit Tree Search
For the dispreferred response y it refers to the mirror notation of (w) (1) to construct the dispreferred state-action trajectory {( )
Th and for each (8) Al"). az (1.3)
ب NJ +i and 8 s((.)) (s (1) (1.1)
(w)
at ... . ))
) Vi
[N[]] in v Given this, for the 1-th state in the dispreferred state-action trajectory, instead of A! we sample another sentence action A, from the parameterized ITS exploration policy म.े i.e. A. = (a) ag (N)) ~ <-(-)) It can be telescoped into {a ~ (+B( with respect to 8! = (xx, Al ... _ di deduction routine, holds
(1) a 1)) From the same
N,
(1) {(1))
r (s (1)
A.) A.)
a(s?") V (s!")) As(s
49)
To a
At E [7,9]
(39)
(1)
i=1 p a
8::
and
T
N₂
N II
|
(1,i)
(1,6) | (1.3)
N.
x (a. 4 (x(0
R(2, y))
Σ
r r(3 ai
(1)
Aw (s(
To a
(40)
Te a |s| (1,8))
Ca, (3) |5
1=1
On top of Lemma.B.4, we prove Theorem 4.3 follows
Proof. According to Lemm.B.2, we have
r(8 a 3 log
na [a
8
S.t.Vt TO, Vi No:
Tre a,
(3) (()
(41)
no Ta(ā (a,
r(8(" (.)) = 3 log
S.t.Vt E "iViiEN
Tref
Therefore
(25 y( (0) = R(æ, (1)) - R[xx, ()))
7
N.
7.
N,
T N.
T3s N,
-( [R(x y (m))
(1)
( +
2
r( (
) y (00)
+
t=1
1=1
(=1 i=1
1=1 1=1
1=1==1
T
No
- R(x, ((1)
(( a(o)) + R(I, ())
r
a(.))
1=1
N
Ta(a!
1s((0) (1)
1/S N.
To (a
(1)
((())
+ 3
log
log
Teef (a s((1)
Tref (a (1((()))
Nr(w)
(v (w.()
N
T
N
(1,8) (1,5)
N:
(3) (1)
AN (8:
(nr)
II
To (a,
18
To
AN (0)
To aa
tt (a,
(w)))
186
(m.)))
==
ai
1=1
(1.1)
(a.
(i)
# (2)0))
-4
2 N,
T/ N.
(1)
n T
8
no (āt
+
B
log
log
Teel (a
(2) ((())
π Tref (a, ((())))
Am
iml
(0)
(42)
Set up N( = = and NV.") (4.1 then the theorem has been proved.
19

---

Language Models as Implicit Tree Search
Algorithm 1 The algorithm pipeline of IT-PO
Input: preference dataset D; pre-trained LLMs 0, y.
Hyper-parameters: e; K; the batch size M construct the batch of cDPO; the number of alternative training Ralter-
Output: LLMSs 0*, 00,""" =4"..
Initialize LLMs 0, yp by SF with the prompt-response pairs drawn from D, Nateer O;
Minimize LaDPO (0) post-train LLM 0 with the prompt and its pairwise responses drawn from the dataset D;
repeat
Implicit- Tree Preference Optimization:
repeat
Construct the training batch by M triplets drawn from D;
For each triplet (æe y ()) construct {(a]"), (") ((")) } {aa 81 ) based on the rule of token-level MDP
(1)
(w.rt. LSS-IT-PO (p; ; 0) for LM alignment) or sentence-level MDP (w.rtt fas-ITPP((;;0) 0) for LM Reasoning);
Set K K To Vt Tw (parallel), draw K tokens from (-1s, (w)) construct the samples of token-level action
random variable ā,, draw K. sentences from क (-16(())) construct the samples of the sentence-level action
random variable Ag:
Set Ki T VI E Ti (parallel), draw K2 tokens from p to construct the samples of token-level action
random variable ã, or draw K₁ sentences from (-1s,)) to construct the samples of the sentence-level action random variable Ac; Fix A. minimize Lys- 8) update yp for LM alignment minimize fas-ITPo((p: to update & for LM reasoning:
until The number of training epoches reach the same of (0).
Preference Policy Augmentation:
For each prompt æ in D, generate responses } using Tip
For each prompt æ in and jjE [K], calculate Usa (ar, yi Fz) or Uns( yıs Uj);
Build the token-level policy augmentation pool D = {(x, y Jy Ivi + [K], Us ye y, 0z,
(HUx Uc v2) (K)) build the sentence-level policy augmentation pool D (2, Uey Uj) vi + [K], (x, y. y2) 0, (z. y, y2) topk (1, 3/ fy {)){))((())
Minimize LODPO to post-train LLM 0 with the prompt and its pairwise responses drawn from DU D or D U
Nalter Natter + 1;
until Natter = 7aatter
0 t 0, 4p + sp.
C. Implementation
The algorithm pipeline of IT-PO are presented in Algorithm. 1. The algorithm implementation almost holds the consistency with its theoretical foundation except for two details:(I) the specification of AN(8:); (2) the yps gradient implementation in (ss-ITPPO(P; f) and Las-ITPO 8).
Suppose that (=( AN denote the number of reasoning paths generated from the state 8,, which consists of a prompt x and its responses ((),, y with their contents in the previous - steps. For each preference pair, we set K., and Vi {1...., Ti), AN ( K., where Kw,, K₁ denote how many search start (9) respectively. Notice that Tw, T, change with respect to the preference pair. So IT-PO adaptively configure K T Ki K to balance the optimization with different response lengths in (")", ())) for each pair. We set K 8, inspired from the number of sampled responses for each prompt many RLHF implementations.
(w))
VI E (1...., , ), AN (n()
from the 1-th leaf nodes s st
K.
Ti
In pps gradient analysis in (ypp 8), the gradient of o consists of terms in the form
sa es)) (a
[og[s(a,(ss)) V logg (ar]s)).. Due to
ma(ar) ax). E (0, +ox), updating the models with ma(a.le:) V logl (ar [s:]] may suffer from exploding/vanishing gradients. (a,le))
To this, we used their logarithmic scaling se(a;]s:) - exp((og( (To (s)) log (ag(T)(((lss))) to ensure the less sensitive
(a(())))
20

---

Language Models as Implicit Tree Search
Table Task setups. The node, width, and depth search space parameters. The max trec-width and tree-depth follow the empirical experience in (Feng et al., 2023).
Task Task Category
Train/test size Node
Tree Max width Tree Max depth
GSM8K Mathematical Reasoning 7.5k 1.3k
Sentence 6
8
Game24 Mathematical Planning 1.0k / 0.3k
Sentence 20
4
MATH Mathematical Reasoning /-
Sentence 6
8
Table 6. Performance Comparison on ProofWriter and Chess Endgame Tasks
Setting
Baselines
ProofWriter (Aec %) Chess Endgame (Win rafe
Path@1
CoT-greedy
37.72
58.14
BFS-V
48.94
67.75
MCTS-a
66.71
96.90
MCTS-rollout
69.23
98.76
ITS-a (ours)
71.77
99.21
ITS-rollout (ours)
75.31
99.83
Equal-Token CoT-SC-MAJ
36.50
9.84
CoT-SC-MAT
36.58
73.80
BFS-V-ORM
63.42
93.18
MCTS-ORM
60.86
94.26
ITS-a (ours)
74.26
96.48
ITSSrollout (ours)
78.15
98.57
update ratio. In ips gradient analysis in fas-II:P((p; 0), it can derive the similar gradient as
V VoH
Σ
T
As
(())
II
(a,
(wr |s
(wn)))
log
(wri)))
(s (m:))))))
Te (a,
(w.+)
|s
(w))))
N II
ne (a
8
v logg (a()=
(a.
1=1
(43)
T/a
|
(1.0) (11)
14
- (p)0) --
Σ Av
(8t
(0)
II
Tol a
log
(a
(12) (1 (1:))]))
(1.1
Te (a;
1=1
N,
N:
n
V log t. (a
(1)) (1())(())))) (1)
where we also took the logarithmic scaling for the gradients in their implementation, e.g.,
(1..)) (mn,i)
To a st
II 1
exp (Iog(Te(a) (w.)) ((w.)))) (( ( (a( ((00)))))))))
(44)
(a
(w))
(w)d))
1=1
and so do others.
To train our policy networks in GSM8K, Game24, and MATH, we propose the preference data reconfigured from their training set. For each question with correct response y, we compute log कeef (yel (z) across all responses y from another
21

---

Language Models as Implicit Tree Search
question generate the hard negative preference pairs, then take them to initialize va via cDPO. We set e=0 human alignment task, yet set 6=0.25 to mathematical reasoning and planning tasks. As for tree-based decoding, employ the same tree-width pruning strategy in (Feng et al., 2024), difference only rises from the deterministic decision making stochastic decision making. In GSM8K, we also provided the component analysis by varying é in the range {100%, 75%, 50%, 25%, 0%) ). along with the results ranged from 53.2, 52.9, 53.4, 51.8, 50.1, accordingly. The performance drastically drops when the ratio less than 50%.
D. LLM-based Reasoning Experiments Beyond Mathematics
We offer evaluation based on ProofWriter (Tafjord et al., 2020) for deductive logical reasoning, and Chess Endgame (Abdulhai et al., 2023) for long-term multi-turn decision making. For ProofWriter, we follow (Pan et al.) to generate the test set, then the rest are merged to 41,433 training instances. All training and test instances employed the prompt template in (Pan et al.) that initiated the start CoT, then we employ LLAMA2-7B as the base model and all fine-tuning methods only run for single epoch. For Chess Endgame, we follow the experimental setup in (Feng et al., 2023). With regards to each prompt-response pair (æ,, ()) in ProofWriter and Chess Endgame, we find the dispreferred response y using the same strategy in our mathematical reasoning tasks. We ensure the evaluation in the fair comparison with the CoT and LLM-based tree-search baselines: CoT-greedy, BFS-V, MCTS- MCTS- CoT-SC-MAJ, CoT-SC-ORM, MCTS-ORM, whose implementations are consistent in the paper.
For simplicity, we skip the average token number metric to highlight Acc in ProofWriter and Win rate in Chess Endgame. While their results remain based on @ath@ to promise the computation efficiency, and Equal-Toker to encourage the comparison in the similar scale of computation consumption cross baselines. the table, we found that CoT variants almost fail in ProofWriter due to their performances close random guess (33.33%). MCTS variants obtain significantly better results yet basically under-perform ITS variants with substantial gap in ACC, probably due to the cold-start effect in MCTS learned with epoch. As for Chess Endgame, ITS variants almost solve the problems with Win rates 99.83 % in Path @ I and 98.57% in Equal-Token It proves ITS also competitive in long- horizon reasoning.
22


Reviews:
[{"review_id": "lvaVABVrKG", "reviewer": "Reviewer_MF7d", "summary": "The paper proposes \"Implicit Tree Search\" (ITS), a stochastic approach that reformulates Monte Carlo Tree Search (MCTS) as a policy optimization problem. Unlike traditional MCTS methods that rely on discrete visit counts for exploration, ITS uses a continuous policy with reversed KL-divergence constraints.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and suggestions.\n\n**Q1. More implementation details behind theory (\"they sometimes gloss...more detailed explanation\").**\n\n**R1**: Despite Theorems 4.2, 4.3 containing numerous variables, most are derived from the data rather than serving as hyperparameters. Thus, IT-PO holds implementation consistency with its theoretical foundation except for only two details:\n\n1.1 $\\lambda_N(s^{(w)}_t),\\lambda_N(s^{(l)}_t)$ indicate how many reasoning paths generated from the state $s_t$, which consists of a prompt $x$ and its responses $y^{(w)}$,$y^{(l)}$ with their contents in the previous $t-1$ steps. For each preference pair, we set $\\forall t\\in${$1,\\cdots,T_w$}, $\\lambda_N(s^{(w)}_t)=K_w$ and $\\forall t\\in${$1,\\cdots,T_l$}, $\\lambda_N(s^{(l)}_t)=K_l$, where $K_w$, $K_l$ denote how many search start from the $t$-th leaf nodes $s^{(w)}_t, s^{(l)}_t$, respectively. Note that $T_w, T_l$ change with respect to the preference pair. So IT-PO adaptively configure $K_w=\\frac{K}{T_w}$, $K_l=\\frac{K}{T_l}$ to balance the optimization with different response lengths in $y^{(w)}$,$y^{(l)}$ for each pair. We set $K=8$, inspired from the number of sampled responses for each prompt in many RLHF implementations.\n\n1.2 In gradient analysis in Eq.19, the gradient of $\\varphi$ consists of terms in the form $\\frac{\\pi{\\theta}(a_t|s_t)}{\\overline{\\pi}{\\varphi}(a_t|s_t)}$ $\\nabla \\log [{\\overline{\\pi}}(a_t|s_t)]$. Due to $\\frac{\\pi{\\theta}(a_t|s_t)}{\\pi{\\varphi}(a_t|s_t)}\\in(0,+\\infty)$, updating the models with $\\frac{\\pi{\\theta}(a_t|s_t)}{\\overline{\\pi}{\\varphi}(a_t|s_t)}$ $\\nabla \\log [{\\overline{\\pi}}(a_t|s_t)]$ may suffer from exploding/vanishing gradients. To this, we used their logarithmic scaling $\\frac{\\pi{\\theta}(a_t|s_t)}{\\overline{\\pi}{\\varphi}(a_t|s_t)}$$\\rightarrow$ $\\exp(\\log(\\pi{\\theta}(a_t|s_t))-\\log(\\overline{\\pi}{\\varphi}(a_t|s_t)))$ to ensure the less sensitive update ratio. We also took the logarithmic scaling for the gradients in the Step-Asynchronous case (Eq.17), which will be elaborated in our next version due to our rebuttal limit.\n\n**Q2. More experiments for other reasoning tasks (Weakness and Questions For Authors).**\n\n**R2**: We offer evaluation based on ProofWriter [1] for deductive logical reasoning, and Chess Endgame [2] for long-term decision making. For ProofWriter, we follow [3] to generate the test set, then the rest are merged to 41,433 training instances. All training and test instances employed the prompt template in [3] that initiated the start of CoT, then we employ LLAMA2-7B as the base model and all fine-tuning methods only run for a single epoch. For Chess Endgame, we follow the experimental setup in (Feng, et al. 2023). With regards to each prompt-response pair $(x,y^{(w)})$ in ProofWriter and Chess Endgame, we find the dispreferred response $y^{(l)}$ using the same strategy in our mathematical reasoning tasks. We ensure the evaluation in the fair comparison with the CoT and LLM-based tree-search baselines : CoT-greedy, BFS-V, MCTS-$\\alpha$tr, MCTS-rollout, CoT-SC-MAJ, CoT-SC-ORM, BFS-V-ORM, MCTS-ORM, whose implementations are consistent in the paper.\n\n| Setting | Baselines |  | ProofWriter (Acc %) | Chess Endgame (Win rate %) |\n|--------|--------|--------|--------|--------|\n| Path@1 | CoT-greedy |  | 37.72 | 58.14 |\n|  |BFS-V|  | 48.94 | 67.75  |\n|  |MCTS-$\\alpha$  |  | 66.71 | 96.90 |\n|  |MCTS-rollout |  | 69.23 | 98.76 |\n|  |ITS-$\\alpha$ (ours) |  | 71.77 | 99.21 |\n|  |ITS-rollout (ours) |  | 75.31 | 99.83 |\n|--------|--------|--------|--------|--------|\n|Equal-Token  |CoT-SC-MAJ|  | 36.50 | 9.84 |\n|  |CoT-SC-MAJ|  | 36.58 | 73.80 |\n|  |BFS-V-ORM|  | 63.42 | 93.18 |\n|  |MCTS-ORM|  | 60.86 | 94.26 |\n|  |ITS-$\\alpha$ (ours)|  | 74.26 | 96.48 |\n|  |ITS-rollout (ours)|  | 78.15 | 98.57 |\n\nFor simplicity, we skip the average token number metric to highlight Acc in ProofWriter and Win rate in Chess Endgame. While their results remain based on Path@1 to promise the computation efficiency, and Equal-Token to encourage the comparison in the similar scale of computation consumption cross baselines. In the table, we found that CoT variants almost fail in ProofWriter due to their performances close to random guess (33.33%). MCTS variants obtain significantly better results yet basically under-perform ITS variants with substantial gap in ACC, probably due to the cold-start effect in MCTS learned with one epoch. As for Chess Endgame, ITS variants almost solve the problems with Win rates 99.83% in Path@1 and 98.57% in Equal-Token. It proves ITS also competitive in long-horizon reasoning. \n\nRef:\n\n1. Tafjord, O., et al. ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language (ACL-IJCNLP 2021).\n\n2. Abdulhai, M., et al. Lmrl gym: Benchmarks for multi-turn reinforcement learning with language models. arXiv preprint\n\n3. Pan L, et al. Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning[C] EMNLP-2023", "claims_and_evidence": "The math checks out for their theoretical connection between ITS and MCTS - they've got formal proofs showing how their stochastic policy approach converges to AlphaZero-style search. And when they show their method beating DPO variants on that Anthropic human preference dataset, the numbers in their tables and graphs seem convincing. They're also showing competitive results on those math reasoning benchmarks compared to MCTS approaches.", "methods_and_evaluation_criteria": "Their Implicit Tree Search approach tackles a real problem with traditional MCTS - those discrete visit counts can be limiting, especially early in the search process. Moving to a stochastic policy feels like a natural solution. And I like how they've connected this to preference optimization without needing explicit rewards - that's clever and practical given recent trends.\nThe datasets they picked seem reasonable. Anthropic HH is pretty standard for testing human preference stuff. And those math datasets (GSM8K and Game24) make sense since they need multi-step reasoning where tree search should help.", "theoretical_claims": "I took a look at several of the theoretical claims and proofs in the paper. The main ones I examined were Theorem 3.3 about the asymptotic equivalence between ITS and MCTS policies, Lemma 3.4 on the solution of ITS policy, and the proofs surrounding Lemma 4.1 and Theorem 4.2 that establish the connection between preference optimization and their implicit tree search approach.\nOverall the proofs seem technically correct for the most part, but they sometimes gloss over implementation details that would matter in practice. The theoretical foundation is sound enough to justify their approach, even if some of the finer points might benefit from more detailed explanation or justification.", "experimental_designs_or_analyses": "I examined several aspects of the experimental designs and analyses in the paper. The key experiments involve comparing IT-PO against baseline methods on preference alignment tasks (Anthropic HH dataset) and mathematical reasoning tasks (GSM8K and Game24).\nFor the preference alignment experiments (Section 5.1), I looked at their design for evaluating accuracy, diversity, and win rates. The way they measure these metrics is relatively standard in the field. They use accuracy on chosen vs. rejected completions, predictive entropy for diversity, and GPT-4 judgments for win rates - all common approaches.\nTheir win rate evaluation method involves a temperature scaling study (Figure 1a) which shows how performance varies with different sampling temperatures. This is a solid approach to examine robustness across different decoding strategies. The preference policy distillation experiments (Figure 1b) also make sense methodologically - they're measuring improvement over iterations of their approach.\nFor the mathematical reasoning experiments (Section 5.2), I examined their Path@1 and Equal-Token evaluation setups. The Path@1 metric (success rate for first-path generation) makes sense for evaluating reasoning quality. The Equal-Token comparison is a good attempt to control for computational budget differences between methods.", "relation_to_broader_scientific_literature": "The paper effectively creates a bridge between two previously distinct approaches: direct preference optimization methods that are computationally efficient but struggle with complex reasoning, and tree search methods that excel at reasoning but require explicit reward modeling and significant computational resources. By reformulating tree search as implicit policy optimization, it offers a novel way to get \"reasoning with free lunch\" - complex reasoning capabilities without the overhead of explicit tree search or reward modeling.", "essential_references_not_discussed": "I think most of the citations are discussed in the paper.", "other_strengths_and_weaknesses": "Weakness: While the mathematical reasoning tasks do demonstrate reasoning capabilities, testing on a wider range of reasoning domains (logical puzzles, programming tasks, etc.) would strengthen generalizability claims.", "other_comments_or_suggestions": "I don't have any major comment left.", "questions_for_authors": "Your evaluation focuses primarily on mathematical reasoning tasks and preference alignment. Have you tested IT-PO on other reasoning-heavy domains such as logical puzzles, programming tasks, or complex planning scenarios? Evidence of broader applicability would strengthen your claim that this approach provides general reasoning improvements", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IIXh5oogm0", "reviewer": "Reviewer_U4U8", "summary": "The paper introduces a novel approach to preference optimization for LLM by incorporating Implicit Tree Search, drawing inspiration from Monte Carlo Tree Search and AlphaZero-like algorithms. The key contribution is an alternative preference optimization framework that allows LMs to implicitly execute a tree search strategy without relying on explicit value modeling, which is typically required in traditional MCTS-based methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and concerns. We attempt to address the concerns by discussing the writing quality and the causes of marginal performance gain.\n\n**Q1: Writing quality.**\n\n**R1**: We response from three aspects.\n\n**First**, we appreciate the critique to phrases and grammar, and commit that our writing can be largely improved to encourage the readability. **In contrast to complicated terms, particularlly, our abstract and introduction, opt for more accessible and illustrative expressions to enhance comprehension**. Here are the argues to some cases found by Reviewer U4U8:\n\nCase 1.1 \"... remains enabling LLM-based reasoning as AlphaZero\": AlphaZero (Silver et, al. 2017b) is the famous Chess game Go system combining MCTS and value-based RL. Our IT-PO exactly uses the stochastic tree-search strategy derived from the consistent AlphaZero-like MCTS pipeline in (Feng, et al. 2023).\n\nCase 1.2 \"It's also concerning... as a universal approximator\": Policies separatly learned by state-specific objectives (Eq.8) can be uniformly approximated by the same LLM. \n\nSuch writing style aims to provide a straightfoward sight of our work before diving into our formulations. It may also cause the unexpected confusion, which is promised to fix. \n\n**Second**,  though the clarity can be improved, we **do not agree** with the judge \"unclear motivation and lack of sufficient background\" to our work. Our motivation is intuitivly explained in the first paragraph: **LLM trained for preference alignment hardly achieves reasoning without value modeling or RL, in particular, LLM-based reasoning with MCTS.** To this, through analyzing the connection between MCTS and its stochastic variant (i.e. implicit tree search in our paper) , we propose **IT-PO, the first alignment framework that simultaneously achieve LLM-based reasoning without RL and value modeling**. Then we provide the prelimary and warm-up sections (2.5 pages) to elaborate our technical motivation and background. The comments in Reviewers MF7d, REkf, zco2, and also your summary, captured the motivation of this paper. \n\nBeyond this, we found that **some unjustified comment misinterpret our claim**, e.g.\"\"inherits all advantages of DPO\" without introducing drawbacks is unprecise\" (we did not claim its escape from the DPO drawbacks.)\n\n**Third**, we did provide some intuitions to our theoretical parts. In Figure.2, we have illustrated the theoretical connection across MCTS, ITS derived from (Grill et, al. 2020b), and ITS learned by IT-PO. And each formula was always followed by its source and interpretation, e.g., 131-136 (right) for Theorem 3.3; 175-181 (left) for Lemma 3.4; 207-214(right), 234-237(left) for Lemma 4.1; 263-269 (left) for Theorem 4.2, etc. We commit that more illustrative examples can be introduced to improve the understanding of Theorem 4.3 (and will be refined), while the line of proofs in the paper still can be followed by the majority of reviewers.\n\nIn general, we acknowledge the manuscript's writing deficiencies and promise for revision, yet we believe the aforementioned evidences insufficient to rate it below the ICML bar.\n\n**Q2: The causes of marginal performance gain.**\n\n**R2**: Our following experiments further explain, even refine the marginal gain:\n\n**Insufficient iterations of policy distillation**. In Sec.4.3, we know IT-PO trains LLM $\\varphi$ along with cDPO with respect to fine-tuning LLM $\\theta$, which constructs the alternative optimization between $\\varphi$ and $\\theta$. While in our implementation, we only set the iter=5 in AnthropicHH, and iter=1 in mathematical reasoning tasks (consistent with MCTS-based baselines). With regards to the analysis to Eq.19, increasing the iter number supposes to benefit the IT-PO performance. To this, we reset the IT-PO's evaluation with iter=7 in AnthropicHH, and iter=2 in GSM8K (we also reset iter=2 for MCTS for a fair comparison in Path@1). The results below support our claim.\n\n| AnthropicHH | Metric | TDPO$_2$ | IT-PO (ours, iter=5) | IT-PO (ours, iter=7) |\n|--------|--------|--------|--------|--------|\n|  | Alignment (Acc) | 67.33 | 69.12 | 70.83 |\n|  |Diversity (Ent)| 4.915 | 5.315 | 5.421  |\n\n| GSM8K | Baselines |  | iter=1 | iter=2 |   \n|--------|--------|--------|--------|--------|\n|  | CoT-greedy |  | 41.4 | 41.4 |\n|  |BFS-V|  | 52.5 | 52.5  |\n|  |MCTS-$\\alpha$  |  | 51.9 | 51.8 (-0.1) |\n|  |MCTS-rollout |  | 47.8 | 48.4 (+0.6) |\n|  |ITS-$\\alpha$ (ours) |  | 53.2 | 54.3 (+1.1) |\n|  |ITS-rollout (ours) |  | 51.6 | 54.8 (+3.2) |\n\n**More appropriate experimental setup**. Based on the analysis in Sec.2, ITS could be promising in the cold-start search senarios, or more complex reasoning problems. This claim is supported by the results in ProofWriter (R2 in Reviewer MF7d, gain 6%$\\sim$17%) and MATH (R2 in Reviewer REkf).\n\n**Q3. Missing numbers in table 2**\n\n**R3**: In GSM8K, the numbers in Equal-Token are consistent with those in Path@1 using tree-search baselines (see (Feng, et al. 2023)).", "claims_and_evidence": "The claims presented in the submission are partially supported by empirical evidence, specifically in the experimental comparisons provided in Tables 1-3, which demonstrate performance improvements in preference alignment and mathematical reasoning tasks. However, several claims remain problematic due to unclear presentations. Additionally, the assertion that the proposed method \"inherits all advantages of DPO\" without introducing drawbacks is unprecise. It's also concerning to use the language model policy as a \"universal approximator\".", "methods_and_evaluation_criteria": "The proposed methods in the submission are conceptually relevant to the intended application—integrating implicit tree search (ITS) into language model preference optimization. The authors employ empirical comparisons using datasets (Anthropic HH, GSM8K, and Game24) suitable for evaluating preference alignment and reasoning capabilities. However, the performance improvements reported in these experiments are marginal in many cases, raising questions about the practical advantage and meaningfulness of the proposed methodological complexity.", "theoretical_claims": "The paper introduces a dense and highly formalized mathematical framework, but its presentation could be significantly improved. Currently, it lacks sufficient intuitive justification before diving into complex formulations, making it extremely difficult to follow.\n\nI think it's a pity that the theoretical contribution is buried in dense formalism, making it hard to assess whether ITS is a fundamentally new insight or just a reformulation of existing search techniques.", "experimental_designs_or_analyses": "While empirical results mostly demonstrate some performance gains over existing methods, such improvements are often marginal rather than substantial. By the way, why are some numbers in table 2 missing?", "relation_to_broader_scientific_literature": "The key contributions of this paper build on prior literature by integrating ideas from Direct Preference Optimization (DPO), Reinforcement Learning from Human Feedback (RLHF), and Monte Carlo Tree Search (MCTS), particularly AlphaZero-like variants, into a unified implicit policy optimization framework. Specifically, the authors leverage theoretical results from Grill et al. (2020) that interpret AlphaZero-like MCTS as regularized policy optimization and propose using language models as implicit policies to replace explicit tree search.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The manuscript currently lacks a clear motivation, intuition, and sufficient background prior to introducing complex mathematical content. Both the abstract and introduction do not effectively fulfill their intended roles of providing context and engaging readers.\n\nMoreover, the manuscript includes many informal and imprecise statements, negatively impacting clarity and professionalism. Some specific examples from the abstract and introduction are:\n\n- The phrase \"... remains enabling LLM-based reasoning as AlphaZero\"\n\n- The sentence \"While MCTS demands the value function to execute its procedure, contradicting the critical advantage of DPO that skips value learning to achieve faster and more stable preference optimization than RLHF,\" contains grammatical errors and requires restructuring for readability.\n\nAdditionally, the current title, \"Language Models as Implicit Tree Search,\" is confusing. Based on the content presented in the main text, a more accurate title would be \"Language Models as Implicit Tree Search Policies.\"\n\nAddressing these points will enhance readability, precision, and overall scholarly quality.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3hc4XnLj2J", "reviewer": "Reviewer_REkf", "summary": "This paper introduces a novel preference optimization framework called Implicit Tree Search Preference Optimization (IT-PO) that addresses the reasoning limitations of existing LM alignment methods like Direct Preference Optimization (DPO). The key innovation is incorporating a second language model policy that approximates AlphaZero-like tree search behavior without requiring explicit tree construction or value modeling. By leveraging the asymptotic equivalence between stochastic policy optimization and MCTS, the authors formulate a preference optimization approach that maintains DPO's advantages while enabling more effective exploration and reasoning. The authors develop both step-synchronous and step-asynchronous variants of IT-PO, along with self-improved policy distillation and decoding strategies. Empirical evaluations demonstrate that IT-PO outperforms both DPO variants in human preference alignment tasks and surpasses MCTS-based language models in mathematical reasoning and planning benchmarks like GSM8K and Game24, while maintaining computational efficiency.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and suggestions.\n\n**Q1. The limitation due to the demand of two language models.**\n\n**R1**: It is a good question since the requirement of LLM $\\theta$ and $\\varphi$ is inevitable in IT-PO. Despite so, the implementation can partially mitigate the limitation. First, despite the alternative training between $\\theta$ and $\\varphi$, we may only use one of them for inference, in particular, we may decode with either $\\theta$ or $\\varphi$ while the LLMs are derived from the IT-PO for token-level alignment. Second, since LLM $\\varphi$ is the key to achieve reasoning, we may resort to the small-size LLM to reduce the training burden. The experiment of MATH in R2 verified this claim.\n\n**Q2. Larger language models as the base of IT-PO**;\n\n**Q3. Evaluation on more diverse and complex reasoning scenarios.**\n\n**R2-R3**: We provide the experiment to simultaneously address the concerns 2 and 3. It is because larger LLMs demand a more difficult task setup for the evaluation, and sufficiently complex reasoning task also requires a base model strong enough to support IT-PO. Specifically, we consider the reasoning-based evaluation on MATH and construct the training set integrated with the training splits of GSM8K and MATH. Due to our computation resource limited in the rebuttal period, comphrensive results based on 70B-size LLM are hardly achieved. Instead, we resort to other larger base LLMs in the Qwen family, i.e., Qwen1.5-32B.  Besides, we introduced LLAMA3.1-8B as a small LLM, aiming to verify our claim in R1. Then our evaluated LLMs ($\\theta$, $\\varphi$) in IT-PO are defined Qwen1.5-32BX2, (Qwen1.5-32B,LLAMA3-8B), then employed the decoding strategies ITS-$\\alpha$ and ITS-rollout, respectively. For a comparison, we further train Qwen1.5-32B with MCTS to provide the baselines MCTS-$\\alpha$ and MCTS-rollout, where the search depth = 4 and search width = 3. In our implementation, all IT-PO models are trained with the hyper-parameters consistent with GSM8K in SFT, cDPO, and IT-PO, while the search depth and breadth for training are not limited in MATH (i.e., LLM $\\varphi$ trained as a stochastic policy without restriction). For decoding, all tree-search baselines use the search depth and width setup in GSM8K. The results are presented as\n\n |  | Baselines/Decoding | greedy CoT | -$\\alpha$ | -rollout |   \n|--------|--------|--------|--------|--------|\n|  | Qwen1.5-32B | 36.1 | - | - |\n|  |MCTS- (Qwen1.5-32B)  | - | 36.0 | 36.7 |\n|  |ITS- ($\\theta$=Qwen1.5-32B, $\\varphi$=Qwen1.5-32B) | - | 39.8 | 40.2 |\n|  |ITS- ($\\theta$=Qwen1.5-32B, $\\varphi$=LLAMA3-8B) | - | 37.9 | 38.2 |\n\nIn terms of the greedy CoT results in LLAMA3-8B (20.5), some observations can be found in the table. First, we note that the MCTS strategy derived from  is unreliable in MATH, probably due to the conflict between the problem complexity and limited search width and depth during training, while ITS does not suffer from this problem. Second, with a weaker model (LLAMA3-8B) for LLM $\\varphi$, IT-PO still enable the improvement of LLM-based reasoning.   \n\n**Q4. Confusion between T-DPO and TDPO.**\n\n**R4**: Will fix it in the next version.\n\n**Q5. Quantify the inference-time overhead of IT-PO compared to alternatives like standard DPO and MCTS-based approaches.**\n\n**R5**: The inference-time overhead of IT-PO can be significantly different w.r.t. decoding methods. For token-level alignment, IT-PO used a single model for decoding so that the overhead is consistent of standard DPOs. For reasoning tasks, it refers to ITS-$\\alpha$ and ITS-$rollout$ strategies. ITS-$\\alpha$ decodes the token like beam-search and for generated sentences, it evaluates their advantages via Eq.22. The process is similar with value inference, and ITS-$\\alpha$ holds the similar inference time with MCTS-$\\alpha$ (In GSM8K, each token is generated in $\\sim$16ms by MCTS-$\\alpha$ and in $\\sim$18ms by ITS-$\\alpha$ using a single A100 80G). ITS-$rollout$ can be treated as test-time-training version of ITS-$\\alpha$, which updates $\\varphi$ by Eq.21 to execute ITS-$\\alpha$ afterwards. It generates 8 (K=8 in Reviewer MF7d's R1) responses for each test prompt to achieve self-training. In our experiment, it results in the extra 30min~1h for each evaluation. \n\n**Q6. The sensitivity of the preference pairs to the hard negative response.**\n\n**R6**: We evaluate ITS-$\\alpha$ in GSM8K with hard negative ratio ranged from 100%, 75%, 50%, 25%, 0%, along with the results ranged from 53.2, 52.9, 53.4, 51.8, 50.1, accordingly. The performance drastically drops when the ratio less than 50%.", "claims_and_evidence": "The paper's claims are generally well-supported by theoretical analysis and empirical evidence, though with some limitations. The mathematical formulation establishing asymptotic equivalence between implicit tree search and MCTS (Theorem 3.3) provides a sound theoretical foundation for the approach.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate and well-aligned with the paper's objectives. The authors use established datasets (Anthropic HH for preference alignment, GSM8K and Game24 for reasoning tasks) that are standard in the field, enabling fair comparison with baseline methods.", "theoretical_claims": "I reviewed the theoretical claims and proofs presented in the paper, with particular focus on the foundational results in Sections 3 and 4.\nThe proof of Theorem 3.3, which establishes the asymptotic equivalence between implicit tree search policy and AlphaZero-like MCTS, appears to be mathematically sound. The authors clearly derive the upper bound on the approximation error between the empirical visit distribution and the stochastic policy solution. The theorem appropriately builds on prior work by Grill et al. (2020), and the adaptation to the language modeling context is logical.\n\nLemma 3.4, which provides the solution form for the implicit tree search policy, is correctly derived. The constraints and conditions for the parameter α(st) are well-specified, though the process of dichotomic search to find this parameter is somewhat glossed over in terms of practical implementation.", "experimental_designs_or_analyses": "I reviewed the experimental designs and analyses presented in the paper, focusing on the main empirical evaluations in Section 5.\nThe human preference alignment experiments (Section 5.1) use a standard methodology with the Anthropic HH dataset. The authors appropriately use Pythia 2.8B as the base model and employ consistent evaluation metrics (accuracy, diversity, win rate) across all methods. The win rate evaluation using GPT-4 follows established protocols in the field. The visualization of win rates across temperature scaling (Figure 1a) and across iteration rounds of policy distillation (Figure 1b) provides valuable insights into the model's behavior.\nThe mathematical reasoning experiments (Section 5.2) on GSM8K and Game24 datasets are well-designed. The authors properly implement both Path@1 and Equal-Token evaluation settings, allowing for fair comparison across computational budgets. Tables 2 and 3 effectively demonstrate performance across different search widths and node sizes, which helps validate the method's robustness.", "relation_to_broader_scientific_literature": "The paper's key contributions intersect several important research directions in language model alignment, reinforcement learning, and reasoning capabilities.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "**Strengths**\n1. The authors establish a solid theoretical connection between Monte Carlo Tree Search (MCTS) and policy optimization through stochastic search, building on previous work by Grill et al. (2020). This provides a principled basis for their implicit tree search approach.\n2. IT-PO elegantly combines the benefits of DPO (avoiding reward modeling) with the exploration capabilities of tree search algorithms, addressing a significant gap in current LM alignment methods.\n3. Using two separate language models - one for token selection (πθ) and another for implicit tree search exploration (πφ) - is an innovative solution to the reasoning limitations of traditional preference optimization.\n\n**Weaknesses**\n1. While avoiding reward modeling, IT-PO introduces additional complexity by requiring two language models instead of one, which increases computational and memory requirements compared to standard DPO.\n2. The experiments are conducted using relatively small models (Pythia 2.8B and Llama-7B). It remains unclear how IT-PO would scale to much larger language models, e.g. meta-llama/Llama-3.3-70B-Instruct.\n3. While the GSM8K and Game24 benchmarks are standard, they represent relatively constrained reasoning tasks. Evaluation on more diverse and complex reasoning scenarios would strengthen the claims, e.g. MATH and AIME.", "other_comments_or_suggestions": "- The abbreviation \"T-DPO\" is used in Figure 1 but \"TDPO\" in the text, which creates confusion.", "questions_for_authors": "1. Your method employs two language models (πθ and πφ) during inference, which potentially increases computational requirements compared to standard DPO. Could you provide quantitative metrics on the inference-time overhead of IT-PO compared to alternatives like standard DPO and MCTS-based approaches?\n2. For the mathematical reasoning tasks, you mention generating hard negative preference pairs using responses from other questions. How sensitive is your method to the quality of these synthetic preference pairs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gHjDAIj3a4", "reviewer": "Reviewer_zco2", "summary": "This submission proposes a novel preference optimization method for LLMs, grounded in the theoretical insight that LLMs can be viewed as implicit tree search, combining direct performance optimization with Monte Carlo Tree Search (MCTS).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and suggestions.\n\n**Q1. The concept of Implict Tree search (ITS) is not clearly stated in the main part, and authors should explain what the difference between explicit and implicit tree search and what the advantages of implicit tree search in the introduction section**\n\n**R1**: The concept ITS is derived from the theoretical result in (Grill et al. 2020), which verfiies that given each intermediate node in MCTS, if the intermediate node is treated as a state $s$ in RL, then the search process can be approximated by a state-specific stochastic policy $\\overline{\\pi}(\\cdot|s)$ (Theorem.3.3). With such regards, for each AlphaZero-like MCTS, it always holds a stochastic variant defined by $\\overline{\\pi}(\\cdot|s)$ across all possible intermediate nodes in the MCTS. However, $\\overline{\\pi}$ can not be universally optimized by gradient descent. Instead, given each state $s$, $\\overline{\\pi}(\\cdot|s)$ can only be obtaind by solving a state-specific problem via dichotomic search. To this end, $\\overline{\\pi}(\\cdot|s)$ can not be used as explicit search like MCTS and instead, only applicable for policy distillation to update the Q value function in AlphaZero-like MCTS (see Eq.7).\n\nThe difference between MCTS (i.e., explicit tree search) and ITS mainly refers to three parts. \n\nFirst, MCTS is defined and executed by UCB in Eq.7, while ITS is defined through the set of policy optimization objectives (Eq.8) across all possible intermediate nodes in MCTS.\n\nSecond, the execution of MCTS relies on the empirical visit distribution $\\frac{1 + n(s,a)}{|\\mathcal{A}{\\sf MCTS}| + \\sum_{a'\\in \\mathcal{A}_{\\sf MCTS}}n(\\boldsymbol{s},\\boldsymbol{a}')}$. The empirical visit distribution suffers from the cold-start search problems and its expressivness is always lower than the continuous distrbituion. **It implies that ITS is more powerful than MCTS**.\n\nThird, ITS can not be explicitly used to search like MCTS due to its complexity to obtain the universal form of $\\overline{\\pi}$. Instead, ITS was mostly used in policy distillation to enhance Q-learning. \n\nThe introduction would be updated to present more details of ITS. \n\n**Q2. The figure 2 in the appendix should be put in the main part, so that readers can have a clear high-level intuitive understanding at the begining; Line 137, a typo Convnetional**\n\n**R2**: Will rearrange the figures, and fix all typos in the next version.\n\n**Q3. How to implement an implicit tree search (ITS) process?** \n\n**R3**: In the original ITS defined in (Grill et al. 2020), it can not be implemented as the search strategy. However, in this paper, we establish a connection between ITS and DPO. So the universal ITS policy $\\overline{\\pi}$ can be approximated using a second LLM $\\varphi$ by solving either Step-Synchronous IT-PO (Eq.16) or Step-Asynchronous IT-PO (Eq.18), alongside the LLM $\\theta$ obtained through DPO-like algorithms. Once LLM $\\varphi$ is properly trained, the ITS process can be implemented either by directly using $\\varphi$ for next-token prediction or by employing our newly proposed decoding strategies: ITS-$\\alpha$ and ITS-rollout.", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, the proofs are correct", "experimental_designs_or_analyses": "Experimental Designs Or Analyses are solid and extensive", "relation_to_broader_scientific_literature": "This submission is quiet related to reinforcement learning and MCTS,  like AlphaGo.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Pros: This paper provides solid theoretical demonstration, connecting direct performance optimization and MCTS, showing a novel idea for  LLMs preferences alignment without additional reward or value model.\n\nCons: The concept of Implict Tree search is not clearly stated in the main part. The figure 2 in the appendix should be put in the main part, so that readers can have a clear high-level intuitive understanding at the begining. And authors should explain what the difference between explicit and implicit tree search and what the advantages of implicit tree search in the introduction seaction.", "other_comments_or_suggestions": "Line 137, a typo Convnetional", "questions_for_authors": "What the difference between explicit and implicit tree search and what the advantages of implicit tree search? How to implement an  implicit tree search  process?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides a theoretical connection between reward-guided text generation (e.g. under (tokenwise) alignment algorithms like DPO) and AlphaZero-like MCTS as a regularized policy optimization (Grill et al., 2020). Based on this insight, the authors proposed a method called Implicit Tree Preference Optimization (IT-PO), which uses an additional language model to approximate the AlphaZero policy. This additional policy network is trained via a tokenwise loss similar to DPO. Experiments show that IT-PO can achieve better alignment results than various baselines.

The majority of the reviewers agree that the proposed analysis and method are novel and interesting. I agree with this assessment.

Nevertheless, I also agree with the reviewers' assessments that the presentation of the paper is its weakest point. There are many grammatical errors and typos in the manuscript. The exposition of the main idea of the paper and the method are also quite confusing. I suggest the authors move Fig. 2 in the appendix to the main text and package the method into a dedicated algorithm environment.
Decision: Accept (poster)