← 论文沉淀 / 🗂 Semantic ID ·2026-07 ·RecSys 2026

Beyond Fixed Depths and Widths: Optimizing Textual Decoding Tries in LLM-based Generative Recommendation

Jingzhe Liu, Hanbing Wang, Jiliang Tang, Liam Collins, Tong Zhao et al. (7 人)

Michigan State University × Snap Inc.

把 term ID（文本 ID）的设计问题从“词选得好不好”转成“它们拼出来的解码 trie 适不适合 beam search”：作者用 beam 存活率模型论证好 trie 需要两条性质：浅层分支因子小、叶子深度可变（ID 长度随物品语义丰富度自适应）。BONSAI 先用 LLM 从标题/描述里抽关键词，再在每个节点上用贪心最小集合覆盖选最少的共享词把物品切开、递归建树，配合 SFT + 在 trie 上做受限 beam search 的 GRPO，在 Amazon 三个子集上比 GRLM 高 16%~21.6%；只把 GRLM 的原有关键词按最小覆盖重排，也能涨 7.7%~9.1%。

Decoding Trie DesignVariable-Length Item IDsMinimum Set CoverTextual Term IDsBeam Survival Analysis

📝 我的备注

加载中…

核心思路

LLM 生成式推荐在推理时需要在候选物品 ID 构成的前缀树（trie）上做受限 beam search，才能保证生成的是合法物品。已有的 term ID（文本 ID）工作，比如 IDGenRec、GRLM、AgenticTagger，主要在优化“用哪些词描述物品”，trie 只是这些词拼出来的副产品。

这篇论文（Michigan State University × Snap）换了一个问题：如何同时设计 term ID 和它的解码 trie。作者得到两条结构性质：

ID 长度可变：Amazon 物品元数据长度从不到 10 个词到几百个词不等，所有物品统一 ID 长度，等于让 trie 的叶子都在同一深度，会压缩信息丰富的物品，也给简单物品加上没用的结构。
浅层分支因子要小：beam 在前几层选错路径后，后面无法挽回。GRLM 的 trie 第一层平均分支因子是 1114（Beauty）、2344（Sports）、2085（Toys）。预实验中，在“预测下一个物品类目”的任务上，分支因子从 6 增加到 12，Hit@5 持续下降。

方法 BONSAI（Branching-Optimized Node Structure for Adaptive Identifiers）的核心做法是：每个节点都选尽量少的共享关键词，把当前物品集合完全切开（最小集合覆盖），然后递归建树。这样分支因子被压到最低，深度又随物品的特征数自然变化。

整体实现思路

四个阶段：

特征过滤：用 Qwen3-32B 从标题和描述中抽取有信息量的关键词，只做抽取、不做改写。
建 trie：递归地用贪心最小集合覆盖切分物品集合，物品 ID 等于根到叶的关键词序列。
SFT：Qwen3-1.7B 学习“历史物品路径序列 → 下一物品路径”。
RL（GRPO）：在 trie 上做受限 beam search 产生 rollout，命中目标物品的任意合法路径得奖励 1，否则为 0。

理论部分把 trie 的 beam 正确率写成：

R(T) = Σ_i p_i · Π_{t=1..d(i)} φ_B(k_t(i)),   φ_B(k) = min(1, B/k)
Val(U, P) = φ_B(|P|) · Σ_j p(C_j)/p(U) · V(C_j),   V(U) = max_P Val(U, P)

定理 1：已知先验 p_i 时，用 Bellman 递归能得到全局最优树。
定理 2：先验未知时，在“每次切分 |P| ≥ B”和“各子集的后续价值差异有界（常数 ρ）”的假设下，贪心集合覆盖的切分能达到局部最优的 1/(ρ·α_U)，其中 α_U 是贪心覆盖与最小覆盖的大小比。
定理 3：等深树的最优值不超过任意树的最优值；如果补齐深度时至少有一层分支数大于 B，那么把变深树强行补成等深树会严格变差。

子模块实现（可复现细节）

1. 特征过滤（Feature Filtering）

