🤖 machine learning

Indexing: the Beginning and the End

Dit artikel introduceert het concept causale complexiteit om aan te tonen dat gemaskeerde deep-learning architecturen zoals RNN's en linear-attention transformers fundamenteel beperkt zijn in het oplossen van de indexerings-primitief wanneer de index aan het einde van de input verschijnt, terwijl softmax en niet-gemaskeerde linear-attention transformers dit efficiënt kunnen oplossen, een theoretische scheiding die wordt bevestigd door empirische experimenten.

Oorspronkelijke auteurs: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

Gepubliceerd 2026-07-27

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een superintelligente robot probeert te bouwen die een verhaal kan lezen en vragen erover kan beantwoorden. Dit is de wereld van kunstmatige intelligentie, specifiek een vakgebied genaamd "deep learning", waar computers patronen leren door enorme hoeveelheden data te bekijken. Een lange tijd waren de meest populaire robots voor deze taak "Transformers" genoemd. Ze zijn als briljante bibliothecarissen die razendsnel door een heel boek kunnen bladeren om een specifieke feit te vinden. Maar er is een addertje onder het gras: naarmate het boek langer wordt, wordt de bibliothecaris steeds langzamer, en het bouwen van hen kost veel energie en geld.

Om dit op te lossen, hebben wetenschappers nieuwe soorten robots uitgevonden, zoals "RNN's" (die verhalen woord voor woord lezen, net als een mens) en "SSM's" (die proberen het hele verhaal in één keer te lezen, maar op een zeer gestroomlijnde manier). De grote vraag die iedereen stelt is: "Zijn deze nieuwe, snellere robots net zo slim als de oude, langzame robots, of hebben ze verborgen blinde vlekken?" Om dat antwoord te vinden, laten onderzoekers de robots niet simpelweg raden; ze geven ze kleine, lastige puzzels. Deze puzzels zijn als het "huiswerk" van de AI-wereld. Als een robot een simpel huiswerkprobleem niet kan oplossen, bewijst dat dat het brein van de robot een fundamentele limiet heeft, ongeacht hoeveel je hem traint.

Dit artikel, getiteld "Indexing: the Beginning and the End," neemt een zeer specifieke, eenvoudige puzzel genaamd "Indexing" en gebruikt deze om de hersenen van deze verschillende robotarchitecturen te testen. De puzzel is misleidend eenvoudig: stel je hebt een lijst van $n$ bits (een reeks 0'en en 1'en) en een getal $i$ dat vertelt welke bit je moet kiezen. Het doel is simpelweg om de waarde van die specifieke bit te geven. Het is alsof je een rij van 64 lichtschakelaars krijgt en een getal, zeg "17", en gevraagd wordt: "Staat schakelaar 17 aan of uit?"

De onderzoekers, Alexander Kozachinskiy, Vicente Opazo en Felipe Urrutia, ontdekten dat de volgorde waarin de robot de informatie ziet, alles verandert. Ze ontdekten dat sommige robots ongelooflijk snel zijn in deze taak, terwijl anderen tegen een muur aanlopen die ze simpelweg niet kunnen beklimmen, ongeacht hoeveel lagen van "denken" ze hebben.

Hier komt de wending: het artikel bewijst dat voor bepaalde soorten robots (specifiek die welke informatie op een "causale" of "gemaskeerde" manier verwerken, wat betekent dat ze alleen naar wat vóór hen kwam kunnen kijken en niet naar wat ná hen komt) het oplossen van deze puzzel wiskundig onmogelijk is als de lijst met bits lang is en het indexgetal aan het einde verschijnt. Het is alsof je een robot een lange rij mensen geeft, vraagt om ieders gezicht te onthouden, en dan aan het einde fluistert: "Vertel me de naam van persoon nummer 42." Het artikel laat zien dat robots zoals RNN's, Mamba en gemaskeerde linear-attention transformers een "geheugenbottleneck" hebben. Ze kunnen al die informatie niet comprimeren in een pakketje dat klein genoeg is om de specifieke bit te onthouden wanneer de index eindelijk arriveert. De auteurs hebben dit bewezen met rigoureuze wiskunde die standhoudt, zelfs als de robots over oneindige precisie beschikken (dat wil zeggen: ze raken niet in de war door afrondingsfouten).

