Как вы обновляете ANN индекс при добавлении новых векторов без перестроения?

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

Обновление ANN (Approximate Nearest Neighbor) индекса без полного перестроения — задача с компромиссами. HNSW (Hierarchical Navigable Small World) поддерживает инкрементальные вставки, но со временем точность поиска деградирует. IVF (Inverted File Index) требует периодического перестроения кластеров. Оптимальная production-стратегия — hot/warm индексы: маленький «горячий» индекс для новых векторов (быстрая вставка) и большой «тёплый» индекс, перестраиваемый по расписанию, с последующим слиянием.

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

ANN — это семейство алгоритмов для поиска ближайших соседей в многомерном пространстве, которые жертвуют точностью ради скорости. В RAG ANN используется для поиска релевантных чанков по эмбеддингу запроса. Основные алгоритмы: HNSW, IVF, PQ (Quantization|Product Quantization), LSH (Locality-Sensitive Hashing).

Зачем нужно обновление без перестроения
В реальных RAG-системах данные постоянно добавляются: новые документы, пользовательские фидбэки, логи. Полное перестроение индекса (reindex) — дорогая операция (часы на миллионах векторов). Инкрементальное обновление позволяет добавлять векторы «на лету» без остановки сервиса.

2. Проблема: инкрементальные вставки и деградация

Большинство ANN-индексов проектировались для статических наборов данных. При добавлении новых векторов структура индекса может «разбалансироваться»:

• HNSW: новые узлы вставляются в граф, но со временем граф может стать менее оптимальным (появляются длинные пути, снижается recall).
• IVF: новые векторы добавляются в ближайший кластер, но центроиды не обновляются — кластеры смещаются, точность падает.
• PQ: кодовая книга (codebook) фиксирована, новые векторы квантуются с ошибкой, если распределение данных изменилось.

Ключевой компромисс: скорость вставки vs точность поиска. Инкрементальные методы быстры, но требуют периодического «ремонта» (перестроения).

3. HNSW: инкрементальные вставки

HNSW строит иерархический граф: на нижнем уровне — плотный граф, на верхних — разреженные «слои» для быстрого приближения. Новый вектор вставляется так:

1. Выбирается случайный уровень (чем выше уровень, тем меньше вероятность).
2. На каждом уровне находится ближайший узел через жадный поиск.
3. Новый узел соединяется с M ближайшими соседями (параметр M).
4. При необходимости обрезаются лишние рёбра (параметр efConstruction).

Плюсы: вставка за O(log N), не требует перестроения всего графа.
Минусы: со временем граф «засоряется» — новые узлы могут подключаться к неоптимальным соседям, recall падает на 5–15% после 10⁵ вставок (эмпирически).
Рекомендация: перестраивать индекс полностью после каждых N вставок (например, 10% от размера индекса) или при падении recall ниже порога.

4. IVF: кластеризация и перестроение

IVF разбивает пространство на K кластеров (алгоритм K-means). При поиске сначала выбирается несколько ближайших кластеров, затем внутри них — полный перебор.

Проблема обновления:

• Новые векторы приписываются к ближайшему центроиду (без пересчёта центроидов).
• Если распределение данных сдвигается, кластеры становятся нерепрезентативными → recall падает.
• Полное перестроение (пересчёт центроидов + переиндексация всех векторов) — дорого (O(N * K * d)).

Частичное решение:

• IVF with online updates: пересчитывать центроиды только для кластеров, в которые было добавлено много новых векторов (например, каждые 1000 вставок).
• IVF+ADC (Asymmetric Distance Computation): кодовая книга для остаточных векторов тоже требует перестроения.

Вывод: IVF не подходит для частых инкрементальных обновлений. Лучше использовать в сценариях с пакетными добавлениями (раз в день/неделю).

5. Другие методы: PQ, LSH, ScaNN

Практический совет: для production выбирайте HNSW (FAISS, hnswlib) или DiskANN (Microsoft) — последний поддерживает эффективные вставки на SSD.

