PSG: Pair-Space Generation for Efficient Generative Reranking

1. 问题与动机

工业推荐的重排阶段接收上游召回与排序给出的 n 个候选，输出长度为 L 的有序列表。目标并非逐物品分数之和，而是包含互补、冗余、位置级联、参与度和商业价值的列表效用；完整解空间大小为 n!/(n-L)!，无法穷举。Generator-Evaluator（G-E）框架让生成器从组合空间采样多条列表，再由评估器按列表级奖励选出最优结果，比逐点模型更能探索物品间作用。

问题在于，G-E 的自回归生成器必须连续作出 L 次决策，而评估器直到整条列表完成后才返回一个标量。论文把后果分成两类：第一，线上生成器总预算通常不超过 30 ms，L 约为 3–8，即使有 KV cache，逐步解码仍占据显著延迟；第二，训练采用 teacher forcing，推理却依赖模型自己先前生成的 token，前序错误会沿长轨迹放大。非自回归方法虽然并行，但忽略用户按顺序浏览列表的依赖关系，论文实验中的 NAR4Rec、JDRec 等也没有消除精度损失。

作者的关键观察是，重排效用的自然单元常常不是单个物品，而是物品之间的相互作用。因此，将动作原子从一个物品提升为一个有序物品对，可能在不缩小原列表解空间的情况下把决策步数减半。这项工作要回答三个具体问题：pair token 是否会损失表达能力；每请求 n(n-1) 个动态 token 是否能在工业延迟内计算；缩短轨迹后，速度和误差累积的理论收益能否在公开数据与快手线上流量中兑现。

2. 方法详解

2.1 Pair-space tokenization 与等价性

当 L 为偶数时，PSG 为当前请求构造有序词表 P(V)={(v_i,v_j): i≠j}，大小是 n(n-1)，然后只生成 L/2 个 pair token；每个 token 再确定性展开成两个连续物品。奇数 L 则在末尾保留一个单物品槽位。论文证明 item-space 与 pair-space 的列表集合存在双射：任意原始排列都能唯一切成连续物品对，任意合法 pair 序列也能还原成同一排列。更进一步，可令 pair 概率等于两个原始条件概率的乘积，使 L/2 步的乘积恰好望远镜式还原 L 步概率，因此两类自回归策略可表达的列表分布相同。

这不是把所有物品对做成全局静态 embedding。每个物品先由内容向量、统计特征和类目 ID 得到 e(v)，再加入两个不同的角色向量 p1、p2，并通过 MLP 融合：e(v_i,v_j)=MLP([e(v_i)+p1; e(v_j)+p2])。角色向量确保 (i,j) 与 (j,i) 的表示不同。pair 表示只针对当前候选集动态计算，从而避免为全目录维护平方规模词表，也能处理任意请求候选集。

2.2 编码器、解码器与动态输出层

用户输入是行为序列 X，每个历史行为把物品表示与停留时长、交互类型、位置等动作信号拼接，再经 MLP 得到 x_i。Transformer encoder 以自注意力编码历史；decoder 以已生成的 pair token 为输入，通过 cross-attention 读取用户历史。每一步隐藏状态 h_t 不连接固定分类头，而是与本请求所有合法 pair embedding 做内积并 softmax，形成动态词表分布。生成时用 mask 排除已经使用过的物品，保证展开后的列表无重复。

公开实验采用一层 encoder、一层 decoder、单注意力头，说明收益主要来自动作空间重构，而非更大模型。动态 pair 表示模块可以与用户编码并行；论文认为它是高算术强度的 batch GEMM，而历史 encoder 更偏内存带宽瓶颈。候选 n≤400、历史长度 b≥50 时，pair 表示能被用户编码和首个 decoder step 的墙钟窗口吸收。实测候选规模 20–100 时，PTR 只占总推理延迟的 2.8%–3.4%。

2.3 三阶段训练

第一阶段预训练 pair 表示。对曝光列表中的任意 i<j，若两个物品都被点击，pair 标签为 1；只点击一个时为 0.5；都未点击时为 0。模型对 pair embedding 各维求均值、过 sigmoid，再用 MSE 拟合该标签，以大规模曝光共现缓解平方动作空间的稀疏问题。

第二阶段使用 next-token prediction。对真实曝光排列切成 pair 序列，每一步以 h_t 与所有 n(n-1) 个动态 token 的内积做多分类交叉熵。第三阶段用外部列表评估器做 GRPO：一次采样 G 条重排列表，奖励按组内均值和标准差标准化成相对优势，再用 clipped policy ratio 与 KL 惩罚更新生成器。总损失为 pair 预训练、NTP 和 GRPO 的加权和；这使日志模仿负责稳定性，列表奖励负责搜索与业务效用。

