Gefilterde Vector Search: Wat ACORN oplost en wat ACORN aanvult

Gefilterde vector search raakt ontregeld wanneer metadatafilters een gezonde 'nearest-neighbor graph' veranderen in verspreide eilanden. De $m$-parameter van HNSW bepaalt hoeveel koppelingen elk punt krijgt. Bij de standaardinstelling van Qdrant ($m=16$) had een collectie van één miljoen punten in de onderstaande benchmark gemiddeld ongeveer 21 koppelingen per node op laag 0. Wanneer 96% van de punten wordt weggefilterd, overleeft gemiddeld minder dan één koppeling per node, waardoor de traversering kan stranden voordat de werkelijke dichtstbijzijnde matches zijn bereikt.

Qdrant herstelt deze schade op twee punten. Filterable HNSW voegt extra randen (edges) toe tijdens de indexering; ACORN stapt tijdens de zoekopdracht door de buren van buren. Beiden werken op dezelfde collectie. ACORN is waardevol waar de extra randen niet reiken: bij waarden die te algemeen zijn om te koppelen, AND-filters waar geen enkele individuele veldrand dekking voor biedt, en payload-velden die tijdens de build zijn overgeslagen.

Deze benchmark is uitgevoerd op één Qdrant-instantie en vergelijkt vier eigen zoekstrategieën van Qdrant over vier verschillende builds.

De twee varianten van ACORN

Het ACORN-paper (Patel et al., SIGMOD 2024) beschrijft twee algoritmen. De headline-claim van "2-1.000x hogere throughput bij een vaste recall" heeft betrekking op ACORN-gamma. Deze variant breidt de lijst met buren uit tijdens de constructie van de index, wat volgens de tabel in het paper 8,8x tot 33,1x langer duurt dan een standaard HNSW-build.

ACORN-1 is lichter. Het bouwt een standaard HNSW-graaf en controleert tijdens de zoekopdracht de buren van buren op momenten dat directe buren niet voldoen aan het filter. Qdrant implementeert ACORN-1 als een query-parameter die per verzoek kan worden geactiveerd, zonder dat daar wijzigingen in de index voor nodig zijn.

De graaf die Qdrant in plaats daarvan bouwt

Filterable HNSW, beschreven door mede-oprichter Andrey Vasnetsov in 2019, bouwt het herstel direct in de index. Wanneer een payload-veld (de metadata die aan elk punt is gekoppeld) wordt geïndexeerd, voegt Qdrant extra HNSW-randen toe tussen punten die een waarde in dat veld delen. Hierdoor blijft bij een gefilterde query een verbonden graaf over om doorheen te navigeren. Qdrant wijst deze randen toe aan payload-velden tijdens de indexering, maar niet elk veld krijgt ze automatisch.

Deze randen kosten bouwtijd. In onze collectie van één miljoen punten werd de HNSW-index in 116 seconden gebouwd zonder deze randen, en in 507 tot 652 seconden mét deze randen—een kostenstijging van 4,4x tot 5,6x. Dit bereik weerspiegelt de variatie tussen verschillende builds met identieke instellingen. Beiden zijn index-bouwtijden, waarbij de ingest-tijd is uitgesloten.

Qdrant bouwt deze randen per payload-veld, nooit per combinatie. Een AND-filter landt daarom op een intersectie die niet door de randen van een enkel veld wordt gedekt. ACORN-1 vult dit gat op en verschuift de kosten van de bouwtijd naar de querytijd. De query-planner van Qdrant kiest automatisch tussen ACORN, een volledige scan, directe retrieval uit de payload-index, of Filterable HNSW.

Samenvattend: Dezelfde graaf kan op twee manieren worden hersteld. ACORN stapt tijdens de zoekopdracht door weggefilterde buren; Filterable HNSW voegt tijdens de indexering extra randen toe waar een gefilterde query direct overheen kan lopen.

De Benchmark

De benchmark is uitgevoerd op één miljoen deep-image-96 vectoren (96-dimensionale image embeddings uit de ANN-benchmarks suite). Keyword-filters matchen tussen 20% van de punten en 0,012%. Recall@10 wordt gescoord tegenover exact brute force over 500 queries per filter, en latentie is de gemiddelde server-side querytijd.

Er zijn vier strategieën getest:

1. Plain graph: Standaard HNSW zonder extra randen.
2. Plain graph + ACORN: Dezelfde graaf met ACORN geforceerd aan.
3. Filterable HNSW: De standaard build met extra randen.
4. Planner + ACORN: De standaard query-planner van Qdrant, die elke query kan routeren naar ACORN, een volledige scan, of de payload-index.

Elk filter matcht één keyword-waarde op een payload-veld. De collectie bevat zeven van dergelijke velden, met elk 5, 10 of 100 verschillende waarden. De meeste filters zijn onafhankelijk van de vectoren. De rij "Correlated (10%)" is het makkelijke scenario, waarbij punten die het filter passeren ook dicht bij elkaar liggen in de vectorruimte.

