Что такое Memory-optimized ANN и какие алгоритмы лучшие для ограниченной RAM (<16GB)?

Краткий тезис

Memory-optimized ANN (Approximate Nearest Neighbor) — это алгоритмы поиска ближайших соседей, спроектированные для работы в условиях жёсткого лимита оперативной памяти (менее 16 ГБ). Основная идея — хранить векторы в сжатом виде (квантование) или на диске, а в RAM держать только компактный индекс и кэш популярных векторов. Лучшие алгоритмы для таких сценариев: Faiss IVF-PQ (Inverted File with Quantization|Product Quantization) и ONNG (Optimized Navigable Small World). Они позволяют обрабатывать миллиарды векторов на обычном ноутбуке или сервере с 8–16 ГБ RAM.

1. Термин: ANN (Approximate Nearest Neighbor)

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

Почему важна память
Векторные представления (эмбеддинги) обычно имеют размерность 128–1536 и хранятся как float32 (4 байта на число). Один вектор размерности 768 занимает ~3 КБ. Для 10 миллионов векторов это уже ~30 ГБ — больше, чем 16 ГБ RAM. Поэтому без сжатия или выгрузки на диск такой объём не помещается в память.

Memory-optimized ANN — это подмножество ANN-алгоритмов, которые специально адаптированы для работы с ограниченной RAM. Они используют:

• Квантование (Quantization) — сжатие векторов до меньшего числа бит (например, 8-битное или Quantization|product quantization).
• Дисковое хранение (Disk-based index) — векторы лежат на SSD, в RAM только метаданные и кэш.
• Структуры с низким потреблением (например, Navigable Small World графы с контролем степени вершин).

2. Основные подходы к экономии памяти

2.1 Product Quantization (PQ)

Product Quantization — метод сжатия векторов, при котором вектор разбивается на подвекторы, каждый подвектор квантуется в центроид из небольшого кодового словаря. В результате каждый вектор заменяется набором коротких кодов (например, 8–64 байта вместо 3072 байт для float32).

Как работает

1. Обучается кодовая книга (codebook) на обучающей выборке.
2. Каждый вектор разбивается на M подвекторов.
3. Для каждого подвектора находится ближайший центроид (из K центроидов).
4. Вектор представляется как M индексов центроидов (каждый индекс — log2(K) бит).

Экономия
Исходный вектор 768 float32 = 3072 байта.
После PQ с M=96, K=256: 96 * 1 байт = 96 байт. Сжатие в 32 раза.

Недостаток Потеря точности — расстояние между сжатыми векторами оценивается приближённо (через асимметричное расстояние, ADC).

2.2 Inverted File (IVF) с PQ

IVF (Inverted File Index) — кластеризация пространства на ячейки (воронки). При поиске просматриваются только ближайшие к запросу ячейки, а не все векторы. Комбинация IVF+PQ (Faiss IVF-PQ) — стандартный индустриальный подход:

• IVF делит пространство на Nlist кластеров (например, 4096).
• Внутри каждого кластера векторы хранятся в сжатом виде (PQ).
• Поиск: находим ближайшие к запросу кластеры (probe), внутри них — приближённый поиск по PQ-кодам.

Потребление памяти

• Кластерные центроиды (Nlist * dim * 4 байта) — обычно несколько МБ.
• PQ-коды для всех векторов (N * M байт) — например, 10M * 96 = 960 МБ.
• Итого ~1 ГБ для 10M векторов — помещается в 16 ГБ.

2.3 Optimized Navigable Small World (ONNG)

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

• Уменьшает среднюю степень вершин (количество рёбер).
• Использует квантование для хранения векторов (например, 8-битное).
• Позволяет хранить граф на диске, а в RAM — только активные узлы.

Память HNSW vs ONNG
HNSW для 10M векторов (dim=768) может занимать 5–10 ГБ (граф + векторы). ONNG с квантованием — 1–3 ГБ.

Преимущество ONNG Высокая скорость поиска (логарифмическая сложность) при умеренной памяти.

2.4 Дисковые индексы (DiskANN, Faiss IndexIVF with disk storage)

DiskANN — алгоритм от Microsoft, который хранит векторы на SSD, а в RAM — только граф (или PQ-коды) и кэш. При поиске подгружает векторы с диска по мере необходимости. Позволяет работать с миллиардами векторов на машине с 8 ГБ RAM.

Faiss поддерживает IndexIVF с опцией store_vectors_on_disk=True — векторы лежат в файле, в RAM только инвертированный список и PQ-коды.

Компромисс Скорость поиска ниже (из-за I/O), но память практически не ограничена.

3. Сравнение лучших алгоритмов для RAM <16 ГБ

Вывод для <16 ГБ

• Если точность критична и скорость не очень важна → Faiss IVF-PQ (настройка nprobe, M, nbits).
• Если скорость важна и точность >0.95 → ONNG (или HNSW с PQ).
• Если векторов >100M → DiskANN или Faiss с дисковым хранением.

4. Практические приёмы для ограниченной RAM

4.1 Хранить векторы на диске, кэшировать популярные

