acceptodds
Under review as a conference paper at ICLR 2027

X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization

Abstract

Multi-step agents are trained on flat action streams: SFT and RLVR weight every token uniformly and ignore the sub-procedures that recur across tasks, the hierarchy that lets humans plan top-down from reusable routines. This structure sits unused, and flat training uses each scarce trajectory less fully than its content allows. Recent agents do use that structure, but only as LLM-written skills in context, never in the weights, so their gains do not generalize beyond retrieval. We instead recover this hierarchy from the data itself and train on it, with no LLM calls. Following text tokenizers, which build a vocabulary by counting alone, we score action spans by reusability and merge canonicalized actions into a reusable eXperience tree (X-Tree). Each X-Tree node captures how a frequent and success-bearing skill is composed from sub-skills, guiding efficient generalization. We integrate X-Tree into three training settings: offline RL, with each node as a training instance; online RLVR, with an adaptive skill bonus; and on-policy self-distillation, with X-Tree as the self-teacher's privileged context. Across WebArena, ScienceWorld, and WebShop at three model scales, X-Tree improves over standard recipes at matched data and budget by up to SR on WebArena, SR on ScienceWorld and success on WebShop. Matched analyses attribute the gains to the X-Tree structure and the three integrations.

Primary area:
reinforcement learning
Keywords:
Language Agents, Generalization, Learning from experience, Reinforcement Learning

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_Spe9OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes X-Tree, which aims to improve how efficiently multi-step agents use limited interaction experience. The method normalizes actions and, by combining occurrence frequency, fragment length, and success information, recursively constructs a reusable hierarchical skill library without relying on LLMs to generate skills. The authors further apply this approach to training examples in offline RL, additional rewards in online RLVR, and teacher context in self-distillation. Experiments on WebArena, ScienceWorld, and WebShop demonstrate that this approach improves agent performance across various settings and shows potential for replacing LLM-based skill generation with deterministic skill mining.

Critical strengths
  1. The author proposes the X-tree method as a plug-in, which has broad application prospects in modern machine learning problems.
  2. The experiments span multiple environments, model sizes, and another family of models, and include analyses of additional SFT training, full-trajectory RL, random fragments, random trees, and the number of rollouts, providing multifaceted evidence of the method’s effectiveness under various configurations.
Critical weaknesses
  1. In the WebShop settings, β=0\beta=0, causing the gate in Eq. 4 to remain constant at 1/21/2. When the teacher is fixed and the derivative is computed directly on the sampled trajectories, the gradient of the auxiliary loss no longer depends on the teacher’s probability; therefore, it cannot explain the performance differences resulting from changing the skill library, as shown in Table 23. The authors need to clarify the actual loss function and how gradients are handled, and explain their relationship with Eq. 4.
  2. Offline training uses only two rollouts per group. Under standard deviation normalization within the standard group, the advantage depends almost entirely on the reward ranking, and the completion and depth rewards in Eq. 2 do not alter this ranking. Therefore, the improvement ranging from 20.7 to 22.9 in Table 2 is difficult to explain directly by the described reward mechanism. It is necessary to clarify how the actual advantage is calculated and to verify whether this ablation experiment altered only the reward terms.
  3. On ScienceWorld G2, random trees with matched length and depth achieved 26.7, higher than X-Tree’s 25.6; in WebShop, shuffled skill texts still reached 76.5, close to the 77.1 achieved with complete texts. Furthermore, the teacher prompt included manually written task rules. These results suggest that gains may also stem from general fragment reuse, lexical prompts, or task knowledge.
Questions for authors
  1. Do WebArena’s three evaluations involve independent training seeds, or are they repeated runs of the same model in the same environment?
  2. Based on Eq. 3 and the parameters from ScienceWorld, does {0,12,1}\{0,\frac{1}{2},1\} in 5.2.1 actually refer to wgw_g? Additionally, is the reward multiplier of 10 in Table 7 of WebShop used for all relevant experiments? Could you note this consistently in the main text?
5 comments
AuthorsOpenReview ↗

Response to Reviewer Spe9 – Part I

Thank you for your constructive feedback. We clarify the WebArena evaluation protocol, report multiple training seeds result, correct the WebShop OPSD results and clarify the WebArena ablations. We also clarify the notation, the WebShop bonus multiplier, the random tree results on ScienceWorld and WebShop. All results reported here are by 3 training x 3 evaluation seeds. We will include these results and clarifications in the revision.

WebArena multiple training seeds result (Q1)

Common evaluation protocol in literature. In the submitted paper, the three WebArena evaluations are repeated passes of a single trained checkpoint per configuration (Appendix E.2). Go-Browse, our main baseline, reports one run per model with one greedy evaluation, as do WebAgent-R1 (Wei et al., 2025) and AgentGym (Xi et al., 2024).

Independent training runs. To address your concern about training-seed variance, we now report three independent training runs per configuration, each evaluated three times. X-Tree Full exceeds SFT-Full in all three runs, with a 3.8-point difference in mean normalized success rate. We will add multi-seed raining results of other settings in the revision.

Table Q1: WebArena results across independent training runs.

WebArena normalized SRRun 1Run 2Run 3Mean ± SD
SFT-Full18.418.818.218.5 ± 0.3
X-Tree OfflineRL integration22.922.521.622.3 ± 0.7 (+3.8)

Win-rate notation and the WebShop multiplier (Q2)

