acceptodds
Under review as a conference paper at ICLR 2027

TSR: Trajectory‑Search Rollouts for Multi‑Turn RL of LLM Agents

Abstract

Advances in large language models (LLMs) are driving a shift toward using reinforcement learning (RL) to train agents from iterative, multi-turn interactions across tasks. However, multi-turn RL remains challenging as rewards are often sparse or delayed, and environments can be stochastic. In this regime, naive trajectory sampling can hinder exploitation and induce mode collapse. We propose **TSR** (**T**rajectory-**S**earch **R**ollouts), a training-time approach that repurposes test-time scaling ideas for improved per-turn rollout generation. TSR performs lightweight tree-style search to construct higher-quality trajectories by selecting promising actions and trajectory prefixes during rollout generation. This improves rollout quality while preserving stable policy optimization and remains compatible with standard policy-gradient optimizers by design. Across Sokoban, FrozenLake, and WebShop, TSR achieves success-rate gains of up to 15 percentage points and converges in fewer optimization steps, while trading additional training-time rollout compute for stronger policies that require no search at inference time. By moving search from test time to the rollout stage of training, TSR provides a modular mechanism for stronger multi-turn agent learning, complementary to existing frameworks and rejection-sampling-style selection methods.

Primary area:
reinforcement learning
Keywords:
large language models, LLM agents, multi-turn RL

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Z9aiOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

TSR (Trajectory-Search Rollouts) moves test-time search ideas into the rollout stage of multi-turn RL for LLM agents: at each turn the current policy proposes several candidate actions, the environment executes them, a scoring function ranks the resulting prefixes, and a search strategy (trajectory-level best-of-N, per-turn beam search with B=2 and M=4, or shallow lookahead with depth 2) decides which partial trajectories survive, while PPO or GRPO then updates on the retained trajectories using only the original task reward. The scoring signal is the step reward in Sokoban, goal distance plus a hole penalty in FrozenLake, and milestone progress plus keyword overlap in WebShop, and TSR is layered on RAGEN's variance-based instance filtering. With Qwen2.5-0.5B and 3B models and three seeds, beam search raises success over the instance-filtering baseline from 43.7 to 52.3 on Sokoban, 48.7 to 60.7 on FrozenLake, and 70.3 to 85.3 on WebShop, converges in 40 to 50% fewer update steps, and produces shorter responses and fewer turns at inference with no search at deployment. Controls show that scaling naive sampling to 2× or 4× adds only 1 to 2.5 points, that beam search beats score-augmented selection and greedy per-turn search under identical scoring information, that gains persist with raw task reward, entropy, learned value, noisy, or Monte Carlo-backed scorers, that per-step KL stays near 0.02 to 0.05 for beam widths up to 5 but learning degrades beyond width 20, and that TSR outperforms reimplemented ARPO and GiGPO and composes with GiGPO, with further gains on ALFWorld and AppWorld up to 7B. Training cost is about equal to baseline on Sokoban and FrozenLake but about 40% higher on WebShop, the method requires a checkpointable environment, and all comparators are the authors' own RAGEN reimplementations on the Qwen2.5 family only.

Critical strengths
  • A clean, modular intervention. TSR changes only how rollouts are generated. The optimizer, objective, advantage estimator, and task reward are untouched, which makes it easy to adopt in any PPO or GRPO pipeline and to compose with other improvements. The GiGPO combination (80.2 to 87.0 on WebShop) demonstrates this directly.
  • Consistent gains across tasks, model sizes, optimizers, and environments. Beam search beats the baseline in every one of the five main cells, under both PPO and GRPO, from 0.5B to 7B, and on two further environments (ALFWorld and AppWorld) that differ substantially from the original three. The ordering beam > lookahead > best-of-N > baseline holds everywhere, which is more convincing than a single large number.
  • The controls address the obvious confounds. The paper anticipates the questions a reviewer would ask and runs the experiments: a budget-scaled naive baseline, information-matched comparisons that hand the same scorer to flat selection and greedy search, scorer-sensitivity sweeps (raw reward, entropy, learned value, noisy), a Monte Carlo-backed variant that uses only terminal reward, and an information-matched comparison with ARPO. Together they make a reasonable case that per-turn branching with multiple live prefixes is what matters.
Critical weaknesses
  • The budget-matched baseline may not use its budget. Scaled instance filtering generates 32 or 64 trajectories per group but retains 16, and the paper never states how those 16 are chosen. If they are selected at random, the extra compute is thrown away and the near-flat results in Tables 3 and 7 are guaranteed by construction. The only real compute-matched control is best-of-N at 2×, and against that the beam-search gap is 3 to 12 points rather than the 9 to 15 reported against the baseline.
  • Gains rest on privileged scoring signals. The main FrozenLake and WebShop numbers use scorers that read agent coordinates, hole positions, and milestone flags from the simulator. With raw task reward only, the beam-search improvement drops from 12.0 to 4.7 points on FrozenLake and from 15.0 to 5.6 on WebShop. The abstract's "up to 15 percentage points" is the privileged-scorer result. The Monte Carlo-backed variant recovers most of the gain but at unreported extra compute.
  • Narrow experimental scope. Qwen2.5 only, 7B at most, five-turn horizons for two of the three main environments, and RAGEN's simplified WebShop. The claim that TSR helps with long horizons is tested only at K=10.
  • Novelty relative to concurrent work is not established empirically. Tree search for agent RL (Ji et al.), lookahead tree rollouts (Xing et al.), and process-reward-guided tree rollouts (Li et al.) are cited as closely related but none is compared, and related work lives entirely in the appendix.
