💬 NLP

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$ -Hard Problems

Dit artikel stelt vast dat standaard Modern Hopfield Networks theoretisch beperkt zijn tot de $\mathsf{TC}^0$ complexiteitsklasse en niet in staat zijn om $\mathsf{NC}^1$ -harde problemen op te lossen, maar demonstreert dat het uitrusten van hen met een Chain-of-Thought mechanisme hen in staat stelt deze grenzen te overstijgen en inherent seriële taken op te lossen.

Oorspronkelijke auteurs: Yang Cao, Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, Zhao Song

Gepubliceerd 2026-01-26

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Yang Cao, Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, Zhao Song

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

Het Grote Plaatje: De Supersterke Bibliothecasse

Stel je een Modern Hopfield Network (MHN) voor als een zeer geavanceerde, supersnelle bibliothecasse. Haar belangrijkste taak is om naar een rommelige stapel aantekeningen (input) te kijken en direct de meest vergelijkbare, perfecte pagina te vinden uit een enorm boek vol herinneringen (opgeslagen patronen).

In de wereld van AI staan deze assistenten bekend om hun ongelooflijke snelheid en enorme geheugen. Ze worden vaak gebruikt om oudere, tragere onderdelen van AI-systemen te vervangen, waarbij ze fungeren als een "super-pool" die informatie verzamelt of als een "super-aandachtsspanne" die zich op de juiste details concentreert.

Echter, dit paper stelt een fundamentele vraag: Hoe slim is deze assistent eigenlijk? Kan hij elk probleem oplossen, of zijn er dingen die hij simpelweg niet kan, ongeacht hoe snel hij is?

De Ontdekking: De "Instant" Assistent Heeft een Plafond

De auteurs van dit paper gedroegen zich als circuit-detectives. Ze onderzochten de interne bedrading van deze AI-assistenten om te zien wat voor soort logica zij kunnen verwerken.

Ze ontdekten dat standaard Modern Hopfield Networks (zelfs de varianten met veel lagen) lijken op instantane rekenmachines. Ze zijn geweldig in het uitvoeren van taken die kunnen worden opgedeeld in veel kleine, parallelle taken die tegelijkertijd plaatsvinden. In computerwetenschappelijke termen behoren ze tot een klasse genaamd TC0.

De Analogie:
Stel je voor dat je een team hebt van 1.000 arbeiders in een fabriek.

Standaard MHN: Elke arbeider krijgt een stukje van de puzzel en voltooit zijn deel gelijktijdig. Ze kunnen heel snel een eenvoudige muur bouwen.
De Beperking: Als de taak vereist dat een arbeider moet wachten tot de persoon vóór hem klaar is om vervolgens een gereedschap door te geven aan de volgende persoon, en zo verder (een "seriële" taak), dan stort deze fabriek in. Ze kunnen geen taken uitvoeren die een lange keten van "Stap A, dan Stap B, dan Stap C" vereisen.

Het paper bewijst dat deze netwerken bepaalde complexe problemen niet kunnen oplossen die deze vorm van stapsgewijze redenering vereisen. Specifiek kunnen ze de volgende zaken niet oplossen:

Graph Connectivity: Bepalen of je van punt A naar punt B kunt lopen in een doolhof zonder te verdwalen.
Tree Isomorphism: Vaststellen of twee complexe stambomen (of organisatiestructuren) qua structuur identiek zijn, alleen met verschillende namen.

Deze problemen behoren tot een moeilijkere categorie genaamd NC1. Het paper betoogt dat, tenzij een groot, onopgelost mysterie in de wiskunde onwaar wordt bewezen (dat TC0 gelijk is aan NC1), deze AI-assistenten fundamenteel te "ondiep" zijn om deze puzzels op te lossen. Ze zijn snel, maar ze missen diep, sequentieel denkvermogen.

De Oplossing: De Assistent een "Denkkap" Geven (Chain-of-Thought)

Als de standaard assistent vastloopt, kunnen we dat dan oplossen? Het paper zegt ja, maar alleen als we hem een specifiek hulpmiddel geven: Chain-of-Thought (CoT).

De Analogie:

Zonder CoT: De assistent probeert het doolhof op te lossen met één grote, flitsende blik. Hij ziet het hele plaatje, maar mist het pad omdat hij er niet mentaal doorheen kan "lopen".
Met CoT: We zeggen tegen de assistent: "Gok niet zomaar het antwoord. Schrijf je stappen op. Controleer eerst het linkerpad. Controleer daarna het rechterpad. Combineer die aantekeningen vervolgens om de uitgang te vinden."

Door het netwerk te dwingen om tussenliggende "gedachten" te genereren (zoals het opschrijven van stappen op een kladblok) voordat het het definitieve antwoord geeft, verandert de aard van het netwerk. Het stopt met het zijn van slechts een "instant rekenmachine" en wordt een "stapsgewijze redeneerder".

Het Resultaat:
Met deze "denkkap" (Chain-of-Thought) kan het Modern Hopfield Network eindelijk die moeilijke problemen (zoals het doolhof of de stamboom) oplossen die voorheen onmogelijk waren. Het overstijgt zijn oorspronkelijke grenzen.

Samenvatting van de Bevindingen

De Limiet: Standaard Modern Hopfield Networks zijn krachtig maar beperkt. Ze zijn als een supersnelle fotoscanner: geweldig in het direct herkennen van patronen, maar slecht in het oplossen van puzzels die een lange keten van logica vereisen. Ze kunnen specifieze moeilijke problemen niet oplossen, zoals het navigeren door complexe doolhoven of het vergelijken van complexe boomstructuren.
De Fix: Als je een "Chain-of-Thought"-mechanisme toevoegt (de AI zijn redeneerstappen één voor één laat opschrijven), doorbreekt dit het plafond. Het krijgt het vermogen om die moeilijke, stapsgewijze problemen op te lossen.
De Conclusie: Het paper trekt een duidelijke lijn in het zand. Standaard MHNs zijn geweldig voor geheugen en patroonherkenning, maar als je wilt dat ze diepe, logische redeneringen uitvoeren, moet je ze een manier geven om stapsgewijs na te denken. Zonder dat lopen ze tegen een harde muur aan.

Technische Samenvatting: Modern Hopfield Networks hebben Chain-of-Thought nodig om NC1-harde problemen op te lossen

Probleemstelling

Modern Hopfield Networks (MHNs) zijn opgekomen als krachtige componenten in deep learning en dienen als effectieve vervangers voor pooling-lagen, LSTM's en attention-mechanismen. Hoewel recente ontwikkelingen hun opslagcapaciteit en retrieval-efficiëntie hebben verbeterd, blijft hun fundamentele theoretische grens met betrekking tot computationele expressiviteit onderbelicht. Specifiek is er een gebrek aan een rigoureuze karakterisering van de klasse problemen die MHNs kunnen oplossen wanneer ze worden bekeken door de lens van de circuitcomplexiteitstheorie. De centrale vraag die wordt behandeld is: Wat zijn de fundamentele limieten van Modern Hopfield Networks in termen van circuitcomplexiteit?

Methodologie

De auteurs maken gebruik van het framework van de circuitcomplexiteitstheorie om de computationele middelen die door MHNs worden vereist, rigoureus te analyseren. De methodologie omvat:

Mapping naar Computationele Circuits: De auteurs mappen de architecturale componenten van MHNs (inclusief de Hopfield-laag, kernelized varianten en bijbehorende feed-forward netwerken) naar Booleaanse circuits.
Precisie en Architecturale Beperkingen: De analyse richt zich op netwerken met polynomiale precisie ( $p \le \text{poly}(n)$ ), constante diepte ( $m = O(1)$ ) en een lineaire verborgen dimensie ( $d \le O(n)$ ).
Complexiteitsklasse Analyse: De auteurs bepalen de specifieke complexiteitsklasse (bijv. $\text{TC}^0$ , $\text{NC}^1$ ) waarin deze netwerken zich bevinden door de diepte en grootte van de threshold-circuits te analyseren die hun operaties simuleren, inclusief floating-point rekenkunde, matrixvermenigvuldigingen en niet-lineaire activatiefuncties.
Hardheidsproeven: Door de bovengrens van MHNs binnen een specifieke complexiteitsklasse vast te stellen, demonstreren de auteurs hun onvermogen om problemen op te lossen die bekend staan als hard voor die klasse (specifiek $\text{NC}^1$ -harde problemen), uitgaande van standaard complexiteitsvermoedens ( $\text{TC}^0 \neq \text{NC}^1$ ).
Chain-of-Thought (CoT) Uitbreiding: De studie breidt de analyse uit naar MHNs die zijn uitgebreid met een Chain-of-Thought mechanisme, waarbij wordt onderzocht of iteratieve redeneerstappen de gevestigde complexiteitsbarrières kunnen overstijgen.

