🤖 machine learning

Variational Learning for Insertion-based Generation

Dieses Paper führt den Insertion Process (IP) ein, ein variatorisches Lernframework, das die Generierung von variablen, nicht-monotonen Sequenzen durch das Erlernen datengesteuerter Einfügeordnungen mittels einer bijektiven Korrespondenz zwischen Einfüge-Trajektorien und Permutationen ermöglicht und dadurch die Modellierungsqualität sowie die Generalisierung in Domänen verbessert, denen eine kanonische Links-Rechts-Struktur fehlt.

Ursprüngliche Autoren: Yangtian Zhang, Zhe Wang, Arthur Gretton, Rex Ying, David van Dijk, Michalis K. Titsias, Jiaxin Shi

Veröffentlicht 2026-06-02

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Yangtian Zhang, Zhe Wang, Arthur Gretton, Rex Ying, David van Dijk, Michalis K. Titsias, Jiaxin Shi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, eine komplexe Lego-Burg zu bauen.

Der alte Weg (Autoregressive Modelle):
Die meisten KI-Modelle von heute bauen wie eine strikte Baustelle, die nur von links nach rechts arbeitet. Sie legen den ersten Stein, dann den zweiten, dann den dritten und so weiter. Wenn sie auf halbem Weg merken, dass sie einen Turm in der Mitte der Mauer benötigen, können sie nicht einfach einen Stein dort hineinsetzen. Sie müssen alles abreißen und von vorne beginnen oder versuchen, den Turm unbeholfen oben auf die bestehende Mauer zu setzen, was oft zu einem wackeligen, instabilen Durcheinander führt. Das funktioniert gut für einfache Sätze, aber es bereitet Probleme bei komplexen Strukturen, bei denen die „Mitte“ von dem „Ende“ abhängt.

Das Problem mit aktuellen „flexiblen“ Modellen:
Wissenschaftler haben versucht, dies mit „Masked Diffusion“-Modellen zu beheben. Stellen Sie sich diese als eine Crew vor, die mit einer vorab festgelegten Anzahl an leeren Lego-Plätzen (einem festen Raster) beginnt und diese zufällig auffüllt.

Der Fehler 1: Sie sind an eine feste Anzahl von Plätzen gebunden. Wenn Sie ein winziges Haus oder einen riesigen Wolkenkratzer wollen, müssen Sie die Größe im Voraus erraten.
Der Fehler 2: Es ist ihnen egal, wann sie einen Platz auffüllen. Sie könnten das Dach füllen, bevor das Fundament steht, oder den Schornstein vor den Wänden. Während dies flexibel ist, ist es ineffizient, weil die KI lernen muss, mit jeder möglichen Reihenfolge des Bauens konsistent zu sein, was eine massive, verwirrende Aufgabe ist.

Die neue Lösung: Der „Insertion Process“ (Einfügeprozess)
Die Autoren dieser Arbeit führen eine neue Art des Bauens ein, die den Insertion Process nennt. Stellen Sie sich einen Meisterbaumeister vor, der keinem festen Raster oder einer Links-nach-rechts-Regel folgt. Stattdessen besitzt er die magische Fähigkeit:

Die halbfertige Struktur zu betrachten.
Genau zu entscheiden, wo er das nächste Teil einfügen wird (z. B. „Ich setze dieses Fenster genau in die Mitte der Wand“).
Zu entscheiden, welches Teil er dort einsetzt.
Zu entscheiden, wann er aufhört (z. B. „Die Burg ist fertig, keine weiteren Steine mehr nötig“).

Dieses Modell lernt, in der für die spezifische Aufgabe besten Reihenfolge zu bauen, anstatt eine starre Reihenfolge vorzugeben.

Wie sie es zum Laufen brachten (Der „magische Trick“)
Der schwierige Teil war, der KI mathematisch beizubringen, diese „beste Reihenfolge“ zu lernen. Wenn man versucht, es ihr beizubringen, indem man sie raten lässt, an welchen Einfügestellen sie arbeiten soll, wird die Mathematik unordentlich und instabil.

Die Autoren entdeckten einen cleveren mathematischen Shortcut. Sie erkannten, dass jede mögliche Art, eine Sequenz aufzubauen, eigentlich nur eine andere Art ist, dieselben fertigen Teile zu ordnen.