Questions for authors
  1. In scaled instance filtering (Lgen = 32 or 64, Ltrain = 16), how are the 16 retained trajectories chosen from the generated set? If at random, what is the result when the top 16 by return are kept, and how does that differ from the best-of-N row?
  2. Can you compare directly with the concurrent tree-search rollout methods you cite (Ji et al., Xing et al., Li et al.), or at least explain what TSR does differently from each in mechanism rather than framing?
6 comments
AuthorsOpenReview ↗

Response 1: W1/Q1, W2

Thank you for the detailed and accurate review. Your W1/W2 identified two places where we claimed more than evidence suggested, and both are now fixed! New results are marked as [new] below.

We will split our response in 2 comments to accomodate the new results tables!


In short: (1) The retention rule is stated, and the compute claim now rests on flat-selection controls: Best-of-64 at 4× stays below TSR at 1×. (2) The scorers are not privileged, the headline number is decomposed, and gains without a task-specific scorer are +7 to +11 points at 2×. (3) Horizons reach 50 turns, and the gains transfer to a second model family. (4) We add a mechanism comparison with the cited tree methods and a Tree-GRPO experiment: TSR is 5.5 / 7.2 points ahead, and the two combine.


W1 / Q1. Budget-matched baseline and retention rule

The rule. In scaled instance filtering, all generated trajectories (32 or 64) are used to estimate group uncertainty, and 16 are then uniformly subsampled for the update. You are right about the consequence: within a group, the training trajectories are distributed as at 1×, so this baseline only tests whether more naive sampling helps through better group selection. It does not (48.7 / 49.5 / 49.8 on FrozenLake, within run-to-run variation). It is not a control for trajectory selection, and we no longer present it as one.

Top 16 by return. This is exactly TSR (Best-of-N) with N=32, so the 2× answer is the Best-of-N row. We added the 4× point and rebuilt Sec. 5.4 around flat-selection controls (Qwen2.5-3B):

MethodBudgetSokobanFrozenLakeWebShop
Instance filtering1×43.7 ± 1.648.7 ± 1.970.3 ± 1.8
Best-of-32 (top 16 by return)2×47.7 ± 1.551.0 ± 1.673.3 ± 1.5
Best-of-64 (top 16 by return) [new]4×49.0 ± 1.453.2 ± 1.475.6 ± 1.3
Score-augmented filtering (top 16 by progress score)2×n/a55.6 ± 1.679.2 ± 1.5
TSR beam (M=B=2)1×53.1 ± 1.159.5 ± 1.183.4 ± 1.2
TSR beam (M=4, B=2)2×52.3 ± 1.360.7 ± 1.285.3 ± 1.1
  • Your reading is correct. Against Best-of-N at 2×, beam gains 4.6 / 9.7 / 12.0 points with the progress scorer, but only 2.4 / 2.6 (FrozenLake / WebShop) when both use the task reward alone (Table 15 now, was Table 13 before). The latter is within about 1.5 standard deviations, and we have softened the corresponding claim in App. F.7.
  • Same scorer. With the progress scorer given to flat selection, beam still gains +5.1 / +6.1.
  • Equal budget. With M=B=2, beam uses a 1× transition budget (App. E) and gains +9.4 / +10.8 / +13.1 over instance filtering (Tables 10-12, was Tables 8–10 before).
  • More flat budget does not close the gap [new]. Going from 2× to 4× adds 1.3 / 2.2 / 2.3 points. Best-of-64 at 4× remains 4.1 / 6.3 / 7.8 below beam at 1×. On Sokoban this comparison is also information-matched, since the scorer there is the environment reward.

W2. Scoring signals

Privileged? No. The FrozenLake scorer (Eq. 12 now, was Eq. 9 before) uses the agent position, goal, and hole locations, all rendered in the text grid the agent observes at every turn. The WebShop scorer (Eq. 14 now, was Eq. 10 before) uses the instruction, the interaction history, and the text of the resulting page. App. D.2 described these as simulator-derived, which was a bit misleading perhaps. We have thus added a new paragraph "Scorer Information Access", which now states the inputs.

Your numbers are right. With the task reward only, the gain over the baseline is 4.7 / 5.6 points, not 12.0 / 15.0. The 15-point figure belongs to the task-specific progress scorer. We have thus revised the abstract, which now reads: "TSR improves success rates by up to 15 percentage points with lightweight progress-based scoring. Under identical scoring information, structured per-turn search accounts for 5–6 of these points, and gains of 9–11 points persist with a learned observation-only scorer."

TSR beam scorer (Qwen2.5-3B)Task-specificFrozenLakeWebShopRollout transitions
Task reward onlyno53.4 ± 1.575.9 ± 1.42×
Entropy (task-agnostic)no55.8 ± 1.578.6 ± 1.42×
Learned observation-only valueno57.6 ± 1.381.4 ± 1.32× + value model
Monte Carlo-backed terminal rewardno59.1 ± 1.082.9 ± 1.08.9× / 15.6× [new]
Progress scoreyes60.7 ± 1.285.3 ± 1.12×
  • Without a task-specific scorer, at the same 2× budget, TSR gains +7.1 / +8.3 (entropy) and +8.9 / +11.1 (learned value) over the baseline.
  • ALFWorld and AppWorld use only the learned observation-only value (App. F.11), with no hand-designed scorer, and show gains of +14.9 / +11.1 (3B).
  • Monte Carlo compute. With C=2 continuations per candidate, the realized transition count is 8.9× (FrozenLake) and 15.6× (WebShop) the baseline. This variant is therefore a heuristic-free robustness check, not a compute-matched result. Thus, the scorer-free claim rests on the 2× rows.

