Пяць спосабаў індэксаваць вектары для RAG на мільёне эмбедынгаў Вікіпедыі

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

Што такое індэксавання вектараў і чаму гэта важліва

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

Точна выкарыстоўванне дадзейнаў з мінімальным часам адзыву ёсць адной з аснов кожнай масштабавальнай сістэмы RAG. Вялікія сервісы вялікі час ужэ залежаць ад гэтага: Amazon выкарыстоўвае каталогі з мільйонамі тавароў, Netflix — тыясячы фільмаў, адпрацоўваных пад асобістыя патрабаванні корыстувачаў у всім свеце, а X — мільярды пастаў і абліков. Дадзеіны цяпер надходзяць у кантэйнерах па тэрабайтах ў дзень, таму масштабаванне не можа быць чымсь, што расследжваецца пазней. Яго трэба ўключыць у архітэктуру з самага пачатку ўзгляду.

Кожны з наведзеных ніжэй методаў ацэніваецца па трох памерах:

• Час адзыву: насколькі шыбка індэкс вяртае топ-К рэзультатаў.
• Точнасць выкарыстоўвання дадзейнаў: насколькі рэзультаты падобныя да тых, якія атрымліваюцца пад час точнага пошуку.

Складна адміністрацыя: ступень складнасці падтрымання індэкса у актуальны стан. Факты, на якіх базуецца прыкладна програма 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, незважаючы на дадатковую інжынерную працу. Баланс павільнасці і точнасці ёсць прыемным, якім не можна назваць выдаюшчымся.

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

Інодзе явны ўтвары ёсць правыя. Калі ўвага зосераджваецца на ўсё бол складных падходах, трыдцятыгадовы «ветэран» працюе непазірна. BM25 — гэта алгорытм лексычнага ранжыравання, які оцінюе дакументы за тым, як часта з’являюцца тэрміны запіту, насколькі рэдкіяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя

У момент запіту тэрміны запіту шукаюцца ў зворачанай індэксе, апраноцьваныя па даскладзеныя дакументы, і вяртаюцца тыя, якія маюць найвышыя оцэнкі.

Сама формула не ўжо такая прыемная, але ідэя простая: знайсці дакументы, якія ў большай меры адпавядаюць словам у пошуку.

Калі гэтыя дакументы знайдзены, прастор для пошуку значна зменшыўся. Пошук у вектарнай форме на гэтым маленькім наборэ дакументаў дапамагае знайсці найлепшыя рэзультаты. Гэта ўжо гібрыдны спосаб знаходжэння інформацыі.

Адна прытамніця: першы этап шукае точныя ключавыя словы, таму памылкі у напісанні ад корыстніка можу пашкодзіць рэзультаты. Крок нормалізаціі пад кераваннем ШЫ, які вылечвае памылкі напісання і варыянты да пачатку пошуку, лёгка справляецца з гэтым.

Затрымка. Вектарная частка адаптуюцца за прыткі час, але лексычная частка у гэтым раскладзе працавала прыблізна 12–14 секунд. Кэшаванне можа вырашыць гэтыя проблемы, хоць першы запіт застаецца повольным. Кэшаванне заслуговае на адзін пункт, таму што яно особа паслужыць для BM25: точныя дакументы атрымліваюцца па адпаведнасці з ключовымі словамі. Для іншых методаў індэксавання кэшаванне павінна быць семантычным, што выкалікае патрэбу ў пороге схожасці і можа пашкодзіць точнасць атрымання дакументаў.

Тыражаванне. Яго няма, адколі не ствараецца вектарны індэкс.

У практыцы, для большасці продуктов AI з прыблізна 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: калі RAM стае дорогім. SSD парадыжае вельмі вялікія об’ёмы, таму лімітам являецца сама памяць, а не ўжо ўся ўпорка.
• IVFFlat: вялікія наборы дадзеных, апошнія ад аднаго да дзесяці мільйонаў вектараў, калі распад дадзеных добра кластэруецца. У іншым случае падвыканне падвяршаецца.

Супаўязаная літэратура

• Гібрыдны пошук для RAG: практычнае застосоўванне BM25, вектараў і фюзыі рангу — чаму RAG, які выкарыстоўвае толькі вектары, втрачае точныя ідэнтыфікаторы, як RRF фюзуюць BM25 з эмбедынгамі, дзе гібрыдны пошук паспелвае гірш і чаму фільтры метададзэнаў павінны выконвацца раней за фюзыю.
• Практычныя прыемы: RAG на базе вектараў у Oracle: эмбеддынгі, HNSW/IVF і гібрыдныя падходы — Паследовыя інструкцыі па вікорыстоўванні Практычных прыемаў: RAG на базе вектараў у Oracle: эмбеддынгі, HNSW/IVF і гібрыдныя падходы: контракты, перакананні ў правільнасці і шаблоны коду для команд, якія впрыменяюць гэты падход.