П’ять способів індексування векторів для RAG, протестовано на мільйоні ембеддингів Вікіпедії

Система RAG існує чи зникає залежно від здатності до пошуку, а цей процес ускладнюється зі зростанням корпусу даних. У цьому огляді порівнюються п’ять способів індексування векторів за допомогою реального експерименту, тож вибір методу ґрунтується на цифрах, а не на звичці.

Що таке індексування векторів та чому воно важливе

Індексування векторів — це спосіб організації великої кількості векторів так, щоб схожі з ними можна було швидко знайти, не порівнюючи запит із кожним окремим вектором. У реляційних базах даних існують аналогічні методи — бакетування та Z-впорядкування, які зменшують обсяг даних, що скануються під час пошуку. Бази даних векторів використовують спеціалізовані структури для скорочення простору пошуку в тому ж дусі.

Точне отримання даних із низькою затримкою є основою будь-якої масштабованої системи RAG. Великі компанії вже залежать від цього: Amazon отримує дані з каталогів, що містять мільйони товарів, Netflix — з тисяч фільмів, адаптованих під глобальну аудиторію, а X — з мільярдів повідомлень та облікових записів. Обсяг даних зараз становить терабайти на день, тому масштабування не може бути питанням, яке вирішують пізніше. Воно має бути частиною архітектури з самого початку її проектування.

Кожен з наведених нижче методів оцінюється за трьома критеріями:

• Затримка: швидкість, з якою індекс повертає топ-K результатів.
• Точність отримання даних: ступінь відповідності результатів результатам точного пошуку.

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

Налаштування тесту

У експерименті використовували перші мільйон рядків набору даних CohereLabs/wikipedia-2023-11-embed-multilingual-v3 — обсяг, достатній для демонстрації відмінностей між методами. Запити інкорпорували за допомогою mxbai-embed-large, який генерує 1 024-вимірні вектори, що відповідають векторам з цього набору даних. Індекси створювали в PostgreSQL за допомогою pgvector.

Метод 1: прямий пошук

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

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

Середня затримка під час тестування становила 6,25 секунди. Великий ритейлер та невелика стартап-компанія негайно відхилили б такий варіант.

Метод 2: IVFFlat

Inverted File Flat — це техніка найближчого сусіда з наближеним підходом. Вона використовує алгоритм K-Means для розділення векторного простору на кластери. Замість того, щоб сканувати все, вона знаходить центри, які знаходяться найближче до запиту, та шукає лише всередині цих кластерів, використовуючи точні розрахунки відстаней у їх межах.

Алгоритм роботи виглядає так:

Query → closest centroids → search selected clusters → Top-K

У pgvector це контролюється двома параметрами. Кількість кластерів, які називаються списками, вибирається заздалегідь, і у тесті використовувалося 1 000 списків. Під час запиту другий параметр — проби — визначає, скільки з цих списків буде оброблено. Якщо кількість проб встановлена на 10, то скануються десять списків, центри яких знаходяться найближче до запиту.

Затримка була прийнятною. З мільйоном векторів та 1 000 кластерами запити виконувалися протягом максимум однієї секунди.

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

Підвищення кількості зондів з 10 до 500 призвело до збільшення затримки, хоча в цьому тесті це було лише незначно. Однак немає способу заздалегідь дізнатися, чи 10, 100, 500 чи 900 зондів забезпечать найкращий рівень відтворення даних, адже справжні сусідні елементи можуть знаходитися в кластері, який було проігноровано. Використання всіх 1 000 зондів робить цей підхід марним, оскільки це перетворює індекс назад на метод грубої сили.

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

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

Метод 3: HNSW

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

HNSW, скорочення від hierarchical navigable small world, працює так само. Він починає з розріджених, довгодистанційних зв’язків на верхніх рівнях та просувається через все більш щільні зв’язки на нижчих рівнях, поки не досягне найближчих векторів. Якщо ієрархія доріг добре організована, пошук прямує безпосередньо до цілі, а якісна структура забезпечує високу точність результатів.

Затримка знову була прийнятною — не більше однієї секунди для обробки мільйона векторів.

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

    CREATE INDEX wikipedia_embeddings_hnsw_idx
    ON wikipedia_embeddings
    USING hnsw (emb vector_cosine_ops)
    WITH (
        m = 16,
        ef_construction = 64
    );

Це твердження дозволяє створити індекс на основі корпусу. Важливі три параметри:

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