Win-rate notation. Yes, you are correct: 0,12,1\\{0,\tfrac12,1\\} are the possible values of the group win rate wgw_g, not the bonus weight λg\lambda_g, when n=2n=2. With ScienceWorld's λ0=0.75\lambda_0=0.75 and wref=0.4w_{\mathrm{ref}}=0.4, Eq. 3 gives λg(wg=0)=0.75\lambda_g(w_g=0)=0.75 and λg(wg=12)=λg(wg=1)=0.\lambda_g(w_g=\tfrac12)=\lambda_g(w_g=1)=0. We will clarify this point in Section 5.2.1.

WebShop multiplier. The factor of 10 in Table 7 multiplies the skill bonus used in all of the WebShop RLVR integration experiments. We will state the implemented coefficient explicitly alongside Eq. 3.

The OPSD objective and rerun on WebShop (W1)

Thank you for pointing this out. We acknowledge the mistake. With β=0\beta=0, the WebShop update is teacher-independent. We rerun the experiments with β=5\beta=5, the default gate sharpness in the released SDAR recipes (Lu et al., 2026), the same as in our ScienceWorld experiments.

The corrected runs use the same objective as Eq. 4, changing only the gate sharpness: L=LGRPO(Rout)+c∣y∣∑tgtδtL=L_{\mathrm{GRPO}}(R_{\mathrm{out}})+\frac{c}{|y|}\sum_t g_t\delta_t, where δt=log⁡πθˉ(yt∣stea)−log⁡πθ(yt∣sstu)\delta_t=\log\pi_{\bar\theta}(y_t\mid s^{\mathrm{tea}})-\log\pi_\theta(y_t\mid s^{\mathrm{stu}}), gt=σ(βδt)g_t=\sigma(\beta\delta_t), and c=0.01c=0.01. With this correction, our conclusion stays unchanged. Our X-Tree integration with OPSD, without any LLM calls, consistently exceeds outcome-only at all three scales and is comparable with LLM-written skill bank.

Table W1: Corrected WebShop OPSD results across model scales.

WebShop Success (%)1.5B3B7B
Outcome-only RLVR73.4 ± 1.375.0 ± 1.075.3 ± 2.0
LLM-written bank74.5 ± 1.8 (+1.1)77.6 ± 1.1 (+2.6)77.8 ± 0.4 (+2.5)
X-Tree bank76.2 ± 2.2 (+2.8)75.9 ± 1.3 (+0.9)79.1 ± 0.7 (+3.8)

Stop-gradients. In both ScienceWorld and WebShop, we follow SDAR: the teacher log-probabilities and gate are detached, so gradients flow only through the student log-probabilities. With β>0\beta>0, the teacher still influences the update through the gate’s value. ⁠

References

  • Gandhi and Neubig (2025), Go-Browse: Training Web Agents with Structured Exploration.
  • Wei et al. (2025), WebAgent-R1: Training Web Agents via End-to-End Multi-Turn Reinforcement Learning.
  • Xi et al. (2024), AgentGym: Evolving Large Language Model-based Agents across Diverse Environments.
  • Lu et al. (2026), Self-Distilled Agentic Reinforcement Learning (SDAR).
AuthorsOpenReview ↗

Response to Reviewer Spe9 – Part II

Clarification on WebArena Ablations (W2)

Thank you for pointing this out. We will clarify the ablation settings and ease your concern about the depth term. We will add these points in the revision.

Ablation settings. Only the Plain mixing experiment replaces the completion bonus with a fixed reward with other settings fixed. We acknowledge that the difference on this setting is only from training run variance. The other WebArena ablations (Table 2) change only the training data used by our offline RL method, or replace offline RL with SFT. They do not change the reward terms.

Depth term clarification. You are correct. We acknowledge that the WebArena Plain mixing–Full comparison does not establish the effect of the depth-scaled term. With n=2n=2, two unequal rewards yield advantages of +1/2+1/\sqrt{2} and −1/2-1/\sqrt{2}. The completion bonus preserves the step-matching ranking, yielding the same advantages. Therefore, we cannot attribute the reported gap to the depth term in this comparison. Since WebArena experiments are slow and costly, we will add an experiment with n=8n=8 on WebArena in the revision.

Depth term ablation. To ease your concern in the rebuttal with complementary evidence, we ablate the depth term at 1.5B with n=8n=8 rollouts on ScienceWorld: instead of scaling the bonus by node depth, we assign a fixed bonus across depths. The RLVR bonus from X-Tree is calculated the same way as the depth term in WebArena. Results shows that removing the depth term degrades the results by 0.8–1.0 points, while still improving the outcome-only RLVR.

Table W2: ScienceWorld depth-term ablation.

MethodG0G1G2
Outcome-only38.6 ± 2.5 (−1.2)36.2 ± 0.3 (−3.3)22.8 ± 1.3 (−2.8)
w/o depth term39.0 ± 1.2 (−0.8)38.5 ± 0.4 (−1.0)24.8 ± 1.7 (-0.8)
X-Tree39.8 ± 1.039.5 ± 1.725.6 ± 1.3

Clarification on the G2 gap in ScienceWorld (W3)

The G2 setting tests generalization to held-out task types, where patterns mined from the trajectory data naturally transfer less well. We therefore do not expect X-Tree to outperform a randomly merged tree in every held-out setting. However, X-Tree exceeds the matched random tree by +1.7 on G0 and +2.7 on G1. On G2, X-Tree still improves over outcome-only RLVR by +2.8.

Ablation study on WebShop OPSD (W3)

