Programmsynthese

Programmsynthese bezeichnet die automatische Erzeugung eines Programms aus einer Spezifikation dessen, was es leisten soll – etwa aus Beispielen von Ein- und Ausgaben, aus formalen Bedingungen oder aus einer natürlichsprachlichen Beschreibung. In der AGI-Debatte gilt sie als Entwicklungspfad, der die Generalisierungsdefizite rein statistischer Verfahren überwinden soll.

Zusammenfassung

Programmsynthese ist ein klassisches Gebiet der Informatik, das durch die AGI-Debatte neue Aufmerksamkeit erhielt.

Der Gedanke: Wer aus wenigen Beispielen ein Programm gewinnt, das die zugrunde liegende Regel ausdrückt, hat die Regel erfasst und nicht bloß Muster reproduziert – das Programm gilt dann auch für Fälle, die im Trainingsmaterial nicht vorkamen.

François Chollet baute den Benchmark ARC-AGI auf dieser Überlegung auf und gründete 2024 mit Mike Knoop das Unternehmen Ndea mit dem erklärten Ziel, AGI über Programmsynthese zu erreichen. Die zentrale Schwierigkeit ist der Suchraum: Die Menge möglicher Programme wächst mit deren Länge explosionsartig.

Verfahren

Die Ansätze unterscheiden sich nach Art der Spezifikation und nach Suchstrategie:

Synthese aus Beispielen. Aus Paaren von Ein- und Ausgaben wird ein Programm gesucht, das alle Paare erklärt. Dieses Vorgehen entspricht der Aufgabenstellung von ARC-AGI.

Formale Synthese. Aus einer logischen Spezifikation wird ein Programm konstruiert, dessen Korrektheit beweisbar ist. Der Ansatz liefert Garantien, skaliert aber schlecht.

Aufzählende Suche. Programme werden systematisch nach Größe durchmustert, geleitet durch Heuristiken oder eine gelernte Bewertungsfunktion.

Bibliothekslernen. Das System baut während der Bearbeitung vieler Aufgaben einen Vorrat wiederverwendbarer Bausteine auf und verkürzt damit die Suche für spätere Aufgaben. Das System DreamCoder ist dafür ein bekanntes Beispiel.

Neuronal geführte Synthese. Ein neuronales Netz schlägt aussichtsreiche Programmbestandteile vor, die anschließend geprüft werden. Dieser Ansatz verbindet die Mustererkennung des Lernens mit der Verlässlichkeit ausführbarer Programme und ist damit dem neurosymbolischen Feld zuzurechnen.

Bedeutung für die AGI-Debatte

Chollets Argument verläuft in zwei Schritten. Erstens: Intelligenz ist die Effizienz des Fähigkeitserwerbs, nicht die Menge des Gewussten. Zweitens: Wer aus wenigen Beispielen ein Programm gewinnt, das die zugrunde liegende Regel ausdrückt, hat genau diese Effizienz demonstriert – denn das Programm gilt auch außerhalb der beobachteten Fälle.

Daraus folgt die Konstruktion von ARC-AGI: Die Aufgaben verlangen, aus wenigen Beispielpaaren eine Transformationsregel zu erschließen. Wettbewerbsbeiträge arbeiten häufig mit einer domänenspezifischen Programmiersprache und einer Suche über deren Ausdrücke.

Chollets These lautet, dass Sprachmodelle grundsätzliche Generalisierungsdefizite aufweisen, weil sie interpolieren statt Regeln zu abstrahieren. Programmsynthese ist der Gegenentwurf: Statt eine Antwort vorherzusagen, wird ein Verfahren erzeugt, das die Antwort berechnet.

Verhältnis zu Sprachmodellen

Der Gegensatz ist weniger scharf, als die Programmatik nahelegt. Die praktisch erfolgreichste Form von Programmsynthese ist gegenwärtig die Codeerzeugung durch Sprachmodelle – sie synthetisieren Programme aus natürlichsprachlichen Beschreibungen, wenn auch ohne Korrektheitsgarantie.

Umgekehrt nutzen leistungsfähige ARC-Lösungen Sprachmodelle zur Steuerung der Suche. Die aussichtsreichen Ansätze verbinden damit beides: gelernte Vorschläge, symbolische Ausführung und Prüfung an den Beispielen.

Ein struktureller Unterschied bleibt: Ein erzeugtes Programm ist ausführbar und an den Beispielen überprüfbar; eine Modellantwort ist es nicht. Diese Prüfbarkeit ist der eigentliche Vorzug des Ansatzes.

