💬 NLP

Scaling Agentic Verifier for Competitive Coding

The paper introduces Agentic Verifier, an execution-based agent that actively generates discriminative test inputs through multi-turn reasoning and reinforcement learning to significantly improve the accuracy of large language models in competitive programming by effectively identifying and filtering out incorrect candidate solutions.

Original authors: Zeyao Ma, Jing Zhang, Xiaokang Zhang, Jiaxi Yang, Zongmeng Zhang, Jiajun Zhang, Yuheng Jing, Lei Zhang, Hao Zheng, Wenting Zhao, Junyang Lin, Binyuan Hui

Published 2026-02-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zeyao Ma, Jing Zhang, Xiaokang Zhang, Jiaxi Yang, Zongmeng Zhang, Jiajun Zhang, Yuheng Jing, Lei Zhang, Hao Zheng, Wenting Zhao, Junyang Lin, Binyuan Hui

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "One-Shot" Guessing Game

Imagine you are a genius chef (a Large Language Model) trying to recreate a complex dish based on a recipe description. Sometimes, you get it perfect on the first try. But often, you might miss a subtle detail, like using salt instead of sugar, or forgetting a step.

In the world of competitive programming (solving hard logic puzzles with code), even the smartest AI chefs struggle to get the answer right 100% of the time in a single attempt.

To fix this, researchers usually ask the AI to cook the dish 64 times (generating 64 different solutions) and then pick the best one. But how do you know which one is actually good if you don't have the "official answer key" handy?

The Old Way: Throwing Darts Blindly

The traditional method for checking these 64 solutions is called Execution-Based Verification. You take the 64 code recipes and run them against some test ingredients (inputs).

The Flaw: The old method was like throwing darts at a giant wall of possible ingredients to see which ones reveal a mistake. It just picked random ingredients (e.g., "What if the number is 5?" "What if it's 100?").
The Result: Most of these random ingredients are too easy. They don't catch the subtle mistakes. You might run 64 tests, and all 64 wrong solutions still look perfect because none of the tests were tricky enough to expose their errors. It's like trying to find a crack in a diamond by tapping it with a feather; you need a hammer.

The New Solution: The "Detective Chef" (Agentic Verifier)

The authors of this paper built a new tool called the Agentic Verifier. Think of this not as a random dart-thrower, but as a super-smart detective or a tough food critic.

Instead of guessing random ingredients, this detective:

Looks at two different solutions side-by-side.
Thinks deeply about how they work.
Actively hunts for the one specific ingredient that will make the two solutions behave differently.

If Solution A says "The answer is 10" and Solution B says "The answer is 12," the detective doesn't just pick a random number. It asks, "What specific input will force Solution A to crash or give a wrong answer while Solution B stays correct?" It keeps asking questions and testing until it finds that "smoking gun" input.

How They Trained the Detective

You can't just tell a computer to "be smart." You have to train it. The authors used a three-step training camp:

Data Synthesis (The Practice Kitchen): They created thousands of fake cooking problems and pairs of "good" and "bad" solutions.
Rejection Fine-Tuning (The Elimination Round): They let the AI try to find the tricky ingredients. If it failed to find a difference, that attempt was thrown in the trash. Only the successful attempts were kept to teach the AI what "good detective work" looks like.
Agentic Reinforcement Learning (The Championship): They gave the AI a reward system. If it found an input that exposed a difference between two solutions, it got a point. If it failed, it got a penalty. Over time, the AI learned to become incredibly efficient at finding those "smoking gun" inputs.

The Results: Smarter Tests, Better Winners

When they tested this new "Detective Chef" against the old "Random Dart-Thrower":

Efficiency: The detective found the mistakes much faster. It didn't need to run hundreds of tests; it found the right test to run.
Accuracy: On hard puzzles (like those from the USACO or ICPC competitions), the new method improved the AI's success rate by 10–15%. That is a massive jump in this field.
Scaling: The more "thinking time" and test inputs they gave the detective, the better it got. It didn't hit a wall like the old methods did.

A Bonus Discovery: The "Imperfect Judge"

The paper also found something interesting about the competitions themselves. The official test cases used by these competitions are actually imperfect.