Scrambled-bank clarification. We clarify that the scrambled-bank is distinct from the randomly merged tree. Instead, it tests the sensitivity to how the X-Tree bank is rendered: we shuffle the actions within the X-Tree chains while preserving X-Tree vocabulary. For example, click<option-size>, click<option-color>, click<buy> could be shuffled into click<option-color>, click<option-size>, click<buy> which still presents the information as a prompt. The teacher prompt also includes a fixed task description. We conduct detailed ablations of the teacher context under the corrected OPSD implementation. We will clarify this clearly in the revision.

Ablation Study. To address your concern about the source of the WebShop OPSD gains, we compare the X-Tree bank with a randomly merged tree, X-Score merging over raw actions without canonicalization, a task-description-only context and a scrambled X-Tree bank.

At 1.5B, the task-description-only control is 2.2 points below the X-Tree bank, close to outcome-only RLVR. The randomly merged tree and raw-action control score 1.8 and 0.9 points below X-Tree, respectively, while the scrambled bank is 0.1 points lower. These results suggest that the gain is from the rendered X-Tree bank composed of the canonicalization, the merging and the rendering method, and that performance is relatively insensitive to the rendering method. We will add these results into the revision.

It’s worth noting that in other integrations, X-Tree exceeds the random tree ablation by 5.0 points (27.9% relative) on WebArena and by up to 2.7 points (7.3% relative) on ScienceWorld (Section 5).

Table W3: WebShop OPSD teacher-context ablations.

MethodSuccess (%)
Outcome-only RLVR73.4 ± 1.3 (−2.8)
OPSD: Task-description-only74.0 ± 1.1 (−2.2)
OPSD: Randomly merged tree74.4 ± 1.3 (-1.8)
OPSD: X-Score on raw actions, w/o canonicalization75.3 ± 0.6 (−0.9)
OPSD: Scrambled X-Tree76.1 ± 1.3 (-0.1)
OPSD: X-Tree bank76.2 ± 2.2
AuthorsOpenReview ↗

Kind request for feedback on our response

Dear Reviewer Spe9,

Thanks again for your insightful and helpful comments! In our response, we clarified the WebArena evaluation protocol, the WebArena ablations, the notation and bonus in WebShop and the random tree results on ScienceWorld and WebShop. We also reported multiple training seeds result of WebArena and corrected the WebShop OPSD experiments. We hope these had addressed all your concerns.

As the discussion period ends soon, we sincerely look forward to your feedback on our responses. We are happy to clarify anything further to improve our paper.

Authors of Submission 38615

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

The authors propose X-tree, a deterministic method for mining hierarchical "skills" from a pool of agent trajectories. The method works in two steps, beginning with canonicalisation where each action is mapped to a typed token verb⟨role⟩ using hand-written templates for each environment. Followed by a bpe-style merging where adjacent symbols are merged in the manner of BPE. The merge criterion is the X-Score, a product of pair frequency, span length, and the success rate of episodes containing the pair. Merging is gated by a compression constraint.

The resulting trees are used in three settings: (i) offline RL on WebArena. Each node becomes a GRPO instance. The policy is rolled out from the gold prefix and rewarded by step-matching plus a depth-scaled completion bonus. (ii) RLVR on ScienceWorld and WebShop and (iii) for on-policy self distillation.

Critical strengths
  1. Simple, reproducible, auditable abstraction. Mining is deterministic and needs no LLM calls. The resulting nodes are interpretable.

  2. Using the same mined structure as data, as reward shaping, and as privileged context is a clean framing.

  3. The paper includes random-span and random-tree controls, whole-trajectory RL, compute-matched SFT, rollout-budget scaling, resource-matched mining, mining-corpus size, a held-out-task mining corpus, and a scrambled-bank control for OPSD. Which I think is quite a broad coverage in terms of ablations.

  4. The paper reports per-cell standard deviations, paired t-statistics for WebShop, official vs normalized WebArena SR (Table 17), and a reproduction of the released Go-Browse checkpoint. It also lists the hyperparameters in full.

  5. The WebShop success-rate stratification (Table 14) is informative. Nodes that engage goal-named options succeed 81–97% of the time, universal macros sit at the 0.56 corpus mean, and pagination chains sit at 0.14-0.36. This gives a concrete reason why a success-weighted merge criterion could matter.

Critical weaknesses
  1. The paper does not show that its central contribution, the X-Score-mined hierarchy, is what produces the gains. The paper’s novelty over PRISE and Subwords-as-Skills is the merge criterion: success- and length-weighted merging instead of frequency-only BPE. Yet frequency-only BPE is never compared on the same canonicalized alphabet, and neither the success nor the length term is ablated. When controls do exist, they weaken the attribution rather than support it:

Random tree, ScienceWorld. On the held-out fold G2 it scores 26.7, above X-Tree’s 25.6 (Table 20).

Random tree, WebArena. It is shallower by construction (App. E.2), so it automatically gets less of the depth-scaled completion bonus. This confounds the 5.0-point drop.

Scrambled bank, OPSD (on-policy self-distillation). A word-scrambled X-Tree bank recovers about 80% of the gain over an empty context (76.5 vs 77.1 vs 74.2, Table 23). The rendered bank also includes a hand-written "Plan:" sentence that states the task rules.

Resource-matched runs, WebShop. When X-Tree is mined only from the warm-start data, the RLVR (reinforcement learning with verifiable rewards) gain falls to about +1 point in two of three settings (Table 4). This suggests the extra mining data, not the structure, accounts for much of the main-table gain.

  1. Most reported improvements lack statistical support, so perhaps the numbers cannot be relied on. For WebShop, the paper’s own paired t-statistics with n=3 (df=2) give p≈0.14p \approx 0.14 at 3B and p≈0.17p \approx 0.17 at 7B for the RLVR bonus. The 7B result is the reported +3.6 success headline. Then for ScienceWorld, no paired tests are provided, and the per-cell standard deviations are often as large as the effects. The +4.9 SR (success rate) at 7B is 56.7 ± 8.4 vs 61.6 ± 8.7. And in WebArena, the ± 0.6 used to argue robustness comes from three greedy evaluation passes of what appears to be one trained model per recipe. It therefore says nothing about training-seed variance, and the 1–2 point gaps between ablation rows in Table 2 are not shown to be real. This I believe also has attribution effects pointed out in 1.
