🤖 AI

Empirical Computation: Prompting versus Programming

Dieses Vision Paper schlägt „empirische Komputation“ als ein neues Paradigma vor, bei dem Large Language Models computergestützte Probleme mittels Prompting anstatt durch traditionelle Programmierung lösen, wobei argumentiert wird, dass ihre einzigartigen Fähigkeiten und Grenzen die Software-Engineering-Gemeinschaft dazu veranlassen, neue grundlegende Theorien und Techniken zur Analyse von Korrektheit und fundamentalen Grenzen zu entwickeln.

Ursprüngliche Autoren: Eric Tang, Jing Liu, Marcel Böhme

Veröffentlicht 2026-07-08

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Eric Tang, Jing Liu, Marcel Böhme

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 haben zwei Möglichkeiten, eine Aufgabe zu erledigen: Programmieren und Prompten.

Der alte Weg: Programmieren (Der strenge Architekt)

Stellen Sie sich traditionelles Programmieren wie die Anstellung eines strengen, regelkonformen Architekten vor. Sie geben ihm einen Bauplan mit exakten Maßen, spezifischen Materialien und einem Schritt-für-Schritt-Plan.

Wie es funktioniert: Sie sagen dem Computer genau, wie er ein Problem lösen soll, wie zum Beispiel das Sortieren einer Liste von Zahlen. Sie sagen: „Verwende diesen spezifischen Algorithmus (Merge Sort), nimm diese Eingaben und folge diesen Regeln.“
Das Ergebnis: Wenn der Architekt einen Fehler macht, können Sie den exakt defekten Ziegelstein im Bauplan finden, ihn reparieren und mit Sicherheit wissen, dass das Gebäude beim nächsten Mal korrekt stehen wird.
Die Grenze: Die Zeit, die es dauert, etwas zu bauen, hängt von der Komplexität der Mathematik ab. Das Sortieren einer riesigen Liste von Zahlen dauert auf eine vorhersehbare Weise, die von der Größe der Liste abhängt (speziell $O(n \log n)$ ).

Der neue Weg: Prompten (Der intuitive Künstler)

Stellen Sie sich nun vor, Sie engagieren stattdessen einen brillanten, intuitiven Künstler. Sie geben ihm keinen Bauplan. Sie sagen einfach nur: „Hey, hier ist ein unordentlicher Haufen Zahlen, könntest du sie für mich sortieren?“

Wie es funktioniert: Sie verwenden natürliche Sprache (einen „Prompt“), um das Problem zu beschreiben. Der „Computer“ (ein Large Language Model oder LLM) folgt keinen strengen Regeln. Stattdessen rät er die wahrscheinlichste Antwort basierend auf allem, was er jemals im Internet gelesen hat. Es ist wie ein Koch, der eine Suppe probiert und die Zutaten errät, anstatt einem Rezept zu folgen.
Das Ergebnis: Die Antwort kommt schnell zurück, aber sie ist eine Vermutung, keine Garantie. Es ist die „wahrscheinlichste“ Antwort, nicht die „bewiesenermaßen korrekte“ Antwort.

Was die Arbeit herausfand: Die „empirische“ Überraschung

Die Autoren dieser Arbeit führten Experimente durch, um zu sehen, wie gut dieser „intuitive Künstler“ bei klassischen mathematischen Problemen wie dem Sortieren von Zahlen oder dem Finden von Elementen in einer Liste abschneidet. Hier ist, was sie entdeckten:

1. Zeit funktioniert nicht auf die gleiche Weise

Programmieren: Wenn Sie die Anzahl der zu sortierenden Elemente verdoppeln, steigt die Zeit, die es dauert, auf eine spezifische, mathematische Weise an.
Prompting: Die Zeit, die das LLM benötigt, um Zahlen zu sortieren, steigt linear (also als gerade Linie) an, wenn die Liste größer wird. Warum? Nicht, weil die Mathematik schwieriger wird, sondern weil das LLM mehr Wörter (Token) lesen und schreiben muss, um die längere Liste zu verarbeiten. Es ist wie das Lesen eines längeren Buches; es dauert länger, die Wörter zu lesen, nicht weil die Geschichte komplexer ist.

2. Genauigkeit sinkt, wenn die Aufgaben größer werden

