Knihovna FAISS a embedding: základ jazykových modelů (3. část – role indexů)

Obsah

1. Knihovna FAISS a embedding: základ jazykových modelů (3. část – role indexů)

2. Časová složitost vyhledávání při použití výchozího indexu FlatL2

3. Benchmark: zjištění časové složitosti vyhledávání při použití výchozího indexu FlatL2

4. Výsledky prvního benchmarku

5. Vliv rychlosti vyhledávání na počtu prvků (dimenzi) vektorů

6. Výsledky druhého benchmarku

7. Dimenze vektorů vs. jejich počet

8. Benchmarky měřící rychlosti vyhledání nejpodobnějších vektorů v sadě s proměnným počtem vektorů i proměnným počtem dimenzí

9. Výsledky třetího a čtvrtého benchmarku: lineární a logaritmická stupnice

10. Indexy založené na použití sofistikovanějších datových struktur

11. Rozdělení celého prostoru Voroného dekompozicí

12. Konstrukce indexu IVFFlat

13. Benchmark: časy vyhledávání nejpodobnějších vektorů s využitím indexu FlatL2

14. Výsledky pátého benchmarku

15. Benchmark: modifikace počtu buněk při konstrukci indexu FlatL2

16. Výsledky šestého benchmarku

17. Index HNSW (Hierarchical Navigable Small World)

18. Výsledky sedmého benchmarku

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Knihovna FAISS a embedding: základ jazykových modelů (3. část – role indexů)

V předchozích článcích o knihovně FAISS jsme používali dva typy indexů. První z těchto indexů je založen na výpočtu Eukleidovské vzdálenosti vektorů – jeho cílem je nalézt k vektorů, které se nejvíce podobají vstupnímu vzorku. Druhý index je založen na výpočtu skalárního součinu, protože u normalizovaných vektorů platí, že jejich skalární součin odpovídá míře jejich podobnosti. Tyto dva typy indexů ve své základní podobě mají jména IndexFlatL2 a IndexFlatIP. Jejich výhodou je jednoduchá implementace i absolutní přesnost výsledků – skutečně se vždy vrátí k nejpodobnějších vektorů. Nevýhodou je obecně lineární časová složitost, což začne být problematické v případě, že se pracuje s modely, které obsahují jednotky, desítky či dokonce stovky milionů vektorů.

Právě lineární časová složitost (resp. v těchto případech i její „strmost“) vedla k tomu, že do knihovny FAISS byly přidány i další typy indexů. Některé z nich nemusí být zcela přesné, tj. indexy sice vrací požadovaných k vektorů, ovšem nemusí se jednat o nejpodobnější vektory. Pro potřeby jazykových modelů je však určitá nepřesnost akceptovatelná a někdy i vítaná.

Mezi indexy podporované knihovnou FAISS patří například:

2. Časová složitost vyhledávání při použití výchozího indexu FlatL2

Nejprve si ověříme časovou složitost (konkrétně závislost času vyhledání na počtu uložených vektorů) indexu IndexFlatL2. Prvky vektorů budou datového typu float32, což sice znamená relativně velké nároky na operační paměť, ovšem samotné výpočty (na CPU!) jsou poměrně rychlé, protože lze využít instrukční sady SSEx či AVX.

Jednoduchý benchmark, který slouží pro změření časové složitosti vyhledávání, jsme si již ukázali v předchozích článcích o knihovně FAISS. Ovšem aby byly výsledky měření přesnější, musíme celý benchmark nepatrně upravit. V benchmarku se provádí následující operace:

1. Vytvoření matice obsahující zvolený počet vektorů s předem známou dimenzí (počtem prvků).
2. Konstrukce indexu (L2) z této matice.
3. Opakované vyhledání k nejpodobnějších vektorů k náhodně zvolenému vektoru. Čím větší bude počet opakování tohoto kroku, tím přesnější budou výsledky benchmarku.
4. Vykreslení závislosti času vyhledávání (předchozí bod) na celkovém počtu vektorů n.

[project]
name = "faiss-1"
version = "0.1.0"
description = "Default template for PDM package"
authors = [
    {name = "Pavel Tisnovsky", email = "ptisnovs@redhat.com"},
]
dependencies = [
 "faiss-cpu>=1.11.0",
 "matplotlib>=3.10.3",
 "numpy>=2.3.1",
]
requires-python = "==3.12.*"
readme = "README.md"
license = {text = "MIT"}
 
 
[tool.pdm]
distribution = false

3. Benchmark: zjištění časové složitosti vyhledávání při použití výchozího indexu FlatL2

V první verzi benchmarku je dimenze vektorů (počet prvků) specifikován konstantou DIMENSIONS (která se pochopitelně nemění). Počet opakování vyhledání náhodného vektoru je uložen v konstantě REP_COUNT. Čím větší je hodnota této konstanty, tím pomalejší bude benchmark, ovšem tím více se omezí náhodné vlivy.

Úplný zdrojový kód dnešního prvního benchmarku vypadá následovně:

# Knihovna FAISS
#
# - benchmark rychlosti nalezení nejpodobnějších vektorů
# - výpis výsledků v tabulkové formě
# - vizualizace výsledků formou grafu
 
from time import time
import faiss
import numpy as np
 
