дорожка · 13.11.2026 · поиск соседей

Как найти ближайшие векторы среди миллионов: приближённый поиск соседей

В прошлой дорожке мы учили модель ставить вопрос рядом с нужным текстом. Но когда векторов миллионы, сравнить вопрос с каждым становится дорого, и векторные базы ищут соседей приблизительно. Узкий вопрос дня: как устроены индексы приближённого поиска ближайших соседей (approximate nearest neighbor search) — ячейки IVF, граф HNSW, сжатие PQ — и чем каждый платит за скорость. Все примеры ниже запускались на коробке на 100 000 игрушечных векторах длины 64, собранных в 1000 сгустков, как эмбеддинги текстов по темам; поиск написан вручную на numpy, чтобы было видно каждый шаг. Время в миллисекундах — замер на коробке, оно зависит от машины; надёжнее смотреть на число сравнений. Цифры из чужих работ помечены как опубликованные.

Все дорожки — /put. Прошлая — контрастное обучение.

1 Точный перебор и как мерить «приблизительно»: доля найденных соседей

Зачем это в работе. Любая векторная база — Qdrant, Milvus, pgvector в PostgreSQL, библиотека Faiss — на вопрос «найди 10 ближайших векторов» почти всегда отвечает не точно, а приблизительно. Она может пропустить часть настоящих соседей, и сама об этом не скажет: выдача выглядит нормально. Чтобы выбрать настройки индекса, понять, почему RAG вдруг перестал находить нужный кусок, или решить, нужен ли индекс вообще, надо уметь посчитать, сколько соседей потеряно и сколько работы сэкономлено. Отправная точка — точный перебор и мера, с которой сравнивают всё остальное.

Как это устроено. Точный перебор (brute force, в Faiss — «плоский» индекс, flat): вопрос-вектор сравнивают с каждым вектором базы, считают N косинусов и берут k самых больших. Для векторов длины 1 косинус равен скалярному произведению, поэтому вся работа — одно умножение матрицы базы на вектор вопроса. Затраты растут прямо пропорционально числу векторов N и их длине d: вдвое больше документов — вдвое больше работы на каждый вопрос. Память тоже линейна: вектор из 64 чисел в формате float32 занимает 256 байт, из 1024 чисел — 4 КиБ, и миллион таких векторов — уже около 4 ГиБ, которые надо держать в памяти и прочитывать на каждом вопросе.

Отбор k лучших не требует сортировать все N чисел. Функция частичного отбора (в numpy — argpartition) за один проход откладывает k лучших в начало, и сортируют уже только их. Поэтому основная цена точного поиска — не сортировка, а сами сравнения и чтение базы из памяти.

Приближённый поиск ближайших соседей (approximate nearest neighbor, ANN) сравнивает вопрос не со всеми, а только с небольшой частью базы, выбранной по заранее построенной структуре — индексу. Качество меряют долей найденных соседей (recall@k): берут настоящие k ближайших из точного перебора и смотрят, какая их доля попала в выдачу индекса. Recall@10 = 0,9 значит, что в среднем 9 из 10 настоящих соседей найдены, а один заменён чуть более далёким вектором. Вторая ось — цена: сколько векторов пришлось сравнить, сколько миллисекунд и памяти это заняло. Каждый индекс даёт кривую «доля найденных против цены», и настройка индекса — это выбор точки на ней.

Чем это отличается от соседних понятий. Recall@10 индекса — не то же самое, что качество поиска для пользователя из дорожки про поиск: там «правильный» документ определял человек, а здесь «правильные» — просто математически ближайшие векторы. Если модель эмбеддингов плохая, идеальный индекс честно найдёт плохих соседей. Ошибка индекса добавляется поверх ошибки модели.

Подробный пример. Строим базу: 1000 центров тем в 64-мерном пространстве, вокруг каждого — сгусток векторов разной ширины, всего 100 000 векторов, все нормированы к длине 1. 500 вопросов берём из тех же тем, но это новые точки, которых нет в базе. Считаем точных 10 соседей для каждого вопроса — это эталон для всех следующих ступеней — и замеряем время перебора на одном вопросе при разном размере базы.

import numpy as np, time

def l2n(x):
    return x / np.linalg.norm(x, axis=1, keepdims=True)

def make_base(n=100_000, d=64, n_clusters=1000, seed=0):
    """Смесь сгустков: как эмбеддинги текстов, которые собираются по темам."""
    rng = np.random.default_rng(seed)
    centers = rng.normal(size=(n_clusters, d))
    spread = rng.uniform(0.5, 1.5, size=n_clusters)       # сгустки разной ширины
    lab = rng.integers(0, n_clusters, size=n)
    x = centers[lab] + spread[lab, None] * rng.normal(size=(n, d))
    q_lab = rng.integers(0, n_clusters, size=500)
    q = centers[q_lab] + spread[q_lab, None] * rng.normal(size=(500, d))
    return l2n(x).astype(np.float32), l2n(q).astype(np.float32), lab

def exact_topk(base, q, k=10):
    s = q @ base.T                                   # косинусы: векторы уже длины 1
    idx = np.argpartition(-s, k, axis=1)[:, :k]      # k лучших без полной сортировки
    order = np.argsort(-np.take_along_axis(s, idx, 1), axis=1)
    return np.take_along_axis(idx, order, 1)

def recall_at_k(found, truth):
    """Доля настоящих k ближайших, которые нашёл приближённый поиск."""
    k = truth.shape[1]
    return np.mean([len(set(f[:k]) & set(t)) / k for f, t in zip(found, truth)])

