QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Authors: Zongyu Lin
Yao Tang
Xingcheng Yao
Da Yin
Ziniu Hu
Yizhou Sun
Kai-Wei Chang
Venue: ICML 2025 poster (2025)
Keywords: Agent
process reward model
Primary area: deep_learning->large_language_models

Abstract: Language agents have become a promising solution to complex interactive tasks. One of the key ingredients to the success of language agents is the reward model on the trajectory of the agentic workflow, which provides valuable guidance during training or inference. However, due to the lack of annotations of intermediate interactions, most existing works use an outcome reward model to optimize policies across entire trajectories. This may lead to sub-optimal policies and hinder the overall performance. To address this, we propose QLASS (Q-guided Language Agent Stepwise Search), to automatically generate annotations by estimating Q-values in a stepwise manner for open language agents. By introducing a reasoning tree and performing process reward modeling, QLASS provides effective intermediate guidance for each step. With the stepwise guidance, we propose a Q-guided generation strategy to enable language agents to better adapt to long-term value, resulting in significant performance improvement during model inference on complex interactive agent tasks. Notably, even with almost half the annotated data, QLASS retains strong performance, demonstrating its efficiency in handling limited supervision. We also empirically demonstrate that QLASS can lead to more effective decision making through qualitative analysis.

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Zongyu Lin 1*
Yao Tang" 2'
Xingcheng Yao
Da Yin
Ziniu Hu"
Yizhou Sun
Kai-Wei Chang
Abstract
1. Behavior Cloning
4. Q-gulded G Generation
SFT Dataset
QNet
Language agents have become a promising solu- tion to complex interactive tasks. One of the key ingredients to the success of language agents is the reward model on the trajectory of the agen- tic workflow, which provides valuable guidance during training or inference. However, due to the lack of annotations of intermediate interac- tions, most existing works use an outcome reward model to optimize policies across entire trajecto- ries. This may lead to sub-optimal policies and hinder the overall performance. To address this, we propose QLASS (Q (Q-guided Language Agent Stepwise Search), to automatically generate an- notations by estimating Q-values in stepwise manner for open language agents. By introducing a exploration tree and performing process reward modeling, QLASS provides effective intermediate guidance for each step. With the stepwise guid- ance, propose Q-guided generation strategy to enable language agents to better adapt to long- term value, resulting in significant performance improvement during model inference on complex interactive agent tasks. Notably, even with almost half the annotated data, QLASS retains strong performance, demonstrating its efficiency in han- dling limited supervision. We also empirically show that QLASS can lead to more effective deci- sion making through qualitative analysis.
2. Self-Generation & Tree Construction
81
33
LLM Agent
E Environment
0.9
0.1
0.8
U: task
5: state
8: action
a2
q: Qivillu
S2
3. Train QNet
$5
(5
QNet
Figure 1. QLASS pipeline overview. QLASS involves mainly four stages: 1) Supervised fine-tuning (SFT) on expert data. 2) Leverage SFT agent to explore the environment and construct an exploration tree for each task. After construction, estimate the Q-value of cach tree node based on Equation 7. 3) Train QNet on the estimated Q-values. 4) Use the trained QNet to provide inference guidance at each step.
et al., 2023; Yin et al., 2024). However, the substantial hu- man annotations required to collect training data present a significant bottleneck, limiting both performance and seal- ability. This challenge is particularly pronounced in agent tasks (Yao et al., 2022: Shridhar al., 2021; Wang et al., 2022a), where data scarcity is a critical issue due to the inherent complexity and diversity of real-world interactions. To overcome this challenge, self-improvenen have shown to be a promising area of research, enabling L.MMs to learn from self-generated data without extensive human intervention (Wang et al., 2022b; Singh et al., 2023; Hosseini et al., 2024; Zhang et al., 2024), and most recently, enable L.MSs to improve their outputs by scaling up their test-time computation in a more intelligent way (Wang et al., 2024; Shinn et al., 2023; Snell et al., 2024). Inspired by this, we focus on improving the inference- time search for language agents, which is crucial technique for the success of more generalizable agents in real-world environments.
techniques
1. Introduction
Supervised fine-tuning (SFT) is commonly employed to make base LLMs perform effective reasoning and planning in complex agent tasks by imitating expert trajectories (Chen
Equal contribution. Equal advising. 'University Califor- nia, Los Angeles, USA "Shanghai Jiaotong University, Shanghai, China. Correspondence to: Yizhou Sun <yizhou.suu @un.ucla.eduu. Kai- Wei Chang www.eeiichhan@ulll.dd......
An essential component of inference-time scaling methods is the reward model (Snell et al., 2024), which evaluates the quality of self-explored data. Many existing works derive single outcome reward based on ground-truth (Wang et al., 2024; Shinn et al., 2023). Although this approach is straight- forward, it falls short in handling complex agent tasks, since an outcome- reward model cannot accurately score each step within long trajectory in intricate scenarios, In addition, a
Proceedings of the nddd International Conference Machine I Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s))
'We will release our code and data in https: //t::////itt thub. com/ Ra fa zy/C QLASS

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
trajectory achieving a high final outcome reward does not necessarily indicate that every action taken was optimal; the agent may have completed the task successfully, but some actions could have been inefficient or suboptimal (Uesato et al., 2022).
ward through trajectories, dynamically pruning actions with low reward while preserving critical decision points. This enables agents to disentangle productive reasoning from wasteful loops, even with limited supervision. To summa- rize, our contribution can be divided into three folds:
Therefore, a good process reward model is necessary to learn from the environmental feedback and provide step- wise evaluations of agent actions. This model enables the agent to fully understand and learn from the intermediate stages of complex tasks, ultimately improving performance and generalization. The key challenge lies in developing an effective process reward model for self-improvement with- out relying on extensive human annotations for the stepwise reward. There has been a thread of work that has focused on process reward modeling (Uesato et al., 2022; Lightman et al., 2023; Wang al., 2023; Chen et al., 2024). However, these methods rely on either costly human annotation or computationally heavy random rollouts, rendering them in- efficient for the self-improvement of language model agents.
1) Process Reward Modeling with Q-Value Estimation: We introduce QLASS, novel strategy that leverages es- timated Q-values to generate intermediate annotations for language agents, providing stepwise guidance for model inference. We visualize the overall framework of QLASS in Figure 1.
2) Q-Guided Generation Strategy: We propose a Q- guided generation technique that significantly enhances agent performance via process-based guidance during infer- ence, ensuring effective decision making at each step.
3) Superior Performance with Limited Supervision: QLASS shows strong performance on set of diverse agent environments, including WebShop, ALFWorld, and Sci- World. QLASS can give effective inference-ting guidance even when nearly half of the annotated data reduced. These experimental results highlight the efficiency and ro- bustness of QLASS in scenarios with limited supervision.
To reduce the annotation reliance on process rewards, we propose QLASS to perform effective process reward mod- eling to guide agent inference. Specifically,, we explicitly formalize the self-generated exploratory trajectories ploration trees and update the process rewards of all the tree nodes based on the tree structures. To better capture the future utility at each step of a multi-turn reasoning pro- cess, we employ the Bellman equation (Bellman & Dreyfus, 2015) to learn a Q-based process reward. Unlike simple outcome-basee rewards, this Q-value captures how imme- diate decisions contribute longer-term payoffs, enabling finer-grained control over the reasoning trajectory. More- over, the Bellman update rule iteratively refines the esti- mated Q-values by propagating future rewards hack to ear- lier states, reducing reliance on sparse or delayed feedback signals. This allows us to efficiently gather supervision for state-action pairs without requiring explicit annotations of full trajectories. With these Q values in hand, can then train a function approximator (QNet) (Watkins & Dayan, 1992) to predict the expected return of any partial solu- tion, ultimately providing a strong inductive bias to guide laen-language agents. By prioritizing actions with higher estimated Q values, the agent steers its own reasoning in a more targeted manner, facilitating efficient stepwise plan- ning within expansive search spaces.
2. Related Work
2.1. Large Language Model Agent
Large language models have shown impressive performance in complex interactive tasks, such as web navigation (Yao et al., 2022), scientific reasoning (Wang et al., 2022a), and action planning in embodied environments (Shridhar et al., 2021). ReAct (Yao et al., 2023) developed a prompting method to shape language models as agents that can reason and act. While several works (Shen et al., 2024; Song et al., 2023) improve agent performance with closed-source LLM controllers, the open-source LLM agents still offer unique advantages like accessibility and customization. FireAct (Chen al., 2023) and LUMOS (Yin et al., 2024) leverage high-quality data generated by experts and employ teacher- forcing to improve the performance of open-source agents. Koh et al. (2024) uses best-first tree search for language agents with the value function given by GPT-4o. In line with this, our QLASS is also based on open-source LLMs.
While recent attempts like KIMI-k1.5 (Team et al., 2025) and Deepseek-R1 R1 (Guo et al., 2025) report failures in pro- cess reward modeling, we argue that such modeling is indis- pensable for agent tasks. Back-and- forth agent behaviors inherently create stepwise inefficiencies (e.g., repetitive en- vironment queries or cyclic reasoning). which the sparse outcome rewards cannot diagnose. Our Q-value estimation directly addresses this by propagating future utility back-
2.2. Self-Improvement for LLM
The self improvement of LLM can be a good way to im- prove LLM without heavy human annotation, which can be divided into two parts. (I) Training models on self- generated data is a promising approach. A large number of works (Dou et al., 2024; Wang et al., 2022b; Yuan et al., 2023; Singh et al., 2023; Gulcehre et al., 2023; Wang et al., 2023) follow the paradigm of self-training, which filters
2

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
positive self-generated data and performs model training on those filtered data. Some other works (Song et al., 2024; Setlur et al., 2024) utilize both positive and negative data to construct preference pairs and update the policy using direct preference optimization (Rafailov et al., 2024). (2) Another approach is to scale up the computation of inference to im- prove the outputs of LLMs. The methods include guiding the inference based on scalar-based reward models (Wang al., 2024; Xu et al., 2022; Zhai et al., 2024) and modifying the output conditioning on the language feedback (critique provided by the LLM itself or another critique LLM) (Zhou et al., 2024; Wu et al., 2024; Shinn et al., 2023). In our paper, we focus on the self-ing ieff-improveeent at inference time using our proposed process reward models.
future rewards by taking action a given state 8. The optimal Q-function can be written as,
Q' (s. max B[r, + mit + +7 22ree22 +
x
(I)
8, s, 0 = a0 n]
where π is the policy, y the discount factor, and re is the received reward at step t. Given the definition of op- timal Q-fuention in Equation the Bellman Optimality Equation (Bellman & Dreyfus, 2015) of Q-function can be written as,
(s) = r2 + max Q" (5)+1,
(2)
ae
In Q-learning, the value model Q(s,, a.) is updated itera- tively by,
2.3. Process Reward Modeling for LLM
(1), -(1 (() + a(ri + 7 maa Q(++1,a)), aaA
Existing works have explored various strategies and rea- soning policies for process reward modeling. (Uesato et al., 2022) and (Lightman et al., 2023) utilize human- annotated step-level correctness train reward model. Math-Shepherd (Wang et al., 2023) infers per-step rewards through random rollouts. TS-LLM (Feng et al., 2023) em- ploys an MCTS-basee policy and infers per-step rewards us- ing the TD-A (Sutton, 1988) method. ReST-MCTS* (Zhang et al., 2024) uses Monte Carlo tree search (MCTS) with re-inforced self-training to enhance the diversity and per- formance on general reasoning tasks like maths, science, and code. Most recently, Wang et al. (2024) Zhai et al. (2024) and Chen et al. (2025) also use step-level guidance for agent inference through training step-level value model. Putta et al. (2024) applies a hybrid process reward model- ing for web navigation tasks by combining Monte Carlo Tree Search (MCTS) rewards with scores generated by large language models to form process rewards. Our approach fo- cuses solving complex agent tasks by providing effective per-step guidance for LLM agent inference. Our method differs from Putta et al. (2024) because we do not rely on a strong proprietary LLM to provide rewards. Compared with Wang et al. (2024) and Zhai et al. (2024), we shift our focus on more complex agent tasks with larger search space and deeper search depth like ALFWorld and SeiWorld. Compared with Zhang al. (2024), our framework is much simpler with less stages of training and more straightforward to make process reward modeling works better compared with strong crainin-bbssed basclines.
(4)
where a is the learning rate and A is the action space. Com- bining immediate rewards from the current action and future potential rewards from subsequent actions, Q-value can be interpreted as the expected long-term value of taking spe- cific action in a given state.
In complex interactive tasks, the agent needs to account not only for immediate rewards but also for the potential long-term effects of its current decisions. This is where the Q-value becomes essential. However, directly adapting RL algorithms such as Q-learning to language agents can be sample-inefin ineffleiieffiiientt (Jin et al., 2018). This is because the action space in language agent tasks is typically a vast vo- cabulary, which may lead to an explosion of potential action sequences to be explored. To address this challenge, our approach successfully adapts Q-value extraction to language agent tasks by introducing an exploration tree, which we will introduce in the next section.
4. QLASS Pipeline Details
In this section, we will follow the order of QLASS pipeline and introduce each critical component step by step. The overall pipeline is shown in Figure 1 and Algorithm 1.
First, we will describe the initial stage of behavior cloning, Then, will explain how the exploration tree is constructed during the second self-generation stage and how we use it to extract Q-values as the supervision to train Q-network (QNet Training). Finally, we will detail the Q-guided generation how the QNet is employed to guide the agent's test-time inference in a stepwise manner.
3. Preliminaries
In this section, we introduce Q-learning, the key algorithm that inspires QLASS to extract Q-values from the explo- ration trees. Q-learning (Watkins & Dayan, 1992) is a tradi- tional model-free reinforcement learning algorithm, where a value function (ss, a) is trained to represent the expected
4.1. Behavioral Cloning
Behavior cloning provides a strong initial foundation for language agents by supervised fine-tuning on expert trajec-
3

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Algorithm 1 General QLASS Pipeline
Specifically, a Tree Node N in exploration tree T is defined set of the following attributes:
Input:
Expert dataset Deupert = {(us, dz, 0t)t-1lim)
policy To, QNet 2B
State (sy): Represents the accumulated historical context from the initiation of the process up to the current time step i, encapsulating all preceding reasoning paths and actions. Formally, the state at time is given by
Stage 1: Behavior Cloning
Train Th on D Deapert minimizing loss 5
Stage 2: Construct Reasoning Trees
for i == to Ne do
Construct a reasoning tree with Algorithm 2 Update Q-values recursively with Equation 7
{u, 01 0..... 0:-1: 1
(6)
including the task description and history at step t.
end for
Collect Q-values from (T));=1 as dataset De
Action (a,): denotes the specific operation performed at the current node, which affects the subsequent state. The action is selected by the policy language agent и and is conditioned on the current state and reasoning path.
Stage 3: QNet Training
Train QNet 2g on dataset De Step 4: Q-guided Generation
Use QNet Q2 to score state-actions at each step
Reward (r²): the immediate feedback received from envi- ronment after performing action 0g. In most language agent tasks, the immediate rewards from environments are to zero or very sparse. For example, WebShop (Yao al., 2022) only provides a final reward from 0 to I at the end of trajectories.
tories. Formally, the first stage of QLASS is to supervised fine-tune our language agent, denoted as the policy n, on set of annotated samples Despert. We use ReAct (Yao al., 2023)-style data for supervised fine-tuning, which addition- ally generates reasoning paths before executing each action. We will use a to denote the complete ReAct-style response generated by ı for simplicity.
oaain--o-Thouhhh (CoT) (Wei et al., 2022)
Children (C): is represented by a list containing nodes explored at the next step.
Q-value (q): represents the expected total future reward achievable starting from the current state 8t, taking action dg, The Q-values are updated once an exploration tree is constructed. We will introduce how we extract Q- Q-values in the following section.
Formally, given dataset Despert = {(u;, de, ==) )=i where u; represents the task description, T is the trajectory length, N₂ is the number of trajectories in the expert dataset, of is the environment observation after taking action aj at step f, we optimize the policy æ by minimizing the negative log-like ligeliill loss:
4.2.2. TREE CONSTRUCTION
We construct the reasoning trees in Algorithm With each step in trajectory formalized as a TreeNode, the entire trajectory is branch within exploration tree. To ex- plicitly construct an exploration tree that captures potential generations from the root node (i.e., the initial task), ex- ploring new trajectories can be viewed as expanding new branches from the existing TreeNodes. For any non-leaf tree node, effective generation can be achieved by: 1) directly exploring and adding new child nodes that differ from the existing ones. 2) For each branch that reaches leaf node, we assess its quality based on the final reward provided by the environment. If the branch yields a zero reward, we stop generation on that branch's 's nodes, thereby reducing ineffective generation.
((0) - -E log To (ai
I ui dies dee)
(5)
where @ denotes the parameters of the policy model mo. which outputs the probability of action a given task descrip-
tion u and historical interactions h, = {aac, Oct)
4.2. Constructing an Exploration Tree
The supervised fine-tuned agents can explore the environ- ment and collect a large amount of trajectories. However, due to the extremely large search space of language agents, directly sampling trajectories without any guidance may lead to low efficiency. To address this issue, we propose to construct exploration tree during self-generation.
We introduce our strategy for tree construction detail as follows.
4.2. 1. TREE STRUCTURE
Tree Pruning. In practice, we have found that the average depths of tree searching for agent tasks are large. Build- ing an exploration tree and expanding every potential tree nodes may lead to heavy cost to the trajectory generation. To address this, we propose several strategies to reduce the computational burden during tree construction. We employ
For a trajectory, we take the task description as the root node, and each node below the root node is composed of the state, action, and related information for each step. For all trajectories of a task, they can be seen as different branches that originate from the same root node.

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Algorithm 2 Constructing a Reasoning Tree
Input: A LLM agent Tg. a given task description u, a trajectory To from the training set D Pexpert on task u, max exploration depth D, max exploration width W
Initialize root node U with state Initialize the reasoning tree T with U The expansion node queue E - [u]
u. depth /. + 0, reward r 0, action null, children set C 0
Subroutine ProcessExpunsionnuuuuec.. while E is not empty do
Get a node N < pop with state N.s, action N.a, reward N.r, children set C' at step N. if the number of children in N.C < W and N.t s then Sample new trajectory T based on state N.s Get new branch b constructed on and merge b in node N.C if achieves a non-zero final reward then
Push all the nodes on b with N.t s D into E end if end if
end while
End Subroutine PronessExxpnssionnuuuee
Call ProcessExpansionnuuueeeee
Construct branch with To and merge in U.C
Push all the nodes on b with depth i and s D into E
Call Exreesssxpansiinnuuuee return the reasoning tree T
pre-pruning techniques lower the generation costs when constructing an exploration tree for each task. First, limit the expansion of tree nodes to the early stages of trajectory (e.g., the first three to five steps, depending on the environ- ment's complexity, with details provided in Appendix A.2).
from the policy æ. We provide the pseudocode of Q-value estimation the exploration trees in Appendix A.3.1.
4.3. QNet Training
Inspired by the value function representing the expected long-term value in Q-learning (Watkins & Dayan, 1992), extract Q-values for each node the exploration trees using Equation 7. For each node N = (s, a, Q.... in the collected exploration trees, we can then construct super- vised dataset Dq {(s, a, q)} to train a Q-network (QNet), initialized from supervised-fine-tne plying online Q-learning in language settings is often im- practical, due to the unbounded action space of natural lan- guage and the sparse nature of rewards. Instead, by labeling each node with a corresponding Q-value offline and then training QNet in a purely supervised manner, we bypass the instability and excessive exploration costs that typical rein- forcement learning loops would incur in fiigh-dmensionall language environments. The model architecture of QNet introduced in Appendix A.2.2.
Next, when a branch leads to a zero-outcome reward at its leaf node, we propagate a Stop expans on signal from the leaf node back the earliest unexpanded intermediate node on that branch. This helps prioritize the generation of optimal trajectories given limited generation budget. This construction process is illustrated in Figure 2.
LLM. Directly ap-
With a set of exploration trees, we aim to efficiently gather effective step-wise signals for training an effective process reward model. Since most language agent tasks only return an outcome reward at the end of the trajectory, which is stored at the leaf nodes of the exploration tree, we need to develop methods to leverage these outcome rewards to generate effective intermediate signals.
Extracting Q-values. After constructing an exploration tree, with the outcome rewards stored in leaf node rewards, we estimate the Q-values for each intermediate node lever- aging
Training Objective. Given each exploration tree T with nodes: T (N₁, N2...., .., N,), we train the QNet 2s by minimizing the Mean Squared Error (MSE) loss between the predicted Q-values d and the target Q-value calculated previously at each time step.
-C, Q1), = + max [Q(8441,
(7)
where y is the discount factor, $1+1 is the new state after action a,, C2 is the children set containing nodes explored at the next step, and the expectation is over actions 4,+1 drawn
(())
1 (á. t=
Σ
B
g²)
(8)
n
5

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Reasoning Tree
Task
I'd like to buy pair of black pants for cocktail party.
S1:[u]
S1: [u]
a1 Search [black parts]
ay Search [8 ack causal pants]
r1.. 0
0
F2: [4, d1 0z]
5y [4. 01
52: [M, a1 01.01]
Stop expansion
az Click (tem
Keep expansion
ag. Clice (Itam B]
ag. Cikck (Itam
Fz
Fg.
rg 0
Pr: is notcompleeed!
Oy: Task completed!
Ty.Task completed!
0
Ey. 0.3
0.9
Figure 2. Illustrative example of constructing exploration tree. Grey nodes represent the branches with zero oulcome reward. Once the leaf node with a zero outcome reward is detected, a Stop expansi on signal will be sent back to the first unexpanded node on the branch. Green nodes are on branches where zero outcome reward is not detected and can keep expanding.
5.1. Setup
Table 1. The statistics of datasets (We follow the same setup ETO (Song et al., 2024)). "Test-Seen" and "Test- "Tnsecn are test with seen and unseen cases respectively. "#Turns" means the average number of interaction turns for the SFT trajectories.
Datasets. We assess the ability of QLASS Web- Shop (Yao et al., 2022), ALFWorld (Shridhar et al., 2021) and SciWorld (Wang et al., 2022a). These environments only provide single outcome reward at the end of each trajectory. The statisties of three agent datasets are dis- played in Table The evaluation metric is the reward averaged on the test sets. During the sampling process, environments will give a termination signal when certain actions like "Click[Buy Now]" in Webshop are taken or the set maximum steps are reached. Details can be found in Appendix A.2.
Dataset
#Train
#Test-Seen
#Test-Unseen
#Turns
WebShop 1,938
4.9
SeiWorld
1,483
194
241
14.4
ALFWorld
3,321
140
134
10.1
By minimizing this loss, we encourage the QNet to pro- duce consistent Q-value estimations across the sequence that align with the target Q-value q. This training objective emphasizes accurate Q-value predictions at each token, re- inforcing the model's 's ability to assess the long-term value of actions throughout the trajectory.
Training Setup. In our work, we mainly use -lama-2-BB Chat as base policy model and QNet backbone. We train our models mainly using 4 or 8 A6000 GPUs. The experiments Webshop, including the training of SFT model, QNet, self-generation and Q-guided exploration, takes one two days and the experiments on ALFWorld and SciWorld takes for training
4.4. Q-Guided Generation
four or five days. The detailed and model architectures can be found in Appendix A.2.
The effectiveness of good process reward model can be represented by whether can lead to better agent self- improvement. Therefore, we conduct Q-guided genera- tion for self-improvement to evaluate the effectiveness of QLASS. Q-guided generation enables agents generate each step under the guidance of QNet. At each step, agents sample several actions and the one with the highest Q-value is executed by the agent. We provide a more detailed algo- rithm of Q-guided generation in Appendix A.3.2.
Baselines. 1) SFT (Chen et al., 2023) is the base agent after supervised fine-tuning the expert data. 2) RFT (Rejection sampling Fine-Tuning) (Yuan et al., 2023) is self-improvement baseline which is trained on the merged data consisting of successful trajectories sampled and expert data. 3) ETO (Song et al., 2024) a seffiimproeement base- line which updates policy via constructing trajectory-level preference pairs and conducting DPO. PPO (Proximal Policy Optimization) (Schulman al., 2017): reinforce- ment learning baseline which directly trains the base agents to optimize the final rewards. 5) Best-of-N samples N tra- jectories for each task and selects the one with the highest oracle outcome reward.
5. Experiment
In this section, we aim to evaluate the effectiveness of QLASS for solving complex agent tasks in the following aspects: 1) whether QLASS can aid better decision making on different complex agent tasks; 2) whether the Q-value in QLASS is an effective process reward to facilitate self- improvement; 3) whether QLASS can retain strong perfor- mance with reduced annotated data.
N set to Table and Table 3. All the inference- time baselines in the tables are under the same search bud- get for fair comparison. 6) Closed-source agents: GPT.
6

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Table Performance of all the haselines on WehShop, SciWorld and ALFWorld. The tahle is divided into sections: the first presents the results of closed-source agents and the second includes open sour-ee agents. indicates the baseline based on GPT-4o. In each column, the best result bolded and the second-best result is underlined.
SciWorld
ALFWorld
Method
WebShop
Seen
Unseen
Seen
Unseen
GPT-4
63.2
64.8
64.4
42.9
38.1
GPT-3.5-Tubo
62.4
16.5
13.0
7.9
10.5
Reflexion (Shinn et al., 2023)*
64.2
60.3
64.4
45.7
55.2
Base Agent (Llama-2-7B-CN))
17.9
3.8
3.1
0.0
0.0
SFT
63.1
67.4
53.0
60.0
67.2
RFT (Yuan et al., 2023)
63.6
71.6
54.3
62.9
66.4
PPO (Schulman et al., 2017)
64.2
59.4
51.7
22.1
29.1
Best-of-N
67.9
70.2
57.6
62.1
69.4
ETO (Song al., 2024)
67.4
73.8
65.0
68.6
72.4
MATH-SHEEPHERD (Wang et al., 2023)
66.9
72.5
63.3
72.9
76.9
TS-LLM (Feng al., 2023)
67.7
73.7
65.3
74.3
79.1
QLASS
70.3
75.3
66.4
77.9
82.8
3.5-Turbo and GPT-4 with ReAct prompting (Yao et al., 2023), and methods depending on the emergent properties of self-reflection and planning from large proprictary mod- els, and we use Reflexion (Shinn et al., 2023) as the base- line (use GPT-4o as the base model). We also include (7) Process reward model based baselines, including MATH- SHEPHERD (Wang al., 2023) and TS-LLM (Feng al.,
72.6
72
Best-of-N QLASS
70.9
WebsShop Score
70
68.4
68
67.9
67.7
2023).
66.4
66
5.2. Evaluation Results
65.1
150
200
250
300
350
400
Completion Tokens
In this section, we compare the performance of our QLASS with all the baselines WebShop, SciWorld, and ALF- World. We evaluate all algorithms using one-shot evaluation. The decoding temperatures are set to 0.7 for QLASS and Best-of-N and for other baselines.
Figure 3. QLASS and Best-of-N under different search budgets. The x-axis represents the number of tokens consumed by the tra- jectories generated during inference averaged on all the tasks each test set.
Overall Baseline Comparison. Results are summarized in Table 2. From Table 2, we can observe that QLASS consistently achieves the highest scores among all the open- sourced baselines, including both wrining-based methods and inference-basee methods. QLASS also demonstrates comparable performance with the best proprietary base- lines. Specifically, GPT-4 the state-of-the-art model, but QLASS still outperforms on all three benchmarks by 17.9% on average, especially on SeiWorld and ALFWorld. Also, QLASS outperforms ETO and PPO consistently by over 5% average, which two strong baselines based on multiple stages of training, including supervised fintun- ing on expert trajectories, training reward models and doing DPO or PPO on the explored trajectories. We achieve better performance while avoiding the heavy cost (including the hyperparameter tuning on DPO/ PPO).
the results in Figure 3. We find that increasing the number of completion tokens will improve the performance of all inference methods. We can observe that QLASS is con- sistently better than Best-of-N under almost all the search budgets. Another notable observation is that compared with Best-of-N (68.4) under 400K tokens, QLASS (70.3) with only about half of search budgets under 240k tokens, out- performs the highest score of Best-of-N (68.4). Also, as the completion tokens approach 360K, Best-of-N begins to flatten, while the score of QLASS still gets improved by a relatively larger margin from 360K tokens to 400K tokens. This indicates that our approach is a more effective way to scale up the compute for inference-time aol--imprveeent.
Self-training Performance. Since process reward model- ing is an important module in our framework, we ablate on how different choices of process reward can affect the perfor-
Inference-time Search Efficiency. We compare QLASS and Best-of-N under different search budgets and visualize
Part of the results results are adopted from (Song et al., 2024) and (Zhou et al., 2024).

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Table 4. The performance different base LLM on SciWorld.
68
SciWorld
66.4
Base LLM
Method
WebSStop Score
66
65.4
Seen
Unseen
64.7
SFT
68.1
57.6
Llama-2-13B
'4
63.6
ETO
71.4
68.6
63.1
QLASS
72.7
69.3
62
60 SFT RFT Avg Reward Reward Q-value
Figure 4. Self-training baselines. The three methods marked with diagonal stripes leverage diffcrent process reward modeling based on the same exploration trees constructed in Stage 2 guide self- training data generation.
5.3. Fewer Annotations
In many real-world applications, collecting large amounts of expert-annotatee data is both time-consuming and costly, To evaluate the effectiveness of our approach under such constraints, designed this setup with fewer annotations to test how quickly the agents adapt to new environments in this section. We extract 1000 trajectories as subset from the original 1938 trajectories. Under this setup, all baselines can only conduct behavior cloning with access to the SFT dataset of 1K trajectories. After that, baselines like RFT, ETO and QLASS which involve generation can explore 1938 tasks. The performance comparison is listed in Table 3. We can observe that QLASS outperforms other methods trained on both the full WebShop training set and WebShop-1000 subset. This highlights the robustness of our method, especially its potential scenarios with scarce expert data. While other methods like RFT and SFT show a significant drop in performance, QLASS remains effective, demonstrating the advantage of Q-guided generation for data selection even in annotation-limited environments.
Table 3. Average reward comparison on WehShop with 1000 anno- tated trajectories for behavior cloning. The best result bolded, and the second- best result is underlined.
Method
WebShop
WebShop-1000
SFT
63.1
21.7
ETO
67.4
66.7
Best-of-N
67.9
47.1
QLASS
70.3
67.3
mance. We mainly experiment with three approaches of con- structing process rewards for each intermediate nodes on the exploration trees: O-value (ours) is to estimate v-value for each state-action pair (i.e. each tree node except for root node) using Equation 7; Avg reward (Wang et al., 2023) computes the averaged the final rewards; Reward (Yuan et al., 2024) directly treats the final outcome reward and backpropagates it as the process reward for each intermedi- ate step. In addition to the self-impun seff-improvement at inference time, we also evaluate the effectiveness of QLASS for se- lecting high-quality data for sell-training. We train the base agent on the SFT dataset in addition the Q-guided gen- erated data. Results are visualized in Figure 4. We observe that QLASS achieves the highest among all the self-training baselines, compared with RFT which leverages oracle out- come rewards to filter high-quality trajectories and baselines guided by other process reward models such as Rewa rd and Avg Reward
5.4. Case Study
We pick out an example from ALFWorld in Figure 5 to showcase the difference between basclines and our models. The SFT agent correctly picks up the lettuce, cools it using the fridge, and places it on the countertop in the beginning. However, it continues performing redundant actions after- ward, such as repeatedly opening and closing the fridge. The environment responds with "Nothing happened" until the agent exhausts its step limit, failing to recognize the task is already complete. By contrast, the QLASS uses stepwise reward mechanism. Once it has cooled the lettuce and placed it on countertop. it gains no further reward from reopening the fridge or replacing the lettuce. Conse- quently, the QLASS avoids futile actions and terminates as soon as the goal is satisfied, successfully completing the task in fewer steps. We can observe that Q-value gradually grows with the number of steps, but suddenly converges to an extremely high or low value at Action 5, indicating it is a key step that differentiates success and failure, where QLASS assigns "cool lettuce with fridge 1" with very high Q-value, only gives 0.10 to "close fridge 1 that leads to nonsense behavior.
Ablation on Process Reward Modeling, We train three dif- ferent process reward models guiding trajectory generation for self- telf-nraining. Self-training results in Figure 4. From Figure 4, we can observe that Q-value ue utilized by our QLASS yields the best performance, while the one using Avg reward is slightly better than the one directly using Reward, indicating the effectiveness of using Q-value to model process reward.
8

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Goal: put cool lettuce countertop.
Action1: countertop
SFT
Action1: go to countertop (q=0.25)
LAASS
Observation: sees lettuce emong other items.
Observation' sees lettuce 1.
Action2: take lettuce from countertop 3
Action2: take lettuce 1 from countertop (q=0.41)
Observation picks up lettuce
Observation: picks up lettuce 1.
Action5
Action3: fridge
Action3: go to fridge 1 (q=0, close fridge 1
Observation: fridge 1 closed.
Observation: fridge is closed.
(q=0.10)
Action4: open fridge
Action4: open fridge (q+0.71)
cool lettuce 1 with
fridge (g=0.89)
Observation: fridge is now open.
Observation: fridge is now open.
fridge
Action5:
with fridge (g=0.89)
Observction: you closed fridge 1.
Observation "You cool the lettuce 1 using the fridge 1.'
Actions: open fridge
Action6: go to countertop (q=0.95)
Observation: fridge is now open. Action7: close fridge
Observation: sees butterknife 1.
Action7: put lettuce
countertop
Observation closed fridge 1. Repeatedly until hit max of turns
Observation: "You put the lettuce 1 on countertop 1," Task Completed Successfully.
Figure 5. One example on the ALFWorld, the right QLASS and left the SFT baseline.
5.5. Ablations Across Different Base Policy Models
multi-turn tasks without much human annotation efforts.
To validate the robustness of our method across different model architectures, we also conduct experiments on large base model: 1-133-2-13B. As shown in Table 4, QLASS still outperforms the baseline reported in Song et al. (2024) on the World benchmark.
From an ethical and societal standpoint, more capable and autonomous language agents raise considerations regarding misinformation, biases, and potential misuse. In particu- lar, any method that enhances an agent's ability explore and generate content scale should be paired with careful oversight and robust filtering mechanisms. While our ap- proach focuses on improving performance through better trajectory evaluation rather than content manipulation, we acknowledge that improved capabilities can be leveraged for harmful or deceptive purposes if not properly governed.
6. Conclusion
In this paper, we introduce QLASS, a novel approach that enhances open-source language agents at inference time by integrating evalue-based process guidance. By model- ing the Q-value at each intermediate step during planning, our method offers step-wise feedback that surpasses the limitations of outcome-based reward models, particularly in complex, Long-horizon tasks. Through extensive exper- iments, we have demonstrated that QLASS significantly improves the language agent to search more intelligently. Moreover, our method demonstrates strong performance even in scenarios with limited annotated data used for be- havior cloning. This work paves the way for more efficient and scalable self-improvement techniques in language mod- els, enabling them to tackle complex tasks with reduced reliance on human annotations.
A Acknowledgement
This work is supported by DARPA ANSR program FA8750- 23-2-0004, DARPA ECOLE Program HR00112390060,
ONR grant N00014--3-1-27880, NSF 2211557, NSF 2119643, NSF 2303037, NSF 2312501, SRC JUMP 2.0
Center, Amazon Research Awards, and Snapchat Gifts.
References
Bansal, H., Lin, Z., Xie, T., Zong, Z., Yarom, M., Bitton, Y.. Jiang, C., Sun, Y., Chang, K.-W., and Grover, A. Videophy: Evaluating physical commonsense for video generation. arXiv preprint arXiv:2406.03520, 2024.
Impact Statement
Bellman, R. E. and Dreyfus, S. E. Applied dynamic programming, volume 2050. Princeton university press, 2015.
Our work aims to improve the inference-time search for open language agents by learning Q-based process reward which reduces the reliance extensive human annotations. By leveraging self-generated data and more efficient step- wise evaluations, we hope to lower the barrier to developing advanced language agents for tasks where data is scarce.
Chen, B., Shu, C., Shareghi, E., Collier, N., Narasimhan, K., and Yao, S. Fireact: Toward language agent fine-tuning. arXiv preprint arXiv:2310.0591 2023.
This has the potential to broaden access to high-quality AI- driven solutions, enabling researchers, even those with lim- ited resources-te to deploy models that can handle complex,
Chen, Z., Zhao, Z., Zhu, Z., Zhang, R., Li, X., Raj. B., and Yao, AutoPRM: Automating procedural super-

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
vision for multi-step reasoning via controllable question decomposition. In Duh, K., Gomez, H., and Bethard, S. (eds.), Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human I Language Technologies (Volume 1: Long Papers), pp. 1346-1362, Mexico City, Mexico, June 2024. Association for Computational Linguistics. URL https: letacclllnn 73.
Putta, P., Mills, E., Garg, N., Motwani, S., Finn, C., Garg, D., and Rafailov, R. Agent q: Advanced reasoning and learning for autonomous ai agents. arXiv preprint arXiv:2408. 00000007999.. 2024.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. Direct preference optimiza- tion: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2024.
doi: 10.186653/1120224mmmcc //aclanthology. wttp:/looooorgg/2/2//////// wwt.orrg//2//
Chen, Z., Chen, D., Sun, R., Liu, W., and Gan, Scaling autonomous agents via automatic reward modeling and planning. arXiv preprint arXiv:2502. 12130, 2025.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. 2017.
arXiv preprint
Dou, Z.-Y., Yang, C.-F., Wu, X., Chang, K.W.,, and Peng. N. Reflection-reinforcee self-training for language agents. arXiv preprint arXiv:2406.01 0149,, 2024.
Setlur, A., Garg, S., Geng, X., Garg, N., Smith, V., and Kumar, A. RI on incorrect synthetic data scales the efficiency of Ilm math reasoning by eight-fold. arXiv preprint 1itii:2440.1153522 2024.
Feng, X., Wan, Z., Wen, M., Wen, Y., Zhang, W., and Wang, J. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17179 2023.
Shen, Y., Song, K., Tan, X., Li, D., Lu, W., and Zhuang, Y. Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face. Advances Neural Information Processing Systems, 36, 2024.
Gulcehre, C., Paine, T. L.,, Srinivasan, S., Konyushkova, K., Weerts, L.. Sharma, A., Siddhant, A., Ahern, A., Wang, M.. Gu, C., Macherey, W., Doucet, A., Firat, O., and de Freitas, N. Reinforced self-training (rest) for language modeling, 2023. URL wwtthhtt////rtttt org/ abs/ 2308. 08998.
Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K. R., and Yao, S. Reflexion: language agents with verbal reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL htttps://openree//// id=vAE1hFcKWG.
net forum?
Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q.. Ma, S., Wang, P., Bi, X., al. Deepseek-rl: In- centivizing reasoning capability in ilms via reinforcement learning. arXiv preprint arXiv:2501.1299
Shridhar, M., Yuan, X., Cote, M.-A., Bisk, Y., Trischler, A., and Hausknecht, M. {ALFW)orld: Aligning text and embodied environments for interactive learning. In International Conference on Learning Representations, 2021.
2025.
Hosseini, A., Yuan, X., Malkin, N., Courville, A., Sor- doni, A., and Agarwal, R. V-star: Training verifiers for self-taught reasoners. arXiv preprint arXiv:2402.06457 2024.
Singh, A., Co-Reyes, D., Agarwal, R., Anand, A., Patil, P., Liu, P. J., Harrison, J., Lee, J., Xu, K., Parisi, A., et al. Beyond human data: Scaling self-training for problem-solving with language models. arXiv preprint arXiv:2312.06585. 2023.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., ineruu. 2018. URL Siaagrr_ffllss/sppp////////ee cc cc/paper cc/paper_filess/eeeeeeeeeeeeeeee d3b1 229116600066a2622277722231111122 pdf.
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling 11m test- time compute optimally can be more effective than scal- ing model parameters. arXiv preprint MxXiv22408.03//1 2024.
Song, Y., Xiong, W., Zhu, D., Wu, W., Qian, H., Song, M., Huang, H., Li, C., Wang, K., Yao, R., et al. Restgpt: Connecting large language models with real-world restful apis. arXiv preprint (XXi:2330600662. 2023.
Koh, J. Y., McAleer, S., Fried, D., and Salakhutdinov, R. Tree search for language model agents. arXiv preprint atXiv:2407.01476 2024.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. arXiv preprint arXiv:2305.2003 2023.
Song, Y., Yin. D., Yue, X., Huang, J., Li. S., and Lin, B. Y. trajectory optimization of LLM agents. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of
Trial and error: Exploration-
10

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
the Association for Computational Linguisties (Volume 1: Long Papers), pp- 7584-7600, Bangkok, Thailand, August 2024. Association for Computational Linguis- tics. URL https:/ htt///aaannntolooorrr/ro/o/ orgp2044 acl - bel-long long.o0... .00.
Xu, H., Lin, Z., Zhou, J., Zheng, Y., and Yang. Z. A uni- versal discriminator for zero-shot generalization. arXiv preprint arXiv:2211.0885 2022.
Yao, S., Chen, H., Yang. J., and Narasimhan, K. Webshop: Towards scalable real-world web inter- action with grounded language agents. Advances in Neural Information Processing Systems, 35:20744-
Sutton, R. S. Learning to predict by the methods of temporal differences. Machine learning, 3:9-44, 1988.
Team, K., Du, A., Gao, B., Xing. B., Jiang, C., Chen, C., Li, C., Xiao, C., Du, C., Liao, C., et al. Kimi k1. 5: Scaling reinforcement learning with Ilms, arXiv preprint arXiv:2501.12599, 2025.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, Y. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023.
Uesato, J., Kushman, N., Kumar, R., Song, F., Siegel, N., Wang, L.,, Creswell, A., Irving, G., and Higgins, Solv- ing math word problems with process- and outcome- based feedback, 2022.
Yin, D., Brahman, F., Ravichander, A., Chandu, K., Chang, K.-., Choi, Y., and Lin, B. Y. Agent lumos: Unified and modular training for open-source language agents. In Ku, I.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 12380-12403, Bangkok, Thailand, August 2024. Asso- ciation for Computational Linguistics. URL https: / //aclanthology. org/2024/4222 acl- aol-llng......... 670.
Wang, C., Deng, Y., Lv, Z., Yan, S., and Bo, A. Q*: Im- proving multi-step reasoning for Ilms with deliberative planning. arXiv preprint arXiv:2406. 142.:24466....,,,.. 2024.
Wang, P., Li, I.., Shao, 7., Xu, R., Dai, D., Li, Y., Chen, D., Wu, Y., and Sui, Z. Math-shepherd: A label-free step-by-step verifier for Ilms in mathematical reasoning. arXiv preprint a12iv:2312.08995, 2023.
Yuan, L.,, Li, W., Chen, H., Cui, G., Ding, N., Zhang, K., Zhou, B., Liu, Z., and Peng, H. Free process rewards without process labels. arXiv preprint arXiv:2412.01981, 2024.
Wang, R., Jansen, P., Côté, M.-A., and Ammanabrolu, P. ScienceWorld: Is your agent smarter than a 5th grader? In Goldberg. Y., Kozareva, Z., and Zhang, Y. (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 11279- 11298, Abu Dhabi, United Arab Emirates, December 2022a. Association for Computational Linguistics. doi: URL https://
Yuan, 2., Yuan, H., Li, C.,, Dong, G., Lu, K., Tan, C., Zhou, C., and Zhou, J. Scaling relationship on learning math- ematical reasoning with large language models. arXiv preprint arXiv22308.01825, 2023.
Zhai, Y. Yang, T. Xu, K., Dawei, F. Yang, C., Ding, B., and Wang, H. Enhancing decision-making for Ilm agents via step-level q-value models. arXiv preprint uxiv:2409.093455 2024.
10. 12.16663/41222222emmmmmmiia aclanthology. org/ 22t///2222..2 emn pallppmmaa main. 775.
Wang, Z., Lin, Z., Liu, P., ZHeng, G., Wen, J., Chen, X., Chen, Y., and Yang, Z. Learning to detect noisy labels using model-based features. arXiv preprint arXiv:2212.13767, 2022b.
Zhang, D., Zhoubian, S., Hu, Z.,, Yue, Y., Dong, Y., and Tang, J. ReST-MCTS*: LLM self-training via process reward guided tree search. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:::t///....... /ttpss:////peeeeeereeee net/ forum? id id=8raFOqEud5.
Watkins, C. J. and Dayan, P. Q-learnin. Machine learning, 2:279-292, 1992.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. Zhou, D., et al. Chain-of-thouuge prompting elicits reasoning in large language models. Advances in neural information processing systems, 0124824-248877 2022.
Zhou, A., Yan, K., Shlapentokh- -opppnntokh--RRhmma M., Wang, H., and Wang, Y.-X. Language agent tree search uni- fies reasoning, acting, and planning in language mod- cls. In Forty-first International Conference on Machine Learning, 2024. URL https: http///pppneeeeeeeeeeee net/ forum?ides www.iddwwwwwWWB.....
Wu, X., Lin, Z., Zhao, S., Wu, T.-L., Lu, P., Peng, N., and Chang, K.-W. Vdebugger: Harnessing execution feedback for debugging visual programs. arXiv preprint arXiv:2406.1 13444, 2024.

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
A. Appendix
A.I. Discussion
Why supervised train the offline QNet using LLM as the backbone instead of directly using deep Q-learning? Directly applying deep Q-learning (Watkins & Dayan, 1992) to language agents face critical challenges. First, the action space (all possible text outputs) is unbounded and orders of magnitude larger than typical RL environments (e.g.. Atari's s 18 discrete actions). Standard exploration strategies like e-greedy fail because random text sampling rarely yields meaningful rewards or trajectories. Second, language tasks often involve sparse rewards, destabilizing Q-learnin'ss ' reliance on frequent reward signals. Pure online Q-learning would suffer from high gradient variance and require infeasible exploration budgets.
Initializing the value function model from a well-pretrained large foundation model can encode rich linguistic and reasoning priors, as well as world commonsense knowledge (Bansal et al., 2024; Song et al., 2024; Xu et al., 2022; Wang et al., 2023). So we initialize our QNet with the LLM trained in the agent environment to embrace both knowledge during pretraining and agent specific capabilities, thus boosting the adaption to the long-term value modeling,
A.2. Experimental details
A.2.1. DATASETS
We follow the setup of ETO (Song et al., 2024) to use the three agent tasks for our experiments.
(a) WebShop is online shopping environment. The available action types for agents include search(keywords) and click/valueJ. The agent is instructed to complete the task with RcAct(Yao et al., 2023)-style response. The instruction is specified in Figure 6.
(b) WoFlo (Shridhar et al., 2021) consists of interactive TextWorld environments paralleling the embodied worlds. In this sctup, agents must explore and complete complex household tasks. The ALFWorld dataset includes both seen and unseen evaluation sets. The seen set tests in-distribution generalization, while the unseen set evaluates diitt--distribution generalization, featuring entirely new task instances for the agents solve.
(c) SciWorld (Wang et al., 2022a) is text-based virtual platform designed around conducting basic scientific experiments across ten task categories, such as thermodynamies and electrical circuits. Agents engage in embodied, interactive environments to grasp scientific concepts through practical tasks. Each task in ScienceWon includes optional subgoals, with the final reward calculated based on the achievement of these subgoals.
We have summarize the statistics of SFT datasets for behavior cloning on all the environments in the main body. Note that the default reward from the environment is zero for the intermediate step before terminal. For self-generation and tree construction, set the maximum step 5 in WehShop and 18 in ALFWorld and SeiWorld. For inference, we set the maximum step 5 in WebShop and 40 in ALFWorld and SeiWorld. The instruction templates are displayed in Figure 6, 7 and 8.
A.2.2. QNET
Model Architecture. Our QNet is designed by sharing the backbone of the Large Language Model (LLM) and appending a value head to predict Q-values. Specifically, we utilize a pre-trained LLM, denoted as LLMg, which serves as the foundational model for encoding input sequences. The value head a Multi-Layer Perceptron (MLP) that takes the hidden states from the LLM and outputs scalar Q-value predictions.
Formally, given input sequence of tokens (I1,42, ..,) representing state-action pair, the LLM produces hidden states h = (h,, h,,,...,,.... ):
h = (x),
(9)
where h2 E Rd represents the hidden state at time step 4, and d is the hidden size of the LLM. The value head MLP processes each hidden state h to predict the corresponding Q-value q.:
q (h+)
(10)
12

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Algorithm 3 Q-value Estimation
Input: reasoning tree with a root node U, discount factor y
Procedure Update Q Values(N)
if = = Ø then
return
L-Laff nodes do not update
end
for node Nohild in N.C do Update_Q. Q- Values(NVemuu) end for N.q N.r + max Naw E. c. -9)
Reecursvvely update child nodes first
> Update Q-value after all children updated
End Procedure
U V-luusss(U)
b Start the update process from the root
Qmin = MinNET (N.q)
Qmax maxNe7 (N.4) for node N in do
N.q Qua Qui
Qui
Apply min-max normalization
end for
return the reasoning tree T with estimated Q-value of each node
where q. E IR is the predicted Q-value at time step t, and & denotes the parameters of the MLP.
The MLP consists of multiple layers with ReLU activations, culminating in a linear layer that outputs scalar Q-value. This design allows the model to capture complex patterns the hidden representations and map them to accurate Q-value estimates.
Training Objective. Given an explored trajectory (x), (2,,, ........ In,) with an associated target Q-value q, we train the QNet by minimizing the Mean Squared Error (MSE) loss between the predicted Q-values and the target Q-value g each time step:
((0,
Σ (1r 9)² 1=1
(1))
7
By minimizing this loss, we encourage the QNet to produce consistent Q-value estimations across the sequence that align with the target Q-value This training objective emphasizes accurate Q-value predictions at each token, reinforcing the model's ability to assess the long-term value of actions throughout the trajectory.
Implementation Details. practice, we implement the value head an MLP with two hidden layers of size 1024 and ReLU activation functions.
The entire model, including the LLM and the value head, operates in 6 precision to optimize memory usage without sacrificing performance. The LLM backbone remains frozen or fine-tuned depending on the specific experimental setup, allowing us to leverage pre-trained language representations while focusing on learning accurate Q-value predictions through the value head. By integrating the value head with the LLM, our QNet effectively combines language understanding with reinforcement learning principles, enabling the agent to make informed decisions based on both linguistic context and estimated future rewards.
A.3. Algorithms
1. PSEUDOCODE OF Q- VALUE DISTILLATION
In this section, we provide the pseudocode of how we distill the Q-value from an exploration tree Algorithm
13

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Algorithm 4 Q-guided Generation
Input: LLM agent Te. given task description u, an action set A, containing M candidates at step t, a trained QNet 2g. sampled trajectory number N, max trajectory length L
traj traj_candidates for = 1 to N do Initialize state 8; <- [u] for t to L do
Collect a set of action candidates A, + Sample a ~ To(a 8;) for M times
dg + argmax A. 2 (8;,0) a)
Seeecc the best action with max Q-value Update state with executed action and new observation
Take action a, and receive new observation or from environment
S; 8; + [a,, or]
if s; is the final state then
break end if end for traj wel..caddddte..aan. cappddddaess..ppenn((ss)
> Exit loop if stop condition is met
end for Select the best trajectory s with best final reward s.reward from traj.candidates
A.3.2. Q-GUIDED GENERATION
In this section, present the pseudocode of Q-guided generation in Algorithm 4, which is critical component of our framework.
Perturbation augmented generation. In WebShop, due to the limited diversity of sampled actions, we introduce augmenting action diversity with perturbation during this stage, which is realized by prompting GPT-3.5- Turbo to paraphrase the task description. This utilization of perturbation enables us to inject more variability into the prompts that guide action selection, substantially enriching the range and relevance of possible actions. Such enhanced prompts help prepare the model to handle more diverse and unforeseen situations effectively. We augmented the action diversity in all inference-basee algorithms when evaluating in WebShop for fair comparison. Noted that it costs too much on ALFWorld and SciWorld, so we only conduct perturbation on the WebShop.
We introduce our implementation details and examples as follows. We use GPT-3.5-Turee to perturb the task descriptions using the prompt "Paraphrase the text: {task description]" ", We show an illustrative example on a WebShop task in Figure 9,
A.4. Hyper-parameters
We summarize the hyper-parameters used across both all stages of QLASS in this section. The hyper-parameters leveraged in behavior cloning and self-training is in Table 5. Training QNet shares all the same hyperparameters, except that the number of training epochs is set 2.
14

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Table S. Hyperparameters used in QLASS.
Hyperparameter
Value
Batch size
64
Number of training epochs
Weight decay
0.0
Warmup ratio
0.03
Learning rate
le-5
LR scheduler type
Cosine
Logging steps
Model max length
4096
Discount factor y
0.9
Maximum expansion depth D on WebShop
Maximum expansion depth D on SciWorld
6
Maximum expansion depth D on ALFWorld
8
Action candidate set size M for inference
2
Sampled trajectory number N for self-training Exploration temperature
0.7
WebShop Instruction
You are web shopping. will give you instructions about what to do. You have to follow the instructions.
Every round will give you an observation and list of available actions, you have to respond an action based on the state and instruction.
You can use search action if search is available. You can click one of the buttons in clickables. An action should be of the following structure: search[keywords]
click[value]
the action not valid, perform nothing. Keywords in search are up to you, but the value in click must be value in the list of available actions.
Remember that your keywords in search should be carefully designed.
Your response should use the following format: Thought: think
Action: click[ click[somethin]
Figure 6. The instruction prompt provided to language agent on WehShop.
15

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
SciWorld Instruction
You helpful assistant to some experiment an environment.
In the environment, there are several rooms: kitchen, foundry, warkshop, bathroom, living You should explore the environment and find the items you need complete the experiment.
greenhouse,
way
teleport any room one step.
All containers in the environment have already been opened, you can directly get items containers.
The aveilable actions open open container dose OBU: dase container activate OB): activete device
deectivate OB); deactivate a device
connect OBJ to OBI: connect electrical components
components
use 06J (on OBJ use a device//tem Ieem
look around: describe the current room examine OBI: describe an object detail
look at OBI: describe containe''s contents book
mowe CBI to OBI: move an object to container
pick OBI:
object the inventory
pour into OBI: pour liquid container
mix OBI: cherriaaly mix container
teleport
teleport
focus on OBI: signal intent an task object
wall: action for 10 steps
waltt: tack no action for step
the
Task Description:
Your task to bail lead For campounds without beil ng point, combusting the substance substance. Then,
acceptable, change its state motter.
Figure instruction prompt provided to language agent on SciWorld.
ALFWorld Instruction
Imagine you intelligent apent househald envtronment and your target is to perform actions complete the task goal. the beginning interactions, ourrent environment your goal accompl
household
will be the detailed ailedd descr iptionn the
For each of your turn, you will be given the observation the lest turn. You should first plan your action in this turn, Your output mus strictly fallow this format:" "Thughh your thoughts. |nAction: your next action".
think
And output your
The available actions are:
to (recep)
task [ob)] from (recep)
3. put [obi] In/on (recep)
open (recep)
dosee (recep)
toggle (obi) [recep]
deen (oog] with (recep)
B. heat (obi) with (recep)
(obji (recep)
where (obj) and frecep) correspord to objects and receptacles.
Mite your each the enwironment give immediate feedbbckk based which you plan your next steps. envrionment output "Nothing happened", means the previous action invalid and you should try more options.
response use the following format:
Thought: syour thoughts> Action: syour next actiono
Now,
is the
You are in the midcle af roam. Looking quickly around you, see cabinet cabinet countertop 3, countertop 2, countertop 1, drawer 3, drawer 2, drawer fridge garbagecan
cabinet
shelf 3, shelf staveburner 4, stoveburer3. 3, stavebumer 2, stoveburer 1, Your task to: put clean knife countertap.
sinkbasin
Figure instruction prompt provided to language agent on ALFWorld.
16

---

QLASS: Boosting Language Agent Inference via Q-Guided Stepwise Search
Perturbation
Paraphrase the task: need a long lasting 6.76 oz bottle of l'eau d'issey, and price lower than 100.00 dollars
I'm looking for a 6.76 fl oz bottle of L'eau D'Issey that lasts long time and costs less than $100.
need a durable 6.76 ounce bottle of L'eau D'Issey, with a price under $100.
am searching for a long-lasting 6.76 fluid ounce l'eau D'Issey perfume for less than 100 dollars.
Figure 9. An illustrative example on task perturbation.
17


Reviews:
[{"review_id": "l3WCvdsdJe", "reviewer": "Reviewer_dLz3", "summary": "The paper proposes an LLM self-improvement recipe for tasks where there is a (possibly sparse) external verification signal, inspired by the Q-learning algorithm for Markov Decision Processes. Experiments conducted on three domains (ALFWorld, SciWorld and WebShop) show that the proposed recipe can yield performance improvements for LLM-as-agents, and scales well with increased inference-time compute budgets.\n\n[Post rebuttal update] The additional experiments and details submitted by the authors in their rebuttal address most of my questions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "The main claims are:\n1. The proposed approach for constructing reasoning trees and computing Q-values can produce a good quality dataset for LLM self-improvement.\n2. Using predicted Q-values to guide LLM generation can yield a good policy for agent tasks.\n3. The general QLASS pipeline produces good performance at low cost for agent tasks, relative to other baselines.\n\nThe evidence for (1) can be substantially improved with some additional analysis:\n- For a given cost budget (w.r.t. number of tokens or LLM calls or latency) there is a tradeoff between trying a task for longer (i.e. higher T; trajectory length) vs. backing off and exploring other nodes as in Algorithm 2. By carefully varying T, D (reasoning tree max_depth) and W (reasoning tree max_branching) we can empirically understand this tradeoff.\n- The paper conjectures that outcome reward models yield inferior policy learning results than process reward models because sometimes the resulting policy may be inefficient. An ablation experiment with varying gamma (discount factor) would be a great way to verify or falsify this conjecture -- does gamma=1 allow inefficient policies and as gamma < 1 the learned policies become more timestep-efficient?\n- Can we still produce good Q-value datasets after multiple steps of LLM self-improvement? An experiment where Stages 2 and 3 of Algorithm 1 are re-iterated a few times would shed light on this question.\n\nThe evidence for (2) seems adequate. Figure 3 can be made more convincing by including other inference-compute scaling techniques.\n\nThe evidence for (3) is missing some important baselines: (even allowing for excluding the ones discussed in Appendix A.1).\nFor instance, from the paper's citations & related work -- process reward models learned via random rollouts (e.g. Uesato'22, Lightman'23, Wang'23, Chen'24); learned outcome reward models (Snell'24, Wang'24a, Shinn'23); MCTS approaches to building the \"reasoning tree\" (e.g. TS-LLM Feng'23, ReST-MCTS* Zhang'24). A representative approach from each of these 3 threads of research are important baselines to compare.", "methods_and_evaluation_criteria": "The benchmarks used (WebShop, Alfworld, SciWorld) are well-motivated. Evaluation metrics such as task success rate and token counts are also reasonable.\n\nEvaluating the costs of the proposed approach vs. baselines needs clarification or perhaps a more rigorous approach.\nQLASS has a dataset generation step, followed by Q-Net training, and followed by using Q-Net during inference.\nThe only costs reported are in Figure 3 which only reports the cost of Q-Net during inference.\nThe other costs are important to contextualize.", "theoretical_claims": "The paper does not make any theoretical claims.", "experimental_designs_or_analyses": "How were the hyper-parameters for QLASS (e.g. expansion depth D) selected across the different task domains? Was it by monitoring performance on the test set? If so, there may be unfair bias against the other tested baselines. This is an important missing detail that should be clarified for a rigorous experimental setup.", "relation_to_broader_scientific_literature": "The paper adequately describes the related works on self-improvement recipes for LLMs, using LLMs as agents, and using process reward models to derive fine-tuning reward signals on intermediate steps of agent tasks.", "essential_references_not_discussed": "N.A.", "other_strengths_and_weaknesses": "The biggest strength of the paper is the very strong empirical performance of QLASS across the three tested domains.", "other_comments_or_suggestions": "Section 3: Mention the MDP problem setting that the Q-learning algorithm is designed for (because it is not yet apparent that the tasks tackled later in the paper are modeled well by an MDP).\n\nNotation of N has a conflict. N is the number of expert trajectories during SFT; and also denotes a node in the exploration tree.\n\nAppendix A.2.2. Notation clash between (x1 ... xn) representing tokens being input to the LLM vs. the subscript representing the time-step of the task trajectory (each step of the task trajectory will have a sequence of tokens right?)\n\nSection 4.4: the second paragraph is superfluous and can be cut. Algorithm 2 should be in the main paper instead.\n\nAlgorithm 2: \"Get a new branch b constructed on \\tau\" this is not described adequately in the paper. When a trajectory is sampled from a state, is each call to the LLM made into a node? And the state corresponding to the node is the concatenation of all previous inputs and outputs of the LLM from the root node to that node?\nLine numbers are not printed, so \"repeat function in Line 5-12\" is hard to interpret; perhaps refactor into an Algo block and a Subroutine block.\n\nMain paper Section 5.1 should mention the perturbation augmentation done for WebShop. Why was the cost for that step high on SciWorld/AlfWorld (since it was just about paraphrasing the task descriptions)?\n\nAlgorithm 3: When describing Q-value estimation in the main paper, mention that the Q-values are normalized to be in [0,1].", "questions_for_authors": "Please see questions in the other review responses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mwYrdUNIPF", "reviewer": "Reviewer_hiva", "summary": "This paper proposes QLASS, a method for Q-value estimation in process reward modeling, providing stepwise guidance for language agents. QLASS consists of four main stages: SFT to train the LLM agent, exploration tree construction, QNet training and Q-guided generation. Compared to multiple baselines, QLASS achieves significant performance improvements across various tasks with fewer training data, demonstrating its efficiency and effectiveness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer hiva,\n\nWe sincerely thank you for the constructive suggestions and positive feedback. We will address your concerns below.\n\n> W1: Lack of experiments of applying QLASS to different LLM agents\n\nWe understand that the reviewer encourages us to experiment on diverse LLM agents to validate the effectiveness of QLASS. In Section 5.5, we experimented with base agents with different model sizes to investigate the effectiveness of QLASS on different LLM agents. Additionally, we experimented on applying QLASS on GPT-4o (stated in Q3 below). We also summarize the results below.\n\n| Base LLM | Method | SciWorld-seen | SciWorld-unseen |\n|----------------|--------|---------------|-----------------|\n| Llama-2-7B     | SFT    | 67.4          | 53.0            |\n| Llama-2-7B     | ETO    | 73.8          | 65.0            |\n| Llama-2-7B     | **QLASS**  | **75.3**          | **66.4**            |\n| Llama-2-13B    | SFT    | 68.1          | 57.6            |\n| Llama-2-13B    | ETO    | 71.4          | 68.6            |\n| Llama-2-13B    | **QLASS**  | **72.7**          | **69.3**            |\n\nFrom the table above, we can see that QLASS can effectively enhance the performance significantly across diverse LLM agents.\n\n\n> W2: Lack of comparison with other process reward modeling methods\n\nTo validate the effectiveness of QLASS compared with other PRM, we compared our Q-value based method with Avg reward[2] and Reward[3]. Avg reward computes the averaged final rewards; Reward directly treats the final outcome reward and backpropagates it as the process reward for each intermediate step. In addition to the self-improvement at inference time. More details are included in Section 5.2, L370-384. We leverage Q-value, Avg reward, Reward to guide agent self-training. \n\nResults are in the table below.\n| Q-value | Avg reward | Reward |\n|-------------|-------------|-------------|\n| 66.4 | 65.4 | 64.7 |\n\nWe can observe that Q-value achieves the highest among all the PRM baselines, demonstrating the effectiveness of QLASS compared with other process reward models.\n\n> W3: Lack of cross-domain generalization experiments.\n\nIn our current setup, we experimented on unseen test sets on SciWorld and ALFWorld in Table 2, which is a commonly adopted setup to test the out-of-distribution generalization ability of LLM agents in prior works[1].\n\nAlso, we respectfully clarify that the tasks and action spaces explored in our experiments, such as WebShop (a shopping task) and ALFWorld (a navigation task), involve distinctly different knowledge bases with minimal overlap. Consequently, it is impractical to apply the QNet trained on WebShop to enhance performance on ALFWorld due to these fundamental differences. We acknowledge the importance of this clarification and will include this point in the revised version of our paper.\n\n> Q1: The cross-domain generalization ability of QLASS\n\nWe have discussed this question in W3 and we kindly direct the reviewer to the discussion in W3.\n\n> Q2: How the inherent performance of the backbone affects the quality of Q-value predictions\n\nIn practice, we found that QNet, when initialized by sharing the backbone and weights from the agent's LLM, performs slightly better than when trained from scratch.\nWe previously employed llama3.2 3B as the base model for both the agent model and QNet. However, llama3.2 3B performs poorly in our multi-turn, interactive agent tasks. It also struggled to provide effective process rewards during inference time. These shortcomings may stem from the model's capacity limitations, as the 3B size may be inadequate for handling the complexity required for solving these specific tasks.\n\n\n> Q3: Applying QNet to different LLM agents\n\nWe have experiments showing that our method can also work on 13B LLM in Table4. Also, \nwe add additional experiments by applying the trained 7B QNet to GPT4o on the Webshop. Noted that GPT-4o is not specifically trained on agent tasks so the 7B results after behavior cloning can perform better.\n\n| Method | Performance|\n|-------------|-------------|\n| GPT-4o | 54.5 |\n| GPT-4o w/ QLASS | 56.2 |\n\n> Q4: Comparison with other process reward models\n\nWe include detailed discussion on comparison with other PRMs in W2.\n\nWe hope that our answers can resolve your concerns. \n\n\n[1] Song, Y., Yin, D., Yue, X., et al. (2024). Trial and Error: Exploration-Based Trajectory Optimization for LLM Agents.\n\n\n[2] Wang, P., Li, L., Shao, Z., et al. (2023). Math-shepherd: A label-free step-by-step verifier for LLMs in mathematical reasoning.\n\n\n[3] Yuan, L., Li, W., Chen, H., et al. (2024). Free process rewards without process labels.", "claims_and_evidence": "The paper claims that QLASS enhances LLM-based agents' decision-making performance in complex interactive tasks and enables self-improvement under limited supervision. These claims are well-supported by experimental results, which show that QLASS outperforms several baselines across multiple benchmarks.", "methods_and_evaluation_criteria": "QLASS utilizes Q-value-based stepwise guidance to optimize agent behavior, which is a well-justified approach. The construction of QNet appears to be a key advantage of this method compared to others, however, the evaluation does not assess QNet in combination with multiple different LLM-based agents, which makes it difficult to fully demonstrate the superiority of the approach.", "theoretical_claims": "The paper employs Q-learning for process reward modeling, which is theoretically sound.", "experimental_designs_or_analyses": "The paper provides a comprehensive comparison with various agent training paradigms, effectively demonstrating QLASS's advantages. However, the absence of comparisons with other process reward modeling methods weakens the argument that QLASS is the best approach for process reward estimation.", "relation_to_broader_scientific_literature": "The key contributions of this paper build upon and extend multiple areas of prior research, including LLM-based agent reasoning and process reward modeling.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths\n\n1. QLASS introduces an innovative stepwise search strategy, effectively addressing the issue of suboptimal decision-making caused by outcome-based rewards.\n\n2. The paper conducts thorough experiments across multiple complex interactive environments, demonstrating QLASS's effectiveness and robustness.\n\n3. QLASS maintains strong performance even with reduced annotated data, making it valuable for real-world applications where labeled data are scarce.\n\nWeaknesses\n\n1. QNet's effectiveness is not tested with multiple LLM-based agents, making it unclear whether its benefits extend beyond the specific agent used in the experiments.\n\n2. The paper does not compare QLASS with alternative process reward modeling techniques.\n\n3. Lack of cross-domain generalization experiments.", "other_comments_or_suggestions": "The visual consistency of figures could be improved to enhance clarity and readability. Unifying the style across diagrams would make the presentation more polished.", "questions_for_authors": "1. I am curious about the generalization ability of QLASS. If the model is trained with SFT and QNet only on WebShop data, can it still achieve performance improvements on the ALFWorld test set?\n\n2. Since QNet is designed by sharing the backbone of the LLM, I would like to know whether the inherent performance of the backbone affects the quality of Q-value predictions.\n\n3. Could you demonstrate the effectiveness of Q-guided generation by applying the trained QNet to other LLM agents?\n\n4. How does a QNet constructed using QLASS compare to other process reward models (e.g., process rewards built using the Math Shepherd paradigm or process rewards derived from advanced closed-source models) in terms of performance when used with the same LLM agent?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xashilvm07", "reviewer": "Reviewer_agwr", "summary": "Given the limitation that current agent task do not possess high-quality granular reward signals, this work proposes the QLASS (Q-guided Language Agent Stepwise Search) method to automatically explore states , learn step-wise values, and apply these value-based heuristics are inference time. QLASS is shown effective in improving downstream agent performance through efficient value learning procedures.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer agwr,\n\nWe greatly appreciate your insightful comments for our work. Here are our responses to your questions.\n\n> 1 Incomplete computation cost calculation and explanation on “Completion tokens”\n\nWe would like to clarify that all the inference-time methods in Figure 3, i.e., Best-of-N and QLASS, share the same policy training computation. The computation overhead of QLASS lies in exploring trajectories to build the reasoning tree and then train the reward model. Second, the training cost is once while inference cost is almost infinite from a long-term perspective. The terminology is also used in prior work[1].  \n\nFor the computation leveraged for exploration, we have included the hyperparameters in Table 5 and discussed in Appendix A.2, where we kindly direct the reviewer for further details.  \n\nThe “Completion tokens” in Figure 3 x-axis refers to all the inference cost leveraged in Best-of-N and QLASS. A rough estimation is that each complete trajectory includes 40 * 1e3 tokens. Take 400 * 1e3 on the x-axis as an example, it means the inference cost includes 10 generated trajectories.\n\n> 2 Justification of QLASS with 13B model weaker than 7B\n\nWe summarize and compare the results on 7B and 13B models in the table below.\n\n| | SciWorld-seen | SciWorld-unseen |\n|-|-|-|\n|SFT-7B|67.4|53.0|\n|SFT-13B|68.1 (+0.7) |57.6 (+4.6)| \n|ETO-7B|73.8 | 65.0|\n|ETO-13B|71.4 (-2.4)| 68.6 (+3.6) |\n|QLASS-7B|75.3| 66.4  |\n|QLASS-13B|72.7 (-1.6) | 69.3 (+2.9)|\n\nOn the seen set, both the ETO-13B and QLASS-13B models show slightly lower performance compared to their 7B counterparts (-2.4 and -1.6, respectively). This might suggest some degree of overfitting in the larger 13B models, where the model may have specialized too much on the training data.\n\nOn the unseen set, all 13B models show significant improvements over their 7B counterparts (+4.6, +3.6, and +2.9, respectively). This indicates that the larger 13B models demonstrate better generalization capabilities, performing better on new, unseen data.\n\n> 3 The necessity of BC stage and the impact of BC with different N examples\n\nWe observe that both the effectiveness of exploration and the QNet depend heavily on the initial capabilities of the model. Recent research [2] suggests that a good initialization of the LLM achieved through SFT is crucial for reducing the search space and is beneficial for inference-time scaling. We empirically found that with N=0, the quality of exploration was very poor, making it difficult to train a good reward model. Some tasks show nearly zero performance w/o BC as shown in Table 2. In practical applications, it is generally feasible to secure a small set of high-quality training trajectories annotated by experts or researchers. But scaling up the dataset is difficult due to cost, time, and maintaining consistency in data quality.\n\nWe added experiments on the setup of using 200 examples for behavior cloning and summarize the results of leveraging different N examples for BC in the table below.\n\n|  |WebShop| WebShop-1000 | WebShop-200 | \n|-|-|-|-|\n| SFT | 63.1|21.7| 20.9 | \n| ETO | 67.4 |66.7| 52.1 | \n| BoN|67.9| 47.1| 45.1|\n| QLASS|70.3| 67.3| 53.7|\n\nWe can observe from the table that QLASS consistently outperforms other baselines under setups leveraging different BC examples, demonstrating its robustness across different BC datasets.\n\n> 4 Choice of Llama-2-Chat\n\nWe chose the Chat version because it is more appropriate and more easily adapted to the multi-turn, interactive agent tasks that our paper focused on. We chose Llama-2-Chat for our experiments because we are building on the code from ETO [3], which also uses Llama-2-Chat. Additionally, FastChat that we use for serving and generation, provides stable support specifically for Llama-2 models. Due to resource limitations, we are unable to rerun all experiments on Llama-3 at this stage but plan to include Llama-3 results in the future.\n\n> 5 More API-based models\n\nWe have GPT4, GPT3.5-Turbo, and GPT-4o based Reflexion included in our main Table 2. We also add additional experiments on GPT4o on the WebShop. We kindly direct you to the discussion in Q3 of Reviewer hiva.\n\n\n> 6 Explanation of 66.4 of Q-value in Figure 4 and 70.3 of QLASS in Table 2\n\nThe experimental setups are different. As we stated in L358-361, results in Figure 4 are self-training baselines where QNet is used for self-training data generation. QLASS in Table 2 is leveraged to provide inference-time guidance.\n\n> 7 Missing citation\n\nThanks for bringing this missing citation to us. We will add it in our revised version.\n\nWe hope that our answers can resolve your concerns.\n\n[1] Zhang, D., Zhoubian, S., Hu, Z., et al. (2024). Rest-MCTS: LLM self-training via process reward guided tree search.  \n\n[2] Team, K., Du, A., Gao, B., et al. (2025). Kimi K1.5: Scaling reinforcement learning with LLMs.  \n\n[3] Song, Y., Yin, D., Yue, X., et al. (2024). Trial and Error: Exploration-Based Trajectory Optimization for LLM Agents.", "claims_and_evidence": "1. The main claim that learning and applying Q-value to language agents improves performance, is supported by the main result in Table 2, where the proposed QLASS method achieves the highest result on all three benchmarks on varied settings.\n2. The claim on inference-time search efficiency in Figure 3, may not be fully supported due to incomplete computation cost calculation. IIUC, the baseline Best-of-N method only requires inference-time scaling, therefore the cost (“Completion Tokens”) calculated in Figure 3 are sufficient; nonetheless, for the QLASS method, additional training process on policy and reward models are required, yet Figure 3 only computes the inference-time cost. A more detailed discussion on the overall computation cost could be helpful. Furthermore, the metric “Completion Tokens” is not very intuitive to understand, e.g., if 150 tokens is sufficient for generating 1 or multiple responses (which is sufficient for common agent inference), or what’s the expected value/distribution of “Completion Tokens” on the tested benchmarks. Knowing this information would help decide which are the critical regions on Figure 3 x-axis, and if QLASS is more empirically useful than the simple Best-of-N method.\n3. For ablation study in Section 5.5, while QLASS still achieves higher results than other methods with the 13B model. However, comparing to 7B model results in Table 2, which should be presumably lower since smaller models are usually weaker, QLASS with 13B model actually underperforms QLASS with 7B model. More justification on this inferior result, or further more comprehensive studies on model scaling could be helpful.", "methods_and_evaluation_criteria": "The method design is well-motivated and reasonable in general. However, one question that I have is the necessity of the “Behavioral Cloning” stage introduced in Section 4.1. Because it is a warm-start for the language agent and not related to the core Q-value model, it seems that the QLASS method could potentially work without this BC process. While BC is a beneficial process given that the main task-solving agent experimented in this work is open-source models, another experiment that (1) do not involve this BC stage, or (2) ablates more Ns in section 5.3 (including N=0) could be helpful. Furthermore, using closed API models (e.g., gpt-4o, claude) as the task-solving agent (while keeping the QNet training and Q-Guided training with open-source models), could offer more information on the effectiveness of the designed modules.", "theoretical_claims": "The paper introduces the Q-value learning process in symbolic expressions, which reads reasonable.", "experimental_designs_or_analyses": "1. Corroborated by the “Methods and Evaluation Criteria” section, additional experiments using varying N examples for BC could be helpful, especially the case when N=0.\n2. The choice of main model, LLama-2-7B-chat, is somewhat unexpected. As more upgraded versions of similar-sized Llama models (3.1, 3.2) have been released, it is a bit unclear why the somewhat older Llama-2 model is selected. Similar confusion holds for choosing the “-Chat” version specifically.", "relation_to_broader_scientific_literature": "The key Q-learning idea of this paper is related to reinforcement learning and process reward modeling. The results are consistent with several reward modeling works in that PRMs are effective (more so that ORMs) in improving multi-step agentic tasks.", "essential_references_not_discussed": "The related work section has discussed the relevant literature rather comprehensively. However, there is one paper that I find relevant but not cited in this paper:\nKoh, Jing Yu, et al. \"Tree search for language model agents.\" arXiv preprint arXiv:2407.01476 (2024).", "other_strengths_and_weaknesses": "The paper is written with clarity; all results are presented clearly in tables and figures.", "other_comments_or_suggestions": "For Figure 4, the bar plot shows Q-value achieves 66.4, while Table 2 shows 70.3. What causes the difference between?", "questions_for_authors": "The method (specifically BC and Q-learning) requires supervision data corresponding to the test set, I wonder how the method could be generalized to agent tasks without compatible training examples or ground-truth environmental rewards?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a technique for LLM self-improvement that is inspired by the Q-learning algorithm in RL. The reviewers agreed that the problem studied in the paper is timely and well-motivated (improving LLM-powered AI agents), the proposed technique is interesting (generating tree-structured rollouts and estimating Q-values from sparse outcome reward signals) and the empirical evidence is sound and convincing.

In their rebuttal, the authors submitted several additional experiments that addressed all of the concerns and suggestions raised by the reviewers. Including all of these additional experiments substantially strengthens the paper.
Decision: Accept (poster)