ANN-поиск по HNSW даёт те же результаты, что полный перебор?

Не гарантированно. Это приближённый алгоритм: он почти всегда находит ближайших соседей, но может пропустить истинный топ. Параметром ef качество подтягивается к перебору ценой скорости и памяти.

HNSW всегда лучший выбор индекса?

Нет. Он быстрый, но прожорлив к памяти: граф хранит рёбра плюс векторы. На огромных базах с жёстким бюджетом памяти смотрят квантование и другие типы индексов.

Глоссарий

HNSW: иерархический граф ближайших соседей в векторных БД

Коротко: HNSW (Hierarchical Navigable Small World) это графовый алгоритм приближённого поиска ближайших соседей, стандартный индекс векторных баз. Векторы связываются в многослойный граф: верхние слои редкие, с длинными рёбрами для быстрых прыжков, нижние плотные для точного добора соседей. Поиск стартует на верхнем уровне и жадно спускается к окрестности запроса, не перебирая всю базу, поэтому миллионы векторов ищутся за миллисекунды ценой небольшой вероятности пропуска истинного соседа. HNSW встречается в Qdrant, pgvector, Faiss; главные настройки это M, число рёбер на узел, и ef, размер очереди кандидатов при поиске.

HNSW это причина, по которой векторный поиск вообще масштабируется: без приближённых индексов каждый запрос был бы полным перебором всех эмбеддингов.

Практика настройки: ef поднимают, пока recall на золотом наборе не упрётся в потолок, дальше увеличение только тормозит запросы.

Частые вопросы

ANN-поиск по HNSW даёт те же результаты, что полный перебор?: Не гарантированно. Это приближённый алгоритм: он почти всегда находит ближайших соседей, но может пропустить истинный топ. Параметром ef качество подтягивается к перебору ценой скорости и памяти.
HNSW всегда лучший выбор индекса?: Нет. Он быстрый, но прожорлив к памяти: граф хранит рёбра плюс векторы. На огромных базах с жёстким бюджетом памяти смотрят квантование и другие типы индексов.