抽取器：Qwen3-32B。提示词要求：只看标题和描述字段；词还原为原形；只保留和类目、功能、特征、卖点相关的词，去掉泛化或含糊的词；不输出任何解释。
不限制每个物品保留的词数，所以每个物品是一个变长特征集合。
只保留原文中出现过的词，不做 LLM 扩写或增强（与 GRLM、AgenticTagger 不同），以便把增益归到 trie 结构上。

2. Trie 构建（Algorithm 1 + 2）

Build(U):
  if |U| == 1: 建叶子; return
  P = GreedyCover(U)
  if P is empty: 每个物品用其唯一特征直接挂叶子; return
  建内部节点 U
  for C_j in P: 递归 Build(C_j)，挂为子节点
  未被覆盖的物品：用唯一特征挂叶子

GreedyCover(U):
  U_rem = U; P = {}
  while U_rem 非空:
    F* = argmax_F |F ∩ U_rem|      # 选覆盖未覆盖物品最多的共享特征
    C* = F* ∩ U_rem
    if C* 为空: break
    P += {C*}; U_rem -= C*
  return P

精确的最小集合覆盖可以用 CP-SAT 求解，但数据规模下代价太高，实际只用贪心。
工程降本：先按元数据类目切分物品，再在每个类目内分别建树。
防碰撞：有碰撞的 ID 末尾拼上标题首词。最终碰撞率：Beauty 3.38%、Sports 3.20%、Toys 3.81%。
一物多路径：论文称同一物品可能和不同物品组共享不同特征组合，因此可能有多条合法路径。叶子数为 Beauty 13,823 / Sports 31,306 / Toys 15,824，对应物品数 12,101 / 18,357 / 11,923。

3. 监督微调（SFT）

输入模板：The user has interacted with the following items in chronological order: <r1>, <r2>, ..., <rt>. Please predict the next item the user may prefer.，输出 <r_{t+1}>。
物品有多条路径时，用最长那条作为监督目标，以保留更细的语义。
L_SFT = -Σ_k log P_θ(y_k | x, y_<k)；lr 1e-4，余弦衰减。

4. 强化学习（GRPO on Beam Search）

对每个 prompt，在 trie 上做受限 beam search 得到 G 条候选路径（rollout beam size 10）。
奖励：R(y_g, Y*) = 1 if y_g ∈ Y* else 0，其中 Y* 是目标物品的所有合法 ID。
优势：A_g = (R_g - μ) / (σ + ε)；token 级 PPO-clip：L_RL = -1/G Σ_g Σ_k min(ρ_{g,k} A_g, clip(ρ_{g,k}, 1-η, 1+η) A_g)。
从 SFT ckpt 出发训练 1 个 epoch，lr 1e-6；硬件为 8×A100 80GB。
作用：让模型在真实解码条件下学习，同时把概率分到同一物品的所有合法路径上。

实验设置与结果

数据集（Amazon Review）：

数据集	用户	物品	交互
Beauty	22,363	12,101	198,502
Toys and Games	19,412	11,924	167,597
Sports and Outdoors	35,598	18,357	296,337

所有 LLM 方法统一使用 Qwen3-1.7B 骨干。

主结果（Recall@5 / Recall@10 / NDCG@5 / NDCG@10）：

方法	Beauty	Sports	Toys
SASRec	.0402/.0607/.0254/.0320	.0199/.0301/.0106/.0141	.0448/.0626/.0300/.0358
TIGER	.0405/.0623/.0267/.0337	.0215/.0347/.0137/.0179	.0337/.0547/.0209/.0276
HSTU	.0424/.0652/.0280/.0353	.0268/.0343/.0173/.0226	.0366/.0566/.0245/.0309
MiniOneRec	.0441/.0643/.0298/.0330	.0252/.0362/.0164/.0192	.0459/.0645/.0314/.0466
OneRec-Think	.0563/.0791/.0398/.0471	.0288/.0412/.0199/.0239	.0579/.0797/.0412/.0482
IDGenRec	.0484/.0693/.0337/.0404	.0270/.0388/.0185/.0223	.0595/.0800/.0432/.0498
GRLM	.0582/.0804/.0416/.0483	.0326/.0449/.0225/.0278	.0640/.0866/.0440/.0508
BONSAI	.0691/.0960/.0493/.0577	.0379/.0524/.0261/.0324	.0776/.1053/.0528/.0614
相对 GRLM	+18.7/19.4/18.5/19.5%	+16.4/16.8/16.0/16.5%	+21.3/21.6/20.1/20.8%