Questions for authors
  1. X-Score vs. frequency-only merging (critical). Please report X-Tree mined with frequency-only BPE on the same canonicalized alphabet. Please also report X-Score without the success term and without the length term, at least for online RLVR (reinforcement learning with verifiable rewards) on ScienceWorld and WebShop. This is the comparison that separates X-Tree from PRISE and Subwords-as-Skills. If X-Score clearly beats frequency-only merging, my main concern about attributing the gains to the method would be resolved.

  2. Contribution of the extra mining data. In the resource-matched runs (Table 4), the gain falls to about +1 point in two of three settings. What fraction of the main WebShop and ScienceWorld gains do you attribute to the additional mining data rather than to the structure? Can the resource-matched comparison be extended to ScienceWorld?

  3. Training-seed variance. WebArena's ± 0.6 appears to reflect evaluation passes of one trained model. Please report variance across training seeds for the main recipes. Please also add paired tests for ScienceWorld and more seeds for the WebShop 3B and 7B cells.

  4. OPSD objective. With g_t treated as a constant, Eq. 4 only raises the likelihood of sampled tokens, and with β=0\beta = 0 on WebShop the teacher context seems to have no effect on the gradient. Which objective and stop-gradients are actually used in each environment?

7 comments
AuthorsOpenReview ↗

Response to Reviewer Z5tK – Part I

Thank you for the constructive feedback. We add frequency-only comparisons, extend the resource-matched experiment to ScienceWorld, and report training-seed results. We also clarify the random tree results, and report corrected WebShop OPSD results. We report here with mean over 3 training x 3 evaluation seeds. We will include the results and clarifications in the revision.

Comparison with Frequency-only BPE (Q1)

We understand the need to separate the effects of the success and length terms. To address your concern, we report additional 1.5B RLVR ablations.

Setup. We understand that the frequency-only BPE comparison aims to ablate the success and length term introduced in X-Score. However, we can not ablate both in all environments.

  • In ScienceWorld, all mining trajectories succeed, so removing success weighting has no effect. Therefore, we ablate the length term.
  • In WebShop, 808 of 1,824 mining trajectories fail. The action space and trajectory patterns are limited: 17 canonical action types, an average of 3.9 actions per episode and the top 10 of 95 distinct episodes cover 89% of the corpus. Removing length weighting changes only 3 of 48 skills, so we ablate success term in WebShop.

We also test merging raw commands without canonicalization to access the role of canonicalizing language-agent actions when extending the BPE-style merging to LLM tool calls.

Table Q1: ScienceWorld and WebShop RLVR mining ablations at 1.5B.

MethodScienceWorld G0ScienceWorld G1ScienceWorld G2WebShop successWebShop graded
Outcome-only RLVR38.6 ± 2.5 (−1.2)36.2 ± 0.3 (−3.3)22.8 ± 1.3 (−2.8)73.4 ± 1.3 (−3.9)88.0 ± 0.4 (−1.6)
w/o length term39.0 ± 1.7 (−0.8)37.8 ± 0.9 (−1.7)22.2 ± 1.4 (−3.4)––
w/o success term–––75.9 ± 0.2 (−1.4)89.0 ± 1.3 (−0.6)
w/o canonicalization38.2 ± 2.1 (−1.6)36.2 ± 3.5 (−3.3)25.7 ± 1.9 (+0.1)75.6 ± 0.1 (−1.7)88.5 ± 0.8 (−1.1)
X-Tree39.8 ± 1.039.5 ± 1.725.6 ± 1.377.3 ± 1.089.6 ± 0.4

Results. X-Tree exceeds the length-term ablation on all three ScienceWorld folds, by up to 3.4 points, and exceeds the success-term ablation by 1.4 points on WebShop success. The raw-command control is near outcome-only performance on ScienceWorld G0 and G1. These results support the canonicalization and measure of reusability to mine X-Tree.

Paper framing (Section 1). Our contribution is to make better use of a finite trajectory pool by mining reusable structure for language-agent training and integrating it into three training methods. The mining procedure extends BPE-inspired merging from tokens to tool calls. We do not claim BPE-inspired merging itself as a contribution. X-Score is a design choice within that procedure.

Contribution of the mining data (Q2)

To address your concern about the contribution of extra mining data, we extend our resource-matched experiment to ScienceWorld at 1.5B. We show that extra mining data is not required for a gain, while it can further improve results (Section 5.2.1). We change the trajectory pool to mine X-Tree with other settings fixed.

When mined from 200 SFT trajectories (the warm start data), X-Tree still exceeds outcome-only across all three folds by 1.0-1.7 points. Mining from the larger pool of 1,673 trajectories yields further improvements. Thus, additional mining data is not required for a positive mean gain in these experiments, although the larger pool helps.

Table Q2: ScienceWorld results by mining-pool size at 1.5B.

ScienceWorldMined fromG0G1G2
Outcome-only–38.6 ± 2.536.2 ± 0.322.8 ± 1.3
X-Tree200 SFT trajectories39.6 ± 0.8 (+1.0)37.9 ± 1.8 (+1.7)24.3 ± 1.2 (+1.5)
X-Tree1,673 trajectories39.8 ± 1.0 (+1.2)39.5 ± 1.7 (+3.3)25.6 ± 1.3 (+2.8)