def kmeans(x, k, iters=10, seed=0):
    rng = np.random.default_rng(seed)
    c = x[rng.choice(len(x), k, replace=False)].copy()
    for _ in range(iters):
        a = np.argmax(x @ c.T - 0.5 * (c * c).sum(1), axis=1)   # ближайший центр по расстоянию
        for j in range(k):
            m = a == j
            if m.any(): c[j] = x[m].mean(0)
    return c

def assign(x, c, chunk=20000):
    out = []
    for i in range(0, len(x), chunk):
        xx = x[i:i+chunk]
        out.append(np.argmax(xx @ c.T - 0.5 * (c * c).sum(1), axis=1))
    return np.concatenate(out)
from common import *
base, q, _ = make_base()
print("векторов:", base.shape, " память float32:", round(base.nbytes / 2**20, 1), "МиБ")
truth = exact_topk(base, q); np.save("truth.npy", truth)
for n in (25_000, 50_000, 100_000):
    b = base[:n]; ts = []
    for i in range(200):
        t = time.perf_counter(); exact_topk(b, q[i:i+1]); ts.append(time.perf_counter() - t)
    print(f"N = {n:6d}: медиана {np.median(ts)*1000:.3f} мс на вопрос, сравнений на вопрос {n}")
s = np.sort(q[:3] @ base.T, axis=1)[:, ::-1]
for row in s: print("косинусы 1-го, 10-го, 11-го, 100-го соседа:", np.round(row[[0, 9, 10, 99]], 4))
gap = np.sort(q @ base.T, axis=1)[:, ::-1]
print("средний зазор между 10-м и 11-м соседом:", round(float(np.mean(gap[:, 9] - gap[:, 10])), 4))

У нас этот код напечатал:

векторов: (100000, 64)  память float32: 24.4 МиБ
N =  25000: медиана 0.073 мс на вопрос, сравнений на вопрос 25000
N =  50000: медиана 0.145 мс на вопрос, сравнений на вопрос 50000
N = 100000: медиана 0.641 мс на вопрос, сравнений на вопрос 100000
косинусы 1-го, 10-го, 11-го, 100-го соседа: [0.6589 0.5956 0.5956 0.4264]
косинусы 1-го, 10-го, 11-го, 100-го соседа: [0.5968 0.4793 0.4786 0.3965]
косинусы 1-го, 10-го, 11-го, 100-го соседа: [0.5361 0.4621 0.4618 0.3935]
средний зазор между 10-м и 11-м соседом: 0.0034

Что видно. База из 100 000 коротких векторов занимает 24,4 МиБ, и один вопрос перебором обходится меньше миллисекунды — для такого объёма индекс не нужен вовсе. При удвоении базы с 25 до 50 тысяч время выросло ровно вдвое (0,073 → 0,145 мс), а при переходе к 100 тысячам — вчетверо: база перестала помещаться в быстрый кэш процессора, и упёрлись в скорость чтения памяти. Важнее вторая половина вывода: 10-й и 11-й соседи различаются по косинусу в среднем на 0,0034, а в первой строке совпадают до четвёртого знака. Значит, если индекс вернул 11-го вместо 10-го, recall@10 упал, но для пользователя разницы нет. Recall — строгая мера, и потеря нескольких процентов на ней часто незаметна в ответах; потеря же половины соседей заметна всегда.

Где обычно ошибаются.

  • Ставят индекс приближённого поиска на базу в десятки тысяч векторов. Перебор там занимает доли миллисекунды и не теряет ни одного соседа; индекс добавляет только настройки и ошибки.
  • Оценивают индекс по «выдача выглядит разумно». Без точного перебора на своих же вопросах потерю соседей не увидеть; эталон нужно посчитать хотя бы на нескольких сотнях вопросов.
  • Берут чужие кривые скорости из обзоров вроде ann-benchmarks и переносят на свою базу. Кривая зависит от данных, длины векторов и машины; мерить надо на своём.

Словарь ступени.

Точный перебор (brute force, flat). Сравнение вопроса с каждым вектором базы; находит настоящих соседей ценой N сравнений.

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

Индекс. Заранее построенная структура над базой векторов, которая подсказывает, с кем сравнивать вопрос.

Доля найденных соседей (recall@k). Какая часть настоящих k ближайших попала в выдачу индекса, от 0 до 1.

Частичный отбор (argpartition). Выбор k лучших из N чисел без сортировки всех N.

float32. Формат числа с плавающей точкой, занимающий 4 байта; обычный формат хранения эмбеддингов.

Faiss. Открытая библиотека Meta для поиска ближайших векторов, в которой есть и перебор, и все индексы этой дорожки.

Векторная база (vector database). Хранилище, которое держит векторы вместе с данными и умеет искать по ним соседей.

2 Ячейки IVF: сначала выбрать районы, потом искать внутри

Зачем это в работе. Индекс с ячейками (IVF) — самый простой и понятный способ ускорить поиск, и он лежит в основе многих настроек Faiss, Milvus и индекса ivfflat в pgvector. У него один главный рычаг — сколько ячеек просматривать, — и по нему хорошо видно общий закон всего приближённого поиска: скорость покупается потерей соседей, и потеря эта неравномерна. Если вы видите в настройках слова nlist и nprobe, это он.

