Hast du keine genügend schwierige Aufgaben auf Codeforces? Xie Saining und andere haben eine KI-Aufgaben-Generierungsmaschine entwickelt, die originale Programmieraufgaben erstellen kann.

Rich Sutton hat einmal gesagt: „KI kann nur innerhalb des Rahmens, in dem sie sich selbst verifizieren kann, Wissen erschaffen und aufrechterhalten.“ Albert Einstein und Leopold Infeld schrieben in ihrer gemeinsam verfassten Schrift „Die Evolution der Physik“ auch: „Das Stellen einer Frage ist oft wichtiger als das Lösen einer Frage. Letzteres mag vielleicht nur eine Frage der mathematischen oder experimentellen Technik sein. Das Stellen neuer Fragen, das Aufzeigen neuer Möglichkeiten und das Betrachten alter Fragen aus einem neuen Blickwinkel erfordert hingegen kreative Vorstellungskraft und markiert den wahren Fortschritt der Wissenschaft.“

Mit dem Fortschritt von Large Language Models (LLMs) in Richtung auf allgemeine Fähigkeiten und dem Ziel der allgemeinen Künstlichen Intelligenz (AGI) gewinnt die Prüfung ihrer Fähigkeit, Fragen zu generieren, immer mehr an Bedeutung. Dies ist insbesondere bei der Anwendung von LLMs in fortgeschrittenen Programmieraufgaben wichtig, da die zukünftige Entwicklung der Programmierfähigkeiten von LLMs und ihre wirtschaftliche Integration eine große Menge an Verifizierungsarbeit erfordern werden.

Zunächst erfordert das Erstellen von Aufgaben für Programmierwettbewerbe ein tiefgreifenderes Verständnis von Algorithmen als das Lösen von Aufgaben.

Beispielsweise können einfache Aufgaben oft auf erkennbare Muster zurückgeführt werden und mit einfachen Techniken gelöst werden. Viele Standardprogrammieraufgaben erlauben auch die Abgabe von teilweise richtigen oder vordefinierten Lösungen, was fehlerhafte Denkprozesse verbergen kann. Programmierwettbewerbsaufgaben hingegen haben strenge Standards, die darauf abzielen, ein tieferes Verständnis der zugrunde liegenden Algorithmen, Datenstrukturen und Komplexitätsabwägungen zu bewerten. Die Verifizierung einer großen Anzahl möglicher Lösungen und die vollständige Abdeckung aller möglichen Abkürzungen oder Randfälle ist äußerst herausfordernd, aber für Programmierwettbewerbsaufgaben unerlässlich. Daher beinhaltet das Erstellen von Aufgaben nicht nur alle Herausforderungen des Aufgabe-Lösens, sondern geht darüber hinaus.

Zweitens führt eine bessere Fähigkeit zur Aufgabenstellung zu strengeren Benchmarks für Programmierwettbewerbe. Da die offiziellen Testdaten von Top-Plattformen wie Codeforces und AtCoder nicht öffentlich zugänglich sind, verlassen sich Forscher derzeit auf synthetische Datensätze wie CodeContests+, TACO und HardTests.

Analysen haben jedoch gezeigt, dass die bestehenden Testdatensätze möglicherweise sowohl eine hohe Falsch-Positiv-Rate (FPR) als auch eine hohe Falsch-Negativ-Rate (FNR) aufweisen. Beispielsweise könnte ein Greedy-Algorithmus mit schlechter Zeitkomplexität eine Reihe von kleinen Zufallstests bestehen, aber bei gegenläufigen Testfällen, die auf die Aufdeckung seiner Schwächen abzielen, scheitern. Diese entscheidende Schwäche schafft eine verzerrte Bewertungsumgebung, die Modelle belohnt, die Abkürzungen finden können.

Drittens könnte das erfolgreiche Stellen neuer Herausforderungen den Weg für die Selbstverbesserung von Modellen und die AGI ebnen und gleichzeitig die Einbindung von Modellen in komplexen Softwarestapeln verifizieren.

Können wir also AI genauso trainieren, um hochwertige, sogar von Menschen nicht gedachte neue Fragen zu stellen, wie wir sie trainieren, um Probleme zu lösen? Kürzlich hat das LiveCodeBench Pro-Team eine klare Antwort gegeben: AutoCode. Dies ist ein systematisches Framework, das LLMs in einem geschlossenen, mehrrollenbasierten System nutzt, um den gesamten Lebenszyklus der Erstellung und Bewertung von Programmierwettbewerbsaufgaben zu automatisieren.