Echter, het verhaal verandert als je het scenario omdraait. Als het indexgetal aan het begin van de lijst verschijnt (waardoor de robot verteld wordt: "Onthoud persoon 42" voordat je zelfs de rij mensen ziet), worden de RNN's de superhelden. Ze kunnen dit in één stap oplossen, terwijl de andere robots (inclusief de beroemde Transformers) minstens twee stappen nodig hebben om het uit te vogelen.

De auteurs deden niet alleen de wiskunde; ze voerden ook experimenten uit met echte modellen. Ze trainden deze robots op lijsten van tot wel 64 bits. De resultaten kwamen exact overeen met hun theorie. De robots die de wiskunde zei dat zouden falen (de causale robots die proberen de bit aan het einde van een lange lijst te vinden) gaven consequent op naarmate de lijsten langer werden. Ondertussen leerden de robots die de wiskunde zei dat ze zouden slagen de taak gemakkelijk.

Dus, wat is de kern van het verhaal? Het is niet dat de ene robot "beter" is dan de andere in elke opzicht. In plaats daarvan onthult het artikel dat verschillende architecturen verschillende "superkrachten" en verschillende "kryptoniet" hebben. De manier waarop een robot informatie verwerkt — of hij nu van links naar rechts leest, alles in één keer bekijkt, of het verleden probeert samen te vatten — bepaalt precies welke puzzels hij kan oplossen en welke hem voor altijd zullen verbazen. Dit helpt wetenschappers om de fundamentele limieten van AI te begrijpen, zodat we weten wat ze kunnen en niet kunnen wanneer we de volgende generatie slimme machines bouwen.

Technische Samenvatting: Indexering: Het Begin en het Einde

Probleemstelling

Dit artikel onderzoekt de expressiviteit en informatie-bottlenecks van moderne deep learning-architecturen—specifiek Recurrent Neural Networks (RNN's), Softmax Transformers, Linear-Attention Transformers en State-Space Models (SSM's)—door de lens van het indexeringsprimitief.

De indexeringstaak wordt als volgt gedefinieerd: gegeven een sequentie van $n$ bits $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ en een index $i \in \{1, \dots, n\}$ , moet het model de waarde van de $i$ -de bit, $\sigma_i$ , produceren. De auteurs analyseren twee specifieke variaties van deze taak om verschillende architecturale beperkingen te onderzoeken:

Rechts-georiënteerde Indexering (RHI): De index $i$ verschijnt aan het einde van de invoersequentie (na de bits). Het model moet $\sigma_i$ ophalen op basis van de informatie die is verwerkt uit de voorafgaande $n$ bits.
Links-georiënteerde Indexering (LHI): De index $i$ verschijnt aan het begin van de invoersequentie (vóór de bits). Het model moet de indexinformatie door de sequentie dragen om $\sigma_i$ aan het einde te extraheren.

De studie richt zich op "kleine" architecturen, gedefinieerd als zijnde met $o(1)$ parameters (een constant aantal parameters ten opzichte van de sequentielengte $n$ ) en potentieel oneindige-precisie reële rekenkunde.

Methodologie

De auteurs maken gebruik van een theoretisch kader gebaseerd op causale complexiteit en VC-dimensie om onvoorwaardelijke ondergrenzen af te leiden.

Causale Complexiteit

Voor causale (gemaskeerde) architecturen, waarbij de output op positie $k$ alleen afhangt van inputs $1$ tot en met $k$ , introduceren de auteurs het begrip causale complexiteit. Dit meet de minimale dimensie $s$ waartoe de geschiedenis van inputs ( $x_1, \dots, x_{k-1}$ ) kan worden gecomprimeerd (via een "fingerprint"-functie), zodat de $k$ -de output kan worden berekend vanuit deze gecomprimeerde representatie en de huidige input $x_k$ met een lage rekenkundige complexiteit.