Analogie: Stellen Sie sich vor, Sie haben ein Kartendeck. Egal, ob Sie die Karten einzeln von oben nach unten ausgeben oder sie mischen und in einem seltsamen Muster ausgeben, die fertige Hand bleibt dieselbe. Der „Insertion Process“ übersetzt den unordentlichen Akt des „Einfügens in einen wachsenden Haufen“ in eine saubere, organisierte „Permutation“ (eine spezifische Anordnung) der fertigen Karten.
Durch diese Übersetzung konnten sie eine Standardmethode der effizienten Ausbildung (Variational Inference) nutzen, um der KI beizubringen, welche Ordnung für die gesehenen Daten am besten ist.

Was sie damit getestet haben
Die Autoren testeten diesen neuen Baumeister an zwei spezifischen Herausforderungen, bei denen die „Links-nach-rechts“-Regel keinen Sinn ergibt:

Einen Pfad planen (Labyrinthe):
- Die Aufgabe: Die KI musste einen Pfad durch ein Labyrinth planen, der bestimmte Checkpoints besucht.
- Das Ergebnis: Die alten „Links-nach-rechts“-Baumeister blieben stecken, weil sie nicht leicht wieder zurückspringen konnten, um eine Lücke im Pfad zu schließen. Der neue Insertion Process konnte herumspringen und die Lücken zwischen den Checkpoints perfekt schließen. Er löste fast 100 % der schwierigsten Labyrinthe, während die alten Methoden kläglich scheiterten.
Moleküle entwerfen (Chemie):
- Die Aufgabe: Die KI sollte gültige chemische Strings (SMILES) generieren. Diese Strings sind wie eine Landkarte eines Moleküls. Eine gültige Karte benötigt passende Klammern (wie öffnende und schließende Ringe) und Zahlen, um entfernte Teile zu verbinden.
- Das Ergebnis: Das neue Modell lernte eine „schlaue“ Art des Bauens. Es hat nicht einfach Atome zufällig hinzugefügt. Es lernte, zuerst das „Skelett“ (die Ringe und Verbindungen) zu bauen und dann die Atome einzufüllen.
- Warum es wichtig ist: Dies ermöglichte es der KI, viel besser gültige, einzigartige und neuartige Moleküle zu erstellen, als Modelle, die einfach nur Teile am Ende anhängen. Sie lernte die „Grammatik“ der Chemie, ohne dass ihr die Regeln explizit erklärt werden mussten.

Das Fazsit
Diese Arbeit präsentiert eine neue Art für KI, Sequenzen (wie Text, Pläne oder chemische Formeln) zu generieren, die nicht eine starre „Anfang-zu-Ende“-Reihenfolge erzwingt. Stattdessen lernt sie, Teile genau dort einzufügen, wo sie gebraucht werden, und dann, wenn sie gebraucht werden. Durch einen cleveren mathematischen Trick, der „Einfügen“ in „Anordnung“ übersetzt, trainierten sie ein Modell, das komplexere Aufgaben mit variabler Länge besser bewältigen kann als bisherige Methoden.

Technisches Resümee: Variationales Lernen für die insertionsbasierte Generierung

1. Problemstellung

Autoregressive Sequenzmodelle generieren Token typischerweise in einer festen Links-Rechts-Reihenfolge. Obwohl dies für viele Aufgaben effektiv ist, ist diese Faktorisierung nicht inhärent für alle Datenstrukturen und kann mit realen Generierungsproblemen wie dem Design biologischer Sequenzen, der Programmsynthese oder der strukturierten Planung nicht im Einklang stehen, bei denen Teile der Ausgabe von zukünftigem Kontext abhängen können.

Existierende Alternativen, wie etwa maskierte Diffusionsmodelle (nicht-monotone Generierung), bieten Flexibilität, indem sie Teilmengen maskierter Positionen auf einem festen Gitter aktualisieren. Diese Ansätze leiden jedoch unter zwei primären Einschränkungen:

Statisches Canvas: Sie operieren auf vorgegebenen, festen Gittern, was externe Längenangaben erfordert und die Generierung variabler Längen indirekt macht.
Ordnungsagnostik: Ihre Trainingsziele marginalisieren oft über oder setzen implizit viele mögliche Aktualisierungszeitpläne voraus. Dies zwingt das Modell dazu, Konditionals für eine faktoriell hohe Anzahl von Generierungsordnungen zu approximieren, selbst wenn nur ein kleiner Teil davon mit der zugrunde liegenden Struktur der Daten übereinstimmt.

