Meta’s Faiss 1.16.0 tilføjer E-Means for hurtigere klyngedannelse i stor skala

Vedligeholderne af Meta’s Faiss udgav version 1.16.0 den 10. november 2026 med FAIR at Meta’s e-means-klyngedannelsesalgoritme i pakningen samt implementeringer til CPU, GPU og distribueret brug. Forskerne rapporterer, at algoritmen opnår lavere tabsfejl end Lloyds k-means efter 1,4 til 2,6 epoker mod 25 epoker, med 10–45× hurtigere køretid på GPU end de implementeringer, der blev sammenlignet med.

Softwareudgivelsen følger forskningsfortrykkets indsendelse til arXiv den 6. november 2026 og er ikke algoritmens første offentlige omtale. Arbejdet er udført af forskere fra FAIR at Meta og École Nationale des Ponts et Chaussées.

Version 1.16.0 tilføjer referenceimplementeringer af e-means, distribueret træning og træning med opdeling af centroidpunkter på tværs af enheder, Triton- og CuTe-backends til tildeling, tildeling med reduceret præcision samt benchmarks til reproduktion af forskningsresultaterne. Den indeholder også DINO-demonstrationer, hvor data enten holdes i hukommelsen eller streames fra SSD’er.

Sådan opdaterer E-Means centroidpunkter

K-means søger efter centroidpunkter, der minimerer den gennemsnitlige kvadrerede afstand mellem vektorerne og deres nærmeste centroidpunkt, hvilket understøtter informationssøgning, kvantisering og dataudvælgelse. Lloyds algoritme tildeler hvert punkt til det nærmeste centroidpunkt og genberegner summen og antallet af punkter i hver klynge ud fra hele datasættet. E-means opdaterer i stedet eksponentielt henfaldende summer og antal ud fra minibatches, så ældre tildelinger gradvist får mindre betydning; hvert centroidpunkt er fortsat forholdet mellem den løbende vektorsum og det løbende antal. Hvis hele datasættet bruges som én batch med en trinlængde på 1, svarer det til én iteration af Lloyds algoritme.

To tilpassede skalalove beregner batchstørrelse og indledende trinlængde ud fra datasættets størrelse, antallet af klynger og epokebudgettet. Dermed undgår man den særskilte søgning efter hyperparametre, som tidligere minibatchmetoder krævede. En cosinusplan sænker trinlængden til en tiendedel af startværdien. Den udgivne klasse bruger som standard fem træningsgennemløb og accepterer brøkdele af et gennemløb.

Forfatterne tilpassede lovene ved hjælp af 75,000 optimeringskørsler på DEEP-konfigurationer. De rapporterer en medianregret på holdte datasæt – det vil sige den ekstra fejl i forhold til den bedste indstilling i gitteret – på 0.07% for loven for trinlængde og 0.19% for standardloven for batchstørrelse. Metoden genopliver også underudnyttede klynger ved at dele en donorklynge og afslutter derefter med det nøjagtige gennemsnit for hver klynge ud fra tildelingerne i den sidste epoke. En separat afslutningsmetode med langsomt glidende gennemsnit sigter i stedet mod at reducere fejlen på data uden for træningssættet.

Benchmarks strækker sig til ti milliarder vektorer

Den fulde artikel beskriver validering på tværs af indlejrings- og syntetiske datasæt. De vigtigste GPU-sammenligninger blev udført på H100-GPU’er med 80 GB, og CPU-forsøgene på en 64-kernet Xeon Platinum 8462Y+. På tværs af 11 VIBE-indlejringstests rapporterer forfatterne, at e-means brugte 1,6 til 2,6 epoker på at nå Lloyds fejl efter 25 epoker. Hastighedsforbedringen var 8.0× til 22.8× sammenlignet med Flash-KMeans på én H100 og 9.0× til 15.0× sammenlignet med Faiss på 64 CPU-kerner, med 20 frø pr. test.

I den største skala rapporterer forfatterne, at de fordelte DINO10B, som indeholder 10 milliarder 1,024-dimensionelle DINO-patchindlejringer, på cirka 16.7 millioner klynger på 2,5 epoker med nøjagtig tildeling. Testfejlen blev dermed en smule lavere end med Lloyds baseline efter 25 epoker. Kørslen brugte 779 GPU-timer fordelt på 32 maskiner. I en separat kørsel med omtrentlig søgning efter nærmeste centroidpunkt via et IVF-indeks (inverted file) blev baselinen overgået efter tre epoker med et forbrug på 23.2 GPU-timer på én maskine med otte GPU’er. IVF-metoden søger i udvalgte centroidpunktspuljer i stedet for at sammenligne hvert punkt med hvert centroidpunkt.

Artiklen rapporterer, at IVF-tildeling er 34× billigere end nøjagtig tildeling ved en skala på ti milliarder vektorer, men ikke giver nogen gevinst ved 100 millioner vektorer. Forskellen viser, hvorfor antallet af epoker alene ikke afgør infrastrukturbehovet: Implementeringen og tildelingsmetoden bestemmer, hvor meget hardware en kørsel kræver.

Tilgængelighed og dokumenterede begrænsninger

Den officielle brugervejledning indeholder NumpyEmeans til NumPy-data og Emeans til PyTorch-tensorer. Faiss alene understøtter kørsel på CPU; kørsel på GPU kræver CUDA-aktiveret PyTorch, og CuTe-kerner er tilgængelige på H100 og H200, mens Triton understøttes på andre nyere NVIDIA-GPU’er. Kun tildeling til nærmeste centroidpunkt bruger reduceret præcision på GPU, mens centroidpunkter, løbende summer og returnerede afstande fortsat er FP32. Klasser med replikerede og opdelte centroidpunkter understøtter træning på flere GPU’er; artiklen bemærker, at FP32-summer for 16 millioner centroidpunkter fylder 64 GiB, hvilket gør opdeling nødvendig i den skala.

Skalalovene er tilpasset data med forholdsvis mange dimensioner og er ikke optimale til meget lavdimensionelle eller små datasæt. Standardindstillingerne i den udgivne version vælger derfor kvalitetsloven for batchstørrelse ved 16 dimensioner eller færre og deaktiverer genoplivning ved to dimensioner eller færre. Vejledningen gør også opmærksom på, at de returnerede træningsetiketter stammer fra det sidste gennemløb og ikke nødvendigvis svarer til tildelingerne for de endelige centroidpunkter, og at GPU-forløbet ikke kontrollerer input for NaN- eller uendelige værdier.

For AI-pipelines, der klynger store samlinger af indlejringer, gør udgivelsen afvejningen konkret: Det er nu muligt at bruge færre træningsgennemløb i et vedligeholdt bibliotek, mens de største reduktioner i GPU-forbrug afhænger af skalaen, hardwaren og af, om omtrentlig tildeling passer til arbejdsbelastningen.