Что такое HNSW: быстрый поиск близких векторов

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

Как уровни графа ускоряют приближённый поиск соседей

Идея HNSW опирается на слоистую структуру. В обзоре Pinecone описан принцип: верхние слои держат длинные рёбра для быстрого перемещения, нижние — короткие рёбра для аккуратного поиска. Это перекликается со структурой списка с пропусками: редкие «экспресс-узлы» наверху позволяют перепрыгивать большие расстояния, а плотная сетка внизу уточняет результат.

Документация Weaviate формулирует свойство слоёв так: один объект может присутствовать более чем в одном слое, при этом каждый объект базы представлен в самом нижнем слое. Практический вывод: нулевой слой содержит все векторы, а верхние слои — подмножество. Поиск стартует сверху, где узлов мало и шаги крупные, затем спускается на уровень ниже, пока не дойдёт до слоя 0.

Механика спуска выглядит так:

1. На верхнем слое алгоритм выбирает точку входа и жадно движется к соседям, которые ближе к запросу.
2. Когда локальный минимум на текущем слое достигнут, поиск переходит на слой ниже, сохраняя найденную точку как стартовую.
3. На слое 0 выполняется более широкая выборка кандидатов с заданным бюджетом ef.
4. Из накопленного набора возвращаются k ближайших.

Жадное движение по слою означает, что на каждом шаге алгоритм смотрит на соседей текущего узла и переходит к тому, кто ближе к запросу. Когда ни один сосед не улучшает расстояние, слой считается пройденным. Такой подход даёт логарифмическое по числу узлов число шагов на верхних слоях и ограниченную работу на нижнем.

В описанном Pinecone графе NSW уже есть длинные и короткие связи. HNSW организует поиск иерархически: верхние слои с длинными рёбрами помогают быстро перемещаться по пространству, нижние уточняют результат. Такая структура сокращает обход по сравнению с полным перебором.

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

Важно различать два уровня гарантий. Точный поиск возвращает истинный топ по выбранной метрике. Приближённый поиск возвращает набор, который совпадает с истинным частично. Насколько велика эта часть — измеряемая величина, и её называют полнотой, или recall. Пригодность конфигурации оценивают по recall вместе со скоростью и требованиями задачи.

Слоистость влияет и на память. Каждый объект хранится в слое 0, а часть объектов дублируется в верхних слоях. Чем выше среднее число слоёв на объект, тем больше ссылок и тем больше памяти занимает индекс. Параметр M задаёт число связей на узел и напрямую влияет на этот расход.

Чем индекс отличается от модели эмбеддингов и метрики

Три сущности в поиске по векторам часто смешивают, и это ведёт к неверной диагностике.

Модель эмбеддингов превращает объект (текст, картинку, запись) в вектор фиксированной размерности. Качество модели определяет, насколько близкие по смыслу объекты оказываются близкими в пространстве. Если модель плохая, никакой индекс не спасёт: истинные соседи по смыслу окажутся далеко друг от друга.

Метрика задаёт способ измерения расстояния между векторами. Это может быть евклидово расстояние L2, косинусная близость или скалярное произведение. Метрика определяет, что вообще значит «близкий». Смена метрики меняет порядок соседей, даже если векторы не изменились.

Индекс — структура данных для ускорения поиска по уже готовым векторам и выбранной метрике. HNSW относится именно к этому слою. Он не меняет векторы и не переопределяет расстояние; он организует обход так, чтобы не перебирать всё.

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

В hnswlib метрика задаётся при создании индекса. Библиотека поддерживает L2, косинусную близость и скалярное произведение; выбранная метрика фиксируется в момент инициализации. Это ещё одна причина не смешивать настройки разных систем: параметры и умолчания Faiss, Weaviate, Azure AI Search и hnswlib различаются, и перенос значения из одной документации в другую даёт неверный результат.

Отдельно стоит помнить о нормализации. Косинусная близость и скалярное произведение связаны с L2 через норму векторов. Если векторы нормализованы, ранжирование по этим метрикам совпадает. Для ненормализованных векторов результаты могут расходиться; это различие связано с выбранной метрикой.

Параметры M, ef_construction и ef в hnswlib; цена построения и поиска

hnswlib — библиотека с заголовочным C++ и Python-биндингами, реализующая HNSW. Её документация по параметрам алгоритма описывает три ключевые настройки.

M — число устанавливаемых связей на узел при построении. Большее значение даёт более плотный граф, что повышает качество и увеличивает расход памяти. M влияет и на построение, и на итоговый размер индекса.

ef_construction — размер динамического списка кандидатов при построении. Документация hnswlib формулирует прямо: большее ef_construction ведёт к более долгому построению и лучшему качеству индекса. Это бюджет качества на этапе сборки.

ef — размер списка кандидатов при поиске. Документация Weaviate описывает эффект: более высокое значение ef даёт более обширный поиск, повышая точность и потенциально замедляя запрос. Документация hnswlib добавляет ограничение: ef нельзя задать меньше числа запрашиваемых ближайших соседей k.