Continued in the next comment

AuthorsOpenReview ↗

Response 2: W3, W4/Q2

Continued from the previous comment.


W3. Scope

We agree on the limits and now state them: one model family up to 7B in the original experiments, full fine-tuning, resettable simulators, and RAGEN's reduced webshop-minimal setting with 1,000 products. App. D.1 described the full million-product corpus and has been corrected.

Horizons. The long-horizon claim is not tested only at K=10. ALFWorld and AppWorld allow 50 turns, and episodes average 18 to 36 turns, which we had not reported (Qwen2.5-3B):

EnvironmentMax turnsMean turns (IF / TSR)IFTSR beam
Sokoban54.1 / 3.643.752.3
FrozenLake53.6 / 3.148.760.7
WebShop106.8 / 5.870.385.3
ALFWorld5021.6 / 18.369.884.7
AppWorld5036.2 / 32.420.431.5

TSR gains +14.9 / +11.1 points at these horizons. Both results are now in the main text.

Model family [new]. We trained a second backbone under the same optimization and evaluation settings:

Llama-3.2-3B-InstructFrozenLakeWebShop
Instance filtering39.8 ± 2.158.4 ± 1.9
TSR beam49.6 ± 1.871.2 ± 1.7

The gains (+9.8 / +12.8) are similar in size to those with Qwen2.5-3B (+12.0 / +15.0) and show generalization to other model architectures.


W4 / Q2. Relation to tree-search rollout methods

We proide a more detailed overview as requested.

Mechanism. The methods differ in what triggers a branch, what is pruned, and what enters the update (table added to App. A):

MethodBranch triggerPruned byPolicy trains onUpdate rule changed
Tree-GRPO (Ji et al.)random agent-step nodesnothingall branchesyes: intra- + inter-tree advantage
ARPO / AEPO (Dong et al.)high-entropy tool-call stepsnothingall branchesyes: advantage attribution; AEPO also clipping
LATR (Xing et al.)uncertain tokens, single-turnnear-duplicate continuationsremaining diverse branchesno
PATR (Li et al.)process score at periodic checkpointslow-scoring branches stopped earlycompleted and early-stopped branchesno
TSR (ours)every turn, every executed candidate scoredestimated returnsearch survivors onlyno

In the other methods, the tree decides where rollout budget is spent or how credit is assigned. In TSR, search decides which trajectories the policy learns from, which is why the distribution-shift boundary in Sec. 5.5 arises for TSR. These are differences in mechanism, not a claim that other tree methods leave the training distribution unchanged.

Empirical comparison [new]. We implemented Tree-GRPO in the same framework (random node expansion, all branches in the update, intra- plus inter-tree advantage; configuration in App. F.8) and matched executed environment transitions. To separate expansion from selection, we also apply return-based selection to its randomly expanded trees:

Qwen2.5-3BExpansionTrains onPrefix scorerBudgetFrozenLakeWebShop
Instance filteringnoneall samplednone1×48.7 ± 1.970.3 ± 1.8
Tree-GRPO [new]randomall branchesnone2×55.2 ± 1.578.1 ± 1.5
Tree-GRPO + selection [new]randomtop 16 by returnnone2×57.3 ± 1.4n/a
TSR beamscored, per turnsurvivorstask reward only2×53.4 ± 1.575.9 ± 1.4
TSR beamscored, per turnsurvivorsprogress2×60.7 ± 1.285.3 ± 1.1
TSR beam + tree advantages [new]scored, per turnsurvivorsprogress2×63.0 ± 1.187.2 ± 1.0
  • Outcome reward only. The two are close: Tree-GRPO is 1.8 / 2.2 points ahead of reward-only TSR, about one standard deviation.
  • Selection helps even on random trees. Training only on the top 16 leaves by return raises Tree-GRPO from 55.2 to 57.3 on FrozenLake.
  • Scored per-turn search adds more. TSR with the progress scorer is a further 3.4 points above that, and 5.5 / 7.2 above Tree-GRPO. With the learned observation-only value it is 2.4 / 3.3 ahead.
  • Combined. Adding tree advantages to TSR gives the best result (+2.3 / +1.9), so rollout selection and tree-based credit assignment are complementary.

LATR branches within token sequences in single-turn tasks and does not transfer to environment-step branching without adaptation. PATR was posted to arXiv in July 2026 and is concurrent. We cite it, compare mechanisms, and leave an empirical comparison to future work.


Summary of changes. (1) Retention rule stated; compute claim rebuilt on Best-of-N, Best-of-64, same-scorer flat selection, and the 1× result. (2) Scorer inputs stated, abstract revised, Monte Carlo compute reported. (3) Horizons reported, second model family added, limits stated. (4) Mechanism table and Tree-GRPO comparison added.

We hope this addresses your concerns and are happy to clarify further.

Just a brief reminder that the author-reviewer discussion period ends tomorrow (Nov 18).

In our response, we adopted your two main points and ran new experiments for the others. The compute claim now rests on flat-selection controls (Table 2): Best-of-64 at 4× stays 4.1 / 6.3 / 7.8 points below beam search at 1×. The abstract now attributes the 15-point figure to progress scoring: under identical scoring, search adds 5.1 / 6.1 points, and gains without a task-specific scorer are 7 to 11 points at 2×. We also report horizons of up to 50 turns and a second model family (Tables 4 and 28), and added a mechanism comparison (Table 5) and a Tree-GRPO experiment (Table 20), where TSR is 5.5 / 7.2 points ahead and the two methods combine.

