TLDR: AutoCode is a new framework that uses large language models (LLMs) to automatically create and evaluate competitive programming problems. It features a Validator-Generator-Checker system for highly reliable test case generation, achieving over 98% consistency with official judgments on challenging benchmarks. AutoCode can also generate novel, contest-quality problems, validated by human experts, by adapting existing ‘seed problems’ and using a dual-verification protocol. The research highlights LLMs’ strengths in combining existing knowledge for problem creation but also points out their current limitations in truly novel reasoning and self-assessment of problem quality.
Creating challenging and fair problems for competitive programming contests is a highly demanding task. It requires authors to meticulously define constraints, input distributions, and edge cases that prevent shortcuts, while also targeting specific algorithms and calibrating complexity to be just beyond the reach of most competitors. This intricate process makes problem setting an ideal test for the advanced capabilities of large language models (LLMs).
A new research paper, AutoCode: LLMs as Problem Setters for Competitive Programming, introduces a novel framework called AutoCode. This system leverages LLMs in a sophisticated, closed-loop, multi-role setup to automate the entire lifecycle of competitive programming problem creation and evaluation. The goal is to determine if LLMs can reliably generate competition-grade problems and test cases.
The AutoCode Framework: A Multi-Role System
AutoCode operates on a Validator-Generator-Checker framework, which is enhanced with several key heuristics to ensure robustness and accuracy. This framework mirrors the meticulous process human experts follow when designing programming contest problems.
First, the **Validator** is the cornerstone, ensuring that any generated input strictly adheres to all problem constraints. This is crucial for preventing correct solutions from being unfairly rejected due to malformed data. AutoCode guides the LLM to generate a targeted suite of 40 test cases, including valid and ‘near-valid’ illegal inputs, to rigorously test the Validator’s robustness. The best-performing Validator out of several candidates is then selected.
Next, the **Generator** is tasked with maximizing test coverage by creating a diverse and challenging set of test cases. It employs a multi-pronged strategy:
- **Small Data Exhaustion:** For problems with small constraints, it explores all permutations and combinations of small-scale data to cover fundamental boundary conditions.
- **Randomized and Extreme Data:** It generates large-scale random inputs to stress-test solutions, pushing integer limits, testing floating-point precision, and designing adversarial cases to expose flaws in common greedy algorithms or induce hash collisions.
- **TLE-Inducing Data:** To catch solutions with incorrect time complexity, it constructs inputs designed to maximize computational load, ensuring only efficient solutions pass.
The **Checker** is responsible for determining the final verdict of a submission by comparing its output with the reference solution’s output. Similar to the Validator, the LLM generates multiple candidate Checkers, which are then evaluated against a set of 40 test cases (each with valid input, a reasonable but potentially incorrect output, the correct output, and the expected verdict) to select the most accurate one.
For interactive problems, AutoCode introduces an **Interactor**. This component engages in a real-time dialogue with a contestant’s program. A novel mutant-based discrimination process is used, where the LLM creates slightly incorrect ‘mutant’ programs from the reference solution. The Interactor that successfully passes the correct reference solution while failing the maximum number of mutants is chosen, proving its ability to robustly probe for specific logic.
Generating Novel and High-Quality Problems
Beyond test case generation, AutoCode pioneers a systematic process for generating new, high-quality problems. This process begins with a ‘seed problem’ (a random Codeforces problem with a difficulty rating less than 2200) to inspire the LLM. The LLM then generates a new problem by modifying conditions from the seed, along with an efficient reference solution and a simple brute-force solution.
A critical dual-verification protocol ensures correctness without human intervention: a comprehensive set of test data is constructed, and both the brute-force and efficient solutions are executed on it. A problem is only accepted if both programs’ outputs are consistent across all test cases. This process successfully filters out a significant portion of error-prone problems, raising the correctness rate of LLM-provided solutions from 86% to 94%.
Also Read:
- Evaluating AI’s Ability to Build Interactive Science Demos
- AI-Generated Software Contracts Enhance Bug Detection and Verification
Performance and Insights
AutoCode demonstrates state-of-the-art reliability in test case generation. On a large-scale benchmark of 7538 problems, it achieves 91.1% consistency with official judgments, a significant improvement over existing methods (which don’t surpass 81.0%). It also substantially reduces the False Positive Rate (FPR) to 3.7% and the False Negative Rate (FNR) to 14.1%, representing approximately a 50% decrease in both metrics. On a more challenging benchmark of 720 recent Codeforces problems, AutoCode maintains exceptional performance, achieving 98.7% consistency.
Human experts, including Grandmaster-level competitive programmers, judged the novel problems generated by AutoCode. Over 61.6% were deemed of sufficient quality for large language model training, and 3.2% were considered contest-quality, suitable for ICPC/IOI-level competitions.
The research also provides fascinating insights into LLM problem generation:
- LLMs can generate solvable problems that they themselves are unable to solve (about 4.2% of problems).
- LLMs tend to create new problems by combining existing algorithmic knowledge and frameworks, rather than proposing entirely new problem models requiring original solution strategies.
- Novel problems generated by LLMs tend to have a larger difficulty gain over their seed problems. High-quality problems are predominantly generated when the seed problem is moderately difficult.
- There is a significant divergence between human and LLM judgments of problem quality and novelty, with almost no correlation. However, LLMs show high within-group consistency.
- The difficulty of the generated problem and the difficulty gain over the seed problem serve as better indicators of problem quality than LLM self-evaluations.
In conclusion, AutoCode represents a significant advancement in leveraging LLMs for competitive programming. By providing a robust framework for test case generation and a novel process for creating contest-quality problems, it opens new avenues for automated problem setting and potentially for self-improving AI models in the future.
