Как работает HNSW
Вопрос
Расскажите, как устроен индекс HNSW и как вы настраиваете его под требования по скорости и полноте.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Многоуровневый граф: верхние уровни разреженные, нижний содержит всё
Поиск жадно спускается от верхнего уровня к нижнему
M, ef_construction влияют на граф и требуют перестроения
ef_search регулирует полноту и задержку в рантайме
Качество меряют recall@k против точного поиска
Минусы: память, сложное удаление
Что могут спросить следом
- Чем HNSW отличается от IVF?
- Что делать, если индекс не помещается в память?
Разбор
Образцовый ответ: «HNSW это многослойный граф близости. Каждая вершина попадает на верхние уровни с убывающей вероятностью, поэтому сверху мало вершин и длинные переходы, внизу все вершины и короткие связи. Поиск стартует с верхнего уровня, жадно идёт к ближайшей к запросу вершине, спускается ниже и продолжает уже с более широким списком кандидатов. Параметр M задаёт число связей, ef_construction ширину поиска при вставке: оба влияют на качество графа и память и требуют перестроения. ef_search регулирует полноту при запросе, им я и подбираю баланс. Подбираю так: беру выборку запросов, считаю точные top-k перебором, меряю recall@k и задержку при разных ef_search и выбираю минимальный, который даёт целевую полноту. Минусы HNSW: граф в памяти и сложные удаления. Если память не помещается, смотрю на IVF с PQ или на дисковые индексы».
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.