实验先监督 warm-up 20 个 epoch，再做 GRPO；公开设置的 group size 为 16、clip ratio 为 0.2、KL 系数为 0.01，NTP 与 GRPO 权重分别为 1 和 0.1，推理 beam size 为 4。理论误差分析另以部署条件 n≤400、pair 预训练密度远大于 10^3、pair GRPO group size 32 对比 item-space 的 16，说明扩大采样可补偿动作空间变大。论文没有披露 optimizer、batch size、学习率、训练步数或训练硬件；推理实验只说明使用 FP32、峰值 59.8 TFLOPS 的未命名 GPU，k=3 在 48GB GPU、n=100 时 OOM。

2.4 复杂度与误差界

item-space 的固定 decoder 计算随 L 线性增长，KV-cache 读随 L² 增长；pair-space 将步数改为 L/2，因此两项分别理论降低 2 倍和 4 倍。代价是输出投影从 n 扩张到约 n²，每步投影开销增加约 n/2 倍，但这部分更适合并行，串行 KV 读取往往主导真实延迟，所以总体理论收益落在 2–4 倍之间。

在每步策略与最优策略的总变差误差为 ε 的假设下，结果奖励的最坏次优界由 item-space 的 O(R_max·L²·ε_item) 变为 pair-space 的 O(R_max·(L/2)²·ε_pair)。若 pair encoder 已饱和且 ε_pair≈ε_item，次优界改善接近 4 倍。论文也承认更大词表可能提高编码误差和有限 GRPO 覆盖误差，因此 4 倍并非无条件结论。

3. 核心技术贡献

1. 无损地改变自回归动作粒度。 PSG 不是把两步粗暴合成一个近似动作，而是给出列表集合双射和分布等价构造，证明 pair policy 没有丢失 item policy 的表达能力。它因此把“少生成几步”从经验技巧变成可分析的结构重参数化。

1. 用请求级动态词表解决平方规模问题。 静态 n² embedding 会面临存储和长尾稀疏，PSG 改为由两个物品表示、顺序角色向量和 MLP 即时组成 pair token，并在当前候选集上做内积输出。pair 预训练再用 1/0.5/0 的行为标签注入共现先验，使平方动作空间仍可训练。

1. 同时改善推理成本与结果质量。 理论上步数减半让固定 decoder 成本减半、KV 读取降至四分之一，并在 encoder-saturated 假设下把 outcome-only 奖励的最坏次优界改善近 4 倍。公开实验不仅更快，还在三个数据集的主要指标上超过 GoalRank 等强基线，说明一阶 look-ahead 的 pair 语义与较短误差链确实改善生成质量。

1. 给出可复用的生产证据。 快手实验使用 60 个候选、长度 6 的列表、每请求生成 50 条候选序列，服务 4 亿以上日活用户。PSG 在同一云容器上把生成器延迟从 38.42 ms 降到 20.99 ms，QPS 从 734 提到 1320，并带来人均停留时长 +0.178%，把理论设计与线上容量收益闭环。

4. 实验结果分析

离线实验包含 ML-1M（161,646 个请求、3,043 个物品）、Amazon-Books（309,917 个请求、38,121 个物品）和短视频工业数据 RecFlow（3,308,233 个请求、14,181,768 个物品）。前两个数据集先用 MF 从 top-200 中抽 50 个候选，历史最长 100；RecFlow 使用请求级候选，实验保留 60 个候选、长度 6 的目标列表，历史最长 50。主要结果如下：

相对各数据集最强竞争者，PSG 在 ML-1M 的 NDCG@6、Precision@6、Recall@6、F1@6 分别提升 2.01%、4.83%、4.77%、4.79%；Amazon-Books 四项提升 4.81%、11.88%、0.31%、6.95%；RecFlow 四项提升 8.38%–8.70%。Amazon 的 Recall 增益较小而 Precision 增益很大，说明 pair-space 在该目录上主要改善了列表筛选精度，并非所有指标都同幅增长。

消融清楚显示三阶段并非装饰。在 ML-1M 上，完整 PSG 的 NDCG@6 为 0.7548；去掉 pair 预训练降至 0.7463，去掉 GRPO 降至 0.7232，去掉 NTP 则大幅降至 0.6452。Amazon-Books 同样从 0.8652 降到 0.8527、0.8175 和 0.7595。NTP 是稳定序列生成的基础，GRPO 负责超越日志模仿，pair 预训练贡献较小但一致；如果生产数据稀疏或没有可靠评估器，不能预期只换 tokenization 就获得全部收益。

