X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization
Sitao Cheng, Xunjian Yin, Zhiyuan Sun, Yuxuan Li, Ruiwen Zhou, Xiangru Jian, Victor Zhong
cs.AI
2026-09-27
X-Tree merges canonicalized agent actions BPE-style into a reusable skill tree, plugged into offline RL, RLVR, and self-distillation; up to +4.5 SR on WebArena at matched budget.
Experience is the scarce resource in multi-step agent training. A trajectory is collected by humans or synthesized and verified by a model, and the environment, the tasks, and the verifier all cost real engineering, so nothing scales the way web text does. Standard recipes still treat a trajectory as a flat action stream: SFT and RLVR (reinforcement learning from verifiable rewards) weight every token equally, and recurring sub-procedures like 'fill two dates, click Apply' are never recognized as structure. The hierarchy is in the data; the objective ignores it.
Recent harnesses do use that structure, OpenClaw among them, by having an LLM summarize past experience into natural-language workflows that live in the prompt. That road is limited at both ends: skills stay out of the weights and die with retrieval, and the abstraction step costs LLM calls that are expensive, hard to control, and impossible to reproduce from the data alone. Hence the question: can the hierarchy be recovered from the trajectories themselves, without an LLM, and then trained on?
X-Tree applies the BPE tokenizer recipe to experience, in three steps:
The tree then enters training three ways. In offline RL (trajectories only, no environment), each node is one GRPO (group-relative policy optimization) instance: the policy partially rolls out from the gold prefix, rewarded for step matching plus a depth-scaled completion bonus. In online RLVR, an adaptive skill bonus rides on the outcome reward, at full weight when a group has zero successes and annealed to zero as the group win rate reaches a threshold; it supplies gradient while the verifier is silent and steps aside once the signal is dense. In OPSD (on-policy self-distillation), the self-teacher reads the same prompt plus retrieved X-Tree skills as privileged context, and a per-token gate pulls the student toward the teacher only on tokens the skills actually inform, replacing the LLM-written skill bank outright.
| Setting | Baseline | X-Tree | Gain |
| WebArena offline RL (Qwen2.5-7B, SR) | 18.4 (SFT-Full) | 22.9 | +4.5 |
| ScienceWorld online RLVR (7B, G1 SR) | 56.7 | 61.6 | +4.9 |
| WebShop online RLVR (7B, graded score) | 85.6 | 90.2 | +4.6 |
| ScienceWorld SFT integration (7B, G0+G1 SR) | 20.8 (per-action SFT) | 29.9 | +9.1 |
The WebArena number is a 24% relative gain; matching the RL compute with two extra SFT epochs moves SFT-Full by only 0.4, so the gain is not compute. The ablations are clean: swapping in random spans of matched count and length costs 3.4 points, a randomly merged tree costs 5.0 and lands below SFT-only, so the structure comes from X-Score; a binary trajectory-level reward costs 4.7, so step-level signal matters. On the online side, the bonus leads by 3.6 to 4.4 at n=4 rollouts and narrows by n=16, matching the design intent of acting only while the verifier is quiet; resource-matched runs that mine the tree from the SFT data itself still gain 1.0 to 3.2. In OPSD, the rendered X-Tree matches and mostly edges out skill banks written by gpt-oss-120b and GPT-o3, and at 7B sits 5.8 SR above outcome-only RLVR on ScienceWorld. The SFT integration spends 446 tokens per supervised action against 1,766 for per-action SFT and posts the largest gain in the table.
For agent training teams, this is an experience-reuse route that does not depend on LLM abstraction. The library is reproducible from the data, auditable (every node carries its success rate and occurrence count), and cheap: a tree mined from just 100 trajectories already beats the outcome-only baseline (75.2 vs 73.8 on WebShop). The three integrations cover the common regimes: offline RL without an environment, online RLVR with a verifier, self-distillation with a stable model. The gains are a few points, an incremental improvement, but the ablations argue cleanly that the structure itself, not extra compute or data, does the work.
The authors list three: the tree is mined once and never updated during training, so it cannot co-evolve with the policy; the three integrations are evaluated separately and never combined; and X-Tree only reorganizes existing experience rather than generating new trajectories. A few more caveats from the read. Canonicalization templates are hand-written per environment (accessibility-tree roles on WebArena, a nine-class keyword lexicon on ScienceWorld), an engineering cost the paper never stress-tests. The main WebArena table reports normalized SR rather than the official evaluator's score (21.5 vs 17.2 for the full recipe); the normalizer recovers 4 to 11 exact-match tasks per pass, a small but real protocol difference. Everything runs on Qwen2.5 and GLM-4 at 1.5B to 14B in three text-only environments; evidence for larger models or computer-use settings like OSWorld is absent, and the gain shrinks to +1.6 at 14B and +2.0 on GLM-4-9B, both below the +4.5 at 7B.