🤖 AI

On the Complexity of Neural Computation in Superposition

Dit artikel vestigt theoretische onder- en bovengrenzen voor de complexiteit van neurale berekeningen in superpositie, waarbij wordt aangetoond dat het berekenen van $m'$ features in superpositie aanzienlijk meer neuronen en parameters vereist dan het louter representeren ervan, wat een expliciet limiet stelt aan modelverdichting en de parameteraantallen koppelt aan de berekende feature-capaciteit.

Oorspronkelijke auteurs: Micah Adler, Nir Shavit

Gepubliceerd 2026-02-27

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Micah Adler, Nir Shavit

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

De Kunst van het "Superpositie" Rekenen: Hoe Neurale Netwerken Meer doen dan Ze Neuzen hebben

Stel je voor dat je een enorme bibliotheek hebt, maar je hebt maar één bibliothecaris. Normaal gesproken zou die bibliothecaris maar één boek tegelijk kunnen uitlezen. Maar wat als die bibliothecaris een magische bril zou dragen waarmee hij duizenden boeken tegelijk kan scannen, zonder dat ze in de war raken?

Dat is precies wat dit paper onderzoekt. Het gaat over superpositie in neurale netwerken (zoals de AI-modellen die we vandaag de dag gebruiken). Superpositie is het vermogen van een netwerk om meer "ideeën" of "kenmerken" (features) te representeren dan er daadwerkelijk neuronen (hersencellen) zijn. Het is alsof je duizenden woorden in één zin propt, maar de zender nog steeds begrijpt wat je bedoelt.

De auteurs, Micah Adler en Nir Shavit, stellen een heel belangrijke vraag: Hoeveel "ruimte" (neuronen) heb je echt nodig om al die ideeën tegelijk te berekenen zonder dat het systeem instort?

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Koffiehuis"-chaos

Stel je een druk koffiehuis voor.

De Neuronen zijn de tafels.
De Kenmerken (Features) zijn de gesprekken die mensen voeren.

In een "normaal" netwerk (monosemantic) heeft elke tafel één gesprek. Als je 1000 gesprekken wilt voeren, heb je 1000 tafels nodig. Dat is duur en inefficiënt.
In superpositie proberen we 1000 gesprekken te voeren op slechts 100 tafels. Mensen zitten dicht bij elkaar, praten hardop, en hopen dat hun gesprek niet in de war raakt met de buren.

De vraag is: Hoe dicht bij elkaar kunnen ze zitten voordat het een onbegrijpelijke ruis wordt?

2. De Ontdekking: Er is een Grens (De Ondergrens)

De auteurs hebben bewezen dat er een harde grens is. Je kunt niet oneindig veel gesprekken op één tafel proppen.

De Regels: Als je $m'$ gesprekken wilt voeren, heb je minstens ongeveer $\sqrt{m'}$ tafels nodig.
De Metapher: Stel je hebt een grote zaal met 1000 tafels. Je kunt daar niet 1 miljoen gesprekken tegelijk houden zonder dat het een chaos wordt. Je kunt er ongeveer 1000 tot 10.000 tegelijk doen, maar daarboven breekt het systeem.
Waarom is dit belangrijk? Veel mensen dachten dat AI-modellen misschien "magisch" oneindig veel dingen konden onthouden in superpositie. Dit paper zegt: "Nee, er is een wiskundige muur." Je kunt een model niet tot in het oneindige verkleinen (distilleren) zonder dat het zijn intelligentie verliest. Er is een minimale grootte nodig om de logica te behouden.

3. De Oplossing: De "Magische Splitsing" (De Bovengrens)

Maar het goede nieuws is: het is wel mogelijk! De auteurs hebben een manier bedacht om dit slim te doen. Ze hebben een algoritme ontworpen dat laat zien hoe je die duizenden gesprekken op de 100 tafels kunt laten plaatsvinden zonder dat het mislukt.

Hun methode werkt als een slimme postbezorgdienst:

De "Kanalen": In plaats van iedereen op één grote tafel te laten zitten, maken ze speciale, onzichtbare "kanalen" (zoals privélijntjes) tussen de tafels.
De Strategie: Als twee mensen een gesprek moeten voeren (bijvoorbeeld "Huis" EN "Dier" = "Hond"), worden ze naar een specifiek kanaal gestuurd waar alleen zij kunnen praten.
Het Resultaat: Ze kunnen duizenden paren tegelijk berekenen, zolang ze maar op de juiste "kanalen" zitten. Het algoritme gebruikt wiskundige trucs (zoals willekeurige patronen) om te zorgen dat de gesprekken elkaar niet verstoren.

4. Het Verschil tussen "Kijken" en "Rekenen"

