HNSW алгоритм простыми словами: как ИИ ищет в памяти

На полке у Лины стоят тонкие папки, по одной на клиента, и чтобы найти нужную, раньше приходилось снимать и пролистывать каждую по очереди. Память ассистента устроена иначе: это не полка, где ищут по корешку, а библиотекарь, который помнит смысл каждой папки и сразу подсказывает нужную. ИИ находит нужное быстро, потому что не перебирает записи подряд. Память ассистента хранит знания в виде векторов, числовых отпечатков смысла, а поиск по ним ведёт алгоритм HNSW: Hierarchical Navigable Small World, по-русски «иерархический навигационный граф тесного мира». Он заранее строит из векторов карту похожести с несколькими этажами. Верхний этаж это редкая сеть дальних связей, нижний это плотная сеть ближайших соседей. Запрос входит сверху и на каждом шаге переходит к тому соседу, который ближе к цели: сначала грубыми прыжками через всю базу, потом всё точнее. Поэтому вместо миллиона сравнений хватает нескольких десятков шагов. Сложность поиска растёт логарифмически: удвоение базы почти не замедляет ответ. Это приближённый поиск: он изредка промахивается мимо формально ближайшей записи, зато отвечает за доли секунды, и для поиска по смыслу такой размен почти всегда выгоден.

Почему нельзя просто перебрать всё

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

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

Представьте, что Вы ищете знакомое лицо в незнакомом городе, опрашивая всех жителей по очереди. В деревне это сработает, в миллионном городе нет. А ассистенту такой «опрос» нужен не раз в день: на один Ваш вопрос он может сходить в память несколько раз. Полный перебор здесь означал бы паузу в секунды и лишние расходы на каждое обращение. Нужен способ искать, не глядя на всех.

Приближённый поиск: размен точности на скорость

Выход нашёлся в смене требования. Точный поиск обязан вернуть самую близкую запись, и ради этой гарантии приходится смотреть всё. Приближённый поиск ближайших соседей, по-английски approximate nearest neighbor или ANN, обещает меньше: вернуть очень близкую запись, почти всегда ту же самую, что нашёл бы полный перебор.

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

У этой честной сделки есть измеримая цена. Качество приближённого поиска описывают метрикой recall: какую долю истинных ближайших соседей алгоритм действительно нашёл. Recall 0,95 означает, что 95 из 100 правильных соседей на месте. Настройками алгоритма эту долю можно двигать: выше точность, ниже скорость, и наоборот. Ручка настройки остаётся у инженера, а не у случая.

Как устроен HNSW: карта с этажами

HNSW опирается на идею «тесного мира», знакомую по разговорам о шести рукопожатиях: в сети знакомств почти любые два человека связаны короткой цепочкой. Если хранить записи не списком, а графом, где каждая соединена со своими смысловыми соседями, то до любой точки можно дойти короткой цепочкой переходов: на каждом шаге идём к тому соседу, который ближе к цели.

К этой идее в 2016 году добавили главное: иерархию. Получившаяся структура похожа на то, как Вы добираетесь по незнакомому адресу. Сначала самолёт: крупный прыжок в нужный город. Потом метро: до нужного района. Потом пешком: до подъезда. В HNSW то же самое делают этажи графа. На верхних этажах живёт малая часть записей с длинными связями через всю базу, на нижнем этаже все записи со связями к ближайшим соседям. Поиск входит на верхний этаж, грубыми прыжками добирается до нужной «области смысла», спускается этажом ниже, уточняет, и так до самого низа.

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

Откуда известно, что это работает: ANN Benchmarks

Проверять такие алгоритмы на слово не нужно: для этого есть открытый проект ANN Benchmarks. Он гоняет десятки реализаций поиска на одних и тех же открытых наборах данных: например, SIFT, миллион векторов по 128 чисел, или GloVe, около 1,2 миллиона векторов. Каждый алгоритм запускается в одинаковых условиях, а результат рисуется одной картинкой: recall по горизонтали, число запросов в секунду по вертикали.

Эта картинка и есть портрет честной сделки из предыдущего раздела: кривая показывает, сколько скорости алгоритм отдаёт за каждый процент точности. Среди участников есть и hnswlib, эталонная реализация авторов HNSW, и pgvector, расширение PostgreSQL, где HNSW работает внутри обычной базы данных. На наборах в миллион записей реализации HNSW стабильно держатся среди самых быстрых при высоком recall: то самое «найти за доли секунды среди миллионов», измеренное независимо и воспроизводимо.

Что это даёт памяти ассистента

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

У Хермес память живёт в PostgreSQL с расширением pgvector, где работают те же HNSW-индексы: открытая, проверенная технология, а не закрытый ящик. Логарифмическая сложность здесь превращается в практическое обещание: память продукта рассчитана на годы накопления. Чем дольше Вы работаете с ассистентом, тем больше он знает о Вашем деле, а скорость ответа при этом остаётся прежней. Карта похожести просто получает ещё несколько этажей, и путь к нужному факту по-прежнему занимает десятки шагов, а не миллионы сравнений.