Как это устроено. Шаг первый, обучение индекса: на выборке векторов запускают кластеризацию k-средних (k-means) — алгоритм, который ищет nlist центров так, чтобы каждый вектор был близко к своему центру. Шаг второй, наполнение: каждый вектор базы относят к ближайшему центру и кладут в список этой ячейки. Получается «перевёрнутый файл» (inverted file, отсюда IVF): для каждого центра — список его векторов, как в книжном указателе для каждого слова — список страниц.

Шаг третий, поиск: вопрос сравнивают со всеми nlist центрами (это дёшево, центров сотни или тысячи), берут nprobe ближайших ячеек и уже внутри них перебирают векторы точно. При nprobe = 1 смотрим одну ячейку — это примерно 1/nlist базы. При nprobe = nlist просматриваем всё и получаем точный перебор.

Главное ограничение — граница ячеек. Настоящий сосед может лежать в соседней ячейке, если вопрос оказался у края своей. В многомерном пространстве почти всё лежит «у края»: у каждой ячейки очень много соседних, и ближайшие соседи вопроса часто расползаются по нескольким. Поэтому recall растёт с nprobe медленно, а не скачком.

Чем это отличается от соседей. Обычная кластеризация нужна, чтобы понять данные; здесь центры — просто способ разрезать пространство на районы, и «смысловых» тем от них не ждут. От графа (третья ступень) IVF отличается тем, что структура грубая и одинаковая для всех вопросов, зато её легко хранить на диске, делить между машинами и сочетать со сжатием (четвёртая ступень).

Подробный пример. Учим 256 центров на 20 000 случайных векторах, раскладываем все 100 000 по ячейкам и для nprobe от 1 до 64 меряем recall@10 и долю просмотренной базы. Отдельно считаем, какая доля настоящих соседей лежит в той же ячейке, что и вопрос.

from common import *
base, q, _ = make_base(); truth = np.load("truth.npy")
rng = np.random.default_rng(1)
nlist = 256
cent = kmeans(base[rng.choice(len(base), 20_000, replace=False)], nlist)   # центры учим на выборке
cell = assign(base, cent)
lists = [np.where(cell == j)[0] for j in range(nlist)]
sizes = np.array([len(l) for l in lists])
print(f"ячеек {nlist}; размер ячейки: мин {sizes.min()}, медиана {int(np.median(sizes))}, макс {sizes.max()}")

def ivf_search(qv, nprobe, k=10):
    near = np.argsort(-(cent @ qv - 0.5 * (cent * cent).sum(1)))[:nprobe]   # nprobe ближайших ячеек
    cand = np.concatenate([lists[j] for j in near])
    s = base[cand] @ qv
    return cand[np.argsort(-s)[:k]], len(cand)

for nprobe in (1, 2, 4, 8, 16, 32, 64):
    found, scanned = zip(*(ivf_search(v, nprobe) for v in q))
    print(f"nprobe = {nprobe:2d}: recall@10 = {recall_at_k(np.array(found), truth):.3f}, "
          f"просмотрено {np.mean(scanned)/len(base)*100:5.1f}% базы")
# где лежат настоящие соседи относительно ячейки вопроса
qcell = assign(q, cent)
same = np.mean(cell[truth] == qcell[:, None])
print(f"доля настоящих 10 соседей в той же ячейке, что и вопрос: {same:.3f}")

У нас этот код напечатал:

ячеек 256; размер ячейки: мин 93, медиана 396, макс 842
nprobe =  1: recall@10 = 0.578, просмотрено   0.5% базы
nprobe =  2: recall@10 = 0.647, просмотрено   0.9% базы
nprobe =  4: recall@10 = 0.705, просмотрено   1.9% базы
nprobe =  8: recall@10 = 0.772, просмотрено   3.9% базы
nprobe = 16: recall@10 = 0.846, просмотрено   7.8% базы
nprobe = 32: recall@10 = 0.907, просмотрено  15.5% базы
nprobe = 64: recall@10 = 0.962, просмотрено  30.5% базы
доля настоящих 10 соседей в той же ячейке, что и вопрос: 0.578

Что видно. Ячейки неравные: от 93 до 842 векторов, хотя в среднем по 390; в больших ячейках поиск дороже. При nprobe = 1 просмотрено полпроцента базы и найдено 58% соседей — ровно та доля, которая лежит в ячейке вопроса. Каждое удвоение nprobe удваивает работу, а recall прибавляет всего 5–7 пунктов: чтобы дойти до 0,96, пришлось просмотреть почти треть базы. Наши данные специально сделаны трудными — сгустки широкие и перекрываются, — у настоящих эмбеддингов кривая обычно лучше, но форма у неё та же: последние проценты recall самые дорогие.

Где обычно ошибаются.

  • Оставляют nprobe по умолчанию. В Faiss он по умолчанию равен 1, в pgvector у ivfflat параметр probes тоже по умолчанию 1; это самая быстрая и самая неточная точка кривой.
  • Учат центры на слишком маленькой или нерепрезентативной выборке, например на первых по времени документах. Тогда ячейки получаются очень разного размера, и поиск в больших ячейках становится медленным (пятая ступень).
  • Берут nlist наугад. Слишком мало ячеек — каждая огромная и ускорения нет; слишком много — соседи разбросаны и нужен большой nprobe. Обычно начинают с порядка корня из N и подбирают по замеру.

Словарь ступени.

Индекс с ячейками (IVF, inverted file). Индекс, который делит векторы по ближайшим центрам и при поиске смотрит только несколько ячеек.

k-средних (k-means). Алгоритм кластеризации, который подбирает k центров, чередуя «отнеси точки к ближайшему центру» и «сдвинь центр в среднее своих точек».