import matplotlib.pyplot as plt
 
 
def similarity_search(n, k):
    """Nalezeni k nejblizsich vektoru v mnozine n vektoru."""
    # pocet slozek vektoru
    DIMENSIONS=128
 
    t1 = time()
 
    # nahodne vektory
    data = np.random.rand(n, 128).astype('float32')
 
    t2 = time()
 
    # konstrukce indexu pro vyhledavani na zaklade vzdalenosti
    index = faiss.IndexFlatL2(DIMENSIONS)
    index.add(data)
 
    t3 = time()
    REP_COUNT = 20
 
    # opakovane mereni rychlosti nalezeni nejpodobnejsich vektoru
    for _ in range(REP_COUNT):
        # vektor, ke kteremu budeme pocitat vzdalenost
        query_vector = np.random.rand(1, DIMENSIONS).astype("float32")
 
        # pocet nejblizsich bodu
        distances, indices = index.search(query_vector, k)
 
        # test, kolik vektoru se nalezlo
        assert len(distances) == k
        assert len(indices) == k
 
    t4 = time()
 
    return n, t2-t1, t3-t2, (t4-t3)/REP_COUNT
 
 
ns = []
ts_search = []
 
for n in np.linspace(0, 1000000, 11):
    print(n)
    n, t_rand, t_index, t_search = similarity_search(int(n), 1)
    ns.append(n)
    ts_search.append(t_search)
 
 
plt.xlabel("# vectors")
plt.ylabel("Time/sec")
plt.plot(ns, ts_search, "m-", label="similarity search")
 
# přidání legendy
plt.legend(loc="upper left")
 
# povolení zobrazení mřížky
plt.grid(True)
 
plt.savefig("faiss_benchmark_1.png")
 
# zobrazení grafu
plt.show()

4. Výsledky prvního benchmarku

Výsledky benchmarku popsaného v předchozí kapitole vypadají následovně:

Obrázek 1: Výsledky benchmarku při použití standardního indexu FlatL2 pro proměnný počet vektorů

Autor: tisnik, podle licence: Rights Managed

5. Vliv rychlosti vyhledávání na počtu prvků (dimenzi) vektorů

V prvním benchmarku, jehož výsledky jsme si právě ukázali, jsme měnili pouze počet vektorů uložených do indexu a měřili jsme čas vyhledání nejpodobnějších vektorů. Ovšem jaký vliv má na rychlost vyhledávání počet prvků vektorů, tj. jejich dimenze? Pro zjištění podobnosti vektorů se používá klasická metrika L², tj. výpočet Eukleidovské vzdálenosti v n-dimenzionálním prostoru. Tento výpočet je založen na zobecněné Pythagorově větě (sčítají se druhé mocniny rozdílů odpovídajících si prvků, teoreticky se ještě výsledek odmocní, ale to již nehraje podstatnou roli). A pochopitelně s rostoucím počtem dimenzí roste i počet operací.

Benchmark upravíme tak, že počet vektorů bude konstantní, ale bude se měnit jejich dimenze v rozsahu 0 až 4000 (některé embedding modely se hodnotě 4000 skutečně přibližují):

# Knihovna FAISS
#
# - benchmark rychlosti nalezení nejpodobnějších vektorů
# - je použit index FlatL2
# - postupně se zvyšuje počet dimenzí vektorů
# - délka vektorů zůstává konstantní
# - vizualizace výsledků formou grafu
 
from time import time
import faiss
import numpy as np
 
import matplotlib.pyplot as plt
 
 
def similarity_search(dimensions, n, k):
    """Nalezeni k nejblizsich vektoru v mnozine n vektoru."""
    t1 = time()
 
    # nahodne vektory
    data = np.random.rand(n, dimensions).astype('float32')
 
    t2 = time()
 
    # konstrukce indexu pro vyhledavani na zaklade vzdalenosti
    index = faiss.IndexFlatL2(dimensions)
    index.add(data)
 
    t3 = time()
    REP_COUNT = 20
 
    for _ in range(REP_COUNT):
        # vektor, ke kteremu budeme pocitat vzdalenost
        query_vector = np.random.rand(1, dimensions).astype("float32")
 
        # pocet nejblizsich bodu
        distances, indices = index.search(query_vector, k)
 
        # test, kolik vektoru se nalezlo
        assert len(distances) == k
        assert len(indices) == k
 
    t4 = time()
 
    return n, t2-t1, t3-t2, (t4-t3)/REP_COUNT
 
 
ns = []
ts_search = []
 
for dimensions in np.linspace(0, 4000, 11):
    n = 100000
    print(dimensions, n)
    n, t_rand, t_index, t_search = similarity_search(int(dimensions), n, 1)
    ns.append(dimensions)
    ts_search.append(t_search)
 
 
plt.xlabel("# dimensions")
plt.ylabel("Time/sec")
plt.plot(ns, ts_search, "m-", label="similarity search")
 
# přidání legendy
plt.legend(loc="upper left")
 
# povolení zobrazení mřížky
plt.grid(True)
 
plt.savefig("faiss_benchmark_2.png")
 
# zobrazení grafu
plt.show()

6. Výsledky druhého benchmarku

I ze změřených výsledků druhého benchmarku vyplývá (v souladu s teorií), že vyhledání nejpodobnějších vektorů má lineární časovou složitost, tentokrát ovšem s ohledem na počtu prvků vektorů. To by nemělo být příliš překvapivé zjištění, ovšem naznačuje, že se (pravděpodobně) interně neprovádí žádné sofistikované optimalizace:

Obrázek 2: Výsledky benchmarku při použití standardního indexu FlatL2 pro proměnný počet dimenzí

Autor: tisnik, podle licence: Rights Managed

7. Dimenze vektorů vs. jejich počet

Při tréninku embedded modelů je nutné volit vhodný počet dimenzí, který do jisté míry souvisí i s celkovým počtem vektorů (tj. počtem textů/vět, které jsou daným modelem reprezentovány). Dimenze vektorů se většinou pohybuje v rozsahu 256 až 4096 (což už jsou specializované případy); typická hodnota dimenze je 384, 512 nebo 768. A celkový počet vektorů se pohybuje od několika set tisíc (modely pro konkrétní malou oblast) až do stovek milionů (obecné embedded modely).

Paměťové nároky se (pro přímé indexy) počítají jednoduše:
dimenze × počet vektorů × velikost prvku (bit, byte, float16, float32)

To tedy vlastně znamená, že pokud zachováme konstantní hodnotu dimenze × počet vektorů, můžeme zjistit, která z těchto hodnot má větší vliv na rychlost vyhledávání – zda je to dimenze (vyšší dimenze = složitější početní operace, například více výpočtů čtverce rozdílů prvků vektorů a více součtů) nebo počet vektorů (vyšší počet = vyšší počet výpočtů). To si ověříme v benchmarku, který je uveden v navazující kapitole.

8. Benchmarky měřící rychlosti vyhledání nejpodobnějších vektorů v sadě s proměnným počtem vektorů i proměnným počtem dimenzí

Dva benchmarky, které jsou popsány v této kapitole, měří rychlost vyhledání nejpodobnějších vektorů v datové sadě s proměnným počtem vektorů n, která navíc mají proměnný počet dimenzí dimensions. Počet dimenzí roste s mocninou dvojky a počet vektorů je odvozen ze vztahu 65536*64 // dimensions. To tedy znamená, že celkový počet prvků zůstává konstantní: n×dimensions=65536*64=4194304 (to je dostatečně malý počet, aby se nepřesáhla dostupná kapacita operační paměti).

Oba parametry vstupující do benchmarků se vypočítají takto:

for d in range(0, 14):
    dimensions = 2**d
    n = 65536*64 // dimensions

A proč jsou vytvořeny benchmarky dva? Samotné měření zůstává naprosto stejné, ovšem první benchmark vykreslí grafy s využitím lineární stupnice/měřítka a druhý benchmark použije logaritmické měřítko (důvod uvidíme v další kapitole). Jinak se tyto dva benchmarky nijak neliší:

# Knihovna FAISS
#
# - benchmark rychlosti nalezení nejpodobnějších vektorů
# - je použit index FlatL2
# - výpis výsledků v tabulkové formě
# - postupně se zvyšuje počet dimenzí vektorů
# - délka vektorů se zmenšuje s rostoucím počtem dimenzí vektorů
# - vizualizace výsledků formou grafu
 
from time import time
import faiss
import numpy as np
 
import matplotlib.pyplot as plt
 
 
def similarity_search(dimensions, n, k):
    """Nalezeni k nejblizsich vektoru v mnozine n vektoru."""
    t1 = time()
 
    # nahodne vektory
    data = np.random.rand(n, dimensions).astype('float32')
 
    t2 = time()
 
    # konstrukce indexu pro vyhledavani na zaklade vzdalenosti
    index = faiss.IndexFlatL2(dimensions)
    index.add(data)
 
    t3 = time()
    REP_COUNT = 20
 
    for _ in range(REP_COUNT):
        # vektor, ke kteremu budeme pocitat vzdalenost
        query_vector = np.random.rand(1, dimensions).astype("float32")
 
        # pocet nejblizsich bodu
        distances, indices = index.search(query_vector, k)
 
        # test, kolik vektoru se nalezlo
        assert len(distances) == k
        assert len(indices) == k
 
    t4 = time()
 
    return n, t2-t1, t3-t2, (t4-t3)/REP_COUNT
 
 
ns = []
ts_search = []
 
for d in range(0, 14):
    dimensions = 2**d
    n = 65536*64 // dimensions
    print(dimensions, n)
    n, t_rand, t_index, t_search = similarity_search(dimensions, n, 1)
    ns.append(dimensions)
    ts_search.append(t_search)
 
 
plt.xlabel("# dimensions")
plt.ylabel("Time/sec")
plt.plot(ns, ts_search, "m-", label="similarity search")
 
# přidání legendy
plt.legend(loc="upper left")
 
# povolení zobrazení mřížky
plt.grid(True)
 
plt.savefig("faiss_benchmark_3.png")
 
# zobrazení grafu
plt.show()

# Knihovna FAISS
#
# - benchmark rychlosti nalezení nejpodobnějších vektorů
# - je použit index FlatL2
# - výpis výsledků v tabulkové formě
# - postupně se zvyšuje počet dimenzí vektorů
# - délka vektorů se zmenšuje s rostoucím počtem dimenzí vektorů
# - vizualizace výsledků formou grafu (logaritmické měřítko)
 
from time import time
import faiss
import numpy as np
 
