💻 computer science

AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation

Das Papier stellt ALGOBENCH vor, ein neuartiges Framework, das adaptive algorithmische Probleme generiert, indem es bestehende Wettbewerbsprogrammierungs-Herausforderungen transformiert, um die Wiederverwendung von Lösungen zu verhindern, begleitet von komplexitätsbewussten Metriken, um rigoros zu evaluieren, ob Sprachmodelle über bloße funktionale Korrektheit hinaus echte algorithmische Denkfähigkeiten besitzen.

Ursprüngliche Autoren: Xinyuan Song, Zekun Cai, Liang Zhao

Veröffentlicht 2026-07-02

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Xinyuan Song, Zekun Cai, Liang Zhao

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 trainieren einen Schüler beim Lösen von Matheaufgaben. Sie geben ihm einen Übungstest, und er besteht ihn mit Bravour. Sie denken vielleicht: „Wow, er hat die Analysis wirklich verstanden!“ Aber was, wenn er die Mathematik gar nicht gelernt hat? Was, wenn er einfach nur die Antworten auf diese spezifischen Fragen auswendig gelernt hat, weil er sie zuvor in einem Lehrbuch gesehen hat?

Genau dieses Problem versucht das Paper ALGOBENCH bei Large Language Models (LLMs) zu lösen – den KI-Systemen, die Code schreiben.

Das Problem: Der „Spickzettel“-Effekt

Aktuelle KI-Modelle sind gut darin, Standard-Coding-Tests wie HumanEval zu bestehen. Das Paper argumentiert jedoch, dass diese Tests zunehmend „kontaminiert“ sind. Da diese Probleme öffentlich zugänglich sind, hat die KI die exakten Fragen und deren Lösungen höchstwahrscheinlich bereits während ihres Trainings gesehen.

Es ist, als würde ein Schüler eine Prüfung ablegen, bei der der Lehrer versehentlich den Lösungsschlüssel auf dem Tisch liegen gelassen hat. Der Schüler erzielt eine perfekte Punktzahl, nicht weil er ein Genie ist, sondern weil er den Schlüssel auswendig gelernt hat. Das Paper nennt dies Memorierung (Auswendiglernen) statt Reasoning (logisches Schlussfolgern). Die KI findet nicht heraus, wie man das Problem löst; sie erinnert sich lediglich daran, wie die Lösung aussieht.

Die Lösung: ALGOBENCH (Der „Twist“-Test)

Um dies zu beheben, haben die Forscher ALGOBENCH entwickelt. Betrachten Sie es als einen „Twist-Test“ für KI.

Anstatt der KI ein statisches Problem zu geben, nehmen sie ein bekanntes Problem und wenden darauf einen „magischen Twist“ an. Sie ändern die Regeln gerade so weit, dass die alte, auswendig gelernte Antwort nicht mehr funktioniert, das Problem aber dennoch halbwegs vertraut aussieht.

Hier sind die „Twists“, die sie verwenden:

Der „Scale Up“-Twist: Wenn das ursprüngliche Problem verlangt, 100 Zahlen zu sortieren, fragt das neue Problem nach der Sortierung von 1.000.000 Zahlen. Die alte „langsame“ Methode stürzt ab, und die KI muss einen schnelleren, intelligenteren Weg erfinden.
Der „Moving Target“-Twist: Wenn das ursprüngliche Problem von einer statischen Liste von Zahlen handelte, fügt das neue Problem eine Regel hinzu, wonach sich Zahlen ändern, während man daran arbeitet. Die alte „Read-only“-Lösung versagt, und die KI benötigt eine dynamische Strategie.
Der „Trap“-Twist (Die Falle): Sie konstruieren ein Szenario, in dem eine gängige Abkürzung (wie eine gierige Annäherung/Greedy-Ansatz) anfangs so aussieht, als würde sie funktionieren, aber bei versteckten, kniffligen Fällen scheitert.

Wenn die KI versucht, ihre alte memorierte Lösung zu verwenden, scheitert sie. Um zu bestehen, muss sie ihr Denken anpassen und einen neuen Algorithmus generieren.

Der „Geschwindigkeitsbegrenzung“-Check

Das Paper weist auch auf einen Fehler in der Art und Weise hin, wie wir KI normalerweise bewerten. Normalerweise prüfen wir nur: „Lief der Code ohne Fehler durch?“ (Bestanden/Nicht bestanden).