Neuere Arbeiten haben diese Probleme isoliert adressiert: Insertionsbasierte Modelle ermöglichen variable Sequenzlängen durch beliebige Einfügungen, während Methoden zum Lernen der Ordnung Verteilungen über Permutationen einführen. Die Kombination dieser Ansätze ist jedoch nicht trivial, da in Insertionsmodellen die Einfügestellen keine festen Koordinaten sind, sondern sich mit der Teilsequenz entwickeln, was die Generierungsordnung eng mit den Zwischenzuständen koppelt.

2. Methodik: Der Insertionsprozess (IP)

Die Autoren schlagen den Insertion Process (IP) vor, einen probabilistischen Rahmen, der gemeinsam lernt:

Wo einzufügen ist: Eine datengesteuerte Präferenz über Insertionsentscheidungen (Slot-Selektion).
Was einzufügen ist: Eine Token-Verteilung.
Wann abzubrechen ist: Eine Stopp-Regel (policy-basiert oder klassifikator-basiert).

2.1. Reparametrisierung via Permutationen

Ein zentraler theoretischer Beitrag ist die Formalisierung einer bijektiven Korrespondenz zwischen Insertions-Trajektorien und Permutationen der Zielsequenz-Indizes.

Die Herausforderung: Direkte variationale Inferenz über Insertions-Trajektorien ist schwierig, da relative Slot-Indizes ( $z_i$ ) trajektorienabhängig sind, was es schwierig macht, eine stabile Posterior-Verteilung über die Ordnung im Raum relativer Aktionen zu definieren.
Die Lösung: Die Autoren bilden jede gültige Insertions-Trajektorie, die eine Sequenz $y_L$ erzeugt, auf eine eindeutige Permutation $\sigma \in S_L$ ab, wobei $\sigma_i$ der Index des zum Schritt $i$ ausgefüllten Elements ist.
Deterministische Abbildung: Der relative Insertions-Slot zum Schritt $i$ wird zu einer deterministischen Funktion der Permutations-Präfix-Struktur ( $\sigma_{\le i}$ ). Konkret gilt: $z_i = 1 + |\{j \in \sigma_{<i} : j < \sigma_i\}|$ .
Likelihood-Faktorisierung: Diese Änderung der Variablen wandelt die Marginalisierung über trajektorienabhängige Aktionen in eine exakte Summe über Permutationen um, was eine exakte Reparametrisierung der Daten-Likelihood ermöglicht:
$p(y_L) = \sum_{\sigma \in S_L} p(y_L, \sigma)$

2.2. Variationale Inferenz und Training

Um das Modell zu trainieren, maximieren die Autoren eine Evidence Lower Bound (ELBO) auf die Log-Likelihood der Daten, wobei die Generierungsordnung (Permutation $\sigma$ ) als latente Variable behandelt wird.

Variationale Posterior: Sie führen eine amortisierte variationale Posterior $q_\theta(\sigma | y_L)$ ein, die als Plackett-Luce (PL) Modell parametrisiert ist.
Optimierung: Da die latente Ordnung diskret ist, ist das Ziel nicht differenzierbar. Die Autoren optimieren die ELBO mittels:
- Gumbel-Top-k Trick: Um Permutationen effizient aus der PL-Verteilung zu sampeln.
- REINFORCE mit Leave-One-Out (RLOO): Um Gradienten zu schätzen.
- Varianzreduktion: Durch Ausnutzung der Permutations-Trajektorien-Struktur wird die innere Erwartung über den nächsten Index $\sigma_i$ (bedingt auf einem fixen Präfix) exakt in geschlossener Form ausgewertet, was die Varianz des Monte-Carlo-Schätzers reduziert.

2.3. Netzwerkarchitektur

Generativer Decoder: Ein Transformer-basierter Decoder verarbeitet die Teilsequenz (ergänzt durch Boundary-Token), um kontextuelle Embeddings zu erzeugen.
- Ein Location Head bewertet Kandidaten-Insertions-Slots (einschließlich einer Terminierungsaktion) basierend auf den Embeddings.
- Ein Content Head sagt die Token-Verteilung bedingt auf den ausgewählten Slot voraus.
Inferenz-Encoder: Ein bidirektionaler Transformer-Encoder verarbeitet die vollständige beobachtete Sequenz, um Scores für jeden globalen Index auszugeben, welche die Plackett-Luce-Verteilung für das Sampling der Generierungsordnung parametrisieren.

3. Kernbeiträge

