Technische Samenvatting: Neuro-symbolische Syntactische Parsing: Een Neuraal Netwerk Vormgeven met het CYK-algoritme

Probleemstelling

Het artikel behandelt een fundamentele beperking van huidige Large Language Models (LLMs) en transformer-gebaseerde architecturen: hun onvermogen om betrouwbaar complexe algoritmische kennis te leren en te extrapoleren uit trainingsdata. Hoewel transformers "grokking" (generalisatie voorbij overfitting) vertonen op eenvoudige taken, worstelen ze met veeleisende algoritmische generalisatie, zoals het leren van een complex parseringsalgoritme zoals Cocke-Younger-Kasami (CYK) vanuit het niets. De auteurs stellen dat de verwachting dat transformers bekende algoritmen puur uit data zullen ontdekken een overdreven verwachting is, aangezien deze modellen vaak louter fungeren als "grote taalgeheugens" in plaats van als algoritmische motoren. Het kernprobleid is of bekende algoritmen direct kunnen worden gecodeerd in neurale netwerkarchitecturen die worden beheerst door matrix-vectorvermenigvuldigingen, in plaats van te vertrouwen op de passieve opkomst van capaciteiten door massale schaal en training.

Methodologie

De auteurs stellen CYKNN voor, een eenvoudige recurrent neurale netwerkarchitectuur die is ontworpen om het CYK-algoritme direct in een neuraal netwerkframework te injecteren. De methodologie rust op drie kerncomponenten:

1. Holografische Gereduceerde Representaties (HRRs): Om de tweedimensionale CYK-parseringstabel en symbolische grammatica-regels te coderen, maken de auteurs gebruik van HRRs. In dit kader worden symbolen gerepresenteerd als matrices afgeleid van willekeurige vectoren. Een specifieke eigenschap van deze representaties is dat een symbool en zijn inverse (bijv. $[a]^\oplus$ en $[a]^\ominus$) elkaar opheffen in matrixvermenigvuldiging, wat een identiteitsmatrix benadert. Dit maakt "holistische" operaties mogelijk waarbij sequenties van symbolen algebraïsch gemanipuleerd kunnen worden, vergelijkbaar met stukjes in een spelletje Tetris.

2. Algoritmische Injectie via Matrixoperaties:

   • Representatie: De CYK-tabelcellen $P[i, j]$ worden gerepresenteerd als gedistribueerde matrices. Grammatica-regels (bijv. $A \to BC$) worden gecodeerd als gewichtsmatrices ($W$) geconstrueerd uit de inverse en forward representaties van de niet-terminalen.
   • Holistische Update: In plaats van door lussen te itereren om de tabelcel cel voor cel te vullen (zoals in het klassieke $O(n^3)$ CYK-algoritme), formuleren de auteurs de update-stap als een enkele matrix-vectorvermenigvuldiging: $P' = PRP$. Hierbij is $P$ de huidige staat van de tabel en $R$ codeert de grammatica-regels. Deze operatie voert theoretisch de logica uit van het parallel combineren van constituenten.
   • Verfijning: Om de benaderingsfouten te mitigeren die worden geïntroduceerd door de $O(n^3)$ complexiteit te reduceren tot een enkele operatie, bevat de architectuur een Diagonale Decoder (Dd). Dit module extraheert specifieke diagonale informatie uit de gedistribueerde matrix, zuivert het signaal en voert het terug in de recurrente lus voor verfijning.

3. Architectuur (CYKNN): Het netwerk bestaat uit:

   • Holografische Encoder (He): Transformeert input-tokens naar de initiële matrix $P_0$.
   • Unaire Module (U): Past unaire grammatica-regels toe om de eerste diagonaal te initialiseren.
   • Binaire Module (B): Implementeert de kernoperatie $P_{i+1} = P_i R_B P_i$ om de propagatie van binaire regeltoepassingen uit te voeren.
   • Diagonale Decoder (Dd): Extraheert en verfijnt de symbolische inhoud uit de gedistribueerde matrix bij elke stap.

Belangrijkste Bijdragen

