Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization

Pedro Orvalho, Mikolás Janota, Vasco M. ManquinhoAAAI 2025 · DOI

TL;DR

This paper introduces a novel approach to automatically repair introductory programming assignments (IPAs) by combining the strengths of formal methods (MaxSAT-based fault localization) and large language models (LLMs) through zero-shot learning. By providing LLMs with "bug-free program sketches" and guiding them with counterexamples, the method significantly improves repair capabilities, leading to more programs fixed with smaller, more educational patches.

What Problem Does This Paper Address?

The explosion of students in introductory programming courses presents a significant challenge for educators: providing timely and personalized feedback on assignments. Manually grading and debugging thousands of student programs is time-consuming and resource-intensive. Automated Program Repair (APR) offers a potential solution, but existing methods have limitations. Traditional formal methods-based APR tools are often slow and struggle when the buggy code significantly deviates from the correct implementation. On the other hand, Large Language Models (LLMs) are fast and adept at code generation, but they tend to produce overly broad "fixes" that rewrite large portions of code, hindering student learning by obscuring the original mistakes. This paper aims to bridge this gap by developing an APR system that leverages the precise fault localization of formal methods with the generative power of LLMs, while ensuring repairs are minimal and educational.

Methods

The core of this work lies in a hybrid approach that combines MaxSAT-based fault localization with LLM-driven synthesis within a Counterexample Guided Inductive Synthesis (CEGIS) loop.

  1. MaxSAT-based Fault Localization: The process begins by using MaxSAT (Maximum Satisfiability) techniques to pinpoint the minimal set of "buggy statements" within a student's program. This is achieved by encoding the program's behavior against a test suite into a MaxSAT problem.
  2. Program Sketch Generation: Instead of feeding the LLM the entire buggy program, the identified buggy lines are replaced with placeholders (e.g., @ HOLE @), creating a "program sketch." This sketch, along with the problem description and test suite, forms the prompt for the LLM.
  3. Zero-Shot LLM Synthesis: The LLM, without any task-specific fine-tuning (zero-shot learning), is tasked with synthesizing the missing code to fill these holes.
  4. CEGIS Loop:
    • Verification: The synthesized program is evaluated against the test suite.
  5. Counterexample Generation: If the program fails any test case, a "counterexample" (an input-output pair that reveals the failure) is generated.
  6. Iterative Refinement: This counterexample is then fed back to the LLM in a subsequent prompt, guiding it to refine its synthesis and produce a more accurate fix. This iterative process continues until the program passes all tests.

This approach contrasts with traditional LLM-based APR, which might simply be given the buggy code and asked to fix it, or with formal methods that require significant structural similarity between buggy and correct code.

Datasets

The evaluation was performed on C-PACK-IPAS, a dataset comprising 1431 semantically incorrect student C programs that compile but fail at least one test case. This dataset is described as a benchmark of introductory programming assignments.

Key Insights and Ideas

  • The Power of "Less is More" for LLMs: LLMs are powerful, but simply asking them to "fix this code" often leads to overly aggressive rewrites. By providing them with a structured "sketch" and focusing their attention on specific "holes," we can elicit more precise and minimal repairs.
  • Formal Methods as a Precise Guide: MaxSAT-based fault localization provides a rigorous way to identify exactly where the bugs are, allowing for targeted repairs rather than broad guesswork. This is crucial for making LLM fixes educational.
  • Counterexamples are Key for Iterative Improvement: The CEGIS loop, powered by counterexamples, is essential for refining LLM outputs. It transforms LLMs from one-shot code generators into iterative problem solvers, much like human programmers.
  • Reference Implementations: A Double-Edged Sword: While providing a reference implementation can boost the number of programs repaired by LLMs, it often leads to the LLM simply copying the reference, rather than truly understanding and fixing the original bug. This highlights the importance of evaluating repair quality (e.g., using Tree Edit Distance) beyond just success rate.

Key Results

  • The proposed approach significantly improves the repair capabilities of all six evaluated LLMs.
  • The method enables LLMs to repair more programs and produce smaller, more precise fixes compared to other configurations and state-of-the-art symbolic program repair tools.
  • Configurations using bug-free program sketches (SK) and incorporating counterexamples (CE) generally yielded better results.
  • When reference implementations were excluded, the approach still outperformed other methods, demonstrating the robustness of the sketch-based guidance.
  • The Tree Edit Distance (TED) analysis revealed that while reference implementations increased repair rates, they also sometimes led to LLMs replicating the reference code, resulting in a TED of zero, indicating a lack of genuine repair.

Limitations and Future Work

  • LLM Replication of Reference Implementations: A significant limitation noted is that LLMs, when provided with reference implementations, tend to copy them rather than perform genuine repairs. This suggests a need for further research into methods that discourage direct replication while still leveraging the reference for guidance.
  • Generalizability of Counterexample Effectiveness: The effectiveness of counterexamples varied across different LLMs, suggesting that their impact might depend on the LLM's training data and architecture. Future work could explore how to make counterexample guidance more universally beneficial.
  • Scalability to More Complex Programs: While successful for introductory programming assignments, the approach's scalability to more complex, real-world software remains an open question.
  • Future Directions: The authors suggest exploring more sophisticated prompt engineering techniques, investigating the impact of different LLM architectures, and further refining the CEGIS loop for even more efficient and accurate repairs. The potential for combining this approach with other formal methods or static analysis techniques is also a promising avenue.

Summary updated

BibTeX
@inproceedings{orvalho2025counterexample,
  author = {Pedro Orvalho and Mikolás Janota and Vasco M. Manquinho},
  title = {{Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i1.32046},
}
Figure