Este relatório técnico apresenta um framework "Certify-then-Rectify" que combina a velocidade dos grafos HNSW (Hierarchical Navigable Small World) com garantias teóricas de correção. O método avalia dinamicamente a qualidade da busca e escala para um algoritmo de recuperação exata se necessário, garantindo precisão no pior caso.
- Usa um certificador estatístico livre de distribuição para avaliar a qualidade da busca HNSW com sobrecarga mínima.
- Reinterpreta o grafo HNSW como um spanner geométrico para limitar a distância máxima dos vizinhos mais próximos reais.
- Aplica a Teoria dos Valores Extremos para estimar estocasticamente o fator de estiramento empírico máximo.
- Fornece a velocidade média do caso médio do HNSW enquanto mantém a correção no pior caso da busca exata.
Esta abordagem preenche a lacuna entre a busca heurística e a recuperação rigorosa, superando outras abordagens aplicáveis em conjuntos de dados de benchmark.