Language Models can Self-Improve at State-Value Estimation for Better Search
Authors: Ethan Mendes
Alan Ritter
Venue: NeurIPS 2025 spotlight ()
Keywords: LLMs
agents
reasoning
self-improvement
multi-step reasoning
search
Primary area: applications
TL;DR: a self-supervised method that improves open-weight value models using state-transition dynamics, enabling reward-free, efficient search with performance comparable to search with costly large models and tree-based methods

Abstract: Collecting ground-truth rewards or human demonstrations for multi-step reasoning tasks is often prohibitively expensive, especially in interactive domains such as web tasks. We introduce Self-Taught Lookahead (STL), a reward-free framework that improves language model–based value functions by reasoning explicitly about state transitions. STL can be viewed as a chain-of-thought analogue of the value iteration algorithm: instead of regressing directly on numeric values, a value LLM is trained to simulate a step of lookahead in natural language—predicting the next action, resulting state, and rationale for its value. This process refines value estimates without any labeled data. The self-supervised procedure yields more accurate state-value predictions, which in turn enable lightweight search algorithms to expand fewer states while maintaining strong performance. Empirically, STL-trained value models built on moderately sized (8B-parameter) open-weight LLMs boost web agent success rates by over 39%, achieving performance comparable to proprietary models. STL also generalizes to multi-hop question answering and math puzzles. Overall, STL enables small open-source models to guide efficient search, reducing inference costs by integrating explicit reasoning with value learning.

