🤖 machine learning

Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching

Das Papier stellt Sketch-and-Verify vor, eine kosteneffiziente Strategie zur Skalierung während der Inferenz für kleine Code-Modelle, die das flache Sampling durch das Aufzählen diverser algorithmischer Skizzen und das Auffüllen mit mehreren Kandidaten übertrifft, obwohl sie die Leistung stärkerer Modellstufen nicht vollständig ersetzen kann.

Ursprüngliche Autoren: Shan Jiang, Zijian Yi, Chenguang Zhu

Veröffentlicht 2026-05-12

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shan Jiang, Zijian Yi, Chenguang Zhu

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, ein kniffliges Rätsel zu lösen, haben aber nur einen kleinen, günstigen Roboter zur Hilfe. Dieser Roboter ist schnell und billig, hat jedoch eine schlechte Angewohnheit: Wenn er versucht, ein Problem zu lösen, wählt er fast immer denselben falschen Denkweg. Wenn Sie ihn bitten, 100 Mal zu versuchen, erhalten Sie einfach 100 leicht unterschiedliche Versionen derselben falschen Antwort.

Dies ist das Problem, das die Arbeit „Sketch-and-Verify" (Skizzieren und Verifizieren) zu lösen versucht. Sie bietet einen neuen Weg, diesen kleinen, günstigen Roboter so einzusetzen, dass er mehr Probleme lösen kann, ohne auf einen super-teuren, riesigen Roboter upgraden zu müssen.

So funktioniert die Methode, aufgeschlüsselt in einfache Schritte:

1. Das Problem: „Der immer gleiche Song"

Normalerweise, wenn wir eine KI bitten, Code zu schreiben, sagen wir einfach: „Versuche es 100 Mal und gib mir die beste Version."

Der Fehler: Wenn die „Standard"-Idee der KI falsch ist, ist es so, als würde man eine Person bitten, 100 verschiedene Versionen eines schlechten Songs zu schreiben. Man mag den Text oder das Tempo ändern, aber die Melodie ist immer noch falsch. Die KI gerät in eine Schleife von „kosmetischen" Änderungen (Ändern von Variablennamen oder Formatierung), ohne jemals einen grundlegend anderen Ansatz zu versuchen.

2. Die Lösung: „Der Architekt und der Baumeister"

Die Autoren schlagen einen zweistufigen Prozess namens Sketch-and-Verify vor. Anstatt die KI zu bitten, sofort den gesamten Code zu schreiben, teilen sie die Aufgabe in zwei Rollen auf:

Schritt 1: Der Architekt (Die Skizze)
Zuerst bitten sie die KI, wie ein Architekt zu agieren. Sie sagen: „Schreibe den Code noch nicht. Liste einfach 5 völlig verschiedene Wege auf, dieses Problem zu lösen."
- Beispiel: „Strategie A: Verwende eine Karte. Strategie B: Sortiere die Liste zuerst. Strategie C: Verwende eine Schleife."
- Sobald die KI eine Strategie gewählt hat, zeichnet sie einen groben „Grundriss" (eine Skizze) mit Lücken darin. Der Grundriss hat die Hauptstruktur (die Wände und das Dach), lässt aber die spezifischen Details (die Farbe, den Türknauf) als leere Felder markiert mit ??.
- Warum das hilft: Dies zwingt die KI, innezuhalten und über verschiedene Wege nachzudenken, bevor sie mit dem Bauen beginnt. Es garantiert, dass die KI verschiedene „Nachbarschaften" von Lösungen erkundet, anstatt nur im Kreis in derselben zu laufen.
Schritt 2: Der Baumeister (Das Ausfüllen)
Jetzt füllt die KI für jeden Grundriss als Baumeister die ??-Lücken aus, um ein vollständiges Programm zu erstellen.
- Wenn die KI 5 Grundrisse (Strategien) erstellt und jeden davon 10 Mal ausgefüllt hat, hat sie nun 50 völlig verschiedene Programme zum Testen.
- Da die Grundrisse unterschiedlich waren, sind diese 50 Programme strukturell vielfältig. Sie sind nicht nur Umschreibungen derselben Idee, sondern wirklich unterschiedliche Ansätze.
Schritt 3: Der Inspektor (Verifizieren)
Schließlich werden alle diese Programme durch einen Test laufen gelassen. Sie behalten diejenigen, die funktionieren, und wählen die beste aus.

3. Die Ergebnisse: Günstig vs. Teuer

