X-Tree mines a hierarchy of reusable skills from agent trajectories using only frequency and success counts (no LLM call), then injects that hierarchy into training as data, as reward bonus, or as privileged context, improving sample efficiency over flat SFT and outcome-only RL at matched budget.
You’re training an LLM agent to click through websites or run science experiments. You have a few thousand trajectories, each one hard-won: a human recorded it, or a stronger model generated and a verifier checked it. Standard practice is Supervised Fine-Tuning then RL with verifiable rewards, and both weight every action token equally. If the trajectory contains a recurring sub-procedure like “fill two date fields and click Apply,” the training signal does not know that chunk is a reusable unit; it just sees 3 of N tokens.
Recent agent harnesses (the paper names AWM and similar systems) try to recover this hierarchy by asking a strong LLM to summarize past episodes into natural-language “skills” that get pasted into the prompt at inference. That costs LLM calls, the skill library is not reproducible from the data, and nothing lands in the weights, so the skills do not generalize beyond retrieval.
The core move: treat an action stream the way Byte-Pair Encoding treats a character stream. Start from a vocabulary of primitive actions, then greedily merge the adjacent pair that is most “worth” merging, repeat, and you get a tree whose internal nodes are composite skills.
Two differences from text BPE. First, raw actions are canonicalized before mining: fill(bid, '2/2/26') becomes type<date>, so structurally identical actions share a symbol. Second, merges are scored not by raw frequency but by a reusability score called 𝒳-Score. In plain English: a pair is worth merging if it recurs often, if it is long (so merging compresses more), and if it tends to appear in successful episodes. The score multiplies these three factors.
A compression constraint prevents the corpus from collapsing into a few giant symbols. The result is the X-Tree: a deterministic, auditable hierarchy where each node is a frequent, success-bearing composite skill, built with zero LLM calls.
vocab = canonicalize_actions(trajectories) # verb<role> tokens
while True:
pairs = adjacent_pairs(corpus)
scores = {(u,v): freq[uv] * (len_u+len_v)**p_l * (succ_rate(uv)+eps)**p_s
for (u,v) in pairs}
best = argmax(scores)
if not compresses_enough(best) or len(vocab) >= cap: break
merge(best); vocab.add(best)
return tree_of_merges
The X-Tree then plugs into training three ways. Offline Reinforcement Learning (no live environment): each tree node becomes one RL training instance. The policy rolls out from the gold prefix just before the node and is rewarded for matching the gold actions, with a bonus for completing the whole node scaled by its depth. Optimized with Group Relative Policy Optimization (GRPO). Online RLVR: add a per-rollout bonus for each X-Tree skill the rollout actually executed, weighted by an adaptive coefficient that is strong when the verifier gives no signal (early training, no successes in the group) and fades to zero once the verifier can discriminate. On-Policy Self-Distillation: a self-teacher reads retrieved X-Tree skills as privileged context and distills into the student at the token level. This replaces the usual LLM-written skill bank.
Evaluated on three environments at Qwen2.5 scales 1.5B / 3B / 7B, each result averaged over three seeds. Comparisons are matched for data and compute.
•
Offline RL on WebArena (7B): X-Tree reaches 22.9% SR versus the Go-Browse SFT baseline at 18.4%, a +4.5 gap. Extra SFT epochs to match compute only move SFT to 18.8%, so the gain is not from compute. Ablations isolate the source: replacing X-Tree with random spans of matched length drops to 19.5, a random tree drops to 17.9 (below SFT), and training on the same X-Tree nodes with a binary outcome reward drops to 18.2. Both the structure and the depth-scaled completion reward matter.
•
Online RLVR on ScienceWorld and WebShop: the adaptive X-Tree bonus beats outcome-only GRPO at every scale, by up to +4.9 SR on ScienceWorld (including held-out task types) and up to +3.6 success / +4.6 graded score on WebShop. The gain is largest at smaller rollout counts, where the verifier signal is sparse, and shrinks as rollouts grow. The adaptive weight does fade to near zero as win rates rise, matching the design.
•
OPSD: using the X-Tree rendering as the teacher’s privileged context performs comparably to an LLM-written skill bank (built by gpt-oss-120b on ScienceWorld, GPT-o3 on WebShop), ahead in most cells by up to +3.7 SR, with no LLM calls.
•
Mining is cheap: an X-Tree built from only 100 trajectories already beats outcome-only RL on WebShop at 1.5B.
Behavioral analysis on the trained policy shows the X-Tree bonus does not increase the number of skills executed per episode. It shifts mass toward deeper, longer composites (mean executed skill depth rises from 2.11 to 2.39). The authors read this as the policy stitching atomic skills into longer procedures.
•
If you are training a multi-step agent with Supervised Fine-Tuning plus RL with verifiable rewards and have a modest trajectory pool, X-Tree is a drop-in way to extract more signal without buying more data. The mining step is deterministic and does not require an LLM. The paper’s code is on GitHub.
•
If your environment has a strong, dense verifier and plenty of rollouts, the adaptive bonus is designed to fade out, so expect smaller gains. Where it helps is early training, small rollout groups, or sparse-reward settings. Worth testing when GRPO groups frequently have zero successful rollouts.
•
If you have trajectories but no live environment, the offline-RL integration (each node as an instance, step-matching reward with depth-scaled completion bonus) is the setup that produced the +4.5 WebArena result and is the most differentiated contribution from standard SFT.
•
If you were considering an LLM-written skill library for in-context use, the OPSD result suggests the deterministic X-Tree rendering is a reasonable substitute at zero inference-time LLM cost, at least for ScienceWorld and WebShop with the paper’s rendering template. Worth benchmarking against your current skill-mining pipeline.
•
Building the canonicalizer is per-environment work: you write a template that maps raw actions to verb<role> tokens. The paper gives full templates for its three environments in appendices.
•
X-Tree is mined once from a fixed pool and never updated during training. The authors flag a closed-loop version (mine from the policy’s own rollouts) as future work.
•
The three integrations are evaluated separately, never combined.
•
Canonicalization requires per-environment engineering. Quality of the role lexicon affects which patterns are mergeable.
•
Gains on OPSD depend on model scale: at 1.5B and 3B the margin over outcome-only RLVR is within a few points; the larger +5.8 SR gap appears at 7B, where the base model can better follow the skill text.
•
WebArena numbers are on the 694 deterministic (non-fuzzy) tasks of the 812-task set, scored with a normalization pass. Comparisons to published WebArena numbers from other papers may use the full set or a different harness.
•
The method reorganizes existing experience; it does not synthesize new trajectories to fill gaps in a thin corpus.