Kerninzicht: Als een architectuur een lage causale complexiteit heeft (specifiek $o(1)$ ), kan deze de noodzakelijke geschiedenis niet comprimeren om taken op te lossen die het ophalen van specifieke verleden informatie vereisen wanneer die informatie niet direct toegankelijk is.

Theoretische Instrumenten

VC-dimensie: De auteurs passen de techniek van Kozachinskiy et al. (2025) aan om aan te tonen dat als een model de indexeringstaak oplost, de bijbehorende conceptklasse een VC-dimensie van ten minste $n$ moet hebben.
Rekenkundige Complexiteit: Ze maken gebruik van de rekenkundige complexiteit van de functies die door de lagen worden berekend (inclusclusief exponenten, rekenkundige operaties en conditionele logica) om de VC-dimensie te begrenzen.
Onvoorwaardelijke Grenzen: In tegen tegenstelling tot eerdere werken die vertrouwden op aannames van beperkte precisie, gelden deze resultaten zelfs voor modellen die gebruikmaken van reële getallen met oneindige precisie.

Experimentele Validatie

De theoretische bevindingen worden gevalideerd door experimenten op binaire indexeringstaken voor sequentielengtes $n \in \{8, 16, 32, 64\}$ . De auteurs vergelijken:

Volledige en causale varianten van Softmax en Linear-Attention Transformers.
RNN's (specifiek GRU's).
SSM's (specifiek Mamba).
Alle modellen worden vanaf nul getraind met vaste hyperparameters om de leerdynamiek naarmate $n$ toeneemt te observeren.

Belangrijkste Bijdragen en Resultaten

1. Rechts-georiënteerde Indexering (Index aan het Einde)

In dit scenario verwerkt het model alle $n$ bits voordat het de index ziet. Om de taak op te lossen, moet het model de volledige $n$ -bits string comprimeren in een staat die klein genoeg is om door de index-token te worden verwerkt.