Die Forscher testeten dies an einem Standard-Code-Test namens HumanEval+ unter Verwendung von drei Versionen von Googles Gemini-KI:

Lite: Das kleine, günstige, schnelle Modell.
Flash: Das mittlere Modell.
Pro: Das große, teure, intelligente Modell.

Die großen Erkenntnisse:

Für den günstigen Roboter (Lite): Die „Sketch-and-Verify"-Methode war ein Wendepunkt.
- Wenn sie den Lite-Roboter einfach normal 100 Mal versuchen ließen (Flat Sampling), löste er etwa 53% der schwierigen Probleme.
- Wenn sie die Sketch-and-Verify-Methode verwendeten (10 Grundrisse erstellen und jeden 10 Mal ausfüllen), löste er 79% der schwierigen Probleme.
- Die Analogie: Es ist so, als würde man einem Schüler sagen: „Schreibe nicht einfach 100 Aufsätze über dasselbe Thema. Erstelle 10 Gliederungen für 10 verschiedene Themen und fülle sie dann aus." Der Schüler lernt mehr und erhält für denselben Aufwand eine bessere Note.
Für den teuren Roboter (Pro): Die Methode half nicht viel.
- Der Pro-Roboter ist bereits so intelligent, dass seine „Standard"-Idee meist richtig ist. Ihn zu zwingen, verschiedene Strategien zu skizzieren, machte ihn tatsächlich etwas schlechter, da er von seinem besten Instinkt abgelenkt wurde.
- Die Regel: Wenn Sie einen super-intelligenten Roboter haben, lassen Sie ihn einfach hart nachdenken (Greedy). Wenn Sie nur einen günstigen Roboter haben, verwenden Sie Sketch-and-Verify, um ihn zu zwingen, kreativ zu denken.

4. Das Fazit

Die Arbeit argumentiert, dass Sketch-and-Verify ein intelligenter Weg ist, zusätzliche Rechenleistung einzusetzen, wenn man mit einem kleineren, günstigeren KI-Modell feststeckt.

Es ist kein Zauber: Es macht ein schwaches Modell nicht stärker als ein starkes Modell. Wenn Sie sich das teure „Pro"-Modell leisten können, verwenden Sie einfach dieses.
Es ist eine Strategie: Wenn Sie müssen, das günstige Modell verwenden (wegen Budget oder Geschwindigkeit), ist diese Methode der beste Weg, um zusätzliche Leistung daraus herauszuholen. Sie verhindert, dass die KI in einer Sackgasse stecken bleibt, und zwingt sie, verschiedene Lösungen zu erkunden, ähnlich wie eine menschliche Brainstorming-Sitzung.

Kurz gesagt: Bitten Sie die KI nicht nur, es härter zu versuchen; bitten Sie sie, es anders zu versuchen.

Technische Zusammenfassung: Sketch-and-Verify: Strukturierte Skalierung zur Inferenzzeit durch Programmskizzierung

1. Problemstellung

Die Arbeit adressiert eine spezifische operationelle Einschränkung, mit der Praktiker konfrontiert sind: Gegeben ein festes, kleines und kosteneffizientes Code-Modell (z. B. Gemini 3.1 Flash Lite), das aus Gründen der Latenz oder des Budgets ausgewählt wurde, wie sollte man eine begrenzte Menge an zusätzlicher Rechenleistung zur Laufzeit (Test-Time Compute) einsetzen, um die Genauigkeit zu verbessern?

Standardansätze beinhalten flaches Sampling (Generieren von $N$ unabhängigen Kandidatenprogrammen und Auswahl des besten mittels Ausführung). Die Autoren argumentieren, dass flaches Sampling ineffizient ist, da es den Programmraum als homogen behandelt. Große Sprachmodelle (LLMs) weisen häufig eine hohe Wahrscheinlichkeitsmasse auf eine einzelne „modale" algorithmische Strategie auf. Folglich fehlt der resultierende Kandidatenpool selbst bei hoher Temperatur oder großem $N$ an struktureller Diversität; er besteht hauptsächlich aus oberflächlichen kosmetischen Varianten (unterschiedliche Variablennamen, Formatierung) derselben 2–3 Strategien. Wenn die Standardstrategie des Modells für ein bestimmtes Problem falsch ist, wird flaches Sampling wahrscheinlich scheitern, die korrekte Lösung zu entdecken, unabhängig von der Anzahl der Stichproben.

2. Methodik: SKETCHVERIFY