• Titel der Studie: AutoCode: LLMs as Problem Setters for Competitive Programming
• Link zur Studie: https://arxiv.org/abs/2510.12803v1
• Projektseite: https://livecodebenchpro.com/projects/autocode/overview

Es ist erwähnenswert, dass das Team Forscher aus zehn Institutionen umfasst und es insgesamt fünf Erstautoren gibt. Darüber hinaus sind in der Autorenliste auch bekannte Forscher wie Xiesainen enthalten.

Insgesamt leistet diese Studie zwei wesentliche Beiträge:

• Ein verbessertes Validator-Generator-Checker-Framework, das bei der Generierung von Testfällen einen Stand der Technik in Bezug auf Zuverlässigkeit erreicht.
• Ein innovativer Prozess zur Generierung von hochwertigen neuen Aufgaben. Dieser Prozess beginnt mit einer „Ansatzaufgabe“, um das LLM in eine vielversprechende Richtung zu lenken.

Generierung von Testfällen

Der Prozess zur Generierung von Testfällen des Teams ist ein strukturiertes Framework, das darauf abzielt, maximale Strenge und Abdeckung zu erreichen.

Wie in Abbildung 1 gezeigt, beginnt das Framework mit dem Validator, der der Grundpfeiler des gesamten Systems ist. Seine Aufgabe besteht darin, sicherzustellen, dass jede gegebene Eingabe alle in der Aufgabenbeschreibung festgelegten Einschränkungen strikt einhält. Ein Validator ist für die Minimierung der Falsch-Negativ-Rate (FNR) von entscheidender Bedeutung, da er verhindert, dass korrekte Programme bei fehlerhaft formatierten Daten scheitern.

Anschließend verwendet der Generator vielfältige Strategien, um eine breite Palette von Eingaben zu erstellen, um die Falsch-Positiv-Rate (FPR) zu reduzieren, d. h. dass fehlerhafte oder ineffiziente Programme fälschlicherweise als korrekt eingestuft werden. Alle ungültigen Fälle, die der Generator erzeugt, werden vom Validator herausgefiltert, um sicherzustellen, dass das Team eine hochwertige Menge an Eingaben erhält.

Schließlich vergleicht der Checker zur Bewertung der Ausgabe der Teilnehmer diese mit der Ausgabe der Referenzlösung.

Bei interaktiven Aufgaben führt der Interactor mehrere Runden von Dialog mit dem Programm des Teilnehmers durch, um ein endgültiges Urteil zu fällen.

Da eines der Hauptziele des Teams darin besteht, hochwertige Validatoren für RLVR (Reinforcement Learning from Verified Results) bereitzustellen, legt das Team besonderen Wert auf die Reduzierung der Falsch-Positiv-Rate (FPR). Das Team unterscheidet zwischen Testfällen (Eingabe-Antwort-Paaren) und Testdaten, letztere umfassen auch die für die Bewertung erforderlichen Checker- und Interactor-Programme.

Benchmarking: Robustheit der Testfälle

Um das Framework zur Generierung von Testfällen des Teams streng zu bewerten, haben sie zwei verschiedene Benchmarks erstellt.

Der Hauptbenchmark umfasst 7.538 Aufgaben, die aus dem Schnitt bekannter existierender Datensätze stammen: CodeContests+, CodeContests, HardTests und TACO.

Es ist bemerkenswert, dass diese umfangreiche Sammlung keine interaktiven Aufgaben enthält und aufgrund der inhärenten Filterung dieser Datensätze die durchschnittliche Schwierigkeit der Testdatengenerierung etwas geringer ist als bei einem typischen Codeforces-Wettbewerb.

Um dieses Problem zu lösen und das neue System unter anspruchsvolleren realen Bedingungen zu testen, hat das Team einen zweiten Benchmark erstellt, der 720 aktuelle, bewertete Aufgaben aus Codeforces-Wettbewerben umfasst. Diese Sammlung ist vollständig unbefiltert und enthält auch diejenigen interaktiven Aufgaben, die für ihre Schwierigkeit bekannt sind, sowie Aufgaben, die komplexe, strukturierte Testdaten erfordern. Das Team hat angegeben, dass es nicht möglich war, frühere Methoden an diesem neueren Benchmark zu bewerten, da deren Codebasis zur Datengenerierung nicht öffentlich zugänglich ist.

