让并行搜索不重复,用分片替代冗余,提升召回率
Coordination-Free Lane Partitioning for Convergent ANN Search
- 每个查询构建确定性候选池,按随机排列分给不同线程
- 在相同预算下,SIFT1M上召回率从24.9%升至99.9%
- 无需运行时协调,适合高并发向量搜索系统
生产环境的向量搜索系统常将查询广播到多个并行通道以满足延迟SLO。但各通道重复发现相同候选,额外计算未扩大覆盖范围。本文提出无协调的车道划分方法,将冗余转化为互补工作,在相同成本与截止时间下实现。对每个查询:(1) 构建大小等于总top-k预算的确定性候选池;(2) 应用每查询伪随机置换;(3) 将位置不相交地分配给各车道。车道返回结果天然不同,无需运行时协调。在4车道(总候选预算64)下,使用HNSW索引于SIFT1M数据集上,recall@10从0.249提升至0.999,车道重叠从近100%降至0%;在MS MARCO(880万段落)上,hit@10从0.200升至0.601,MRR@10从0.133升至0.330。对倒排文件(IVF)索引也有显著增益(如在MS MARCO上+11%),通过去重列表路由实现。微基准测试显示,规划器开销约37微秒/查询(均值),随合并候选数线性增长。结果给出明确操作建议:将每查询候选池设为总预算,确定性划分位置,将冗余广播转为互补覆盖,无需改变预算或截止时间。
原文摘要 · Abstract (English)
Production vector search systems often fan out each query across parallel lanes (threads, replicas, or shards) to meet latency service-level objectives (SLOs). In practice, these lanes rediscover the same candidates, so extra compute does not increase coverage. We present a coordination-free lane partitioner that turns duplication into complementary work at the same cost and deadline. For each query we (1) build a deterministic candidate pool sized to the total top-k budget, (2) apply a per-query pseudorandom permutation, and (3) assign each lane a disjoint slice of positions. Lanes then return different results by construction, with no runtime coordination. At equal cost with four lanes (total candidate budget 64), on SIFT1M (1M SIFT feature vectors) with Hierarchical Navigable Small World graphs (HNSW) recall@10 rises from 0.249 to 0.999 while lane overlap falls from nearly 100% to 0%. On MS MARCO (8.8M passages) with HNSW, hit@10 improves from 0.200 to 0.601 and Mean Reciprocal Rank at 10 (MRR@10) from 0.133 to 0.330. For inverted file (IVF) indexes we see smaller but consistent gains (for example, +11% on MS MARCO) by de-duplicating list routing. A microbenchmark shows planner overhead of ~37 microseconds per query (mean at the main setting) with linear growth in the number of merged candidates. These results yield a simple operational guideline: size the per-query pool to the total budget, deterministically partition positions across lanes, and turn redundant fan-out into complementary coverage without changing budget or deadline.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。