Onmogelijkheid voor architecturen met lage causale complexiteit: De auteurs bewijzen dat geen enkele constante hoeveelheid ( $O(1)$ $O (1)$ ) lagen met $o(1)$ $o (1)$ causale complexiteit RHI kan oplossen.
- Beïnvloede Architecturen: Kleine RNN's, SSM's (bijv. Mamba) en gemaskeerde Linear-Attention Transformers hebben allemaal $o(1)$ causale complexiteit. Daarom kunnen zij RHI niet oplossen in een constant aantal lagen, zelfs niet met oneindige precisie.
- Experimentele Bevestiging: Modellen in deze categorie (1-laagse en meerlaagse causale linear-attention, GRU's, Mamba) slagen er consequent niet in om RHI te leren naarmate $n$ groeit, waarbij ze een succespercentage van 0% bereiken bij $n=64$ .
Mogelijkheid voor architecturen met hoge causale complexiteit:
- Softmax Transformers: Een enkele laag met $O(1)$ parameters kan RHI oplossen. Dit wordt toegeschreven aan hun hoge causale complexiteit (via het softmax-mechanisme dat globale aandacht mogelijk maakt).
- Volledige Linear-Attention: Twee lagen met $O(1)$ parameters kunnen RHI oplossen.
- Experimentele Bevestiging: Deze configuraties leren de taak gemakkelijk, met hoge succespercentages zelfs bij $n=64$ .

2. Links-georiënteerde Indexering (Index aan het Begin)

In dit scenario wordt de index eerst verwerkt en moet deze door de sequentie worden gedragen naar de relevante bitpositie.

Dominantie van RNN's: Kleine RNN's kunnen LHI oplossen in een enkele laag met $O(1)$ parameters. Ze onderhouden van nature een verborgen staat die de index $i$ kan dragen en een specifieke coördinaat kan bijwerken wanneer de $i$ -de bit wordt tegengekomen.
Beperkingen van andere architecturen:
- SSM's en Linear-Attention: Zowel 1-laagse SSM's als 1-laagse Linear-Attention (gemaskeerd of volledig) kunnen LHI niet oplossen met $o(1)$ parameters. De lineariteit van de SSM-updates voorkomt dat ze de bitwaarde selectief naar een specifieke positie kunnen "schrijven" die door de index wordt bepaald zonder informatie te mengen op een manier die extractie verhindert.
- Softmax Transformers: 1-laagse Softmax transformers falen ook bij LHI met $o(1)$ parameters.
Oplossing door Diepte: Alle architecturen (inclusief SSM's, Linear-Attention en Softmax Transformers) kunnen LHI oplossen als ze worden voorzien van 2 lagen met $O(1)$ parameters. De eerste laag kan de index voortplanten en de tweede kan de bit extraheren.
Experimentele Bevestiging: 1-laagse GRU's slagen bij alle lengtes. 1-laagse Mamba en Linear-Attention modellen falen voor $n \ge 16$ . 2-laagse versies van alle architecturen slagen.

Samenvattende Tabel van Vereiste Minimale Lagen

Architectuur	Links-georiënteerde Indexering (LHI)	Rechts-georiënteerde Indexering (RHI)
Volledige Softmax	2	1
Causale Softmax	2	1
Volledige Linear-Attention	2	2
Causale Linear-Attention	2	$\omega(1)$ (Onmogelijk)
SSM (bijv. Mamba)	2	$\omega(1)$ (Onmogelijk)
RNN	1	$\omega(1)$ (Onmogelijk)

(Opmerking: $\omega(1)$ geeft aan dat het aantal benodigde lagen niet begrensd is door een constante; oftewel, het groeit met $n$ .)

Betekenis en Claims

Het artikel beweert de eerste multi-laag, oneindige-precisie ondergrenzen te bieden voor een klasse van architecturen met lage causale complexiteit, inclusief SSM's, RNN's en gemaskeerde linear-attention transformers.

Architecturale Separatie: Het indexeringsprimitief onthult een fundamentele scheiding tussen architecturen. Terwijl Softmax Transformers en volledige Linear-Attention modellen RHI efficiënt kunnen oplossen, kunnen gemaskeerde varianten en SSM's dat niet, wat de specifieke rol van globale aandachtmechanismen benadrukt bij het overwinnen van informatie-bottlenecks.
Rol van Lineariteit: De resultaten suggereren dat de lineaire update-regels van SSM's, die vaak worden geprezen om hun efficiëntie, een nadeel worden in LHI-taken waar in één stap een niet-lineaire selectieve schrijfactie vereist is.
Overeenstemming tussen Theorie en Praktijk: De experimenten laten zien dat theoretische onmogelijkheidsresultaten (asymptotische ondergrenzen) kwalitatief zichtbaar zijn in eindige trainingsomgevingen. Configuraties met theoretische oplossingen leren de taak robuust, terwijl die zonder theoretische oplossingen moeite hebben naarmate de sequentielengte toeneemt, zelfs als ze bij een kleine $n$ wel slagen.
Bescheidenheid: De auteurs stellen expliciet dat trainingsfalen geen bewijs is van onmogelijkheid, noch dat succes bij een kleine $n$ de asymptotische ondergrenzen tegenspreekt. Echter, de sterke correlatie tussen hun theoretische grenzen en empirische prestaties suggereert dat causale complexiteit een robuuste voorspeller is van leerbaarheid voor retrieval-taken.

Het werk breidt de analyse van de expressiviteit van transformers (voorheen gericht op functiesamenstelling en inductie-heads) uit naar moderne, efficiënte alternatieven, en biedt een rigoureuze wiskundige rechtvaardiging voor hun beperkingen in specifieke scenario's van informatie-extractie.