Die Autoren schlagen SKETCHVERIFY vor, eine Methode, die die Rechenleistung zur Inferenzzeit neu strukturiert, indem sie den Suchraum in algorithmische Strategie und Implementierungsdetails zerlegt. Inspiriert von Programmskizzierung (Solar-Lezama, 2008, 2013) und früheren Arbeiten zu LLM-gestütztem Compiler-Testing (OBsmith, Jiang et al., 2026b), arbeitet die Methode in vier Stufen:

Stufe 1: Skizzengenerierung (Kategorie-zuerst-Prompting)
- Kategorieenumeration: Das LLM wird aufgefordert, $K$ grundlegend unterschiedliche algorithmische Strategien (z. B. „Hash-Map", „Zwei-Pointer", „Dynamische Programmierung") in natürlicher Sprache aufzulisten. Dies zwingt das Modell, über den Strategieraum nachzudenken, bevor es codiert.
- Skizzierung: Für jede Strategie generiert das LLM ein teilweise Programm (eine „Skizze"), bei dem der Algorithmus, die Datenstrukturen und der Kontrollfluss vollständig spezifiziert sind, Implementierungsdetails (Ausdrücke, Bedingungen, Schleifengrenzen) jedoch durch ??-Platzhalter ersetzt werden. Das Ziel sind 4–8 Lücken pro Skizze.
- Schlüsselinnovation: Dieser Zwei-Schritte-Prozess verhindert, dass das autoregressive Modell auf eine einzelne Standardstrategie fixiert wird, und gewährleistet strukturelle Diversität über die $K$ Skizzen hinweg.
Stufe 2: Ausfüllen
- Jede gültige Skizze wird $M$ Mal ausgefüllt, um $K \times M$ vollständige Kandidatenprogramme zu erzeugen.
- Um Variation innerhalb einer einzelnen Skizze zu fördern, wird jedes dritte Ausfüllen auf die vorherige Ausfüllung konditioniert und aufgefordert, eine andere Implementierung bereitzustellen.
Stufe 3: Verifizierung
- Kandidaten werden auf Kompilierbarkeit und fehlerfreie Ausführung gefiltert.
- Überlebende Kandidaten werden auf $D$ diverse Testeingaben ausgeführt (generiert über einen ähnlichen skizzenbasierten Ansatz).
- Für jeden Kandidaten wird ein Ausführungs-Fingerabdruck generiert: ein Vektor aus (Status, Ausgabe)-Paaren. Identische Fingerabdrücke deuten auf behaviorale Äquivalenz hin.
Stufe 4: Auswahl
- Kandidaten werden nach ihren Ausführungs-Fingerabdrücken geclustert.
- Der größte Cluster (repräsentiert den robustesten behavioralen Konsens) wird ausgewählt.
- Aus dem größten Cluster wird das kürzeste Programm zurückgegeben (Ockhams Rasiermesser). Diese Auswahlnregel ist identisch mit der parallelen „Semantic Voting"-Arbeitslinie und isoliert den Nutzen der strukturierten Generierung vom Auswahlmechanismus.

3. Hauptbeiträge

SKETCHVERIFY-Rahmenwerk: Führt eine kosten-Leistungs-Politik innerhalb einer Tier-Ebene ein, die Programmskizzierung auf die Skalierung zur Inferenzzeit anwendet. Es zerlegt den Suchraum in $K$ (Strategien) und $M$ (Implementierungen) und erreicht eine steilere pass@1-Skalierungskurve als flaches Sampling bei schwachen Modellen.
Kosten-Qualität-Pareto-Analyse: Bietet eine rigorose Analyse am HumanEval+-Benchmark, speziell eine Neubewertung eines „harten Teilsatzes" von 19 Problemen, bei denen das Basis-Lite-Modell (greedy) versagt.
- Innerhalb der Tier-Ebene: Skizzierung dominiert flaches Sampling bei gleicher Anzahl an Kandidaten. Auf dem harten Teilsatz stellt Lite Sketch ( $K=2, M=5$ ) 58 % der Probleme wieder her, verglichen mit 26 % für flaches Sampling ( $N=10$ ). Selbst bei einer 3-fachen Budgeterhöhung erreicht flaches Sampling ( $N=50$ ) nur 47 % und verliert immer noch gegen die günstigere Skizzen-Konfiguration.
- Über Tier-Ebenen hinweg: Skizzierung ersetzt nicht das Hochstufen des Modells. Stärkere Tier-Ebenen (z. B. Gemini Pro greedy) dominieren Lite+Sketch-Konfigurationen sowohl bei Kosten als auch bei Genauigkeit. Skizzierung ist eine Ergänzung zu, kein Ersatz für, das Hochstufen der Modell-Tier-Ebene.
Kategorie-zuerst-Zerlegung: Schlägt eine spezifische Prompt-Strategie vor (Auflistung von Strategienamen vor dem Codieren), die entscheidend für die Generierung struktureller Diversität und nicht kosmetischer Varianten ist.
Charakterisierung des K-vs-M-Trade-offs: Durch Skalierungs-Sweeps zeigen die Autoren, dass die Beziehung zwischen $K$ und $M$ nicht-monoton ist. Gemischte Allokationen (z. B. $K=2, M=5$ ) übertreffen oft reine flache ( $K=1$ ) oder reine skizzenbasierte ( $M=1$ ) Extreme, und eine einfache Erhöhung von $K$ führt nicht immer zu linearen Gewinnen (z. B. schnitt $K=5, M=10$ in einigen Metriken schlechter ab als $K=2, M=5$ ).
Komponierbarkeit: Zeigt, dass strukturierte Generierung sauber mit ausführungsbasierter Auswahl (Semantic Voting) komponiert. Die Methode fungiert als Generator eines diversen Kandidatenpools, während der Selektor gegenüber der Generierungsmethode agnostisch bleibt.

4. Experimentelle Ergebnisse

Benchmarks: Evaluiert auf HumanEval+ (164 Python-Probleme mit erweiterten Test-Suiten). Eine cross-benchmark Validierung auf MBPP+ und LiveCodeBench wird als zukünftige Arbeit notiert.
Modelle: Drei Tier-Ebenen von Google Gemini-Modellen (Pro, Flash, Flash Lite) bei niedrigen Denkleveln.
Leistung auf harten Teilsätzen (19 Probleme, bei denen Lite greedy versagt):
- Lite Sketch ( $K=10, M=10$ ): 79 % pass@1.
- Lite Flat ( $N=100$ ): 53 % pass@1.
- Lite Sketch ( $K=2, M=5$ ): 58 % pass@1 (bei niedrigeren Kosten als Flat $N=50$ ).
- Flash/Pro Greedy: Übertrifft alle Lite-Konfigurationen, was bestätigt, dass die Modellkapazität der primäre Treiber der Genauigkeit ist.
Skalierungskurven: Auf dem gesamten HumanEval+-Set saturiert Lite flaches Sampling bei ca. 89 % pass@1. SKETCHVERIFY durchbricht diese Decke und erreicht 93 % bei $K=10, M=10$ . Jedoch sind bei Flash und Pro, wo Modelle nahezu saturiert sind, die Gewinne durch Skizzierung marginal oder im Vergleich zum Greedy-Decoding nicht vorhanden.

5. Bedeutung und Behauptungen

Die Arbeit positioniert SKETCHVERIFY als eine kosten-Leistungs-Politik innerhalb einer Tier-Ebene, nicht als universelle Genauigkeitsverbesserung.

Regel für Praktiker: Wenn eine stärkere Modell-Tier-Ebene verfügbar ist, verwenden Sie Greedy-Decoding auf dieser Tier-Ebene. Wenn Sie aufgrund von Latenz, Bereitstellung oder Budget auf ein schwächeres Modell beschränkt sind, ist SKETCHVERIFY der kosteneffektivste Weg, zusätzliche Rechenleistung zur Laufzeit einzusetzen.
Mechanismus: Die Methode gelingt, indem sie explizit die Exploration verschiedener algorithmischer Strategien (strukturelle Diversität) erzwingt, anstatt sich darauf zu verlassen, dass die Stochastik des flachen Sampling zufällig einen neuen Ansatz findet.
Limitationen: Die Autoren erkennen Limitationen an, darunter die Abhängigkeit von einer einzigen Modellfamilie (Gemini), einem einzigen Denklevel und die Tatsache, dass die Skizzqualität durch die eigene Strategieverteilung des Modells begrenzt ist (wenn das Modell die korrekte Strategie nicht konzipieren kann, kann Skizzierung sie nicht generieren). Sie vermerken zudem einen Token-Overhead von ca. 7 % für die Phase der Skizzengenerierung.

Die Arbeit kommt zu dem Schluss, dass Skizzierung zwar hochwirksam für schwache Modelle ist, die mit strategischer Diversität kämpfen, aber kein Allheilmittel für Modelle ist, die bereits ihre Kapazitätsgrenze erreicht haben, oder für Probleme, bei denen die korrekte Strategie vollständig außerhalb des latenten Wissens des Modells liegt.