Aber in der realen Welt ist eine Lösung, die zwar funktioniert, aber 100 Jahre braucht, um fertig zu werden, nutzlos. ALGOBENCH führt einen Complexity Verifier (Komplexitätsprüfer) ein. Es ist wie ein Schiedsrichter, der nicht nur prüft, ob das Auto die Ziellinie überquert hat, sondern wie schnell es war.

OPTT (Optimale Zeit): Hat die KI eine schnelle Lösung geschrieben?
OPTS (Optimaler Speicherplatz): Hat die KI eine Lösung geschrieben, die nicht den gesamten Computerspeicher aufbraucht?

Das Paper stellt fest, dass viele KI-Modelle die Tests zwar bestehen, aber den Geschwindigkeitscheck nicht bestehen. Sie schreiben Code, der für kleine Beispiele funktioniert, aber für die realen Anforderungen zu langsam ist.

Was sie herausgefunden haben

Als sie 7 verschiedene KI-Modelle auf diesen „Twist“-Problemen testeten, waren die Ergebnisse augenöffnend:

Leistungseinbrüche: Als die Probleme „getwistet“ wurden, sanken die Scores der KI signifikant. Dies beweist, dass die KI sich auf memorierte Vorlagen verließ, anstatt echtes Verständnis zu zeigen.
Die „Retrieval“-Falle: Wenn die Forscher der KI halfen, indem sie ihr das ursprüngliche Problem zeigten (Retrieval), wurde die KI tatsächlich schlechter im Anpassen. Sie blieb stecken beim Versuch, die alte Lösung auf das neue Problem zu erzwingen – wie der Versuch, einen quadratischen Klotz in eine runde Öffnung zu pressen.
Echtes Reasoning ist schwer: Die meisten Fehler waren keine Tippfehler oder kleine Programmierfehler. Sie scheiterten, weil sie die neue Logik nicht erfassen konnten. Sie versuchten, eine alte, langsame Methode anzuwenden, wenn eine neue, schnelle Methode erforderlich war.

Das Fazente

ALGOBENCH ist eine neue Art, KI zu testen, die verhindert, dass sie durch das Auswendiglernen alter Antworten „schummelt“. Es zwingt die KI zu zeigen, dass sie tatsächlich denken und sich an neue Regeln anpassen kann, anstatt nur ein Skript vorzutragen, das sie in der Schule gelernt hat.

Das Paper kommt zu dem Schluss, dass KIs zwar immer besser darin werden, Code zu schreiben, aber immer noch Schwierigkeiten haben, die Algorithmen hinter dem Code wirklich zu verstehen, wenn sich die Regeln ändern. Sie sind gut darin, einem Rezept zu folgen, aber sie lernen noch, wie man ein neues Gericht von Grund auf selbst kocht.

Technisches Resümee: ALGOBENCH

Problemstellung

Aktuelle Benchmarks für die Codegenerierung durch Large Language Models (LLMs), wie HumanEval und LiveCodeBench, liefern oft hohe Erfolgsraten, die jedoch nicht zwangsläufig echte algorithmische Denkfähigkeiten widerspiegeln. Eine primäre Einschränkung ist die Datenkontamination: Etablierte Problemstellungen, Editorials und Referenzlösungen sind in öffentlichen Trainingskorpora weit verbreitet. Infolgedessen können Modelle hohe Scores erzielen, indem sie memorisierte Lösungsmuster abrufen, anstatt Algorithmen aus den gegebenen Constraints abzuleiten. Während neuere Benchmarks versuchen, dies durch neuere oder schwierigere Probleme zu mildern (z. B. LiveCodeBench, ProBench, HLCE), bleiben diese statisch. Sobald sie veröffentlicht werden, gelangen ihre Problemstellungen und modellgenerierten Lösungen unweigerlich in die Trainingsdaten, was es zukünftigen Modellen ermöglicht, sich durch Exposition statt durch verbesserte Argumentation zu verbessern. Es besteht ein Bedarf an einem Benchmark, der Probleme dynamisch generiert, bei denen das Memorieren der Quelllösung unzureichend ist und die Modelle dazu zwingt, ihre algorithmischen Strategien anzupassen.

Methodik

Kernframework: ALGOBENCH

Die Autoren schlagen ALGOBENCH vor, ein Framework zur automatischen Konstruktion neuartiger algorithmischer Probleme aus bekannten Wettbewerbsprogrammierungs-Quellen. Die Kernphilosophie ist die Constraint-Shifting-Transformation: die Modifikation eines Quellproblems derart, dass der ursprüngliche Referenzalgorithmus fehlschlägt, was einen neuen algorithmischen Ansatz oder eine andere asymptotische Komplexität erforderlich macht.