Идея Векторы лежат в файле (mmap или прямой доступ). В RAM — только индекс (например, списки кластеров IVF). При поиске подгружаются только те векторы, которые попали в кандидаты. Популярные запросы кэшируются (например, LRU-кэш на 10000 векторов).

Реализация в Faiss

import faiss

# Создаём индекс IVF-PQ с хранением на диске
index = faiss.index_factory(dim, "IVF4096,PQ96")
index.train(vectors)
faiss.write_index(index, "index.faiss")

# При поиске используем mmap
index = faiss.read_index("index.faiss", faiss.IO_FLAG_MMAP)
# или
index = faiss.read_index("index.faiss")
index.verbose = True
# Поиск
D, I = index.search(query, k)

4.2 Использовать 8-битное квантование (scalar quantization)

Вместо float32 можно хранить векторы как int8 (1 байт на число). Потеря точности ~1–2%, но память уменьшается в 4 раза.

Faiss: IndexScalarQuantizer или IndexIVFScalarQuantizer.

4.3 Уменьшать размерность эмбеддингов

Использовать модели, которые выдают эмбеддинги меньшей размерности (например, 128 вместо 768). Современные модели (e5-small, bge-small) дают 384-мерные векторы с хорошим качеством.

4.4 Использовать разреженные векторы (Sparse embeddings)

Sparse ANN (например, SPLADE) хранят только ненулевые компоненты, что резко снижает память для текстовых данных.

5. Как выбрать алгоритм под конкретный сценарий

Сценарий 1 Ноутбук с 8 ГБ RAM, 5M векторов (dim=768), нужно отвечать за <100 мс.
→ Faiss IVF-PQ (nlist=4096, M=64, nprobe=10). Память ~500 МБ, скорость ~2 мс на запрос.

Сценарий 2 Сервер с 16 ГБ RAM, 50M векторов, высокая точность (Recall@10 >0.97).
→ ONNG с 8-битным квантованием. Память ~6 ГБ, скорость ~1 мс.

Сценарий 3 Встраиваемое устройство (Raspberry Pi, 4 ГБ RAM), 1M векторов.
→ Faiss IndexFlat (точный поиск) для маленькой базы, или IVF-PQ с малым M.

6. Оценка качества Memory-optimized ANN

Метрики:

• Recall@k — доля истинных ближайших соседей среди top-k результатов.
• Memory usage — пиковое потребление RAM (можно замерить через memory_profiler).
• QPS (Queries Per Second) — пропускная способность.
• Latency p99 — время ответа для 99-го перцентиля.

Пример бенчмарка

import faiss
import time
import numpy as np

dim = 768
n = 10_000_000
nq = 1000

# Генерация данных
xb = np.random.random((n, dim)).astype(np.float32)
xq = np.random.random((nq, dim)).astype(np.float32)

# Построение индекса IVF-PQ
index = faiss.index_factory(dim, "IVF4096,PQ96")
index.train(xb)
index.add(xb)

# Поиск
t0 = time.time()
D, I = index.search(xq, 10)
t1 = time.time()
print(f"QPS: {nq / (t1 - t0):.1f}")

7. Компромиссы и подводные камни

• Компрессия снижает точность PQ с M=64 даёт Recall@10 ~0.90, с M=96 — ~0.95. Нужно тестировать на своих данных.
• Дисковые индексы медленнее DiskANN может давать latency 10–50 мс из-за SSD I/O.
• ONNG сложнее в настройке Параметры (max_degree, ef_construction) сильно влияют на память и скорость.
• Кэширование популярных векторов может исказить статистику, если запросы равномерны.

Пет-проект для закрепления

Задача Разработать систему поиска изображений по смыслу на ноутбуке с 8 ГБ RAM. Использовать предобученный эмбеддер (ResNet-50, выход 2048) и датасет из 500K изображений (например, Flickr30k). Реализовать Memory-optimized ANN с Faiss IVF-PQ и сравнить с HNSW (без квантования).

Инструменты Python, Faiss, torchvision, numpy, psutil (для замера памяти).

Шаги:

1. Загрузить датасет, извлечь эмбеддинги (dim=2048) — сохранить в .npy.
2. Построить два индекса:
   • IVF-PQ (nlist=2048, M=128, nbits=8)
   • HNSW (без квантования, efConstruction=200)
3. Замерить память (через psutil.Process().memory_info().rss).
4. Замерить скорость поиска для 1000 запросов.
5. Вычислить Recall@10 (ground truth — полный перебор для подвыборки).
6. Сделать вывод: какой индекс лучше для 8 ГБ RAM.

Ожидаемый результат

• IVF-PQ: память ~1.2 ГБ, Recall@10 ~0.92, QPS ~1500.
• HNSW: память ~6.5 ГБ (почти не влезает), Recall@10 ~0.98, QPS ~3000 (но может вытесняться в swap).
• Вывод: IVF-PQ — единственный рабочий вариант для 8 ГБ.

Связь с другими вопросами

Навигация

• Предыдущий: 231
• Следующий: 233
• Индекс: 00. Индекс разборов