Thank you again for your careful initial review. If these responses address your concerns, we would appreciate it if you could acknowledge this and consider reassessing your rating to ensure acceptance. Of course, we are happy to answer any follow-up questions!

Best regards, Authors

Reviewer_zZw3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

TSR uses search during RL rollout collection to build better multi-turn trajectories, which are then used for PPO or GRPO updates. The experiments show consistent improvements across five agent benchmarks without requiring search at inference time.

Critical strengths

The method is straightforward to integrate into existing training pipelines, and the gains carry over to deployment without extra search.

The experiments are fairly thorough. The scoring controls, rollout-budget comparisons, and additional environments make the improvements convincing.

Critical weaknesses

I’m not totally convinced by the explanation of distribution shift. Appendix B.2 mentioned selection bias, but clipping does not correct that bias, and the candidate-set KL in F.4 does not establish closeness over full trajectories. The claim that moderate search stays sufficiently close to the policy needs stronger support.

The comparisons with ARPO and GiGPO are useful, but there is no direct comparison with Tree-GRPO. Since it also uses tree-based rollouts for agent training, this comparison would help establish what TSR adds.

Search also changes which task groups survive instance filtering, as Appendix B.2 notes. Without an ablation that fixes the selected groups or removes filtering, it is hard to separate the benefit of better trajectories from a changed training curriculum.

Questions for authors

What evidence beyond the local KL measurement supports the claim that moderate search keeps the updates reliable?

How does TSR compare with Tree-GRPO under the same rollout budget?

Do the gains persist when task-group selection is held fixed or instance filtering is removed?

4 comments
AuthorsOpenReview ↗

Response 1: W1 / Q1

Thank you for the constructive review. All three of your points led to new analysis or experiments, marked as [new] below. All changes are revised in the PDF.

We will split our response in 2 comments to accomodate the new results tables!


In short: (1) For moderate search, the TSR batch gradient is better aligned with the on-policy gradient than a naive batch of the same size (0.75–0.77 vs. 0.64), and alignment breaks down where performance does. (2) At matched budget, TSR with its progress scorer is 5.5 / 7.2 points above Tree-GRPO, and combining the two gives the best result. (3) The gain persists with task groups held fixed (+10.4 / +13.7) and with instance filtering removed (+12.0).


W1 / Q1. Distribution shift and reliability of the updates

You are right on both counts: clipping limits the size of an update but does not correct selection bias, and the candidate-set KL in App. F.4 is a local quantity. We have removed the claim that clipping accommodates the shift (Sec. 5.5, App. B.2) and replaced it with the following (in our opinion) much better characterization (new App. B.3).

What the update optimizes. For flat selection of LL out of NN sampled trajectories, the retained trajectories follow μ(τ)=w(τ)πθ(τ)\mu(\tau)=w(\tau)\pi_\theta(\tau) with w(τ)=NLPr⁡[τ retained]∈[0,NL]w(\tau)=\tfrac{N}{L}\Pr[\tau\text{ retained}]\in[0,\tfrac{N}{L}]. The expected TSR update direction is therefore Eμ[A^(τ)∇θlog⁡πθ(τ)]=∇θEπθ[w(τ)A^(τ)]\mathbb{E}_{\mu}\big[\hat A(\tau)\nabla_\theta\log\pi_\theta(\tau)\big]=\nabla_\theta\mathbb{E}_{\pi_\theta}\big[w(\tau)\hat A(\tau)\big], with ww and A^\hat A held fixed (i.e., for a fixed baseline). TSR thus follows the on-policy gradient of a reweighted return: the selection is a deliberate reweighting, not an uncorrected off-policy error. With a binary task reward (FrozenLake, WebShop) and selection by return, wA^w\hat A is an increasing function of RR, and the direction is a positive multiple of the true policy gradient. With score-guided search, ww additionally up-weights trajectories with high-scoring prefixes, while the sign of each trajectory's contribution is still set by the task reward, so failures that survive search are pushed down. This is a characterization, not a monotonic-improvement guarantee.

Trajectory-level closeness. Since w≤N/Lw\le N/L, we have DKL(μ ∥ πθ)≤log⁡(N/L)D_{\mathrm{KL}}(\mu\,\|\,\pi_\theta)\le\log(N/L) over full trajectories (0.69 nats for Best-of-N), and μ\mu never places mass where πθ\pi_\theta has none. For beam search, counting candidate paths gives w≤MKw\le M^{K}, i.e., DKL≤Klog⁡MD_{\mathrm{KL}}\le K\log M. This worst-case bound is loose (6.9 nats for M=4M=4, K=5K=5, against a measured 0.08), but it shows that the shift is controlled by the search budget, not by clipping, and that it grows with MM, as in Table 3 (was Table 11 before), where M=2BM=2B. We now also report the KL summed over the turns of a trajectory, next to the per-step value.

Evidence beyond local KL [new]. At fixed checkpoints, we compute a reference gradient from naive on-policy trajectories and measure the cosine similarity of standard-size batch gradients to it:

FrozenLake, Qwen2.5-3BSummed KL per trajectory.Cosine to on-policy gradientClip fractionSuccess rate
Naive rollouts (same batch size)0.000.640.0748.7 ± 1.9
TSR beam, B=20.080.750.0860.7 ± 1.2
TSR beam, B=50.190.770.1061.3 ± 1.1
TSR beam, B=100.520.660.1560.9 ± 1.4
TSR beam, B=201.140.430.2953.8 ± 1.8
TSR beam, B=301.760.270.4145.1 ± 2.1
  • For B≤5B\le 5, the TSR batch gradient is more aligned with the on-policy reference than a naive batch of the same size (0.75–0.77 vs. 0.64), at a clip fraction close to the baseline (0.08–0.10 vs. 0.07): moderate search gives a lower-variance estimate of a direction that agrees with the on-policy gradient.
  • At B=10B=10 alignment falls back to the naive level, and for B≥20B\ge 20 it drops well below it (0.43, 0.27) while the clip fraction rises to 0.29–0.41, which is where success degrades.
  • The boundary suggested by the local KL is thus confirmed by a trajectory-level KL and by a direct measurement of the update direction.
  • In addition, every success rate in the paper, including the curves in Fig. 3, is measured without search, so those curves are themselves on-policy measurements of the updated policy.

Continued in the next comment

AuthorsOpenReview ↗

Response 2: W2/Q2, W3/Q3

Continued from the previous comment.


W2 / Q2. Comparison with Tree-GRPO

We implemented Tree-GRPO (we follow the official code) in the same framework, with its random node expansion, all branches entering the update, and its intra- plus inter-tree advantage, and matched it to TSR on executed environment transitions (Qwen2.5-3B):

MethodPrefix scorerBudgetFrozenLakeWebShop
Instance filteringnone1×48.7 ± 1.970.3 ± 1.8
Tree-GRPO [new]none (outcome reward)1×51.4 ± 1.7n/a
Tree-GRPO [new]none (outcome reward)2×55.2 ± 1.578.1 ± 1.5
TSR beamtask reward only2×53.4 ± 1.575.9 ± 1.4
TSR beamlearned observation-only value2×57.6 ± 1.381.4 ± 1.3
TSR beam (M=B=2)progress1×59.5 ± 1.183.4 ± 1.2
TSR beamprogress2×60.7 ± 1.285.3 ± 1.1
TSR beam + tree advantages [new]progress2×63.0 ± 1.187.2 ± 1.0

The two methods use the tree differently. Tree-GRPO shares prefixes to obtain more trajectories per budget and derives step-level credit from sibling branches. No branch is pruned by estimated return. TSR scores every executed candidate and trains only on the survivors.

  • Outcome reward only. The two are close: Tree-GRPO is 1.8 / 2.2 points ahead of reward-only TSR, about one standard deviation.
  • With a prefix scorer. TSR can use information Tree-GRPO has no mechanism for: it is 2.4 / 3.3 points ahead with a learned observation-only value and 5.5 / 7.2 with the progress score. At a 1× budget it is still 4.3 / 5.3 above Tree-GRPO at 2×.
  • Combined. Adding Tree-GRPO's tree advantages to TSR gives the best result (63.0 / 87.2), as with GiGPO (Table 23 now, was Table 20 before). Selecting which trajectories to train on and assigning credit within them are complementary.

A mechanism table covering Tree-GRPO, ARPO/AEPO, LATR, and PATR will be added to the appendix.


W3 / Q3. Interaction with instance filtering

We agree this was not disentangled. We now vary which task groups are selected independently of which trajectories are trained on [new]. "Uniform random" removes instance filtering (same number of groups per update). "Naive-rollout uncertainty" ranks groups with separate naive rollouts, so the selected groups do not depend on search. "Post-search uncertainty" is the setting in the paper.

Env (Qwen2.5-3B)Trained onGroups: uniform randomGroups: naive-rollout uncertaintyGroups: post-search uncertainty
FrozenLakeNaive rollouts45.9 ± 1.848.7 ± 1.949.2 ± 1.7
FrozenLakeTSR beam rollouts57.9 ± 1.459.1 ± 1.360.7 ± 1.2
WebShopNaive rolloutsn/a70.3 ± 1.8n/a
WebShopTSR beam rollouts82.5 ± 1.484.0 ± 1.385.3 ± 1.1
  • Group selection held fixed. With groups chosen by naive-rollout uncertainty, TSR gains +10.4 / +13.7 (FrozenLake / WebShop).
  • Filtering removed. On FrozenLake, TSR gains +12.0 with uniformly random groups. On WebShop, TSR without filtering (82.5) is still 12.2 points above the filtered baseline.
  • Effect of the changed curriculum. Moving from naive-rollout to post-search group selection adds 1.6 / 1.3 points for TSR and 0.5 for naive training, about one standard deviation.

The gain therefore follows the trajectories, not the group selection. App. B.2 now states this result and that search can change which groups are selected.


Summary of changes. (1) New App. B.3 with the reweighting identity and trajectory-level bound, plus gradient-alignment diagnostics. (2) Tree-GRPO comparison at matched budget and in combination, with a mechanism table in the appendix. (3) Group-selection ablation.

We hope this addresses your questions and are happy to clarify further.

Just a brief reminder that the author-reviewer discussion period ends tomorrow (Nov 18).

In our response, we added new analysis and experiments for all three of your questions. On distribution shift, we replaced the clipping argument with a reweighting characterization (App. B.3) and a gradient-alignment diagnostic (Table 3): for B ≤ 5, TSR batch gradients align better with the on-policy reference than naive batches (0.75–0.77 vs. 0.64), and alignment drops where performance does. We ran the Tree-GRPO comparison at matched transitions (Table 20): TSR with progress scoring is 5.5 / 7.2 points ahead, and combining the two gives the best result (63.0 / 87.2). We also separated rollout selection from instance filtering (Table 30): TSR gains 10.4 / 13.7 points with group selection held fixed, and 12.0 with filtering removed.