1. Transformationsoperatoren
Das Framework verwendet zehn regelbasierte Transformationsoperatoren, um Varianten ( $q'$ ) aus Quellproblemen ( $q$ ) zu generieren. Diese umfassen:

Constraint Scaling (CS): Erhöhung der Eingabegrenzen (z. B. $N \le 2000 \to N \le 2 \times 10^5$ ).
Static-to-Dynamic (SD): Umwandlung statischer Probleme in dynamische Probleme (z. B. Hinzufügen von Update-Operationen).
Objective Perturbation (OP): Änderung des Optimierungsziels.
Greedy-Trap Injection (GT): Einführung von Constraints, die Greedy-Heuristiken ungültig machen und Dynamic Programming erfordern.
Weitere Operatoren sind Constraint Coupling, Edge-Case Expansion, Output Requirement Change sowie breitere Transformationen wie Real-World Wrapping und Graph-Structure Change.

2. Quality Gates (Qualitätskontrollen)
Um Validität zu gewährleisten und Trivialität zu verhindern, müssen generierte Probleme vier automatisierten Gates standhalten:

Gate 1 (Old-Solution Rejection): Die ursprüngliche Referenzlösung ( $a^*$ ) muss beim neuen Problem scheitern (erzeugt WA, TLE oder MLE).
Gate 2 (New Solution Verification): Eine neue Referenzlösung ( $\hat{a}^*$ ) muss gegen eine Brute-Force-Oracle bei kleinen Eingaben verifiziert werden.
Gate 3 (Non-Paraphrase): Die generierte Problemstellung muss hinreichend verschieden von der Quelle sein (TextSim $< \tau_{text}$ ).
Gate 4 (Complexity Certification): Die neue Lösung muss die Ziel-Zeit- und Platzkomplexität erfüllen.

3. Deterministischer Komplexitätsverifizierer
Ein dreistufiger Verifizierer bewertet eingereichte Lösungen, um zwischen funktionaler Korrektheit und algorithmischer Optimalität zu unterscheiden:

Layer 1 (Statische AST-Analyse): Parst den Code, um Zeit-/Platzkomplexität basierend auf Schleifenverschachtelung, Rekursion und Datenstrukturen zu schätzen.
Layer 2 (Algorithmus-Tag-Verifizierung): Prüft auf strukturelle Anzeichen erwarteter Algorithmen (z. B. Lazy Propagation für Segment Trees) und das Fehlen verbotener Algorithmen.
Layer 3 (Kalibrierte Laufzeit-Skalierung): Führt Lösungen auf zunehmenden Eingabegrößen aus, um ein Laufzeitmodell $T(n) = cn^\alpha (\log n)^\gamma$ anzupassen. Lösungen werden bestraft, wenn der gefittete Exponent den Zielwert um mehr als 0,15 überschreitet.

Evaluierungsmetriken

Über das Standardmaß pass@k hinaus führt ALGOBENCH komplexitätsbewusste Metriken ein:

OPTT/OPTS: Raten von Einreichungen, die korrekt und im Rahmen der Zielzeit-/Platzkomplexität sind.
TRAPRATE: Der Anteil der fehlerhaften Einreichungen, die strukturell den Quellalgorithmus wiederverwenden (indiziert die "Old-Solution Trap").
GAPT (Efficiency Gap): Misst die Differenz zwischen dem gefitteten Laufzeit-Exponenten und dem Ziel-Exponenten.
CONSENS: Misst den Leistungsabfall bei zunehmender Magnitude der Constraints.
$\Delta_{gen}$ : Der Leistungsabfall von Quellproblemen zu generierten Varianten.

Zentrale Beiträge

Framework: Einführung von ALGOBENCH, einer automatischen Pipeline zur Generierung nachvollziehbarer, aber algorithmisch distinkter Probleme.
Transformation & Validierung: Design von zehn Transformationsoperatoren und eines vierstufigen Qualitätskontrollsystems, das sicherstellt, dass generierte Probleme alte Lösungen ablehnen und neue Komplexität erfordern.
Benchmark-Datensatz: Konstruktion eines Benchmarks mit 598 akzeptierten Varianten (420 für Hauptexperimente verwendet), abgeleitet aus 300 Quellproblemen (Codeforces, AtCoder, Kattis, LeetCode Hard), inklusive Metadaten, Referenzlösungen und Brute-Force-Oracles.
Metriken: Vorschlag von Metriken (OPTT, OPTS, TRAPRATE, GAPT, CONSENS), die asymptotische Eignung bewerten, nicht nur funktionale Korrektheit.
Empirische Erkenntnisse: Evaluierung von sieben LLMs über sechs Prompting-Strategien, die zeigen, dass die Leistung bei generierten Varianten signifikant sinkt und viele "korrekte" Lösungen die Komplexitätsanforderungen verfehlen.

Experimentelle Ergebnisse

Leistungsabfall und Adaption

Generalisierungslücke: Modelle zeigen einen starken Leistungsabfall beim Übergang von Quellproblemen zu ALGOBENCH-Varianten. Ältere Modelle fielen von durchschnittlich 85,1 % pass@1 bei Quellproblemen auf 53,6 % bei Varianten. Selbst die neuesten Frontier-Modelle (GPT-5.4, Claude Opus 4.5) sanken um 33,3 %.
Komplexitäts-Mismatch: Es besteht eine signifikante Lücke zwischen pass@k und OPTT. Beispielsweise erreichte GPT-4o 72,7 % pass@5, aber nur 63,6 % OPTT, was darauf hindeutet, dass viele korrekte Lösungen suboptimalen Algorithmen verwendeten.
Retrieval-Risiken: Retrieval-Augmented Generation (RAG) unter Verwendung von Quellproblemen als Kontext erhöhte oft die TRAPRATE. Für Gemini 2.5 Flash erhöhte RAG die Trap Rate von 3,6 % auf 30,0 %, was darauf hindeutet, dass Retrieval die Modelle an die ursprüngliche (nun ungültige) Lösung bindet.

Fehleranalyse

Eine Analyse von 400 fehlgeschlagenen Einreichungen ergab, dass die Fehler überwiegend algorithmischer Natur sind und nicht auf Implementierungsebene liegen:

Old-Solution Trap (42,3 %): Modelle implementierten den Quellalgorithmus, bestanden die öffentlichen Beispiele, scheiterten aber an versteckten Trap-Tests.
Zu langsam (21,8 %): Modelle identifizierten den korrekten Ansatz, versäumten es jedoch, notwendige Optimierungen vorzunehmen (z. B. den Wechsel von $O(N^2)$ zu $O(N \log N)$ zu vollziehen).
Implementierungsfehler: Machten nur 9,0 % der Fehler aus.

Sensitivität und Kontamination

Constraint-Sensitivität: Die Leistung sank drastisch, als die Eingabegrenzen erhöht wurden (z. B. $N=10K \to 50K$ ), genau dort, wo quadratische Lösungen zeitlich ablaufen (Time Out).
Kontaminationseffekt: Modelle schnitten bei älteren Quellproblemen (2020) signifikant besser ab als bei neueren (2024), was auf Memorierung hindeutet. Diese Lücke verringerte sich jedoch bei ALGOBENCH-Varianten, die unabhängig vom Publikationsjahr des Quellproblems konsistent schwierig blieben.

Bedeutung und Behauptungen

Das Paper behauptet, dass ALGOBENCH eine distinkte Fähigkeit evaluiert, die sich von Standard-Code-Benchmarks unterscheidet: die Fähigkeit, algorithmisches Denken an neuartige Constraints anzupassen, anstatt sich auf memorierte Templates zu verlassen.

Jenseits der funktionalen Korrektheit: Der Benchmark zeigt, dass hohe Pass-Raten auf statischen Datensätzen keine asymptotische Eignung garantieren. Viele Modelle produzieren Lösungen, die zwar funktional korrekt, aber algorithmisch ineffizient sind.
Robustheit gegenüber Memorierung: Durch die automatische Generierung von Problemen, bei denen die Quelllösung fehlschlägt, mildert ALGOBENCH das Risiko der Trainingsdaten-Kontamination und bietet ein zuverlässigeres Maß für wahre algorithmische Denkfähigkeit.
Diagnostischer Wert: Das Framework identifiziert spezifische Fehlermodi (z. B. Unfähigkeit, von Greedy zu DP zu wechseln, oder das Versagen beim Umgang mit dynamischen Updates), die in traditionellen Benchmarks verborgen bleiben.

Die Autoren kommen zu dem Schluss, dass aktuelle LLMs Schwierigkeiten haben, wenn vertraute Templates nicht ausreichen, und dass zukünftiger Fortschritt im algorithmischen Denken Benchmarks erfordert, die echte Adaption statt Mustererkennung verlangen.