X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization
发表时间:2026-09-26
arXiv · HF 讨论 · alphaXiv① 一句话定位
X-Tree 把 agent 轨迹当作文本字符流来“分词”:它从轨迹池中确定性挖掘一棵可复用的 eXperience 树,节点是高频且成功承载的动作组合,全程不调用 LLM。论文的核心主张是,flat SFT/RLVR 把每个 token 同等加权,浪费了跨任务反复出现的子过程层级;X-Tree 恢复这一层级,并把它作为数据、奖励和上下文三种形态注入训练:offline RL(节点作为训练实例)、online RLVR(自适应技能奖励)、OPSD(自教师的特权上下文)。作者在 WebArena、ScienceWorld、WebShop 三个环境、三个模型规模上,以匹配数据与预算的对照,声称 X-Tree 稳定超过标准配方,并宣称收益来自树结构与三种集成设计。
② 背景与动机
多步 agent 通常在 flat action stream 上训练:SFT 和 RLVR 对每个 token 均匀加权,忽略了跨任务反复出现的子过程(如 browse-and-select、pick-up-and-move)和人类自上而下规划所用的层级结构。轨迹数据里存在这种层级,但训练目标没有利用它,导致每条稀缺轨迹被利用得不充分。经验本身很稀缺:轨迹由人类收集或模型合成并验证,环境要搭建、任务要编写、验证器要可信,这些都无法像 web text 一样规模化。已有工作有两种路线但都有缺陷:OpenClaw 等 harness 让 LLM 把过去经验总结为自然语言 workflow 并在上下文中回放,但知识没有压进权重,无法超越检索泛化;on-policy self-distillation(OPSD)把 LLM 写的技能作为自教师的特权上下文引入训练,但仍依赖 LLM 撰写抽象,昂贵、不可控且无法从数据本身复现。语言模型在文本上早已解决类似问题:基于共现的 BPE tokenizer 递归合并相邻字符对,构建结构化词表。本文把这一思想迁移到经验上,但做两处改造:先对动作做 canonicalization 以消除噪声,再用“可复用性”而非纯频率选择合并。相关工作包括 WebArena(Zhou et al., 2023)、ScienceWorld(Wang et al., 2022)、WebShop(Yao et al., 2022)、GRPO(Shao et al., 2024)、OPSD(Zhao et al., 2026; Lu et al., 2026)以及 ScienceWorld 泛化 fold(Zhang et al., 2025)。论文的空白是:没有方法能在零 LLM 调用下从轨迹池本身恢复层级并用它指导训练。
③ 方法机制
核心机制分两部分:X-Tree 挖掘(§3.1)和三种训练集成(§3.2–3.4)。 【X-Tree 挖掘】设轨迹 τ = a1…aT,带 episode 级成功标签,D 为目标域轨迹池。类比 BPE:文本 tokenizer 递归合并最频繁相邻对;本文对经验做两处改造。 1) Canonicalization:把每个 raw action(排除 thought)映射为 typed token `verb⟨role⟩`,role 是动词作用的对象类别。例如 `fill(bid,'2/2/26') ↦ type⟨date⟩`;element id、object name 等值被剥离但保留在 slots 中,做到确定性、完备、信息不丢失;Chain-of-Thought 从不进入字母表。ScienceWorld 上 object class c(·) 用九类关键词词典(door/instrument/paint/container/device/plant/animal/substance/location),因此“move thermometer to metal pot”和“move thermometer to ceramic cup”都成为 `put⟨container⟩`,而区别于“move thermometer to stove”。结构化相同的动作共享符号,使复发可见。 2) 𝒳-Score:衡量合并出的技能的可复用性。设 u、v 为相邻符号(各为 canonicalized action 或早先合并出的节点),候选 uv 合并二者。f_uv 是相邻出现次数,ℓu 是符号 u 展开成的 primitive action 数,succ(uv) 是 f_uv 中落在成功 episode 的比例。定义 𝒳(u,v) = f_uv · (ℓu+ℓv)^pℓ · (succ(uv)+ε)^ps pℓ、ps 默认取 1,ε=0.001 平滑成功率。因此“长、可靠、复发”的结构会超过“频繁但短或易失败”的 pair,这是纯文本 tokenizer 无法区分的。同时合并必须压缩语料:仅当 f_uv − 1 > η(ℓu+ℓv) 才合并,η 防止语料塌缩成少数巨大符号(WebArena 0.3,ScienceWorld/WebShop 0.5)。递归选择 𝒳-Score 最高的 pair 合并,直到没有 pair 通过压缩条件或达到技能 cap。结果是一棵确定性、可审计的树:叶子是 canonicalized action,内部节点是技能(skill),深度 d_v 比其较深子节点深一层。把 X-Tree 施加到一条轨迹得到 top-level tiling:分割成极大已挖掘技能,未覆盖位置保留为 primitive。X-Tree 因此是“reuse prior”:标记轨迹中哪些部分是复发、组合且成功承载的。 【集成一:Offline RL,每个节点一个 RL 实例】只有 D 没有环境,唯一信号是与 gold 轨迹一致。设节点 v 在标注轨迹位置 t 实例化,长度 ℓv、深度 dv。条件于 t 之前的 gold 动作与观测(prefix s_<t),策略最多生成 ℓv 步。match_j∈{0,1} 表示第 j 步是否复现 gold 动作(同 action 且同 element);若 match_j=1,拼接 gold 轨迹中第 j 步的观测,否则 rollout 停止,因此从不虚构观测。c_v = ∏ match_j,仅当节点每一步都匹配时为 1。GRPO 奖励为 r = (1−α)·(1/ℓv)·Σ_j match_j + α·(1+γ·d_v)·c_v α=0.3、γ=0.5。第一项是 step-matching reward(rollout 在 gold 路径上走了多远),第二项是带深度缩放的 node completion bonus(完成节点的奖励)。论文例:`date filter` 节点填两个日期并点击 apply(ℓv=3,dv=2);完整复现得满匹配分加深度缩放完成奖励,过早点击 apply 在第二步停止只拿 1/3 匹配分且无完成奖励。 【集成二:Online RLVR,自适应技能奖励】有环境和验证器。训练早期,一组 rollout 全失败时 GRPO 优势为零、无梯度;X-Tree 提供缺失的对比:执行更多已挖掘技能的 rollout 被区分出来,并在验证器自己变得有信息时下调权重。设 τi 为组 g 的第 i 个 rollout,R_out(τi) 为验证器奖励,matched(τi) 为动作序列出现在 τi 中的 X-Tree 节点(每 episode 只计一次),b_v 为执行节点 v 的奖励。w_g 是组内验证器判为成功的比例,w_ref 是阈值,λ_g 是奖励权重: r_i = R_out(τi) + λ_g·Σ_{v∈matched(τi)} b_v λ_g = λ0·clip(1 − w_g/w_ref, 0, 1) λ0=0.75;ScienceWorld w_ref=0.4、WebShop w_ref=0.85。没有 rollout 成功时 λ_g 满强度,一旦 w_g 达到 w_ref 就归零。b_v 按环境设计:ScienceWorld 用 b_v = 1 + γ·d_v,每 episode 授予一次;当两个技能嵌套时,外层只奖励其 b_v 与内部已奖励最大值的差,嵌套族贡献其最大成员的值而非求和。WebShop 用 b_v = s_v·k_v/T:语料成功率 s_v × 节点中对任务目标有帮助的步数 k_v,除以 episode 长度 T(表中 ×10)。帮助机制有三:i) λ_g 依赖组内 win rate,n=2 时取 {0,½,1};ii) 全失败组中 outcome 项抵消,组内梯度完全由 X-Tree 节点匹配驱动,保持训练存活;iii) 退火随能力而非步数。 【集成三:OPSD 特权上下文】OPSD 训练模型在自己的 rollout 上逼近一个“同样的模型 + 特权信息”的教师。设学生为 prompt s_stu 采样响应 y,教师用同一 prompt 前置检索到的 X-Tree 技能文本 s_tea,θ̄ 为教师冻结权重。逐 token 差距 δ_t = log π_θ̄(y_t|s_tea) − log π_θ(y_t|s_stu),置信门 g_t = σ(β·δ_t)(σ 为 logistic,β 为锐度):教师在技能文本下更自信的 token 上接近 1,学生更自信处接近 0,因此只在这些 token 上把学生拉向教师。目标在 RL loss 上加一项: L = L_GRPO(R_out) + c·(1/|y|)·Σ_t g_t·(log π_θ̄(y_t|s_tea) − log π_θ(y_t|s_stu)) c=0.01,ScienceWorld β=5、WebShop β=0。最小化该项会提升特权上下文认为更可能的 token 的学生概率。X-Tree 渲染为纯文本:每个节点一行,带成功率和出现次数,无 LLM 调用。 【训练与数据细节】WebArena:从 7,974 条轨迹挖 256 个技能,Qwen2.5-7B-Instruct,先在一半池上 SFT,再对另一半 X-Tree 节点做 GRPO(verl),评估 694 个确定性任务。ScienceWorld:从 1,673 条轨迹挖 80 个技能,200 条轨迹 SFT warm start,GRPO n=8、100 步,评估 G0/G1/G2。WebShop:从 1,824 条轨迹挖 48 个技能,500 条轨迹 SFT warm start,GRPO n=8、150 步,512 个 held-out episode 上评估 success 与 graded score。OPSD 与 RLVR 共享 X-Tree、SFT warm start 和评估;LLM 技能库为 ScienceWorld gpt-oss-120b、WebShop GPT-o3。所有 online 运行同规模同环境从同一 warm-start checkpoint 开始。
④ 实验与证据
论文在三个环境、三个模型规模上验证三种集成,全部在匹配数据与预算下与标准配方对比。WebArena 的 offline RL 实验显示,X-Tree 节点作为 RL 实例并配以 step-matching 与深度缩放完成奖励,显著超过 full-data SFT,且收益集中于过程密集站点;消融逐项替换树结构和奖励设计,表明增益同时来自 𝒳-Score 挖出的结构与 RL 方法。ScienceWorld 与 WebShop 的 online RLVR 实验显示,自适应 X-Tree 奖励在 seen 与 held-out fold、success 与 graded score 上一致领先 outcome-only GRPO,并且在验证器信号稀疏(rollout 组小)时帮助最大、信号密集时自动退火。资源匹配与少轨迹挖掘实验表明增益不是来自额外挖掘语料,少量轨迹即可。OPSD 实验显示 X-Tree 作为自教师特权上下文与 LLM 撰写的技能库相当,无需任何 LLM 调用。另有迁移性实验支持方法跨模型家族与更大规模有效。
-
WebArena 上 offline RL + X-Tree 在匹配数据与预算下取得对 Go-Browse full-data SFT 的相对收益。
offline RL with X-Tree reaches a 24 % 24\% relative gain over Go-Browse recipe (SFT-Full) (Table 1 , 22.9 22.9 vs 18.4 18.4 ).
-
offline RL 收益集中在过程密集站点,admin、gitlab、shopping 提升最大。
admin improves the most ( + 6.4 +6.4 SR), followed by gitlab, the most procedure-intensive site ( + 5.2 +5.2 SR), and then shopping ( + 4.9 +4.9 SR).
-
消融表明树结构本身贡献增益:整条轨迹、随机 span、随机树均低于 X-Tree。
Training on the whole trajectory with the same RL stage drops 3.0 3.0 . Random span matches the count and length histogram of X-Tree, which keeps the chunking but moves the boundaries, which drops 3.4 3.4 . A random tree with the same number of merges, which replaces 𝒳 \mathcal{X} -Score by random, drops 5.0 5.0 , below SFT-only ( 18.4 18.4 ).
-
offline 奖励设计同样重要:去掉深度缩放完成奖励(plain mixing 或 curriculum)会损失性能。
Plain mixing trains without completion bonus in Eq 2 , which drops 2.2 2.2 . Curriculum also removes the completion term and trains bottom-up by d v = 1 d_{v}{=}1 then 2 2 , …, which drops 1.7 1.7 .
-
轨迹级二值 outcome 奖励太稀疏,明显不如 X-Tree 的 step-matching + 完成奖励。
A binary trajectory-level reward drops 4.7 4.7 , showing that the outcome signal is too sparse to learn the multi-turn reasoning.
-
ScienceWorld online RLVR 上,X-Tree 奖励在 seen 与 held-out fold 上均领先 outcome-only GRPO。
On seen tasks (G0, G1), X-Tree integration is above outcome-only GRPO in all comparisons and scales well with model sizes (by up to 4.9 % 4.9\% SR). On held-out tasks (G2), X-Tree leads at every scale, by up to 3.9 % 3.9\% SR.
-
WebShop 上自适应 X-Tree 奖励同时提升 success 与 graded score。
The adaptive X-Tree bonus improves success (by up to 3.6 % 3.6\% ) and graded score (by up to 4.6 % 4.6\% ).
-
自适应奖励在验证器信号稀疏(小 rollout 组)时帮助更大,验证其设计窗口。
Our recipe is ahead in 11 / 12 11{/}12 cells. The gain is larger at smaller rollout size (from 3.6 3.6 to 4.4 4.4 at n = 4 n{=}4 ), where outcome-only GRPO receives less reward signal.
-
从少量轨迹挖掘的 X-Tree 仍有效,说明增益来自结构而非挖掘语料规模。
The 100-trajectory X-Tree is already above outcome reward with 500 sample SFT warm start ( 75.2 75.2 vs. 73.8 73.8 ). Success reaches 76.5 76.5 with full corpus, not monotonically in between, showing the robustness and efficiency of building X-Tree.
-
OPSD 中 X-Tree 作为自教师特权上下文与 LLM 撰写的技能库相当。
our rendered X-Tree is comparable to the LLM-written bank, ahead at most of the runs (by up to + 3.7 +3.7 on ScienceWorld and + 1.7 +1.7 on WebShop).
-
OPSD + X-Tree 的收益随模型规模增大,7B 上最明显。
At 7B, OPSD reaches + 5.8 +5.8 SR on ScienceWorld and + 4.4 +4.4 graded score on WebShop, while at 1.5B and 3B the gains stay within a few points.
-
offline X-Tree 配方可迁移到更大规模和另一模型家族。
On Qwen2.5-14B, our recipe adds + 1.6 +1.6 over full-data SFT. On GLM-4-9B, it adds + 2.0 +2.0 over the SFT-full recipe.
⑤ 审稿人视角
Novelty:核心新颖点是把 BPE“按共现合并”的思想迁移到 agent 经验,并引入成功感知的 𝒳-Score(复发 × 长度 × 成功率)与压缩门槛,得到零 LLM 调用的确定性技能层级。这比已有的 LLM 写技能库(只存在于 context)更“可训练”,比纯频率 tokenizer 更贴合强化学习信号。三种集成(作为数据、奖励、上下文)构成系统的“一次挖掘、多处使用”框架,其中离线节点即实例 + step-matching/深度完成奖励、在线自适应技能奖励的退火设计都有一定新意。但 GRPO、RLVR、OPSD 本身是借用组件,canonicalization 与技能库检索是手工模板,新意集中在前端挖掘与奖励塑形,属于方法组合式的创新而非范式突破。总体判断:novelty 中等偏上。 Soundness:实验设计大体严谨:同数据同预算对照、逐项消融(整条轨迹/随机 span/随机树/plain mixing/curriculum/二值 reward)、验证奖励窗口的 rollout 数扫描、资源匹配挖掘、held-out 语料重挖、跨模型家族与规模迁移、三 seed 均值。机制层面,λ_g 的动态分析和“全失败组中 outcome 项抵消、梯度由技能匹配驱动”的解释清楚。但仍有关切:只覆盖三个模拟环境,泛化证据有限;X-Tree 挖掘依赖 episode 级成功标签,成功标签噪声会直接进入 𝒳-Score;canonicalization 是每个环境手工编写的模板,可能把设计者先验藏进“从数据挖掘”的叙述中;WebArena 采用归一化 SR 与官方 SR 并列,二者有差异;OPSD 对 LLM 库的优势较窄,部分比较接近持平;统计检验主要在附录,正文多给点估计。总体上方法推导与消融内部一致,soundness 尚可,但外部效度与部分基线结论需要更谨慎解读。 Significance:针对“有限经验下高效训练多步 agent”这一真实瓶颈,提出不依赖 LLM、可审计、可复现的技能挖掘与三路集成,工程上可直接接入 verl/GRPO/OPSD 管线,实用性较高。若方法在更多环境成立,它有潜力降低对 LLM 撰写技能库的依赖,并让离线轨迹被更充分利用。但当前收益幅度中等,且未展示跨域复用同一棵树或三集成联合使用,限制了“通用经验 tokenizer”这一叙事的分量。对社区的意义更多是提供了一个清晰、可扩展的“经验结构化 + 训练集成”模板和一批可对照的消融结论,而非颠覆性提升。总体 significance 中等。
⑥ 局限与保留意见
论文自陈的局限:X-Tree 从固定池挖掘一次,未随训练或策略自身 rollout 迭代改进;三种集成只在各自 setting 中评估,从未组合成单一模型;X-Tree 只重组已有经验,不能创造新技能;它记录哪些 pair 复发、哪些成功,从而标记语料稀薄处,可用于指导轨迹合成,但本文未做。其他可指出的局限:canonicalization 模板是每环境手工编写,跨环境需要重新设计,且剥离值(element id、object name)保留了信息但技能本体仍是类型级,实例级泛化依赖前缀与检索;挖掘需要 episode 级成功标签,失败轨迹中的潜在好子过程只能通过成功率平滑间接利用;CoT 被排除在字母表外,可能丢失可复用的推理子程序;WebArena 评估混合官方 SR 与归一化 SR,绝对数字的横向可比性需谨慎;OPSD 的增益依赖基础模型读懂技能文本,小模型上优势有限;统计显著性与误差棒主要在附录,正文结论以点估计呈现。
⑦ 值得跟进
最直接的方向是闭环挖掘:从策略自身 rollout 中不断重挖/更新 X-Tree,让结构与策略互相提升,并验证结构是否随训练进化出更高层技能。其次是把三种集成合并到单一模型(用 X-Tree 节点做离线数据、同时加自适应奖励、再以 X-Tree 为 OPSD 特权上下文),检验信号是否叠加。第三是跨环境/跨域共享或迁移 X-Tree:一棵树能否作为多任务 agent 的通用动作原语库。第四是用 𝒳-Score 的“复发但低成功”区域反向定位语料缺口,指导轨迹合成与主动数据采集。第五是扩展 canonicalization 到含推理/思维链的 span,把可复用“思考-动作”子过程也纳入树。第六是改进 OPSD 的检索与渲染(当前为关键词规则与固定模板),引入更精细的 retriever 或可学习嵌入。最后,为 𝒳-Score 的压缩/最优合并提供理论刻画,并在更长时程、更真实的 agent 基准上做规模化验证。