Este informe técnico presenta un marco de trabajo "Certificar-rectificar" que combina la velocidad de los grafos HNSW (Hierarchical Navigable Small World) con garantías teóricas de corrección. El método evalúa dinámicamente la calidad de la búsqueda y escala a un algoritmo de recuperación exacta si es necesario, asegurando la precisión en el peor caso.
- Utiliza un certificador estadístico libre de distribución para evaluar la calidad de la búsqueda HNSW con una sobrecarga mínima.
- Reinterpreta el grafo HNSW como un spanner geométrico para acotar la distancia máxima de los vecinos más reales.
- Aplica la Teoría de Valores Extremos para estimar estocásticamente el factor de estiramiento empírico máximo.
- Ofrece la velocidad promedio de HNSW mientras mantiene la corrección en el peor caso de la búsqueda exacta.
Este enfoque cierra la brecha entre la búsqueda heurística y la recuperación rigurosa, superando a otros enfoques aplicables en conjuntos de datos de referencia.