Functorial Neural Architectures from Higher Inductive Types

Die Arbeit zeigt, dass das Scheitern neuronaler Netze an der kompositorischen Generalisierung auf einem fehlenden Funktorialitätsprinzip beruht, und stellt einen neuen Architekturbaukasten vor, der Higher Inductive Types in strikt funktoriale Decoder übersetzt, um durch strukturelle Verkettung und gelernte natürliche Transformationen signifikant bessere Generalisierungsergebnisse auf topologischen Räumen wie dem Torus oder der Kleinschen Flasche zu erzielen.

Das Wesentliche

Das Problem: Warum KI beim „Zusammensetzen" scheitert

Stellen Sie sich vor, Sie haben einem Roboter beigebracht, wie man einen einzelnen Stuhl um ein Hindernis herumführt. Wenn Sie ihm nun sagen, er soll zwei Stühle um zwei Hindernisse führen, sollte er das einfach tun, indem er den ersten Plan macht und dann den zweiten Plan anhängt. Das ist für uns Menschen logisch: Komposition. Wir bauen Neues aus Bekanntem zusammen.

Neuronale Netze (die „Gehirne" moderner KI) scheitern daran jedoch regelmäßig. Sie können zwar das Einzelne lernen, aber wenn man die Teile neu kombiniert, geraten sie in Panik oder liefern Unsinn. Es ist, als würde ein Kind, das „Apfel" und „Baum" kennt, bei „Apfelbaum" denken, dass es sich um einen Baum aus Äpfeln handelt, statt um einen Baum, auf dem Äpfel wachsen.

Die Autoren dieser Studie sagen: Das liegt nicht daran, dass die KI nicht intelligent genug ist. Das Problem liegt im Bauplan (der Architektur). Die KI ist so gebaut, dass sie nicht wirklich „zusammensetzen" kann.

Die Lösung: Ein neuer Bauplan aus der Mathematik

Die Autoren haben eine neue Art von KI-Architektur entwickelt, die auf einem sehr abstrakten mathematischen Konzept namens Higher Inductive Types (HITs) basiert. Aber keine Sorge, wir übersetzen das in Alltagssprache:

Stellen Sie sich vor, Sie wollen eine KI bauen, die komplexe Pfade zeichnet.

1. Die alten KIs (wie Transformers/Attention): Diese schauen sich den ganzen Satz oder Pfad auf einmal an. Sie versuchen, durch „Aufmerksamkeit" (Attention) alle Wörter miteinander zu verknüpfen. Das Problem: Wenn Sie einen neuen Satz bilden, vermischt die KI die alten Muster mit den neuen auf eine Weise, die die Logik der Kombination zerstört. Es ist wie ein Koch, der versucht, ein neues Gericht zu kochen, indem er alle Zutaten in einen Topf wirft und rührt, anstatt sie nacheinander hinzuzufügen.
2. Die neue KI (Functorial): Diese KI baut den Pfad Stück für Stück.
   • Sie hat kleine, spezialisierte Werkzeuge für jeden einzelnen Schritt (z. B. „einen Kreis drehen" oder „geradeaus gehen").
   • Wenn sie einen langen Weg bauen soll, nimmt sie einfach das Werkzeug für Schritt 1, dann das für Schritt 2, und klebt sie mechanisch zusammen.
   • Der Clou: Da sie die Teile nicht neu erfindet, sondern nur zusammenklebt, funktioniert das Ergebnis immer korrekt, egal wie lang der Weg ist. Sie kann einen Weg mit 100 Schritten genauso gut planen wie einen mit 2 Schritten.

Die drei Experimente: Von der flachen Ebene zum Kaffeebecher

Die Autoren haben ihre neue KI an drei verschiedenen „Welten" getestet, die immer schwieriger werden:

1. Der Torus (ein Donut):

   • Die Aufgabe: Pfade auf einem Donut zeichnen. Hier sind die Regeln einfach (Reihenfolge ist egal: Links dann Rechts ist das Gleiche wie Rechts dann Links).
   • Das Ergebnis: Die neue KI war 2- bis 3-mal besser als die alten KIs. Sie hat die Pfade sauber gezeichnet, während die alten KIs anfingen zu wackeln, je länger der Weg wurde.

2. Der „S1 ∨ S1" (zwei Kreise, die sich berühren):

   • Die Aufgabe: Hier ist die Reihenfolge wichtig! Erst Kreis A, dann Kreis B ist etwas anderes als erst B, dann A.
   • Das Ergebnis: Hier brach die alte KI komplett zusammen. Sie verlor die Orientierung und zeichnete wirre Linien. Die neue KI hingegen war 5- bis 10-mal besser. Sie behielt die Struktur perfekt bei, weil sie die Teile mechanisch aneinanderreihte, statt sie zu vermischt.

3. Der Klein-Flaschen-Hals (Kleinsche Flasche):

   • Die Aufgabe: Dies ist die schwierigste Welt. Hier gibt es eine spezielle Regel: Wenn man einen bestimmten Weg geht, dreht sich die Welt um (wie bei einem Kaffeebecher, der sich im Inneren mit dem Äußeren verbindet).
   • Das Ergebnis: Die neue KI hatte einen zusätzlichen „Zaubertrick" eingebaut (ein mathematisches Beweisstück, das sie lernte). Dank dieses Tricks konnte sie die Drehung der Welt korrekt vorhersagen. Ohne diesen Trick hätte sie den Fehler gemacht, dass sie die Orientierung verliert. Die neue KI schloss eine Fehlerlücke von 46 %.

Warum ist das wichtig?

Die Autoren beweisen mathematisch (sogar mit Computer-Programmen, die die Beweise selbst überprüfen!), dass die alte Methode (Attention) niemals perfekt zusammensetzen kann. Sie ist wie ein Werkzeug, das für das falsche Job gebaut wurde.

Die neue Methode hingegen garantiert, dass die KI die Regeln der Welt einhält, bevor sie überhaupt lernt. Es ist wie der Unterschied zwischen:

• Lernen durch Ausprobieren: „Vielleicht klappt es, wenn ich die Zutaten nochmal mische." (Oft falsch).
• Lernen durch Konstruktion: „Ich baue ein Haus aus Ziegeln. Wenn ich einen Ziegel auf den anderen lege, steht das Haus, egal wie hoch es wird." (Immer richtig).

Fazit für den Alltag

Diese Forschung zeigt uns, dass wir KI nicht nur mit mehr Daten und mehr Rechenkraft verbessern müssen. Wir müssen sie besser bauen. Wenn wir KI-Systeme für Aufgaben brauchen, bei denen Logik und Kombination wichtig sind (z. B. Roboter, die komplexe Pläne ausführen, oder Software, die Code schreibt), sollten wir Architekturen verwenden, die das „Zusammensetzen" von Grund auf garantieren.

Die Botschaft ist einfach: Wenn Sie eine KI bauen wollen, die Dinge verstehen und kombinieren kann, bauen Sie sie so, dass sie die Teile einfach aneinanderklebt – und nicht so, dass sie versucht, alles auf einmal zu erraten.

Technische Zusammenfassung

1. Problemstellung: Das Versagen bei der kompositionellen Generalisierung

Neuronale Netze scheitern systematisch an der kompositionellen Generalisierung: Sie können korrekte Ausgaben für neue Kombinationen bekannter Teile nicht zuverlässig generieren, auch wenn sie die einzelnen Teile beherrschen. Beispiele hierfür sind das Lösen von 5-stelligen Zahlen, wenn nur 2-stellige gelernt wurden, oder das Navigieren um mehrere Hindernisse nach dem Lernen einzelner Hindernisse.

Die Arbeit argumentiert, dass dieses Versagen nicht auf mangelnde Kapazität (Größe des Modells) zurückzuführen ist, sondern ein architektonisches Problem darstellt. Standardarchitekturen, insbesondere solche mit Softmax-Self-Attention (Transformer), verletzen die strukturellen Anforderungen der Kompositionalität.

2. Methodik: Von Higher Inductive Types (HITs) zu neuronalen Architekturen

Der Kern der Arbeit ist die Formulierung, dass kompositionelle Semantik äquivalent zur Funktorialität eines Decoders ist. Das bedeutet, der Decoder $D$ muss ein monoidaler Funktor sein:
$$D(w_1 \cdot w_2) = D(w_1) \oplus D(w_2)$$
wobei $\cdot$ die Konkatenation von Eingabe-Wörtern und $\oplus$ die strukturelle Kombination der Ausgaben ist.

Um dies zu realisieren, schlägt der Autor einen Kompilierungsprozess vor, der mathematische Spezifikationen direkt in neuronale Architekturen übersetzt:

• Spezifikation durch Higher Inductive Types (HITs): Aufgaben werden als topologische Räume definiert, die durch Generatoren (Punkte, Schleifen) und Relationen (2-Zellen/Homotopien) beschrieben werden. Beispiele sind der Torus ($T^2$, abelsch), der Keil von Kreisen ($S^1 \vee S^1$, freie Gruppe) und die Kleinsche Flasche ($K$, nicht-abelsche Relation).
• Kompilierungsfunktor: Ein mathematischer Funktor übersetzt die HIT-Konstrukte in neuronale Komponenten:
  1. Generatoren werden zu unabhängigen neuronalen Netzwerken (MLPs), die Schleifenabschnitte erzeugen.
  2. Komposition wird durch strukturelle Konkatenation (Listen-Anhängen) der Ausgaben dieser Netzwerke realisiert.
  3. 2-Zellen (Relationen) werden zu gelernten Homotopien (zusätzlichen MLPs), die kontinuierliche Deformationen zwischen Schleifen abbilden.
• Architekturen-Typen:
  • Typ-B (Funktional): Der Decoder komponiert unabhängig generierte Segmente strukturell. Dies garantiert die Funktionalität per Konstruktion.
  • Typ-A (Nicht-funktional): Der Decoder erlaubt Informationsfluss zwischen Segmenten (z. B. durch Attention).

3. Theoretische Ergebnisse und Unmöglichkeitssätze

Die Arbeit liefert formale Beweise (in Cubical Agda verifiziert), die fundamentale Grenzen aufzeigen:

• Transport-Decoders sind strikte monoidale Funktoren: Decoders, die Segmente unabhängig generieren und strukturell verketten, erfüllen die Kompositionsbedingung exakt für alle Parameterwerte und Wortlängen (Theorem 3.3).
• Attention ist nicht funktional: Es wird bewiesen (Theorem 4.1), dass Softmax-Self-Attention für keine Parameterkonfiguration ein monoidaler Funktor sein kann. Da Attention auf Token-Inhalten basiert und nicht auf Äquivalenzklassen, unterscheidet sie Wörter, die im zugrunde liegenden algebraischen System identisch sein sollten (z. B. $ab$ vs. $ba$ in abelschen Gruppen), und bricht somit die Kompositionalität.
• Tiefe-Obstruktion: Für nicht-solvable Gruppen (wie die freie Gruppe $F_2$) scheitern Transformer zusätzlich an der benötigten Rechen Tiefe ($\Omega(\log n)$), die durch feste Schichtanzahlen nicht erreicht werden kann.

4. Experimentelle Validierung

Die Theorie wurde an drei topologischen Räumen getestet, die verschiedene Ebenen der Komplexität abdecken:

1. Torus ($T^2$, $\pi_1 = \mathbb{Z}^2$):

   • Ergebnis: Funktional (Typ-B) Decoder übertrafen nicht-funktionale (Typ-A) um den Faktor 2–2,7×.
   • Bedeutung: Selbst bei abelschen Gruppen, wo Zählen ausreicht, führt die strukturelle Komposition zu besserer Generalisierung.

2. Keil von Kreisen ($S^1 \vee S^1$, $\pi_1 = F_2$):

   • Ergebnis: Der Leistungsabfall bei Typ-A Architekturen war drastisch (Faktor 5,5–10×). Transformer und sequentielle Modelle (GRU) verloren die topologische Struktur (sie konnten nicht mehr unterscheiden, welcher Kreis gemeint war), während der Transport-Decoder 100% Genauigkeit beibehielt.
   • Bedeutung: Nicht-Abelsche Strukturen verstärken das Versagen von Attention-basierten Modellen massiv.

3. Kleinsche Flasche ($K$, $\pi_1 = \mathbb{Z} \rtimes \mathbb{Z}$):

   • Ergebnis: Hier wurde die Rolle der gelernten 2-Zelle (Proof Term $H$) getestet. Bei Wörtern, die die nicht-triviale Relation ($bab^{-1} = a^{-1}$) ausnutzen, reduzierte der Homotopie-Decoder (Typ-B mit $H$) den Fehler um 46% im Vergleich zum reinen Transport-Decoder.
   • Bedeutung: Dies ist der erste Nachweis, dass ein neuronales Netz eine natürliche Transformation (Beweisglied) lernen kann, um algebraische Relationen topologisch korrekt zu handhaben.

5. Wichtige Beiträge

1. Kompilierungsfunktor: Ein systematischer Weg, um HIT-Spezifikationen direkt in neuronale Architekturen zu übersetzen, wobei die algebraische Struktur der Aufgabe die Architektur bestimmt.
2. Formale Garantie: Die erste Anwendung von verifiziertem Machine Learning, bei der die Kompositionsgarantie durch den Architekturentwurf (nicht durch Training) für alle Parameterwerte gilt.
3. Impossibility Result: Der Beweis, dass Softmax-Attention inhärent nicht kompositionell ist, was eine theoretische Erklärung für das Scheitern von Transformern bei Aufgaben wie SCAN, COGS und CFQ liefert.
4. Typ-A vs. Typ-B Klassifikation: Eine klare Unterscheidung zwischen Architekturen, die durch strukturelle Zerlegung kompositionell sind, und solchen, die dies durch Lernen versuchen (und scheitern).

6. Bedeutung und Ausblick

Die Arbeit verschiebt das Paradigma von der Frage „Kann das Netzwerk Kompositionalität lernen?" zu „Garantiert die Architektur Funktionalität?". Sie zeigt, dass für Aufgaben mit klarer kompositioneller Struktur (z. B. Robotik-Planung, modulare Programmierung, chemische Ringstrukturen) Attention-basierte Modelle prinzipiell ungeeignet sind.

Der vorgeschlagene Workflow „Specify – Verify – Compile – Train" (Spezifikation in HoTT, Verifikation in Cubical Agda, Kompilierung, Training) bietet einen Weg zu zertifizierten neuronalen Netzen. Die Ergebnisse deuten darauf hin, dass zukünftige Architekturen für komplexe, strukturierte Probleme nicht auf reine Datenmenge setzen sollten, sondern auf eine korrekte, kategorientheoretisch fundierte Architektur.