It’s worth noting that on WebArena, our gain (+4.5 SR) is from exactly the same data in Table 1. On WebShop, we also show that X-Tree does not require additional data for the gain (Table 4, 5).

AuthorsOpenReview ↗

Response to Reviewer Z5tK – Part II

The OPSD objective and rerun on WebShop (Q4)

Thank you for pointing this out. We acknowledge the mistake. With β=0\beta=0, the WebShop update is teacher-independent. We rerun the experiments with β=5\beta=5, the default gate sharpness in the released SDAR recipes (Lu et al., 2026), the same as in our ScienceWorld experiments.

The corrected runs use the same objective as Eq. 4, changing only the gate sharpness: L=LGRPO(Rout)+c∣y∣∑tgtδtL=L_{\mathrm{GRPO}}(R_{\mathrm{out}})+\frac{c}{|y|}\sum_t g_t\delta_t, where δt=log⁡πθˉ(yt∣stea)−log⁡πθ(yt∣sstu)\delta_t=\log\pi_{\bar\theta}(y_t\mid s^{\mathrm{tea}})-\log\pi_\theta(y_t\mid s^{\mathrm{stu}}), gt=σ(βδt)g_t=\sigma(\beta\delta_t), and c=0.01c=0.01. With this correction, our conclusion stays unchanged. Our X-Tree OPSD integration, without any LLM calls, consistently exceeds outcome-only at all three scales and is comparable with LLM-written skill bank.

Table Q4: Corrected WebShop OPSD results across model scales.

WebShop Success (%)1.5B3B7B
Outcome-only RLVR73.4 ± 1.375.0 ± 1.075.3 ± 2.0
LLM-written bank74.5 ± 1.8 (+1.1)77.6 ± 1.1 (+2.6)77.8 ± 0.4 (+2.5)
X-Tree bank76.2 ± 2.2 (+2.8)75.9 ± 1.3 (+0.9)79.1 ± 0.7 (+3.8)

Stop-gradients. In both ScienceWorld and WebShop, we follow SDAR: the teacher log-probabilities and gate are detached, so gradients flow only through the student log-probabilities. With β>0\beta>0, the teacher influences the update through the gate’s value. ⁠

Clarification on the random-tree results (W1)

ScienceWorld. The G2 setting tests generalization to held-out task types, where patterns mined from the trajectory data naturally transfer less well. We therefore do not expect X-Tree to outperform a randomly merged tree in every held-out setting. However, X-Tree exceeds the random tree by +1.7 (G0) and +2.7 (G1). On G2, X-Tree still improves over outcome-only RLVR by +2.8.

WebArena. We thank the reviewer for pointing this out. We agree that the random tree’s shallower depth may affect the depth-scaled bonus, so the 5.0 point gap cannot be attributed to the merge criterion alone. However, in Table 2, we indeed includes the complementary controls:

  • Whole trajectory. It trains with the deepest possible unit, the top of any hierarchy. However, it scores 3.0 points below X-Tree.
  • Random span. This control retains X-Tree’s structure and depth distribution but replaces the nodes with randomly chosen spans. It matches the number of training instances and the depth (span-length) distribution, while changing the span boundaries. It scores 3.4 points below X-Tree.
  • Random tree. It keeps the canonicalization and the merge count, but it merges random pairs instead of the pairs X-Score selects. It scores 5.0 points below X-Tree.

These controls provide complementary evidence that the mining method of X-Tree matters. We will clarify these points more clearly in the revision.

Ablation study on WebShop OPSD (W2)

Scrambled-bank clarification. We clarify that the scrambled-bank is distinct from the randomly merged tree. Instead, it tests the sensitivity to how the X-Tree bank is rendered: we shuffle the actions within the X-Tree chains while preserving X-Tree vocabulary. For example, click<option-size>, click<option-color>, click<buy> could be shuffled into click<option-color>, click<option-size>, click<buy> which still presents the information as a prompt. The teacher prompt also includes a fixed task description. We conduct detailed ablations of the teacher context under the corrected OPSD implementation. We will clarify this clearly in the revision.

Ablation Study. To address your concern about the source of the WebShop OPSD gains, we compare the X-Tree bank with a randomly merged tree, X-Score merging over raw actions without canonicalization, a task-description-only context and a scrambled X-Tree bank.

At 1.5B, the task-description-only control is 2.2 points below the X-Tree bank, close to outcome-only RLVR. The randomly merged tree and raw-action control score 1.8 and 0.9 points below X-Tree, respectively, while the scrambled bank is 0.1 points lower. These results suggest that the gain is from the rendered X-Tree bank composed of the canonicalization, the merging and the rendering method instead of the task description alone, and that performance is relatively insensitive to the rendering method. We will add these results into the revision.

It’s worth noting that in other integrations, X-Tree exceeds the random tree ablation by 5.0 points (27.9% relative) on WebArena and by up to 2.7 points (7.3% relative) on ScienceWorld (Section 5).

Table W2: WebShop OPSD teacher-context ablations.

MethodSuccess (%)
Outcome-only RLVR73.4 ± 1.3 (−2.8)
OPSD: Task-description-only74.0 ± 1.1 (−2.2)
OPSD: Randomly merged tree74.4 ± 1.3 (-1.8)
OPSD: X-Score on raw actions, w/o canonicalization75.3 ± 0.6 (−0.9)
OPSD: Scrambled X-Tree76.1 ± 1.3 (-0.1)
OPSD: X-Tree bank76.2 ± 2.2
AuthorsOpenReview ↗

