Counterexamples as Feedback for Agent Self-Correction
Authors: Sidhesh Badrinarayan, Adithya Parthasarathy
Publication: arXiv:2609.02892 [cs.CL], Submitted 1 July 2026
Abstract
Single-turn code-generation metrics fail to capture a critical property of deployed AI agents: their ability to repair incorrect artifacts after receiving concrete, actionable feedback. In response, this paper introduces A-CEGIS, a lightweight framework that leverages counterexamples as feedback to evaluate multi-turn refinement in natural-language-to-regex synthesis. The agent proposes a regex, a deterministic oracle assesses it under full-match semantics, and concise false-positive or false-negative witnesses guide subsequent turns. On 30 NL-RX-Turk tasks, diagnostic counterexample feedback resolves 90% of tasks within a four-turn ablation budget, outperforming zero-shot generation (17%), generic self-correction (27%), and error-only feedback (23%). In a full diagnostic run with hardening, all tasks are solved on the hidden set by the final turn, achieving a mean time-to-success of 2.7 turns and a robust success rate of 77% after targeted probing. These results demonstrate that A-CEGIS effectively measures how efficiently an agent improves across turns while providing a practical robustness check beyond the initial held-out cases.
Introduction
The evaluation of code-generation models has traditionally centered on single-turn benchmarks, which assess whether a model can produce a correct artifact in one shot. However, deployed agents in real-world scenarios often operate in multi-turn environments where they receive feedback, iterate, and refine their outputs. This discrepancy underscores the need for evaluation frameworks that capture the dynamics of agent self-correction.
The A-CEGIS Framework
A-CEGIS (Counterexample-Guided Evaluation for Iterative Synthesis) is designed to fill this gap. It provides a lightweight yet robust mechanism for assessing an agent's ability to improve over multiple turns. Key components include:
- Agent Proposal: The agent generates a candidate regex based on the natural-language specification.
- Oracle Validation: A deterministic oracle checks the proposed regex under full-match semantics against the input-output examples.
- Counterexample Feedback: The oracle provides compact false-positive or false-negative witnesses, which serve as diagnostic signals for the agent's next iteration.
This iterative loop continues until the agent solves the task or reaches a predefined turn budget.
Experimental Setup
To evaluate A-CEGIS, we used the NL-RX-Turk benchmark, which consists of 30 natural-language-to-regex tasks. We compared the performance of our framework against several baselines, including:
- Zero-Shot Generation: The agent produces a regex in a single attempt without any feedback.
- Generic Self-Correction: The agent revises its output based on generic guidance (e.g., "try again").
- Error-Only Feedback: The agent receives feedback indicating whether an error occurred, but without specific counterexamples.
Each method was evaluated within a four-turn ablation budget to assess efficiency and success rates.
Results and Findings
Our experiments reveal significant advantages of counterexample-driven feedback:
- With A-CEGIS, agents solved 90% of tasks within the four-turn budget, compared to 17% for zero-shot generation, 27% for generic self-correction, and 23% for error-only feedback.
- In a full diagnostic run with hardening (where the agent is evaluated on a hidden set of tasks), all tasks were solved by the final turn. The mean time-to-success was 2.7 turns, indicating rapid convergence.
- After targeted probing (adversarial intervention to test robustness), the agent maintained a 77% success rate, demonstrating resilience against extraneous perturbations.
These findings underscore the importance of counterexample-based feedback in facilitating efficient and effective self-correction.
Conclusion
A-CEGIS offers a valuable framework for evaluating multi-turn agent performance, moving beyond single-turn metrics to capture the iterative nature of real-world problem-solving. By providing concrete, actionable counterexamples, it enables agents to identify and rectify errors more efficiently, while also serving as a practical robustness check. Future work will explore extending A-CEGIS to other synthesis tasks and integrating it into larger agent pipelines.
References
- arXiv:2609.02892 [cs.CL]. Available at: https://arxiv.org/abs/2609.02892
Keywords: code generation, multi-turn refinement, counterexample feedback, natural-language-to-regex synthesis, agent self-correction, robustness evaluation
via ArXiv CL+LG