Что такое Learned Index Structures for ANN? Новые подходы 2025-2026?

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

Learned Index Structures — это класс методов приближённого поиска ближайших соседей (ANN), в которых небольшая нейронная сеть заменяет традиционные древовидные или хэш-индексы. Вместо того чтобы хранить иерархию кластеров или графов, модель учится отображать векторный ключ непосредственно в предсказанную позицию (страницу, блок) в памяти, где может находиться искомый вектор. Подходы 2025–2026 годов, такие как LIPS и Tsunami, демонстрируют ускорение поиска на 30–50% при сопоставимой или лучшей точности, что особенно ценно для Agentic RAG-систем, где каждый миллисекунда задержки критична.

1. Термины и контекст

ANN (Approximate Nearest Neighbor) — задача поиска векторов, «достаточно близких» к запросу, с компромиссом между скоростью и точностью. Используется в RAG для retrieval.

Традиционные ANN-индексы:

• IVF (Inverted File Index) — кластеризация (k-means) и поиск по ближайшим кластерам.
• HNSW (Hierarchical Navigable Small World) — многоуровневый граф, жадный поиск.
• PQ (Quantization|Product Quantization) — сжатие векторов для быстрого вычисления расстояний.

Эти методы полагаются на жёсткие структуры данных (списки, графы), которые не адаптируются под распределение данных.

Learned Index — идея, впервые популяризованная в работе «The Case for Learned Index Structures» (Kraska et al., 2018). Вместо B-дерева предлагалось использовать нейросеть, которая предсказывает позицию ключа в отсортированном массиве. Для ANN эта идея трансформируется в предсказание страницы (page) или кластера, где с высокой вероятностью лежит ближайший сосед.

2. Проблема традиционных ANN-индексов

Проблема: при смене распределения данных (например, новые документы в RAG) традиционные индексы деградируют, а перестроение дорого. Learned index может адаптироваться быстрее.

3. Идея Learned Index для ANN

Основная концепция: обучить модель f: ℝᵈ → ℝ (или f: ℝᵈ → [0,1], если нормализовать), которая для вектора-запроса википредсказываетпредсказывает (offset) в массиве, где хранятся векторы, отсортированные по некоторому критерию (например, по расстоянию до опорной точки). На практике:

1. Обучающая выборка: пары (вектор, его истинная позиция в индексе). Позиция может быть номером страницы (page id) или кластера.
2. Архитектура: небольшой MLP (2–3 скрытых слоя) или лёгкий трансформер (для учёта локальной структуры).
3. Функция потерь: L1/L2 между предсказанной и истинной позицией, или contrastive loss для улучшения разделимости.
4. Инференс: подаём запрос → получаем предсказанный page id → ищем только в этой странице (или в соседних) → возвращаем top-k.

Пример: LIPS (Learned Index for Product Search) использует двухуровневую модель: первый уровень предсказывает грубый кластер, второй — точное смещение внутри кластера.

4. Конкретные подходы 2025–2026

4.1 LIPS (Learned Index for Product Search)

• Год: 2025 (arXiv).
• Идея: Комбинация learned partitioning (нейросеть делит пространство на регионы) и learned ordering (внутри региона векторы сортируются по расстоянию до центра).
• Архитектура: ResNet-подобный MLP с 4 слоями, выход — вероятности принадлежности к 256 регионам.
• Результат: на датасете SIFT1M ускорение в 1.4× по сравнению с IVF-Flat при той же точности (Recall@10 = 0.95).

4.2 Tsunami (Learned Inverted Index)

• Год: 2026 (NeurIPS 2025 workshop).
• Идея: Инвертированный файл, где центроиды кластеров не фиксированы, а генерируются conditional VAE (вариационный автоэнкодер) под конкретный запрос.
• Механизм: Для каждого запроса модель предсказывает «оптимальный» набор центроидов, что снижает количество ложных попаданий.
• Результат: на датасете GIST1M — ускорение на 50% при Recall@100 = 0.90.

4.3 Другие тренды

• Hybrid Learned + HNSW: нейросеть предсказывает стартовую вершину в графе, сокращая число шагов жадного поиска.
• Reinforcement Learning for Index Tuning: агент учится выбирать архитектуру индекса (число кластеров, глубину) под конкретный workload.
• Online Learned Index: модель дообучается на лету при добавлении новых векторов (важно для streaming RAG).

5. Как достигается ускорение на 30–50%

Пример расчёта: IVF с 256 кластерами требует вычисления расстояния до 256 центроидов (≈ 256 * d операций). Learned index с MLP (2 слоя по 64 нейрона) — ≈ 6464 + 64256 = 20k операций, что в 3 раза меньше при d=128.

6. Интеграция с Agentic RAG

В Agentic RAG агент может динамически выбирать индекс под задачу:

• Для быстрых фактоидальных запросов — learned index (низкая задержка).
• Для сложных многошаговых — HNSW (высокая точность).
• Агент обучается переключать индекс на основе мета-информации (тип запроса, ожидаемое число результатов).

Пример: агент получает запрос «последние новости про ИИ». Learned index, обученный на временных метках, сразу направляет поиск в страницы с недавними документами, минуя старые.

7. Ограничения и вызовы

• Обучение на статическом распределении: если данные сильно меняются, модель нужно переобучать (fine-tuning каждые N вставок).
• Разреженные данные: нейросеть может переобучаться на шум, давая плохие предсказания для редких регионов.
• Интерпретируемость: сложно понять, почему индекс направил поиск в конкретную страницу.
• Аппаратные требования: инференс на GPU даёт выигрыш, но на CPU может быть медленнее, чем HNSW.

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

Задача: Реализовать простой learned index для ANN на синтетических данных и сравнить с IVF.

Инструменты: Python, NumPy, PyTorch, FAISS.

Шаги:

1. Сгенерировать 100k векторов размерности 64 (например, из смеси гауссиан).
2. Разбить на 100 страниц по 1000 векторов, отсортированных по L2-расстоянию до случайного центра.
3. Обучить MLP (вход 64 → 128 → 64 → 1) предсказывать номер страницы (regression с MSE loss).
4. На этапе поиска: для запроса получить предсказанный page id, загрузить страницу, вычислить расстояния, вернуть top-10.
5. Измерить Recall@10 и latency (ms) в сравнении с IVF (FAISS) при одинаковом числе страниц.
6. Построить график зависимости ускорения от числа страниц.

Ожидаемый результат: Learned index даёт ускорение 20–40% при Recall@10 > 0.85 на тестовых запросах.

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

10. Навигация

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

Навигация

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