Dit is misschien wel het belangrijkste punt van het paper:

Alleen Kijken (Representatie): Als je alleen wilt opslaan dat een "Golden Gate Bridge" bestaat, heb je heel weinig ruimte nodig. Je kunt het als een code in een klein hoekje stoppen. (Dit is als een postkaart in je zak steken).
Rekenen (Computation): Als je wilt berekenen wat er gebeurt als je de "Golden Gate Bridge" combineert met "Zonsondergang", dan heb je veel meer ruimte nodig. Je moet de twee concepten actief laten "botsen" en een nieuw idee genereren.

Het paper bewijst dat rekenen in superpositie veel zwaarder is dan alleen opslaan. Het kost veel meer "neuronen" om de logica te draaien dan om de feiten te onthouden.

5. Wat betekent dit voor de toekomst?

Voor AI-onderzoekers: Het geeft een blauwdruk. We weten nu dat er een fundamentele limiet is aan hoe klein we AI-modellen kunnen maken. Je kunt niet zomaar alles wegknippen; je moet de "rekenkracht" behouden.
Voor ons allemaal: Het helpt ons begrijpen waarom AI-modellen soms "verwarrend" gedrag vertonen. Soms zijn ze niet dom, maar zitten ze gewoon in een situatie waar te veel gesprekken tegelijk op te weinig tafels plaatsvinden, waardoor er ruis ontstaat.

Samenvattend:
Dit paper is als een bouwplan voor een super-drukke bibliotheek. Het zegt: "Je kunt duizenden boeken op één plank zetten, maar je hebt een slim systeem nodig om ze te vinden. En je kunt niet oneindig veel boeken op één plank proppen; er is een fysieke grens aan hoeveel logica je in een klein ruimte kunt persen."

Het bewijst dat de "magie" van AI niet zomaar magie is, maar een strikte wiskundige balans tussen ruimte, energie en de hoeveelheid ideeën die we willen verwerken.

Titel: Over de Complexiteit van Neurale Berekening in Superpositie

Auteurs: Micah Adler en Nir Shavit (MIT & Red Hat)

1. Probleemstelling en Context

Neurale netwerken vertonen vaak een fenomeen genaamd superpositie: het vermogen om meer features (kenmerken) te representeren dan het aantal beschikbare neuronen. In plaats van één-op-één mapping (monosemanticiteit), gebruiken netwerken polysemantische neuronen die deelnemen aan de representatie van meerdere features tegelijk. Dit wordt mogelijk gemaakt door feature-sparseit (slechts een klein subset van features is actief tijdens een berekening) en het gebruik van bijna-orthogonale vectoren in de activatieruimte.