Центр ячейки (centroid). Средний вектор группы; по нему решают, в какую ячейку класть вектор и какие ячейки смотреть.

nlist. Число ячеек, на которые делят базу.

nprobe. Сколько ближайших к вопросу ячеек просматривать при поиске; главный рычаг «скорость против точности» у IVF.

Граница ячеек. Место, где вопрос лежит в одной ячейке, а его соседи — в другой; главная причина потерь IVF.

Список ячейки (inverted list). Перечень номеров векторов, отнесённых к одному центру.

3 Поиск по графу соседей: HNSW, M и ef

Зачем это в работе. Граф HNSW — самый распространённый индекс в векторных базах: он по умолчанию или как основной вариант стоит в Qdrant, Weaviate, Milvus, pgvector, Elasticsearch и OpenSearch. У него три параметра, которые встречаются везде под похожими именами: M, ef_construction и ef (в pgvector — m, ef_construction и hnsw.ef_search). Понимая, как идёт поиск по графу, вы поймёте, что именно меняет каждый из них и почему граф «помнит» удалённые записи.

Как это устроено. Каждый вектор — вершина графа, и у каждой есть список из нескольких соседей — рёбер к близким векторам. Поиск — жадный обход: начинаем с входной вершины, смотрим её соседей, переходим к тем, что ближе к вопросу, и так далее, пока улучшаться некуда. Чтобы не застрять в первой же «ямке», держат не одного лучшего, а список ef лучших найденных (лучевой поиск, beam search) и раскрывают кандидатов, пока ближайший нераскрытый не окажется хуже худшего в этом списке. Чем больше ef, тем дольше обход и тем меньше потерянных соседей. ef должен быть не меньше k.

Связность важнее близости. Если брать в соседи только M самых близких, граф распадается на островки: вершины плотного сгустка ссылаются только друг на друга, и от входа до нужного сгустка дороги нет. Поэтому в HNSW (Malkov и Yashunin, опубликовано в 2016 году) рёбра делают двусторонними и выбирают соседей с эвристикой: кандидат не добавляется, если он ближе к уже выбранному соседу, чем к самой вершине. Так в списке остаются рёбра в разные стороны, а не десять ссылок внутрь одного комка.

Этажи. Буква H — иерархия: часть вершин случайно попадает на верхние этажи, где их мало и рёбра длинные. Поиск начинается сверху, быстро спускается к нужному району и продолжается на нижнем этаже, где есть все вершины. Авторы показывают, что так число шагов растёт примерно как логарифм от размера базы. Параметр M — сколько соседей у вершины (больше M — больше памяти и точнее), ef_construction — ширина того же лучевого поиска при вставке вершины (больше — дольше строится и лучше граф), ef — ширина при запросе.

Ограничения. Граф целиком живёт в памяти, и сверх векторов он хранит рёбра: при M = 16 это десятки номеров на вершину. Вставлять легко, а удалять трудно: удалённую вершину обычно лишь помечают, и обход продолжает идти через неё. Отличие от IVF: там каждый вопрос просматривает одинаковые по форме районы, а граф сам подстраивает маршрут под вопрос и при той же точности обычно сравнивает меньше векторов.

Подробный пример. Строим упрощённый граф на 20 000 векторах: каждому даём 12 точных ближайших соседей. Сравниваем три варианта рёбер — только ближайшие, плюс обратные рёбра, плюс ещё 4 случайных длинных ребра на вершину — и вариант с упрощённым «верхним этажом» из 200 случайных вершин. Это не настоящий HNSW: нет эвристики выбора соседей и нескольких этажей, но механика обхода и роль ef та же.

import heapq
from common import *
base, q, _ = make_base(n=20_000)          # граф строим на 20 000 векторах, чтобы хватило минуты
truth = exact_topk(base, q)
M = 12
nbr = np.empty((len(base), M), dtype=np.int64)
for i in range(0, len(base), 2000):        # точные M ближайших для каждого вектора
    s = base[i:i+2000] @ base.T
    s[np.arange(len(s)), np.arange(i, i+len(s))] = -9   # себя не берём
    nbr[i:i+2000] = np.argpartition(-s, M, axis=1)[:, :M]

def with_reverse(nbr):
    g = [set(r) for r in nbr]
    for a, row in enumerate(nbr):
        for b in row: g[b].add(a)              # обратные рёбра: «меня считает соседом — я его тоже»
    return [np.array(sorted(x)) for x in g]

def with_random(g, r=4, seed=0):
    rng = np.random.default_rng(seed)
    return [np.concatenate([x, rng.integers(0, len(g), r)]) for x in g]

def beam_search(g, qv, ef, k=10, entry=0):
    seen = {entry}; d0 = -float(base[entry] @ qv); comps = 1
    cand = [(d0, entry)]; best = [(-d0, entry)]          # cand — кого раскрыть, best — лучшие ef найденных
    while cand:
        d, v = heapq.heappop(cand)
        if len(best) >= ef and d > -best[0][0]: break    # ближайший нераскрытый хуже худшего из лучших — стоп
        for u in g[v]:
            if u in seen: continue
            seen.add(u); du = -float(base[u] @ qv); comps += 1
            if len(best) < ef or du < -best[0][0]:
                heapq.heappush(cand, (du, u)); heapq.heappush(best, (-du, u))
                if len(best) > ef: heapq.heappop(best)
    top = sorted(best, reverse=True)[:k]
    return [u for _, u in top], comps

def reach(g, start=0):
    seen = {start}; st = [start]
    while st:
        v = st.pop()
        for u in g[v]:
            if u not in seen: seen.add(u); st.append(u)
    return len(seen)

