X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization

AI summary

Overview

Research area: Multi-step agent training — specifically how to extract reusable hierarchical structure from a fixed pool of agent trajectories and inject it into supervised fine-tuning, reinforcement learning with verifiable rewards (RLVR), and on-policy self-distillation (OPSD).

Technical level: Advanced. The paper assumes familiarity with reinforcement learning for language models (GRPO, RLVR, KL regularization), Byte-Pair-Encoding (BPE) tokenization, and privileged-context distillation.

Scope: The paper introduces a deterministic, LLM-free method for mining a hierarchy of reusable action sub-procedures ("X-Tree") from a trajectory corpus and shows that integrating it into three training recipes improves agent success rates across WebArena, ScienceWorld, and WebShop at three model scales.

What This Paper Is About

Multi-step agents are typically trained on flat streams of actions where every token receives equal weight, ignoring the sub-procedures that recur across tasks (e.g., browse-and-select or pick-up-and-move). Because verified agent experience is scarce and expensive to collect, this uniform treatment wastes signal that is already present in the data. The authors' goal is to recover that recurring hierarchy directly from the trajectory pool — with no LLM calls — and train on it so that a fixed amount of experience generalizes further.

Key Contributions

1. X-Tree: A deterministic, auditable miner that tokenizes reusable experience from a trajectory pool into a hierarchy of skills with zero LLM calls. Actions are first canonicalized into typed tokens (verb⟨role⟩), then adjacent pairs are recursively merged using a reusability score, the 𝒳-Score, which combines recurrence, length, and success rate. Each node captures how a frequent, success-bearing skill is composed from sub-skills.

2. Three training integrations of X-Tree, one per setting: (a) offline RL, where each X-Tree node is a training instance partially rolled out from a gold prefix; (b) online RLVR, where X-Tree contributes an adaptive skill bonus; and (c) OPSD, where X-Tree replaces the LLM-written skill bank as the self-teacher's privileged context. An SFT integration is also included in Appendix D.

3. Matched-data, matched-budget experiments across three environments (WebArena, ScienceWorld, WebShop) and three model scales (1.5B, 3B, 7B), showing improvements over standard recipes of up to 4.5% SR on WebArena, 5.8% SR on ScienceWorld, and 4.1% success on WebShop.

4. Ablations that isolate the source of the gain: replacing X-Tree with whole trajectories, random spans, or a random tree, and replacing the proposed offline RL objective with plain mixing, a depth curriculum, or a binary outcome reward.

Main Findings

• Offline RL on WebArena (Qwen2.5-7B): X-Tree Full reaches 22.9 SR across all 694 tasks versus 18.4 for the Go-Browse SFT-Full recipe, a gain of +4.5 SR, described as a 24% relative gain. Matching RL compute with two extra SFT epochs raises SFT-Full only to 18.8 (a 0.4 gain), so the improvement is not attributable to compute.

• Per-site gains are uneven and interpretable: admin improves the most at +6.4 SR, followed by gitlab at +5.2 SR and shopping at +4.9 SR. The margin shrinks on reddit, map, and wiki, which the authors attribute to those sites being driven mainly by query formulation rather than procedural execution.

• Both the tree structure and the RL method contribute. Against the full recipe, training on whole trajectories drops 3.0, a random span matching X-Tree's count and length histogram drops 3.4, and a random tree with the same number of merges (replacing 𝒳-Score with random) drops 5.0 — falling below SFT-only at 18.4. On the method side, plain mixing drops 2.2, a depth curriculum drops 1.7, a binary trajectory-level outcome reward drops 4.7, and SFT-Full with 2 and 4 epochs drops 4.5 and 4.1.

• Online RLVR on ScienceWorld: The adaptive X-Tree bonus is ahead of outcome-only GRPO on seen tasks (G0, G1) at all scales by up to 4.9% SR, and leads on held-out tasks (G2) at every scale by up to 3.9% SR.

• Online RLVR on WebShop: The adaptive bonus improves success by up to 3.6% and graded score by up to 4.6%, with the largest gap at 7B.

• The bonus helps most when the verifier is silent. In the rollout-number scaling study on ScienceWorld at 1.5B, the recipe is ahead in 11/12 cells. The gain is larger at smaller rollout size (3.6 to 4.4 at n=4) and narrows at larger n. Measured late-training λ_g exposure falls from 0.50 at n=2 to 0.18–0.26 at n=16.

• The gain is not from extra mining data. In resource-matched WebShop runs at 1.5B, X-Tree still improves over outcome-only at every warm-start size: 73.8 → 74.9 (+1.1) at 500 samples, 74.9 → 78.1 (+3.2) at 1,016 successes, and 76.4 → 77.4 (+1.0) at all 1,824 trajectories.

• Mining X-Tree does not require many trajectories. Re-mining from random corpus subsets gives success of 68.7 (50 trajectories, 9 skills), 75.2 (100 trajectories, 11 skills), 72.9 (200, 16), 74.4 (500, 24), and 76.5 (1,824, 48). The 100-trajectory X-Tree already exceeds the outcome-reward baseline with a 500-sample SFT warm start (75.2 vs 73.8), and the trend is not monotonic.

• OPSD with X-Tree matches LLM-written skill banks at zero LLM cost. Across both environments, generalization levels, and three model scales, the rendered X-Tree is comparable and ahead in most runs (by up to +3.7 on ScienceWorld and +1.7 on WebShop). The LLM-written banks used for comparison were produced by gpt-oss-120b (ScienceWorld) and GPT-o3 (WebShop).

