On the Theoretical Limitations of Embedding-Based Retrieval

Deze paper toont aan dat vector-embeddings fundamentele theoretische beperkingen hebben die zelfs bij realistische, eenvoudige queries leiden tot falen, omdat het aantal mogelijke zoekresultaten beperkt is door de dimensie van de embedding, wat een oproep is voor nieuwe technieken buiten het huidige paradigma.

De kern

Hier is een uitleg van het onderzoek, vertaald naar begrijpelijk Nederlands met behulp van alledaagse analogieën.

De Kernboodschap: De "Telefoonboek"-Probleem

Stel je voor dat je een gigantisch telefoonboek hebt met miljoenen namen. Je wilt iemand vinden die een heel specifieke combinatie van eigenschappen heeft. Bijvoorbeeld: "Vind iemand die van pizza houdt, maar niet van ananas, en die ook van fietsen houdt, maar alleen op zondag."

In de wereld van computers (en zoekmachines zoals Google) gebruiken we embeddings. Dit zijn slimme nummers (vectoren) die een tekst of document vertegenwoordigen. Het idee is simpel: als twee dingen op elkaar lijken, staan hun nummers dicht bij elkaar in een virtuele ruimte.

De onderzoekers van Google DeepMind en Johns Hopkins hebben ontdekt dat deze slimme nummers een fundamenteel fysiek probleem hebben. Ze kunnen niet alles tegelijk onthouden, hoe slim ze ook zijn.

De Analogie: De Koffer en de Kleding

Stel je een koffer voor (dit is de embeddings-dimensie, oftewel hoeveel "ruimte" de computer heeft om informatie op te slaan).

• Je hebt een kledingstuk voor elke mogelijke combinatie van zoekopdrachten (bijv. "pizza + ananas", "pizza + geen ananas", "fiets + zondag", etc.).
• De koffer heeft een vaste grootte.

Het probleem is dat er oneindig veel kledingstukken zijn (combinaties van interesses), maar de koffer maar één vaste grootte heeft.

De onderzoekers bewijzen wiskundig dat als je te veel unieke combinaties wilt vinden, je koffer simpelweg te klein wordt. Je kunt niet alle mogelijke kledingstukken in die ene koffer proppen zonder dat ze elkaar verpletteren.

• Huidige situatie: We hebben koffers van 1024 of 4096 vakjes. Dat is groot, maar niet groot genoeg voor alle mogelijke vragen die een mens kan bedenken.
• Het gevolg: Als je een vraag stelt die een specifieke, zeldzame combinatie van dingen vraagt, zal de computer falen. Hij kan die specifieke "kledingstuk" niet vinden omdat het niet in de koffer past.

Wat hebben ze gedaan? (Het "LIMIT"-Experiment)

Om dit te bewijzen, maakten ze een heel simpel spelletje, genaamd LIMIT.

1. Het Spel: Ze maakten een lijst met 50.000 mensen. Elke persoon houdt van een paar dingen (bijv. "Jon houdt van Quokkas en Appels", "Ovid houdt van Quokkas en Konijnen").
2. De Vraag: Ze stelden heel simpele vragen: "Wie houdt van Quokkas?" of "Wie houdt van Appels?"
3. De Twist: Ze maakten een vraag voor elke mogelijke combinatie van twee mensen. Als je 46 mensen hebt, zijn er duizenden mogelijke combinaties van "wie houdt van wat".

Het Resultaat:
Zelfs de allerbeste, slimste AI-modellen van vandaag (zoals die van Google, Snowflake en Qwen) faalden hierop. Ze konden de juiste mensen niet vinden, zelfs niet als de vragen zo simpel waren als "Wie houdt van appels?".

Het was alsof je een supercomputer vraagt om een telefoonboek te raadplegen, maar de computer vergeet telkens de naam van de persoon die je zoekt, omdat de lijst te lang is voor zijn geheugen.

Waarom is dit belangrijk?

Vroeger dachten we: "Als we maar genoeg data verzamelen en de modellen groter maken, kunnen ze alles doen."

Dit papier zegt: Nee. Het is niet alleen een kwestie van meer data of slimmere training. Het is een wiskundige muur.

