X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization

X-Tree. Tokenizing Reusable Experience for Efficient Agent Generalization. By Sitao Cheng and six others, from the University of Waterloo, Duke University, and one other institution. Published on the twenty-sixth of September. Its code repository is a placeholder: a readme, and nothing to run yet.

Agents that act in many steps are trained on flat streams of actions. SFT and RLVR weight every token the same, and they ignore the sub-procedures that keep recurring from one task to the next. That recurring structure is the hierarchy that lets people plan from the top down, out of routines they reuse. Left unused, it means each scarce trajectory is used less fully than its content allows, and trajectories are exactly the thing in short supply. Some recent agents do exploit the structure, but only as skills written by an LLM and placed in context. The skills never reach the weights, and so, the authors argue, their gains do not generalize beyond retrieval. An agent is only as good as the skills it manages to look up.

Here the hierarchy is recovered from the data itself, and the model is trained on it, with no LLM calls at all. The inspiration is the text tokenizer, which builds a vocabulary by counting alone. In the same spirit, action spans are scored by how reusable they are, and canonicalized actions are merged into a reusable eXperience tree, the X-Tree. Each node records how a skill that is both frequent and tied to success is composed out of smaller sub-skills. Like merged tokens in a vocabulary, larger routines are built from smaller ones, and the tree keeps that composition visible. That structure is meant to guide efficient generalization.

One tree, built once from the data, is then plugged into three quite different training settings. In offline RL, each node becomes a training instance of its own. In online RLVR, it supplies an adaptive skill bonus. And in on-policy self-distillation, the X-Tree serves as privileged context for the self-teacher, information the teacher sees that the student does not.

Experiments run on WebArena, ScienceWorld and WebShop, at three model scales, with data and budget matched against standard recipes. X-Tree improves on them by up to four point five percent success rate on WebArena, five point eight percent on ScienceWorld, and four point one percent success on WebShop. Matched analyses attribute those gains to two things together: the structure of the tree, and the three ways of integrating it.

Borrowing from tokenization is the move that makes this cheap. A tokenizer finds its vocabulary by counting, with no model consulted, and X-Tree finds an agent's reusable routines the same way, then writes them into training rather than into a prompt. The bet is that skills held in the weights will travel further than skills fetched from a library.