Pinecone в своём разборе отмечает порядок настройки: efConstruction задаётся до построения индекса через index.add(xb), а efSearch можно менять в любой момент до поиска. Это разделение важно: качество графа фиксируется при сборке, а бюджет поиска можно подстраивать на лету под требования к задержке.

Цена построения и цена поиска — разные бюджеты. ef_construction задаёт бюджет построения графа; качество полученного графа влияет на дальнейший поиск. ef оплачивается на каждом запросе. M оплачивается памятью постоянно. Настройка индекса — это выбор, какой из трёх ресурсов вы готовы тратить.

При сохранении через save_index и загрузке через load_index README hnswlib требует снова задать ef. Для сериализации через pickle в том же README указано сохранение ef. Сравнивая результаты между сессиями, проверяйте способ сохранения и фактическое значение параметра.

Ещё одно ограничение из README касается потоков: запросы knn_query потокобезопасны между собой, а с add_items — нет. Добавление элементов во время параллельных запросов требует внешней синхронизации. Это относится к конкретной реализации hnswlib и к её API.

Полный набор пяти векторов и точный L2 ground truth

Чтобы разобраться с полнотой индекса, нужен эталон. Возьмём учебный пример: пять векторов в двумерном пространстве и один запрос.

Векторы: A = [1, 0], B = [0.9, 0.1], C = [0.8, 0], D = [0, 1], E = [−1, 0]. Запрос: query = [1, 0]. Метрика — евклидово расстояние L2.

Считаем расстояния от запроса до каждого вектора:

• A: sqrt((1−1)² + (0−0)²) = 0
• B: sqrt((0.9−1)² + (0.1−0)²) = sqrt(0.01 + 0.01) = sqrt(0.02) ≈ 0.1414
• C: sqrt((0.8−1)² + (0−0)²) = sqrt(0.04) = 0.2
• D: sqrt((0−1)² + (1−0)²) = sqrt(1 + 1) = sqrt(2) ≈ 1.4142
• E: sqrt((−1−1)² + (0−0)²) = sqrt(4) = 2

Точный порядок по возрастанию расстояния: A, B, C, D, E. Это ground truth — истинное ранжирование, с которым сравнивают приближённую выдачу. Точный top-3: [A, B, C].

Такой набор хорош тем, что расстояния различимы и не требуют вычислений с плавающей точкой высокой точности. A совпадает с запросом, B близок, C чуть дальше, D ортогонален, E противоположен. Любая ошибка ранжирования видна сразу.

Этот пример — арифметика на пяти точках. Он не является запуском HNSW и не измеряет производительность библиотеки. Его задача — дать эталон, относительно которого считается полнота.

Расчёт recall@3 для двух искусственных выдач: 2/3 и 1

Recall@k — доля истинных соседей из top-k, попавших в приближённую выдачу. Формула: размер пересечения приближённого и точного top-k, делённый на k.

Возьмём две искусственные выдачи и посчитаем recall@3.

Первая выдача: [A, C, D]. Пересечение с точным top-3 [A, B, C] даёт {A, C} — два элемента. Recall = 2/3 ≈ 0.667. Индекс потерял B и вернул D, который в истинный top-3 не входит.

Вторая выдача: [C, B, A]. Пересечение с [A, B, C] даёт {A, B, C} — три элемента. Recall = 1. Все истинные соседи найдены, хотя порядок внутри списка отличается от точного.

Второй случай показывает, что recall@k измеряет состав множества. Перестановка найденных элементов на него не влияет. Если приложение использует только факт попадания в top-k, перестановка внутри списка не влияет на метрику. Если важен точный порядок, нужна другая метрика, например нормализованный дисконтированный накопленный выигрыш.

Полный код расчёта на стандартной библиотеке Python:

# Учебный расчёт exact L2 и recall. Здесь нет запуска HNSW.
from math import sqrt

vectors = {"A": (1, 0), "B": (0.9, 0.1), "C": (0.8, 0),
           "D": (0, 1), "E": (-1, 0)}
query = (1, 0)

def l2(a, b):
    return sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))

def calc_recall(approximate, exact, k):
    return len(set(approximate[:k]) & set(exact[:k])) / k

exact = sorted(vectors, key=lambda name: (l2(vectors[name], query), name))
print("Точное ранжирование:", [(name, round(l2(vectors[name], query), 6))
                               for name in exact])
# Два придуманных списка нужны только для проверки формулы recall.
for artificial in [["A", "C", "D"], ["C", "B", "A"]]:
    print(artificial, "recall@3 =", calc_recall(artificial, exact, 3))
assert exact == ["A", "B", "C", "D", "E"]
assert calc_recall(["A", "C", "D"], exact, 3) == 2 / 3
assert calc_recall(["C", "B", "A"], exact, 3) == 1

Код печатает точное ранжирование с расстояниями и обе проверки recall. Утверждения assert фиксируют ожидаемый результат: точный порядок A, B, C, D, E и значения 2/3 и 1.

Практический порядок работы с recall:

1. Соберите точный ground truth полным перебором по вашему набору векторов.
2. Получите приближённую выдачу из индекса с текущими параметрами.
3. Посчитайте recall@k как долю пересечения.
4. Меняйте ef и пересчитывайте recall, пока не достигнете приемлемого уровня.
5. Зафиксируйте связку параметров и recall как паспорт конфигурации.