Response to Reviewer Z5tK – Part III

Training-seed variance and statistical claims (Q3, W2)

To address your concern about training-seed variance and statistical support, we report training-seed statistics on the three benchmarks.

Submitted protocol. The ScienceWorld results use three training seeds. WebShop and WebArena use one trained checkpoint per configuration, with repeated evaluations. The evaluation follows the protocol of common practice: GiGPO, RLVMR, iStar, CALM in ScienceWorld, Go-Browse, AgentGym, and WebAgent-R1. We will report multi-seed training results in the revision and release the models upon acceptance.

ScienceWorld. For each cell in Figure 3, we report the mean paired success-rate difference Δ\Delta from outcome-only and its 95% paired-tt confidence interval, using the three paired training runs. X-Tree has a higher mean in all nine cells. We will report the intervals in the revision. We acknowledge the high variance in ScienceWorld and will transparently report results across all environments. The WebShop and WebArena experiments provide complementary evidence supporting X-Tree’s effectiveness.

Table Q3a: ScienceWorld paired differences and 95% confidence intervals.

ScaleGroupOutcome-onlyX-TreeΔ [95% CI]
1.5BG038.6 ± 2.539.8 ± 1.0+1.2 [−3.3, +5.8]
1.5BG136.2 ± 0.339.5 ± 1.7+3.2 [−0.2, +6.7]
1.5BG222.8 ± 1.325.6 ± 1.3+2.9 [−3.0, +8.7]
3BG054.6 ± 6.056.4 ± 3.7+1.8 [−21.7, +25.3]
3BG148.8 ± 3.152.6 ± 5.6+3.7 [−17.5, +25.0]
3BG224.0 ± 3.826.2 ± 2.3+2.2 [−6.4, +10.8]
7BG056.7 ± 8.461.6 ± 8.7+4.9 [−35.9, +45.7]
7BG150.2 ± 3.653.1 ± 4.6+2.9 [−17.1, +22.9]
7BG221.7 ± 1.625.6 ± 1.5+3.9 [+0.8, +7.0]

WebShop. We report three independent RLVR training runs at each model scale (Please refer to Q4 for OPSD results). X-Tree has a higher mean success rate than outcome-only at all three scales.

Table Q3b: WebShop RLVR results across model scales.

WebShopSuccess: outcomeSuccess: X-TreeGraded: outcomeGraded: X-Tree
1.5B73.4 ± 1.377.3 ± 1.0 (+3.9)88.0 ± 0.489.6 ± 0.4 (+1.6)
3B75.0 ± 1.076.2 ± 0.4 (+1.2)88.6 ± 0.988.5 ± 1.0 (−0.1)
7B75.3 ± 2.079.1 ± 2.0 (+3.8)87.3 ± 2.190.2 ± 0.7 (+2.9)

WebArena. We report three independent training runs per main recipe, each evaluated three times. X-Tree Full exceeds SFT-Full in all three runs, with an average gain of 3.8 points. We will add multi-seed raining results of other settings in the revision.

Table Q3c: WebArena results across independent training runs.

WebArena normalized SRRun 1Run 2Run 3Mean ± SD
SFT-Full18.418.818.218.5 ± 0.3
OfflineRL with X-Tree22.922.521.622.3 ± 0.7 (+3.8)

References

  • Feng et al. (2025), Group-in-Group Policy Optimization for LLM Agent Training (GiGPO).
  • Lu et al. (2026), Self-Distilled Agentic Reinforcement Learning (SDAR).
  • Zhang et al. (2025), RLVMR: Reinforcement Learning with Verifiable Meta-Reasoning Rewards for Robust Long-Horizon Agents.
  • Liu et al. (2025), Agentic Reinforcement Learning with Implicit Step Rewards (iStar).
  • Wang et al. (2022), ScienceWorld: Is your Agent Smarter than a 5th Grader?
  • Gandhi and Neubig (2025), Go-Browse: Training Web Agents with Structured Exploration.
  • Xi et al. (2024), AgentGym: Evolving Large Language Model-based Agents across Diverse Environments.
  • Wei et al. (2025), WebAgent-R1: Training Web Agents via End-to-End Multi-Turn Reinforcement Learning.
Reviewer_SeXfOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes X-Tree to extract reusable action structures from existing trajectories without using an LLM to generate abstractions. It canonicalizes actions into typed symbols and recursively merges adjacent symbols using X-Score, which combines occurrence frequency, span length, and association with successful episodes. The resulting hierarchy enters training in three ways: as sub-trajectory training instances for offline GRPO with action-matching rewards; as an adaptive skill-completion bonus for online reinforcement learning; and as privileged teacher context for on-policy self-distillation.

Critical strengths

The paper offers a useful, reproducible alternative to LLM-written abstractions. The canonicalization and merge rules produce an inspectable hierarchy directly from labeled trajectories. This removes abstraction-model calls and makes the source of each mined structure traceable. It also avoids expensive and difficult-to-control generation pipelines.

Experimental results provide evidences that exploiting trajectory structure can improve training. Experiments cover WebArena, ScienceWorld, and WebShop across several model scales. The paper reports a 4.5-point normalized WebArena improvement over full-data SFT, consistent mean improvements from the online bonus in the main comparisons, and broadly comparable performance between mined and LLM-written teacher contexts.

Critical weaknesses