Alle metingen zijn gedaan op Qdrant v1.18.2 op één laptop-klasse machine, met seriële queries. Focus op de ratio's, niet op de absolute milliseconden.

Enkele filters: Extra randen winnen

hnsw_ef (hierna kortweg ef) is het aantal kandidaten dat de zoekopdracht evalueert; het verhogen hiervan verbetert de recall maar vertraagt de query. Selectiviteit is het fractie van de punten die het filter passeren.

De onderstaande tabel vergelijkt de eerste drie strategieën. fullscanthreshold vertelt Qdrant wanneer een gefilterd resultaat klein genoeg is om direct te scannen (gemeten in kilobytes aan vector data). Voor deze drie strategieën is dit laag ingesteld zodat elke query op de graaf bleef; Planner + ACORN gebruikt de standaard threshold. Elke cel toont Recall@10 en de gemiddelde server-side latentie bij hnsw_ef=64.

Filter (selectiviteit)	Plain graph	Plain graph + ACORN	Filterable HNSW
One keyword (20%)	62.9% @ 1.6ms	98.9% @ 4.4ms	94.8% @ 1.2ms
One keyword (10%)	20.6% @ 1.7ms	98.1% @ 4.3ms	99.0% @ 1.1ms
One keyword (1%)	0.1% @ 1.6ms	67.7% @ 4.7ms	99.8% @ 1.0ms
Correlated (10%)	88.4% @ 1.7ms	98.6% @ 3.5ms	99.0% @ 1.2ms

De plain graph stort in naarmate filters strenger worden, behalve bij het gecorreleerde filter. ACORN brengt de recall terug tegen een latentie die 2,1x tot 2,9x hoger ligt dan die van de plain graph, maar stagneert bij het 1%-filter (een zwakte waar het RACORN-1 vervolgpaper zich op richt). Het enige filter waarop ACORN wint (bij 20%) draait op een payload-veld dat geen extra randen heeft gekregen, wat in de volgende sectie wordt uitgelegd.

De planner van Qdrant staat boven deze drie. Hij schat hoeveel punten een filter passeert en kiest per query een pad. Planner + ACORN behoudt een recall van 99,9% tot 100% op alle vier de filters, met latenties van 7,2ms tot 10,9ms op de graaf en 1,5ms bij het 1%-filter (waar alle 500 queries uit de payload-index kwamen).

Waarom sommige payload-velden geen extra randen krijgen

Qdrant bouwt extra randen door de waarden van elk geïndexeerd payload-veld te doorlopen. Voor elke waarde vindt het de punten die deze delen en koppelt deze, zodat een query gefilterd op die waarde nog steeds een graaf heeft om te traverseren.

Een waarde die door meer punten wordt gedeeld dan een bepaalde limiet (size cap), krijgt geen extra randen, omdat de hoofdgraaf deze hoeveelheid punten waarschijnlijk al verbonden houdt. Qdrant bepaalt deze limiet per segment (een deel van een collectie met een eigen index) via de formule: (aantal punten / gemiddelde koppelingen per node) * 4.

In dit geval bevatte één segment alle miljoen punten. Met 21 koppelingen per node geeft dit: (1.000.000 / 21) * 4 = 190.476 punten, ongeveer 19% van de collectie. Dichtere grafen hebben striktere limieten: bij 24 koppelingen per node daalt de limiet naar 16,7%.

De zeven payload-velden in de benchmark resulteerden in het volgende:

Veld	Unieke waarden	Punten per waarde	Extra randen gebouwd
2 velden	5	~200.000	Nee, alle 5 waarden boven de limiet
2 velden	10	~100.000	Ja, 10 van de 10 waarden
Correlated veld	10	~100.000	Ja, 10 van de 10 waarden
2 velden	100	~10.000	Ja, 100 van de 100 waarden

De velden met 5 waarden zitten 5% boven de limiet, waardoor alle waarden werden overgeslagen. Dit is waarom ACORN beter presteert dan Filterable HNSW bij het 20%-filter en bij de 4%-intersectie.

Dit overslaan is bewust: extra randen kosten bouwtijd en geheugen. Een waarde onder de limiet kan nog steeds worden overgeslagen als deze onder de fullscanthreshold valt of als een steekproef aantoont dat de punten al voldoende verbonden zijn.

Dubbele filters: Het intersectie-gat

Dezelfde benchmark bij hnsw_ef=64, maar nu met een AND-filter over twee keyword-velden.

Filter (selectiviteit)	Plain graph + ACORN	Filterable HNSW	Planner + ACORN
Two keywords (4%)	95.2% @ 7.7ms	63.7% @ 1.2ms	99.9% @ 13.9ms
Two keywords (1%)	72.7% @ 6.8ms	70.8% @ 1.5ms	100% @ 3.7ms
Two keywords (0.012%)	0.6% @ 2.6ms	1.8% @ 2.6ms	100% @ 1.3ms