Такой цикл отделяет полноту индекса от качества эмбеддинга: ground truth считается по тем же векторам, что и приближённый поиск, поэтому разница в recall объясняется работой индекса.

Как оценивать полноту, задержку и память индекса

Полноту, задержку и память измеряют отдельно.

Полнота (recall) — доля истинных соседей, найденных индексом. Измеряется сравнением с точным поиском. Зависит от ef, M и структуры данных.

Задержка — время ответа на запрос. Зависит от ef, размера графа, железа и загрузки. Это отдельная величина, которую нельзя вывести из recall.

Память — объём, занимаемый индексом. Зависит от M, числа векторов и размерности. Документация Microsoft отмечает, что HNSW требует размещения всех точек данных в памяти для быстрого произвольного доступа, что расходует квоту размера векторного индекса.

Связь между ними нелинейна. Увеличение ef повышает recall и задержку. Увеличение M повышает качество и память. Улучшение одного показателя обычно стоит другого. Оптимум зависит от задачи: для интерактивного поиска важна задержка, для офлайн-аналитики — полнота.

Замеры времени в этой статье не приводятся. Любое конкретное число задержки зависит от железа, размера набора, размерности и версии библиотеки. Проверяйте задержку на собственном наборе с выбранными параметрами и фиксируйте условия измерения.

Отдельно про исчерпывающий поиск. Документация Microsoft рекомендует его для малых и средних наборов данных или когда потребность в точности перевешивает требования к скорости запроса. Это ориентир для выбора: на небольшом наборе точный перебор может оказаться достаточным, и сложность HNSW не окупится.

Фильтры и удаления требуют проверки конкретной реализации

HNSW как алгоритм описывает построение графа и поиск по нему. Операции с фильтрами и удалениями относятся к слою конкретной реализации, и их поведение различается между системами.

Удаление. В hnswlib удаление помечает элемент как удалённый, и он исключается из результатов поиска. Физическая структура графа при этом меняется не сразу. Повторное добавление элемента с тем же идентификатором требует явной обработки. Точное поведение зависит от версии библиотеки, поэтому его проверяют на своей версии.

Фильтры. Постфильтрация применяет фильтр к результатам поиска после обхода графа. Если фильтр отсекает большую часть кандидатов, итоговая выдача может оказаться короче ожидаемой: индекс вернул k соседей, но после фильтра осталось меньше. Предфильтрация ограничивает пространство поиска заранее, что меняет и качество, и задержку. Выбор стратегии — решение конкретной системы.

Согласованность. README hnswlib указывает, что запросы потокобезопасны между собой, а с добавлением элементов — нет. Если приложение добавляет векторы во время обслуживания запросов, нужна внешняя синхронизация. Игнорирование этого правила даёт непредсказуемые результаты.

Практический чек-лист перед внедрением:

1. Проверьте, как ваша система обрабатывает удаление и влияет ли оно на качество поиска.
2. Определите, применяется фильтр до или после обхода графа.
3. Измерьте recall отдельно с фильтрами и без них.
4. Проверьте поведение при параллельных добавлениях и запросах.
5. Зафиксируйте версию библиотеки: поведение может меняться между релизами.

Параметры разных систем не взаимозаменяемы. Значение ef, подобранное для hnswlib, не переносится автоматически в Faiss, Weaviate или Azure AI Search: у каждой системы свои умолчания, свои имена настроек и свои ограничения. Перенос настройки без проверки на своей системе даёт неверный результат.

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

Что такое алгоритм HNSW простыми словами?
HNSW — многоуровневый граф для приближённого поиска ближайших векторов. Верхние слои содержат длинные рёбра и дают быстрый черновой маршрут, нижний слой содержит все векторы и уточняет результат. Поиск идёт сверху вниз, что сокращает число проверяемых узлов по сравнению с полным перебором.

Чем индекс HNSW отличается от модели эмбеддингов?
Модель эмбеддингов превращает объект в вектор и определяет смысловую близость. Индекс HNSW организует обход готовых векторов для ускорения поиска. Плохая модель даёт плохих соседей независимо от качества индекса, а приближённый индекс может потерять истинного соседа при хорошей модели.

Что означают параметры M, ef_construction и ef?
M задаёт число связей на узел и влияет на память и качество. ef_construction задаёт бюджет качества при построении: большее значение ведёт к более долгой сборке и лучшему индексу. ef задаёт бюджет поиска: более высокое значение повышает полноту и потенциально замедляет запрос.

Как посчитать recall@3?
Recall@k — доля истинных соседей из top-k, попавших в приближённую выдачу. Для точного top-3 [A, B, C] и приближённого [A, C, D] пересечение даёт {A, C}, recall равен 2/3. Для выдачи [C, B, A] пересечение даёт три элемента, recall равен 1.

Почему результаты поиска различаются между сессиями?
После загрузки hnswlib через load_index параметр ef нужно задать вручную. При сериализации через pickle README указывает сохранение ef. Сверяйте способ сохранения, версию библиотеки и метрику.