import matplotlib.pyplot as plt
 
 
def similarity_search(dimensions, n, k):
    """Nalezeni k nejblizsich vektoru v mnozine n vektoru."""
    t1 = time()
 
    # nahodne vektory
    data = np.random.rand(n, dimensions).astype('float32')
 
    t2 = time()
 
    # konstrukce indexu pro vyhledavani na zaklade vzdalenosti
    index = faiss.IndexFlatL2(dimensions)
    index.add(data)
 
    t3 = time()
    REP_COUNT = 20
 
    for _ in range(REP_COUNT):
        # vektor, ke kteremu budeme pocitat vzdalenost
        query_vector = np.random.rand(1, dimensions).astype("float32")
 
        # pocet nejblizsich bodu
        distances, indices = index.search(query_vector, k)
 
        # test, kolik vektoru se nalezlo
        assert len(distances) == k
        assert len(indices) == k
 
    t4 = time()
 
    return n, t2-t1, t3-t2, (t4-t3)/REP_COUNT
 
 
ns = []
ts_search = []
 
for d in range(0, 14):
    dimensions = 2**d
    n = 65536*64 // dimensions
    print(dimensions, n)
    n, t_rand, t_index, t_search = similarity_search(dimensions, n, 1)
    ns.append(dimensions)
    ts_search.append(t_search)
 
 
plt.xlabel("# dimensions")
plt.ylabel("Time/sec")
plt.semilogy(ns, ts_search, "m-", label="similarity search")
 
# přidání legendy
plt.legend(loc="upper left")
 
# povolení zobrazení mřížky
plt.grid(True)
 
plt.savefig("faiss_benchmark_4.png")
 
# zobrazení grafu
plt.show()

9. Výsledky třetího a čtvrtého benchmarku: lineární a logaritmická stupnice

Z výsledků třetího benchmarku by se mohlo zdát, že pokud budeme ignorovat situaci s nejmenší dimenzí vektorů (a tím pádem s jejich největším počtem), bude čas pro nalezení k nejpodobnějších vektorů konstantní – neboli že pokud je celkový počet prvků konstantní, bude stejný i čas hledání:

Obrázek 3: Výsledky benchmarku – proměnný počet vektorů i počet dimenzí (lineární stupnice)

Autor: tisnik, podle licence: Rights Managed

Ve skutečnosti je však situace odlišná od předchozího popisu, protože s rostoucím počtem dimenzí (a proporcionálně se snižujícím počtem vektorů) čas vyhledání nejpodobnějších vektorů roste. To odhalíme použitím logaritmického měřítka na vertikální ose, což bylo realizováno ve čtvrtém benchmarku. Jeho výsledky vypadají následovně:

Obrázek 4: Výsledky benchmarku – proměnný počet vektorů i počet dimenzí (logaritmická stupnice)

Autor: tisnik, podle licence: Rights Managed

10. Indexy založené na použití sofistikovanějších datových struktur

Z předchozích benchmarků je patrné, že čas vyhledání nejpodobnějších vektorů lineárně roste s jejich rostoucím počtem. Ovšem v jazykových modelech se setkáme s datovými sadami, které obsahují desítky či dokonce stovky milionů vektorů, takže (pochopitelně) existuje snaha o snížení času vyhledávání – ideálně změnou časové složitosti (z lineární složitosti k například logaritmické složitosti nebo složitosti s odmocninou), nebo alespoň sice se zachováním lineární složitosti, ovšem s jejím menším sklonem (což je ona někdy podceňovaná konstanta k ve vztahu k O(n)). I v těchto oblastech nám knihovna FAISS nabízí různá řešení. V rámci dalších kapitol se seznámíme se dvěma různými technikami, které jsou založeny na použití sofistikovanějších datových struktur, než jsou pouhé sekvence (tabulky) vektorů.

11. Rozdělení celého prostoru Voroného dekompozicí

Jeden z dostupných a relativně často používaných algoritmů určených pro urychlení vyhledávání podobných vektorů spočívá v tom, že se n-dimenzionální prostor, ve kterém vektory vstupní datové sady leží, rozdělí do zadaného počtu oblastí. Pro rozdělení se přitom typicky používá Voroného dekompozice, i když by teoreticky bylo možné použít i další metody (možná zobecněný oktalový strom?). Algoritmus vyhledávání je v tom nejjednodušším případě upraven následujícím způsobem:

1. Vstupem je vektor (dotaz) k němuž v datové sadě hledáme nejbližší vektory
2. Pro tento vstupní vektor je zjištěna oblast (Voroného dekompozice), ve které bude prováděno vyhledávání
3. Následně jsou nejbližší vektory vyhledávány pouze v této oblasti

Problém spočívá v tom, že právě popsaný algoritmus nemusí vyhledat skutečně nejbližší vektory. To nastane v případě, že se vstupní vektor nachází blízko hranice oblasti a nejbližší vektor(y) by se tedy nacházel za touto hranicí. Proto může být algoritmus vyhledávání upraven do nepatrně odlišné podoby:

1. Vstupem je vektor (dotaz) k němuž v datové sadě hledáme nejbližší vektory
2. Pro tento vstupní vektor je zjištěna oblast (Voroného dekompozice), ve které bude prováděno vyhledávání
3. Dále jsou zjištěno m sousedních oblastí k nalezené oblasti (m je konfigurovatelné)
4. Následně jsou nejbližší vektory vyhledávány v nalezené oblasti (bod 2) i oblastech sousedních (bod 3)

Čím větší je hodnota m, tím pomalejší, ale přesnější je vyhledání nejbližších vektorů.

12. Konstrukce indexu IVFFlat