效率实验中，生成 6 个物品时，k=1 在不同候选规模下约为 25 ms；k=2 从 n=20 的 15.7 ms 增到 n=100 的 18.7 ms，仍明显更快。k=3 在 n=20 时为 14.0 ms，但 n=60 已升至 106.5 ms，n=100 直接 OOM，证明 token 组合数继续增加会让输出投影吞噬缩短轨迹的收益。

线上 A/B 在快手主应用单列信息流运行七天，对照和实验各使用互斥的 10% 流量。两组均输入 60 个候选和长度 100 的行为序列，生成 50 条长度 6 的列表；总预算 50 ms，其中生成器 30 ms、评估器 20 ms。PSG 将生成器延迟从 38.42 ms 降到 20.99 ms，达到 1.83 倍加速，在同一台 120 CPU 线程、500GB 内存的云容器上 QPS 提升 79.8%。停留时长相对提升 0.178%，高于作者所述快手通常 0.1% 的全量发布门槛。延迟在不影响曝光的 dry-run 流量上测量，因此它证明服务容量，却不能完全替代真实流量下的端到端 P99 观测。

5. 局限与未来方向

论文没有独立 Limitations 章节，但正文和结论给出明确边界。最重要的是动作空间按 n^k 指数增长。k=2 时，n=60 只有 3,540 个有序 pair，n=400 约 160,000，尚可处理；k=3 对应 216,000 和 6,400 万，k≥4 在 n=60 就超过 1,300 万。作者因此把 k=2 称为工业甜点位，并将更紧的实例依赖误差界和随机转移扩展列为未来工作。

第二，接近 4 倍的误差界改善依赖 ε_pair≈ε_item。若 pair encoder 训练不足、候选更大或 GRPO group 覆盖不够，平方词表可能让每步误差显著高于 item-space，抵消缩短轨迹的收益。论文虽给出部署密度和 group size 条件，却没有直接测量两类 ε，也没有报告不同目录稀疏度下的梯度方差。

第三，实验复现信息不完整。作者给出模型层数、epoch、GRPO 超参和 beam size，却没有 optimizer、batch size、学习率、随机种子、训练时长和明确 GPU 型号；公开实验只覆盖两个经典数据集与一个 RecFlow 数据集，线上只验证快手单列短视频。论文也省略线上 evaluator 的结构，因此无法判断 pair 生成器对不同列表奖励是否同样稳健。

第四，pair 模型天然强调相邻两物品的关系，但列表效用可能包含跨越多位置的高阶依赖。Transformer 和外部 evaluator 可以部分补偿，然而 pair 预训练标签只用两个曝光物品的点击组合，可能把位置偏差或共同曝光偏差写入表示。线上 +0.178% 虽超过平台门槛，但论文没有置信区间、分人群结果、长期留存、内容多样性或创作者生态指标，仍需更长周期验证。

6. 工业实践意义

PSG 最适合已有 G-E 重排器、候选规模中等、列表长度 4–10 且 KV-cache 串行解码已成为瓶颈的团队。落地前应先对每请求 n 计算 pair vocabulary：例如 n=60 时只有 3,540 个 pair，适合作为试点；如果 n 达到数千，应先缩小 rerank pool、分块或引入近似 top-pair 检索，不能直接物化 n² 个 logits。奇数列表需要明确尾部单 token 协议，并把已选物品 mask、pair 展开、beam 父节点和 evaluator 输入做一致性测试。

对社区 UGC 搜索，pair token 可以表达相邻结果的互补与冗余，例如同一观点的重复帖子应降权、教程与问答可能互补。建议先保持现有列表评估器和下游曝光逻辑不变，只把 generator 替换为 k=2；监督阶段用点击、长点击或收藏构造 pair 标签，NTP 学稳定列表，GRPO 再优化 nDCG、停留和多样性组合奖励。首轮验收应同时比较 NDCG/Recall、列表内相似度、长尾覆盖、生成器 P50/P99、QPS、PTR 占比和单位请求成本。

上线可以采用影子流量—小比例 A/B—容量扩张三步。影子阶段验证 n 增大时输出投影是否越过拐点，并监控非法/重复列表；A/B 阶段固定 evaluator，隔离 generator 贡献；容量阶段才把节省的 79.8% QPS 空间用于生成更多候选序列。若离线收益来自 NTP 而 GRPO 不稳定，应先保留监督版本；若 pair 预训练受曝光偏差影响，则加入位置校正或反事实权重。最终不应只追求 1.83 倍模型延迟，还要确认端到端请求解析、日志与响应开销下仍能稳定守住 30 ms 生成预算。