Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval
分布近似最近邻搜索：面向不确定性感知的检索
aampe · Antwerp, Belgium
在 ANN 索引中为每个物品采样多个嵌入副本，用不确定性隐式驱动检索阶段的探索，大幅提升长尾覆盖
📌 工作参考价值
- 直接在 Faiss 等现有 ANN 索引上实现：每个物品预先采样多个嵌入加入索引，查询时也采样用户嵌入并检索去重，无需修改模型或索引后端，即可将嵌入不确定性转换为长尾物品的曝光机会。
- 自适应采样预算：对冷门、高不确定性的物品分配更多样本（如 S=2~10），头部物品保持单样本，可有效控制索引膨胀，同时将探索算力集中在需要曝光的尾部。
- 用交互计数简单构造“合成后验”：令 σ_i ∝ 1/(1+n_i)^γ，以此从点估计中生成模拟贝叶斯不确定性的噪声样本，低成本实现类似汤普森采样的检索阶段探索。
- 将精确度损失交由下游排序模型吸收：候选生成阶段允许少量 top-K 精度下降，换取覆盖率的数倍提升，后续排序器可以利用丰富特征对新增的探索候选重排，整体 pipeline 收益明显。
动机：大规模推荐系统的候选生成阶段通常使用点估计嵌入进行近似最近邻（ANN）检索，这会造成对头部热门物品的系统性偏好，而长尾物品由于交互稀疏、嵌入估计方差大，几乎永远无法进入检索结果。这种确定性 top-K 截断忽视了嵌入本身的不确定性，导致覆盖率和公平性极差。
方法：提出 dinosaur 框架，不改变模型架构或 ANN 引擎本身。离线时，对每个物品从其嵌入分布中采样 S_i 个向量全部加入索引；在线时，用户侧同样采样一个嵌入进行检索，最后将检索到的原始向量去重得到 K 个物品。这一双侧随机过程隐式地边缘化了嵌入不确定性，物品方差越大，其样本在隐空间中占据的区域越广，被检索的概率越高。理论证明：当方差趋向 0 时，dinosaur 以高概率复原确定性 top-K；且检索概率随物品方差单调非减。为控制索引大小，提出自适应采样，仅对尾部高不确定物品分配多个采样点，头部物品保持 1 个。不确定性来源可以是从贝叶斯模型学到的后验，也支持用交互计数直接构造 σ_i 作为代理。
实验：在 MovieLens-32M 上，用 iALS 学习 128 维点估计嵌入，以 σ_i = α/(1+n_i)^{0.25} 添加不确定性，使用 IVFFlat 索引。结果表明，当 S=5，K=1000 时，全局目录覆盖率从基线的 23.52% 提升到 62.97%，而 Recall@1000 仅从 0.9135 微降至 0.9094。分层分析中，最不流行的物品组覆盖率从 0% 提升到 81.88%，超过 13% 的用户至少看到一件该组物品。与 ε-贪婪探索对比，dinosaur 在同等探索比例下取得更高召回，形成严格帕累托改进。
核心洞见：在固定 ANN 基础设施上，仅仅通过复制采样、去重这样一个最小侵入式改动，就能让检索过程天然地偏向探索，将不确定性转化为长尾内容的曝光动力。