Programmieren: Ein korrektes Programm ist jedes Mal zu 100 % korrekt.
Prompting: Das LLM ist bei kleinen Aufgaben großartig, wird aber verwirrt, wenn die Liste wächst.
- Bei einer Liste von 50 Zahlen lag das LLM etwa 90 % der Zeit richtig.
- Bei einer Liste von 150 Zahlen war es nur noch in 58 % der Fälle korrekt.
- Wenn man es bittet, ein bestimmtes Muster in einem kurzen String zu finden, kann es fast sofort scheitern, wenn der String etwas länger wird.
- Der „Denk“-Modus: Wenn das LLM erlaubt wird, vor der Antwort zu „denken“ (schrittweise zu argumentieren), bleibt es sehr genau, aber es dauert viel länger.

3. Das Sprachspiel

Programmieren: Es spielt keine Rolle, ob Sie den Code in Englisch oder Deutsch schreiben; der Computer liest die Symbole auf die gleiche Weise.
Prompting: Das LLM ist durch das, was es im Internet gelesen hat, voreingenommen.
- Wenn Sie das LLM bitten, Zahlen zu sortieren, die als englische Wörter geschrieben sind („one, two, three“), macht es einen guten Job.
- Wenn Sie es bitten, Zahlen in deutscher Sprache zu sortieren („eins, zwei, drei“), versagt es fast vollständig.
- Warum? Das LLM hat Millionen von englischen Beispielen im Internet gesehen, aber weit weniger deutsche. Es ist, als würde man einen Koch bitten, ein Gericht zu kochen, das er noch nie gesehen hat; er könnte falsch raten.

4. Das „Defekte-Ziegelstein-Problem“

Programmieren: Wenn ein Programm fehlschlägt, können Sie den Bug finden, den Code korrigieren und das Problem ist dauerhaft gelöst.
Prompting: Wenn das LLM eine falsche Antwort gibt, können Sie nicht einfach „den Bug“ finden. Sie können nicht auf eine bestimmte Zeile Code zeigen, um sie zu reparieren. Sie können versuchen, Ihren Prompt zu ändern oder es zu bitten, „tiefer nachzudenken“, aber es gibt keine Garantie, dass dies beim nächsten Mal funktioniert. Es ist, als würde man versuchen, einen Traum zu reparieren, indem man die Stimmung des Träumers ändert.

Das große Fazit

Die Arbeit argumentiert, dass wir in eine neue Ära eintreten, die „Empirische Komputation“ genannt wird.

In der alten Welt vertrauten wir Computern, weil sie strengen Regeln folgten (rationalistischer Rahmen). In dieser neuen Welt vertrauen wir Computern, weil sie „gebildete Vermutungen“ basierend auf Daten anstellen (empirischer Rahmen).

Die Autoren rufen Softwareentwickler dazu auf, aufzuhören, diese KI-Systeme wie klassische Programme zu analysieren. Wir brauchen neue Werkzeuge, um zu messen, zu testen und zu verstehen, wie diese „Rate-Maschinen“ funktionieren, denn die alten Regeln von Mathematik und Logik treffen auf sie nicht mehr vollumfänglich zu. Wir müssen herausfinden, wie wir einem Ergebnis vertrauen können, das „wahrscheinlich richtig“ statt „definitiv richtig“ ist.

Technisches Resümee: Empirische Komputation: Prompting versus Programmierung

Problemstellung

Die Arbeit identifiziert einen Paradigmenwechsel bei der Lösung computationaler Probleme: den Übergang von der Programmierung (Spezifikation präziser Algorithmen und Datenstrukturen) zum Prompting (Bereitstellung informeller, natürlicher Sprachbeschreibungen für Large Language Models oder Agenten). Während die traditionelle Komputation auf deterministischen Verfahren mit verifizierbarer Korrektheit und wohldefinierten Komplexitätsgrenzen beruht (z. B. $O(n \log n)$ für Sortieren), basiert „empirische Komputation“ auf dem Sampling von Ausgaben aus einer Wahrscheinlichkeitsverteilung.

Das Kernproblem besteht darin, dass die Fähigkeiten und Grenzen dieser neuen Form der Komputation nicht innerhalb des klassischen, rationalistischen Rahmens der Informatik verstanden werden können. Speziell:

Mangel an Determinismus: Ausgaben werden nicht prozedural generiert, sondern sind das „empirisch wahrscheinlichste“ Ergebnis, was sie anfällig für Halluzinationen und Fehler macht, die sich nicht lokalisieren oder mittels traditioneller Debugging-Methoden reparieren lassen.
Ambiguität im Input: Im Gegensatz zur Programmierung, die formale Kontrakte (Typen, Formate) erfordert, akzeptiert Prompting informelle Eingaben, bei denen die Interpretation vom Kontext und der Trainingsverteilung des Modells abhängt.
Unklare Komplexität: Das Laufzeitverhalten scheint von der klassischen algorithmischen Komplexität entkoppelt zu sein und korreliert stattdessen mit Tokenisierung und Modell-Inferenzverhalten.
Verifizierungs-Gap: Bestehende Software-Engineering-Techniken (statische Analyse, formale Verifikation) sind ungeeignet, um Systeme zu analysieren, in denen kein explizites Programm zur Verifikation existiert.

Methodik

Die Autoren führten vorläufige Experimente durch, um die Effizienz und Korrektheit der empirischen Komputation anhand von fünf klassischen computationalen Problemen zu charakterisieren:

Sortieren: Aufsteigende Reihenfolge von Zufallszahlen.
Suchen: Finden eines Index in sortierten und unsortierten Listen.
Längster palindromischer Substring: Finden der längsten palindromischen Sequenz in einem String.
Subset Sum Problem (SSP): Finden einer Teilmenge von Zahlen, deren Summe einen Zielwert ergibt.

Experimentelles Setup:

Modell: Die Experimente nutzten das Open-Weights-Modell gemma-4-26b-a4b, das lokal auf einem MacBook Pro (M5 Pro, 48 GB RAM) ausgeführt wurde, um Netzwerk-Latenzen zu eliminieren.
Konfigurationen: Drei Modi wurden getestet:
- Default: Temperatur = 1.0.
- Deterministisch: Temperatur = 0.0.
- Thinking: Reasoning-Modus aktiviert.
Metriken:
- Effizienz: Zeit bis zur Lösung und Zeit bis zur ersten korrekten Lösung.
- Korrektheit: Anteil der Versuche, die das mathematisch korrekte Ergebnis liefern.
Variablen: Eingabegröße ( $n$ ), Zahlenpräzision und sprachliche Repräsentation (Ziffern vs. Wörter in verschiedenen Sprachen: Englisch, Deutsch, Koreanisch, Japanisch, etc.).
Ground Truth: Für nicht-triviale Probleme (Substring, SSP) wurden einfache Python-Programme zur Validierung der korrekten Antworten verwendet.

Kernergebnisse

1. Effizienz vs. klassische Komplexität

Im Gegensatz zur klassischen Theorie folgt die Laufzeit der empirischen Komputation nicht strikt der algorithmischen Komplexität des Problems (z. B. $O(n)$ vs. $O(n \log n)$ ).

Lineare Skalierung: Für Sortieren, Suchen und SSP stieg die Zeit bis zur Lösung linear mit der Eingabegröße ( $O(n)$ ) über alle Modi hinweg an. Die Autoren führen dies auf die lineare Zunahme der Input-/Output-Token zurück, nicht auf die computational-logische Komplexität.
Token-Abhängigkeit: Die Zeit, die benötigt wurde, um eine Zahl zu inkrementieren, war vergleichbar mit der Vorhersage von Klartext aus einem SHA-512-Hash, was darauf hindeutet, dass die Laufzeit durch Tokenisierung und Inferenzmechanismen getrieben wird und nicht durch die Schwierigkeit des Problems.
Kosten des Thinking-Modus: Das Aktivieren von „Thinking“ (Reasoning) erhöhte die Laufzeit signifikant (z. B. bis zu 275s für das Sortieren von 150 Elementen), bewahrte jedoch eine hohe Korrektheit.

2. Korrektheit und Eingabegröße