Sometimes, a solution is technically "wrong" (it fails on inputs the competition didn't test), but it passes the official tests and gets a gold medal. The Agentic Verifier acts like a truth-teller that can find these "fake winners" by generating new, tricky tests that the official judges missed. It shows that even the "answer keys" in these competitions aren't perfect, and this new tool can help find the truly correct code.

Summary

In short, the paper says: "Stop guessing random test cases to check AI code. Instead, train an AI detective to actively hunt for the specific, tricky tests that reveal the truth. This makes finding the best code much faster and much more accurate."

Technical Summary: Scaling Agentic Verifier for Competitive Coding

Problem Statement

While Large Language Models (LLMs) have demonstrated strong capabilities in program synthesis, they frequently struggle to solve competitive programming problems correctly in a single attempt. A common strategy to improve accuracy is test-time scaling, where multiple candidate solutions are sampled and a verifier selects the best one.

Existing verification methods face significant limitations in the context of competitive programming:

Full Test Case Generation: Generating complete test cases (inputs + ground-truth outputs) is often as difficult as solving the original problem, making it computationally expensive and unreliable.
Input-Only Execution: Recent approaches generate only valid test inputs and select solutions based on output agreement (voting). However, these methods typically rely on random input sampling.
Inefficiency of Random Sampling: The space of valid inputs in competitive programming is vast, but only a small fraction are "discriminative" (i.e., capable of exposing behavioral differences between correct and incorrect solutions). The paper's preliminary experiments demonstrate that scaling the number of random inputs yields diminishing returns and fails to close the performance gap compared to ground-truth test cases.

Methodology: Agentic Verifier

The authors propose Agentic Verifier, an LLM-based agent designed to actively reason about program behaviors and search for highly discriminative test inputs that expose discrepancies among candidate solutions.

Core Mechanism

Instead of blind random sampling, the verifier engages in multi-turn interaction with a code execution environment:

Task Formulation: Given a problem $Q$ and a pair of candidate solutions $(C_a, C_b)$ , the agent's goal is to generate an input generator program $G$ that produces a valid input $x$ where $Exec(C_a, x) \neq Exec(C_b, x)$ .
Interaction Loop: The agent iteratively proposes inputs, executes candidate solutions, inspects feedback (runtime errors, outputs), and refines its hypotheses to discover counterexamples.
Selection Strategy: At inference time, the trained verifier generates targeted test inputs for pairs of candidate solutions. These inputs are used in an execution-based voting strategy to select the final solution.

Training Pipeline

The verifier is trained via a scalable three-stage pipeline:

Large-Scale Data Synthesis: The authors construct a dataset of competitive programming problems with labeled solutions. For problems lacking ground-truth test cases, they synthesize high-quality test suites using a consensus-based majority voting mechanism across multiple reference solutions to ensure reliability.
Rejection Fine-Tuning: Using a strong teacher model (Qwen3-235B), they collect successful multi-turn interaction trajectories where the agent successfully generates distinguishing inputs. The base model is fine-tuned on these high-quality trajectories, masking initial prompts and feedback to learn effective interaction patterns.
Agentic Reinforcement Learning (RL): The verifier is further optimized using GRPO (Group Relative Policy Optimization). The reward function is sparse and outcome-based:
- $+1$ : Valid input that distinguishes the two solutions.
- $0$: Valid input that does not distinguish (solutions agree).
- $-1$: Invalid input or empty generator.
  The training curriculum prioritizes "hard negative" pairs where distinguishing inputs are rare, encouraging the agent to learn targeted generation behaviors.

Key Contributions

Empirical Analysis: The paper empirically demonstrates that random input generation is highly inefficient for input-only execution-based verification, revealing a substantial performance gap compared to discriminative test inputs.
Agentic Verifier: Introduction of an agent that actively generates highly discriminative test inputs through multi-turn interaction, moving beyond static or random sampling.
Scalable Training Pipeline: A novel pipeline combining data synthesis, rejection fine-tuning, and agentic reinforcement learning to train the verifier.
Test-Time Scaling: Demonstration that the proposed method benefits continuously from increased test-time computation, scaling effectively with both the number of candidate solutions and the number of generated inputs.

Experimental Results

The approach was evaluated on five competitive programming benchmarks (USACO, LiveCodeBench, OJBench, ICPC-Eval, and a new CodeForces benchmark) using two policy models (Qwen3-30B and Qwen3-235B).

Performance Gains: The Agentic Verifier consistently outperformed strong baselines, including random input generation, model-generated test cases (CodeT, CodeRM), and reward-model-based selection.
- Achieved absolute gains of +10–15% in Best@k accuracy over strong execution-based baselines.
- On the OJBench "Hard" subset, the trained 30B verifier improved performance by +34.1% over the baseline, significantly outperforming a zero-shot 235B model.
Scaling Behavior: Unlike baselines that showed early saturation, the Agentic Verifier exhibited clear test-time scaling behavior, with performance improving steadily as the number of test inputs increased.
Zero-Shot vs. Trained: Zero-shot LLMs provided some improvement, but the task-specific trained verifier significantly outperformed them, even when the trained model was 7x smaller than the zero-shot counterpart.

Significance and Claims

The paper claims that the effectiveness of execution-based voting is determined primarily by the discriminative quality of test inputs rather than their sheer quantity.

Beyond improving Best-of-N selection, the authors highlight a broader implication: Benchmark test suites are imperfect verifiers. Fixed test suites cover only a limited portion of the valid input space, leading to false positives where incorrect solutions pass all benchmark tests. The Agentic Verifier can actively expose these failures by discovering targeted counterexamples. Thus, the authors position the verifier not merely as a reranking tool, but as a complementary correctness-checking mechanism that can expand input coverage and mitigate benchmark-induced noise in large-scale code evaluation.