Schwierigkeiten

Suchraumgröße. Die Zahl möglicher Programme wächst mit der Länge exponentiell. Sämtliche Verfahren stehen und fallen mit der Wirksamkeit der Einschränkung dieses Raums.

Spezifikationsproblem. Wenige Beispiele lassen viele Programme zu, die alle passen, aber unterschiedlich generalisieren. Welches das richtige ist, hängt von einer Annahme über die Einfachheit der Lösung ab – die formal zu fassen selbst ein Problem ist.

Domänenbindung. Erfolgreiche Verfahren beruhen meist auf einer eigens entworfenen Sprache für die jeweilige Domäne. Die Übertragung auf offene, nicht vorstrukturierte Bereiche ist ungelöst.

Empirischer Stand. Trotz der theoretischen Attraktivität haben programmsynthetische Ansätze bislang keine Leistungen erbracht, die mit denen großer Modelle vergleichbar wären. Die niedrigen Werte aller Ansätze auf ARC-AGI-3 betreffen auch sie.

Was der Ansatz eigentlich verspricht

Die anhaltende Anziehungskraft der Programmsynthese erklärt sich weniger aus ihren Ergebnissen als aus drei Eigenschaften, die den vorherrschenden Verfahren fehlen.

Nachprüfbarkeit. Ein erzeugtes Programm ist lesbar. Man kann es prüfen, es zeigt seine Voraussetzungen, es lässt sich abwandeln und auf Grenzfälle hin untersuchen. Die Erklärung ist nicht etwas, das nachträglich aus dem System herausgelesen werden müsste; sie ist das Ergebnis selbst.

Verlässliche Übertragung. Ein korrektes Programm gilt für alle Eingaben seiner Art, auch für solche, die nie vorkamen. Statistische Verfahren übertragen ihre Leistung auf Ähnliches; ein Programm überträgt sie auf alles, was seine Voraussetzung erfüllt. Genau darin besteht die Fähigkeit, deren Fehlen bei Sprachmodellen als Generalisierungsdefizit beschrieben wird.

Sparsamkeit im Lernen. Wo eine Regel gilt, genügen wenige Beispiele, um sie zu erschließen. Der Kontrast zu Verfahren, die dieselbe Regel aus Millionen Beispielen zu approximieren versuchen, ist der Ausgangspunkt für Chollets Bestimmung von Intelligenz als Effizienz des Fähigkeitserwerbs.

Der Preis für diese Eigenschaften ist der Suchraum. Die Zahl möglicher Programme wächst mit ihrer Länge so schnell, dass eine erschöpfende Suche schon bei kurzen Programmen ausscheidet – weshalb praktisch alle Fortschritte des Feldes darin bestehen, den Raum vorab einzuschränken. Genau diese Einschränkung ist es, die den Verfahren ihre Allgemeinheit wieder nimmt.

Verwandte Begriffe

• ARC-AGI – Benchmark, dessen Aufgabenstellung dem Ansatz entspricht
• François Chollet – Vertreter des Ansatzes als AGI-Pfad
• Neurosymbolische KI – übergeordnete Ansatzfamilie
• On the Measure of Intelligence – theoretische Begründung
• AGI – Zielbegriff
• Reasoning-Modelle – konkurrierender Entwicklungspfad
• Symbolische KI – Tradition, aus der der Ansatz stammt

Quellenangaben

1. ARC Prize Foundation (Chollet, François u. a.) (2026): ARC-AGI-3: A New Challenge for Frontier Agentic Intelligence. arXiv: 2603.24621.
2. Chollet, François (2019): On the Measure of Intelligence. arXiv: 1911.01547.
3. Chollet, François / Knoop, Mike / Kamradt, Greg / Landers, Bryan (2024): ARC Prize 2024: Technical Report. arXiv: 2412.04604.
4. Ellis, Kevin u. a. (2021): DreamCoder: Bootstrapping Inductive Program Synthesis with Wake-Sleep Library Learning. In: Proceedings of PLDI 2021. arXiv: 2006.08381.
5. Ndea, o. J. About Ndea. https://ndea.com/about.html

← Zurück zur Lexikon-Übersicht

Zuletzt bearbeitet: 10. August 2026

Zusammengestellt, formuliert, lektoriert und korrigiert mit KI-Unterstützung. Kuratiert von Nils Brauer. Alle Angaben ohne Gewähr.