Внутри векторных баз данных: IVF, древовидные структуры, HNSW и квантизация произведений.

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

Откуда берутся векторы

Модели эмбеддингов, обученные на огромных наборах текста, преобразуют смысл предложения в список чисел. Некоторые из таких моделей расположены в облаке, например, модели эмбеддингов от OpenAI и Google Gemini. Другие работают локально, такие как семейство моделей эмбеддингов Qwen3 в версиях объемом 8B, 4B и 0.6B, или модель Jina v5 text-small с примерно 677 млн параметров. Если пропустить текст через одну из этих моделей, результатом будет вектор, который можно сохранить и воспроизвести позже.

Лексикон

В каждой векторной базе данных встречается несколько основных терминов:

• Коллекция. Пространство имен, содержащее точки, обладающие одной фиксированной размерностью и одной метрикой расстояния.
• Точка. Вектор вместе с его идентификатором и набором метаданных.
• Метрика расстояния. Способ измерения близости, обычно косинусное сходство, скалярное произведение или евклидово расстояние.
• Upsert. Операция, предназначенная для вставки данных — добавления новых точек и обновления существующих.
• Поиск. Операция запроса, ради которой существует весь остальной функционал.

Интуитивное понимание: точное против приближенного

Наивный способ нахождения векторов, связанных с запросом среди 10 000 или более векторов, заключается в вычислении косинусного сходства с каждым сохранённым вектором и сохранении k наиболее близких. Результатом является набор точных ближайших соседей. Однако при миллионах векторов такой метод грубой силы становится нецелесообразным из-за ограничений памяти и времени. Поэтому системы перешли к поиску приближённых ближайших соседей (ANN), который позволяет пожертвовать небольшой точностью ради значительного ускорения.

Эту замену можно осуществить двумя основными способами. Индексация сокращает количество необходимых сравнений. Квантизация снижает стоимость каждого сравнения. Вместе они составляют набор инструментов для поиска приближённых ближайших соседей.

Индексация, первый вариант: кластеризация с использованием IVF

Инвертированный индекс файлов (IVF) разделяет векторы на кластеры, каждый из которых имеет центроид. Сначала запрос сравнивается только с центроидами. После нахождения ближайшего кластера запрос сравнивается только с векторами внутри этого кластера, и возвращаются лучшие k из них.

Следует знать о его недостатках:

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

Неравномерные кластеры делают скорость поиска непредсказуемой. Некоторые ячейки растут до огромных размеров, в то время как другие остаются маленькими; поэтому запрос, попадающий в большую ячейку, обрабатывается медленно, а запрос, попадающий в маленькую — быстро.

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

Трудно настроить два параметра. Количество кластеров и количество элементов, ищемых за один запрос, влияют на результаты, а неверные значения приводят к медленному или неточному поиску.

Высокая размерность размывает кластеры. При очень длинных векторах кластеры становятся размытыми, в результате чего точность поиска на единицу работы уступает HNSW.

Кратко: IVF прост в использовании и экономит память, но теряет точность вблизи границ и плохо справляется с частыми обновлениями; поэтому он отлично подходит для масштабов в миллиарды записей при сочетании с квантизацией данных, тогда как HNSW лучше всего подходит для реального времени и поиска с высокой точностью.

Индексация, второй вариант: разбиение по деревьям

Индексация на основе деревьев использует принцип двоичного поиска. Вместо сравнения запроса со всеми векторами пространство несколько раз делят пополам, и проверяется только та половина, которая содержит запрос.

Чтобы построить индекс, берут всю область и делят её разделительной линией, затем снова делят каждую половину, продолжая до тех пор, пока в каждом небольшом регионе не окажется всего несколько векторов. Каждый такой регион является листом. В двумерном пространстве первое деление может происходить вдоль оси x, следующее — вдоль оси y и так далее. Все эти деления образуют бинарное дерево, в котором каждый узел представляет собой вопрос «да» или «нет», например, «находится ли x ниже 5», а листья располагаются внизу.