Language Models can Self-Improve at State- Value Estimation for Better Search
Ethan Mendes, Alan Ritter
Georgia Institute of Technology
emendes3@gatech, edu, alan. alan. ritterttc.gateeneeeeeeeeeeeeeeee edu
Abstract
Collecting ground-truth rewards or human demonstrations for multi-step reasoning tasks is often prohibitively expensive, particularly in interactive domains such web tasks. We introduce Self-Taught Lookahead (STL), reward- framework that improves language model-based value functions by reasoning explicitly about state transitions. STL can be viewed as chain-of-thought analogue of the value iteration algorithm: instead of regressing directly numeric values, a value LLM is trained to simulate a step of lookahead in natural language language-prediceee predicting the next action, resulting state, and rationale for its value, thereby refining value estimates without any labeled data. This self-supervised procedure yields more accurate state- value predictions, which in turn enable lightweight search algorithms expand fewer states while maintaining strong performance. Empirically, STL-trained value models built on moderately sized (8B parameter) open-weight LLMs boost web agent success rates by over 39%, achieving comparable performance with proprietary models. STL also generalizes multi-hop QA and math puzzles. We find that STL enables small open-source models to guide efficient search, reducing inference costs by integrating explicit reasoning with value learning.
Introduction
While large language models (LLMs) demonstrate strong reasoning capabilities by generating extended token sequences before answering [56 22 40), guiding inference with explicit tree search has the potential to further improve performance on tasks with a structured state space [64 60). In this setting, policy L.M proposes candidate actions, and value L.M evaluates resulting states to steer the search toward promising trajectories. Figure [T summarizes the assumptions different M-drivvee search methods make about information available during training and inference.
52 assume access to ground-truth reward signals or human demonstrations and optimize the model with reinforcement learning (RL) or imitation learning (II.). In contrast, Reward-Guided Inference strategies [74] 49 forego explicit reward during training: they only consult a reward signal at inference time, using it to guide procedures such LLM-based Monte-Carlo Tree Search (MCTS), However, collecting ground-trun rewards or human demonstrations may not be possible in every environment, and can oftentimes be costly. For example, for web agent tasks, even small-scale data collection can cost thousands of dollars (63] Reward and Demo Free methods [65] 64 relax this assumption they can operate without access to reward. However, these methods often rely on prompting an off-the-shelf LLM to serve as both the policy and value models during the search process, which constrains performance compared to models specifically tuned for agentic tasks [55].
Reward and Demo Learning methods 63
70
27
In this paper, we introduce Self-Taught Lookahead (STL), a Reward and Demo Free. self- supervised framework for interactive, multi-step reasoning tasks. Building evidence that search quality is strongly influenced by the accuracy the state-value estimator [10 37,, STL improves an
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Reward and Demo Learning
Reward-Guide Inference
Reward and Demo Free
rewards and humans demonstrations accessible during leaminng (e.g. RL
rewards accassible during inference for refinement search MCTS & Reflextinn
only environment transitions accessible
1. transitions used during inference (e.g. ReACT ToT)
Inference
Environment Transitions
Environment
Transitions
Learning
Environment Transitions
Ground Truth Rewards
Inference
transitions (Via lookaheed values rationales)
also for Isamina
Inference Learning
Ground Rewards
Lookahoad Values and Rationales
Human
Lookehead used for the curment state
Demos
Inference
Environment Transitions
Environment Transitions
+
STL (Our Setting)
Figure I: The information accessible during learning and inference across common search settings, exemplified using web tasks. Our Self- Telght Lookahead method Reward and Demo Free, yet is able to self-improve by learning from state transitions in the form of lookahead values and rationales.
LLM-based value function for better search performance. Unlike neural models traditionally used for state-value estimation in the learning to search literature [50) an L.M can leverage both conventional numerical values and natural language reasoning to estimate state values. STL exploits this feature by having an LLM value model learn to better assign values to states based on their expected future utility by constructing and learning from rationales that explicitly capture state transition dynamics. For instance, without understanding these transitions, it might not be clear whether a CLOSE (X) button on a website interface exits the current view or the entire workflow in web tasks 23). Learning better state-value estimates from state transition dynamics is especially well-suited for self-improvement in agentic tasks, where the environment directly provides transition outcomes. As result, our approach requires neither ground truth rewards nor human demonstrations.
STL (Figure 2 begins by generating eeff-improvement data through single step of lookahead within a tree search. Analogous to the Bellman update, this lookahead refines the estimated value of a state by leveraging information about potential future states. However, unlike classical reinforcement learning (RL) methods, which rely on explicit environment rewards, STL uses a large language model (LLM) to estimate state values. Specifically, during STL, value LLM is fine-tuned to reason about the utility state by predicting the next best action, its resulting state, and a corresponding rationale for the value of that state. During training, the model is fine-tuned using rollouts of states and actions within the environment. At inference time, instead of taking a step of lookahead in the environment, the improved value model simulates step of lookahead to provide more accurate value judgments.
By representing the lookahead process in natural language rather than regressing solely on value estimates, STL takes advantage of LLMs' strong generalization to unseen tasks via learned textual reasoning 42 68). For instance, our results ($4) on web agent tasks from WebShop (63] demon- strate that tree search with an STL fine-tuned 11ama-3. 1-8b-insttruct value model improves performance by 39% or more compared to the base 1lama model. Furthermore, STL matches the performance of search with a base gpt-4o value model and even achieves comparable results to Reward-Guide results also hold for math puzzles and multi-hop question answering 64 62 Finally, by enabling the use of small open-source value model during inference, STL leads to significant cost reduction when agents are deployed. Through an efficiency analysis ($5). we find that STL costs 5x less than a similarly performing gpt-4o value model. As STL produces more accurate state-value estimates, the resulting value models can effectively guide search algorithms that expand fewer states, while maintaining strong performance.
Inference methods such as LATS 74 unseen tasks. We show that these
2 Background: Guiding Tree Search with Language Models
Within a state space S, the goal of the tree search is to reach a desired state 8. E from an initial state so S, where is determined based the natural language task x, with E X, the set of

---

Self-Taught Lookahead (Learning)
Task 3 am looking for queen sized bed that is black, and has price lower than $130.00*
Replace
"o with
in the next iteration
jetoneluratt
Rollost Formatted for Fine-Turing
Lookahead
Buy
Majeesoo)
Format Lookahead Results
Gurrert Sunt. Stonehurs Colloct Lodge
Finetune Value Model
Becaprend GH-
V #k+1
Outaut:
bast bctban bctron Wisaaed
Twin
"Baying +1.5
"eltecting... 3.8
Best Successor
Racoasncl
Vake of Succestce Stste, 0.8
Therefore, ahe dlocuutting vauu the
V outputs and value
Unseen Task : looking for pack manual toothbrushes that good for sensitive (eeth, and has price lower than $40,00 D0"
Inference
Value Judgement:
(soft brand toothbrushi
Nost Beett Action: we pack)
V
Successor State 3'
Simulated
pk11
Reasoning,
Succestor States 0.7 Therefore, after discounting the valuee the current state ? 0.7
Figure 2: Self-taught lookahead self-improves the value model by learning from state-transition dynamics. During the data generation phase (top left), tree search is used to discover diverse states. For every observed state encountered during the search, successor states are expanded using base policy Tee and the current value model VoL and textual training example is formed using verbal representations of the next best action and successor state, as well as Vo, 's outputted value reasoning (r) and numerical value (v) discounted by 7 (top middle). These examples are used fine-tune VoL+i which will be used in the next iteration of the algorithm (top right). Value models learned during STL can be used to evaluate unseen states encountered during search on unseen tasks by simulating step of lookahead, including the next best action and the best successor state 3' (bottom).
all possible tasks. A state 8; E S might be step in a reasoning chain an intermediate webpage web navigation task. While the algorithmic details vary based on the tree search method e.g.. breadth-firs first search (BFS) MCTS, to adapt these methods to utilize language models (LMs), simply need to define how new states (successors) are generated and evaluated.
Action generation. Given trajectory of i + states during the search process, candidate actions (5) the action space A sampled using an LLM-based policy πe:
a
Te Ir so...... s1), Vj E [I,...,BB
where B is the branching factor or the number of specified candidate actions. These sampled actions constitute the set Aag- We denote the transition function as T' x A S, so for an action a, 8(41 T(s,, a.).
State evaluation. A value 1s and a rationale for the value le le of a state 8; is generated using a LL.M-based value model Vg X x S" - R L, where S* is the set of all finite sequences over the state space S and L is the space of natural language sequences:
(Faglzs Usgla)
(0).....))
Note that because V& is an LLM, it usually prompted a chain-of -f-thuggtt [56 manner to first generate fa:jæ and then conditionally generate Vaslæ based the rationale. For notational simplicity, will denote these two generated entities Tagl Rat(Va(zI500 so, s:)) and Us Val(Va( so..... sz)). While previous work [74,
64 [6] do generate rationales during state evaluation, usually they are generated purely to leverage the performance improvements of LLMs when asked to rationalize and are subsequently discarded. As described in 3 inspired by self-taught reasoning [68), we explicitly use these rationales during self-imprrvemmnt by fine-tuning on them along with the value to learn how better estimate state values in given domain.
32

---

3 Better State- Value Estimation with Self-Taught Lookahead
In this section, present proposed self-taught lookahead method. $3.1 and $32 describe the STL improvement procedure, while |3.3exppaiin explains how a STL-improved value model operates during inference. See Figure and Algorithm in Appendix C for overview of the method.
3.1 Generating Rollouts
STL assumes a static policy model my and only trains the value model through one or iterations of self-improvement. We denote the value model initialized with base LLM Vo and the value model used in a subsequent iteration & to assign values and generate rationales V
An iteration & of STL starts with a dataset Prollout, C. X natural language tasks for the current iteration. For each I; Prollouty we roll out the search tree using To and Vo Using tree search enables us to collect a diverse set of states so that the value model trained on these states' values can better generalize unseen states and tasks. We demonstrate this generalization in $4 When visiting state on the trajectory {5p during tree search, we compute 8, lookahead value, Vay²
Vs f max aEA..
Val(V (Zi, So, so..... 83, [s,,, a)))
where y is the discount factor. Since tasks are episodie, we set 7 values capture a better estimate of the true value of 8; they account for sy's successor states. In 7
4
54 35
These lookahead
we describe how generating and learning from these y's is similar to fitted value iteration.
Action-outcome rationales. However, alone, these lookahead values fail to reflect why a given state is valuable they do not capture (1) which action yielded the best (highest value) successor state and (2) why the best successor state was assigned high value by Va.
To better capture the state transition dynamics, also generate action-outcom rationales when vis- iting a state 8j. These rationales are of the form "(action) pouttmmm_ttaee where action is selected by the max operator in Equation 3 outcome_ ststtttteeeee is the state observed after taking the action in the environment and value_ silee_ratinaaleee is the rationale for the evaluation these rationales will enable value model
avalue_rations
of this successor state generated by Vo.- Fine-tuning to predict the result of taking an action and incorporate this prediction (lookahead) into the current state's value estimate. Formally,
define these action-outcome rationales os,:
Oay + []]ls]+ 3+ |Rat(V you (Iz.Su..... su...., Sj. $j,$)+1))
(4)
where -|| denotes concatenation, 55+1 + T(sj, a5)) and
az E arg max Val (1 so...., .,,, (8),
(5)
oEA,,
The training data for iteration k is thus set of tuples: Dr (8k. Osg Moy ). Depending on the task, it might be necessary to automatically filter out tuples that have malformed rationales or account for the same state seen multiple times in different iterations (see Appendices and F
3.2 Fine-Tuning the Value Model
We start training the new value model Vou., from the initial or base LLM value model Von- We can then train using standard fine-tuning negative log- lig-likelihood loss for the generation of both the action-outcome rationale and the lookahead value (o,lly,) of the state. We train the value model to generate the rationale before estimating the value. Automatically constructed text or formatting, as seen in Figure?? is applied for easier learning.
3.3 Search after Self-Taught Lookahead
value model resulting from iteration of STL (Vo can directly replace a value model in any
search algorithm, such Greedy Search ($4.l and $4.2) and BFS ($4.3) As shown in Figure
Vouni simulates a step of lookahead for the state Sn i.e. for (Fa,,lz: [m) Voe (x) Su,
8n).
Ts, än+1 || F.aall
(6)
where dn+1 B1+1 is simulated lookahead step and Fontilx l/ is its value rationale.

---

Table 1: Score and success rate (SR) on WebShop. Results marked with are taken from previous work [74] 47]. Value functions marked with I are fine-tuned. We observe a near 40% improvement in success rate when using the STL value function compared the 11ama-3. 1e-----inssruc base value model in the greedy setting. We compute statistical significance of Reward and Demo Free meth- ods against the underlined results ("p < 0.05, "*p < 0.01, "*p < 0.001) using the paired bootstrap Best results in the Reward and Demo Free setting are bolded.
test 3
Setting
Method
Policy
Value
Mini Test Set (50)
Full Test Set (et( (500)
Score
SR 7
Score
SR
TL.
BERT BART
57.5
34.0
58.9
29.1
Reward and Demo Leurning
IL
BERT BART?
58.9
26.0
62.4
28.7
AgentQ
xLAM-v,, 1-m-16.76f
50.5
Reward-Guided Inference
LATS!
Rellexion
gpt-3.5-turee
3ot-3.3-turbbn
U. Turio
77.2
38.0
72.9
3.5 turbo
1aar 3.1 instruct
gpt-3. tutubo
ri-cistill-llana-Be
68.4
24.0
66.3
24.6
gpt-3. S-turbo
gpt-3.5-turbo
71.5
38,0
70,6
35.6
upt turbo
4p
72.9*
42,0kaa
71,5*aa
40.6
Greedy Boseline
spt-4o
11aru
71.6
28.0
67.2
25.8
Reward
gpt-4o
r1-distil1-11am--0
71.6
32.0"
66.5
25.6
upt-4o
upt-3.5-turbe
77,444
46,0aaa
72,4
38.8
Ap
gpt-1o
74,6*
46,0*em
71,4004
40,8
MCTS Roseline
gpt-3. S-turnn
Thama T-mb-nntrucct
71.9
34.19=
Gready w/
3.3 Turbo
Tlaro
T- Instructt
78.35es
46.04s3
12,8
36.6
STL (Ours)
spt 4o
11are 3.1 86 instruct
76,0ssa
40,00**
74,2**a
40.60s4
Human Expert
76.1
51.0
82.1
59.6
4 Experiments
We benchmark our proposed STL self-improvement approach on applied web agent tasks, multi-step question answering, and math puzzle tasks]]
4.1 Web Tasks
As mentioned in [T it is particularly challenging and expensive to gather ground truth web task complction data [70]. To benchmark our STL method on web tasks, we utilize WebShop [6], which consists of interactive web tasks involving searching for and purchasing an item that matches a short natural language specification. This benchmark is an ideal test bed demon- strate the ability of our approach, as, unlike other web task datasets [75] 31,, ground truth reward is provided for all tasks, allowing a direct comparison between STL and methods in the Reward and Demo Learning and Reward-Guided Inference settings which use this reward.
STL for web tasks. Following the empirical advantages on agent tasks identified by (66,, we generate training data with MCTS by performing step of lookahead at each step during rollout. Note that we use the LLM value model value outputs as a proxy reward to guide UCT (Upper Confidence bounds applied to Trees) 30 selection like [66]. instead of ground truth reward [74]
We perform
STL with a g.t-3.5 5-turbo 5 policy to be consistent with previous work 774 49 as well as a
gpt-4o 43) policy and fine-tune 11ama-3. 1-8b-instrruc [13] value function. STL is performed by rolling out 50 tasks from the WebShop training set, resulting in 1161 training examples, which we find is sufficient for significant performance improvement. We find that training a separate value model at each depth allows us to train with smaller LLMs with fewer active parameters during rollouts (see Appendix D.3 for more details). Also, while we perform data generation during STL with MCTS, we evaluate the agent using the trained value models with greedy search, where the next action greedily chosen based on the values of the policy's proposed actions (see Algorithm 2 for more details). Finally, we find that a single iteration of STL is sufficient to see significant improvement over using a base L.L--iiitaliized value model, and that multiple iterations do not yield additional performance improvements due to difficulties in simulating more than one step ahead, given the complexity of the environment. This conclusion has been corroborated by other LLM agent
OOur code is available at httppp//gghhbb.cc////caaaaa/aaaa
5

---

works 200 6. However, in $4.3 we show that this multi-step simulation is possible for simpler tasks. See Appendix D for further details about data generation, training, and simulation.
Baselines. Within Reward and Demo Learning approaches, we include IL and RL methods orig- inally proposed in the WebShop work that train BERT [22 and BART [36] models on human demonstra- tions and ground truth reward [63]. We additionally compare to the current state-of-the-arr approach AgentQ [47, which finetunes a larger XLAM-v0. 1-r-46. 7b policy on rolled out MCTS search trees using direct preference optimization [48]. We also include Reward-Guider Inference methods such as Reflexion 49 and LATS 774, which work by prompting flosed-source L.LMs within a frame- work, e.g., MCTS, that is guided by ground truth reward. Finally, in the Reward and Demo Free set- ting, we include greedy search and MCT3Q baselines with a ReACT 655 prompted base LLM (L1ama-3.1-8b-instee 1-bb-insttt 1o0t-3.--turbo got- r1-distill-llams 8b [22 All value mod- els are prompted with few-shot examples and are asked to provide reasoning before numerical value. Following LATS for a fair comparison, we use branching factor of 5 for all methods and 30 iterations for MCTS-based approaches. This makes LATS and MCTS baselines strictly more computationally expensive than greedy methods. We use the pass@33 g for methods that do not have access to reward at inference time. Finally, we include comparison to human expert performance measured in the original WebShop paper [63]
Results and discussion. The WebShop average reward (Score) and success rate (SR) of evaluated methods are presented in Table [ with additional baselines in Table 4 We present results on both the full WebShop test set and on the mini test set of 50 tasks used by [74,, as we find running LATS and other MCTS methods on the entire test set is computationally expensive. Both of these sets are distinct from those seen during STL. Within the Reward and Demo Free setting, we find that STL matches the performance of using a gpt-4o value model and leads to greater than 7% improvement in average reward and a 39% improvement in success rate relative to a base 1aama--.---b-instrree
value model, both of which are statistically significant improvements (p < 0.001) using the paired bootstrap test [3. Moreover, we find that STL even performs similarly to Reward-Guided Inference methods that have access to ground truth rewards. Lastly, we find no statistically significant difference between using a gpt-3.5-turbo action diversity in our setup (see Appendix D.2); thus, we evaluate search methods with a single policy (either gpt-3.5-tuu 5-trbo gpt-4o) in subsequent experiments.
gpt-4o policy due to high
Reasoning ablation. In the Reward and Demo Free set- ting. we also perform ablations on the set of information from the step of lookahead used fine-tune the value model during self-improvement. Specifically, we compare STL to variants that use only subsets of the information derived from lookahead. As mentioned in } this information includes (1) the lookahead value, (2) the textual representation of the bext-best action and its successor state, and (3) the value rationale for the successor state. The results of this ablation in Table 2 demonstrate that regressing solely on lookahead values and further incorporating state transitions from lookahcad docs improve performance relative to the base model. However, learning also from the value rationale of the successor state, as done in STL, yields additional performance gains over these other settings. These results substantiate the claims made in ş3Jabout the necessity of learning from action-uutcome rationales, a key difference between STL and both classical RL [19 and other LLM tree search works [16, 70 which fine-tune LLM value model on numerical values only. Note for fairness, we modify the loss-masking to improve the lookahead value-only baseline and include this higher result in the table. See Appendix F4 for more details about loss masking and this baseline.
Table 2: Ablation study on the im- pact of fine-tuning with different combinations of information from lookahead, namely lookahead val- ues (LV), textual representation of the next best action and successor state (TR), and the value rationale for the successor state (R). The underlined results are from the base model before any fine-tuning.
Fine- Fine-tuning Data Setup
Score ?
1lama-3. 1 1-8b-insttruct
70.0
+ LV
76.0
+ LV + TR + +LV + T (STL)
74.4
78.3
We use LLM value proxy reward to guide UCT, like in the data generation phase of STL

---

Table 3: Match rates HotpotQA. Value functions marked with are fine-tuned. Statistical signif- icance with the paired bootstrap test of Reward and Demo Free methods against the underlined results (*"p < 0.001) is provided. The best Reward and Demo Free results are bolded.
Setting
Method
Policy
Value
Rate 1
Test Set (50)
Test (500)
Reward and Demo Learning
R. Searchrr
11 1-bbiisttucct
46.0
44.8
Reward-Guided Inference
Reflesion
b-turbo
70.0
66
LATS
S-turbo
5-turbb
70.0
80t-3.5-turbe
11ama-3.
56.4
Greedy Baseline
8ot-3.5-turbh. 5-turbo
8pt-3. 5-turbo
Reward and Demo Free
3ot-3.5-turbo
got
68.9
57.6
Greedy STL (Ours)
g0t-3.5 tot-ttbt
11ana-3.1 3.10-33.18b-1mm 9.1-0b-instruct?
66.0
61.8
4.2 Multi-Hop Question Answering
We also investigate the efficacy of STL on applied reasoning for retrieval-basee based question-answerinng answering. We specifically utilize the HotpotQA [62) benchmark, consisting of multi-hop question-ans answering tasks that require retrieving and reasoning over multiple Wikipedia entries. We use the same setup as in $4.1 to generate data by rolling out with MCTS, but instead roll out 500 tasks from the training dataset since actions (search terms) proposed by the policy lack diversity compared to web tasks.
Baselines. In the Reward and Demo Learning setting, we evaluate on R1-Searcher [52] which performs RL on outcome-bases answer correctness rewards on the multi-step retrieval QA task. As in $4.1 in the Reward-Guided Inference setting, we include Reflexion and LATS baselines, which have access ground truth correctness during search. Among Reward and Demo Free methods, we compare STL to greedy search with closed-source models.
Results and discussion. Table presents the answer match rate of all evaluated methods. Follow- ing (15), we prompt gpt-4o to help evaluate answer correctness. The prompt used is Appendix [E.3 This fuzzy matching correctness is exposed as the reward for Reflexion and LATS, but not to the greedy methods in the Reward and Demo Free setting. We evaluate on a set 500 unseen questions and also smaller set of 50 examples due the high cost of LATS. STL on 1lama-3. 1-8b-instruct outperforms gpt-4o value model and the R1 R1-Searcher method while approaching the performance of -ewarddGuided Inference methods, which can verify predicted answer correctness during in- ference. Of the Reward and Demo Free approaches, STL the only method that statistically significant compared to the 1lama-3. -er---iiisteen baseline (p < 0.001).
4.3 Math Puzzles
Finally, we also study the performance of STL
Performance on Seen Tasks
on the Game-of-24 task [64], where the goal is
0.80
to construct mathematical expression with 4
Accurad
0.70
provided integers to obtain 24. The task was
0.50
0.60
spt-to value model
originally for Reward and Demo Free meth-
STL (lama-3.1- 1-88-iinsttrtt valu model
Oracle Value
ods, so it serves as good benchmark for STL.
3
Performance Unseen Tasks
0.60
STL for Game-of-24. For this task, we gener-
0.70
data using breadth-first search (BFS) rather
0.60
than MCTS to be consistent with the original Tree-of-Thought [64] approach. We use gpt-4o policy and a 11ama-3. 1-8b-instruct base value function in the first iteration. As described in }3 we replace this base value func- tion with trained model in each subsequent iteration. STL is run for four iterations of 25
0.40
Self-Taught Lookahead Iteration
Figure 3: BFS come-of-24 performance on tasks seen and unseen during STL.
7

---

Total Tokanss (log scalo)
Expanded States
18000
1.0
1320
0.0
0.6
0.4
0.2
0.0
1d8t Bob6))
UCTE
(b-instrncc)
Faya- 2. 4b (i-Inttret))
Methods
Methods
Figure 4: Compute and environmental efficiency during evaluation on WebShop with gpt-3.5-tur policy (left). Compute efficiency is measured in total (prompt and completion) tokens. Environmental efficiency is measured by the number of states expanded (webpages visited). The distribution of tokens (closed vs. open source models) used during search is also shown (right). Value models are specified in parentheses.
puzzles. For this task, we do not have explicit environment observations, but instead use the policy's arithmetic to combine two numbers as psendooobservation. See Appendix Fopendix[Foor further details.
Baselines. We compare the performance of value models learned via STL. with Reward and Demo Free BFS baselines that use the same gpt-4o policy. Specifically, we experiment with a gpt-4o value model and an algorithmic oracle evaluator [10]. This oracle runs recursive algorithm to verify whether the current state (set of numbers) can be combined reach 24. Search performance with this oracle is an upper bound on the performance improvement possible from improving the value function under static policy.
Results and discussion. Figure shows the performance of evaluated methods set of 50 tasks seen during STL and a set of 50 more challenging (determined by lower human solve percentages), unseen tasks. On both sets, STL matches or outperforms a gpt-4o value model. However, STL's performance on seen tasks monotonically increases for the first three iterations, while its performance on unseen tasks decreases before increasing. This phenomenon is due the limited number of tasks the value model sees during training during the first couple of iterations. Specifically, if value models not exposed enough actions and their lookahead values during training, they fail to generalize well to unseen tasks. Limiting the number of tasks per iteration also limits the quantity and diversity of actions and values seen. A full analysis of this result can be found in Appendix F.
Efficiency Analysis
In this section, compare the efficiency of STL with prior methods WebShop. We study efficiency tradeoff's from two perspectives (1) model costs and (2) environment usage, Additionally, in $5.3 we explore how performance changes when scaling the size of the value model trained during STL.
5.1 Compute and Cost Efficiency
Keeping compute requirements and costs low is critical, especially for agents automating routine, repetitive tasks. Since STL can be used to improve an open-source LLM like 1lama-3. 1i-----stttrrct, we can transfer computation from more expensive closed-sourc, models like gpt-4o to open-source alternatives while maintaining performance. Figure 4 (right) demon- strates this transfer, as STL uses more than 50% fewer tokens generated from closed-source than greedy search with gpt-3. 5-turbb or gpt-4o value model. We also compute the monetary costs of different methods. Unlike other methods, STL incurs costs for data generation and fine-tuning in addition to inference. but these one-time costs that do not scale with agent and are quite modest at $8.54 and $1.76, respectively. We plot inference costs against the average WebShop reward in Figure 5 (left), and find that STL is Pareto optimal, 23 cheaper than MCTS methods like LATS, and 5x cheaper than performing greedy search with a gpt-4o 40 value model. See Appendix for details about the cost calculation.
5.2 Environmental Usage
is often crucial for an agent taking actions in physical or digital environments be environmentally efficient conservative in the number of states it visits while performing task. In the case of digital

---

Oredy 130-l
Wea-hee
(lmma 24h4urres
50
06
(log
Expanded (log
Figure 5: Tradeoff between performance and efficiency on WebShop with a 3 policy. Pareto frontiers of existing methods and baselines are shown, illustrating the optimality of STL when considering the tradeoff between inference cost and average reward (left) and between environmental usage and average reward (right). Reward-Guider Inference methods are presented in gold and not included in the Pareto frontier since they belong a different information setting.
web agents, taking many steps per task through exhaustive tree search may put an unnecessary burden on web servers, especially as agents are deployed at scale. Additionally, allowing web agents to search widely when equipped with personal information the ability make purchases may lead to unintended privacy disclosures or financial loss, respectively. In some environments, taking many actions may also lead to unreasonable task completion times. Figure (left) and Figure (5 (right) present the environmental efficiency measured by the count of expanded states or visited sites in the WebShop environment. Considering WebShop score, STL is Pareto optimal and requires expanding half as many states as MCTS-base methods like LATS. Moreover, unlike LATS, STL does not require irreversible actions (actually clicking BUY Now on product page) required to obtain reward.
5.3 STL Scaling Trends
As 8B STL models can match the performance of a gpt-4o value model, possible to use even smaller models for STL while maintaining good performance? STL requires models to (1)
WebShop Success Rate
45
40
4o value model
provide generally consistent values out-of-the- box so that it is possible to compare successor states during data generation and (2) learn to generalize to unseen tasks and states, both of which may be challenging for smaller models. We explore this STL scaling trend on WebShop with < 8 billion parameter models in the 1lama 3 family
35
lama-3. 1-8b-instnuct value model
STL Ilama family
30
Owen
25
20
Model Size (Billions of Parameters)
13 and < 7 billion parameter models in the qwen-2. 5-instruct family [1]. The results presented in Figure [6] demonstrate that while performance does generally decrease with fewer parameters, the smaller 3B parameter models in both families do approach gpt-4o performance. This result suggests that using smaller models for STL is feasible, making large-scale agent deployment new domains more practical.
Figure
STL scaling trends on WebShop for 1lama-3 and qwen-2.5 families with gpt-3. turbo policy.
Discussion: When to use STL?
As discussed O and further detailed Appendix [D.2] achieving strong performance with STL requires high action diversity (a large number of possible actions at each step). When action diversity low, the effect of the value model on search performance diminished, and necessary to roll out more tasks to obtain enough data to fine-tune the value model. For example, Section 4 notes that due to its low action diversity, HotpotQA shows smaller relative gains from STL compared to WebShop and also requires rollouts of 500 tasks (10 times more than WebShop) to get large enough dataset for fine-tuning.
Additionally, STL requires later states to provide good value estimates that can be backed up and learned during training on lookahead results. Search performance will benefit most from STL on
As the 1lama-3 3.1 family lacks smaller models, IB and 3B models from the 11ama-3. 3. family.

---

tasks where state transitions are consistent throughout the environment, i.e.. the same or semantically similar actions yield similar outcomes. For instance, clicking the "Low to High" button on any search results page consistently orders items by price. This consistency enables the STI. value model to accurately simulate step of lookahead ($3.3), leading to better state-value estimation and improved downstream search performance. Tasks that have stochastic transitions or have inconsistent transitions when actions are semantically similar may not show large improvements with STL. Fortunately, most popular tasks where LLM agents have been deployed, such as web navigation, have deterministic and fairly consistent transitions.
7 Related Work
Classical RI.. STT. is loosely inspired by fitted value iteration (FVI) [19], which generalized value iteration [2] the tabular setting. an iteration FVI, target values are computed using the Bellman update and used to train a new value model from the previous model checkpoint using least squares regression. The iterated values in FVI are computed similarly to the lookahead values yıa in $ but with STL, no ground truth reward is assumed, the value model is non-Markovian, and actions are deterministic. Instead of learning directly from iterated values, with STL, they are concatenated with rationales, and together, these sequences are used to fine-tune the LLM value model from scratch each iteration rather than from the previous model checkpoint as FVI.
LLM self-improvement. variety of previous work has shown that LLMs can self-improve with iterative prompting techniques [26 58 39] and have applied these methods to various domains, from agents (29) to privacy protection [9] A separate line of work focuses on bootstrapping a small training dataset through a self-training process to improve either the reasoning policy model 221 [1 28 or the verification or reward model [24] using synthetically generated data. While most self-training approaches utilize outcome- based reward models, other work [0] derive process based rewards like STL to evaluate each step in the reasoning chain.
Training reasoning agents. The majority of prior work on training reasoning agents focuses on performing SFT on human-annotated trajectories 663 34 synthetically generated trajectories 7 17
72
38 45
[33] or a combination of both 669 71.. Other work has trained agents from
tree search-generated data [18 47 70 or with explicit reinforcement learning [46] 57 [4] but
these methods usually require ground truth reward. While prior work has explored self-improving reasoming agents, these approaches fail to generalize beyond the instructions encountered during self- improvement [45] or require fine-tuning frontier models like gpt-4o to achieve generalization [666]
Conclusion
We propose STL efficient method to improve the value model employed during search. This efficiency primarily stems from STL's design for information-scarce settings, where models learn from tate-transition dynamics. Additionally, because STL enables self- celf-improvement deployable with less exhaustive search, it yields significant reductions in both computational cost and environmental usage. Therefore, the STL framework could help enable the more realistic learning and deployment of agent systems.
small models
Acknowledgments
We would like to thank Microsoft's Azure Accelerate Foundation Models Research Program and NVIDIA's Academic Grant Program for providing computational resources to support this work. This research is supported in part by the NSF under grant number IIS IIS-2052498 and SMA-241 CMA-2418946, Any opinions, findings, and conclusions or recommendations expressed this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. We also appreciate Jungsoo Park, Yao Dou, Geyang Guo, and the anonymous Ne reviewers for their valuable feedback, which helped improve the paper.
10

---

References
[1] Renat Aksitov, Sobhan Miryoosefi, Zonglin Li, Daliang Li, Sheila Babayan, Kavya Kopparapu, Zachary Fisher, Ruiqi Guo, Sushant Prakash, Pranesh Srinivasan, et al. Rest meets react: Self-improvement for multi-step reasoning Ilm agent. arXiv preprint arXiv: 2023.
[2] Richard Bellman. Dynamic Programming. Princeton University Press, 1957.
[3] Taylor Berg- Kirkpatrick, David Burkett, and Dan Klein. An empirical investigation of statistical significance in nlp. In Proceedings of the 2012 joint conference on empirical methods in natural language processing and computational natural language leurning, pages 995-1005, 2012.
[4] Daniel S Bernstein and Shlomo Zilberstein. Reinforcement learning for weakly-coupled mdps and an application to planetary rover control. In European Conference on Planning, 2001.
[5] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 33:1877-1901, 2020.
[6] Hyungjoo Chae, Namyoung Kim, Kai Tzu-iunn Ong, Minju Gwak, Gwanwoo Song, Jihoon Kim, Sunghwan Kim, Dongha Lee, and Jinyoung Yeo. Web agents with world models: Learning and leveraging environment dynamics in web navigation. arXiv preprint a3X1v:2410.13232. 2024.
[7] Baian Chen, Chang Shu, Ehsan Shareghi, Nigel Collier, Karthik Narasimhan, and Shunyu Yao. Fireact: Toward language agent fine-tuning, arXiv preprint arXiv:2310.05915, 2023.
[8] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 2021.
[9] Yang Chen, Ethan Mendes, Sauvik Das, Wei Xu, and Alan Ritter. instructed to protect personal information? arXiv preprint arXiv:2310.02222 2023.
Can language models be
[10] Ziru Chen, Michael White, Raymond Mooney, Ali Payani, Yu Su, and Huan Sun. When is tree search useful for Ilm planning? it depends on the discriminator. arXiv preprint arXiv:2402. 10890, 2024.
[11] Maxime Chevalier-Be Boisserrt, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. Babyai: A platform to study the sample efficiency of grounded language learning. arXiv preprint arXiv: 1810.08810082 2018.
[12] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguisties: human language technologies, volume (long and short papers), pages 4171-4186, 2019.
[13] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.2/783 2024.
[14] Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An. Group-in-gren in-grupp policy optimization for Ilm agent training. arXiv preprint 2505. 2025.
[15] Peiyuan Feng, Yichen He, Guanhua Huang, Yuan Lin, Hanchong Zhang, Yuchen Zhang, and Hang Li. Agile: A novel reinforcement learning framework of Ilm agents. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[16) Xidong Feng, Ziyu Wan, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero- tree-search can guide large language model decoding and training. arXiv preprint D.XXi::2309.11799 2023.
[17] Hiroki Furuta, Kuang-Huei Lee, Ofir Nachum, Yutaka Matsuo, Aleksandra Faust, Shixi- ang Shane Gu, and Izzeddin Gur. Multimodal web navigation with instruction-finett finntuned foundation models. arXiv preprint arXiv:2305.11855 2023.

---

[18] Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah Goodman. Stream of search (sos): Learning to search in language. arXiv preprint wrXiv:2404.036833 2024.
[19] Geoffrey J Gordon. Approximate solutions to Markov decision processes. Carnegie Mellon University, 1999.
[20] Yu Gu, Boyuan Zheng, Boyu Gou, Kai Zhang, Cheng Chang, Sanjari Srivastava, Yanan Xie, Peng Qi, Huan Sun, and Yu Su. Is your Ilm secretly a world model of the internet? model-based planning for web agents. arXiv preprint arXiv:241..0653) 2024.
[21] Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjje Gu, et al. Reinforced self-training (rest) for language modeling. arXiv preprint arXiv:2308.08990 08998, 2023.
[22] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprini arXiv:2501.12945 2025.
[23] Aurora Harley. Cancel vs close: Design to distinguish the difference, September 2019.
[24] Arian Hosseini, Xingdi Yuan, Nikolay Malkin, Aaron Courville, Alessandro Sordoni, and Rishabh Agarwal. V-star: Training verifiers for self-taught reasoners. arXiv preprint
400.v:240.006457, 2024.
[25] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685 2021.
[26] Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models can self-improve. arXiv preprint arXiv:2210. 16600, 2022.
[27] Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Serean Arik, Dong Wang, Hamed Za- mani, and Jiawei Han. Search-rl: Training Ilms to reason and leverage search engines with reinforcement learning. arXiv preprint XXXv:25033005/6 2025.
[28] Jachun Jung. Peter West, Liwei Jiang, Faeze Brahman, Ximing Lu, Jillian Fisher, Taylor Sorensen, and Yejin Choi. Impossible distillation: from low-quality model to high-quality dataset model for summarization and paraphrasing. arXiv preprint orXiv:2305.16633 2023.
[29] Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks. Advances in Neural Information Processing Systems, 36, 2024.
[30] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282-293. Springer, 2006.
[31] Jing Yu Koh, Robert Lo, Lawrence Jang, Vikram Duvvur, Ming Chong Lim, Po- Yu Huang, Graham Neubig, Shuyan Zhou, Ruslan Salakhutdinov, and Daniel Fried. Visualwebarena: Evaluating multimodal agents realistic visual web tasks. arXiv preprint arXiv:2401.33644 13649, 2024.
[32] Jing Yu Koh, Stephen McAleer, Daniel Fried, and Ruslan Salakhutdinov. Tree search for language model agents. arXiv preprint 2001::4077.01776. 2024.
[33] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng. Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and lon Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium Operating Systems Principles, pages 61 626, 2023.
[34] Hanyu Lai, Xiao Liu, Iat Long long, Shuntian Yao, Yuxuan Chen, Pengbo Shen, Hao Yu, Hanchen Zhang, Xiaohan Zhang, Yuxiao Dong, et al. Autowebglm: Bootstrap and reinforce large language model-based web navigating agent. arXiv preprint XXXv:24444003445 2024.
[35] Bethany R Leffler, Michael Littman, and Timothy Edmunds. Efficient reinforcement learning with relocatable action models. In AAAI, volume 7, pages 572-577, 2007.
12

---

[36] Mike Lewis. Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy. Ves Stoyanov, and Luke Zeutlemoye.. Bart: Denoising sauuencc-to-sequenee pre-training for natural language generation, translation, and comprehension. arXiv preprint arXiv:1910. 1 13461, 2019.
[37] Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz. Don't throw away your value model! generating more preferable text with malue-guided monte-carlo tree search decoding. First Conference on Language Modeling, 2024.
[38] Zuxin Liu, Thai Hoang, Jianguo Zhang, Ming Zhu, Tian Lan, Shirley Kokane, Juntao Tan, Weiran Yao, Zhiwei Liu, Yihao Feng, et al. Apigen: Automated pipeline for generating verifiable and diverse function-calling datasets. arXiv preprint arXiv:2406. 105244066.18888 2024.
[39] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao. Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024.
[40] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv preprint arXiv:2501.19393 2025.
[41] Shikhar Murty, Dzmitry Bahdanau, and Christopher D Manning. Nnetscape navigator: Complex demonstrations for web agents without a demonstrator. arXiv preprint arXiv:2410.02907 2024.
[42] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint 12.0002/2..0011 14, 2021.
[43] OpenAL. Hello GPT-4o.
http://ai...ommmmdee/eee/eeeeeee gpttooppp/-o/// 2024.
[44] Tianyue Ou, Frank F Xu, Aman Madaan, Jiarui Liu, Robert Lo, Abishek Sridhar, Sudipta Sengupta, Dan Roth, Graham Neubig, and Shuyan Zhou. Synatra: Turning indirect knowledge into direct demonstrations for digital agents scale. arXiv preprint arXiv:2409. 2024.
[45] Ajay Patel, Markus Hofmarcher, Claudiu Ceoveanu-Condrei, Manius-Constantin Dinu, Chris Callison-Bure Burch, and Sepp Hochreiter. Large language models can self-improve at web agent tasks. arXiv preprint arXiv:2405.. 20309, 2024.
[46] Feng Peiyuan, Yichen He, Guanhua Huang, Yuan Lin, Hanchong Zhang, Yuchen Zhang, and Hang Li. Agile: A novel reinforcement learning framework of Ilm agents. Advances in Neural Information Processing Systems, 37:5244-5288 2024.
[47] Pranav Putta, Edmund Mills, Naman Garg, Sumeet Motwani, Chelsea Finn, Divyansh Garg, and Rafael Rafailov, Agent q: Advanced reasoning and learning for autonomous ai agents. arXiv preprint arXiv:2408. 07199, 2024.
[48] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36:53728-53377 2023.
[49] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
[50] David Silver, Thomas Hubert. Julian Schritwieserr, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm, arXiv preprint 17110117/2.018155 2017.
[51] Avi Singh, John D Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Peter J Liu, James Harrison, Jaehoon Lee, Kelvin Xu, Aaron Parisi, et al. Beyond human data: Scaling self-training for problem-solving with language models. arXiv preprint arXiv:2312.06585 2023.
13

---

[52] Huatong Song, Jinhao Jiang, Yingqian Min, Jie Chen, Zhipeng Chen, Wayne Xin Zhao, Lei Fang. and Ji-Rong Wen. RI-searcher: Incentivizing the search capability in llms via reinforcement learning. arXiv preprint urXiv:2503.05592 2025.
[53] Hongjin Su, Ruoxi Sun, Jinsung Yoon, Pengcheng Yin, Tao Yu, and Sercan Ô Ank. Learn-by- interact: A data-centric framework for self-adaptive agents in realistic environments. arXiv preprint arXiv:2501. 10893, 2025.
[54] Martijn Van Otterlo. A survey of reinforcement learning in relational domains. 2005.
[55] Jason Wei, Zhiqing Sun, Spencer Papay, Scott McKinney, Jeffrey Han, Isa Fulford, Hyung Won Chung, Alex Tachard Passos, William Fedus, and Amelia Glaese. Browsecomp: A simple yet challenging benchmark for browsing agents. arXiv preprint arXiv:2504. /2516, 2025.
[56] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thouglee prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24831 2022.
[57] Zhepei Wei, Wenlin Yao, Yao Liu, Weizhi Zhang, Qin Lu, Liang Qiu, Changlong Yu, Puyang Xu, Chao Zhang, Bing Yin, et al. Webagent-rl: Training web agents via end-to-end multi-turn reinforcement learning. arXiv preprint arXiv:2505. 16421, 2025.
[58] Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao. Large language models are better reasoners with self-verification. arXiv preprint arXiv:2212.09956 2022.
(59] Tianhao Wu, Weizhe Yuan, Olga Golovneva, Jing Xu, Yuandong Tian, Jiantao Jiao, Jason Weston, and Sainbayar Sukhbaatar. Meta-rewarding language models: Self-improving alignment with tintas-a-meta-judge. arXiv preprint arXiv:2407. 19594, 2024.
[60] Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, James Xu Zhao, Min- Yen Kan, Junxian He, and Michael Xie. Self-cvaluation guided beam search for reasoning. Advances in Neural Information Processing Systems, 36, 2024.
[61] An Yang. Baosong Yang. Beichen Zhang, Binyuan Hui. Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412. 15115, 2024.
[62] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Mamning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Ellen Riloff, David Chiang. Julia Hockenmaier, and Jun ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2389-2380, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.
[63] Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. Advances in Neural Information Processing Systems, 35:20744 20757, 2022.
[64] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 36, 2024.
[65] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
[66] Xiao Yu, Baolin Peng, Vineeth Vajipey, Hao Cheng, Michel Galley, Jianfeng Gao, and Zhou Yu. Exact: Teaching ai agents to explore with reflective-mets and exploratory learning. arXiv preprint arXiv:2410.0205. 02052,0.0 2024.
[67] Weizhe Yuan, Richard Yuanzhe Pang, Kyunghyun Cho, Sainbayar Sukhbaatar, Jing Xu, and Jason Weston. Self-rewarding language models. arXiv preprint arXiv:2401.10020, 2024.
14

---

[68] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476-15488, 2022.
[69] Aohan Zeng, Mingdao Liu, Rui Lu, Bowen Wang, Xiao Liu, Yuxiao Dong, and Jie Tang. Agenttuning: Enabling generalized agent abilities for Ilms. arXiv preprint arXiv:2310.12823; 2023.
[70] Dan Zhang, Sining Zhoubian, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets Llm self self-training via process reward guided tree search. arXiv preprint orXiv:2406.038/1 2024.
[71] Jianguo Zhang, Tian Lan, Rithesh Murthy, Zhiwei Liu, Weiran Yao, Juntao Tan, Thai Hoang. Liangwei Yang. Yihao Feng, Zuxin Liu, et al. Agentohana: Design unified data and training pipeline for effective agent learning. arXiv preprint arXiv:2402. 15506, 2024.
[72] Jianguo Zhang, Tian Lan, Ming Zhu, Zuxin Liu, Thai Hoang, Shirley Kokane, Weiran Yao, Juntao Tan, Akshara Prabhakar, Haolin Chen, et al. xlam: A family of large action models to 2024.
empower ai agent systems. arXiv preprint arXiv:2409.0322
[73] Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang. Expel: Lim agents experiential learners. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 19632-19642, 2024.
[74] Andy Zhou, Kai Yan, Michal Shlapentokh-Rothmann Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In Proceedings of the 41 International Conference on Machine Learning. ICMI,, 2024.
[75] Shuyan Zhou, Frank Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al. Webarena: A realistic web environment for building autonomous agents. arXiv preprint arXiv:2307. 13854, 2023.
15

---

Algorithm Self-Taught Lookahead
Require: Set of tasks Dolliutt Base LLM M, iterations n, num tasks per iteration
1: To k initialize_policyymdeell
2: Vou <
3: Diraing f
4: for k <- to
5: Drollout,, + D Drallout (k - 1) m
D. Select tasks for iteration
6: for Pollout. do
7:
T + pallout_tree((e 1)
> Generate rollout search tree for task
8:
f calculate + Loo.ulate_Lookaheadd_d. values()
9:
/riltered; Ofiltered < task task.specific
D Apply task-specific filtering
applicable
Drrsine < add_new DDrasnn (arraaiinnyyiaeereerrr (yriitered: Ofiitered))
12: end for
VáL fine_tune(Vooo Diraing)
D. Finetune from base model
14: end for
A Broader Impacts
Our STL method enables LLMs to self-improve search by capturing the mechanics of traditional RL algorithms in natural language. While we leverage this technique for better state-value estimation, can likely be applied other problems. Additionally, show $5 that STL requires significantly less compute overhead than similarly performing methods, thus reducing the energy consumption required for search during inference, helping to improve the sustainability of agent deployment.
As with all self self-improve improvemett work 45 [66, having models self- self-improve without human supervision may enable agents to learn how take actions towards task completion that human values or preferences. To prevent misuse, we only release code to reproduce experiments in this paper and not improve general-purposs agents for which these risks might be prevalent. While these harms are out of the scope of this work, we encourage future research in this area.
well-aligned with
Finally, note that it is possible environments with finite set of actions from each state. While we did not explore how well such a policy would work, improving value estimation improve the policy may be interesting direction for future work.
value model as sort of policy to directly select actions
B Limitations
During self-improvement, STL does require task specifications like "I am looking for queen- sized bed that is black " (see Figure 2 for web tasks. However, this assumption is well- founded as prior self-improvement work, such that on LLM alignment (67 59] also as- sumes tasks, or in their case, user prompts, are provided to initialize the self-improvement process. Additionally, as mentioned throughout the paper, this setting is much more reason- able than Reward and Demo Learning and Reward-Guided Inference settings, which require ground truth reward and/or human demonstrations along with task specifications.
Additionally, due to compute constraints, experiments utilize models up 8 billion parameters for STL, However, our results in demonsttae a scaling trend in performance with respect model size, indicating that using larger models may yield more performant agents. Given these positive results, we leave applying STL to larger models to teams with larger resource budgets.
requirs actions to be grounded in language to be able to leverage LLMs' strong priors. Therefore, STL may struggle in traditional RL tasks like gridworlds, which may have a large state and action space and transitions that are not grounded in language. However, prior work has contextualized gridworld environments by adding landmarks [I], so similar techniques may be used obtain the necessary consistent and grounded transitions for STL to be successful.
16

---

Algorithm 2 Greedy Search
Require: LLM policy To(+), LLM value model V+(+,, Initial state 5.
1: 8; < So
2: while s; is not terminal do
3: 0j < arg aEA, Val(VV su. ... .., ((),
Greedily pick best action
4: 8141 t as)
5: 7+-+1
6: end while
C
Algorithms
The STL algorithm is presented in full in Algorithm bask_specific_file see Appendix D.3 and Appendix F.4
For information about the
Additionally, the algorithm for greedy search as used in is presented in Algorithm
D Self-Taught Lookahead on WebShop
In this section, we outline information about WebShop 63 and the implementation details of running STL the benchmark.
D.1 WebShop Task
There two main types of actions in the WebShop task:
search[query]:
Search actions allow the user to search for particular item with a natural language query, e.g., search[easy to use medium color face kit less than 40 dollars]. This action can only be taken on the search page, which also the initial / home page of WebShop interface.
click[button]: Click actions discrete actions but can take many forms, which enumerate below:
clickkproduct:]: to select a relevant product from the search results e.g. [Bick[BB9B65H764]] where B09B6SH764 is product code.
click(attribute)): to toggle on an attribute or option on the product page an item, e.g. click[small]
[lick[Buy Now]: buy the selected item this terminal action that yields the ground truth reward. This action is not allowed to be taken in STL search but is allowed
other search, RL, and prompting methods 663 49 74..
Other navigation buttons: other navigation buttons include click[Back to Search], click[<Prev], click[Next>], [lick[Descrii inDescription]] click[Features] To sim- plify trajectories, we generally restrict the ability for models to take these actions in all settings following [63]
WebShop provides textual representation of webpages in simple mode. An example of this representation for search results is shown in Figure
D.2
Prompts
The prompt used to generate actions in WebShop presented in Figure g Notice that do not use
think actions part of the classical ReACT framework [65] like 633 or [44] because evaluating the value of these actions difficult as they have no observation. Instead, we prompt the policy model to provide rationale while generating possible actions. Also, note that prompt the policy multiple times, adding to the list of actions that are not allowed and removing from the list of actions that are allowed. This change to "selection" policy enables action diversity, which we find is otherwise low
17

---

WebShop Textual Representation
[Back Search] Page 1 (Total results: 50)
[Next >]
[B0972QIT8T]
Cosycost USB Microphone, Condenser Computer PC Gaming Microphone for PS4/5 Laptop Windows Mac OS Android Phone, Noise Cancelling Instant Mute, Studio Mic for Voice, Music Recording, Podcasting, Streaming
$32.99
[B09N3M6H2Z]
Wired Stereo Headset Noise Cancelling Microphone with in-line Controls/Volume Controller, All-Day Comfort Design, Works for Playstation, Nintendo Switch, PC with USB Connection (HS-HPIOIUNCBK)
$199.99
[B072L2D6LY]
Andrea Communications NC-255VM USB On-Ear Stereo USB Computer Headset with Cancelinn Microphone, in-Line Volume/Mute Controls, and Plug
$34.59
[B071H84LTJ]
Andrea Communications NC-455VM USB Over-Ear Cireumaural Stereo USB Com- puter Headset with Noise-Canceling Microphone, in-Line Volume/Mute Controls, and Plug
$49.24
[B08GLJSWJI]]
Jiade USB Headset with Noise Canceling Microphone for CallCenter Skype Chat, Computer Phone Headset Voice Recognition Speech Dictation, PC Headphone with
Mic Mute Volume Control Binaural Golden
$9.99
Figure 7: Example of simple mode textual representation of the state with the WebShop benchmark.
even with prompting the policy at high temperature. This change also likely explains why there is statistically significant difference between using a 3pt-3.5-turde and gpt-4o policy in 1
Likewise, the prompt used to evaluate states is presented in Figure 9 Note that this evaluation prompt is only used to prompt base models; STL value models are only prompted with the current trajectory. We note that the Likert scale used was crucial to obtaining consistent value outputs on which we could perform STL. We also use special value estimation prompt whenever on a product listing page convert the
to select attributes (see Figure 10p in order to obtain consistent values. Specifically, 4-point scale into a 22 to scale and add the value to the value the prior state's (product selection action) value. We tried to use this in baselines, but found that it actually harmed the baseline scores. However, in exploratory experiments, it helped yield more consistent values, so we use this for STL.
For all value estimates (base model or fine-tuned), we prompt the value model 5 times and use the average score the state value estimate. During the data generation phase, since need a single rationale to fine-tune on which to construct the action-outcome rationale, we choose the rationale corresponding the median of the 5 scores. After the rebuttal period, we found instruction to further discount values in the prompts to the fine-tuned models. While we could not rerun all results due inference costs, reran the STL evaluation the mini test set and found results were maintained.
In total, the data generation phase WebShop yielded a total of 1162 examples, collected from rolling out search trees for 50 tasks. example of the rationale structure of the training data presented in Figure II]
18

---

WebShop Generation Prompt
You are web agent, select the best next action for the search fulfill the task. Example tasks are shown below. Provide a rationale for your selection BEFORE you provide the action.
NOTE: You can only select actions that are provided in the Possible Actions list. You
MAY NOT select actions in the Not Allowed list.
NOTE: You must output BOTH rationale and an action.
NOTE: Do not select any of the following actions: 'Back Search', 'Next >; << Prev', "on","Atturn 'Attributes', 'Description,, 'Features', 'Reviews', even if they are available on the page.
Example Tasks:
(few shot examples)
New Task: [task]
Actions Not Allowed: (not_ allowed actions)
Possible Next Actions (REMINDER: You can only select actions from this list.): (possible actions}
REMINDER: Do not select any of the following actions: 'Back to Search', 'Next >', << Prev', 'Attributes, 'Description', 'Features', 'Reviews', even if they are available on the page.
Figure 8: Generation prompt for WebShop policy.
D.3
Implementing STL
With web tasks, the position of an action in trajectory may influence its value. For instance, selecting certain item from search results early in the trajectory should have higher value than selecting / second time in the same trajectory. To account for this difference, we train value models at each position (depth) in the trajectory. Specifically, we limit trajectories to five steps and train four value models depths to 4, only allowing a terminating BUY action on the final step.
We also filter out malformed rationales from the training data. Specifically, remove rationales that do not provide the proper format, e.g., it does not exactly contain scaffolding like "Thus the correctness score is".
Additionally, we generate lookahead rollouts using iterations of MCTS, which, in practice, we find is sufficient for collecting diverse training data.
Finally, we compute loss over both input and output tokens to enable the value model to more quickly capture the dynamics of the environment from the trajectory. However, we mentioned in $4.1 this practice harms the performance in the setting where the model regresses only on the lookahead value. Therefore, we found that when we only compute loss on the output tokens as in the normal SFT setting, the WebShop score in this setting increases from 70.9 to 76.0. This score is actually higher than the setting where we predict the future next best state without a rationale, which indicates that rationales may be key when we try to learn from transition dynamics. We are not sure why this the case, and why there is not larger gap between STL and this lookahead value baseline, but we believe that it could be due to small differences the prompt due to different information settings and/or the prediction or future state potentially harming value estimation for clearly good or bad states.
D.4 Difficulty in Performing STL for Multiple Iterations.
Empirically, we find that STL after second iteration on WebShop has a lower performance (average reward of 68.6, and success rate of 26.0) than after a single iteration. From manual inspection of the lookahead and rationales generated, we notice that the second step simulated by the value model often does not match the true environment.
19

---

WebShop Value Estimation Prompt
Given item to purchase and trajectory that aims buy item that exactly matches the specification, analyze how well the last action and observation align with the task. Provide a reflection that concludes with. "Thus the correctness score is s", where is either I, 2, 4, 6, 8, or 10. Use the following scale for scoring:
1: The last action and observed state entirely irrelevant to the task captures a purchase of an item that is completely unrelated to the specifications.
2: The last action and observed state captures a step with low likelihood of leading to purchasing the correct item.
4: The last action and observed state captures a step with moderate likelihood of leading to purchasing the correct item.
6: The last action and observed state captures step with a high likelihood of leading to purchasing the correct item.
8: The last action and observed state captures step with very high likelihood of leading to purchasing the correct item.
10: The last action and observed state captures a step that will certainly lead to purchasing the correct item.
Keep reflections short (<100 words). Follow the format of the rationale from the below example task. NOTE: the observation from clicking on the item will be the item's 's product detail page. For instance, click(B07GGWRC) item with code B078GWRCIJ which will include the item's name (e.g. Bright Citrus Deodorant by Earth Mama), price ($10.99), and other relevant details as well as options.
will show the product detail page for the
NOTE: Assume none of the attributes on the product page are selected only provide the reflection for the last action.
Example Tasks: (few shot examples]
New Task:
Respond with the reflection for the last observation of the new task ONLY. As reminder the action and observation as follows: Ilast_action, Your response should start with "Reflection:" and end with "Thus the correctness score is
Figure 9: Value Estimation prompt for WebShop. This prompt was only used to prompt base models.
Table 4: Additional baselines on WebShop. See Table for the full results.
Setting
Method
Policy
Mini Test Set (50)
Score
upt-3.5 Luturb
tuutrb
68.9
36.0
ReACT (No Search)
Reward and Demo Free
70.0
36.0
Gready Baseline
gpt-3.
qwan3-ab
68.6
34.0
D.5 Additional Results on WebShop
We have included performance on other baselines in Table 4 including ReACT
65 baselines with
OpenAl models and an additional greedy search baseline with qwen3-8b reasoning value model. Results with error bars also provided in Table 5
20

---

WebShop Attribute Prompt
Given item to purchase and trajectory that aims buy item that exactly matches the specification, analyze how well the last action and observation align with the task. All the last actions you see will be selecting an attribute on the product page of a candidate item. Provide reflection that concludes with "Thus the correctness score s", where is either 1, 2, or Use the following scale for scoring:
1: The attribute selected is opposite to the specified attribute in the task.
2: The attribute selected is irrelevant to the specified attribute the task.
3: The attribute selected is attribute mentioned in the instruction, but not all attributes mentioned are currently selected.
4: The attribute selected is attribute mentioned in the instruction, and all attributes mentioned are currently selected.
Keep reflections short (< 100 words). Follow the format of the rationale from the example task below.
NOTE: When selecting attributes like click(x-large), click[red], etc., the observa- tions will be "You have clicked x-large" "You have clicked red" respectively. IMPORTANT: Assume options for size, weight, color, etc. on product pages are not selected unless explicitly mentioned in the trajectory (e.g., click[large), click[red], etc.). Selecting these attributes may be crucial to match the task requirements. Only provide the reflection for the last action.
Example Tasks:
[few shot examples}
New Task:
(input)
Respond with the reflection for the last observation of the new task ONLY. As reminder, the last action and observation is as follows: (last_action)
Your response should start with "Reflection:" and end with "Thus the correctness score is..."
Figure 10: Value estimation attribute prompt for WebShop. This prompt was only used to prompt base models during rollouts.
D.6 Reflexion Performance on WebShop
Tracing bugs in Reflexion implementation We originally ran Reflexion baselines on WebShop using the official Reflexion GitHub repository with three iterations, changing only the model from text-davinci- ad0v (a deprecated text completion model used in the original paper) to gpt-3.5-turte During the author rebuttal period, found the following:
Other researchers had obtained similar Webshop performance to our initial Reflexion results (15%) using the unchanged official implementation with gpt-3.5-turbo (see GitHub issue #49).
Others also noted that changes to the prompts were needed adapt the framework to conversational models to see improved performance in the 30-40% range (see GitHub issue #48).
Another researcher also identified bug in the WebShop implementation that prevented the use of memory from prior iterations (see GitHub issue #36). In the discussion of this issue, the first author of the Reflexion paper acknowledged that this bug may have caused the lack
htttos///tttu..cc///nnnniii///is
21

---

WebShop Rationale Structure
Task and Current Trajectory:
Instruction: i'm looking for a pair of women's 's workout shorts with a drawstring
waist. need them be extra large and in light gray, and price lower than 60.00
dollars [Search]
Action: search[woment workout shorts drawstring waist extra large light gray 60 dollars]
Observation: removed for brevity
Current Action: (I
Current Observation; removed for brevity
STL Output:
will evaluate the best successor state from the current state:
Best Next Action: click[x02c-gray]
Observation of Best Successor State: You have clicked x02c-gray.
Reflection the Best Successor State: The last action selects the color 'x02c-gray' for the item B09T3PIMIR. Based on the observation, this product's color is indeed gray, which matches the specified criteria. Therefore, this product matches one of the attributes mentioned in the task. The last action and observation thus capture step that selects an attribute mentioned in the instruction, but not attributes mentioned (specifically the size attribute) currently selected. Thus, the correctness score is 6.00 10.00.
Figure 11: Example of rationale structure from the STL training data rolled out on the WebShop task.
Table 5: Score and success rate (SR) WebShop with bars. The full results are in Table
Full Test Set (500)
Method
Policy
Value
Score
SR 1
5-turbo
11ano-3. 1- 1-8o-instruct
67.7
26.4
got-3. S-turbo
11-dtatt:11-laaaa-h
66.3
24.6 3.78
got-3.5-ture
5-t-bo
3ot-3.b-turbe
spt-to
71.5
Greedy Baseline
got-4o
11ana-3, 1-80--nstruct
6.32
2
got-4o
ri-distill- (illaaa
6..5
25.6 3.83
gt-44o
S-t-ao--turio
7..4+2.40
38.8 4:29
go
gpt-4o
714
40.8 1.335
gpt-3. 5-turbo
11anc-3. 1-eee,,.1111---0 1-8o-Instructt
7238+2232
36.6 4.22
Gready w/ (Ours)
got-fo
1lare-3, 3.1-0-3.----ine 1--8o-instruct
2.33
40.6 4.30
Human Expert
of improvement of the Reflexion agent on WebShop that was reported in Appendix B. of the original Reflexion paper 49
After modifying the prompts and patching this memory bug, the ReAct success rate on the 50-task test set 36%, and the Reflexion success rate is 46% after three iterations, which is similar to the performance reported in other work [73 We hope that this debugging process can be of some use to the community.
Reflexion vs. LATS. In Table I Reflexion outperforms LATS, which is potentially unexpected LATS is more computationally expensive than Reflexion. However, due to differences in the mechanisms of these two methods, it is not necessarily the case that LATS performance is lower- bounded by Reflexion performance. For instance, Reflexion enables the LLM policy to make wholesale changes to any steps in its trajectory after reflecting on previous failures. On the other hand, while LATS provides its policy and value L.LMs with reflections on previous trajectories, still relies on the traditional (non-neural) mechanics of MCTSS For example, LLM reflection is not involved during node selection, and instead, the traditional Upper Confidence bounds applied Trees (UCT) heuristic is used.
22

---

E
Self-Taught Lookahead on HotpotQA
E.1
HotpotQA Task
The HotpotQA [62] is multi-hop question answering benchmark where correct answers require reasoning over multiple Wikipedia entries. There three possible actions at each step:
search[entry]:
Search provides the first five sentences of the corresponding Wikipedia entry it exists, or provides five alternative existing entries.
lookup[string]:
Lookup returns the next sentence in the entry containing the specified string.
finish[strine
Finish signifies the completion of the reasoning process, where the answer is specified with the provided string.
E.2
Prompts
The prompt used to generate actions for the HotpotQA task is presented Figure 14 Likewise, the prompt used evaluate states is presented in Figure 13 Many of the prompting details, such the use of a disallowed action list, are similar to the WebShop task. However, one difference that if five unique actions are found due search term being an entry, we add the top-5 similar terms returned by the retrieval model as possible actions.
In total, the data generation phase on HotpotQA yielded total of 2708 examples, collected from rolling out search trees for 500 tasks.
E.3 Evaluation
We use the same gpt-4o evaluation prompt [15] which is provided in Figure 13 Note that match computed when either there an exact match or match indicated by the gpt-4o evaluator in order to prevent any mistakes by the evaluator, such indicating a non-match even though the two answers were an exact string match.
Additionally, unlike WebShop, we limit trajectories to depth of four, and explicitly prompt models provide a final answer on the fourth step the trajectory.
E.4 Implementing STL
The implementation details of STL for HotpotQA are similar to WebShop in the training of multiple models at different depths, the filtering out of malformed rationales, and the of 5 iterations of MCTS during data generation. However, one difference is that we feed the possible next actions to the value model so that it can provide coherent lookahead simulations and evaluations.
Self-Taught Lookahead on Game-of-24
F1 Game-of-24 Task
As introduced by (64), the Game-of-24 is mathematical reasoning task that involves combining four
in order to obtain 24. An action in this task consists of simply applying mathematical operation to combine two numbers e.g. 2
numbers e.g. "2 3 4 5" together with mathematical operations i.e. +, - /,
5, the resulting state from the operation is the set of remaining numbers e.g "5 4 5""
F.2
Prompts
The prompt used to generate actions for the Game-of-24 task presented in Figure 15 Likewise, the prompt used to evaluate states is presented in Figure [6 Like WebShop, this evaluation prompt is only used to prompt base models; STL value models are only prompted with the current trajectory. However, unlike WebShop, values are not real numbers between and 10, but rather 0,001, 1, and
23

---

HotpotQA Generation Prompt
Solve a question answering task with interleaving Thought, Action, Observation Steps. Thought can reason about the current situation, and Action can be three types:
(1) Search[entityl, which searches the exact entity on Wikipedia and returns the first paragraph it exists. If not, will return some similar entities to search. which returns the next sentence containing keyword in the current passage.
(2)
(3) Finish(answerj, which returns the answer and finishes the task.
After each observation, provide the next Thought and next Action.
NOTE: You MAY NOT select actions in the Actions Not Allowed list. You have to change the wording of the query or lookup somehow.
Keep search queries and lookups short and concise since longer queries will not return any result. For instance, instead of searching Search[eastern sector of the Colorado orogeny], search Search[Coloras orogeny] and then Lookupfeastern sector].
NOTE:
Here are some examples: (few shot examples]
New Task: [task] Actions Not Allowed: [not_ allowed actions) Thought:
Figure 12: Generation prompt for the HotpotQA policy.
20, corresponding the labels of impossible, likely, and sure that the remaining numbers can be combined to reach 24. Note that these values were used by the original Tree-of-Thee ThTughht paper [64], but ad-hoc and used purely as labels. For all value estimates (base model or fine-tuned), we prompt the value model 3 times and use the median score as the state value estimate. During the data generation phase, since need single rationale to fine-tune which construct the action-outcome rationale, we choose the rationale corresponding to the median of the 3 scores.
F.3 Evaluation
For all tested BFS methods, the setup the Tree-of-Thoughts paper, i.e., we select of the best actions (set the branching factor to 5) at each of the 4 steps (two numbers are combined during each step).
F,4
Implementing STL
Since the state space is quite limited, we combine training examples from the previous k 1 iterations with current examples train the value model in the Ath iteration. If the same state encountered multiple times in different iterations, we defer to the value judgment from the latest iteration.
Unlike with WebShop and HotpotQA, do not train value models each depth, due to the small state space. Additionally, we also use a branching factor of 5 during data generation.
Table 6: Performance comparison across different numbers of tasks seen during self-improvement.
Tasks Seen During Improvement Accuracy (25 tasks / iter) Accuracy (50 tasks iter)
0
38,0
38.0
25
34.0
50
30.0
48.0

---

HotpotQA Value Estimation Prompt
Given question and trajectory answer the question, analyze how well the LAST ACTION in the trajectory contributes to finding the answer. Consider ONLY the last action.
The trajectories are labeled by pairs of thoughts that can reason about the current situation and actions that can be of three types:
(1) Search(entityl, which searches the exact entity on Wikipedia and returns the first paragraph it exists. If not, will return some similar entities to search. (2) Lookup/keyword]] which returns the next sentence containing keyword in the current passage.
(3) Finish[answent which returns the answer and finishes the task.
Provide reflection that concludes with "Thus the correctness score is s", where is either 1, 3, 5, 7, or 10. Use the following scale for scoring:
1: The action completely irrelevant to answering the question or there is no relevant search result ("Could not find" is in the observation).
3: The action's 's observation provides information only at the background level to answering the question.
5: The action's s observation provides information that makes a small step towards answering the question.
7: The action's 's observation provides information that makes a key step towards answering the question.
10: The action's 's observation provides the final piece of information needed to answer the question.
Reminder: you see "Could not find" in the observation, the correctness score 1.
Keep reflections short (< 100 words).
Follow the following examples: (few shot examples]
(input}
Figure 13: Value estimation prompt for HotpotQA. This prompt was only used to prompt base models.
E55 Investigating Improvement Dynamics
tasks in Game-of-22 due to lack sufficient tasks seen during seff-improvement. We confirmed this claim by rerunning the experiment by rolling out 50 instead of 25 tasks per iteration. The results summarized in Table O from which we see that performance actually improves in the first iteration the number of tasks seen during self-improvement is increased to 50.
In claimed that the initial decrease in performance
G
Costs
Here detail how computed costs in the efficiency analysis in S
25

---

HotpotQA Evaluation Prompt
Based on the provided question and reference answer, please determine if the response is correct or incorrect. Begin by articulating your rationale, and conclude with single word judgment: 'Yes' for correct or 'No' for incorrect. question: {question]
reference answer: (reference)
response: (response)
Figure 14: Evalaution prompt for the HotpotQA predicted answers.
Game-of Generation Prompt
Use numbers and basic arithmetic operations (+ * to obtain 24. each step, you are only allowed to choose two of the remaining numbers to obtain new number. Follow the example format exactly. (few shot examples]
[input]
Figure 15: Generation prompt for the Game-of-24 policy.
G.1
Data Generation Costs
To compute data generation costs during STL, OpenAl's for gpt-3. 1.tt-3..5tuue 5-turbo and Groq's pricing tables for closed source 1lama models. Note that we only use Groq for a pricing estimate, inference and training the pricing figures that we used for our experiments in Table We also note that experiments were initially run on gpt-3. 5-t.tr-o-001111 on OpenAI Azure, which multiple times as expensive as the newer gpt-3. 3. 5-turbo -0000-1222 0125 due to resource allocation on Azure, despite being the better model. We therefore choose report the data generation costs using the newer pricing point it is more comparable to the current prices of other models.
run in-house GPUs. As may change over time, we provide
G.2 Fine-tuning Costs
We account for the costs incurred from fine-tuning 1lama-3. 1-8b-instruct during STL. Fine- tuning with a single A40 GPU takes 4.5 hours for the WebShop task. While it is difficult to estimate costs on our own in-house GPUs, can estimate the cost by using VastAI's figure of $0.39 per A40 GPU hour when these experiments were run in April, 2025. Thus, the total training run cost roughly $1.76. We also note that the number of tasks seen at test time scales, the fine-tuning costs become increasingly negligible.
G.3 Inference Costs
To compute inference cost, the pricing figures in Table 7
Table 7: Inference pricing used for cost analysis.
Prompt Tokens ($ / 1000 tokens)
Completion Tokens ($ 1000 tokens)
gpt-3.5-turbo
0.0005
0.0015
got-4o
0,0025
0.01
1lama-3, 3. 1-81--8b--- 1b8-insrtuutt
0.0000S
0.00008
hgeenai.com/mpp/prriingg
eroq..com/prccng
26

---

Game-of-24 Value Estimation Prompt
Evaluate if the given numbers can reach 24 (sare//ikely/imposiilee) Follow the example format exactly. Only evaluate the last example. (few shot examples]
(input)
Figure 16: Value estimation prompt for Game-of -0-224 This prompt was only used to prompt base models.
H
Model Fine-tuning and Serving
Table 8: Hyperparameters during STL training.
warmup-steps
learning-rate
weight-decay
per-device-batch size
lora-r
lora-alpha
STL
10
2
0.01
16
Table 9: Effect of 7 on Performance.
0.75
0.80
0.85
0.90
0.95
0.99
1.0
WebShop Success Rate
32.0
24.0
24.0
24.0
28.0
42.0
46.0
Fine-tuning the value model for STL is carried out on single NVIDIA A40 GPU. We use LoRA finetuning [25] and use models provided by unsloth The hyperparameters used are in Table & We fine-tuned Game-of-22 24 value models for 10 epochs and WebShop value models for 20 epochs due to the differences in difficulty for models to learn the format of the action and state representations. We find that we require this large number of epochs to learn both the rationale structure and a good representation of transition dynamics. We note that is clear that overfitting is happening since unseen task performance does improve across tasks.
Additionally, serve base and fine-tuned models using vLLM 33 for efficient value estimation of new states during search. We use temperature = 1.0 and max tokens = 3192.
As mentioned in $3, we use 7 = 1.0 based on prior work. We also ran small hyperparameter tuning validation for y E (0.95, 1.0] on 50-example held-out validation set and found 7 1.0 had an average reward of 73.5 compared to 72.7 for 0.95.
Finally, perform small analysis the effect of the discount factor on search performance on the test. The results of the analysis with a 3.t-3.5- 5-33.55tur turbbo policy on WebShop are presented in The affect of y on the text set more stark.
Table 9
I Significance Testing
the paired bootstrap test to test the statistical significance of our experimental results. Following (3). we set 6 = 10 For WebShop, we run the significance test twice: once for score (average reward) and separate time for success rate.
In 44.1 and 4.2,
NeurIPS Paper Checklist
1. Claims
uniloth.ai
docs. waasvlllmmiiee/aateee
27

---

Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and the introduction, we claim that using STL to improve smaller LLM value model can enable search performance matching that of closed-source models, which is experimentally confirmed in the domains of web agent tasks ($4.1), multi- step question answering ($4.2), and math puzzles ($4.3). The abstract and introduction also make the claim that STL enables more efficient search, which is supported in
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations for our work are presented in Appendix B
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
28

---

Justification:
The paper does not include any theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, our paper fully discloses the information needed reproduce results. $ and Algorithm B outline the STL approach in detail, while Appendices D and F|provide the prompts and implementation details necessary for each domain evaluated. Furthermore, we provide cost calculation specifications in Appendix G and fine- the-ttning hyperparameters in Appendix H
We also provide our code the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
29

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We have provided a link to the code to reproduce our experiments in $4
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.ca
Sublicc/uuides//CdeSuublli
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines tht //nips.cc/publii... httpppuliiigggidee/eeeeeeeeeeeee www.oodeSsuimsssooolollooo.. ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, our paper fully discloses the experimental setting for each domain and evaluated method in $4 This section also specifies the type of search used, the number of tasks used for improvement, and the number iteration of self-improvemmnt used. We further provide prompts and other details for each domain in Appendices D E and [F] Finally, provide cost calculation specifications in Appendix and fine-tuning hyperparameters in Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We measure statistical significance throughout $ such as in Table and Table using the paired bootstrap test 3
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We present compute requirements used for experiments in Appendices G
Hnd
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Yes, our research does conform to the NeurlPS Code of Ethics. We note that we do not propose new dataset employ human participants.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
31

---

Both the potential positive and negative societal impacts are discussed in Appendix A
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification:
We outline safeguards for code release in Appendix A
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification; We have cited the creators of the original assets, including datasets and models that we use for evaluation in $4
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
32

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com commdatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsoureing research with human subjects
Guidelines:
33

---

for The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core method development of this work did involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.M policy what should or should not be deseribed.
34


Reviews:
[{"review_id": "OURupQAxzg", "reviewer": "Reviewer_TNro", "summary": "This paper offers an algorithm to improve LLM-based value function estimates for multi-step reasoning tasks via “self-taught lookahead”: exploring state transitions via tree search, estimating the values at the new states, and performing a Bellman backup to obtain a better estimate of the value of the current states. Iterative finetuning via this approach trains a better LLM value function, which then is paired with LLM-simulated lookahead for greedy value-based action selection at inference time. The paper presents empirical results across Webshop, HotPotQA, and Game-of-24 that indicate improve task performance due to the fine-tuned value function.", "questions": "Could you please provide some context to help me understand the experimental results on Webshop--the baseline numbers for Reflexion are far worse than reported in prior work. See my prior comments for discussion of both ReAct and Reflexion numbers--which should be a lower bound for search-based success rates. This is the place where clarification could most help change my evaluation score. \n\nI would appreciate a longer discussion of Figure 3—is there an experiment you can use with a stronger value function for lookahead states that prevents the earlier decline in performance on unseen tasks? \n\nPractitioners would highly benefit from guidelines for situations in which this approach is applicable vs where it is not--could you please include a discussion of the types of reasoning tasks where LLMs provide good value estimates at terminal states? (Which seems to be the key requirement). This feels like a critical discussion to include and would also help raise my score. \n\nI would suggest including greater detail for some implementation details--number of iterations of Reflexion, source of Human performance baseline, etc.", "limitations": "See note in weaknesses on the assumption that the value estimates from the LLM for terminal states is good—practitioners would highly benefit from guidelines for situations in which this approach is applicable vs where it is not.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**: \n\nThe problem setting is valuable—LLM agents may be deployed in real-world settings where neither rewards nor human demonstrations are available, and in these settings environment transition dynamics provide a self-supervised learning signal. \n\nComparisons to other search-based methods are thorough, and indicate performance on par with/exceeding more powerful baseline LLMs. \n\nComparisons of test-time token usage and cost are informative. \n\n**Weaknesses**:\nThe non-search baselines for Webshop are not strong—looking at Figure 5 in the ExpeL paper (https://arxiv.org/abs/2308.10144), ReAct with GPT3.5 turbo achieves 35% success rate on Webshop, and Reflexion with 1 and 3 rounds improves performance to 43 and 48% respectively—while this paper’s Reflexion baseline with the same LLM (please report number of Reflexion iterations) achieves 16.4% success rate. The performance of tree search-based methods should be an upper bound on the performance of Reflexion—so I would expect these success rates to all be higher than 48%. \n\nA critical component of the problem setup is the assumption that at later/terminal states, the value function estimates provided by the LLM is “good”—so that the backup operation improves value estimates at earlier states. It seems important to include a discussion of the types of tasks where LLMs are good estimators of value at terminal states—to motivate situations in which this approach is applicable. \n\nThe discussion of the presence/absence of human demonstrations in Figure 1 feels extraneous given that, outside the IL baseline, all other discussion of problem setting is whether or not environmental rewards are present at train/test time. \n\nMissing a discussion of train-time token usage when purely discussing test-time compute usage. \n\nHow did you obtain the Human Expert row in Table 1?", "was_revised": true, "final_justification": "Prior to rebuttal, my main concerns were with 1) the weak non-search baseline numbers, 2) the decline in task performance seen over iterations in Figure 3, and 3) some missing details on where the model is applicable, train-time costs, etc.\n\nThe rebuttal and discussion have addressed all three concerns, though I agree with reviewer rcW5's comment that the action spaces considered are hierarchically structured and do not offer the high dimensionality of \"flat\", large action spaces.", "rebuttal": "Thank you for the detailed feedback! We are glad that you found “the problem setting valuable” and our analysis “comprehensive”. We have addressed your comments below:\n\n> The non-search (Reflexion) baselines for Webshop are not strong\n\nThank you for pointing this out! We originally ran these experiments using the official Reflexion Github repository with three iterations, changing only the model from text-davinci-003 (a deprecated text completion model used in the original paper) to gpt-3.5-turbo. During the author rebuttal period, we found the following:\n* Other researchers had obtained similar Webshop performance to our reported numbers (~15%) using the unchanged official implementation with gpt-3.5-turbo (see Github issue #49). \n* Others also noted that changes to the prompts were needed to adapt the framework to conversational models to see improved performance in the 30-40% range (see Github issue #48).\n\n* Another researcher also identified a bug in the WebShop implementation that prevented the use of memory from prior iterations (see Github issue #36). In the discussion of this issue, the first author of the Reflexion paper acknowledged that this bug may have caused the lack of improvement of the Reflexion agent on WebShop that was reported in Appendix B.1 of the original Reflexion paper [1].\n\nAfter modifying the prompts and patching this memory bug, the ReAct success rate on the 50-task test set is *36%* and the Reflexion success rate is *46%* after three iterations, which is similar to the performance reported in the ExpeL paper. For Reflexion, we also recomputed the cost ($0.53) and number of expanded states (488), which are both similar to the current figures in the paper.\n\nWe will update these results in the camera-ready version of the paper and state the changes made to the original repository to achieve these results in the Appendix. We note that this change *does not affect the conclusions of the paper* since Reflexion and STL belong to different reward settings.\n\n\n> The performance of tree search-based methods should be an upper bound on the performance of Reflexion—so I would expect these success rates to all be higher than 48%.\n\nThe performance of LATS, a tree search-based method, is 38% as reported in the original LATS paper. After updating the Reflexion baseline, though their average reward scores at 77.2 and 75.9 are similar, LATS does seem to underperform Reflexion. We agree that LATS is more computationally expensive than Reflexion. However, due to differences in the mechanisms of these two methods, it is not necessarily the case that LATS performance is lower bounded by Reflexion performance. For instance, Reflexion enables the LLM policy to make wholesale changes to any steps in its trajectory after reflecting on previous failures. On the other hand, while LATS provides its policy and value LLMs with reflections on previous trajectories, it still relies on the traditional (non-neural) mechanics of MCTS. For example, LLM reflection *is not involved during node selection*, and instead, the traditional Upper Confidence bounds applied to Trees (UCT) heuristic is used. We will add this discussion to Section 4 of the revised version of the paper to help contextualize these results.\n\nWe would also like to mention that, as noted in the introduction and throughout the paper, LATS and Reflexion are Reward-Guided Inference methods that have access to ground truth reward during inference. However, STL is a Reward and Demo Free method, which *does not have access to ground truth reward* during search. Therefore, since LATS and Reflexion involve a different level of supervision compared to STL, *they are not true baselines*, but rather help contextualize results of the Reward and Demo Free setting with the existing literature.\n\n\n> I would appreciate a longer discussion of Figure 3—is there an experiment you can use with a stronger value function for lookahead states that prevents the earlier decline in performance on unseen tasks?\n\nAfter some investigation, we believe that this early decline in unseen task performance is due to the limited number of tasks the value model sees during training during the first couple of iterations. Specifically, if value models are not exposed to enough actions and their lookahead values during training, they fail to generalize well to unseen tasks. Limiting the number of tasks per iteration also limits the quantity and diversity of actions and values seen. When we double the number of tasks the value model sees during each iteration from 25 to 50, we can avoid a decline in performance (accuracy increases in the first iteration from 38.0% to 48.0%), as shown in the table below:\n\n| **Num Seen Tasks During Self-Improvement** | **Performance: Tasks Seen Per Iteration=25** | **Performance: Tasks Seen Per Iteration=50** |\n|----------------------------------------|----------------------------------------------|----------------------------------------------|\n| 0                                      | 38.0                                         | 38.0                                         |\n| 25                                     | 34.0                                         | -                                            |\n| 50                                     | 30.0                                         | **48.0**                                     |\n\nWe will add a discussion of this result in Section 4.3 of the camera-ready version.\n\n> Practitioners would highly benefit from guidelines for situations in which this approach is applicable vs where it is not\n\nAs discussed in Section 4 and Appendix D.2, achieving strong performance with STL requires high action diversity (a large number of possible actions at each step). When action diversity is low, the effect of the value model on search performance is diminished, and it is necessary to roll out more tasks to obtain enough data to fine-tune the value model. For example, Section 4.2 (lines 202 - 204) notes that due to its low action diversity, HotpotQA shows smaller relative gains from STL compared to WebShop and also requires rollouts of 500 tasks (10 times more than WebShop) to get a large enough dataset for fine-tuning.\n\nAdditionally, as you mentioned, STL requires later states to provide good value estimates that can be backed up and learned during training on lookahead results. Search performance will benefit most from STL on tasks where state transitions are *consistent throughout the environment*, i.e., the same or semantically similar actions yield similar outcomes. For instance, clicking the “Low to High” button on any search results page consistently orders items by price. This consistency enables the STL value model to accurately simulate a step of lookahead (Section 3.3), leading to better state-value estimation and improved downstream search performance. Tasks that have stochastic transitions or have inconsistent transitions when actions are semantically similar may not show large improvements with STL. Fortunately, most popular tasks where LLM agents have been deployed, such as web navigation, have deterministic and fairly consistent transitions.\n\nWe agree that this could be useful information for practitioners and will add this discussion to Section 3 and the Limitations section in the camera-ready version of the paper.\n\n\n> The discussion of the presence/absence of human demonstrations in Figure 1 feels extraneous\n\nThank you for the suggestion. We will remove the depiction of human demonstrations in Figure 1 and also rename the Reward and Demo Learning setting to Reward Learning in the camera-ready version.\n\n> Missing a discussion of train-time token usage when purely discussing test-time compute usage.\n\nTraining data generation costs are quite modest, e.g., generating WebShop data with STL using a gpt-3.5-turbo policy and a llama-3.1-8b-instruct base value model costs $8.54. We note that this is a *fixed, one-time cost* which does not scale with the number of inference tasks. We will add a small discussion of train-time costs in Section 5.1 of the camera-ready version.\n\n> How did you obtain the Human Expert row in Table 1?\n\nThese results were taken from the human expert evaluation performed in the original WebShop paper [2]. We will make this clear in the revised version.\n\n[1] Noah Shinn et al. 2023. “Reflexion: Language Agents with Verbal Reinforcement Learning.” Advances in Neural Information Processing Systems 36 (NeurIPS 2023), Main Conference Track\n\n[2] Shunyu Yao et al. 2023. “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”. Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Main Conference Track"}, {"review_id": "6eiCmSt0eg", "reviewer": "Reviewer_rcW5", "summary": "In this work, the authors propose Self-Taught Lookahead (STL), a self-supervised method that leverages state transition dynamics to improve a value model without using any labeled data. The proposed method is used to train the Llama-3.1-8b-instruct model as a value model, which can then be used with any search algorithm at inference to improve the performance of a Language Model-based Agent. Authors conduct extensive experimentation using different value models (trained and training-free) to demonstrate the efficacy of the learned value model. The experimental analysis is conducted on three tasks: WebShop, Multiple-Choice QA (HotPotQA), and Math Puzzles (Game of 24). Experiments show that a 8B parameter learned value model can match gpt-4o performance in all the tasks. The proposed training approach is comparatively lightweight, resulting in significant experimental efficiency. \n\nThe paper is well structured and clearly written. Numerous approaches have been proposed to utilize and train LLMs as value models. To the best of my knowledge, this work presents a novel approach that demonstrates efficiency and performance gains over contemporary methods. The experimental analysis is exceptionally well done, with strong and relevant baselines. The authors provide statistically significant results, which is rare in this research space and is appreciated.\n\nOverall, this is a well thought out and well executed piece of work, and thus **I vote for a clear accept**.", "questions": "## Questions\n\n- How does the branching factor apply to Greedy search? Is the next action sampled $n$ times, and the best value is selected?\n- Were there any experiments conducted with different search algorithms using the trained value model?\n- In Figure 4, what is the difference between open-source and closed-source tokens?\n- How does the size of the action space affect the performance of the proposed method? Any experiments on this topic would significantly strengthen this paper.\n- One notable result from Table 1 is that the STL with Greedy search performance is significantly lower compared to the AgentQ (trained policy model). It could be interesting to explore the interaction between these trained policy models (even though they are not reward-free) and the trained value model. Additionally, I am uncertain about the contribution of the GPT-4v value model used in the AgentQ method. Any discussion on this would be greatly appreciated.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\n- The problem addressed in this work is well-positioned within the current research landscape.\n- The proposed method is comparatively lightweight and does not require human-labeled data, but still outshines the strong baselines.\n- The experimental analysis demonstrates the statistically significant performance gains while being efficient in terms of cost and search steps.\n- The paper is well-written and easy to follow.\n\n## Weaknesses\n\n- One potential weakness of this work is the optional requirement of task filters while creating the training data. While it is optional, I assume that for complex agent environments, this may prove to be challenging to build.\n- For the Reward and Demo Free setting, authors used slightly outdated models (except R1-distilled) as value models. I assume this is done to maintain budget constraints and to provide a fair comparison with existing baselines. However, it will be interesting to see the comparison between newer models, such as the Claude-3.5/3.7/4-Sonnet or Gemini-2.5-Pro, and the trained value model.\nWhile the datasets selected for this work are suitable, it would have been beneficial to see a more open-ended setting with a relatively larger and more fluid action space, such as software engineering environments.\n\nOverall, the strengths far outweigh the weaknesses, and all the weaknesses can be addressed in future work.", "was_revised": true, "final_justification": "Authors have addressed all of my concerns during the rebuttal phase. My main concern was limited frontier model coverage; however, due to budget constraints, authors are not able to run experiments using these models. In my view, this is a minor issue that can be fixed in later iterations or with community involvement. The core idea explored in this work remains useful, and thus, I vote for accepting this paper with a rating of 5.", "rebuttal": "Thank you for your thorough review! We are glad that you find that our work is “well thought out and well executed” and “vote for a clear accept”. We have addressed your comments below:\n\n> One potential weakness of this work is the optional requirement of task filters while creating the training data. While it is optional, I assume that for complex agent environments, this may prove to be challenging to build.\n\nThe task filters we used in this paper were simple string checks to ensure that the training data did not contain malformed rationales, as we indicate in Appendix D.3. For instance, we verify that the training data rationales follow the correct format such as including the phrase “Thus, the correctness score is” before providing a score estimate so that the value can be easily and accurately parsed. We do not foresee many cases where an especially intricate task filter is needed, but in these cases, an LLM could be used to filter data as has been proposed by prior work, including [1].\n\n> For the Reward and Demo Free setting, authors used slightly outdated models (except R1-distilled) as value models… However, it will be interesting to see the comparison between newer models, such as the Claude-3.5/3.7/4-Sonnet or Gemini-2.5-Pro, and the trained value model.\n\nThank you for the suggestion. Unfortunately, we do not have the budget to run these newer proprietary models at the moment. However, we agree it would be interesting to see results with newer models, so we ran an experiment using a gpt-3.5-turbo policy with a qwen3-8b reasoning value model that was released in late April 2025. The results on the 50-example WebShop test set are provided in the table below:\n\n| **Model**                               | **Average Reward** | **Success Rate** | **Cost** |\n|-----------------------------------------|--------------------|------------------|----------|\n| qwen3-8b (thinking mode enabled)        | 68.6   | 34.0            | $3.80     |\n\nThese figures are quite similar to performance with a r1-distill-llama-8b value model. This result may indicate that while RL-trained reasoning models have steadily improved performance on math reasoning tasks over the last few months, they still struggle to perform calibrated state-value estimation out-of-the-box. We will add this result to the camera-ready version of the paper.\n\n> How does the branching factor apply to Greedy search? Is the next action sampled $n$ times, and the best value is selected?\n\nYes, during greedy search, the branching factor dictates how many actions are sampled from the policy. The value model then evaluates each action and selects the one with the highest value. We will add a couple of sentences in the revised version to make this clearer when it is discussed in Section 4.1, and also add a full algorithm for greedy inference in the Appendix.\n> Were there any experiments conducted with different search algorithms using the trained value model?\n\nWe found that MCTS with the base llama-3.1-8b-instruct value model was quite resource-intensive in terms of GPU hours required. Since STL with greedy search already outperformed MCTS with the base instruct model, we decided against running more expensive search algorithms like MCTS with the STL value model as well, but we believe this may be interesting to explore in future work.\n\n> In Figure 4, what is the difference between open-source and closed-source tokens?\n\nOpen-source tokens are prompt and completion tokens from open-source models like llama-3.1-8b-instruct, r1-distill-llama-8b, etc. Closed-source tokens are prompt and completion tokens used with closed-source proprietary models like gpt-3.5-turbo, gpt-4o, etc. We agree that this distinction could use some clarification; we will update the wording in the Figure 4 caption and in Section 5.1 to make this difference clear.\n\n> How does the size of the action space affect the performance of the proposed method? Any experiments on this topic would significantly strengthen this paper.\n\nAs discussed in Section 4 and Appendix D.2, achieving strong performance with STL requires high action diversity (a large number of possible actions at each step, or a large action space). When action diversity is low, the effect of the value model on search performance is diminished, and it is necessary to roll out more tasks to obtain enough data to fine-tune the value model. For example, Section 4.2 (lines 202 - 204) notes that due to its low action diversity, HotpotQA shows smaller relative gains from STL compared to WebShop and also requires rollouts of 500 tasks (10 times more than WebShop) to get a large enough dataset for fine-tuning. Unfortunately, it is difficult to design an experiment to measure the effect of the size of the action space on performance since different domains intrinsically have different action space sizes. One could artificially reduce the action space size by restricting the set of possible actions, but doing so would introduce confounders since search with an off-the-shelf value model would also likely decrease in performance with such a restriction. Therefore, we believe that comparing gains across domains, such as between WebShop and HotpotQA, is the best way to understand how the size of the action space affects STL performance. As mentioned in the response to TNro, we will add some discussion about this in Section 3 and the Appendix.\n\n> One notable result from Table 1 is that the STL with Greedy search performance is significantly lower compared to the AgentQ (trained policy model). It could be interesting to explore the interaction between these trained policy models (even though they are not reward-free) and the trained value model. Additionally, I am uncertain about the contribution of the GPT-4v value model used in the AgentQ method.\n\nThis is an interesting suggestion! To our knowledge, the 72B AgentQ model has not been released, so we unfortunately cannot run this experiment at this time. However, if this model is released by the authors, we will run this interaction experiment and add the results to the camera-ready version of the paper. The GPT-4v value model that AgentQ utilizes is used to provide feedback on trajectories to guide MCTS search. We will clarify this when we discuss AgentQ in Section 4.1 of the paper.\n\n\n[1] Pei Ke et al. 2024. “CritiqueLLM: Towards an Informative Critique Generation Model for Evaluation of Large Language Model Generation.” Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics."}, {"review_id": "fKNfp36nZs", "reviewer": "Reviewer_XxXy", "summary": "This paper introduces a method called “self-taught lookahead” (STL) which can be thought of as a form of value iteration applied to language models. In STL, the model is prompted to estimate state values along with rationales for multiple successor states, and then actions with the highest value are used to form a finetuning dataset consisting of (state, action, successor state, rationale, value). The model is finetuned, and at inference time greedy search is used to select subsequent actions. Experiments are conducted on three benchmarks (WebShop, HotpotQA, and Game of 24) using a finetuned llama-3.1-8b-instruct as the value model, demonstrating STL to work as well as or better than gpt-4o as the value model.", "questions": "### Clarifications\n\n* I didn’t quite understand how the generation of rationales and values works. In Section 3.1 and Algorithm 1, it sounds as though: (1) values are first generated on their own for several actions, leveraging ground-truth transitions, and then (2) rationales are generated given the actions and outcomes. But then there is only a single prompt (e.g. Figure 9\\) for value estimation, which first estimates the rationale, and then the value. So I’m confused about what the actual order of estimation is.  \n* I don’t think I fully understand what the algorithm looks like at inference time. It would be helpful to include an additional algorithm clarifying this. Is it that several actions are drawn from the base model, then these are each evaluated by the value model, and the best one is picked?  \n* It’s not clear what the dataset sizes were for finetuning. It would be helpful to include this detail in Appendix H, along with maybe some other statistics about the dataset generation (e.g. how many tasks, how many rollouts from each task, how long those rollouts were, what was the success rate/score of the training data, etc.). Additionally, please report other hyperparameters like context size, maximum generation length, temperature, etc.\n\n### Methodological questions\n\n* I didn’t understand why the paper did not include baselines for just vanilla, out-of-the box LLMs with no search at all. The paper includes baselines with out-of-the-box models that are used in the same greedy search fashion as STL, but there does not seem to be anything which just greedily selects actions with no value estimation. I think this is also an important comparison to include with respect to the efficiency argument, since such a model will have a much smaller inference time cost. It would be great if you could add such model-free baselines with GPT-3.5-Turbo and GPT-4o for comparison.  \n* “We train value models at each position (depth) in the trajectory” (line 594\\) → this was a really surprising methodological choice to me, and seems really strange. Couldn’t you just condition the model on what depth it’s at? Also, the fact that you actually have 4x finetuned models is a big overhead (having to serve 5 models in total\\!) and needs to be mentioned in the main text when discussing computational efficiency.  \n* I found the choice to not use ground-truth rewards at all to be curious (especially given that you *do* use the ground-truth transition function). Wouldn’t you want to at least leverage these for final states? Given that you limit trajectories to be of max 5 on WebShop and then force a buy action, it seems like you should be able to include the rewards at these terminal states. The lack of grounding in real rewards might explain why multiple iterations of STL don’t seem to help on WebShop. \n* “We fine-tuned Game-of-24 value models for 10 epochs and WebShop value models for 20 epochs” (line 681\\) → this sounds like a *lot* of epochs and I’m fairly worried about overfitting. Did you do any analysis to verify that overfitting is not happening?  \n* Why did you use MCTS to generate the training data? Does it work better than BFS or just Monte Carlo rollouts? It would help to motivate this choice more, given that it is a more complicated algorithm.\n\n### Other things\n\n* While it’s great that the paper includes tests for statistical significance, it would also be good to include error bars / confidence intervals.  \n* I think there should really be some more discussion of RL-trained reasoning agents in the Related Work section, i.e. R1, o1/o3, Gemini 2.5, Claude 3.7/4, etc., given that this approach is the current zeitgeist.   \n* What’s the budget you use for MCTS?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n\n* Significance: Training LLMs to work well in multistep, agentic settings is an important and active area of research. The demonstrated results are impressive, showing that self-improvement can enable smaller models to work as well as larger, more expensive models.  \n* Clarity: the paper is well-written with the results clearly presented. There are a number of insightful points in the paper that I think will be appreciated by others working in the space of reasoning/planning.  \n* Quality: the paper presents an impressive range of experiments, including a wide range of appropriately chosen baselines, informative ablations, and extensive analyses on efficiency and scaling. Statistical significance tests are conducted.  \n* Originality: the proposed method is a clever application of older ideas in RL to the LLMs, and in particular leverages some of the strengths of LLMs in ways that were impossible to do in the classic setting (i.e., including rationales for the value estimates).\n\nWeaknesses:\n\n* Clarity: there were a few points of confusion I had about the methods. While the appendix is already great, I think it could be further improved with a bit more detail. I discuss my particular points of confusion in more detail in the “Questions” section.  \n* Quality: there are a few methodological choices that seemed a bit strange to me, or which perhaps I didn’t fully understand. I discuss these further in the “Questions” section below.  \n* Significance: the method requires task-specific prompts for value estimation, which limits its generality.", "was_revised": true, "final_justification": "In my original review, I had some clarification questions and some concerns over some of the methodology. I think the authors did a good job addressing these in their rebuttal, especially with the inclusion of the ReAct baseline. Even after the rebuttal I do still think the task-specific prompts limit the significance of the work, but as the authors pointed out this is common in prior work too so I don't think it should be counted against the paper for acceptance.", "rebuttal": "Thank you for your thorough review! We are glad that you found STL to be a “clever application of older ideas in RL to the LLMs” with “impressive results” over an “impressive range of experiments”. We have addressed your comments below:\n\n> How does the generation of rationales and values work?\n\nAs you mentioned, using the base model, values are first generated for actions encountered through a step of lookahead (performed with the ground truth transition function) while visiting nodes during tree search. These values are generated using the prompt in Figure 9. The result of this lookahead is then used to construct formatted training examples that textually capture the lookahead process, as shown in the top right of Figure 2. After training on this dataset, we obtain an STL value model. When we perform inference with this model, we *do not use* the prompt in Figure 9, but instead use a prompt without demonstrations that looks like the training examples in the top right of Figure 2, but with the relevant information about the state being evaluated. The STL value model then simulates a step of lookahead, as shown in the bottom right of Figure 2 and mentioned in Section 3.3. We will add more discussion about the distinction between these two prompts in Section 3.3 and the Appendix.\n\n> I don’t think I fully understand what the algorithm looks like at inference time. Is it that several actions are drawn from the base model, then these are each evaluated by the value model, and the best one is picked?\n\nAs discussed in the previous response, during inference time, a step of lookahead is simulated by the STL value model to generate value judgments. Yes, in greedy search, the policy generates multiple possible actions from the current state. The STL value model then evaluates each of these actions, and the action with the highest estimated value is selected. We will make this clear in the revised version when it is discussed in Section 4.1, and also add a full algorithm for inference like the one we have included for training in the Appendix.\n\n> It’s not clear what the dataset sizes were for finetuning. It would be helpful to include this detail in Appendix H, along with maybe some other statistics about the dataset generation\n\nThe size of the WebShop training set was 1161, collected from rolling out search trees for 50 tasks in the training set. The size of the HotpotQA training set was 2708, collected from rolling out search trees for 500 tasks in the training set. As mentioned in Section 4.2, we require more tasks and training examples for HotpotQA since it has lower action diversity. We used a maximum generation length of 3192 tokens (rationales for most models were only a few sentences, but we raised this token limit to account for reasoning models) and a temperature of 1.0. We will add these to the Appendix of the camera-ready version of the paper.\n\n> I didn’t understand why the paper did not include baselines for just vanilla, out-of-the-box LLMs with no search at all. It would be great if you could add such model-free baselines with GPT-3.5-Turbo and GPT-4o for comparison.\n\nThank you for the suggestion! We have computed the performance of ReAct prompting (without search) with these models. Their results and costs on the 50-task WebShop test set are provided below:\n\n|**Model**|**Average Reward**|**Success Rate**|**Cost**|\n|---|---|---|---|\n|gpt-3.5-turbo|68.9|36.0|$0.18|\n|gpt-4o|70.0|36.0|$1.09|\n\nThese figures support the result that there does not seem to be a significant difference between using a gpt-3.5-turbo and gpt-4o policy model (Section 4.1). We will add these new results to the camera-ready version of the paper.\n\n\n> “We train value models at each position (depth) in the trajectory” (line 594). Couldn’t you just condition the model on what depth it’s at?\n\nYes, in preliminary experiments, we did condition on the current trajectory depth, but found that the fine-tuned llama-3.1-8b-instruct models were unable to properly differentiate between similar actions taken at different depths, which led to poor simulated lookahead and poor search performance. Therefore, we decided to adopt the current approach. We do agree that conditional modeling may work, but it likely requires training a larger LLM. However, we did not have the computing resources to fine-tune the larger llama-3.1-70b-instruct model. Additionally, while hosting multiple models during inference does increase computational costs, the total compute needed is *still far less than that required to host the models from other similar papers*. For instance, AgentQ produces a 72b policy model, which has more than double the number of parameters as our setup. We will add this discussion to Section 5 of the paper.\n\n> I found the choice not to use ground-truth rewards at all to be curious (especially given that you do use the ground-truth transition function)\n\nAs we discussed in the introduction (lines 23 - 25), ground truth reward (such as web task completion) is expensive and time-consuming to collect, as it often has to be manually annotated by humans. However, the ground truth transition function is almost always provided directly by the environment, as we note in the introduction (lines 39 - 41), which makes its use during training and inference a realistic and common assumption. For instance, in web-based tasks, the browser itself determines how transitions occur. STL is designed to address the common setting where practitioners desire to improve LLM search performance on a new task, but are unable to collect ground truth rewards. While the benchmarks we use for evaluation have ground truth rewards, in order to simulate this data-scarce setting, STL does not use the provided reward.\n\n> Did you do any analysis to verify that overfitting is not happening?\n\nOn WebShop and HotpotQA, we found that more epochs were needed for models to learn the lookahead format of rationales. Since STL performance showed significant improvements over using the original llama-3.1-8b-instruct model as the value model on *unseen tasks*, we can be confident that significant overfitting is not occurring on these tasks.\n\nHowever, on the Game-of-24 task, we do see a decrease in performance after the first step of self-improvement. Through an experiment in the response to TNro, we found that this decrease was likely caused by too few tasks seen during each step of self-improvement. However, we also tried training with only a single epoch instead of 10 and found that *performance slightly improved from 48% to 52%* after 50 tasks were seen during self-improvement. Thank you for pointing this out; we will add this result to the camera-ready version of the paper.\n\n> Why did you use MCTS to generate the training data? Does it work better than BFS or just Monte Carlo rollouts?\n\nSTL training data can be generated with any tree search algorithm since data generation only requires a step of lookahead to be performed after visiting each node. As we note in Section 4.1, we used MCTS rollouts on WebShop since prior work has shown empirical advantages to using MCTS as opposed to other algorithms. On Game-of-24, we use BFS to perform rollouts as was canonically done in the Tree of Thoughts paper [1]. Due to experimental costs, we were not able to conduct an ablation on the tree search algorithm used, but the results of such a study would likely be dependent on the task.\n\n\n> While it’s great that the paper includes tests for statistical significance, it would also be good to include error bars\n\nWe are glad that you found our use of statistical significance tests helpful. Below, we have computed error bars on the full WebShop test set, which we will add to the Appendix of the camera-ready version:\n\n| **Policy** | **Value Model**| **Average Reward** | **Success Rate** |\n|-|-|-|-|\n| gpt-3.5-turbo  | llama-3.1-8b-instruct| 67.7 ± 2.26 | 26.4 ± 3.86|\n| | deepseek-r1-distill-llama-8b    | 66.3 ± 2.30| 24.6 ± 3.78|\n|  | gpt-3.5-turbo | 70.6 ± 2.43 | 35.6 ± 4.23|\n|  | gpt-4o | 71.5 ± 2.51| 40.6 ± 4.33|\n| gpt-4o| llama-3.1-8b-instruct  | 67.2 ± 2.30| 25.8 ± 3.84|\n|| deepseek-r1-distill-llama-8b| 66.5 ± 2.33| 25.6 ± 3.83|\n|| gpt-3.5-turbo| 72.4 ± 2.40| 38.8 ± 4.29|\n| | gpt-4o| 71.4 ± 2.49| 40.8 ± 4.35 |\n| **––– STL Results –––** |\n| gpt-3.5-turbo  | llama-3.1-8b-instruct-STL | 72.8 ± 2.32 | 36.6 ± 4.22|\n| gpt-4o | llama-3.1-8b-instruct-STL | 74.2 ± 2.38 | 40.6 ± 4.30|\n\n> I think there should be some more discussion of RL-trained reasoning agents in the Related Work section\n\nThank you for the suggestion! We will add a discussion in the related work section about recent work [2] that shows that models explicitly trained for agentic use, like Deep Research, greatly outperform general-purpose RL-trained reasoning models like o1. This work corroborates findings in our paper that search with specialized value models improved with STL outperforms RL-trained reasoning models like r1-distill and qwen-3. \n\n> What’s the budget you use for MCTS?\n\nWe run MCTS for 30 iterations, which is the same setting used by the LATS baseline. We will clarify this in Section 4.\n\n> The method requires task-specific prompts for value estimation, which limits its generality.\n\nGenerality is an important consideration. However, almost all prior LLM agent work uses task-specific prompts for action generation and/or value estimation, including Reflexion, ReAct, LATS, and ToT.\n\n\n[1] Shunyu Yao et al. 2023. “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”. Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Main Conference Track\n\n[2] Jason Wei et al. 2025. BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agents. OpenAI."}, {"review_id": "cssB9slhhR", "reviewer": "Reviewer_C12m", "summary": "This paper proposes self-taught lookahead (STL), a self-supervised method that leverages state-transition dynamics to improve a value model capable of effectively guiding language model-controlled search without requiring ground-truth rewards or human demonstrations. The method fine-tunes a value LLM using lookahead state transitions and generated rationales, enabling lightweight yet effective search guidance across multiple tasks.", "questions": "1.The paper does not clearly differentiate STL from existing Rewardn and Demo Free models. It seems the main change is adding rationales to trajectories as input for value prediction.\n\n2.Consider adding a brief mention of the method’s limitations and broader impacts in the Conclusion.\n\n3.While most equations are clear, some notations (e.g., Equation 6) could benefit from further clarification.", "limitations": "The authors discussed some limitations and broader impacts.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.Addresses the high cost of human labels in multi-step reasoning tasks, an important practical limitation in deploying LLM-based agents.\n\n2.Evaluates STL across diverse tasks with clear baselines and ablation studies illustrating each component's contribution\n\nWeaknesses:\n\n1.The paper states that it uses a single lookahead step within tree search to generate self-improvement data but does not introduce how tree search itself is performed. \n\n2.Rationales are a key part of STL, but their structure and role remain abstract in the paper.\n\n3.While comparisons with Reflexion, LATS, and AgentQ are present, the paper could be strengthened by explicitly discussing comparisons with recent methods, especially in 2024, highlighting differences in effectiveness and generalization.", "was_revised": true, "final_justification": "I have carefully reviewed the authors' responses and examined all the reviewers' questions and discussions. The authors have fully addressed all my concerns and provided additional experiments. Therefore, I will update my score accordingly.", "rebuttal": "Thank you for your detailed feedback! We are glad you found that our work addresses an “important practical limitation in deploying LLM-based agents”. Please find responses to your comments below:\n\n> The paper states that it uses a single lookahead step within tree search to generate self-improvement data, but does not introduce how tree search itself is performed.\n\nAs detailed in Section 3.1 (lines 97-99), we use classical tree search algorithms (BFS and MCTS) during the data generation phase. These methods have been widely used in prior LLM search work [1, 2] and are detailed in Section 2. For algorithms like MCTS, which require a reward to guide search, we use an LLM-generated value as a proxy reward, as we detail in Section 4.1 (lines 141 - 143). As you have mentioned, when a node is visited during tree search, we perform a step of lookahead to help inform a better estimate of the state’s value, as shown in Figure 2 and Section 3.1. \n\n> Rationales are a key part of STL, but their structure and role remain abstract in the paper.\n\nThe rationales learned during self-improvement take the following form: “{action} {outcome state} {natural language value rationale}” as mentioned in Section 3.1 (line 108) and depicted in the top right of Figure 2. Besides this lookahead structure, we do not impose any format for the natural language value rationale, but rather bootstrap a base instruction-tuned model. However, we agree it would be helpful to see examples of these rationales. We provide an example of the training data below, which we will add to the Appendix:\n\n##### **Task and Current Trajectory:**\n\nInstruction: i'm looking for a pair of women's workout shorts with a drawstring waist. i need them to be extra large and in light gray, and price lower than 60.00 dollars \n[Search] \n\nAction: search[women's workout shorts drawstring waist extra large light gray < 60 dollars]\n\nObservation: *removed for brevity*\n\nCurrent Action: click[B09T3PJM1R]\n\nCurrent Observation: *removed for brevity*\n\n##### **STL Output:**\n\nI will evaluate the best successor state from the current state:\n\nBest Next Action: click[x02c-gray]\n\nObservation of Best Successor State: You have clicked x02c-gray.\n\nReflection of the Best Successor State: The last action selects the color 'x02c-gray' for the item B09T3PJM1R.\t\nBased on the observation, this product's color is indeed gray, which matches the specified criteria.\nTherefore, this product matches one of the attributes mentioned in the task.\nThe last action and observation thus capture a step that selects an attribute mentioned in the instruction, but not all attributes mentioned (specifically the size attribute) are currently selected.\nThus, the correctness score is 6.00 / 10.00.\n\n\n\n> While comparisons with Reflexion, LATS, and AgentQ are present, the paper could be strengthened by explicitly discussing comparisons with recent methods, especially in 2024.\n\nWe agree that comparison with recent methods is crucial to contextualize our work. However, we note that methods like LATS and AgentQ are from 2024, with the former appearing at ICML 2024 and the latter appearing on arXiv in August 2024. We also compare to search with a reasoning value model r1-distill-llama-8b, which was released in January 2025. In the HotpotQA domain, we also compare to R1-Searcher (released in March 2025). However, we do agree that it would be interesting to include additional comparisons with recent models. Therefore, we ran an experiment using a gpt-3.5-turbo policy with a qwen3-8b reasoning value model that was released in late April 2025. The results on the 50-example WebShop test set are provided in the Table below:\n\n| **Model**                               | **Average Reward**  | **Success Rate** | **Cost** |\n|-----------------------------------------|--------------------|------------------|----------|\n| qwen3-8b (thinking mode enabled)        | 68.6   | 34.0            | $3.80     |\n\nWe will add these results to the camera-ready version of the paper.\n\n\n> The paper does not clearly differentiate STL from existing Reward and Demo Free models. It seems the main change is adding rationales to trajectories as input for value prediction.\n\nAs depicted in Figure 1 and explained in the Introduction (lines 27 - 29), other Reward and Demo Free methods are *inference-only methods* that cannot *improve* performance through learning and are therefore constrained to the performance of the off-the-shelf LLM used for search. In contrast, STL enables improvement even in the data-scarce Reward and Demo Free setting by explicitly learning in the form of supervised-finetuning on rolled-out lookahead and generated rationales. As we demonstrate across tasks, this value model improvement yields better value prediction and superior downstream search performance.\n\n> Consider adding a brief mention of the method’s limitations and broader impacts in the Conclusion.\n\nThank you for the suggestion! We note that we have discussed Limitations in Appendix C, but will add some of this discussion to the conclusion in the camera-ready version of the paper.\n\n\n> While most equations are clear, some notations (e.g., Equation 6) could benefit from further clarification.\n\nThank you for the suggestion; we will add references to Figure 2 when discussing Equation 6 in Section 3.3 to help clarify the notation. We will also reiterate the concatenation notation, which was first introduced in Section 3.1, again in Section 3.3.\n\n\n[1] Andy Zhou et al. 2024. “Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models.” Proceedings of the 41st International Conference on Machine Learning\n\n[2] Shunyu Yao et al. 2023. “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”. Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Main Conference Track"}]

Author rebuttal:

Meta-review: This paper proposes to improve LLM-based value model via Self-Taught Lookahead (STL). STL conducts tree search using state transition dynamics and backup value estate from rollout state to obtained better value estimates. The authors tested the proposed method on Webshop, HotPotQA, and Game-of-24 and find STL can improve a 8B open-weight value models to match the performance of gpt-4o on these tasks. Overall reviewers are happy with the significance, clarity and originality of the work. While there were some questions and confusions in the initial reviews, the authors conducted a very effective rebuttal, and addressed most of the concerns. Three reviewers voted to accept the paper as is. Reviewer C12m remained on the fence. The authors did compare to a couple of method published in 2024, so hopefully that alleviate the concern on comparison to more recent methods. The suggestion to include more discussion on the structure and role of rationale in the proposed method is valid, please address in the final draft.
Decision: Accept (spotlight)