6. Стратегия hot/warm индексов

Это паттерн для баланса скорости вставки и точности поиска.

• Hot index (горячий): маленький (до 10⁵ векторов), использует HNSW с быстрыми вставками. Обновляется в реальном времени. Поиск идёт параллельно по hot и warm индексам, результаты объединяются (например, top-k из каждого, затем rerank).
• Warm index (тёплый): большой (миллионы векторов), перестраивается раз в N часов/дней (например, ночью). Использует HNSW или IVF с оптимальными параметрами.
• Слияние: после перестроения warm индекса все векторы из hot переносятся в warm, hot очищается.

Преимущества:

• Новые данные доступны сразу (hot).
• Точность поиска не деградирует (warm перестраивается).
• Можно независимо масштабировать hot (in-memory) и warm (SSD).

Недостатки:

• Удвоение потребления памяти (hot + warm).
• Необходимость объединения результатов (дополнительная логика).

7. Практическая реализация на FAISS

FAISS (Facebook AI Similarity Search) — популярная библиотека. Пример инкрементального добавления в HNSW:

import faiss
import numpy as np

d = 128  # размерность эмбеддинга
index = faiss.IndexHNSWFlat(d, M=32)  # M — количество связей
index.hnsw.efConstruction = 200  # качество построения

# Добавление первого батча
vectors1 = np.random.random((10000, d)).astype('float32')
index.add(vectors1)

# Инкрементальное добавление
vectors2 = np.random.random((1000, d)).astype('float32')
index.add(vectors2)  # просто add — HNSW поддерживает

# Поиск
query = np.random.random((1, d)).astype('float32')
D, I = index.search(query, k=5)

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

Для hot/warm можно использовать два индекса:

hot_index = faiss.IndexHNSWFlat(d, M=16)  # быстрее вставка
warm_index = faiss.IndexHNSWFlat(d, M=32) # точнее поиск

def search(query, k=10):
    D_hot, I_hot = hot_index.search(query, k)
    D_warm, I_warm = warm_index.search(query, k)
    # объединение: уникальные ID, сортировка по расстоянию
    combined = merge_results(I_hot, D_hot, I_warm, D_warm)
    return combined[:k]

8. Мониторинг деградации и автоматическое перестроение

Метрики для отслеживания:

• Recall@k на фиксированном тестовом наборе (gold standard). Если recall упал ниже порога (например, 0.85) — запустить перестроение.
• Latency p99 — рост времени поиска может указывать на разбалансировку графа.
• Количество вставок с последнего перестроения — триггер по порогу (например, каждые 100k вставок).

Инструменты:

• FAISS auto-tuning — не для инкрементальных сценариев.
• Собственный мониторинг — логировать метрики в Prometheus/Grafana.

9. Компромиссы и выбор стратегии

Ключевой принцип: никогда не полагайтесь только на инкрементальные вставки — планируйте периодическое полное перестроение (reindex) для поддержания качества.

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

Задача: реализовать hot/warm систему обновления ANN индекса на FAISS с мониторингом деградации.

Инструменты: Python, FAISS, NumPy, Matplotlib (для визуализации recall).

Шаги:

1. Сгенерировать синтетический датасет: 100k векторов (train), 1k тестовых запросов с известными ground truth (ближайшие соседи через brute force).
2. Построить warm индекс (HNSW) на первых 90k векторов.
3. Создать hot индекс (HNSW с меньшим M) и добавить оставшиеся 10k векторов.
4. Имитировать добавление новых векторов порциями по 1000, измеряя recall@10 после каждой порции (поиск по hot+warm).
5. После каждых 10k вставок перестраивать warm индекс (объединяя hot и warm) и сбрасывать hot.
6. Построить график recall от количества вставок — увидеть, как hot/warm стабилизирует recall.

Ожидаемый результат: recall держится выше 0.9, в то время как без перестроения (только hot) recall падает до 0.7 после 50k вставок.

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

12. Навигация

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

Навигация

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