• Directe Algoritmische Injectie: Het artikel demonstreert een nieuwe benadering van neuro-symbolische methodologieën waarbij een complex, bekend algoritme (CYK) expliciet in de architectuur van een neuraal netwerk wordt gevormd, in plaats van impliciet te worden geleerd.
• Holistisch Redeneren via Lineaire Algebra: De auteurs tonen aan dat de iteratieve logica van dynamisch programmeren (het vullen van een parseringstabel) kan worden vertaald naar holistische matrix-vectorvermenigvuldigingen die de status van data in een enkele operatie veranderen, gebruikmakend van de eigenschappen van HRRs.
• Superieure Prestaties op Algoritmische Taken: De voorgestelde CYKNN presteert beter dan bestaande state-of-the-art LLM's op de specifieke taak van CYK-parsing, zelfs wanneer die LLM's aanzienlijk groter zijn (20B+ parameters) of zijn gefinetuned met LoRA.

Experimentele Resultaten

De auteurs evalueerden CYKNN tegen twee klassen van transformer-gebaseerde modellen:

1. Finetuned Modellen: Qwen2.5-1.5B en Qwen3-8B, gefinetuned met LoRA op de CYK-taak.
2. In-Context Learning (ICL) Modellen: gpt-oss-20B en Gemma-27B, geprompt met few-shot voorbeelden.

Bevindingen:

• Dominantie van CYKNN: CYKNN, met name wanneer het is geïnitialiseerd met de juiste grammatica-regels, behaalde aanzienlijk hogere F-measure scores dan alle vergeleken LLM's op zowel kleine (lengte 5-8) als volledige testsets.
• Beperkingen van LLM's: Gefinetuned Qwen-modellen presteerden slecht; ze slaagden er vaak niet in de algoritmische structuur te leren en memoriseerden in plaats daarvan prefix-associaties. Ze presteerden alleen beter dan een willekeurig geïnitialiseerde CYKNN bij zeer lange sequenties (>12 tokens), wat suggereert dat ze het algoritme niet induceerden. In-context learning modellen vertoonden een hoge precisie maar een lage recall, wat wijst op een conservatieve, niet-algoritmische benadering van het vullen van de tabel.
• Gevoeligheid voor Initialisatie: De prestaties van CYKNN waren sterk afhankelijk van de initialisatie van de grammatica-matrices. Willekeurige initialisatie leidde tot lagere prestaties, terwijl initialisatie met de specifieke grammatica-regels de mogelijkheid bood voor het model om te convergeren naar een hoge nauwkeurigheid.
• Generalisatie: In tegen tegenstelling tot transformers, die moeite hadden met variaties in sequentielengte, vertoonde CYKNN meer intuïtief gedrag met betrekking tot sequentielengte en behield het de prestaties, zelfs bij complexere grammatica's.

Betekenis en Claims

Het artikel beweert een weg te banen voor een andere benadering van neuro-symbolische methodologieën. De auteurs argumenteren dat als algoritmen bekend zijn, er een levensvatbaar alternatief is voor het vertrouwen op de "emergente capaciteiten" van massale transformers: het direct coderen van deze algoritmen in neurale architecturen.

De betekenis ligt in de demonstratie dat:

1. Algoritmen architecturen kunnen vormen: Neurale netwerken kunnen worden ontworpen om specifieke algoritmische logica (CYK) te belichamen via matrix-vectoroperaties, in plaats van alleen statistische patronen te leren.
2. Efficiëntie in Neuro-Symbolische Taken: Voor taken die strikte algoritmische naleving vereisen (zoals parsing), kan een gespecialiseerd, algoritmisch gevormd netwerk beter presteren dan algemene, massale schaal LLM's, zelfs die met miljarden parameters.
3. Alternatief voor "Grokking": Het paper suggereert dat voor complexe algoritmische taken, wachten tot transformers de oplossing "grokken" vanuit data inefficiënt en vaak onsuccesvol is; directe injectie van algoritmische structuur is een robuustere route.

De auteurs blijven bescheiden en erkennen dat de gebruikte grammatica eenvoudig is en de huidige implementatie niet computationeel geoptimaliseerd is, maar zij stellen dat de eenvoud van de grammatica al voldoende was om de beperkingen van huidige transformer-gebaseerde LLM's bloot te leggen.