Vector-indexering met HNSW en IVF uitgelegd

Door Ivo Donker — samengesteld met AI-ondersteuning (Claude & Gemini) · Laatst bijgewerkt: 6 augustus 2026

Inleiding en de rol van embeddings

In moderne AI-toepassingen vormen embeddings de wiskundige weergave van tekst, afbeeldingen of audio. Een embeddingmodel zet ongestructureerde data om in een reeks getallen, een zogenaamde vector. Deze vector heeft vaak honderden of zelfs duizenden dimensies. In deze meerdimensionale ruimte staan concepten met een vergelijkbare betekenis dicht bij elkaar, terwijl ongerelateerde concepten verder van elkaar verwijderd zijn. Als je meer wilt weten over het genereren van deze vectoren, lees dan ons overzicht over embeddings uitgelegd.

Wanneer je zoekt op basis van betekenis, zoals bij Retrieval-Augmented Generation (RAG), vertaal je de zoekvraag eerst naar een zoekvector. Vervolgens vergelijk je deze zoekvector met alle opgeslagen vectoren in je database. De best passende resultaten zijn de vectoren die de kleinste afstand hebben tot de zoekvector, bijvoorbeeld gemeten met cosinus-similariteit of Euclidische afstand. Het efficiënt vinden van deze dichtstbijzijnde buren vormt het centrale vraagstuk van vector-indexering.

Het schaalprobleem bij zoeken op betekenis

Het exact berekenen van de afstand tussen een zoekvector en elke vector in een database wordt de exact k-Nearest Neighbors (k-NN) aanpak genoemd, ook wel een brute-force zoekopdracht. Voor kleine verzamelingen van enkele duizenden vectoren werkt dit prima. De rekenkracht die hiervoor nodig is, groeit echter lineair met het aantal vectoren ($N$) en de dimensionaliteit van de data ($d$). De tijdscomplexiteit van een volledige zoekopdracht bedraagt $O(N \cdot d)$.

Zodra een verzameling groeit naar honderdduizenden of miljoenen documenten, loopt een brute-force zoekopdracht vast. Als je een dataset van één miljoen vectoren met elk 1536 dimensies doorzoekt, vereist één enkele zoekopdracht meer dan anderhalf miljard vermenigvuldigingen en optellingen. Wanneer er meerdere zoekopdrachten per seconde binnenkomen, raakt het geheugen- en rekenstation van de server snel overbelast. Om vector-databases op schaal bruikbaar te houden, is een andere benadering nodig.

Waarom benaderend zoeken wordt geaccepteerd

De oplossing voor dit schaalprobleem is het overstappen van exact zoeken naar benaderend zoeken, in het Engels aangeduid als Approximate Nearest Neighbor (ANN) search. In plaats van te garanderen dat je gegarandeerd de allerbeste $k$ vectoren vindt, accepteer je een kleine kans dat een zoekresultaat de tweede of derde beste lucifer is. In ruil voor deze verwaarloosbare afwijking daalt de zoektijd van een lineaire schaal naar een logarithmische of sublineaire schaal.

Bij semantisch zoeken is de definitie van de "allerbeste" uitkomst immers zelden absoluut. De kwaliteit van de tekst-embeddings zelf heeft al een kleine foutmarge. Een vector die wiskundig gezien op de elfde plaats staat in plaats van de tiende, bevat inhoudelijk vrijwel dezelfde informatie. Zolang het systeem betrouwbaar de relevantste resultaten boven water haalt, is het acceptabel dat een heel enkele keer de mathematisch perfecte buur wordt gemist.

Wat recall betekent voor vector-indexering

Om te bepalen hoe goed een benaderende index presteert, wordt de metriek recall gebruikt. Recall drukt uit welk percentage van de werkelijke top-$k$ dichtstbijzijnde buren door de index wordt gevonden, vergeleken met een exacte brute-force zoekopdracht.

