Meta’s Faiss 1.16.0 voegt E-Means toe voor snellere clustering op grote schaal

De beheerders van Meta’s Faiss brachten versie 1.16.0 uit op 10 november 2026. Deze versie bevat het e-means-clusteringalgoritme van FAIR at Meta, met implementaties voor CPU, GPU en gedistribueerde systemen. De onderzoekers melden dat het algoritme de loss van Lloyd-k-means al na 1,4 tot 2,6 epochs overtreft, tegenover 25 epochs, en dat het 10–45× sneller is in wandkloktijd dan de vergeleken implementaties.

De software-uitgave volgde op de arXiv-indiening van het onderzoeksmanuscript op 6 november 2026 en was dus niet de eerste openbare bekendmaking van het algoritme. Het onderzoek is uitgevoerd door onderzoekers van FAIR at Meta en École Nationale des Ponts et Chaussées.

Versie 1.16.0 voegt referentie-implementaties van e-means toe, evenals gedistribueerde training en training met over shards verdeelde centroiden, Triton- en CuTe-toewijzingsbackends, toewijzing met lagere precisie en benchmarks om de onderzoeksresultaten te reproduceren. Ook bevat de versie DINO-demonstraties waarbij de gegevens in het geheugen blijven of vanaf SSD’s worden gestreamd.

Hoe E-Means centroiden bijwerkt

K-means zoekt centroiden die de gemiddelde kwadratische afstand tussen vectoren en hun dichtstbijzijnde centroid minimaliseren. Dat maakt het algoritme geschikt voor het ophalen van gegevens, kwantisering en gegevenscuratie. Lloyds algoritme wijst elk punt toe aan het dichtstbijzijnde centroid en berekent voor elke cluster de som en het aantal punten opnieuw op basis van de volledige dataset. E-means werkt in plaats daarvan de exponentieel afnemende sommen en aantallen bij op basis van minibatches, waardoor oudere toewijzingen geleidelijk minder zwaar meewegen; elk centroid blijft de verhouding tussen de lopende vectorsom en het lopende aantal. Als de volledige dataset als één batch wordt gebruikt, met een stapgrootte van 1, komt dat overeen met één iteratie van Lloyd.

Twee empirisch bepaalde schaalwetten leiden de batchgrootte en de initiële stapgrootte af uit de datasetgrootte, het aantal clusters en het aantal beschikbare epochs. Daardoor is de afzonderlijke hyperparameterzoektocht die bij eerdere minibatchmethoden nodig was, overbodig. Een cosinusschema verlaagt de stapgrootte tot een tiende van de beginwaarde. De uitgebrachte klasse gebruikt standaard vijf trainingspasses en accepteert ook fracties van een pass.

De auteurs bepaalden de schaalwetten op basis van 75.000 optimalisatieruns met DEEP-configuraties. Ze rapporteren een mediane spijt op de achtergehouden datasets — de extra fout ten opzichte van de beste instelling op het parameterrooster — van 0,07% voor de stapgroottewet en 0,19% voor de standaardwet voor de batchgrootte. De methode activeert ook onderbenutte clusters opnieuw door een cluster als donor te splitsen, en sluit af met het exacte gemiddelde van de toewijzingen aan elke cluster in de laatste epoch. Een afzonderlijke afrondingsmethode met een langzaam voortschrijdend gemiddelde richt zich juist op de fout buiten de steekproef.

Benchmarks reiken tot tien miljard vectoren

Het volledige artikel beschrijft validatie op embedding- en synthetische datasets. De belangrijkste GPU-vergelijkingen zijn uitgevoerd op H100-GPU’s met 80 GB geheugen; de CPU-experimenten gebruikten een Xeon Platinum 8462Y+ met 64 cores. In 11 tests met VIBE-embeddings had e-means volgens de auteurs 1,6 tot 2,6 epochs nodig om de fout van Lloyd na 25 epochs te evenaren. Op één H100 was het algoritme 8,0× tot 22,8× sneller dan Flash-KMeans; op 64 CPU-cores was het 9,0× tot 15,0× sneller dan Faiss. Voor elke test werden 20 seeds gebruikt.

Op de grootste schaal rapporteren de auteurs dat ze DINO10B, met 10 miljard DINO-patchembeddings van 1.024 dimensies, in 2,5 epochs en met exacte toewijzing hebben opgedeeld in ongeveer 16,7 miljoen clusters. De testfout was daarbij iets lager dan die van de Lloyd-baseline na 25 epochs. Deze run vergde 779 GPU-uren verdeeld over 32 machines. Een afzonderlijke run met een omgekeerde-bestandsindex (IVF) voor het benaderend zoeken naar het dichtstbijzijnde centroid overtrof de baseline na drie epochs, met 23,2 GPU-uren op één machine met acht GPU’s. De IVF-methode doorzoekt geselecteerde centroidbuckets in plaats van elk punt met elk centroid te vergelijken.

Volgens het artikel is toewijzing met IVF op de schaal van tien miljard vectoren 34× goedkoper dan exacte toewijzing, maar levert deze geen winst op bij 100 miljoen vectoren. Dat verschil laat zien waarom het aantal epochs op zichzelf niet bepaalt welke infrastructuur nodig is: de implementatie en de toewijzingsmethode bepalen hoeveel hardware een run vereist.

Beschikbaarheid en gedocumenteerde beperkingen

De officiële gebruikershandleiding biedt NumpyEmeans voor NumPy-gegevens en Emeans voor PyTorch-tensors. Faiss alleen ondersteunt uitvoering op CPU; voor uitvoering op GPU is PyTorch met CUDA-ondersteuning nodig. CuTe-kernels zijn beschikbaar op H100 en H200, en Triton op andere recente NVIDIA-GPU’s die worden ondersteund. Alleen de toewijzing aan het dichtstbijzijnde centroid gebruikt op de GPU lagere precisie; centroiden, lopende sommen en geretourneerde afstanden blijven in FP32. Klassen met gerepliceerde en gesharde centroiden ondersteunen training op meerdere GPU’s. Het artikel merkt op dat FP32-sommen voor 16 miljoen centroiden 64 GiB innemen, wat het gebruik van sharding op die schaal verklaart.

De schaalwetten zijn afgestemd op gegevens met relatief veel dimensies en zijn niet optimaal voor datasets met heel weinig dimensies of weinig gegevens. Daarom kiezen de standaardinstellingen van de uitgebrachte versie bij 16 dimensies of minder voor de kwaliteitswet voor de batchgrootte, en schakelen ze bij twee dimensies of minder het opnieuw activeren van clusters uit. De handleiding waarschuwt ook dat de geretourneerde trainingslabels afkomstig zijn van de laatste pass en niet noodzakelijk overeenkomen met toewijzingen aan de uiteindelijke centroiden. Bovendien controleert het GPU-pad de invoer niet op NaN- of oneindige waarden.

Voor AI-pijplijnen die grote verzamelingen embeddings clusteren, maakt deze uitgave de afweging concreet: een onderhouden bibliotheek biedt de mogelijkheid om met minder trainingspasses te werken, terwijl de grootste besparingen op GPU-verbruik afhangen van de schaal, de hardware en de vraag of benaderende toewijzing geschikt is voor de werklast.