Hoewel superpositie essentieel is voor de schaalbaarheid en efficiëntie van grote modellen (zoals LLM's), blijft de theoretische basis van berekening in superpositie onduidelijk. Bestaande werk focust voornamelijk op het representeren van features (encoding), maar dit artikel onderzoekt de fundamentele vraag: Hoeveel neuronen en parameters zijn er theoretisch nodig om logische operaties uit te voeren op features die in superpositie zijn gecodeerd?

Het artikel formuleert dit als een algoritmisch probleem: het parallelle berekenen van een verzameling Boolese formules (specifiek 2-AND operaties en Neurale Permutaties) waarbij zowel de input als de output in superpositie zijn.

2. Methodologie

De auteurs gebruiken een tweeledige benadering om de complexiteitsgrenzen te bepalen:

A. Ondergrenzen (Lower Bounds)

Model: Ze definiëren een algemeen model van "parameter-driven algorithms" dat neurale netwerken omvat, ongeacht specifieke architectuurdetails (zoals activatiefuncties).
Techniek: Ze maken gebruik van Kolmogorov-complexiteit en informatietheoretische argumenten. Ze bewijzen dat om een grote verzameling van mogelijke functies (zoals alle permutaties of alle paren AND-operaties) correct te kunnen onderscheiden, de parameterstring van het netwerk een minimale lengte moet hebben.
Aannames: De bewijzen houden rekening met netwerken die perfect correct zijn, maar ook met netwerken die een klein fractie fouten mogen maken (wat realistischer is voor getrainde netwerken). Ze nemen aan dat de input en output feature-sparse zijn (maximaal $v$ actieve features).

B. Bovengrenzen (Upper Bounds)

Constructie: Ze presenteren expliciete, wiskundig bewezen constructies van neurale netwerken (Multi-Layer Perceptrons met ReLU-activaties) die 2-AND en Permutaties berekenen in superpositie.
Technieken: De constructies maken gebruik van:
- Random Compression/Decompression: Het gebruik van willekeurige matrices om features te comprimeren naar een lagere dimensie en ze later te reconstrueren.
- Output Channels: Het toewijzen van specifieke "rekenkanalen" (subruimtes) aan specifieke output-functies om interferentie te minimaliseren.
- Feature Influence: Een nieuwe maatstaf die definieert hoeveel output-functies door één input-variabele worden beïnvloed. De algoritmen partitioneren het probleem op basis van dit concept (lichte vs. zware inputs).

3. Kernresultaten

Ondergrenzen (Theoretische Limieten)

Voor een breed scala aan problemen, waaronder permutaties en paarwise logische operaties (2-AND) met $m'$ output-features:

Neuronen: Een netwerk vereist minimaal $\Omega(\sqrt{m'} \log m')$ neuronen om $m'$ features in superpositie te berekenen.
Parameters: De totale parameterbeschrijving vereist minimaal $\Omega(m' \log m')$ bits.
Implicatie: Dit impliceert een sub-exponentiële bovengrens voor de capaciteit van een netwerk: een netwerk met $n$ neuronen kan maximaal $O(n^2 / \log n)$ features berekenen. Dit staat in schril contrast met passieve representatie (zonder berekening), waar de Johnson-Lindenstrauss-Lemma suggereert dat $n$ neuronen tot $2^{O(n)}$ features kunnen representeren. Er is dus een exponentiële kloof tussen het representeren van features en het berekenen ervan in superpositie.

Bovengrenzen (Constructieve Bewijzen)

De auteurs tonen aan dat deze ondergrenzen haalbaar zijn door expliciete algoritmen te bouwen:

Efficiëntie: Ze construeren netwerken die 2-AND en Permutaties berekenen met $n = O(\sqrt{m'} \log m')$ neuronen.
Parameters: Het totale aantal parameters is $O(m' \log^2 m')$ , wat dicht bij de theoretische ondergrens ligt (binnen een factor $\log m'$ ).
Foutloosheid: De constructies zijn wiskundig bewezen correct (foutloos) en vereisen slechts een constant aantal lagen ( $O(1)$ ).
Algoritmen:
- Voor lage invloed (inputs die in weinig outputs voorkomen): Gebruik van "output channels" waarbij inputs worden gerouteerd naar specifieke subruimtes.
- Voor hoge invloed: Gebruik van "input channels" met overlappende codes.
- Voor gemengde gevallen: Een hybride aanpak met een speciaal mechanisme ("detect-two-active-heavies") om interferentie tussen zeer zware inputs te voorkomen.

4. Belangrijke Bijdragen en Significatie

Eerste Theoretische Fundament: Dit is het eerste werk dat strikte onder- en bovengrenzen stelt voor de complexiteit van neurale berekening in superpositie. Het vult de empirische schaalwetten aan met rigoureuze wiskundige bewijzen.
Kloof tussen Representatie en Berekening: Het artikel demonstreert dat superpositie veel efficiënter is voor het opslaan van informatie dan voor het verwerken ervan. De noodzaak van $\Omega(\sqrt{m'})$ neuronen voor berekening versus $O(\log m')$ voor representatie toont aan dat berekening de "bottleneck" is in superpositie.
Beperkingen voor Modelcompressie: De resultaten stellen fundamentele limieten aan modelcompressie-technieken (zoals distillatie en pruning). Je kunt een model niet willekeurig verkleinen zonder in te leveren op het aantal features dat het kan berekenen; er is een harde ondergrens aan het aantal parameters dat nodig is voor een bepaalde expressiviteit.
Mechanistische Interpretatie: De auteurs introduceren het concept van "feature influence" en tonen aan dat specifieke mechanismen (zoals het routen van inputs naar dedicated kanalen) theoretisch noodzakelijk zijn. Interessant genoeg is gebleken dat deze mechanismen ook van nature ontstaan in traditioneel getrainde kleine netwerken (verwijzing naar vervolgonderzoek [1]), wat suggereert dat deze theorie de werkelijkheid van getrainde netwerken weerspiegelt.
Generalisatie: De methoden zijn uitbreidbaar naar meer dan twee actieve inputs, meerdere lagen, en $k$ -way AND operaties, hoewel dit de complexiteit exponentieel laat toenemen met het aantal actieve features ( $v$ ).

Conclusie

Het artikel concludeert dat het aantal parameters een goede estimator is voor het aantal features dat een neurale net kan berekenen. Hoewel superpositie cruciaal is voor de schaalbaarheid van AI-modellen, is er een fundamentele wiskundige prijs te betalen voor het uitvoeren van berekeningen in deze staat: de benodigde resources groeien met de wortel van het aantal features, niet lineair of logaritmisch. Dit biedt een nieuwe, theoretische lens om de capaciteit en de beperkingen van moderne neurale netwerken te begrijpen.