Als je vraagt om de 10 dichtstbijzijnde buren ($k=10$), en het benaderende algoritme geeft een lijst terug waarvan er 9 identiek zijn aan de resultaten van een exacte brute-force berekening, dan is de recall op dat specifieke punt 90% (of 0,90). Recall is de belangrijkste knop waarop je een vector-index afstelt:

• Hoge recall (bijv. > 95%): De index geeft bijna altijd de exacte resultaten terug, maar vereist meer rekenkracht en geheugen tijdens het zoeken.
• Lagere recall (bijv. 80% - 90%): De zoekopdracht verwerkt aanzienlijk sneller en verbruikt minder rekenkracht, maar de kans neemt toe dat een relevant document wordt overgeslagen.

Het afstellen van een vector-index is een continu balanceren tussen recall, latency (zoektijd per query) en geheugengebruik. Algoritmes zoals IVF en HNSW bieden specifieke instellingen om deze balans naar wens in te richten.

Inverted File Index (IVF) in gewone taal

Een van de meest gebruikte methoden voor benaderend zoeken is de Inverted File Index (IVF). IVF verdeelt de totale meerdimensionale vectorruimte vooraf in een aantal regio's, ook wel cellen of Voronoi-diagrammen genoemd.

Het proces van IVF werkt in twee stappen:

1. Trainen en clusteren: Met behulp van een clustering-algoritme (meestal $k$-means) wordt de dataset opgedeeld in $N$ clusters. Het centrum van elk cluster wordt een centroid genoemd. Elke vector in de database wordt vervolgens toegewezen aan het dichtstbijzijnde centroid en opgeslagen in de lijst van dat specifieke cluster.
2. Bevragen (Querying): Wanneer er een zoekvector binnenkomt, berekent het systeem niet de afstand tot alle vectoren in de database. Het berekent alleen de afstand tussen de zoekvector en de centroids. Vervolgens doorzoekt het systeem alleen de vectoren die binnen de dichtstbijzijnde clusters vallen.

Met IVF hoef je bij een zoekopdracht slechts een klein gedeelte van de totale database te scannen. Twee belangrijke instellingen bepalen de werking van IVF:

• nlist: Het totale aantal clusters waarin de ruimte vooraf wordt opgedeeld. Een hogere nlist zorgt voor kleinere cellen met minder vectoren per cel, wat het trainen langer maakt maar de zoekruimte per cel verkleint.
• nprobe: Het aantal cellen dat bij een zoekopdracht daadwerkelijk wordt doorzocht. Dit is de primaire knop om de balans tussen snelheid en recall in te stellen.

Het randprobleem van IVF

IVF kent een bekend theoretisch en praktisch probleem: het randprobleem (boundary issue). Stel dat een zoekvector zich vlak bij de grens van cel A bevindt. Een opslagen vector die inhoudelijk heel dicht bij de zoekvector ligt, kan net aan de andere kant van de grens in cel B zijn ingedeeld.

Als de parameter nprobe op 1 staat ingesteld, kijkt het algoritme uitsluitend binnen cel A. Hierdoor wordt de vector in cel B volledig overgeslagen, hoewel deze fysiek dichterbij ligt dan de meeste vectoren in cel A. Om dit op te lossen verhoog je nprobe. Als je nprobe instelt op bijvoorbeeld 5 of 10, doorzoekt het systeem niet alleen het dichtstbijzijnde cluster, maar ook de aangrenzende clusters. Dit verhoogt de recall aanzienlijk, maar verhoogt ook het aantal te vergelijken vectoren.

Hierarchical Navigable Small World (HNSW) in gewone taal

Een alternatieve en zeer populaire benadering is Hierarchical Navigable Small World (HNSW). Waar IVF werkt met ruimtelijke verdeling via clusters, bouwt HNSW een netwerk van verbindingen tussen vectoren op, een zogenaamde graaf (graph).

HNSW is geïnspireerd op het "small world"-fenomeen uit netwerktheorie en de datastructuur van een skip list. De index bestaat uit meerdere lagen van grafen die boven elkaar zijn gestapeld:

• Bovenste lagen: Deze lagen bevatten een klein aantal vectoren met lange verbindingen over grote afstanden. Hier maakt het algoritme grote stappen door de vectorruimte om snel in de juiste regio te belanden.
• Middelste lagen: Bevatten meer vectoren en kortere verbindingen om de zoektocht stapsgewijs te verfijnen.
• Onderste laag (Laag 0): Bevat alle vectoren uit de database, onderling verbonden in een dicht netwerk van lokale buren. Hier voert het algoritme de uiteindelijke verfijning uit om de precieze buren te identificeren.

Tijdens een zoekopdracht begint HNSW in de bovenste laag bij een vast instappunt. Het navigeert van knoop naar knoop in de richting van de zoekvector zolang de afstand afneemt. Zodra er op die laag geen betere buur meer te vinden is, daalt het algoritme af naar de onderliggende laag en herhaalt dit proces. Zo daalt het snel af naar de onderste laag, precies in de juiste regio van de ruimte.

De belangrijkste instellingen van HNSW

Het gedrag en de omvang van een HNSW-index worden gestuurd door drie cruciale parameters:

• M: Het maximale aantal verbindingen (kanten) dat een vector per laag mag hebben met andere vectoren. Een hogere waarde voor M zorgt voor een dichter netwerk. Dit verhoogt de recall bij complexe datasets, maar verhoogt het geheugenverbruik per vector evenredig.
• efConstruction: De diepte van de zoektocht die wordt gebruikt bij het opbouwen van de graaf wanneer er een nieuwe vector wordt toegevoegd. Een hogere waarde levert een beter geoptimaliseerde graaf op met een hogere recall, maar verlengt de opbouwtijd van de index aanzienlijk.
• efSearch: De grootte van de dynamische kandidatenlijst tijdens het uitvoeren van een zoekopdracht. Dit is de knop die je tijdens het bevragen gebruikt. Een grotere efSearch verhoogt de recall van de resultaten ten koste van een langere zoekduur per query.

Praktische afweging tussen HNSW en IVF

Beide indexeringstechnieken hebben duidelijke voor- en nadelen. De keuze tussen HNSW en IVF hangt voornamelijk af van de beschikbare hardware, de omvang van de verzameling en de vereiste zoekprestaties.

In de praktijk levert HNSW vaak betere prestaties als het gaat om de combinatie van lage zoektijd en hoge recall. De prijs die je hiervoor betaalt is het geheugenverbruik. Omdat elke vector in de graaf meerdere pointers naar buren moet bijhouden, kan een HNSW-index aanzienlijk meer werkgeheugen vereisen dan de ruwe vectoren zelf. IVF heeft daarentegen een veel kleinere geheugen-footprint en kan sneller worden getraind.

Als je zelf een oplossing wilt configureren, kun je onze handleiding raadplegen over het lokaal opzetten van een vector-database. Voor een breed overzicht van welke software-oplossingen welke indexen ondersteunen, kun je het overzicht van vector-databases vergeleken bekijken.

Compressie van vectoren: Quantization

Naast de manier waarop de zoekruimte wordt gestructureerd (via clusters of grafen), speelt geheugenruimte een doorslaggevende rol. Drijvende-kommagetallen (float32) nemen 4 bytes per dimensie in beslag. Een vector van 1536 dimensies kost dus ruim 6 kilobyte aan RAM. Bij honderd miljoen vectoren loopt dit op tot honderden gigabytes aan werkgeheugen.

Om dit op te lossen wordt vaak vectorcompressie toegepast, ook wel quantization genoemd. Dit is een aparte techniek die bovenop zowel IVF als HNSW kan worden toegepast:

• Scalar Quantization (SQ): Zet 32-bit floating-point getallen om naar bijvoorbeeld 8-bit integers (SQ8). Dit vermindert het geheugengebruik van de vectoren met bijna 75%, met slechts een klein verlies aan precisie.
• Product Quantization (PQ): Splits de vector op in kleinere sub-vectoren en vervangt elke sub-vector door een verwijzing naar een representatieve codebook-waarde. Dit levert een nog sterkere compressie op, waardoor grootschalige databases volledig in RAM passen of snel vanaf SSD gelezen kunnen worden.

Wanneer je IVF combineert met Product Quantization (IVF-PQ), krijg je een indexstructuur die zeer efficiënt omgaat met geheugen, al levert dit een iets lagere maximale recall op dan een ongecomprimeerde HNSW-index.

Mutaties in de index: Toevoegen en verwijderen

Een statische dataset is eenvoudig te indexeren, maar in de praktijk veranderen gegevens continu. Wat gebeurt er als je vectoren toevoegt of verwijdert?

Bij HNSW is het toevoegen van nieuwe vectoren relatief eenvoudig. De nieuwe vector doorzoekt de bestaande graaf om zijn dichtstbijzijnde buren te vinden en legt daar direct verbindingen mee aan. Verwijderen is echter ingewikkelder: wanneer een knoop uit een graaf wordt gewist, moeten de omliggende verbindingen worden hersteld om gaten in het netwerk te voorkomen. Veel implementaties gebruiken daarom 'tombstones' (zachte verwijderingen) en ruimen de graaf pas later op.

Bij IVF vereist het toevoegen van een nieuwe vector het bepalen van het dichtstbijzijnde centroid, waarna de vector aan die specifieke cel wordt toegevoegd. Als de verdeling van de data over de tijd sterk verandert (data drift), kunnen de oorspronkelijke centroids ongunstig komen te liggen. Sommige cellen worden te groot en andere blijven leeg.

In beide gevallen geldt dat continue mutaties leiden tot fragmentatie en kwaliteitsverlies van de index. Om de afsteltijden en kwaliteit optimaal te houden is periodiek onderhoud noodzakelijk. Meer technische informatie hierover vind je in ons artikel over vector-index-onderhoud.

Hoe kies je zelf de juiste strategie?

Het selecteren en afstellen van de juiste vector-index vereist een gestructureerde aanpak. Neem de volgende stappen door bij het inrichten van je productie-omgeving:

1. Analyseer de omvang en beschikbare hardware: Bepaal hoeveel vectoren je verwacht en hoeveel RAM beschikbaar is op de servers. Kan de volledige set inclusief graafstructuur in de RAM passen? Kies bij voldoende geheugen voor HNSW. Is het geheugen beperkt, overweeg dan IVF of een gecomprimeerde index (SQ/PQ).
2. Stel een representatieve testdataset op: Gebruik niet zomaar willekeurige testdata, maar verzamel een set van echte zoekvragen uit jouw toepassing. Maak een exacte 'ground truth' door op een klein deel van de data een brute-force k-NN zoekopdracht uit te voeren.
3. Meet en optimaliseer de recall: Pas de instellingen (zoals efSearch bij HNSW of nprobe bij IVF) stapsgewijs aan en vergelijk de uitkomsten met je 'ground truth'. Bepaal welke instelling de minimaal vereiste recall (bijvoorbeeld 95%) oplevert.
4. Meet pas daarna latency en doorvoer: Zodra de gewenste recall is vastgesteld, meet je de gemiddelde zoektijd en het aantal verwerkte zoekopdrachten per seconde onder belasting. Pas indien nodig de opbouwparameters (zoals M of nlist) aan om de optimale balans voor jouw infrastructuur te vinden.

Lees ook

• Embeddings uitgelegd: De basis van semantisch zoeken
• Van tekst naar getallen: Embeddings in de praktijk
• RAG voor beginners: Een introductie tot informatie-retrieval
• Handleiding: Een lokale vector-database opzetten
• Vergelijking van populaire vector-databases en leveranciers
• API & Best Practices voor vector-index-onderhoud