Thank you again for your initial positive score. If these responses address your remaining questions, we would be happy if you could acknowledge this and potentially consider reassessing your rating to a higher score to ensure acceptance. Of course, we are happy to answer any follow-up questions!

Best regards, Authors

Dear reviewers,

Will you please check the authors' response and reply it?

Best, AC

Reviewer_BnSvOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Test-Time Search for Rollouts (TSR), which integrates search into the rollout stage of multi-turn reinforcement learning for LLM agents. At each turn, TSR samples and evaluates candidate actions, retaining promising trajectory prefixes. It explores three variants: best-of-N, beam search, and shallow lookahead. The underlying PPO or GRPO optimizer remains unchanged, and no search is required at inference.

Experiments on Sokoban, FrozenLake, and WebShop demonstrate improved task success. For the 3B model, beam search increases success rates over instance filtering alone from 43.7% to 52.3% on Sokoban, 48.7% to 60.7% on FrozenLake, and 70.3% to 85.3% on WebShop, averaged over three runs.

Critical strengths
  1. Simple, optimizer-agnostic method with strong experimental controls. TSR improves rollout quality without modifying the RL optimizer and can be combined with existing methods such as GiGPO. Thorough ablations control for additional compute, reward shaping, and scorer differences, supporting the claim that improved rollouts drive the gains. The paper also reports computational costs in wall-clock hours and EFLOPs.

  2. Consistent improvements without inference-time overhead. TSR achieves gains across three environments, two model sizes, and both PPO and GRPO, with results reported over three runs. Since search is restricted to training, the method offers practical benefits without increasing inference-time costs.

Critical weaknesses
  1. Confounded gains from hand-designed scoring functions. The headline improvements combine search with task-specific progress scorers, making it difficult to isolate the contribution of search itself. On WebShop, beam search achieves 75.9% with raw rewards versus 85.3% with the progress scorer. Even with the same scorer, its advantage over instance filtering is substantially smaller. Moreover, it remains unclear whether the scorer uses privileged simulator information unavailable to the agent.

  2. Stochastic selection bias and unclear compute-matched comparisons. In FrozenLake, search selects actions based on realized stochastic transitions, potentially favoring lucky outcomes rather than better decisions. The compute-matched instance-filtering baseline also retains only 16 trajectories despite generating more, without clearly explaining the selection procedure. These issues weaken the attribution of improvements to better rollout search.

  3. Limited task difficulty and generalizability. The selected benchmarks are relatively simple and constrained, potentially favoring search-based exploration. Evaluation on more challenging, open-ended, and realistic multi-turn agent tasks is needed to establish whether TSR generalizes beyond these environments.

Questions for authors

See Critical Weaknesses

4 comments
AuthorsOpenReview ↗

Response 1: W1, W2a

Thank you for the careful reading, including the appendix controls. We address each point below. New results are marked [new], and all changes are in the revised PDF.

We will split our response in 2 comments to accomodate the new results tables!


In short: (1) At an equal 1× rollout budget, TSR gains +10.8 / +13.1 points on FrozenLake / WebShop. (2) Flat selection at 4× the budget stays below TSR at 1×. (3) The FrozenLake gain does not depend on lucky transitions (60.0 vs. 60.7 when luck is removed from the score). (4) The gains hold on a second model family and at horizons of up to 50 turns.


W1. Scorer vs. search, and privileged information

Is the scorer privileged? No. The FrozenLake scorer (Eq. 9 before, now Eq. 12) uses the agent position, goal, and hole locations, all of which are rendered in the text grid the agent observes at every turn. The WebShop scorer (Eq. 10 before, now Eq. 14) uses the instruction, the interaction history, and the text of the resulting page. Both scorers are task-specific, but neither uses information hidden from the agent. We now state this explicitly in a new paragraph "Scorer Information Access" (App. D.2).

How much of the gain is search? We agree that the headline number combined scorer and search. The revised main text reports the decomposition in a new table (Qwen2.5-3B, success rate in %):

MethodRollout budgetScorerFrozenLakeWebShop
Instance filtering1×none48.770.3
Scaled instance filtering2×none49.572.1
Best-of-N (flat selection)2×task return51.073.3
Score-augmented filtering (flat selection)2×progress55.679.2
TSR beam2×progress60.785.3
TSR beam2×task reward only53.475.9
TSR beam2×entropy (task-agnostic)55.878.6
TSR beam2×learned observation-only value57.681.4
TSR beam (M=B=2)1×progress59.583.4
  • With the same scorer and budget, structured per-turn search adds +5.1 / +6.1 points over flat selection. This is the share attributable to search alone.
  • Without any task-specific scorer, TSR still gains +7.1 / +8.3 (entropy) and +8.9 / +11.1 (learned value) over the baseline.
  • At an equal 1× rollout budget, TSR gains +10.8 / +13.1.

The revised abstract now also reads: "TSR improves success rates by up to 15 percentage points with lightweight progress-based scoring. Under identical scoring information, structured per-turn search accounts for 5–6 of these points, and gains of 9–11 points persist with a learned observation-only scorer."


W2a. Stochastic selection (FrozenLake)

This is a fair point. With Eq. 12 (Eq. 9 before) applied to the realized next state, a prefix can be retained because a slip went the right way. Three remarks on this:

  1. Scope. FrozenLake is the only stochastic environment among the five we evaluate. The largest gains are on deterministic WebShop.
  2. Evaluation is searchless. Success rates are measured without search, in the same slippery environment, on held-out maps. Luck during rollout construction cannot carry over to evaluation. Thus, a policy scores higher only if its decisions are better.
  3. What could carry over is a preference for risky actions, since unlucky outcomes are pruned. We tested this directly with two [new] experiments.