• Als je vraagt om een combinatie van dingen die nog nooit eerder samen zijn gevraagd (bijvoorbeeld: "Vind artikelen over klimaatverandering die ook gaan over de prijs van koffie en die geschreven zijn in 1995"), kan een standaard zoekmachine dit nooit perfect doen.
• De "ruimte" in de computer is simpelweg te klein om elke denkbare combinatie van relevantie op te slaan.

Wat betekent dit voor de toekomst?

De auteurs zeggen dat we moeten stoppen met het denken dat één groot getal (één embedding) alles kan oplossen. We moeten nieuwe manieren vinden om te zoeken:

• Meerdere vectoren: In plaats van één getal per document, misschien wel tien of twintig (zoals een dossier met veel losse pagina's in plaats van één samenvatting).
• Slimmer zoeken: Systemen die eerst een ruwe lijst maken en dan heel nauwkeurig gaan kijken (zoals een mens die eerst een lijst doorbladert en dan de juiste pagina zoekt).

Samenvatting in één zin

Zoekmachines die werken met één "slim getal" per document, lopen tegen een muur aan: ze kunnen niet alle mogelijke combinaties van vragen en antwoorden tegelijk onthouden, hoe slim ze ook zijn, omdat hun "geheugenruimte" wiskundig te klein is.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "On the Theoretical Limitations of Embedding-Based Retrieval" (ICLR 2026) in het Nederlands.

Probleemstelling

Vector-embeddings worden steeds vaker ingezet voor complexe zoekopdrachten die redenering, instructie-opvolging en codering vereisen. De gemeenschap gaat er vaak van uit dat de huidige beperkingen van deze modellen voornamelijk te wijten zijn aan onrealistische query's of onvoldoende trainingsdata, en dat betere modellen en data deze problemen zullen oplossen.

De auteurs betogen echter dat er fundamentele, theoretische beperkingen zijn aan het vermogen van single-vector embedding-modellen om bepaalde combinaties van relevantie weer te geven. Zelfs met zeer simpele query's en realistische scenario's kunnen deze modellen theoretisch bepaalde sets van top-k documenten niet onderscheiden, ongeacht hoe goed ze getraind zijn. De huidige benchmarks testen slechts een klein deel van de mogelijke query-combinaties, waardoor deze fundamentele beperkingen vaak onopgemerkt blijven.

Methodologie

De auteurs benaderen het probleem vanuit drie invalshoeken: theoretische analyse, empirische optimalisatie en realistische evaluatie.

1. Theoretische Analyse (Geometrische Ruimte):

   • De auteurs gebruiken concepten uit de hoge-dimensionale meetkunde en de theorie van het inpakken van bollen (sphere-packing) om een ondergrens te bepalen voor de benodigde embeddingsdimensie ($d$).
   • Ze bewijzen dat voor een corpus van $n$ documenten en een zoekopdracht die $k$ relevante documenten moet teruggeven, het aantal mogelijke unieke top-k subsets beperkt is door de dimensie.
   • Stelling 1: Als elke mogelijke $k$-subset van $n$ documenten met een bepaalde marge $\gamma$ (scoreverschil tussen relevante en irrelevante documenten) moet worden gerealiseerd, dan geldt:
     $$\binom{n}{k} \leq \left(1 + \frac{1}{\gamma}\right)^d$$
     Dit impliceert dat de dimensie $d$ exponentieel moet groeien met het aantal documenten en de complexiteit van de query's om alle combinaties te kunnen onderscheiden.

2. Empirische Validatie (Best-Case Optimalisatie):

   • Om te bewijzen dat dit een fundamentele beperking is en niet slechts een probleem van training, voeren de auteurs experimenten uit met "free embeddings".
   • Hierbij worden de vectorrepresentaties van documenten en query's direct geoptimaliseerd via gradient descent (zonder beperkingen door natuurlijke taal of tokenisatie) om de testset perfect te leren.
   • Ze identificeren een "kritiek punt" (critical-n): het maximale aantal documenten dat een bepaalde dimensie $d$ kan hanteren voordat het niet meer mogelijk is om alle top-k combinaties correct te scheiden.

3. Realistische Evaluatie (LIMIT Dataset):

   • De auteurs construeren een nieuwe dataset genaamd LIMIT (Limitations of Embedding Models for Instruction-based Retrieval).
   • Opzet: Een synthetische dataset met 50.000 documenten (gebaseerd op gebruikersvoorkeuren, bijv. "Jon houdt van Appels") en 1000 query's. De query's zijn extreem simpel (bijv. "Wie houdt van Appels?"), maar de relevantie-matrix is zo ontworpen dat hij alle mogelijke combinaties van top-2 documenten test.
   • Ze evalueren state-of-the-art (SOTA) embedding-modellen (zoals GritLM, Qwen3, Gemini Embeddings) en vergelijken deze met lexische modellen (BM25) en multi-vector modellen (ColBERT).

Belangrijkste Bijdragen

1. Theoretische Ondergrens: Een wiskundig bewijs dat het aantal haalbare top-k subsets beperkt is door de embeddingsdimensie. Dit toont aan dat er een fundamentele "capaciteitsmuur" bestaat voor single-vector modellen.
2. Best-Case Empirisch Bewijs: Experimenten die aantonen dat zelfs als je de vectoren direct op de testset optimaliseert (zonder generalisatieproblemen), de dimensie te klein is om alle combinaties te coderen. De theoretische ondergrenzen blijken in de praktijk zelfs nog te optimistisch.
3. De LIMIT Dataset: Een realistisch maar eenvoudig testset die de fundamentele beperkingen blootlegt. Zelfs de beste huidige modellen falen hierop, wat aantoont dat het probleem niet ligt in de complexiteit van de taal, maar in de representatieve capaciteit van de vectorruimte.

Resultaten

• Theoretische Berekeningen: Voor web-scale zoekopdrachten (bijv. $n=10^6$ documenten, $k=10$) zou de benodigde dimensie volgens de formule vele malen groter zijn dan de huidige standaard (vaak < 4096). Zelfs met een kleine marge is de vereiste dimensie onhaalbaar.
• Free Embedding Experimenten: De curve van het "kritieke punt" volgt een polynoom van de derde graad. Voor een dimensie van 4096 is het maximum aantal documenten dat alle top-k combinaties kan hanteren ongeveer 250 miljoen. Dit is veel lager dan wat nodig is voor grote zoekmachines.
• Evaluatie op LIMIT:
  • Single-vector modellen: Presteren zeer slecht. Zelfs de beste modellen halen nauwelijks 20% Recall@100 op de volledige dataset en falen volledig op de kleine versie (46 documenten) bij Recall@20.
  • Invloed van Dimensie: Er is een sterke correlatie tussen embeddingsdimensie en prestaties; grotere dimensies leiden tot betere resultaten, maar zelfs de grootste modellen (4096 dimensies) halen geen perfecte scores.
  • Alternatieven:
    • BM25 (Lexicaal): Presteert uitstekend (bijna perfect) omdat het een zeer hoge dimensie heeft (een vector per uniek woord), maar faalt volledig zodra synoniemen worden gebruikt (geen lexicaal overlap meer).
    • Multi-vector modellen (ColBERT): Doen het beter dan single-vector modellen, maar lossen het probleem niet volledig op.
    • Cross-Encoders (Rerankers): Een model als Gemini-2.5-Pro kan de taak met 100% nauwkeurigheid oplossen omdat het geen single-vector beperking heeft.

Betekenis en Conclusie

Dit paper waarschuwt de onderzoeksgemeenschap dat het vertrouwen op single-vector embedding-modellen voor elke mogelijke instructie-gebaseerde zoekopdracht fundamenteel onhoudbaar is.

• Benchmarks zijn misleidend: Bestaande benchmarks (zoals MTEB, BEIR) testen slechts een fractie van de mogelijke query-combinaties. Modellen lijken goed te presteren omdat ze op deze beperkte set zijn overgefit, maar ze falen bij het combineren van ongerelateerde concepten via logische operatoren.
• Toekomstige Richting: De auteurs concluderen dat we nieuwe architecturen nodig hebben die deze fundamentele beperkingen kunnen overwinnen. Dit omvat:
  • Het gebruik van cross-encoders voor re-ranking.
  • Multi-vector benaderingen.
  • Lexische modellen (hoewel deze weer andere beperkingen hebben bij synoniemen).
  • Nieuwe technieken voor single-vector modellen (bijv. hyperencoders) die de onderliggende capaciteitsproblemen oplossen.

Kortom: Embedding-modellen zijn krachtig, maar ze hebben een theoretisch plafond in hun vermogen om complexe, willekeurige combinaties van relevantie weer te geven binnen een vaste vectorruimte.