Technische Samenvatting: Ontdekking van een Zeta-kaart Algoritme op Dyck-paden via Mechanistische Interpreteerbaarheid

Probleemstelling

Machine learning wordt steeds vaker toegepast op wiskundig onderzoek, maar er blijft een fundamentele kloof bestaan tussen hoge voorspellingsnauwkeurigheid en de generatie van expliciete, verifieerbare wiskundige constructies. In de combinatoriek is de gewenste output vaak een conjectuur, constructie of algoritme dat onafhankelijk gecontroleerd kan worden, in plaats van een numerieke benadering. Dit artikel adresseert deze kloof door te onderzoeken of instrumenten voor mechanistische interpreteerbaarheid expliciete combinatorische algoritmen kunnen extraheren uit getrainde neurale netwerken.

De specifieke testcase is de zeta-kaart ($\zeta$) op Dyck-paden, een klassieke bijectie die centraal staat in de theorie van $q,t$-Catalangetallen. De zeta-kaart wisselt de $(dinv, area)$-statistieken uit voor de $(area, bounce)$-statistieken. Hoewel de zeta-kaart goed begrepen is en verschillende bestaande algoritmische beschrijvingen toelaat (bijv. via area-sequenties of sweep maps), dient het als een ideale gecontroleerde omgeving voor AI-ondersteunde ontdekking omdat de data exact genereerbaar is, de correctheid uitputtend controleerbaar is, en het doel een discrete combinatorische procedure is.

Methodologie

1. Experimentele Opzet

De auteurs trainden transformer-modellen om de zeta-kaart op Dyck-woorden van semilengte $n$ te leren.

• Data: Gesuperviseerde datasets van Dyck-woorden en hun afbeeldingen onder de zeta-kaart (specifiek $\text{rev} \circ \zeta$, waarbij $\text{rev}$ het achterwaarts lezen van het woord en het omdraaien van 0's en 1's betekent, consistent met de gebruikte SAGEMATH-implementatie).
• Initiële Training: Standaard encoder-decoder transformers (4 lagen, 8 koppen) bereikten $>99\%$ nauwkeurigheid over diverse semlengtes ($n=11$ tot $16$).
• Compressie: Om mechanistische analyse mogelijk te maken, trainden de auteurs een Minimale Dyck Transformer: een doelbewust kleine architectuur met één encoder-laag, één decoder-laag en één attention head (embedding dimensie 128, ~340k parameters). Dit model behaalde perfecte of bijna perfecte nauwkeurigheid.

2. Mechanistische Interpreteerbaarheidsanalyse

De kern van de methodologie omvat het analyseren van de interne werking van de Minimale Dyck Transformer met behulp van drie primaire instrumenten:

• Decoder Cross-Attention Analyse: De auteurs volgden welke invoerposities de hoogste attention-gewichten ontvingen tijdens de generatie van de uitvoersequentie.
• Causale Ablatie: Ze maskeerden cross-attention naar specifieke invoerposities (bijv. opwaartse stappen waar $w_i=1$) om te testen of die posities functioneel noodzakelijk waren voor de decodering.
• Lineaire Probing: Er werden lineaire classifiers getraind op encoder hidden states om de "level" van elke positie in het Dyck-pad te voorspellen, om te testen of deze combinatorische statistiek lineair toegankelijk is in de representaties.

3. Algoritme Extractie

Op basis van de geobserveerde patronen in het minimale model formuleerden de auteurs een nieuw expliciet algoritme, de Scaffolding Map, en bewezen vervolgens de equivalentie ervan aan de zeta-kaart.

Belangrijkste Bevindingen en Bijdragen

1. Ontdekking van een Level-gebaseerd Mechanisme

De interpreteerbaarheidsanalyse onthulde dat het model de zeta-kaart niet behandelt als een willekeurige lookup table, maar de generatie organiseert via een gestructureerd, level-gebaseerd mechanisme:

• Selectie van Hoogste Level: De decoder richt zijn aandacht consequent op invoerposities met maximale levels onder de relevante posities, met name tijdens de vroege generatiestappen.
• Systematische Vermijding van Opwaartse Stappen: De decoder richt zijn aandacht zelden op posities waar $w_i=1$ (Noordelijke stappen). Causale ablatie bevestigde dat het maskeren van de aandacht naar deze posities een verwaarloosbare degradatie in nauwkeurigheid veroorzaakte, wat impliceert dat de decoder ze niet direct "leest" maar vertrouwt op geaggregeerde informatie.
• Triangular Sequential Shift: Het attention-patroon vertoont een verschuiving van een hoog-level East-stap positie ($w_i=0$) naar de volgende in aanmerking komende East-stap positie ($i+1$), wat overeenkomt met een sequentiële afname in level ($\ell_{i+1} = \ell_i - 1$).
• Lineaire Toegankelijkheid: Lineaire probes bevestigden dat de encoder-representaties de level-sequentie ($\ell_i$) van het Dyck-pad lineair toegankelijk maken (84% voorspellende nauwkeurigheid).

2. De Scaffolding Map

Het vertalen van deze signalen naar combinatoriek leidde tot de voorstel van de Scaffolding Map, een peak-gecentreerd traversaal algoritme:

• Mechanisme: Het algoritme groepeert peak-posities op basis van hun level. Het initialiseert "agents" bij deze peaks en traverseert het pad level-voor-level van boven naar beneden.
• Traversatie: Agents bewegen langs aangrenzende East-stap en niet-East-stap posities. Het uitvoerwoord wordt gegenereerd door de symbolen te lezen die de agents tegenkomen terwijl zij de "scaffold" (steiger) volgen die door de opwaartse stappen is gebouwd.
• Structuur: Het algoritme scheidt de latente ondersteunende structuur (de levels gebouwd door opwaartse stappen) van het traversatieproces dat de uitvoer genereert.

3. Theoretische Verificatie

De auteurs leverden een formeel bewijs (Theorem 6.1) dat de Scaffolding Map equivalent is aan de zeta-kaart (modulo de reversie-conventie gebruikt in de dataset).

• Bewijsstrategie: Het bewijs vergelijkt de Scaffolding Map level-voor-level met de area-sequentie beschrijving van $\text{rev} \circ \zeta$. Het demonstreert dat de subsequenties gegenereerd door het queueing mechanisme van de Scaffolding Map ($Q'_k$) exact overeenkomen met de subsequenties gegenereerd door het standaard zeta-kaart algoritme ($P_k$) wanneer de area-sequentie in reverse wordt gescand.

Betekenis en Claims

Het artikel claimt een gecontroleerd voorbeeld te bieden van AI-ondersteunde wiskundige ontdekking, waarbij mechanistische interpreteerbaarheid de modelgedraging transformeert in een precies, menselijk verifieerbaar combinatorisch algoritme.

• Nieuwigheid: Naar weten van de auteurs is dit de eerste instantie waarbij het mechanistische interpreteren van een getraind neurale sequentiemodel wordt gebruikt om een nieuwe expliciete bijectieve beschrijving van een goed bestudeerde combinatorische kaart te extraheren.
• Workflow: Het artikel articuleert een workflow waarbij:
  1. Het model recurrente structurele signalen levert (attention patronen, lineaire probes).
  2. Menselijke onderzoekers deze signalen interpreteren als combinatorische operaties.
  3. Interventies (ablaties) de causale relevantie testen.
  4. De resulterende procedure een wiskundig object wordt (de Scaffolding Map) dat onafhankelijk van het neurale netwerk kan worden geformuleerd en bewezen.
• Beperkingen: De auteurs zijn bescheiden over de reikwijdte en merken op dat:
  • Attention patronen alleen geen bewijs zijn; de combinatie met ablatie en formeel bewijs is essentieel.
  • Het geleerde mechanisme in de transformer een "fuzzy" versie van het algoritme lijkt te zijn (gezien de imperfecte probing resultaten), wat suggereert dat grotere of anders getrainde modellen complexere of "schonere" mechanismen kunnen implementeren.
  • De Scaffolding Map werd geëxtraheerd uit een specifiek eenvoudig model; grotere modellen kunnen andere interne oplossingen implementeren.

Het artikel concludeert dat hoewel de specifieke details van deze ontdekking mogelijk niet direct overdraagbaar zijn naar alle wiskundige problemen, het concept van het gebruik van mechanistische interpreteerbaarheid om de kloof tussen black-box voorspelling en expliciete combinatorische constructie te overbruggen, breed toepasbaar is binnen het combinatorisch onderzoek.