Transformers Can Learn Connectivity in Some Graphs but Not Others

Probleemstelling

Het vermogen tot redeneren is cruciaal voor de feitelijke juistheid van antwoorden van Transformer-gebaseerde Large Language Models (LLMs). Een specifiek en fundamenteel aspect hiervan is het redeneren over transitieve relaties (bijvoorbeeld: als A leidt tot B en B leidt tot C, dan leidt A tot C). Dit probleem is wiskundig equivalent aan het bepalen van connectiviteit in gerichte grafen (het bestaan van een pad van knoop A naar knoop C via B).

Hoewel eerdere studies zich hebben gericht op het vermogen van Transformers om transitiviteit te leren uit in-context voorbeelden (prompting), blijft de vraag onbeantwoord of en hoe Transformers transitiviteit kunnen leren uit trainingsvoorbeelden (supervised learning) en hoe scaling (het vergroten van het model) dit vermogen beïnvloedt.

Methodologie

De auteurs hebben een experimenteel kader opgezet om deze vragen te onderzoeken:

1. Datageneratie: Er zijn gecontroleerde gerichte grafen gegenereerd om Transformer-modellen te trainen.
2. Modelvariatie: Er zijn modellen van verschillende groottes (schalen) getraind om het effect van modelcapaciteit te evalueren.
3. Grafenvariëteit: De studie onderscheidt twee hoofdtypes grafen:
   • "Grid-achtige" grafen: Grafen waarbij knopen in een laag-dimensionale deelruimte kunnen worden ingebed en connectiviteit eenvoudig uit deze embeddings kan worden afgeleid.
   • Niet-grid grafen: Grafen met veel losgekoppelde componenten (disconnected components) die geen regelmatige structuur hebben.
4. Evaluatie: De modellen werden getest op hun vermogen om connectiviteit af te leiden voor grafen van verschillende groottes, met name om te zien of ze kunnen generaliseren naar grotere grafen dan die tijdens het trainen zijn gezien.

Belangrijkste Bijdragen en Resultaten

De studie levert de volgende kernbevindingen:

• Lerbaarheid van Grid-achtige Grafen: Transformers zijn wel degelijk in staat om connectiviteit te leren op "grid-achtige" gerichte grafen. Dit komt doordat de structuur van deze grafen toelaat dat knopen worden ingebed in een laag-dimensionale deelruimte, waardoor de connectiviteit lineair of eenvoudig voorspelbaar is vanuit de knooprepresentaties.
• Invloed van Dimensie: De dimensie van de onderliggende grid is een sterke voorspeller voor het leervermogen.
  • Lage dimensie: Modellen leren de taak effectief.
  • Hoge dimensie: Hoe hoger de dimensie van de grid, hoe moeilijker het is voor de Transformer om de connectiviteit te leren.
• Effect van Scaling: Er is een duidelijke positieve correlatie gevonden tussen modelgrootte en generalisatie. Het vergroten van de schaal van het model leidt tot een betere generalisatie bij het afleiden van connectiviteit over grid-achtige grafen.
• Beperkingen bij Niet-Grid Grafen: Wanneer de grafen geen grid-structuur hebben en bestaan uit vele losgekoppelde componenten, worstelen Transformers om de connectiviteitstaak te leren. Dit probleem verergert naarmate het aantal losgekoppelde componenten toeneemt. In deze scenario's faalt het model vaak in het generaliseren van de transitieve relatie.

Significantie en Implicaties

Deze bevindingen hebben belangrijke implicaties voor het begrijpen van de redeneercapaciteiten van LLMs:

1. Structuur is Bepalend: Het vermogen van Transformers om logische transitiviteit te redeneren is niet universeel; het is sterk afhankelijk van de onderliggende structuur van de data. Modellen gedijen bij gestructureerde, laag-dimensionale patronen, maar falen bij chaotische of sterk gefragmenteerde structuren.
2. Schalingswetten: De studie bevestigt dat grotere modellen beter kunnen generaliseren, maar alleen binnen de grenzen van de leerbaarheid van de specifieke grafenstructuur.
3. Toekomstige Richtingen: Voor toepassingen zoals causale inferentie, waar transitive relaties cruciaal zijn, suggereert dit dat de representatie van kennis in de data (bijv. het vermijden van te veel losgekoppelde componenten of het gebruik van structuur die zich laat inbedden) essentieel is voor het succes van Transformer-modellen.

Samenvattend toont het paper aan dat Transformers transitiviteit kunnen leren, maar dat dit vermogen beperkt is tot grafen met een specifieke, goed-embedbare structuur en dat de complexiteit van die structuur (dimensie en connectiviteit) de prestaties direct beïnvloedt.