While the authors claim that self-distillation is one of the three headline integrations, there is a question about whether the stated update can produce the claimed mechanism. For instance, Table 7 sets the gate sharpness to β=0\beta=0 on WebShop, making gt=1/2g_t=1/2 in Equation 4. Under ordinary back propagation through the sampled-token loss, the authors need to explain whether its gradient depends on the teacher probabilities or privileged context.

The experiments provide evidence that exploiting trajectory structure can improve training, but they do not completely identify which structural choices matter. For example, regarding WebShop, both the canonicalization and reward incorporate whether actions match requested options. The rendered teacher context additionally contains an explicit hand-written plan stating the task rules. Table 23’s scrambled-text control retains most of the improvement: 76.5 versus 77.1 for the intact bank, compared with 74.2 for empty context. This leaves open how much benefit comes from the mined chains, supplied task knowledge, or vocabulary cues.

Questions for authors

What exact loss does the WebShop implementation optimize when β=0\beta=0? Does it include a teacher-dependent policy-gradient term or a full-distribution divergence omitted from Equation 4? For ScienceWorld, is the gate detached during differentiation?

Were held-out ScienceWorld task types excluded from every source of information, including SFT warm starts and mining, in the clean G2 experiment? Is the corresponding result available at scales beyond 1.5B?

For WebArena, do the reported three passes evaluate one trained checkpoint per configuration, or independently trained checkpoints?

How does X-Score compare with frequency-only BPE using the same canonicalizer, skill capacity, and downstream training? Separate removal of the length and success terms would clarify which part of the proposed score contributes.

4 comments
AuthorsOpenReview ↗

Response to Reviewer SeXf – Part I

Thank you for the constructive feedback. We clarify the OPSD objective and report the corrected WebShop results, clarify the G2-exclusion settings and extend it to 3B, report WebArena results across training seeds, and add comparisons with frequency-only BPE and further WebShop OPSD ablations. We report here with mean over 3 training x 3 evaluation seeds. We will include these results and clarifications in the revision.

The OPSD objective and rerun on WebShop (Q1, W1)

Thank you for pointing this out. We acknowledge the mistake. With β=0\beta=0, the WebShop update is teacher-independent. We rerun the experiments with β=5\beta=5, the default gate sharpness in the released SDAR recipes (Lu et al., 2026), the same as in our ScienceWorld experiments.

The corrected runs use the same objective as Eq. 4, changing only the gate sharpness: L=LGRPO(Rout)+c∣y∣∑tgtδtL=L_{\mathrm{GRPO}}(R_{\mathrm{out}})+\frac{c}{|y|}\sum_t g_t\delta_t, where δt=log⁡πθˉ(yt∣stea)−log⁡πθ(yt∣sstu)\delta_t=\log\pi_{\bar\theta}(y_t\mid s^{\mathrm{tea}})-\log\pi_\theta(y_t\mid s^{\mathrm{stu}}), gt=σ(βδt)g_t=\sigma(\beta\delta_t), and c=0.01c=0.01. With this correction, our conclusion stays unchanged. Our X-Tree OPSD integration, without any LLM calls, consistently exceeds outcome-only at all three scales and is comparable with LLM-written skill bank.

Table Q1/W1: Corrected WebShop OPSD results across model scales.

WebShop Success (%)1.5B3B7B
Outcome-only RLVR73.4 ± 1.375.0 ± 1.075.3 ± 2.0
LLM-written bank74.5 ± 1.8 (+1.1)77.6 ± 1.1 (+2.6)77.8 ± 0.4 (+2.5)
X-Tree bank76.2 ± 2.2 (+2.8)75.9 ± 1.3 (+0.9)79.1 ± 0.7 (+3.8)

Stop-gradients. In both ScienceWorld and WebShop, we follow SDAR: the teacher log-probabilities and gate are detached, so gradients flow only through the student log-probabilities. With β>0\beta>0, the teacher still influences the update through the gate’s value. ⁠

The setting in the G2-exclusion experiment (Q2)

In the G2-exclusion setting, we remove G2 task types from both the mining corpus and the SFT warm start. In contrast, the outcome-only and full-mining settings include four G2 task samples in the warm start. Despite having no G2 samples in its warm start, the exclusion setting achieves a higher mean success rate than outcome-only at both 1.5B and 3B. We will clarify this in the revision.

Table Q2: ScienceWorld G2 exclusion results.

ScienceWorld G2 SR (%)1.5B3B
Outcome-only22.8 ± 1.324.0 ± 3.8
Outcome + X-Tree bonus25.6 ± 1.3 (+2.8)26.2 ± 2.3 (+2.2)
G2 types excluded24.8 ± 1.2 (+2.0)25.5 ± 0.6 (+1.5)

WebArena multiple training seeds result (Q3)

Common evaluation protocol in literature. In the submitted paper, the three WebArena evaluations are repeated passes of a single trained checkpoint per configuration (Appendix E.2). Go-Browse, our main baseline, reports one run per model with one greedy evaluation, as do WebAgent-R1 (Wei et al., 2025) and AgentGym (Xi et al., 2024).

Independent training runs. To address your concern about training-seed variance, we now report three independent training runs per configuration, each evaluated three times. X-Tree Full exceeds SFT-Full in all three runs, with a 3.8-point difference in mean normalized success rate. We will add multi-seed raining results of other settings in the revision.

Table Q3: WebArena results across independent training runs.

WebArena normalized SRRun 1Run 2Run 3Mean ± SD
SFT-Full18.418.818.218.5 ± 0.3
X-Tree OfflineRL22.922.521.622.3 ± 0.7 (+3.8)

Release. We will release the models upon acceptance.