Rozdělení n-dimenzionálního prostoru podle Voroného dekompozice je pochopitelně nutné nějakým způsobem realizovat. Podporu pro toto rozdělení programátorům sice nabízí samotná knihovna FAISS, ovšem samotná konstrukce indexu se nepatrně zkomplikuje. Připomeňme si, že původně jsme si nechali zkonstruovat index následujícím postupem:

# konstrukce indexu pro vyhledavani na zaklade vzdalenosti
index = faiss.IndexFlatL2(dimensions)

Ihned poté bylo možné do indexu všechny vektory vložit:

index.add(data)

Při aplikaci Voroného dekompozice se nejprve samostatným příkazem index představující realizaci této dekompozice vytvoří a teprve poté se zkonstruuje index typu IVFFlat. Parametrem nlist je možné určit způsob rozdělení celého n-dimenzionálního prostoru do nepřekrývajících se oblastí:

# konstrukce indexu pro vyhledavani na zaklade vzdalenosti
quantizer = faiss.IndexFlatL2(DIMENSIONS)
index = faiss.IndexIVFFlat(quantizer, DIMENSIONS, nlist)

Rozdílný je nyní způsob přidávání vektorů do indexu, protože index je nutné nejprve „natrénovat“ a teprve poté je do něj možné vektory přidat. Je to ostatně pochopitelné, protože samotná Voroného dekompozice závisí na koncových souřadnicích vektorů. Při tréninku tedy „pouze“ dojde k dekompozici a při vkládání vektorů k rozdělení vektorů do jednotlivých oblastí:

index.train(data)
index.add(data)

13. Benchmark: časy vyhledávání nejpodobnějších vektorů s využitím indexu FlatL2

V dalším demonstračním příkladu, který si dnes ukážeme, budeme měřit čas vyhledání nejpodobnějších vektorů s využitím indexu nazvaného FlatL2, při jehož konstrukci byly vektory rozděleny do předem nastaveného počtu oblastí. Celý benchmark se tedy (z pohledu programátora) liší pouze tím, jakým způsobem se index zkonstruován. Samotné vyhledávání nejpodobnější vektorů je stále stejné (minimálně z pohledu toho, jaké funkce se volají). Měření budeme opět provádět pro datovou sadu s počtem vektorů, který se mění od nuly (resp. od hodnoty odpovídající počtu oblastí, což je „skoro nula“) do jednoho milionu:

# Knihovna FAISS
#
# - benchmark rychlosti nalezení nejpodobnějších vektorů
# - je použit index FlatL2
# - výpis výsledků v tabulkové formě
# - vizualizace výsledků formou grafu
 
from time import time
import faiss
import numpy as np
 
import matplotlib.pyplot as plt
 
 
def similarity_search(n, k, nlist=5):
    """Nalezeni k nejblizsich vektoru v mnozine n vektoru."""
    # pocet slozek vektoru
    DIMENSIONS=128
 
    t1 = time()
 
    # nahodne vektory
    data = np.random.rand(n, 128).astype('float32')
 
    t2 = time()
 
    # konstrukce indexu pro vyhledavani na zaklade vzdalenosti
    quantizer = faiss.IndexFlatL2(DIMENSIONS)
    index = faiss.IndexIVFFlat(quantizer, DIMENSIONS, nlist)
 
    index.train(data)
    index.add(data)
 
    t3 = time()
    REP_COUNT = 100
 
    for _ in range(REP_COUNT):
        # vektor, ke kteremu budeme pocitat vzdalenost
        query_vector = np.random.rand(1, DIMENSIONS).astype("float32")
 
        # pocet nejblizsich bodu
        distances, indices = index.search(query_vector, k)
 
        # test, kolik vektoru se nalezlo
        assert len(distances) == k
        assert len(indices) == k
 
    t4 = time()
 
    return n, t2-t1, t3-t2, (t4-t3)/REP_COUNT
 
 
ns = []
ts_search = []
 
for n in np.linspace(0, 1000000, 11):
    # nlist nemuze byt nulovy a soucasne musi byt mensi nez
    # pocet vektoru
    if n == 0:
        n = 5
    print(n)
    n, t_rand, t_index, t_search = similarity_search(int(n), 1)
    ns.append(n)
    ts_search.append(t_search)
 
 
plt.xlabel("# vectors")
plt.ylabel("Time/sec")
plt.plot(ns, ts_search, "m-", label="similarity search")
 
# přidání legendy
plt.legend(loc="upper left")
 
# povolení zobrazení mřížky
plt.grid(True)
 
plt.savefig("faiss_benchmark_5.png")
 
# zobrazení grafu
plt.show()

14. Výsledky pátého benchmarku

Z výsledků pátého benchmarku je patrné, že se rychlost vyhledávání skutečně zvýšila. Konkrétně pro datovou sadu s jedním milionem vektorů se čas vyhledání snížil z 0,03 sekundy na 0,009 sekundy. Navíc si musíme uvědomit, že počet oblastí, do kterých byly vektory rozděleny, byl na nastaven na velmi malou hodnotu, konkrétně pouze na pět oblastí, takže bychom měli očekávat maximálně pětinásobné urychlení. A dále je z průběhu grafu patrné, že vyhledání má stále lineární časovou složitost (ovšem s mnohem menším sklonem):

Obrázek 5: Výsledky benchmarku při rozdělení prostoru Voroného dekompozicí na pět oblastí