Probabilistischer Rahmen für variable Längen bei der Insertion: Das erste Framework, das die Insertionsreihenfolge für Sequenzen variabler Länge durch eine bijektive Abbildung auf Permutationen lernt, was eine exakte Likelihood-Reparametrisierung ermöglicht.
Permutations-marginalisierte Likelihood: Eine theoretische Herleitung, die zeigt, dass die Daten-Likelihood als Summe über Permutationen ausgedrückt werden kann, was die variationale Inferenz mit einer latenten Ordnungs-Variablen erleichtert.
Effizienter Trainingsalgorithmus: Eine varianzreduzierte Trainingsmethode unter Verwendung von Plackett-Luce-Modellen, Gumbel-Top-k-Sampling und RLOO-Gradienten, um die diskrete, nicht differenzierbare Natur der latenten Ordnung zu handhaben.
Nativität für variable Längen: Im Gegensatz zu Fixed-Canvas-Diffusionsmodellen unterstützt IP nativ die Generierung variabler Längen und lernt datengesteuerte Präferenzen für Insertionsordnungen.

4. Experimentelle Ergebnisse

Die Autoren evaluierten IP in zwei Domänen: zielgerichtete Planung (goal-conditioned planning) und molekulare String-Generierung.

4.1. Zielgerichtete Planung (Goal-Conditioned Planning)

Benchmarks: Maze-Planung (Braided, Imperfect, Perfect) und Star-Graph-Planung.
Baselines: Fixed-Order ARMs (FO-ARM), Any-Order ARMs (AO-ARM), Masked Diffusion Models (MDM) und Learning-Order ARMs (LO-ARM).
Ergebnisse: IP erreichte eine State-of-the-Art-Performance über alle Maze-Familien und Graph-Benchmarks hinweg.
- Bei Perfect Mazes (hochgradig eingeschränkt) verschlechterten sich FO-ARMs signifikant, während IP eine nahezu perfekte Genauigkeit beibehielt (z. B. 99,9 % bei Hard Perfect Mazes gegenüber 27,2 % bei FO-ARM).
- IP verbesserte die Sequenz- und Token-Genauigkeit sowie die Edit-Distanzen im Vergleich zu allen Baselines erheblich, was zeigt, dass das Lernen instanzspezifischer Insertionsordnungen für Aufgaben mit weitreichenden Constraints entscheidend ist.

4.2. Molekulare String-Generierung (SMILES)

Benchmark: GuacaMol unbedingte und bedingte Generierung.
Ergebnisse:
- Validität & Neuheit: IP erreichte eine hohe Validität (97,2–97,4 %) und die höchste Neuheit (~95 %) unter allen Modellen, was die Random-Order-Insertion (AO-IP) mit 88,2 % Validität deutlich übertrifft. Dies deutet darauf hin, dass IP chemische Syntaxregeln erfolgreich internalisiert.
- Distributionale Metriken: Während FO-ARMs auf distributional similarity (KL-Divergenz, FCD) leicht besser abschnitten, bot IP einen überlegenen Trade-off, indem es den chemischen Raum effektiver explorierte.
- Bedingte Generierung: In Aufgaben, die die Insertion zwischen fixen Fragmenten erfordern (z. B. Linker-Design), behielt IP eine Validität von ~100 %, während Fixed-Order-Modelle mit solchen Constraints kämpfen.
Interpretierbarkeit: Eine Analyse der gelernten Insertions-Schedules offenbarte eine interpretierbare, konsistente Generierungsordnung: (1) Aufbau des molekularen Skeletts (Ringe/Klammern), (2) Insertion von Atomen und (3) Terminierung. Dies geschah ohne explizite grammatikalische Priors.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass das Lernen datenabhängiger Insertionsordnungen die Modellqualität und Generalisierung in Domänen signifikant verbessert, die keine kanonische Links-Rechts-Struktur besitzen. Durch die Formalisierung der Verbindung zwischen Insertions-Trajektorien und Permutationen bietet die Arbeit eine handhabbare, unverzerrte (unbiased) variationale Methode für das Training von Insertionsmodellen.

Die Autoren positionieren ihre Arbeit als Schritt in Richtung generativer Modellierung in Domänen, in denen die „natürliche“ Generierungsordnung mehrdeutig oder nicht-linear ist. Sie geben explizit an, dass zukünftige Arbeiten diese Methode auf andere Bereiche wie das Proteindesign anwenden könnten. Das Paper wahrt einen bescheidenen Ton und stellt fest, dass IP zwar die Generalisierung und Validität in komplexen strukturellen Aufgaben verbessert, aber nicht zwangsläufig Fixed-Order-Modelle bei einfachen Metriken der Distributionstreue übertrifft, was den Trade-off zwischen Flexibilität und strikter dimensionaler Treue verdeutlicht.