graphs = {"только M ближайших": [np.array(r) for r in nbr]}
graphs["+ обратные рёбра"] = with_reverse(nbr)
graphs["+ обратные + 4 случайных"] = with_random(graphs["+ обратные рёбра"])
for name, g in graphs.items():
    print(f"{name}: из входа достижимо {reach(g)} из {len(base)}, рёбер на вершину {np.mean([len(x) for x in g]):.1f}")
    for ef in (10, 40, 160):
        res = [beam_search(g, v, ef) for v in q]
        found = np.array([r[0] for r in res]); comps = np.mean([r[1] for r in res])
        print(f"   ef = {ef:3d}: recall@10 = {recall_at_k(found, truth):.3f}, сравнений {comps:6.0f} ({comps/len(base)*100:.1f}% базы)")
# Упрощённый «верхний этаж» как в HNSW: 200 случайных вершин; сначала ищем ближайшую из них, с неё входим вниз
top = np.random.default_rng(2).choice(len(base), 200, replace=False)
g = graphs["+ обратные рёбра"]
print("+ обратные рёбра, вход с верхнего этажа из 200 вершин:")
for ef in (10, 40, 160):
    res = []
    for v in q:
        e = int(top[np.argmax(base[top] @ v)])
        f, c = beam_search(g, v, ef, entry=e); res.append((f, c + 200))
    found = np.array([r[0] for r in res]); comps = np.mean([r[1] for r in res])
    print(f"   ef = {ef:3d}: recall@10 = {recall_at_k(found, truth):.3f}, сравнений {comps:6.0f} ({comps/len(base)*100:.1f}% базы)")

У нас этот код напечатал:

только M ближайших: из входа достижимо 19962 из 20000, рёбер на вершину 12.0
   ef =  10: recall@10 = 0.148, сравнений     87 (0.4% базы)
   ef =  40: recall@10 = 0.435, сравнений    249 (1.2% базы)
   ef = 160: recall@10 = 0.843, сравнений    843 (4.2% базы)
+ обратные рёбра: из входа достижимо 20000 из 20000, рёбер на вершину 15.5
   ef =  10: recall@10 = 0.485, сравнений    155 (0.8% базы)
   ef =  40: recall@10 = 0.835, сравнений    400 (2.0% базы)
   ef = 160: recall@10 = 0.955, сравнений   1232 (6.2% базы)
+ обратные + 4 случайных: из входа достижимо 20000 из 20000, рёбер на вершину 19.5
   ef =  10: recall@10 = 0.517, сравнений    220 (1.1% базы)
   ef =  40: recall@10 = 0.836, сравнений    597 (3.0% базы)
   ef = 160: recall@10 = 0.961, сравнений   1847 (9.2% базы)
+ обратные рёбра, вход с верхнего этажа из 200 вершин:
   ef =  10: recall@10 = 0.534, сравнений    299 (1.5% базы)
   ef =  40: recall@10 = 0.829, сравнений    536 (2.7% базы)
   ef = 160: recall@10 = 0.958, сравнений   1385 (6.9% базы)

Что видно. В графе «только ближайшие» 38 вершин вообще недостижимы от входа, а при ef = 10 найдено лишь 15% соседей: обход застревает в чужом сгустке. Обратные рёбра — самая дешёвая починка: при том же ef recall вырос втрое, до 0,49, а при ef = 160 дошёл до 0,955, и для этого понадобилось сравнить 6% базы. Случайные длинные рёбра и вход с верхнего этажа на 20 000 вершинах почти ничего не добавили: база маленькая, и от любого входа до цели несколько шагов. Их выигрыш виден на миллионах вершин, где путь от случайного входа долгий, — это опубликованный результат авторов HNSW, а не наш замер.

Где обычно ошибаются.

  • Поднимают M, когда надо поднять ef. M меняет граф (нужно перестраивать индекс и платить памятью), а ef меняется на каждом запросе и обычно первым дотягивает recall.
  • Ставят ef меньше, чем число запрашиваемых результатов. Тогда индекс не может вернуть k хороших соседей; часть баз молча поднимает ef до k, часть — нет.
  • Массово удаляют и перезаписывают записи в HNSW и не перестраивают индекс. Помеченные удалёнными вершины остаются в графе, занимают память и ухудшают обход.

Словарь ступени.

HNSW (иерархический граф «малого мира»). Индекс-граф с несколькими этажами, где поиск спускается от редких длинных рёбер к плотным коротким.

Жадный обход графа. Поиск, который всегда переходит к соседу, ближайшему к вопросу, пока может улучшиться.

Лучевой поиск (beam search). Обход, который держит не одного, а несколько лучших кандидатов, чтобы не застрять.

M. Число соседей у вершины графа; влияет на память, время построения и точность.

ef (ef_search). Сколько лучших кандидатов держит поиск по графу; главный рычаг точности на запросе.

ef_construction. Ширина лучевого поиска при вставке вершины; определяет качество построенного графа.

Входная вершина (entry point). Вершина, с которой начинается обход графа.

Связность графа. Можно ли от входа дойти до любой вершины; без неё часть базы недоступна для поиска.

4 Сжатие векторов: произведение квантователей и точный пересчёт

