WebANNS: Fast and Efficient Approximate Nearest Neighbor Search in Web Browsers

近似最近邻搜索（ANNS）已成为现代人工智能基础设施中不可或缺的一部分，尤其是在检索增强生成（RAG）应用中。为了与主流的基于大语言模型（LLM）的网页应用无缝集成，同时应对隐私保护和异构设备部署带来的挑战，许多可在浏览器中运行的 ANNS 引擎应运而生。然而，网页浏览器为实现高效的 ANNS 带来了独特的挑战，包括计算能力受限、外部存储访问问题以及内存使用限制，而现有的最先进（SOTA）方案无法全面应对这些难题。 我们提出了 WebANNS，这是一种专为网页浏览器设计的新型 ANNS 引擎。WebANNS 利用 WebAssembly 技术克服计算瓶颈，设计了一种延迟加载策略以优化从外部存储中检索数据的效率，并采用启发式方法降低内存占用。实验结果表明，WebANNS 速度快捷且内存使用高效，在第99百分位查询延迟方面相较现有最先进的引擎最高可提升达 743.8 倍，同时内存使用量最多减少了 39%。值得注意的是，WebANNS 将浏览器中的查询时间从 10 秒减少到了 10 毫秒级别，使得在浏览器内实现近似最近邻搜索具备了用户可接受的延迟，真正变得实用可行。

论文旨在解决在Web浏览器中实现高效近似最近邻搜索（ANNS）的问题，包括计算瓶颈、外部存储访问困难和内存使用限制等挑战。这是一个新兴且重要的问题，特别是在隐私保护和异构设备部署需求日益增加的背景下。

论文提出了WebANNS，一个专为Web浏览器设计的新型ANNS引擎。其核心思路是利用WebAssembly来提升计算性能，采用延迟加载策略优化外部存储数据检索，并通过启发式方法减少内存占用。相比现有最先进的解决方案，该方法更全面地应对了浏览器环境中的多重限制。

1. 实验结果显示，WebANNS在99百分位查询延迟上比现有最优方案提升了高达743.8倍，同时内存使用减少了最多39%。 2. 查询时间从10秒降低到10毫秒级别，使得浏览器内的ANNS具备用户可接受的延迟。 3. 实验设计覆盖了多个实际应用场景，验证了WebANNS的高效性和实用性。 4. 开源代码和数据集的发布可能推动更多关于浏览器端AI基础设施的研究。

1. ScaNN: Efficiently Searching for Nearest Neighbors in Large-Scale Datasets 2. FAISS: A Library for Efficient Similarity Search and Clustering of Dense Vectors 3. NGT: Nearest Neighbor Search Graph Implementation for High-Performance Applications 4. HNSW: Hierarchical Navigable Small World Graphs for Approximate Nearest Neighbor Search 5. In-Browser Machine Learning: Challenges and Opportunities for Client-Side AI