Meta ve Faiss 1.16.0 přidává E-means pro rychlejší shlukování ve velkém měřítku

Správci knihovny Faiss společnosti Meta vydali verzi 1.16.0 10. listopadu 2026. Ta přináší shlukovací algoritmus e-means od FAIR at Meta v implementacích pro CPU, GPU i distribuované prostředí. Výzkumníci uvádějí, že dosáhli nižší ztráty než Lloydův algoritmus k-means po 1,4 až 2,6 epochy, zatímco Lloydův algoritmus jí dosáhne za 25 epoch. Oproti porovnávaným implementacím se doba běhu na GPU zkrátila 10–45×.

Vydání softwaru následovalo po odeslání výzkumného preprintu na arXiv 6. listopadu 2026; nejde tedy o první veřejné představení algoritmu. Za prací stojí výzkumníci z FAIR at Meta a École Nationale des Ponts et Chaussées.

Verze 1.16.0 přidává referenční implementace e-means, distribuovaný trénink i trénink s rozdělenými centroidy, výpočetní jádra Triton a CuTe pro přiřazování, přiřazování se sníženou přesností a benchmarky umožňující reprodukovat výsledky výzkumu. Obsahuje také ukázky s DINO, které buď ponechávají data v paměti, nebo je načítají průběžně z SSD.

Jak e-means aktualizuje centroidy

Cílem k-means je najít centroidy, které minimalizují průměrnou kvadratickou vzdálenost vektorů od jejich nejbližšího centroidu. Algoritmus se využívá při vyhledávání, kvantizaci a kurátorství dat. Lloydův algoritmus přiřadí každý bod k nejbližšímu centroidu a pro každý shluk znovu vypočítá součet i počet prvků z celého datasetu. E-means místo toho aktualizuje exponenciálně vážené součty a počty na základě mini-dávek, takže starší přiřazení postupně ztrácejí vliv; každý centroid přitom zůstává podílem průběžného součtu vektorů a průběžného počtu. Zpracování celého datasetu v jediné dávce s krokem o velikosti 1 odpovídá jedné iteraci Lloydova algoritmu.

Dva empiricky odvozené škálovací zákony určují velikost dávky a počáteční velikost kroku podle velikosti datasetu, počtu shluků a rozpočtu epoch. Díky tomu není třeba samostatně prohledávat prostor hyperparametrů, jak to vyžadovaly dřívější přístupy založené na mini-dávkách. Kosinová křivka snižuje velikost kroku na desetinu počáteční hodnoty. Výchozí nastavení vydané třídy počítá s pěti průchody při trénování a umožňuje zadat i jejich zlomkový počet.

Autoři odvodili škálovací zákony na základě 75 000 optimalizačních běhů s konfiguracemi DEEP. Uvádějí medián dodatečné chyby na vyhrazené testovací datové sadě, tedy chyby navíc oproti nejlepšímu nastavení z mřížky, ve výši 0,07 % u zákona pro velikost kroku a 0,19 % u výchozího zákona pro velikost dávky. Postup také obnovuje málo využívané shluky tak, že rozdělí dárcovský shluk, a poté každý shluk dokončí přesným průměrem přiřazení z poslední epochy. Samostatný postup dokončení založený na pomalu se měnícím klouzavém průměru se místo toho zaměřuje na chybu mimo trénovací data.

Benchmarky sahají až k deseti miliardám vektorů

Celá studie popisuje ověřování na embedovacích i syntetických datasetech. Hlavní srovnání na GPU proběhla na kartách H100 s 80 GB paměti, zatímco experimenty na CPU využily 64jádrový procesor Xeon Platinum 8462Y+. V 11 testech embedovacích datasetů VIBE autoři uvádějí, že e-means potřeboval 1,6 až 2,6 epochy, aby dosáhl chybovosti Lloydova algoritmu po 25 epochách. Oproti Flash-KMeans na jedné kartě H100 dosáhl zrychlení 8,0× až 22,8× a oproti Faiss na 64 jádrech CPU 9,0× až 15,0×; každý test proběhl s 20 náhodnými inicializacemi.

V největším měřítku autoři uvádějí rozdělení datasetu DINO10B obsahujícího 10 miliard 1 024rozměrných vektorových reprezentací výřezů DINO do přibližně 16,7 milionu shluků za 2,5 epochy s přesným přiřazováním. Výsledná chyba na testovacích datech byla o něco nižší než u výchozího Lloydova algoritmu po 25 epochách. Tento běh využil 779 GPU-hodin na 32 počítačích. V samostatném běhu s přibližným vyhledáváním nejbližšího centroidu prostřednictvím indexu IVF (inverted-file) se podařilo překonat výchozí výsledek po třech epochách; běh využil 23,2 GPU-hodiny na jednom počítači s osmi GPU. Přístup IVF prohledává vybrané skupiny centroidů, místo aby porovnával každý bod se všemi centroidy.

Studie uvádí, že přiřazování pomocí IVF je v měřítku deseti miliard vektorů 34× méně nákladné než přesné přiřazování, ale u 100 milionů vektorů žádnou výhodu nepřináší. Tento rozdíl ukazuje, proč samotný počet epoch neurčuje potřebnou infrastrukturu: množství hardwaru potřebné pro běh závisí na implementaci a metodě přiřazování.

Dostupnost a zdokumentovaná omezení

Oficiální uživatelská příručka nabízí NumpyEmeans pro data NumPy a Emeans pro tenzory PyTorch. Samotné Faiss podporuje běh na CPU; běh na GPU využívá PyTorch s podporou CUDA. Na kartách H100 a H200 jsou k dispozici jádra CuTe a na dalších podporovaných novějších GPU NVIDIA lze použít Triton. Sníženou přesnost používá na GPU pouze přiřazování k nejbližšímu centroidu; centroidy, průběžné součty i vrácené vzdálenosti zůstávají ve formátu FP32. Třídy s replikovanými i rozdělenými centroidy podporují trénink na více GPU. Studie upozorňuje, že součty ve formátu FP32 pro 16 milionů centroidů zabírají 64 GiB, což při tomto rozsahu odůvodňuje rozdělení dat.

Škálovací zákony byly vyladěny pro data s poměrně vysokým počtem dimenzí a nejsou optimální pro velmi nízkodimenzionální ani malé datasety. Výchozí nastavení vydané verze proto při 16 dimenzích nebo méně volí zákon pro velikost dávky zaměřený na kvalitu a při dvou dimenzích nebo méně vypíná obnovování shluků. Příručka také upozorňuje, že vrácené štítky při trénování pocházejí z posledního průchodu a nemusí nutně odpovídat přiřazením ke konečným centroidům. Cesta pro GPU navíc nekontroluje, zda vstupy obsahují hodnoty NaN nebo nekonečno.

Pro AI pipeline, které shlukují rozsáhlé kolekce vektorových reprezentací, toto vydání konkretizuje kompromis: udržovaná knihovna nyní umožňuje snížit počet průchodů při trénování, zatímco největší úspory GPU prostředků závisí na rozsahu, hardwaru a na tom, zda se pro danou úlohu hodí přibližné přiřazování.