Когда поступает запрос, начинают с корня и по очереди отвечают на вопросы: слева от этой разделительной линии или справа? Каждый ответ исключает половину оставшейся области. После примерно log n вопросов, примерно 20 для миллиона векторов, достигается один небольшой лист, и запрос сравнивается с несколькими векторами, находящимися внутри него.

Есть нюанс. Настоящий ближайший сосед может находиться сразу за разделительной линией — на небольшом расстоянии, но в другом дереве, и отдельное дерево никогда не сможет его обнаружить. Поэтому такие библиотеки, как Annoy от Spotify, создают множество деревьев, каждое из которых имеет свои случайные разделения. Каждое дерево предлагает кандидатов, эти предложения объединяются, и возвращаются лучшие из них. То, что упускает одно дерево, обычно замечает другое.

Недостатки:

• Проблема границы здесь серьезнее, чем при методе IVF. При IVF пропуск границы означает необходимость проверки ещё одной ячейки. В дереве неверный поворот близко к вершине направляет поиск в совершенно другой регион.
• Решение требует дополнительной памяти и времени. Лес из 50 деревьев означает необходимость хранения индекса 50 раз и выполнения поиска 50 раз на каждый запрос, что позволяет добиться точности за счёт дополнительных ресурсов.
• Длинные векторы делают этот метод бесполезным. Деревья хорошо работают в 2D, 3D, на картах и в играх. Современные эмбеддинги имеют сотни или тысячи измерений, при этом прямая линия почти не разделяет данные с значимым эффектом, поскольку точки по обе стороны могут находиться на почти одинаковом расстоянии. Именно по этой причине этот метод утратил популярность для поиска по эмбеддингам.
• Индекс является статическим. Деревья создаются один раз на основе существующих данных и не могут эффективно принимать новые векторы. Например, для добавления данных в Annoy требуется полная перестройка, что плохо подходит для коллекций, которые постоянно меняются.
• В целом он уступает другим методам. При одинаковой точности метод HNSW работает быстрее, а при одинаковой памяти метод IVF с квантизацией по произведению позволяет обрабатывать большие объемы данных. Деревья в основном используются в устаревших системах и там, где важны небольшие файлы индексов, доступные в памяти.

Короче говоря, деревья просты в создании и быстры в работе, но высокомережные эмбеддинги уничтожают их структуру разделения и не позволяют вносить обновления, поэтому сегодня они в основном служат этапом на пути к объяснению результатов, а не решением для производственного использования.

Индексация, вариант третий: HNSW

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

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

Несколько параметров контролируют баланс между скоростью и точностью:

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

efSearch определяет ширину списка кандидатов во время выполнения запроса. Повышение этого параметра одновременно увеличивает точность и время обработки.

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

Квантизация: снижение стоимости каждого сравнения

Индексация сокращает количество необходимых сравнений. Квантизация уменьшает стоимость каждого из них. Один 1536-мерный вектор из 32-битных чисел с плавающей точкой занимает 1536 умноженных на 4, то есть 6144 байта. Для миллиарда таких векторов потребуется терабайты памяти, что значительно превышает объем оперативной памяти.

Продуктовая квантизация

Квантизация продукта разбивает каждый большой вектор на меньшие фрагменты одинакового размера. Например, 16-мерный вектор может превратиться в четыре фрагмента по четыре измерения каждый. Для каждой позиции фрагмента на основе сохранённых данных тренируется кодовая книга из 256 записей, каждая из которых представляет типичный подвектор. Затем каждый фрагмент заменяется числом, соответствующим записи из кодовой книги, наиболее близкой к нему, для чего требуется всего один байт.

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

Выбор среди них

Краткое сравнение помогает сделать вывод:

• IVF — простой в использовании и экономичный с точки зрения памяти метод. Его можно сочетать с квантизацией векторов для очень больших статических коллекций.
• Деревья легко понимаются и дешево создаются, но подходят только для данных низкой размерности, не меняющихся со временем.
• HNSW обеспечивает высокую точность и быструю поиск в реальном времени, но требует больше памяти.
• Квантизация векторов сжимает их и ускоряет вычисления расстояний при умеренной потере точности; её можно использовать в сочетании с вышеупомянутыми индексами.

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