Autor: tisnik, podle licence: Rights Managed

15. Benchmark: modifikace počtu buněk při konstrukci indexu FlatL2

V předchozím benchmarku byl počet oblastí (buněk) nastaven na velmi nízkou hodnotu, konkrétně na hodnotu 5. Ovšem nic nám pochopitelně nebrání ve zvýšení této hodnoty, například na padesát oblastí; musíme ale počítat s tím, že se sníží přesnost vyhledání. Zvyšuje se totiž pravděpodobnost, že se vzorový vektor bude nacházet blízko okraje nějaké oblasti a nikoli poblíž jejího středu. Nicméně bude zajímavé zjistit, jak bude vyhledání rychlé v případě, že počet oblastí zvýšíme z hodnoty 5 (což je v praxi velmi malá hodnota) na 50:

# Knihovna FAISS
#
# - benchmark rychlosti nalezení nejpodobnějších vektorů
# - je použit index IVFlat
# - výpis výsledků v tabulkové formě
# - vizualizace výsledků formou grafu
 
from time import time
import faiss
import numpy as np
 
import matplotlib.pyplot as plt
 
 
def similarity_search(n, k, nlist=50):
    """Nalezeni k nejblizsich vektoru v mnozine n vektoru."""
    # pocet slozek vektoru
    DIMENSIONS=128
 
    t1 = time()
 
    # nahodne vektory
    data = np.random.rand(n, 128).astype('float32')
 
    t2 = time()
 
    # konstrukce indexu pro vyhledavani na zaklade vzdalenosti
    quantizer = faiss.IndexFlatL2(DIMENSIONS)
    index = faiss.IndexIVFFlat(quantizer, DIMENSIONS, nlist)
 
    index.train(data)
    index.add(data)
 
    t3 = time()
    REP_COUNT = 100
 
    for _ in range(REP_COUNT):
        # vektor, ke kteremu budeme pocitat vzdalenost
        query_vector = np.random.rand(1, DIMENSIONS).astype("float32")
 
        # pocet nejblizsich bodu
        distances, indices = index.search(query_vector, k)
 
        # test, kolik vektoru se nalezlo
        assert len(distances) == k
        assert len(indices) == k
 
    t4 = time()
 
    return n, t2-t1, t3-t2, (t4-t3)/REP_COUNT
 
 
ns = []
ts_search = []
 
for n in np.linspace(0, 1000000, 11):
    # nlist nemuze byt nulovy a soucasne musi byt mensi nez
    # pocet vektoru
    if n == 0:
        n = 50
    print(n)
    n, t_rand, t_index, t_search = similarity_search(int(n), 1)
    ns.append(n)
    ts_search.append(t_search)
 
 
plt.xlabel("# vectors")
plt.ylabel("Time/sec")
plt.plot(ns, ts_search, "m-", label="similarity search")
 
# přidání legendy
plt.legend(loc="upper left")
 
# povolení zobrazení mřížky
plt.grid(True)
 
plt.savefig("faiss_benchmark_6.png")
 
# zobrazení grafu
plt.show()

16. Výsledky šestého benchmarku

Opět se podívejme na výsledky benchmarku, jehož zdrojový kód byl uveden v předchozí kapitole:

Obrázek 6: Výsledky benchmarku při rozdělení prostoru Voroného dekompozicí na padesát oblastí

Autor: tisnik, podle licence: Rights Managed

Zajímavé bude porovnání hodnot získaných ze všech tří základních benchmarků, tedy benchmarku se základním indexem L2 (bez dalších optimalizací), benchmarku s rozdělením prostoru do pěti oblastí podle Voroného dekompozice a benchmarku s rozdělením prostoru na základě téže dekompozice, ovšem nyní do padesáti oblastí:

17. Index HNSW (Hierarchical Navigable Small World)

Jedním z potenciálně velmi užitečných indexů, které jsou nabízeny (nejenom) knihovnou FAISS, je index označovaný zkratkou HNSW neboli Hierarchical Navigable Small World. Jak již název tohoto indexu naznačuje, je metoda HNSW založena na rozdělení celého prostoru do hierarchicky organizovaných menších částí (ty jsou nazývány „malé světy“). Samotné rozdělování prostoru je časově velmi náročné, ovšem na druhou stranu se urychlí vyhledávání podobných vektorů, a to o jeden až dva řády. Samozřejmě se i s tímto indexem pojí určité nevýhody, ovšem prozatím nám bude postačovat vytvoření benchmarku, z něhož je patrné, jakým způsobem se tento index používá:

# Knihovna FAISS
#
# - benchmark rychlosti nalezení nejpodobnějších vektorů
# - je použit index HNSWFlat
# - výpis výsledků v tabulkové formě
# - vizualizace výsledků formou grafu
 
from time import time
import faiss
import numpy as np
 