Як граф вибирає свої m зв’язків? Для мільйона векторів кожен з них має 999,999 потенційних сусідів. Механізм створення не вибирає їх випадково. Він оцінює кандидатів за відстанню та за допомогою евристики вибору сусідів, залишаючи невеликий набір — близько 16 — які є корисними для навігації по графу.

Чому це забезпечує кращу точність?

1. Невелика кількість корисних сусідів на кожен вектор утворює «шосе» графа.
2. Саме ці зв’язки обираються для того, щоб граф залишався з’єднаним та зручним для навігації.
3. Під час пошуку алгоритм крок за кроком слідує цим шосе до векторів, які більше нагадують запит.
4. Оскільки граф пропонує ефективні шляхи до релевантної області, існує більша ймовірність знаходження справжніх найближчих сусідів.
5. Таким чином, ретельна структурування та навігація підвищують точність, уникаючи при цьому повного перевірення всіх варіантів.

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

Технічне обслуговування — це та сфера, де HNSW має слабкі сторони. Створення індексу з понад мільйона векторів зайняло дивовижні 37 хвилин. Під час оновлень, якщо початковий набір даних великий та добре відображає загальну їхню структуру, нові дані можна додавати без необхідності повторного створення індексу. Однак у міру зростання кількості нових даних порівняно з початковим набором їхня структура може змінитися, граф стане менш оптимальним, і зрештою з’явиться потреба у повторному створенні індексу. Це трапляється рідше, ніж з IVF, але все ж таки трапляється.

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

Метод 4: BM25 плюс пошук векторів

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

Механізм роботи:

1. Документи розділяються на терміни, а зворотний індекс відносить кожен термін до документів, які його містять.
2. Частота терміна вимірює, наскільки часто він зустрічається в певному документі.
3. Зворотна частота документа вимірює, наскільки рідкісним чи поширеним є термін у всій колекції.
4. Термін, який є частим у одному документі, але рідкісним у цілому, отримує вищий рівень важливості.
5. BM25 поєднує ці фактори з довжиною документа для оцінки його релевантності.
6. Під час пошуку терміни запиту шукаються в зворотному індексі, оцінюються за допомогою відповідних документів, і повертаються ті, що мають найвищі оцінки.

Сама формула не є привабливою, але ідея проста: знайти документи, які найбільш корелюють із словами у пошуку.

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

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

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

Технічне обслуговування. Жодного, оскільки не створюється векторний індекс.

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

Метод 5: DiskANN та граф Vamana

Цей метод є більш абстрактним, як і самі ембеддинги. Процес виконується у вісім кроків:

1. Почніть із великої колекції векторів, які потребують ефективного пошуку.
2. Створіть граф, поєднавши кожен вектор із ретельно обраним набором сусідів. Це і є граф Вамани.
3. Зберігайте граф на диску, а не в пам’яті, щоб можна було обробляти набори даних, значно більші за обсяг RAM.
4. Коли надходить запит, почніть з вхідної точки в графі.
5. Йдіть за зв’язками між векторами, крок за кроком наближаючись до регіонів, близьких до запиту.
6. У міру просування пошуку завантажуйте необхідні вузли з SSD.
7. Після дослідження достатньої частини графа зберіть невеликий набір перспективних кандидатів.
8. Порівняйте ці кандидати більш точно та поверніть K найближчих.

Ключовим моментом є те, що граф навігації зберігається на SSD, а не в RAM, тому обсяг стає меншою проблемою, ніж витрати пам’яті.

Спочатку виконайте фільтрацію метаданих

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

Який метод обрати

• Груба сила: невеликі чи середні набори даних, до приблизно 20 000 документів. Найкраща точність при прийнятній затримці.
• BM25 разом із векторним пошуком: середні набори даних, приблизно від 20 000 до 100 000 документів. Хороший баланс між лексичним та семантичним пошуком.
• HNSW: великі набори даних із мільйонами векторів або більше. Хороша затримка та точність, але з вищою складністю побудови.
• DiskANN та Vamana: коли оперативна пам’ять стає дорогою. SSD дозволяє великі обсяги зберігання, тому обмеженням є саме обсяг пам’яті, а не її розмір.
• IVFFlat: великі набори даних — приблизно від одного до десяти мільйонів векторів — коли дані добре групуються за клустерами. В іншому випадку погіршується точність пошуку.