Зачем это в работе. Сотни миллионов векторов длины 768 или 1024 в float32 — это сотни гигабайт, и держать их в памяти дорого. Сжатие произведением квантователей (product quantization, PQ) хранит каждый вектор в нескольких байтах и при этом позволяет быстро считать сходство прямо по сжатым кодам. Им пользуются индексы IVFPQ в Faiss, его варианты стоят в Milvus и в дисковых индексах. Понимать его нужно, чтобы знать, когда сжатие губит поиск и как это лечится пересчётом.

Как это устроено. Шаг первый: вектор длины d режут на m кусков по d/m чисел. Шаг второй: для каждого куска отдельно запускают k-means на 256 центров — это словарь куска (codebook). Шаг третий: каждый кусок вектора заменяют номером ближайшего центра в своём словаре; номер от 0 до 255 помещается в один байт. Вектор превращается в m байт. Вместо 256 байт на вектор длины 64 получаем 8 или 16.

Поиск без распаковки. Для вопроса заранее считают m таблиц по 256 чисел: сходство куска вопроса с каждым центром словаря. Сходство вопроса со сжатым вектором — это просто сумма m чисел, взятых из таблиц по его кодам. Сравнение стоит m чтений из памяти и m сложений вместо d умножений. Вопрос при этом не сжимают — такой способ называют асимметричным расстоянием (asymmetric distance computation, ADC); метод описан Jégou, Douze и Schmid в 2011 году.

Ограничение: код хранит не вектор, а его грубое приближение, и порядок близких соседей путается — разница между 10-м и 11-м соседом обычно меньше ошибки сжатия. Поэтому стандартная схема двухэтапная: по кодам быстро набирают с запасом, например 100–200 кандидатов, а потом пересчитывают их сходство по полным векторам (refine, rerank), которые хранятся на диске или в медленной памяти. Чем меньше байт на вектор, тем больше кандидатов нужно на пересчёт.

Чем это отличается от соседей. Скалярное квантование (scalar quantization) сжимает каждое число отдельно, например из float32 в один байт int8 — это вчетверо меньше и почти без потерь, но не в 32 раза. Двоичное квантование оставляет от каждого числа один бит. Квантование весов модели из дорожки про сжатие весов — родственная идея, но там сжимают параметры сети, а здесь — векторы базы.

Подробный пример. Сжимаем все 100 000 векторов в 8 байт (8 кусков по 8 чисел) и в 16 байт (16 кусков по 4 числа). Для каждого варианта меряем, насколько восстановленный вектор отличается от исходного, recall@10 только по кодам и recall@10 со взятием 50 или 200 кандидатов и точным пересчётом.

from common import *
base, q, _ = make_base(); truth = np.load("truth.npy")
ks, d = 256, base.shape[1]
rng = np.random.default_rng(3); train = base[rng.choice(len(base), 20_000, replace=False)]
for m in (8, 16):                                       # 8 или 16 кусков, 256 «слов» в каждом
    ds = d // m; print(f'--- m = {m}, длина куска {ds}')
    books = [kmeans(train[:, j*ds:(j+1)*ds], ks, iters=8, seed=j) for j in range(m)]
    codes = np.stack([assign(base[:, j*ds:(j+1)*ds], books[j]) for j in range(m)], 1).astype(np.uint8)
    print("байт на вектор: было", base.shape[1] * 4, "стало", codes.shape[1],
          f"; база {base.nbytes/2**20:.1f} МиБ -> {codes.nbytes/2**20:.2f} МиБ + словари {m*ks*ds*4/1024:.0f} КиБ")
    rec = np.concatenate([books[j][codes[:, j]] for j in range(m)], 1)
    print("средняя ошибка восстановления косинуса с исходным:", round(float(1 - np.mean(np.sum(rec * base, 1) / np.linalg.norm(rec, axis=1))), 4))

    def pq_scores(qv):
        tables = np.stack([books[j] @ qv[j*ds:(j+1)*ds] for j in range(m)])   # m × 256 готовых кусочков сходства
        return tables[np.arange(m), codes].sum(1)                              # сходство = сумма m чисел из таблиц

    found, rerank = {}, {}
    for r in (10, 50, 200):
        f = []
        for v in q:
            s = pq_scores(v)
            cand = np.argpartition(-s, r)[:r]
            if r == 10: f.append(cand[np.argsort(-s[cand])])
            else: f.append(cand[np.argsort(-(base[cand] @ v))][:10])          # пересчёт по точным векторам
        tag = "только по сжатым кодам" if r == 10 else f"взять {r} по кодам, пересчитать точно"
        print(f"{tag:38s}: recall@10 = {recall_at_k(np.array(f), truth):.3f}")

У нас этот код напечатал:

--- m = 8, длина куска 8
байт на вектор: было 256 стало 8 ; база 24.4 МиБ -> 0.76 МиБ + словари 64 КиБ
средняя ошибка восстановления косинуса с исходным: 0.1694
только по сжатым кодам                : recall@10 = 0.344
взять 50 по кодам, пересчитать точно  : recall@10 = 0.759
взять 200 по кодам, пересчитать точно : recall@10 = 0.934
--- m = 16, длина куска 4
байт на вектор: было 256 стало 16 ; база 24.4 МиБ -> 1.53 МиБ + словари 64 КиБ
средняя ошибка восстановления косинуса с исходным: 0.0488
только по сжатым кодам                : recall@10 = 0.549
взять 50 по кодам, пересчитать точно  : recall@10 = 0.953
взять 200 по кодам, пересчитать точно : recall@10 = 0.998

