Всередині векторних баз даних: IVF, дерева, HNSW та квантування даних.

Терміни на кшталт RAG, векторних баз даних, процесів пошуку та розділення тексту постійно згадуються, і вони звучать складніше, ніж є насправді. Ця стаття починається з векторних баз даних: що вони зберігають та як насправді відбувається пошук у них.

Де беруться вектори

Моделі ембеддингу, навчені на величезних колекціях тексту, перетворюють значення речення на список чисел. Деякі з них розміщені онлайн, наприклад, моделі ембеддингу тексту від OpenAI та Google Gemini. Інші працюють локально, як-от сімейство моделей ембеддингу Qwen3 у версіях 8B, 4B та 0.6B, або модель Jina v5 text-small з приблизно 677 мільйонами параметрів. Якщо пропустити свій текст через одну з цих моделей, результатом буде вектор, який можна зберегти та відтворити пізніше.

Лексикон

У кожній векторній базі даних постійно зустрічається кілька ключових термінів:

• Колекція. Простір імен, який містить точки, що мають одну фіксовану вимірність та один метрик відстані.
• Точка. Вектор разом із його ідентифікатором та набором метаданих.
• Метрика відстані. Спосіб вимірювання близькості, зазвичай косинусна схожість, скалярний добуток або евклідова відстань.
• Upsert. Операція, яка вводить дані, додаючи нові точки та оновлюючи існуючі.
• Пошук. Операція запиту, для якої існує все інше.

Інтуїція: точне проти приблизного

Наївний спосіб знаходження векторів, пов’язаних із запитом, серед 10 000 або більше векторів — це обчислення косинусової схожості з кожним збереженим вектором та зберігання k найкращих результатів. Результатом є набір точних найближчих сусідів. Однак при мільйонах векторів такий метод прямого пошуку стає непрактичним через обмеження пам’яті та часу. Тому системи перейшли на апроксимований пошук найближчих сусідів (ANN), який йде на невелику втрату точності заради значного прискорення.

Цей компроміс можна досягти двома основними способами. Індексування зменшує кількість необхідних порівнянь. Квантування зменшує витрати на кожне порівняння. Разом вони складають інструментарій ANN.

Індексування, перший варіант: кластерування з IVF

Інвертований індекс файлів (IVF) ділить вектори на кластери, кожен з яких має центроїд. Спочатку запит порівнюється лише з центроїдами. Як тільки знаходиться найближчий кластер, запит порівнюється виключно з векторами цього кластера, і повертаються найкращі k з них.

Варто знати про слабкі сторони:

• Сусідні елементи біля меж клітин залишаються непоміченими. Якщо справжній збіг знаходиться в клітині, яку не було перевірено, його ніколи не знайдуть. Перевірка більшої кількості клітин допомагає, але уповільнює пошук та підриває його ефективність.
• Якість знижується зі зміною даних. Кластери фіксуються під час створення, тому нові дані продовжують потрапляти у старі клітини, що призводить до погіршення якості пошуку. Треба періодично оновлювати індекс.

Нерівномірні кластери роблять швидкість непередбачуваною. Деякі клітини ростуть до величезних розмірів, тоді як інші залишаються мініатюрними, тому запит, який потрапляє у велику клітину, виконується повільно, а той, що потрапляє у маленьку — швидко.

Для цього потрібні дані для навчання заздалегідь. Індекс не може бути створений, поки не буде достатньо даних для формування змістовних кластерів, що ускладнює ситуацію для додатків, які починають з нуля.

Два параметри важко налаштувати. Кількість кластерів та кількість елементів, які шукаються за один запит, обидва впливають на результати, а неправильні значення сповільнюють пошук або роблять його неточним.

Висока кількість вимірів розмиває кластери. При дуже довгих векторах кластери стають нечіткими, тому точність за одиницю роботи поступається HNSW.

У одному реченні: IVF є простим та економить пам’ять, але втрачає точність біля меж та погано справляється з частими оновленнями, тому він чудово підходить у масштабах мільярдів даних у поєднанні з квантизацією продуктів, тоді як HNSW є кращим вибором для реального часу з високою точністю пошуку.

Індексування, другий варіант: розподіл на основі дерев

Індексування на основі дерев запозичує ідею бінарного пошуку. Замість порівняння запиту з кожним вектором простір неодноразово ділиться навпіл, і перевіряється лише та половина, яка містить запит.

Щоб створити індекс, береться весь простір та розділяється він роздільною лінією, потім кожна половина розділяється знову, і так далі, поки кожен маленький регіон не буде містити лише кілька векторів. Кожен регіон є листком. У двовимірному просторі перший розщеплення може відбуватися вздовж осі x, наступне — вздовж осі y тощо. Усі ці розщеплення утворюють бінарне дерево, у якому кожен вузол є запитанням «так» чи «ні», наприклад, чи x менше за 5, а листки знаходяться внизу.

Коли надходить запит, починається робота з кореня та відповідається по одному запитанню за раз: ліворуч від цього розщеплення чи праворуч? Кожна відповідь відкидає половину залишкового простору. Після приблизно log n запитань, близько 20 для мільйона векторів, досягається один маленький листок, і запит порівнюється з невеликою кількістю векторів, що знаходяться в ньому.

Є одна проблема. Справжній найближчий сусід може знаходитися прямо за межею розділення — на невеликій відстані, але в іншій гілці, і окреме дерево ніколи його не побачить. Тому такі бібліотеки, як Annoy від Spotify, створюють багато дерев, кожне з яких має різні випадкові розділення. Кожне дерево пропонує кандидатів, ці пропозиції об’єднуються, і повертаються найкращі. Те, що одне дерево пропускає, зазвичай помічає інше.

