Как вы измеряете recall@k для ANN индекса и какой порог acceptable?

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

Recall@k для ANN (Approximate Nearest Neighbor) индекса — это доля истинных k ближайших соседей (по точному расстоянию), которые попали в top-k результатов приближённого поиска. Измеряется путём сравнения результатов ANN с результатами точного поиска (brute force) на репрезентативной подвыборке запросов. Приемлемый порог зависит от задачи: для большинства production-систем recall@10 > 0.95 считается хорошим, >0.99 — отличным, но всегда нужно учитывать компромисс с задержкой (latency).

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

• ANN (Approximate Nearest Neighbor) — алгоритм, который находит приближённые ближайшие соседи быстрее, чем точный перебор, за счёт аппроксимации (кластеризация, графы, квантование). Примеры: IVF, HNSW, PQ.
• Recall@k — метрика полноты для top-k результатов. Формула:

  recall@k = (количество истинных ближайших соседей среди top-k результатов ANN) / k
  

  (обычно k — то же число, что и в запросе, например k=10).
• Точный поиск (brute force) — полный перебор всех векторов в базе для вычисления точных расстояний. Используется как ground truth.
• Подвыборка (query set) — набор запросов, на которых проводится измерение. Должна быть репрезентативной (похожа на реальные запросы).

2. Зачем измерять recall@k для ANN?

ANN — это компромисс между скоростью и точностью. Без измерения recall@k вы не знаете, насколько сильно пожертвовали качеством ради производительности. Метрика позволяет:

• Выбрать параметры индекса (например, nprobe для IVF, efConstruction для HNSW).
• Сравнить разные типы индексов.
• Убедиться, что retrieval в RAG-системе не теряет релевантные документы.

3. Методология измерения

3.1 Подготовка ground truth

1. Выберите подвыборку из 100–1000 запросов (векторов), не участвовавших в построении индекса.
2. Для каждого запроса выполните точный поиск по всей базе (или по её репрезентативной части, если база слишком велика). Получите список истинных k ближайших соседей (их ID и расстояния).

3.2 Запуск ANN

3. Для тех же запросов выполните поиск через ANN-индекс с теми же k.
4. Для каждого запроса подсчитайте, сколько ID из top-k ANN совпадают с ID из ground truth.

3.3 Вычисление recall@k

5. Усредните по всем запросам:

   recall@k = ([[1. Как бы вы спроектировали RAG-систему для 10 000 документов с разной структурой|1]] / N_queries) * sum( |intersection(ANN_top_k, GT_top_k)| / k )
   

3.4 Учёт дубликатов и расстояний

• Если в базе есть векторы с одинаковым расстоянием (например, дубликаты), recall может быть занижен. В таких случаях используют recall с учётом ранга или допускают несколько правильных ответов.
• Для больших баз ground truth можно получить только на подвыборке векторов (например, 10% от базы), чтобы ускорить точный поиск.

4. Пример на Python с FAISS

import faiss
import numpy as np

# Генерация синтетических данных
d = 128  # размерность
n_total = 100000  # количество векторов в базе
n_queries = 500   # количество запросов

xb = np.random.random((n_total, d)).astype('float32')
xq = np.random.random((n_queries, d)).astype('float32')

# Точный поиск (ground truth)
index_flat = faiss.IndexFlatL2(d)
index_flat.add(xb)
D_gt, I_gt = index_flat.search(xq, k=10)  # I_gt — ID истинных соседей

# ANN индекс (IVF)
nlist = 100
quantizer = faiss.IndexFlatL2(d)
index_ivf = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
index_ivf.train(xb)
index_ivf.add(xb)
index_ivf.nprobe = 10  # количество просматриваемых кластеров

D_ann, I_ann = index_ivf.search(xq, k=10)

# Вычисление recall@10
recalls = []
for i in range(n_queries):
    gt_set = set(I_gt[i])
    ann_set = set(I_ann[i])
    recall = len(gt_set & ann_set) / 10.0
    recalls.append(recall)

mean_recall = np.mean(recalls)
print(f"Recall@10 = {mean_recall:.4f}")

5. Факторы, влияющие на recall@k

6. Приемлемые пороги recall@k

Порог зависит от требований к качеству и допустимой задержки.

Важно: recall@k не должен быть единственной метрикой. Смотрите также latency (p50, p99) и пропускную способность (QPS).

7. Другие метрики для ANN

• Recall@1 — доля запросов, где ближайший сосед найден точно. Жёстче, чем recall@10.
• Precision@k — доля релевантных среди top-k (но для ANN ground truth — это именно ближайшие соседи, поэтому precision@k = recall@k, если k одинаково).
• MAP (Mean Average Precision) — усреднённая точность по рангам.
• NDCG — учитывает порядок результатов.

8. Типичные ошибки при измерении

• Перекос подвыборки: если запросы не похожи на реальные, recall будет нерепрезентативен.
• Игнорирование дубликатов: если в базе есть одинаковые векторы, точный поиск может вернуть любой из них, а ANN — другой, что занизит recall.
• Смещение из-за метрики расстояния: ground truth должен считаться той же метрикой (L2, cosine, dot), что и ANN.
• Измерение на всей базе: для больших баз (миллиарды) точный поиск невозможен — используют sampling или оценку через recall на подмножестве.

9. Инструменты для измерения

• FAISS — встроенные функции range_search и search; можно легко сравнить с IndexFlat.
• Scann (Google) — предоставляет метрики качества.
• Annoy — нет встроенного ground truth, нужно реализовать самому.
• Pinecone / Weaviate / Qdrant — облачные сервисы, часто предоставляют дашборды с recall@k (на основе случайной выборки).

10. Связь с RAG и retrieval

В RAG recall@k для ANN — это аналог recall@k для retrieval (см. вопрос 5). Разница в том, что в RAG ground truth — это релевантные документы (размеченные человеком), а для ANN — это математически ближайшие соседи. На практике для RAG часто используют recall@k по релевантности, но ANN recall@k — необходимая нижняя проверка: если ANN плохо находит ближайшие векторы, retrieval не сможет найти релевантные документы даже при идеальных эмбеддингах.

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

Задача: Оптимизировать ANN индекс для датасета эмбеддингов (например, SIFT1M или GIST1M) под target recall@10 > 0.97 при минимальной latency.

Инструменты: Python, FAISS, time, matplotlib.

Шаги:

1. Загрузите датасет (можно взять из faiss.contrib.datasets).
2. Постройте точный индекс (IndexFlatL2) и получите ground truth для 1000 запросов.
3. Постройте IVF-индекс с nlist=100.
4. Для nprobe от 1 до 100 измерьте recall@10 и среднее время поиска.
5. Постройте график «recall vs latency» и выберите nprobe, при котором recall > 0.97.
6. Повторите для HNSW (параметр efSearch) и сравните.

Ожидаемый результат: Вы получите практическое понимание trade-off и сможете обоснованно выбирать параметры индекса для production.

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

Навигация

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