Что видно. 8 байт на вектор сжимают базу в 32 раза — с 24,4 до 0,76 МиБ, — но только по кодам находят треть соседей (0,344). Пересчёт 200 кандидатов по полным векторам возвращает recall до 0,934. С 16 байтами ошибка восстановления падает втрое, по кодам находится уже 55%, а 200 кандидатов с пересчётом дают 0,998 — почти точный поиск при 2 000 точных сравнений вместо 100 000. Итог: само по себе сильное сжатие плохо ранжирует близких соседей, но отлично отсеивает далёких, а точный пересчёт небольшой верхушки дорабатывает остальное.

Где обычно ошибаются.

  • Включают PQ без пересчёта и удивляются, что поиск «стал хуже». Коды нужны для отбора кандидатов, порядок верхушки надо уточнять по полным векторам.
  • Учат словари на чужих или старых векторах. Словарь подогнан под распределение данных; после смены модели эмбеддингов его надо учить заново.
  • Режут вектор на куски, не подумав о неравномерности. Если важная информация сосредоточена в части координат, одни куски сжимаются плохо; поэтому в Faiss есть вариант OPQ, который перед нарезкой поворачивает пространство.

Словарь ступени.

Произведение квантователей (product quantization, PQ). Сжатие, при котором вектор режут на куски и каждый кусок заменяют номером ближайшего центра.

Словарь куска (codebook). Набор из 256 центров для одного куска вектора, обученный k-means.

Код (code). Последовательность номеров центров, которой хранится сжатый вектор; один номер — один байт.

Асимметричное расстояние (ADC). Сравнение несжатого вопроса со сжатыми векторами через заранее посчитанные таблицы.

Точный пересчёт (rerank, refine). Повторная оценка небольшой верхушки кандидатов по полным векторам.

Скалярное квантование (scalar quantization). Сжатие каждого числа вектора по отдельности, например из 4 байт в 1.

IVFPQ. Индекс Faiss, где ячейки IVF сочетаются со сжатием векторов внутри ячеек.

OPQ. Поворот пространства перед нарезкой на куски, чтобы информация распределилась по кускам ровнее.

5 Где индекс ломается: фильтры, новые темы, удаления и мера близости

Зачем это в работе. Индекс, который на тесте давал recall 0,95, в работе часто ведёт себя хуже, и причина почти никогда не в «плохом алгоритме». Её дают условия эксплуатации: поиск с фильтром по метаданным, новые документы не из той темы, на которой строили индекс, удаления, неверно выбранная мера близости. Все эти поломки тихие — выдача не пустая и выглядит правдоподобно. Ниже — что проверять, когда RAG вдруг стал хуже, хотя модель не менялась.

Как это устроено. Фильтр по метаданным. Частый запрос: «ближайшие среди документов моего отдела» или «за последний месяц». Наивное решение — найти 100 ближайших по смыслу, а потом выбросить неподходящие (пост-фильтрация, post-filtering). Если подходит 1% базы, из 100 кандидатов в среднем останется один, а часто ни одного. Есть три выхода: фильтр внутри обхода индекса (смотреть только подходящие векторы в ячейках или на графе, продолжая обход, пока не наберётся k); точный перебор только отфильтрованных, когда их мало (пре-фильтрация, pre-filtering); отдельный индекс на каждое значение частого фильтра. Например, Qdrant фильтрует прямо во время обхода графа, а в pgvector с версии 0.8 появились итеративные проходы индекса, которые добирают результаты после фильтра.

Сдвиг данных. Центры IVF и словари PQ обучены на данных момента построения. Когда приходят документы на новые темы, они набиваются в немногие ячейки, «чужие» им по форме: ячейки раздуваются, поиск в них медленнее, а соседи вопроса разбросаны по разным ячейкам. Графу HNSW это вредит меньше, потому что каждая новая вершина вставляется своим поиском, но и он стареет при массовых удалениях.

Удаления и обновления. В HNSW удалённую вершину обычно только помечают: она не попадает в выдачу, но через неё идёт обход и она занимает память. Если удалить и заново вставить значительную часть базы, граф деградирует — его периодически перестраивают. В IVF удаление проще — вычеркнуть номер из списка ячейки.

Мера близости. Индекс строят под конкретную меру: скалярное произведение, косинус или евклидово расстояние. Для векторов длины 1 все три дают один и тот же порядок соседей, а для ненормированных — разный. Если модель обучали с косинусом, а индекс построен по скалярному произведению на ненормированных векторах, длинные векторы будут «ближе ко всем». Правило из прошлой дорожки работает и здесь: при поиске используйте ту же меру и ту же нормировку, что при обучении модели.

Подробный пример. Два опыта на той же базе. Первый: помечаем случайный 1% документов как «нужный отдел» и сравниваем пост-фильтрацию 100 кандидатов, фильтр внутри просмотра IVF и точный перебор отфильтрованных. Второй: учим центры IVF только на половине тем («старые данные»), раскладываем по ним всю базу и ищем вопросы из новых тем при том же nprobe, сравнивая с центрами, обученными на всём.

from common import *
base, q, lab = make_base(); truth = np.load("truth.npy"); rng = np.random.default_rng(5)

def build_ivf(train, nlist=256):
    c = kmeans(train, nlist); cell = assign(base, c)
    return c, [np.where(cell == j)[0] for j in range(nlist)]

def ivf(c, lists, qv, nprobe, k=10, allow=None):
    near = np.argsort(-(c @ qv - 0.5 * (c * c).sum(1)))[:nprobe]
    cand = np.concatenate([lists[j] for j in near])
    if allow is not None: cand = cand[allow[cand]]          # фильтр внутри просмотра
    return cand[np.argsort(-(base[cand] @ qv))[:k]]