• OPSD gains grow with model scale. At 7B, OPSD reaches +5.8 SR on ScienceWorld and +4.4 graded score on WebShop over outcome-only RLVR, while at 1.5B and 3B gains stay within a few points.

• Transfer and robustness checks: the offline recipe transfers to another model family (GLM-4) and a larger scale (14B) in Appendix E, and X-Tree remains robust when the mining corpus excludes the held-out tasks (Appendix F.5). X-Tree is also reported as useful as in-context advice (Appendix C).

Methodology in Plain English

The method borrows the idea behind BPE text tokenization — build a vocabulary by counting and merging the most frequent adjacent pair — and applies it to agent behavior, with two changes.

Step 1: Make actions comparable. Each raw action (excluding thoughts) is mapped to a typed token of the form verb⟨role⟩, where the role is the class or object the verb acts on. Values such as element IDs, dates, and object names are stripped, so structurally identical actions share a symbol and their recurrence becomes visible.

Step 2: Score candidate merges by reusability. Instead of ranking merges purely by frequency, the authors define the 𝒳-Score for a candidate merged pair: the number of times the pair occurs adjacently, times the candidate's length in primitive actions raised to p_ℓ, times the fraction of occurrences that lie in successful episodes (plus a smoothing term ε) raised to p_s. The exponents p_ℓ and p_s are set to 1. A merge is only performed if it actually compresses the corpus, governed by a threshold η, and merging stops when no pair passes or a cap is reached. The result is a tree whose leaves are canonicalized actions and whose internal nodes are compositions, each with a depth d_v.

Step 3: Train on the tree in three ways.

• Offline RL (no environment): each X-Tree node becomes one RL instance. The policy partially rolls out from the gold prefix preceding the node and is rewarded by a step-matching term plus a node-completion bonus scaled by depth, with α = 0.3 and γ = 0.5, optimized with GRPO.
• Online RLVR (environment and verifier available): the verifier reward is augmented with a bonus summed over the X-Tree nodes the rollout actually executes, weighted by λ_g = λ_0 · clip(1 − w_g/w_ref, 0, 1). The weight is at full strength when the verifier cannot separate rollouts and falls to zero once it can, using λ_0 = 0.75 and w_ref = 0.4 (ScienceWorld) or 0.85 (WebShop).
• OPSD: the same weights act as a self-teacher given retrieved X-Tree skills as privileged context, adding a gated per-token distillation term (coefficient c = 0.01) to the RL loss so the student is pulled toward the teacher only on tokens the skills inform.

Evaluation. WebArena uses Qwen2.5-7B-Instruct on 694 deterministic tasks with a 30-step cap and official reward; 256 skills are mined from 7,974 trajectories. ScienceWorld mines 80 skills from 1,673 trajectories and evaluates folds G0 (seen, n=1.6k), G1 (unseen variations, n=1.6k), and G2 (unseen tasks, n=0.5k, trained on 19 task types and evaluated on the remaining 10). WebShop mines 48 skills from 1,824 trajectories and evaluates success and graded score on 512 held-out episodes. RLVR and OPSD use Qwen2.5-Instruct at 1.5B/3B/7B with SFT warm starts from 200 (ScienceWorld) and 500 (WebShop) trajectories, reporting the mean over three seeds.

Why This Matters

The paper addresses a structural inefficiency rather than a scale problem: agent trajectories are scarce because each one requires a human annotator or a model plus a trusted verifier, and flat token-level objectives extract less from each trajectory than its content allows. X-Tree shows that the hierarchy humans rely on can be recovered from the data alone, deterministically and without expensive LLM calls, and then written into model weights rather than left in a prompt.

Real-world applications:

• Web and browser agents that automate multi-step site workflows (form filling, filtering, checkout), where procedure-intensive sites showed the largest gains.
• Scientific and laboratory assistants operating simulated or instrumented environments, where X-Tree led on held-out task types the model never trained on.
• E-commerce and shopping assistants that must satisfy multiple requirements per episode, where graded score — partial fulfilment — improved alongside full success.
• Low-resource agent domains that lack an online environment and verifier, where the offline RL integration trains from a collected trajectory pool alone.

Industry relevance: The approach targets the cost structure of agent training rather than raw capability. It requires no proprietary model in the loop, is reproducible from data plus code, runs at matched compute, and works from a mining corpus as small as 100 trajectories in the reported WebShop study — all relevant to teams with limited verified interaction data or restricted access to frontier models.

Future Directions

• Make the tree and the policy improve together. The authors note they mine X-Tree once from a fixed pool and never refine it; mining from the policy's own trajectories could let structure and policy co-evolve in a loop.
• Combine the three integrations. Each integration was evaluated in exactly one setting and they were never used together; training a single model simultaneously on X-Tree nodes, with the X-Tree bonus, and distilling from X-Tree at once is proposed as future work.
• Use the tree to direct data collection. Because X-Tree records which pairs recur and which succeed, it can mark where a corpus is thin and identify trajectories worth synthesizing to fill the gap.
• Test the limits of scale and transfer. The paper reports transfer to GLM-4 and 14B in an appendix; whether the structure survives larger models or harder hierarchical decompositions remains open.

Target Audience

Researchers and practitioners working on LLM agents, reinforcement learning for language models, and hierarchical skill discovery will get the most from this paper. It is also relevant to engineers building production web, shopping, or scientific agents who need to train from limited verified interaction data without paying for LLM-written skill abstractions, and to readers interested in the analogy between BPE-style compression and the discovery of reusable behavior.

Authors’ 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 4.5% SR on WebArena, 5.8% SR on ScienceWorld and 4.1% success on WebShop. Matched analyses attribute the gains to the X-Tree structure and the three integrations.