1) Expected-outcome scoring. We rescore each candidate by the expected progress of the chosen action under the transition kernel, so the realized slip no longer enters the score:

FrozenLake, Qwen2.5-3BScore applied toSuccess rate
Instance filteringn/a48.7 ± 1.9
TSR beam (paper)realized next state60.7 ± 1.2
TSR beam [new]expected outcome of the action60.0 ± 1.4

2) Decision quality against the optimal policy. FrozenLake is small enough to compute the optimal policy exactly. We evaluate the final searchless policies. Excess hole risk is the one-step hole probability of the chosen move minus that of the optimal move in the same state, averaged over moves.

PolicyGoal ↑Hole ↓Timeout ↓Excess hole risk ↓
Instance filtering48.7%30.2%21.1%+0.018
TSR beam (realized)60.7%25.0%14.3%+0.003
TSR beam (expected) [new]60.0%22.7%17.3%+0.001
Optimal policy70.0%17.0%13.0%0.000

Removing realized outcomes from the score changes success by 0.7 points, within run-to-run variation. Both TSR policies end in a hole less often than the baseline (25.0% / 22.7% vs. 30.2%), and their excess hole risk relative to the optimal policy is close to zero (+0.003 / +0.001 vs. +0.018). Selecting on realized transitions therefore did not make the policy risk-seeking: it takes less risk than the baseline and closes more than half of the baseline's gap to the optimal policy (from 21.3 to 9.3 points). Expected-outcome scoring is slightly more cautious (fewer holes, more timeouts) at the same success rate, and we have added it as the recommended scorer for stochastic environments.


Continued in the next comment

AuthorsOpenReview ↗

Response 2: W2b, W3

Continued from the previous comment.


W2b. Retention rule in the compute-matched baseline

Thank you, this was underspecified. In the scaled baseline, all generated trajectories (32 or 64) are used to estimate group uncertainty, and 16 are then uniformly subsampled for the update. We agree this baseline only tests whether more naive sampling helps through better group selection (it does not: 48.7 / 49.5 / 49.8, within run-to-run variation). It does not test trajectory selection. The matched control with trajectory selection is Best-of-N, which keeps the top 16 by return. We ran the 4× point:

MethodBudgetSokobanFrozenLakeWebShop
Best-of-32 (paper)2×47.7 ± 1.551.0 ± 1.673.3 ± 1.5
Best-of-64 [new]4×49.0 ± 1.453.2 ± 1.475.6 ± 1.3
TSR beam (M=B=2)1×53.1 ± 1.159.5 ± 1.183.4 ± 1.2
TSR beam (M=4, B=2)2×52.3 ± 1.360.7 ± 1.285.3 ± 1.1

Doubling the flat-selection budget from 2× to 4× adds only 1.3 to 2.3 points. Best-of-64 at 4× remains 4.1 / 6.3 / 7.8 points below TSR at a 1× budget. On Sokoban this comparison is also information-matched, since the scorer there is the environment reward itself. For FrozenLake and WebShop, the same-scorer flat control is in the table under W1 (+5.1 / +6.1 for search alone). Sec. 5.4 now states the retention rule and bases the compute claim on these comparisons.


W3. Task difficulty and generalizability

We evaluate five environments in total. Besides Sokoban, FrozenLake, and WebShop in the main body, App. F.11 also reports ALFWorld (household tasks) and AppWorld (multi-application API and coding tasks). We have moved these results into the main text, together with the interaction horizons, which we had not reported:

EnvironmentModelMax turnsMean turns (IF / TSR)IFTSR beam
ALFWorld (success)3B5021.6 / 18.369.8 ± 1.884.7 ± 1.3
ALFWorld (success)7B5018.4 / 16.079.4 ± 1.592.1 ± 1.0
AppWorld (TGC)3B5036.2 / 32.420.4 ± 1.631.5 ± 1.2
AppWorld (TGC)7B5033.7 / 29.828.7 ± 1.540.6 ± 1.1

Episodes here run 16 to 36 turns on average, 3 to 7 times longer than in the three main environments, and AppWorld has a free-form code action space on which even the 7B baseline completes under 30% of tasks. TSR gains 11 to 15 points in these settings, so the benefit is not limited to short, constrained tasks.

To test generalization beyond the Qwen family, we also trained a second backbone:

Llama-3.2-3B-Instruct [new]FrozenLakeWebShop
Instance filtering39.8 ± 2.158.4 ± 1.9
TSR beam49.6 ± 1.871.2 ± 1.7

The gains (+9.8 / +12.8) are similar in size to those with Qwen2.5-3B (+12.0 / +15.0). All five environments are resettable simulators and extending TSR to non-resettable settings is stated as a limitation (App. G).


What the paper adds beyond applying known search methods. (i) Where rollout compute is spent matters more than how much: per-turn search at 1× beats flat selection at 4×. (ii) Selection can only move the training data so far from the policy before updates degrade, and we locate that boundary (Sec. 5.5).


Summary of our changes. (1) Attribution table and scorer-access statement are in the main text, with the revised abstract above. (2) Expected-outcome scoring and the optimal-policy analysis show the FrozenLake gain reflects better decisions. (3) The retention rule is now stated, and Best-of-64 shows flat selection at 4× stays below TSR at 1×. (4) ALFWorld and AppWorld are in the main text now, and the gains transfer to a second model family.

We hope this resolves the concerns and are happy to clarify further!

