高維網格近似最近鄰搜尋的縮放定律
本研究系統刻畫了多探針網格演算法在高維空間中的效能，發現其在GloVe嵌入上表現出獨特的維度縮放交叉現象，與其他方法相比具有恆定維度指數、近線性查詢縮放和更低索引成本的優勢，對高效Transformer架構設計具有指導意義。
近年來，近似最近鄰（ANN）搜尋在機器學習和人工智慧領域佔據了核心地位，尤其是隨著高效Transformer架構的發展，自注意力機制已被形式化為ANN操作。然而，基於網格的方法在現代縮放分析中卻長期被忽視。一項來自Matthew J. Liu等七位研究者、於2026年7月1日提交至arXiv的新研究填補了這一空白，系統性地分析了多探針網格演算法相對資料集規模N和維度d的縮放行為。
研究團隊在GloVe嵌入家族上進行了廣泛的實驗，揭示出一個此前未被報道的維度縮放交叉現象：多探針網格搜尋能夠維持一個大致恆定的維度縮放指數，而基於圖（如HNSW）、樹（如KD-tree）和劃分（如IVF）的方法在高維情況下吞吐量顯著下降。這一優勢不僅體現在查詢延遲上，網格方法還實現了近乎線性的查詢縮放（相對於N），並且其索引構建成本顯著低於競爭方法。例如，在需要頻繁重建索引或維度極高的場景中，索引成本和維度魯棒性成為效能瓶頸，而網格方法恰好在這兩方面表現出色。
更廣泛地，由於自注意力已被建模為ANN操作，ANN演算法的N和d縮放性質可以為高效Transformer架構的成本分析提供理論指導。該研究的程式碼已在GitHub上公開（https://github.com/weiz345/MultiProbeANN），便於社群驗證和擴充套件。這項發現不僅復興了網格方法在ANN領域的地位，也提示研究者重新審視那些因高維詛咒而被放棄的簡單方法。未來，網格方法或將成為構建大規模、高維機器學習系統的重要工具。