文本型 LLM GR（IDGenRec、GRLM）总体优于 SID 型（MiniOneRec、OneRec-Think），这与作者此前的 scaling 研究结论一致。

RL 的贡献：在 SFT 基础上 Recall@5 相对提升约 6%~10%。提升主要来自 ID 长度位于前 50% 的物品和有多条路径的物品，这两类物品大量重叠。

结构消融（只给了图）：

固定深度为 4，把最小覆盖换成每层固定选 3~7 个特征：分支数越多，三个数据集的 Recall@5 越低。
把原 trie 截断成 3~8 层的等深结构：越深越好，但都不如原始变深 trie。

迁移到 GRLM（只重排关键词顺序，不改词）：

数据集	方法	L1	L2	L3	L4	L5	提升
Beauty	原始	1114	5.39	1.70	1.12	1.04
Beauty	最小覆盖	375	15.80	3.72	2.05	1.65	8.9%
Sports	原始	2344	4.29	1.54	1.11	1.04
Sports	最小覆盖	508	15.32	3.59	1.90	1.57	7.7%
Toys	原始	2085	3.75	1.39	1.06	1.02
Toys	最小覆盖	373	15.89	4.55	2.60	1.74	9.1%

冷启动（每个数据集随机留出 500 个物品，从训练序列中删除，Recall@10）：

	OneRec-Think	GRLM	BONSAI
Beauty	0.028	0.032	0.038
Sports	0.016	0.018	0.022
Toys	0.028	0.034	0.038

扩展：骨干 0.6B→1.7B→4B→8B、Amazon-M2 数据 200K→1.6M 样本，BONSAI 都保持 Recall@5 最高（只给了图）。

思考与可参考价值

值得肯定的地方

迁移实验是全文最有说服力的部分：词完全不变、只改顺序，就有 7.7%~9.1% 的提升，说明受限 beam search 的第一层宽度确实是瓶颈。
方法简单：只是贪心集合覆盖，不需要训练 tokenizer，代码已开源。

需要警惕的地方

规模：只有 1~2 万物品的 Amazon 子集，没有线上实验。亿级商品库上的建树成本、深度分布和新品增量插入都没有讨论。
对比混杂：BONSAI 用了 GRPO，主表中的 GRLM 等基线是否也做了 RL 没有交代；“仅 SFT 已超过所有基线”这一说法没有给出数字。
一物多路径机制不清：Algorithm 2 的切分是不相交的，但正文说物品可以有多条路径；Sports 的叶子数是物品数的 1.7 倍，与表 4 标题“不显著增加”矛盾，多路径对 Recall 计算口径的影响也没说明。
宽度只是往下挪了：第一层从 1000+ 降到 300~500，但第二层从约 5 升到约 16，最优的深宽权衡没有给出原则。
理论偏弱：φ_B(k)=min(1,B/k) 相当于假设模型在子节点之间均匀猜，忽略了模型的置信度；定理 2 的 ρ、α_U 没有实测；定理 3 只证明了“补齐深度会变差”，并没有证明 BONSAI 的深度分配是最优的。

对电商生成式推荐 / SID 的借鉴

先诊断：统计自己的 SID 或 term ID trie 每层的平均分支因子，以及目标前缀在每层是否还留在 beam 中。RQ 第一层码本较大时（如 256 及以上），小 beam 下第一层很可能就是主要的掉点来源（推断）。
低成本改造：已有属性词或 term ID 时，可以先试按最小覆盖重排顺序，不需要重训词表，适合直接做 A/B。
变长 ID：在 SID 体系中，可以按簇大小或语义丰富度自适应地决定是否继续分层，替代固定 3 层或 4 层（推断）。
多路径 + RL：SID 碰撞或同一物品有多个版本 SID 时，可以借鉴“奖励任意合法路径”的 GRPO 做法。
上线前要确认：建树耗时与增量更新；多路径带来的 trie 膨胀；第二层变宽后 beam 宽度是否需要重调；先按类目切第一层的做法和线上类目体系是否一致。

📄 paper ⌬ code ← 回到沉淀