Die Bewertung des Teams basiert auf drei Schlüsselindikatoren:

• Übereinstimmung (Consistency) misst den Gesamtprozentsatz der Übereinstimmung zwischen den Urteilen des Teams und den offiziellen Urteilen. Das Team hat die inkonsistenten Fälle weiter in zwei Schlüsselfehlerraten aufgeteilt.
• Falsch-Positiv-Rate (FPR) ist definiert als der Anteil der offiziell falschen Lösungen, die von den generierten Tests des Teams fälschlicherweise akzeptiert werden.
• Falsch-Negativ-Rate (FNR) ist der Anteil der offiziell richtigen Lösungen, die von den Tests des Teams fälschlicherweise abgelehnt werden.

Vergleich mit anderen Benchmarks

Das Team hat AutoCode an einem Benchmark mit 7.538 Aufgaben mit vier führenden Benchmarks verglichen.

Wie in Tabelle 1 gezeigt, hat das Framework des Teams eine Übereinstimmung von 91,1 % mit den offiziellen Urteilen erreicht. Dies markiert einen großen Sprung vorwärts, da frühere Methoden eine Übereinstimmung von nicht mehr als 81,0 % erreicht haben. Wichtig ist, dass AutoCode die Falsch-Positiv-Rate (FPR) drastisch auf nur 3,7 % und die Falsch-Negativ-Rate (FNR) auf 14,1 % reduziert hat, was bedeutet, dass beide Indikatoren im Vergleich zum aktuellen Stand der Technik um etwa 50 % gesunken sind.

Abbildung 2 zeigt die Verteilung der fehlerhaften Urteile und zeigt, dass die Urteile bei den meisten Aufgaben mit den tatsächlichen Urteilen übereinstimmen.

Um die Robustheit des Systems weiter zu testen, hat das Team auch einen anspruchsvolleren Benchmark zusammengestellt, der 720 aktuelle, unbefilterte Codeforces-Aufgaben, einschließlich komplexer interaktiver Aufgaben, umfasst.

Wie in Tabelle 2 gezeigt, behält AutoCode seine hervorragende Leistung bei und erreicht eine Übereinstimmung von 98,7 %. Dieses Ergebnis bestätigt die Wirksamkeit der Methode des Teams bei modernen, schwierigen Aufgaben, bei denen frühere Methoden nicht bewertet werden konnten.

Das Team hat auch die Wirksamkeit der Methode durch Ablationsstudien verifiziert.

Nachdem das Team eine so starke Fähigkeit zur Generierung von Testfällen aufgebaut hat, richteten die Forscher ihren Blick auf eine kreativere Aufgabe: die direkte Generierung von völlig neuen, hochwertigen Aufgaben.

Aufgabenstellung

Das neu vorgeschlagene Framework zur Aufgabenstellung des Teams baut auf dem zuvor beschriebenen robusten Testgenerierungsframework (wie in Abbildung 1 gezeigt) auf, führt jedoch ein wichtiges Doppelverifizierungsprotokoll ein, um die Richtigkeit ohne menschliche Intervention sicherzustellen.

Jede generierte Aufgabe wird von führenden menschlichen Wettbewerbsprogrammierern anhand einer 6-stufigen Skala bewertet. Das Team hat 8 menschliche Experten zur Aufgabenstellung befragt, und alle haben angegeben, dass sie bei der Erstellung neuer Aufgaben oft auf eine bestimmte bestehende Aufgabe zurückgreifen. Indem sie bestimmte Bedingungen einer solchen „Ansatzaufgabe“ hinzufügen, entfernen oder ändern, können sie neue, oft schwierigere Aufgaben schaffen, die neue Einsichten erfordern.

Angeregt durch ihre Erkenntnisse wählt das Team zunächst zufällig eine Codeforces-Aufgabe (Schwierigkeitsbewertung unter 2200) als „Ansatzaufgabe“ aus. Die Aufgabe des LLMs besteht darin, durch Hinzufügen, Entfernen oder Ändern bestimmter Bedingungen dieser Ansatzaufgabe eine neue Aufgabe zu generieren und gleichzeitig eine effiziente Referenzlösung (std.cpp) und eine Brute-Force-Lösung (brute.cpp) bereitzustellen.