c, lists = build_ivf(base[rng.choice(len(base), 20_000, replace=False)])
# 1) фильтр по метке: «только документы отдела», 1% базы
allow = rng.random(len(base)) < 0.01
truth_f = np.array([np.where(allow)[0][np.argsort(-(base[allow] @ v))[:10]] for v in q])
post = [[i for i in ivf(c, lists, v, 16, k=100) if allow[i]][:10] for v in q]
print(f"сначала 100 по смыслу, потом фильтр: в среднем {np.mean([len(p) for p in post]):.2f} результата из 10, "
      f"пустых выдач {np.mean([len(p) == 0 for p in post])*100:.0f}%")
for npb in (16, 64):
    inside = np.array([ivf(c, lists, v, npb, allow=allow) for v in q], dtype=object)
    print(f"фильтр внутри просмотра, nprobe={npb}: в среднем {np.mean([len(x) for x in inside]):.2f} результата, "
          f"recall@10 = {np.mean([len(set(a) & set(t)) / 10 for a, t in zip(inside, truth_f)]):.3f}")
print("точный перебор только отфильтрованных: сравнений на вопрос", int(allow.sum()), "- recall 1.000 по определению")

# 2) центры ячеек учили на старых данных, а потом пришли новые темы
old = lab < 500
c_old, lists_old = build_ivf(base[old][rng.choice(old.sum(), 20_000, replace=False)])
q_new = l2n(base[~old][rng.choice((~old).sum(), 300, replace=False)] + 0.6 * rng.normal(size=(300, 64)).astype(np.float32) / 8)
t_new = exact_topk(base, q_new)
sizes = np.array([len(l) for l in lists_old])
print(f"центры по старым данным: размер ячейки мин {sizes.min()}, медиана {int(np.median(sizes))}, макс {sizes.max()}")
for name, (cc, ll) in {"центры по всем данным": (c, lists), "центры только по старым": (c_old, lists_old)}.items():
    f = np.array([ivf(cc, ll, v, 8) for v in q_new]); scanned = np.mean([sum(len(ll[j]) for j in np.argsort(-(cc @ v - 0.5*(cc*cc).sum(1)))[:8]) for v in q_new])
    print(f"{name}: новые темы, nprobe=8: recall@10 = {recall_at_k(f, t_new):.3f}, просмотрено {scanned/len(base)*100:.1f}% базы")

У нас этот код напечатал:

сначала 100 по смыслу, потом фильтр: в среднем 0.97 результата из 10, пустых выдач 37%
фильтр внутри просмотра, nprobe=16: в среднем 10.00 результата, recall@10 = 0.442
фильтр внутри просмотра, nprobe=64: в среднем 10.00 результата, recall@10 = 0.777
точный перебор только отфильтрованных: сравнений на вопрос 1029 - recall 1.000 по определению
центры по старым данным: размер ячейки мин 41, медиана 239, макс 2078
центры по всем данным: новые темы, nprobe=8: recall@10 = 0.762, просмотрено 3.9% базы
центры только по старым: новые темы, nprobe=8: recall@10 = 0.545, просмотрено 6.9% базы

Что видно. Пост-фильтрация вернула в среднем меньше одного результата из десяти, а в 37% случаев — пустую выдачу: в 100 ближайших по смыслу документов нужного отдела просто не оказалось. Фильтр внутри просмотра всегда возвращает 10 результатов, но при nprobe = 16 это лишь 44% настоящих соседей среди отфильтрованных — подходящих векторов в смотренных ячейках мало, и в выдачу попадают далёкие; при nprobe = 64 уже 78%. Точный перебор 1029 отфильтрованных векторов здесь и дешевле, и точнее: при узком фильтре индекс не нужен. Во втором опыте центры, обученные на старых темах, дали ячейки от 41 до 2078 векторов; на вопросах из новых тем recall упал с 0,76 до 0,55, хотя просмотрено почти вдвое больше базы (6,9% против 3,9%).

Где обычно ошибаются.

  • Делают пост-фильтрацию при узком фильтре и не следят за числом результатов. Пустая или короткая выдача в RAG выглядит как «в базе ничего нет», хотя нужные документы есть.
  • Годами не перестраивают индекс, в который постоянно добавляют новые темы или удаляют записи. Recall медленно падает, а мерить его на свежих вопросах никто не догадывается.
  • Строят индекс по скалярному произведению на ненормированных векторах, хотя модель рассчитана на косинус. Проверьте, нормирует ли векторы сама модель или это надо сделать вручную.

Словарь ступени.

Метаданные (metadata). Сведения о документе помимо вектора: отдел, дата, язык, права доступа.

Пост-фильтрация (post-filtering). Сначала найти ближайших по смыслу, потом выбросить неподходящих по фильтру.

Пре-фильтрация (pre-filtering). Сначала отобрать подходящих по фильтру, потом искать соседей только среди них.

Фильтр внутри обхода. Поиск по индексу, который пропускает неподходящие векторы и продолжает, пока не наберёт k.

Сдвиг данных (data drift). Изменение распределения новых данных по сравнению с теми, на которых строили индекс.

Мягкое удаление (soft delete). Пометка записи удалённой без физического удаления её из структуры индекса.

Мера близости (metric). Правило сравнения векторов: скалярное произведение, косинус или евклидово расстояние.

Перестройка индекса (reindex). Построение индекса заново по текущим данным, чтобы вернуть ему качество.

Словарь целиком — /slovar, новости — /novosti. Все дорожки — /put.