Tokenizing reusable experience
Instead of training agents on flat action sequences, we mine the reusable hierarchy latent in existing trajectories, with zero LLM calls, and use it to guide training as data, as reward and as context.
- Agent trajectories hide a reusable hierarchy. The same routines, such as filling two fields and submitting, or walking to the kitchen to fetch a thermometer, recur across tasks and sites, yet flat training relearns them each time.
- The hierarchy can be mined by counting, with zero LLM calls. X-Tree merges canonical actions by how reusable the result is, the way a tokenizer builds a vocabulary, so the tree is deterministic, auditable and reproducible.
- Training on the tree beats training on flat sequences, at the same data and budget. It works as data, as reward and as context: +4.5 SR on WebArena, +4.9 SR on ScienceWorld, and as good as an LLM-written skill bank.
The same routines, again and again
Flat training relearns every routine from scratch. SFT and RL weight every action the same, so a model learns “fill a date, fill a date, click apply” anew each time it sees it, on every site where it appears. Experience is expensive: every trajectory needs an environment, a task and a verifier that can be trusted, and none of that scales the way web text does.
The structure is already in the data. Below is a real WebArena trajectory with the tree mined from 7,974 Go-Browse trajectories. Its last three steps form the node S3, fill two fields and submit, which occurs 411 times in the corpus: as a date filter on the admin panel and as a route query on the map. With the navigation node before it, it forms S127, which filters a table by a date range. The explorer below opens on this trajectory with S127 selected: click fill_two_and_submit in the tree to highlight its three steps, or switch to ScienceWorld to see one node cover the whole trip to fetch the thermometer.
Merge depth
The tree drawing needs a wider screen. The bands, the merge stream and the node card show the same structure.
Counting, not prompting
A tokenizer for actions. Language models already solve a version of this problem before training starts: a tokenizer builds a vocabulary by repeatedly merging the pair that co-occurs most often. We apply the same idea to actions, with two changes.
First, actions are made comparable. Each raw action becomes a typed token such as type⟨date⟩ or click⟨button⟩, and the element ids and values move into slots, so two date filters on different pages read as the same symbol. Second, merges are chosen by reusability, not frequency alone. We score an adjacent pair by how often it recurs, how long the merged span is, and how often it appears in successful episodes. We call this score X-Score. A merge must also shorten the corpus by more than it costs. The merges stack into a tree: a reusable experience tree, or X-Tree.
Other agent systems ask an LLM to write skills instead. Those skills stay in the prompt, never enter the weights, and cannot be rebuilt from the data. X-Tree is deterministic, auditable, and trained into the model.
Why the tree helps training
As data, a node is a dense, graded target. With only trajectories and no environment, each node becomes an RL instance. The policy continues from the gold steps before the node and earns credit for every matched step, plus a completion bonus that grows with depth, instead of a single reward at the end of the episode.
As reward, the tree gives a signal when the verifier is silent. Early in RL, a group of rollouts often has no success, so outcome rewards are all equal and GRPO learns nothing. Every mined skill a rollout executes earns a bonus, which separates the rollouts. The bonus fades as successes appear.
As context, the tree tells the teacher which routine to follow. In on-policy self-distillation the model is its own teacher. Given a rendered X-Tree card, the teacher raises the tokens of the next routine step, and the student is pulled toward it on exactly those tokens. The card replaces the LLM-written skill bank such methods normally use.
The demo below walks through each integration on real tasks. The panel on the right is the hint: the part of the X-Tree the rollouts are matched against, in the same colors.
What we found
Offline RL: the tree drives the gain, not extra compute. On WebArena, with the same Go-Browse trajectories and no environment during training, offline RL with X-Tree raises success from 18.4% to 22.9%, a 24% relative gain. Two extra SFT epochs at the same compute add only 0.4 points. When we keep the RL stage and swap the tree for a random one with the same number of merges, the score falls below SFT. The gain comes from the structure, not from extra optimization.
Online RLVR: X-Tree helps at every scale, including held-out tasks. With a verifier, the adaptive bonus improves outcome-only GRPO at 1.5B, 3B and 7B: by up to 4.9 points on ScienceWorld tasks seen in training and up to 3.9 on held-out task types, and by up to 3.6 points of success and 4.6 of graded score on WebShop. The bonus helps most when reward is scarce. On ScienceWorld the gap is largest at four rollouts per prompt and narrows at sixteen, where the verifier already provides enough signal.
OPSD: a mined tree teaches as well as an LLM-written skill bank. As privileged context for self-distillation, the mined tree performs on par with a skill bank written by gpt-oss-120b on ScienceWorld and GPT-o3 on WebShop. At 7B it reaches 5.8 points over outcome-only RL on ScienceWorld, and its gain grows with model scale.
The tree does not need much data. One mined from 100 WebShop trajectories already beats the outcome-only baseline.
What is next
We mine the tree once from a fixed pool. Mining from the policy's own trajectories would let the tree and the policy improve together. We also use each integration on its own. Combining nodes as data, the bonus and distillation in one model is the obvious next step. And because the tree records which routines recur and which succeed, it also shows where a corpus is thin, which is where new trajectories are worth collecting.