Унутры вектарных баз: IVF, дрэвы, HNSW і прадуктовая квантызацыя

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

Дзе беруцца вектары

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

Словнік

У кожной базе вектарных даных павтараецца калькі тэрмінаў:

• Калекцыя. Простор імен, які маюць спакульную высоту і аднаковы метрык адстані.
• Точка. Вектар разам з яго ID і наборам метадаў.
• Метрык адстані. Спосаб вычыслення блізкасці, зазвычай косінусавая схожасць, скалярны добутак або евклідава адстань.
• Upsert. Операцыя, якая дадзеўляе даныя, дагружаючы новыя точкі і апдэйтуючы існуючыя.
• Пошук. Операцыя запыту, для якой існуе ўсё іншае.

Інтуіцыя: тачны проты прыбліжны

Просты спосаб знаходжэння вектараў, якія адносяцца да запіту сярод 10 000 або больш вектараў, — гэта вычысленне косай схожасці з кожным зберагнутым вектарам і заставаўка тых k вектараў, якія маюць найбольшую схожасць. Рэзультатам яе ёсць набор тых вектараў, якія знаходзяцца на самай маладзейшай адстані. Аднак калі мова йдэ пра мільйоны вектараў, такі метод прымітнага перагляду стае непрактычным з-за прытоку памяці і часу. Таму сістэмы перайшлі на пошук апрыксіваўных найбліжэйшых суседаў (ANN), які праграмае некалькі падышэнняў у тачнасці зарады значных перадоў у швальнасці.

Этота замена можа выконвацца двума основнымі спосабамі. Індэксаванне зменшае колькісць паўтарных порэванаў. Квантызацыя зменшае косць кожнага порэванаў. Разам яны складаюць інструментарыя для пошуку апрыксіваўных найбліжэйшых суседаў.

Індэксаванне, першы варыянт: кластэруванне за дапамогою IVF

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

Варта ведаць прынтэсы такога падходу:

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

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

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

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

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

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

Індэксаванне, другі варыянт: партыцыяванне на аднойчыні

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

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

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

Есць адзін недзея. Праўdziвы найбліжэйшы сусед можа знаходзіцца проста за межай, на малай вялічыні аддалены, але ў іншай гілцы, і адна лінія ніколі яго не пазнае. Таму такі бібліятэкі, як Annoy ад Spotify, ствараюць многа ліній, кожная з якіх мае разныя адбытковыя роздзелы. Кожная лінія прыносіць кандыдатаў, прыказы злучаюцца, а выбіраюцца найлепшыя. Тое, што адна лінія працягвае, іншая зазвычай з’яўляе.

Недзея:

• Проблема межы ўскладненая больш, чым у IVF. У IVF прахапленне межы значыць прабаву ўсёроджэння ў ўсё той жа клетку. У лініі неправы рух поблізу верху прымушвае пошук перайсці ў абсалютна іншы раён.
• Рашэнне коштае памяці і швальнасці. Лес з 50 ліній значыць неабходнасць зберагаць індэкс 50 разоў і выканаць пошук 50 разоў за кожны запіт, што дазволяе падняць тачнасць за рахунак рэсурсаў.
• Дзейны вектары яго практычна параджуюць. Дрэвы добра працуюць у 2D, 3D, на картах і у гэмы. Савэчасныя эмбеддынгі маюць сотні або тыясячы вымяраў, дзе розлініюванне практычна нічога значэнневага не разлічвае, адколі точкі на працэсных бокох можу быць майжэ роўнадалёкімі. Гэта главная прычына, чырвоне гэты метод перастаў быць популярным для пошуку эмбеддынгаў.
• Індэкс ўсталяны. Дрэвы ствараюцца аднойчы на аднойчына з існуючых дадзеных і не можу чыста прыняць новыя вектары. Напрыклад, Annoy патрабуе цэлага перзбудавання, каб дадаць новыя даны, што паслужае па-вялікім чыну проты змянюючыхся колекцыяў.
• У большасці случаў ён застаецца атрыбутам мінулага. Пры роўнай точнасці HNSW працуе быстрэй, а пры роўнай памяці IVF з квантывацыяй працуе ефектывней. Дрэвы застаюцца пераважна ў старых сістэмах і там, дзе важны малыя, памяцю-адаптаваныя файлы індэксаў.

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

Індэксаванне, трэці варыянт: HNSW

Hierarchical Navigable Small Worlds, або HNSW, — гэта тэхніка, якая лежыць у основе большасці вектарных баз дадзэнняў. Яна арганізуе вектары у вачэрку з калькамі слоёў. На верхніх слоях знаходзіцца толькі калькі вектараў з далёкімі зв’язкамі, падобнымі да шосе між горадамі, а на ніжніх слоях — працэсава больш вектараў з корачымі зв’язкамі, пакуль на самым ніжнім слоі не будуць размешаны ўсе вектары.

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

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

• M задае, сколькі звязкаў заставіць кожнам вектару. Больш звязкаў павышае тачнасць і можлівасць знаходжэння рэзультатаў, але спрачынае большы выкарыстоўвання памяці.
• efConstruction задае, насколькі шырокі будзе радаус пошуку пад час стварэння графа. Вышэйшыя значэнні даюць лепшы граф, але працэс стварэння ўсё жа ўсё сповольней.

efSearch задае шырыню спісу кандыдатаў пад час адправкі запіту. Яго падвышэнне адразу падвышае точнасць і час адпаведзьбы.

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

Квантызацыя: зменшэнне вартасці кожнага порэвання

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

Продуктовая квантызацыя

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

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

Выбір сярод іх

Короткае паўстанавленне дапамагае зрозумець сітуацыю:

• IVF — гэта просты і ўнізкатрабатны спосаб. Яго можна выкарыстоўваць разам з квантызацыяй вектараў для вельмі большых статычных колекцыяў.
• Дрэвы лёгкія для разумэння і дэшавыя у стварэнні, але падходзяць толькі для маладымыя размерамі і незменных дадзеных.
• HNSW забезпечвае высокую точнасць і шыране пошук у рэальным часе, але для гэтага трэба больша памяць.
• Квантызацыя вектараў стыскае вектары і прышвыдшуе вычысленні расстоянняў, пры чым ўскладнюецца тачнасць, і можа выкарыстоўвалася разам з вышэўказанымі індэксамі.

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