import matplotlib.pyplot as plt
 
 
def similarity_search(n, k):
    """Nalezeni k nejblizsich vektoru v mnozine n vektoru."""
    M = 32
    ef_search = 16
    ef_construction = 32
    # pocet slozek vektoru
    DIMENSIONS=128
 
    t1 = time()
 
    # nahodne vektory
    data = np.random.rand(n, 128).astype('float32')
 
    t2 = time()
 
    # konstrukce indexu pro vyhledavani na zaklade vzdalenosti
    index = faiss.IndexHNSWFlat(DIMENSIONS, M)
    index.hnsw.efConstruction = ef_construction
    index.hnsw.efSearch = ef_search
 
    index.add(data)
 
    t3 = time()
    REP_COUNT = 100
 
    for _ in range(REP_COUNT):
        # vektor, ke kteremu budeme pocitat vzdalenost
        query_vector = np.random.rand(1, DIMENSIONS).astype("float32")
 
        # pocet nejblizsich bodu
        distances, indices = index.search(query_vector, k)
 
        # test, kolik vektoru se nalezlo
        assert len(distances) == k
        assert len(indices) == k
 
    t4 = time()
 
    return n, t2-t1, t3-t2, (t4-t3)/REP_COUNT
 
 
ns = []
ts_search = []
 
for n in np.linspace(0, 1000000, 11):
    print(n)
    n, t_rand, t_index, t_search = similarity_search(int(n), 1)
    ns.append(n)
    ts_search.append(t_search)
 
 
plt.xlabel("# vectors")
plt.ylabel("Time/sec")
plt.plot(ns, ts_search, "m-", label="similarity search")
 
# přidání legendy
plt.legend(loc="upper left")
 
# povolení zobrazení mřížky
plt.grid(True)
 
plt.savefig("faiss_benchmark_7.png")
 
# zobrazení grafu
plt.show()

18. Výsledky sedmého benchmarku

Výsledky sedmého a dnes již posledního benchmarku jsou zobrazeny na obrázku pod tímto odstavcem. Zajímavé je, že v tomto případě došlo k velmi radikálnímu urychlení vyhledávání podobných vektorů. Konkrétně se (pro jeden milion vektorů) čas vyhledání snížil z přibližně 0,03 sekundy na pouhých 0,0007 sekundy, takže rychlost vyhledávání je zhruba 43× vyšší. Co však nevidíme je čas nutný pro konstrukci indexu – ten je naopak velmi dlouhý. O problematice konstrukce indexu (což nás prozatím příliš netrápilo, ovšem u podobných komplikovanějších indexů je to již reálný problém) se zmíníme v závěrečném článku o knihovně FAISS.

Obrázek 7: Výsledky benchmarku založeného na využití indexu HNSW

Autor: tisnik, podle licence: Rights Managed

19. Repositář s demonstračními příklady

Demonstrační příklady použité v článcích Knihovna FAISS a embedding: základ jazykových modelů a Knihovna FAISS a embedding: základ jazykových modelů (2. část) lze nalézt na následujících odkazech:

Demonstrační příklady vytvořené v Pythonu a popsané v článcích ,i v článku dnešním jsou taktéž uloženy do repositáře https://github.com/tisnik/most-popular-python-libs/. Následují odkazy na jednotlivé příklady:

20. Odkazy na Internetu

1. FAISS: knihovna pro rychlé a efektivní vyhledávání podobných vektorů
   https://www.root.cz/clanky/faiss-knihovna-pro-rychle-a-efektivni-vyhledavani-podobnych-vektoru/
2. FAISS: knihovna pro rychlé a efektivní vyhledávání podobných vektorů (2. část)
   https://www.root.cz/clanky/faiss-knihovna-pro-rychle-a-efektivni-vyhledavani-podobnych-vektoru-2-cast/
3. Knihovna FAISS a embedding: základ jazykových modelů
   https://www.root.cz/clanky/knihovna-faiss-a-embedding-zaklad-jazykovych-modelu/
4. Knihovna FAISS a embedding: základ jazykových modelů (2. část)
   https://www.root.cz/clanky/knihovna-faiss-a-embedding-zaklad-jazykovych-modelu-2-cast/
5. FAISS (Facebook AI Similarity Search)
   https://en.wikipedia.org/wiki/FAISS
6. FAISS documentation
   https://faiss.ai/
7. Introduction to Facebook AI Similarity Search (Faiss)
   https://www.pinecone.io/le­arn/series/faiss/faiss-tutorial/
8. Faiss: Efficient Similarity Search and Clustering of Dense Vectors
   https://medium.com/@pankaj_pan­dey/faiss-efficient-similarity-search-and-clustering-of-dense-vectors-dace1df1e235
9. Cosine Distance vs Dot Product vs Euclidean in vector similarity search
   https://medium.com/data-science-collective/cosine-distance-vs-dot-product-vs-euclidean-in-vector-similarity-search-227a6db32edb
10. F16C
    https://en.wikipedia.org/wiki/F16C
11. FP16 (AVX-512)
    https://en.wikipedia.org/wiki/AVX-512#FP16
12. Top 8 Vector Databases in 2025: Features, Use Cases, and Comparisons
    https://synapsefabric.com/top-8-vector-databases-in-2025-features-use-cases-and-comparisons/
13. Is FAISS a Vector Database? Complete Guide
    https://mljourney.com/is-faiss-a-vector-database-complete-guide/
14. Vector database
    https://en.wikipedia.org/wi­ki/Vector_database
15. Similarity search
    https://en.wikipedia.org/wi­ki/Similarity_search
16. Nearest neighbor search
    https://en.wikipedia.org/wi­ki/Nearest_neighbor_search#Ap­proximation_methods
17. Decoding Similarity Search with FAISS: A Practical Approach
    https://www.luminis.eu/blog/decoding-similarity-search-with-faiss-a-practical-approach/
18. MetricType and distances
    https://github.com/facebo­okresearch/faiss/wiki/Metric­Type-and-distances