Een intersectie van twee keywords heeft geen eigen extra randen, zelfs niet als beide individuele payload-velden die wel hebben. Bij deze ef dichten geen van beide methoden het gat volledig. De plain graph (weggelaten uit de tabel) scoorde 0,1% en 0,0% op de eerste twee rijen; het verhogen van ef naar 512 verandert niets zodra de traversering is uitgeput op een losstaand eiland.

Bij ef=512 wordt de strijd bij de 1%-intersectie wel beslist: Filterable HNSW bereikt 91,2% recall bij 4,9ms, terwijl ACORN 20,1ms nodig heeft voor 90,3% recall. De graaf herstellen tijdens de zoekopdracht kost hier dus vier keer zoveel latentie voor iets minder recall. De 4%-intersectie is de uitzondering: hier overschreden beide velden de limiet en leidt ACORN met 99,6% tegenover 92,5%.

Bij 0,012% matchen ongeveer 120 punten in een miljoen. De graaf is hier niet langer het juiste instrument. Planner + ACORN wint deze ronde door simpelweg de payload-index te lezen.

ACORN op een normale collectie

In de vorige tabellen was de fullscanthreshold laag ingesteld. In een standaardconfiguratie (met extra randen, standaard threshold en een vrije planner) ziet het resultaat er als volgt uit. ACORN staat standaard uit, dus de linker kolom is wat een collectie met payload-indexes vandaag teruggeeft.

Filter (selectiviteit)	Planner, ACORN uit	Planner + ACORN
One keyword (20%)	90.8% @ 1.1ms	100% @ 5.7ms
One keyword (10%)	98.6% @ 0.9ms	99.9% @ 4.4ms
One keyword (1%)	100% @ 1.7ms	100% @ 1.6ms
Correlated (10%)	98.6% @ 1.0ms	100% @ 4.2ms
Two keywords (4%)	39.7% @ 1.1ms	100% @ 7.3ms
Two keywords (1%)	97.2% @ 2.1ms	100% @ 2.5ms
Two keywords (0.012%)	100% @ 1.4ms	100% @ 1.2ms

De meeste filters hebben geen hulp nodig: zeer selectieve filters gaan direct naar de payload-index, en brede filters worden gedragen door de extra randen op de graaf. ACORN is cruciaal in de middelste gevallen waar geen extra randen op de payload-velden zitten. Het verhoogt de recall met 9 procentpunten bij het 20%-filter en met 60 procentpunten bij de 4%-intersectie.

Wanneer de planner op de graaf blijft, is ACORN duur (5,4x latentie bij 20% filter en 6,7x bij de 4% intersectie). Wanneer de planner de meeste queries naar de payload-index routeert, is ACORN bijna gratis.

Wat te meten op je eigen collectie

Meet de recall voor elk type filter dat je gebruikt. Begin met de filters die het meest waarschijnlijk falen: waarden die ongeveer een vijfde van de collectie of meer beslaan, en AND-combinaties daarvan. Facet-counts kunnen je vertellen welke waarden zo breed zijn.

In de standaardconfiguratie hier leverde één filter slechts 39,7% recall op zonder ACORN, terwijl alle andere boven de 90% bleven. Een enkel gemiddelde zou dit resultaat hebben gemaskeerd.

Stappenplan voor testen:

1. Maak een payload-index op elk veld waarop je filtert.
2. Laat ACORN in eerste instantie uit (de standaardinstelling).
3. Neem een steekproef van enkele honderden echte queries per filtertype.
4. Gebruik exact: true om exacte resultaten te krijgen.
5. Scoor zowel recall als latentie met ACORN uit en vervolgens met ACORN aan.

Vergelijk de winst in recall met de kosten in latentie. Een herstel zoals bij het 39,7% filter is precies waar ACORN voor bedoeld is. Een winst van enkele procentpunten is alleen de moeite waard als de latentie-multiplier klein is. Activeer acorn.enable alleen op de query-paden die het echt nodig hebben.

Het inschakelen van ACORN heeft in onze tests nooit geleid tot een lagere recall. De enige kostenpost is de latentie. Qdrant past ACORN alleen toe onder max_selectivity (standaard 0,4), dus een filter dat de helft van je collectie matcht, zal in beide gevallen niet veranderen.

Conclusie: Extra randen herstellen de graaf voordat er een query arriveert; ACORN herstelt de gaten die overblijven.

Verdere lectuur

• ACORN (Patel et al., SIGMOD 2024): Het paper achter ACORN-gamma en ACORN-1.
• RACORN-1: Een vervolgstudie gericht op de recall-instorting van ACORN-1 bij lage selectiviteit.
• PostgreSQL ACORN study: Meet de kosten van de filter-check bij het herstel tijdens de zoekopdracht.
• Filterable HNSW: Het artikel uit 2019 over de extra randen van Qdrant.
• Reproduction kit: Scripts, pinned image en ground truth om deze tabellen te reproduceren tegen jouw Qdrant-versie.