Belangrijkste Bijdragen en Resultaten

1. Circuit Complexiteit Bovengrens voor Standaard MHNs

Het artikel stelt vast dat elk Modern Hopfield Network (of Kernelized Hopfield Network) met polynomiale precisie, constante diepte en een lineaire verborgen dimensie zich binnen de $\text{DLOGTIME-uniform } \text{TC}^0$ complexiteitsklasse bevindt.

Theorem 4.8 & 5.4: De auteurs bewijzen dat de constituerende componenten (Hopfield attention matrices, laag-computaties en ReLU feed-forward netwerken) gesimuleerd kunnen worden door uniforme threshold-circuits van constante diepte en polynomiale grootte.
Implicatie: Tenzij $\text{TC}^0 = \text{NC}^1$ , zijn deze architecturen fundamenteel onbekwaam om $\text{NC}^1$ -harde problemen op te lossen.

2. Onmogelijkheidsresultaten voor Specifieke Problemen

Op basis van de $\text{TC}^0$ bovengrens demonstreren de auteurs dat standaard MHNs specifieke $\text{NC}^1$ -harde problemen niet kunnen oplossen:

Undirected Graph Connectivity: Het bepalen of er een pad bestaat tussen twee knopen in een ongerichte graaf.
Tree Isomorphism: Het bepalen of twee gekleurde bomen isomorf zijn.
Theorema 6.9–6.12: Deze resultaten gelden voor zowel standaard Modern Hopfield Networks als Kernelized Hopfield Networks onder de aanname dat $\text{TC}^0 \neq \text{NC}^1$ .

3. Limieten Overstijgen met Chain-of-Thought

Het artikel laat zien dat deze beperkingen niet absoluut zijn. Door MHNs uit te rusten met een Chain-of-Thought (CoT) mechanisme, kunnen de netwerken de $\text{TC}^0$ barrière overstijgen.

Theorem 7.4: Een Modern Hopfield Network met een $n$ -staps CoT-mechanisme kan het woordprobleem voor de permutatiegroep $S_5$ (een $\text{NC}^1$ -compleet probleem) oplossen.
Contrast: Deze taak is aantoonbaar onmogelijk voor standaard constant-depth MHNs zonder CoT, zelfs met polynomiale embedding-groottes en logaritmische precisie. Dit komt overeen met bevindingen in de Transformer-literatuur waar tussenliggende redeneerstappen de computationele expressiviteit verhogen.

Betekenis

Het artikel biedt een fijnmazige theoretische grens tussen de capaciteiten van standaard Modern Hopfield Networks en die welke zijn uitgebreid met redeneerstappen.

Theoretisch Inzicht: Het verduidelijkt dat, ondanks hun empirische succes en het vermogen om complexe lagen zoals LSTM's en attention-mechanismen te vervangen, standaard MHNs dezelfde fundamentele computationele beperkingen delen als constant-depth Transformers en andere $\text{TC}^0$ -gebonden modellen. Ze zijn inherent beperkt in het oplossen van seriële, $\text{NC}^1$ -harde taken.
Architecturale Begeleiding: De resultaten suggereren dat voor MHNs om inherente seriële problemen aan te pakken (zoals complexe graafconnectiviteit of groepentheoretische woordproblemen), architecturale modificaties die iteratief redeneren toestaan (zoals CoT) noodzakelijk zijn.
Unificatie: Het werk unificeert het begrip van MHNs en Kernelized MHNs onder dezelfde complexiteitsbeperkingen, waarmee de eerdere complexiteitsanalyses die primair gericht waren op Transformers, worden uitgebreid naar deze specifieke klasse van energy-based modellen.

Samenvattend karakteriseert het artikel de expressieve kracht van Modern Hopfield Networks door te bewijzen dat ze zonder iteratief redeneren beperkt zijn tot $\text{TC}^0$ , maar in staat zijn tot het oplossen van $\text{NC}^1$ -harde problemen wanneer ze geïntegreerd worden met een Chain-of-Thought mechanisme.