Just a brief reminder that the author-reviewer discussion period ends tomorrow (Nov 18).

In our response, we ran new experiments for each of your concerns. Scorer and search are now separated (Table 2): with the same scorer and budget, per-turn search adds 5.1 / 6.1 points over flat selection, and at an equal 1× budget TSR gains 10.8 / 13.1 points. To test whether lucky transitions drive the FrozenLake gain, we removed the realized slip from the score: TSR reaches 60.0% vs. 60.7%, and both policies take less hole risk than the baseline (Table 29). The retention rule is now stated, and Best-of-64 at 4× stays below TSR at 1×. The gains also hold at 50-turn horizons and on a second model family (Tables 4 and 28).

Thank you again for your careful initial review. If these responses address your concerns, we would appreciate it if you could acknowledge this and consider reassessing your rating to ensure acceptance. Of course, we are happy to answer any follow-up questions!

Best regards, Authors

Dear reviewers,

Will you please check the authors' response and reply it?

Best, AC

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response

We sincerely thank the reviewers for the careful review of our submission and provide a brief summary to facilitate discussion with the AC!

TSR moves search from test time into the rollout stage of multi-turn RL. Specifically, candidate actions are scored at every turn and the policy trains only on the surviving trajectories, with the optimizer unchanged and no search at inference.

  • We experimentally verified gains of 8.6 / 12.0 / 15.0 points on Sokoban / FrozenLake / WebShop (Qwen2.5-3B), and 11 to 15 points on ALFWorld and AppWorld at up to 50 turns.
  • Under identical scoring information, per-turn search adds 5.1 / 6.1 points over flat selection. Without any task-specific scorer, gains are 7 to 11 points.
  • We also showed that where rollout compute is spent matters more than how much: TSR at a 1× budget beats flat selection at 4×.
  • Also, TSR combines with credit-assignment methods (GiGPO, Tree-GRPO) for further gains.

We especially want to thank the reviewers for recognizing our strong contributions:

  • "Simple, optimizer-agnostic method with strong experimental controls", offering "practical benefits without increasing inference-time costs." (BnSv)
  • "Straightforward to integrate into existing training pipelines"; the controls "make the improvements convincing." (zZw3)
  • "A clean, modular intervention"; "The controls address the obvious confounds." (Z9ai)

All three reviewers also rated their soundness concerns as "minor or fixable".

The reviewers' comments have helped us improve the paper by:

  • adding seven new sets of experiments: Best-of-64 at 4×, expected-outcome scoring and an optimal-policy analysis on FrozenLake, a second model family (Llama-3.2-3B), gradient-alignment diagnostics, a Tree-GRPO comparison including its combination with TSR, and a task-group selection ablation.
  • Our paper now evaluates 25 comprehensive experiments in total (18 in the original submission, 7 new).

Despite our thorough responses, reviewer engagement was low and we hope this changes before the deadline. We briefly summarize how we addressed each reviewer:

1) Reviewer BnSv:

  • Concern 1: Gains confounded by a possibly privileged scorer: We explained that the scorers use only information in the agent's observation. Table 2 also separates scorer and search: +5.1 / +6.1 points for search alone, and +10.8 / +13.1 at an equal 1× budget.
  • Concern 2: FrozenLake search may select lucky transitions: With the realized slip removed from the score, TSR reaches 60.0% vs. 60.7% and takes less hole risk than the baseline (Table 29). The gain does not depend on lucky transitions.
  • Concern 3: Retention rule not stated and task difficulty: The rule is now stated, Best-of-64 at 4× stays below TSR at 1×, and the gains hold at 50-turn horizons and on Llama (Tables 4, 28).

We believe this resolves all three concerns.

2) Reviewer zZw3:

  • Concern 1: Distribution shift: We agreed that clipping does not correct selection bias, removed that claim, and added a reweighting characterization (App. B.3) and gradient-alignment measurements (Table 3): 0.75–0.77 for TSR vs. 0.64 for naive batches at B ≤ 5, degrading only where performance does.
  • Concern 2: Missing comparison with Tree-GRPO: We ran the experiments. At matched transitions the two are close on outcome reward alone. TSR is 5.5 / 7.2 points ahead with progress scoring, and the combination is best at 63.0 / 87.2 (Table 20).
  • Concern 3: Interaction with instance filtering: We ran the experiment. TSR gains 10.4 / 13.7 points with group selection held fixed and 12.0 with filtering removed (Table 30).

Each of the three questions was answered with a new experiment and strengthens TSR even more now.

3) Reviewer Z9ai:

  • Concern 1: Budget-matched baseline: We agreed, stated the rule, and rebuilt the compute claim on flat-selection controls: Best-of-64 at 4× is 4.1 / 6.3 / 7.8 points below beam search at 1× (Table 2).
  • Concern 2: Scoring signals and headline number: The scorers are observation-based. The abstract now attributes the 15 points to progress scoring and reports the search-only share, and the Monte Carlo compute is reported (8.9× / 15.6×).
  • Concern 3: Scope: Horizons reach 50 turns, a second model family is added, and the limits are stated.
  • Concern 4: Related work: We added a mechanism table (Table 5), a related-work paragraph in the introduction, and the new Tree-GRPO experiment.

We adopted both of the reviewer's main criticisms and believe the remaining points are addressed.

We believe the rebuttal has strengthened our contributions and has addressed the reviewers' concerns in full. With these additional results, we hope the reviewers reconsider their scores, and we ask the AC to weigh the new results when making a decision to ensure acceptance!

Thank you for your time! Best regards, Authors.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.