References

  • Lu et al. (2026), Self-Distilled Agentic Reinforcement Learning (SDAR).
  • Gandhi and Neubig (2025), Go-Browse: Training Web Agents with Structured Exploration.
  • Wei et al. (2025), WebAgent-R1: Training Web Agents via End-to-End Multi-Turn Reinforcement Learning.
  • Xi et al. (2024), AgentGym: Evolving Large Language Model-based Agents across Diverse Environments.
AuthorsOpenReview ↗

Response to Reviewer SeXf – Part II

Comparison with Frequency-only BPE (Q4)

We understand the need to separate the effects of the success and length terms. To address your concern, we report additional 1.5B RLVR ablations.

Setup. We understand that the frequency-only BPE comparison aims to ablate the success and length term introduced in X-Score. However, we can not ablate both in all environments.

  • In ScienceWorld, all mining trajectories succeed, so removing success weighting has no effect. Therefore, we ablate the length term in ScienceWorld.
  • In WebShop, 808 of 1,824 mining trajectories fail. The action space and trajectory patterns are limited: 17 canonical action types, an average of 3.9 actions per episode and the top 10 of 95 distinct episodes cover 89% of the corpus. Removing length weighting changes only 3 of 48 skills, so we ablate success term in WebShop.

We also test merging raw commands without canonicalization to access the role of canonicalizing language-agent actions when extending the BPE-style merging to LLM tool calls.

Table Q4: ScienceWorld and WebShop RLVR mining ablations at 1.5B.

MethodScienceWorld G0ScienceWorld G1ScienceWorld G2WebShop successWebShop graded
Outcome-only RLVR38.6 ± 2.5 (−1.2)36.2 ± 0.3 (−3.3)22.8 ± 1.3 (−2.8)73.4 ± 1.3 (−3.9)88.0 ± 0.4 (−1.6)
w/o length term39.0 ± 1.7 (−0.8)37.8 ± 0.9 (−1.7)22.2 ± 1.4 (−3.4)––
w/o success term–––75.9 ± 0.2 (−1.4)89.0 ± 1.3 (−0.6)
w/o canonicalization38.2 ± 2.1 (−1.6)36.2 ± 3.5 (−3.3)25.7 ± 1.9 (+0.1)75.6 ± 0.1 (−1.7)88.5 ± 0.8 (−1.1)
X-Tree39.8 ± 1.039.5 ± 1.725.6 ± 1.377.3 ± 1.089.6 ± 0.4

Results. X-Tree exceeds the length-term ablation on all three ScienceWorld folds, by up to 3.4 points, and exceeds the success-term ablation by 1.4 points on WebShop success. The raw-command control is near outcome-only performance on ScienceWorld G0 and G1. These results support the canonicalization and measure of reusability of X-Tree.

Paper framing (Section 1). Our contribution is to make better use of a finite trajectory pool by mining reusable structure for language-agent training and integrating it into three training methods. The mining procedure extends BPE-inspired merging from tokens to tool calls. We do not claim BPE-inspired merging itself as a contribution. X-Score is a design choice within that procedure.

Ablation study on WebShop OPSD (W2)

Scrambled-bank clarification. We clarify that the scrambled-bank is distinct from the randomly merged tree. Instead, it tests the sensitivity to how the X-Tree bank is rendered: we shuffle the actions within the X-Tree chains while preserving X-Tree vocabulary. For example, click<option-size>, click<option-color>, click<buy> could be shuffled into click<option-color>, click<option-size>, click<buy> which preserves the actions in the node. The teacher prompt also includes a fixed task description. We conduct detailed ablations of the teacher context under the corrected OPSD implementation. We will clarify this clearly in the revision.

Ablation Study. To address your concern about the source of the WebShop OPSD gains, we compare the X-Tree bank with a randomly merged tree, X-Score merging over raw actions without canonicalization, a task-description-only context and a scrambled X-Tree bank.

At 1.5B, the task-description-only control is 2.2 points below the X-Tree bank, close to outcome-only RLVR. The randomly merged tree and raw-action control score 1.8 and 0.9 points below X-Tree, respectively, while the scrambled bank is 0.1 points lower. These results suggest that the gain is from the rendered X-Tree bank composed of the canonicalization, the merging and the rendering method instead of the task description alone, and that performance is relatively insensitive to the rendering method. We will add these results into the revision.

It’s worth noting that in other integrations, X-Tree exceeds the random tree ablation by 5.0 points (27.9% relative) on WebArena and by up to 2.7 points (7.3% relative) on ScienceWorld (Section 5).

Table W2: WebShop OPSD teacher-context ablations.

MethodSuccess (%)
Outcome-only RLVR73.4 ± 1.3 (−2.8)
OPSD: Task-description-only74.0 ± 1.1 (−2.2)
OPSD: Randomly merged tree74.4 ± 1.3 (-1.8)
OPSD: X-Score on raw actions, w/o canonicalization75.3 ± 0.6 (−0.9)
OPSD: Scrambled X-Tree76.1 ± 1.3 (-0.1)
OPSD: X-Tree bank76.2 ± 2.2

Thank the authors for your responses and the additional experimental results, which have addressed my main concerns. I have raised my rating accordingly.

AuthorsOpenReview ↗

Thank you for your constructive feedback and positive recommendation

We sincerely appreciate your reconsideration and your decision to raise the score. We are glad that our clarifications and new experiments address your main concerns.

We also appreciate your recognition of the motivation, usefulness and experimental results of X-Tree. Your detailed comments led to clearer explanations of X-Tree mining and integration method, stronger experimental evidence, and more complete reproducibility details.

Thank you again for your careful review and constructive feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.