19. RAG – Retrieval-augmented generation
    https://en.wikipedia.org/wi­ki/Retrieval-augmented_generation
20. pgvector na GitHubu
    https://github.com/pgvector/pgvector
21. Why we replaced Pinecone with PGVector
    https://www.confident-ai.com/blog/why-we-replaced-pinecone-with-pgvector
22. PostgreSQL as VectorDB – Beginner Tutorial
    https://www.youtube.com/wat­ch?v=Ff3tJ4pJEa4
23. What is a Vector Database? (neobsahuje odpověď na otázku v titulku :-)
    https://www.youtube.com/wat­ch?v=t9IDoenf-lo
24. PGVector: Turn PostgreSQL Into A Vector Database
    https://www.youtube.com/wat­ch?v=j1QcPSLj7u0
25. Milvus
    https://milvus.io/
26. Vector Databases simply explained! (Embeddings & Indexes)
    https://www.youtube.com/wat­ch?v=dN0lsF2cvm4
27. Vector databases are so hot right now. WTF are they?
    https://www.youtube.com/wat­ch?v=klTvEwg3oJ4
28. Step-by-Step Guide to Installing “pgvector” and Loading Data in PostgreSQL
    https://medium.com/@besttechreads/step-by-step-guide-to-installing-pgvector-and-loading-data-in-postgresql-f2cffb5dec43
29. Best 17 Vector Databases for 2025
    https://lakefs.io/blog/12-vector-databases-2023/
30. Top 15 Vector Databases that You Must Try in 2025
    https://www.geeksforgeeks.org/top-vector-databases/
31. Picking a vector database: a comparison and guide for 2023
    https://benchmark.vectorvi­ew.ai/vectordbs.html
32. Top 9 Vector Databases as of Feburary 2025
    https://www.shakudo.io/blog/top-9-vector-databases
33. What is a vector database?
    https://www.ibm.com/think/to­pics/vector-database
34. SQL injection
    https://en.wikipedia.org/wi­ki/SQL_injection
35. Cosine similarity
    https://en.wikipedia.org/wi­ki/Cosine_similarity
36. Euclidean distance
    https://en.wikipedia.org/wi­ki/Euclidean_distance
37. Dot product
    https://en.wikipedia.org/wi­ki/Dot_product
38. Hammingova vzdálenost
    https://cs.wikipedia.org/wi­ki/Hammingova_vzd%C3%A1le­nost
39. Jaccard index
    https://en.wikipedia.org/wi­ki/Jaccard_index
40. Manhattanská metrika
    https://cs.wikipedia.org/wi­ki/Manhattansk%C3%A1_metri­ka
41. pgvector: vektorová databáze postavená na Postgresu
    https://www.root.cz/clanky/pgvector-vektorova-databaze-postavena-na-postgresu/
42. Matplotlib Home Page
    http://matplotlib.org/
43. matplotlib (Wikipedia)
    https://en.wikipedia.org/wi­ki/Matplotlib
44. Dot Product
    https://mathworld.wolfram­.com/DotProduct.html
45. FAISS and sentence-transformers in 5 Minutes
    https://www.stephendiehl.com/pos­ts/faiss/
46. Sentence Transformer: Quickstart
    https://sbert.net/docs/qu­ickstart.html#sentence-transformer
47. Sentence Transformers: Embeddings, Retrieval, and Reranking
    https://pypi.org/project/sentence-transformers/
48. uv
    https://docs.astral.sh/uv/
49. A Gentle Introduction to Retrieval Augmented Generation (RAG)
    https://wandb.ai/cosmo3769/RAG/re­ports/A-Gentle-Introduction-to-Retrieval-Augmented-Generation-RAG---Vmlldzo1MjM4Mjk1
50. The Beginner’s Guide to Text Embeddings
    https://www.deepset.ai/blog/the-beginners-guide-to-text-embeddings
51. What are Word Embeddings?
    https://www.youtube.com/wat­ch?v=wgfSDrqYMJ4
52. How to choose an embedding model
    https://www.youtube.com/wat­ch?v=djp4205tHGU
53. What is a Vector Database? Powering Semantic Search & AI Applications
    https://www.youtube.com/wat­ch?v=gl1r1XV0SLw
54. How do Sentence Transformers differ from traditional word embedding models like Word2Vec or GloVe?
    https://zilliz.com/ai-faq/how-do-sentence-transformers-differ-from-traditional-word-embedding-models-like-word2vec-or-glove
55. BERT (language model)
    https://en.wikipedia.org/wi­ki/BERT_(language_model)
56. Levenštejnova vzdálenost
    https://cs.wikipedia.org/wi­ki/Leven%C5%A1tejnova_vzd%C3%A1le­nost
57. IVFFlat (Inverted File Flat) Index
    https://skyzh.github.io/write-you-a-vector-db/cpp-05-ivfflat.html
58. HNSW (Hierarchical Navigable Small Worlds) Index
    https://skyzh.github.io/write-you-a-vector-db/cpp-06–02-hnsw.html
59. Vector Indexing: Your Guide to Understanding and Implementation
    https://www.teradata.com/insights/ai-and-machine-learning/what-is-vector-index
60. Vector Indexing Explained: Everything You Need to Know
    https://www.datastax.com/guides/what-is-a-vector-index
61. Voroného diagram
    https://cs.wikipedia.org/wi­ki/Voron%C3%A9ho_diagram