Certify-then-Rectify

新框架保证HNSW图的准确性，开销极小

研究人员开发了一个新的“认证后修正”（Certify-then-Rectify）框架，以提高分层可导航小世界（HNSW）图的准确性。HNSW图因其速度而被广泛使用，但缺乏理论正确性保证。该框架使用统计认证器评估HNSW搜索结果的质量，并在需要时升级到精确恢复算法。通过将HNSW图重新解释为几何跨度图并应用极值理论，该系统可以在数学上界定到真正最近邻的距离，从而实现HNSW的速度和精确搜索的最坏情况正确性。