Типы индексов FAISS

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

IndexFlat — точный перебор

IndexFlatL2 и IndexFlatIP — плоские индексы, которые хранят векторы как есть и при поиске сравнивают запрос со всеми векторами в базе. Первый использует евклидово расстояние (L2), второй — скалярное произведение (IP, inner product).

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

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

Обратите внимание: IndexFlatL2 возвращает в матрице расстояний квадрат евклидовой дистанции, а не само расстояние. Это сделано намеренно — вычисление квадратного корня дороже, а порядок соседей от его отсутствия не меняется.

Отдельного индекса для косинусной близости в FAISS нет. Его получают через IndexFlatIP, предварительно нормализовав все векторы по L2-норме — тогда скалярное произведение нормированных векторов эквивалентно косинусному сходству. Нормализацию нужно применять и к базе, и к запросам.

IndexIVFFlat — кластеризация пространства

В предыдущем модуле мы реализовывали IVF своими руками — здесь принцип тот же. IndexIVFFlat делит пространство на nlist кластеров с помощью k-means. При добавлении каждый вектор попадает в ближайший кластер. При поиске мы находим nprobe ближайших к запросу кластеров и ищем только внутри них.

Это приближённый поиск: если ближайший сосед оказался в кластере, который мы не просматривали, мы его пропустим. Но при разумных параметрах вероятность такого пропуска мала, а скорость значительно выше — на миллионе векторов с nprobe=10 при nlist=1000 поиск обрабатывает около 1% базы.

nprobe — главный рычаг компромисса: больше значение → выше полнота (recall) → дольше поиск. При nprobe = nlist получается полный перебор, как в IndexFlat.

Важная особенность: перед добавлением данных IVF-индекс нужно обучить — вызвать train() на репрезентативной выборке, чтобы k-means нашёл центроиды кластеров.

IndexHNSW — графовый поиск

IndexHNSWFlat — реализация алгоритма HNSW (Hierarchical Navigable Small World). Индекс строит многоуровневый граф: вершины — это векторы, рёбра — связи с ближайшими соседями. Верхние уровни разрежены и позволяют быстро «приблизиться» к нужной зоне пространства, нижний уровень плотный — здесь происходит финальный поиск.

Три параметра определяют поведение. M — количество связей у каждой вершины (обычно 16–48): больше связей — плотнее граф, выше точность, но больше памяти. efConstruction — глубина поиска при построении графа, влияет на качество индекса. efSearch — глубина поиска при запросе, главный рычаг после построения.

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

Product Quantization — сжатие векторов

Product Quantization (PQ) позволяет резко уменьшить объём памяти. Каждый вектор делится на m равных частей (субвекторов), для каждой части строится словарь из 2^nbits центроидов. Вместо исходных координат хранится только индекс ближайшего центроида в каждом словаре.

Например, вектор размерности 768 делим на 16 частей. Для каждой части — словарь из 256 центроидов (8 бит). Итого на вектор уходит 16 байт вместо 768 × 4 = 3072 байт — сжатие почти в 200 раз. При поиске расстояния вычисляются по сжатым кодам через предрассчитанные таблицы.

Точность снижается: чем агрессивнее сжатие, тем больше погрешность. Но для многих приложений 90–95% правильных результатов вполне достаточно, а возможность уместить сотни миллионов векторов в оперативную память — существенное преимущество.

В чистом виде IndexPQ всё равно перебирает все векторы, просто каждое сравнение происходит по сжатым кодам. Реальная мощь PQ раскрывается в комбинации с IVF.

IndexIVFPQ — комбинация кластеризации и сжатия

IndexIVFPQ объединяет оба подхода: пространство делится на кластеры (IVF), а внутри каждого кластера векторы хранятся в сжатом виде (PQ). При поиске мы выбираем несколько ближайших кластеров и вычисляем приближённые расстояния по кодам.

Это самый популярный выбор для больших коллекций — он экономит и время, и память. Параметров больше: nlist и nprobe для кластеризации, m и nbits для PQ. Требуется обучение.

Улучшенная версия — OPQ (Optimized Product Quantization). Перед квантованием применяется обучаемое ортогональное преобразование, которое лучше распределяет информацию по субвекторам. OPQ даёт заметный прирост точности при той же длине кода практически без дополнительных затрат памяти. Если уже идёте в IVFPQ — стоит сразу рассматривать OPQ.

IndexIVFSQ — скалярное квантование

IndexIVFSQ (Scalar Quantization) — промежуточный вариант между IVFFlat и IVFPQ. Вместо product quantization он просто квантует каждую компоненту вектора независимо: приводит значения к 8-битному целому (или 4-битному, в зависимости от настройки). Это проще и быстрее в вычислении, чем PQ, но и сжимает меньше — примерно в 4 раза против 10–200 раз у PQ.

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

IndexIVFPQFastScan — ускоренная версия IVFPQ

IndexIVFPQFastScan — современный вариант IVFPQ, оптимизированный под SIMD-инструкции современных процессоров (AVX2/AVX-512). Он обрабатывает несколько PQ-кодов одновременно в рамках одной процессорной инструкции, что даёт существенное ускорение на тех же параметрах без потери точности. На современном железе это фактически рекомендуемая замена стандартного IVFPQ.

IndexLSH — хэш-поиск

IndexLSH реализует Locality Sensitive Hashing — подход, при котором векторы проецируются в пространство бинарных хэшей так, чтобы похожие векторы с высокой вероятностью получали близкие хэши. Это узкоспециализированный индекс: он работает с бинарными кодами и подходит для сценариев, где данные изначально представлены в бинарном виде или нужна очень быстрая грубая предварительная фильтрация.

Композиция через index_factory

Помимо отдельных классов, FAISS предоставляет index_factory — способ собирать составные индексы из строки-описания. Например, строка "PCA256,IVF4096,PQ16x8" описывает сначала снижение размерности через PCA до 256, затем IVF с 4096 кластерами, затем PQ с 16 субвекторами по 8 бит. Это удобно для быстрого экспериментирования с разными конфигурациями.

В следующем шаге посмотрим на практическую сторону выбора: какой индекс брать под конкретные ограничения.