只需修改兩行代碼，RAG向量檢索效率暴漲30%！

不僅適用于文搜文”、“圖搜圖”、“文搜圖”、“推薦系統(tǒng)召回”多種任務(wù)；而且具備良好擴(kuò)展性，適合十億、百億級別大規(guī)模應(yīng)用。

浙江大學(xué)高云君、柯翔宇團(tuán)隊(duì)聯(lián)手向量檢索領(lǐng)域大佬傅聰，開源新方法PSP（Proximity graph with Spherical Pathway），突破RAG兩大難題。

簡單來說，主流向量檢索方法都是基于歐幾里得距離設(shè)計(jì)，主要看“誰離你最近”；但有時(shí)AI其實(shí)更需要比較“語義相關(guān)性”，也就是最大內(nèi)積、看誰最相似。

以往的內(nèi)積檢索辦法，不能像歐式距離檢索方法那樣滿足數(shù)學(xué)上的三角關(guān)系，所以很多老方法失效。

PSP發(fā)現(xiàn)，只要進(jìn)行微小改動，老圖結(jié)構(gòu)也能找到最大內(nèi)積最優(yōu)解。

而且PSP還設(shè)置了提前停止策略，能判斷檢索是否應(yīng)該提前結(jié)束，避免浪費(fèi)算力，讓搜索更快。

AI產(chǎn)品背后的技術(shù)核心

向量檢索，是支撐起明星AI產(chǎn)品的核心技術(shù)組件。它不僅大大拓寬傳統(tǒng)語義檢索（關(guān)鍵詞檢索）的邊界，和大模型的配合更是渾然天成。

如何發(fā)揮這項(xiàng)技術(shù)的真正潛力，讓向量模型和向量數(shù)據(jù)庫的組合真正跑出效果，關(guān)鍵在于——選對“度量空間”。

盡管基于圖的向量檢索算法，如HNSW、NSG等，因其優(yōu)秀的檢索速度備受青睞，但往往被忽視的是，它們都是面向歐式空間設(shè)計(jì)的向量檢索算法。

“度量錯(cuò)配”在很多場景下是毀滅性的，很多適合用“最大內(nèi)積”檢索的向量數(shù)據(jù)，搭配歐式向量算法，往往會出現(xiàn)“檢索結(jié)果和query語義無關(guān)”的問題。

回看最大內(nèi)積檢索領(lǐng)域，其實(shí)還沒有出現(xiàn)類似HNSW、NSG這樣現(xiàn)象級的檢索算法。之前的很多工作往往只在某些數(shù)據(jù)集上面表現(xiàn)良好，但換了數(shù)據(jù)集，效果就會劇烈退化。

破局關(guān)鍵：僅需修改兩行代碼，實(shí)現(xiàn)全局最大內(nèi)積解

研究團(tuán)隊(duì)通過理論探索發(fā)現(xiàn)，在最大內(nèi)積檢索領(lǐng)域的研究涇渭分明地分成兩種范式：

一是把最大內(nèi)積轉(zhuǎn)換為最小歐式距離，進(jìn)而可以用HNSW、NSG來解決。但這種轉(zhuǎn)化往往會伴隨著信息損失或者拓?fù)淇臻g的非線性轉(zhuǎn)換，而這些問題會對搜索效果帶來不同程度的負(fù)面影響。

二是不進(jìn)行空間轉(zhuǎn)化，直接在內(nèi)積空間進(jìn)行檢索。這樣做的好處是避免了信息損失或空間扭曲，但相對應(yīng)的痛點(diǎn)是，缺少有效手段對無效檢索空間進(jìn)行裁剪，進(jìn)而難以達(dá)到更好的檢索速度。

為什么在內(nèi)積空間直接做檢索這么難呢？

