vector-similarity-ann.js·4 scenarios
Vector similarity & ANN concept page. Distance metrics (cosine/dot/euclidean), brute-force kNN O(n) baseline, then ANN families (HNSW/IVF/PQ/LSH/ScaNN/DiskANN/Annoy). 4 scenarios: brute-force slow, HNSW logarithmic descent, IVF-PQ billion-scale, filtering pre/post/filterable HNSW. ADR on HNSW vs IVF-PQ vs DiskANN selection.
Любой современный поиск, который понимает смысл («найди похожее по картинке», «вспомни статью про X», «подбери продукт под этот текст»), под капотом сводится к одной задаче: найти ближайших соседей в пространстве embeddings. Embedding — это плотный вектор размерностью обычно 768–4096, в котором каждая компонента не интерпретируется отдельно, но геометрия (расстояния, углы) кодирует смысловую близость.
Точная постановка задачи звучит так: дано N векторов в R^d и query-вектор q, верни K векторов с минимальным расстоянием до q. Метрика — cosine, dot product или L2 (зависит от того, как тренировалась модель). Это kNN — k-nearest neighbors.
Наивное решение — посчитать расстояние от q до каждого из N векторов, отсортировать, вернуть top-K. Сложность O(N·d). На 10M векторов размерности 1024 это 40 GB чтения и ~5–10 секунд CPU на один запрос. RAG с такими цифрами не работает: пользователь ждать не будет, и кластер в продакшне развалится на первом росте traffic.
ANN (approximate nearest neighbor) решает проблему через осознанный компромисс: жертвуем точностью (recall@10 = 95–99% вместо 100%) ради скорости (1000–10000× быстрее). Вместо линейного скана строим структуру, по которой можно прыгать «почти к нужному месту» за O(log N) или за константу. Все промышленные системы — Spotify recommendations, Pinterest visual search, Twitter «For You», GitHub Copilot retrieval, Google Search, ChatGPT file_search — построены на ANN. Без ANN современного семантического поиска не существует.
Представь карту метро в очень большом городе. Точный kNN — это пешком обойти каждый дом и измерить расстояние до твоей цели. ANN — это «доехать до ближайшей станции, пересесть на узел поближе к цели, в финале пройти пешком пару кварталов».
Главный закон: recall и latency — это slider, не enum. Все ANN-алгоритмы имеют tuning knobs (ef_search для HNSW, nprobe для IVF), и ты явно выбираешь точку на кривой recall-vs-throughput. Измерять recall в проде — обязательно, иначе незаметно сползёшь в «выдаём не то».
Слева сверху — query side: пользователь и query embedder (1024-dim модель, нормализующий вектор так, чтобы cosine == dot product). Справа сверху — brute-force baseline: один процесс, который сканирует все N векторов линейно. Это эталон recall=100% и одновременно anti-pattern для интерактивного поиска.
Снизу слева — HNSW как три слоя: Layer 2 (sparse, длинные прыжки между регионами), Layer 1 (промежуточный), Layer 0 (плотный, фиксирует ef_search кандидатов). Рёбра между слоями показывают descent: query входит на верх и спускается вниз. На канвасе это упрощено — реально каждый слой это граф из тысяч-миллионов узлов.
Снизу справа — IVF-PQ: nlist центроидов (k-means), три представительных кластера с PQ-кодами по 16 байт каждый, и отдельная нода rerank на raw float32. Edges от centroids к кластерам — fanout query на nprobe ближайших; edges от кластеров к rerank — gather top-N кандидатов для финального refinement.
Внизу — payload index (фильтрация): отдельный B-tree/KV индекс по бизнес-полям (category, year). Подключён к HNSW Layer 0 и к embedder напрямую — это иллюстрирует три стратегии фильтрации (post-filter, pre-filter, filterable HNSW), которые разбираются в соответствующем сценарии.
ADR на ноде brute-force scan содержит детальный decision tree по выбору ANN-алгоритма в зависимости от размера датасета, бюджета памяти и latency. Открывай его при выборе для конкретного проекта.
1. brute-force. Линейный скан N векторов, разбор трёх distance metrics (cosine для нормализованных text embeddings, L2 для image embeddings, dot для рекомендашек без нормализации), демонстрация cost (40 GB чтения, 5–10 секунд CPU на одном запросе) и явное падение в showError. Финальный месседж — где brute-force допустим (eval pipeline, <100K vectors) и где это антипаттерн.
2. hnsw-descent. Query → embedder → entry на Layer 2 → greedy walk → descend на Layer 1 → descend на Layer 0 → beam search ef_search=50 → top-K. Все ключевые knobs (M, ef_construction, ef_search) и их влияние на recall/latency/память. Memory math для 100M×1024-dim (600 GB RAM, r6i.16xlarge ~$4/h). Два explicit failure modes: recall cliff (распределение данных поплыло) и cold start (первые 1000 inserts строят непредставительный граф).
3. ivf-pq. Query → routing к nlist=3162 центроидам → nprobe=8 ближайших → parallel scan кластеров с PQ-кодами → asymmetric distance lookup → gather top-100 → rerank на raw float32 → top-K. Объясняет, почему PQ обязательно с rerank, и упоминает варианты OPQ/ScaNN, дающие +5–10% recall. Два антипаттерна: PQ без rerank и cosine/L2 mismatch.
4. filtering. Самая частая боль в продакшне. Один и тот же запрос «best running shoes WHERE category=footwear AND year=2024» прогоняется тремя способами: post-filter (ANN top-100 → drop по payload — теряем top-K при sparse фильтре), pre-filter (фильтр → brute-force на subset — медленно при большом subset), filterable HNSW (Qdrant подход — payload condition encoded в graph traversal с adaptive fallback). Заканчивается двумя ловушками: filter explosion и multi-tenant без collection-per-tenant.
На ноде brute-force scan есть ADR-001: HNSW vs IVF(-PQ) vs DiskANN — when to pick each ANN algorithm. Кратко decision tree:
Universal tuning законы: M ↑ → recall ↑ + память ↑ + build ↑; ef_search ↑ → recall ↑ + latency ↑ (линейно); nprobe ↑ → recall ↑ + latency ↑ (линейно); PQ M ↓ → память ↓ + recall ↓ агрессивно. Always: metric должен совпадать с той, под которую тренировалась модель; нормализованные векторы делают cosine == dot; измерять recall@10 на 1K golden queries; мониторить recall в проде (recall cliff незаметен).
WHERE фильтры, но без filterable HNSW (post-filter промахивается).tenant=X поверх общего графа медленный и небезопасный. Делай collection-per-tenant.embeddings-basics (как вектора получаются и почему cosine), qdrant-vector-db (operational сторона), rag-architecture (как ANN встраивается в полный RAG-пайплайн).