Größensensitivität: In den Modi Default und Deterministisch sank die Korrektheit mit zunehmender Eingabegröße rapide ab.
- Beim Sortieren von 50 Integern sank die Korrektheit auf ~50% (Wahrscheinlichkeit eines Münzwurfs).
- Beim Sortieren von 150 Integern fiel die Korrektheit auf ~58% (trotz der linearen Zeitzunahme).
- Beim Subset Sum Problem näherte sich die Korrektheit bei Listen der Länge 10 dem Wert Null.
- Beim Substring-Problem sank die Korrektheit bei Strings der Länge 5 auf nahezu Null.
Resilienz des Thinking-Modus: Wenn Reasoning-Fähigkeiten aktiviert wurden, blieb die Korrektheit auch bei größeren Eingaben hoch (>90%), sofern die Token-/Zeitlimits eingehalten wurden.

3. Einfluss der natürlichen Sprachrepräsentation

Die Studie untersuchte, wie die Sprache, in der Zahlen repräsentiert werden, die Korrektheit beeinflusst.

Datenrepräsentations-Bias: Die Korrektheit hängt stark von der Repräsentation der Sprache in den Trainingsdaten des Modells ab.
Hohe vs. niedrige Repräsentation: Das Sortieren von Zahlen in Englisch (gut repräsentiert) ergab eine Korrektheit von >95% bei Größe 20. Im Gegensatz dazu lieferte das Sortieren von Zahlen in Deutsch (unterrepräsentiert) bei der gleichen Größe eine Korrektheit von <1%.
Fazit: Empirische Komputation ist nicht sprachneutral; sie ist verzerrt zugunsten von Sprachen und Formaten, die im Trainingskorpus vorherrschen.

4. Fehlercharakteristika

Im Gegensatz zu traditionellen Programmen, bei denen Fehler auf spezifische Codezeilen lokalisiert werden können, sind Fehler in der empirischen Komputation nicht-deterministisch. Das LLM kann:

Zahlen hinzufügen, die nicht in der Eingabe enthalten sind.
Vorhandene Zahlen entfernen.
Zahlen duplizieren.
Nicht die gesamte Liste sortieren.
Große Eingaben abschneiden.

Zentrale Beiträge

Definition der empirischen Komputation: Die Arbeit führt „empirische Komputation“ formal als ein distinktes Feld ein, in dem Lösungen durch Prompting und Sampling statt durch prozedurale Ausführung generiert werden.
Empirische Charakterisierung: Sie liefert die erste systematische Messung von Effizienz und Korrektheit für LLMs bei der Lösung klassischer algorithmischer Probleme und zeigt auf, dass die Laufzeit mit der Tokenisierung und nicht mit der algorithmischen Komplexität korreliert.
Identifikation von Grenzen: Die Studie demonstriert, dass die empirische Komputation ohne Reasoning-Modi nicht zuverlässig mit der Eingabegröße skaliert und hochsensibel gegenüber der linguistischen Repräsentation der Eingaben ist.
Aufruf nach neuen SE-Fundamenten: Die Autoren argumentieren, dass die Software-Engineering-Community neue Werkzeuge für die „empirische Programmanalyse“ (statistische, kontrafaktische oder kausale Argumentation) entwickeln muss, um die Korrektheit dieser Systeme zu analysieren, zu schätzen und vorherzusagen.

Bedeutung und Vision

Die Arbeit postuliert, dass die Software-Engineering-Community sich nicht auf klassische rationalistische Frameworks oder bestehende Programmanalyseverfahren verlassen kann, um die Vertrauenswürdigkeit KI-gestützter Komputation zu gewährleisten. Da LLMs und Agenten immer integraler Bestandteil bei der Lösung computationaler Probleme werden, muss sich das Feld weiterentwickeln, um folgende Fragen zu adressieren:

Wie analysiert man Korrektheit in Abwesenheit eines formalen Programms?
Wie definiert und testet man die Grenzen der empirischen Komputation?
Wie verbessert man die Korrektheit für spezifische Probleminstanzen, ohne Regressionen einzuführen?

Die Autoren rahmen dies als ein zeitgemäßes und reichhaltiges Forschungsgebiet ein und fordern die Entwicklung neuer Techniken der „empirischen Programmanalyse“, um die Lücke zwischen der probabilistischen Natur von LLMs und den rigorosen Anforderungen des Software-Engineerings zu schließen. Die Arbeit behauptet nicht, diese Probleme zu lösen, sondern zielt darauf ab, das Feld zu etablieren und die dringende Notwendigkeit neuer theoretischer und praktischer Fundamente hervorzuheben.