最核心原因在于內(nèi)積空間并不是一個(gè)嚴(yán)格意義上的“度量空間”。從數(shù)學(xué)上來說，一個(gè)空間可以稱之為“度量空間”，需要滿足諸多條件，典型地，我們最常接觸的歐式空間就是一個(gè)度量空間。而作為一個(gè)“殘缺空間”，內(nèi)積空間缺少的最重要的屬性就是“三角不等式”。

根據(jù)NSG論文的理論部分，HNSW、NSG、SSG等state-of-the-art的向量檢索算法之所以能如此高效，就是因?yàn)樗麄兌祭昧巳遣坏仁綄λ饕Y(jié)構(gòu)（圖結(jié)構(gòu)）進(jìn)行了高效的裁剪。

而以內(nèi)積作為距離度量，構(gòu)建的三角形，不滿足我們耳熟能詳?shù)哪蔷淇谠E“三角形中任意兩邊之和大于第三邊，而任意兩邊之差小于第三邊”。正是這一屬性的缺失，阻礙了最大內(nèi)積檢索算法進(jìn)一步發(fā)展。

PSP研究團(tuán)隊(duì)對這一問題進(jìn)行了深入研究，從理論上證明了一件事情：對任意搜索請求，即Query點(diǎn)q，它在一個(gè)為歐式距離設(shè)計(jì)的圖索引結(jié)構(gòu)上，可以通過簡單的貪心算法找到全局最優(yōu)的最大內(nèi)積解。

基于圖的向量檢索算法都利用貪心算法進(jìn)行檢索：當(dāng)我們從隨機(jī)點(diǎn)開始在圖上游走時(shí)，NSG這類算法會從路徑上的點(diǎn)的鄰居中，尋找一個(gè)距離目標(biāo)“最近”的鄰居進(jìn)行跳轉(zhuǎn)，這樣從鄰居的鄰居逐步跳轉(zhuǎn)到全局最優(yōu)解。

而這種貪心算法曾經(jīng)隱含的理論要求的是，如果構(gòu)建圖用的是歐式距離表達(dá)“遠(yuǎn)和近”，那么貪婪游走也需要用歐式距離來定義遠(yuǎn)和近。

而PSP團(tuán)隊(duì)的研究成果意義在于，如果構(gòu)建圖用的是歐式距離，在貪婪游走的時(shí)候可以用內(nèi)積來定義遠(yuǎn)和近，最終到達(dá)的終點(diǎn)就是全局最優(yōu)的最大內(nèi)積解！

因此，研究團(tuán)隊(duì)可以通過僅修改檢索（貪婪游走）算法中的兩行代碼，就實(shí)現(xiàn)將一個(gè)現(xiàn)有的歐式算法向最大內(nèi)積的適配：

△實(shí)操中改變候選點(diǎn)隊(duì)列的“最大堆”、“最小堆”設(shè)定，以及距離度量

優(yōu)化：合理引導(dǎo)搜索行為規(guī)避冗余計(jì)算

PSP研究團(tuán)隊(duì)發(fā)現(xiàn)，最大內(nèi)積檢索的過程中，會存在大量冗余計(jì)算，而這些冗余是可以通過合理引導(dǎo)搜索行為來規(guī)避的。

最大內(nèi)積中的搜索行為與歐式空間中的搜索行為有極大差異，如下圖所示：

左圖中，綠色方框（query）的最近歐式近鄰是紅色三角，但它的最大內(nèi)積近鄰是橙色方塊。因此，在搜索query的最近歐式鄰居的時(shí)候，游走行為會很快在三角形附近停止，但搜索他的最大內(nèi)積鄰居會繼續(xù)走到“外圍”橙色方塊附近。

從更宏觀的角度看，研究團(tuán)隊(duì)發(fā)現(xiàn)，最大內(nèi)積檢索的解空間往往在數(shù)據(jù)集“外圍”（不同于歐式距離最近鄰，可以存在于數(shù)據(jù)空間的任意位置）。因此，最大內(nèi)積的搜索行為往往服從一種“由內(nèi)而外，再外圍擴(kuò)展”的模式（如上圖右圖）。