Недоліки:

• Проблема межі гірша, ніж у IVF. У IVF пропуск межі означає необхідність перевірки ще однієї клітинки. У дереві неправильний поворот близько вершини відправляє пошук у зовсім інший регіон.
• Вирішення коштує пам’яті та швидкості. Ліс з 50 дерев означає необхідність зберігання індексу 50 разів та проведення пошуку 50 разів на запит, що дозволяє досягти точності за рахунок ресурсів.
• Довгі вектори їх перемагають. Дерева добре працюють у 2D, 3D, на картах та в іграх. Сучасні ембеддинги мають сотні чи тисячі вимірів, де розділююча лінія майже нічого значущого не виділяє, оскільки точки з протилежних боків можуть бути майже на однаковій відстані. Це основна причина, чому цей метод втратив популярність для пошуку за ембеддингами.
• Індекс є статичним. Дерева створюються один раз на основі наявних даних та не можуть ефективно приймати нові вектори. Наприклад, для додавання даних у Annoy потрібна повна перебудова, що погано підходить для змінюваних колекцій.
• Вони зазвичай поступаються. При однаковій точності HNSW працює швидше, а при однаковій кількості пам’яті IVF з квантуванням добутку дозволяє обробляти ще більші обсяги даних. Дерева залишаються переважно у застарілих системах та там, де важливі невеликі індексні файли, які можна зберігати в пам’яті.

Коротко кажучи, дерева є простими та швидкими у створенні, але високорозмірні ембеддинги руйнують їхню структуру розділень та не дозволяють вносити зміни, тому сьогодні вони переважно використовуються як проміжний етап для пояснень, а не як варіант для практичного застосування.

Індексування, третій варіант: HNSW

Ієрархічні навігові малі світи, або HNSW, — це технологія, яка лежить в основі більшості векторних баз даних. Вона організовує вектори у вигляді графа з кількома шарами. Верхні шари містять лише кілька векторів із довгими зв’язками, схожими на автомагістралі між містами, тоді як нижні шари містять все більше векторів із коротшими зв’язками, аж до нижнього шару, який містить усі вектори.

Пошук починається з верхнього рівня та жадібно переходить до сусіда, який знаходиться найближче до запиту. Коли ближчого сусіда немає, він опускається на один рівень нижче та повторює процедуру з того місця, використовуючи більш деталізовані посилання. На нижньому рівні він досліджує більшу область та повертає найкращі результати. Довгі кроки швидко прокроковують великі відстані, а короткі кроки уточнюють відповідь, тому кількість порівнянь залишається невеликою навіть для величезних колекцій.

Кілька параметрів контролюють баланс між швидкістю та точністю:

• M визначає, скільки посилань зберігає кожен вектор. Більше посилань покращує точність та повноту результатів, але збільшує витрати пам’яті.
• efConstruction визначає, наскільки широкою буде область пошуку під час створення графа. Вищі значення забезпечують кращий граф, але уповільнюють процес його створення.

efSearch визначає ширину списку кандидатів під час пошуку. Його підвищення одночасно покращує точність та збільшує затримку.

Якщо подивитися, як запит проходить через різні рівні обробки та як ці налаштування впливають на шлях обробки, можна зрозуміти, як їх зміна впливає на поведінку пошуку.

Квантування: зниження вартості кожного порівняння

Індексування зменшує кількість необхідних порівнянь. Квантування знижує вартість кожного з них. Один 1536-вимірний вектор з 32-бітними числами з плаваючою комою займає 1536 помножені на 4, тобто 6144 байти. Для мільярда векторів це означає терабайти пам’яті, що значно більше, ніж може вміститися в RAM.

Продуктове квантування

Квантування продукту розділяє кожен великий вектор на менші фрагменти однакового розміру. 16-вимірний вектор може стати, скажімо, чотирма фрагментами по чотири виміри кожен. Для кожної позиції фрагмента тренується кодова книга на збережених даних із 256 записами, кожен з яких представляє типовий підвектор. Кожен фрагмент потім замінюється номером найближчого запису з кодової книги, що потребує лише одного байта.

Таким чином вектор, який займав тисячі байтів, перетворюється на короткий рядок малих цілих чисел. Для пошуку запит також розділяється таким самим способом, а відстані до записів кодової книги обчислюються один раз та використовуються під час пошуку кожного збереженого вектора. Ці обчислення є дуже наближеними, але швидкість та економія пам’яті значні.

Вибір серед них

Швидке порівняння підсумовує все:

• IVF є простим та економічним з точки зору використання пам’яті. Його можна поєднувати з квантизацією векторів для дуже великих статичних колекцій.
• Дерева легко зрозумілі та дешеві у створенні, але підходять лише для низьковимірних даних, які не змінюються.
• HNSW забезпечує високу точність та швидке пошук у реальному часі, але вимагає більше пам’яті.
• Квантизація векторів стискає їх та прискорює обчислення відстаней, спричиняючи контрольовану втрату точності, і може поєднуватися з вищезгаданими індексами.

Знання цих компромісів допомагає вам вирішити, коли доцільний приблизний пошук, який алгоритм підходить для певного завдання, та коли brute force все ще є правильним рішенням, наприклад, у випадку невеликих колекцій, де точність не має великого значення.