Multi-step AI agents are typically trained on flat action streams, where supervised fine-tuning and reinforcement learning with verifiable rewards weight every token equally. This approach ignores the recurring sub-procedures that appear across tasks — the kind of reusable hierarchy humans rely on when planning top-down. According to a new paper, X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization, that structure sits unused, and flat training uses each scarce trajectory less fully than its content allows.
Existing agents that exploit such structure do so only as LLM-written skills kept in context, never in the model weights, so their gains do not generalize beyond retrieval. X-Tree instead recovers the hierarchy directly from the data and trains on it, with no LLM calls. Inspired by text tokenizers that build a vocabulary by counting alone, the method scores action spans by reusability and merges canonicalized actions into a reusable eXperience tree. Each node captures how a frequent, success-bearing skill is composed from sub-skills.
The authors integrate X-Tree into three training settings: offline RL, where each node becomes a training instance; online RLVR, with an adaptive skill bonus; and on-policy self-distillation, where the tree serves as the self-teacher's privileged context. The paper reports gains over standard recipes at matched data and budget of up to 4.5% success rate on WebArena, 5.8% on ScienceWorld, and 4.1% success on WebShop, across three model scales.
Matched analyses attribute the improvements to the X-Tree structure and the three integrations. The authors describe the tree as deterministic, auditable, and reproducible, and note that it can act as data, as reward, and as context — with the context variant performing as well as an LLM-written skill bank.