針對這種特性，PSP會設(shè)計(jì)針對性的策略，讓圖上搜索的起始點(diǎn)就盡量分布在距離“答案”更近的區(qū)域。

同時(shí)，冗余不僅僅發(fā)生在搜索過程的前段，也非常多地集中在搜索過程的后段。

如上圖，PSP研究團(tuán)隊(duì)發(fā)現(xiàn)，在圖索引上搜索到精確解的“最少步數(shù)”因Query而異，呈現(xiàn)明顯的長尾分布（圖a），而他們也通過大量實(shí)驗(yàn)挖掘出四類“特征”幫助我們判斷搜索應(yīng)該在什么時(shí)候停下來（圖b）。這四類特征可以在搜索過程中以非常低的成本被計(jì)算和記錄，實(shí)現(xiàn)自適應(yīng)的“早停”策略。

具體來說，可以在數(shù)據(jù)庫中隨機(jī)采樣一部分點(diǎn)作為query，通過對它們進(jìn)行搜索來收集最優(yōu)停止步數(shù)前后的數(shù)據(jù)構(gòu)成可分類的樣本，再用這個(gè)樣本去訓(xùn)練一顆決策樹，就可以輔助搜索過程判斷停止條件：

如上圖，研究團(tuán)隊(duì)通過對決策樹剪枝，可以讓整棵決策樹保留較小的高度。選擇決策樹作為分類器，可以有效擬合少量樣本，并直接翻譯為if-else語句嵌入搜索代碼中，實(shí)現(xiàn)高效的“停止判斷”。

性能實(shí)測：穩(wěn)定、高效、可擴(kuò)展性

研究團(tuán)隊(duì)為了充分測試PSP算法的效果，在8個(gè)大規(guī)模、高維度的數(shù)據(jù)集上進(jìn)行了充分測試。從維度看，DBpedia100K和DBpedia1M分別高達(dá)1536和3072維，用OpenAI text-embedding-3-large模型抽取；從數(shù)量看，最大的數(shù)據(jù)集Commerce100M包含1億數(shù)據(jù)庫點(diǎn)。

比較向量檢索算法，往往關(guān)注相同召回率下的檢索速度，即Query-Per-Second（QPS）。從上圖中可看出，PSP相對于現(xiàn)有state-of-the-art的方法有著穩(wěn)定、明顯的提升。在MNIST數(shù)據(jù)上，甚至超過第二名4倍之多。

值得注意的是，baseline的方法里，往往有一些會在圖中“缺席”。這是因?yàn)樗鼈冃阅苓h(yuǎn)差于其它方法，而很難和其它方法畫到同一張圖中。比如ip-HNSW在MNIST數(shù)據(jù)集中缺席；ScaNN在Laion10M和Commerce100M上缺席等等，這突出了PSP的表現(xiàn)穩(wěn)定性。

另外，所使用的數(shù)據(jù)集包含了“文搜文”“圖搜圖”“文搜圖”“推薦系統(tǒng)召回”等諸多數(shù)據(jù)模態(tài)，體現(xiàn)出PSP強(qiáng)大的泛化性。

除了比較檢索性能，另外一個(gè)考察向量檢索算法的應(yīng)用價(jià)值的重要維度是scalability。好的檢索需要遠(yuǎn)低于線性增長的時(shí)間復(fù)雜度（time complexity）。

上圖可以看出，PSP在Top-1近鄰上表現(xiàn)出log(N)速率增長的時(shí)間復(fù)雜度。而在Top-K檢索上表現(xiàn)出接近log(N)的復(fù)雜度。這體現(xiàn)出PSP優(yōu)秀的可擴(kuò)展性，即在十億乃至百億級別的數(shù)據(jù)上進(jìn)行高效檢索的潛力。

論文鏈接: https://arxiv.org/pdf/2503.06882

Github鏈接：https://github.com/ZJU-DAILY/PSP