- 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
- 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?
- 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
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):
| Environment | Max turns | Mean turns (IF / TSR) | IF | TSR beam |
|---|---|---|---|---|
| Sokoban | 5 | 4.1 / 3.6 | 43.7 | 52.3 |
| FrozenLake | 5 | 3.6 / 3.1 | 48.7 | 60.7 |
| WebShop | 10 | 6.8 / 5.8 | 70.3 | 85.3 |
| ALFWorld | 50 | 21.6 / 18.3 | 69.8 | 84.7 |
| AppWorld | 50 | 36.2 / 32.4 | 20.4 | 31.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-Instruct | FrozenLake | WebShop |
|---|---|---|
| Instance filtering | 39.8 ± 2.1 | 58.4 ± 1.9 |
| TSR beam | 49.6 ± 1.8 | 71.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):
| Method | Branch trigger | Pruned by | Policy trains on | Update rule changed |
|---|---|---|---|---|
| Tree-GRPO (Ji et al.) | random agent-step nodes | nothing | all branches | yes: intra- + inter-tree advantage |
| ARPO / AEPO (Dong et al.) | high-entropy tool-call steps | nothing | all branches | yes: advantage attribution; AEPO also clipping |
| LATR (Xing et al.) | uncertain tokens, single-turn | near-duplicate continuations | remaining diverse branches | no |
| PATR (Li et al.) | process score at periodic checkpoints | low-scoring branches stopped early | completed and early-stopped branches | no |
| TSR (ours) | every turn, every executed candidate scored | estimated return | search survivors only | no |
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-3B | Expansion | Trains on | Prefix scorer | Budget | FrozenLake | WebShop |
|---|---|---|---|---|---|---|
| Instance filtering | none | all sampled | none | 1× | 48.7 ± 1.9 | 70.3 ± 1.8 |
| Tree-GRPO [new] | random | all branches | none | 2× | 55.2 ± 1.5 | 78.1 ± 1.5 |
| Tree-GRPO + selection [new] | random | top 16 by return | none | 2× | 57.3 ± 1.4 | n/a |
| TSR beam | scored, per turn | survivors | task reward only | 2× | 53.4 ± 1.5 | 75.9 ± 1.4 |
| TSR beam | scored, per turn | survivors | progress | 2× | 60.7 ± 1.2 | 85.3 ± 1.1 |
| TSR beam + tree advantages [new] | scored, per turn | survivors | progress | 2× | 63.0 ± 1.1 | 87.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
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):
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."
Continued in the next comment