Research map / Large language models / Agents, code and math
Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Combines MaxSAT-based fault localization (CFaults) with open LLMs in a zero-shot counterexample-guided (CEGIS) loop that gives bug-free program sketches to repair introductory C programming assignments.
Problem
Automated program repair for introductory programming assignments: symbolic FM-based repair tools (Clara, Verifix) fail on control-flow mismatches, while LLMs often rewrite code extensively rather than making minimal fixes.
Approach
Use MaxSAT-based fault localization to mask minimal buggy statements as holes in a program sketch, then have an off-the-shelf LLM fill the holes zero-shot inside a CEGIS loop where failing test cases are fed back as counterexamples; repair quality is also scored by a tree-edit-distance-based distance score.
Key results
- Portfolio of all configurations without reference implementation repairs 1013 of 1431 programs (70.8%), versus 240 deemed-repairable by Clara's 495 (34.6%) and Verifix's 91 (6.3%) within 90 s.
- Granite with Sk_De-TS-CE-RI repairs 876 programs (61.2%) but many repairs copy the reference implementation; without reference, Granite Sk_De-TS repairs 691 (48.3%).
- On the 738 programs Clara fails on control-flow mismatches, Granite with Sk_De-TS repairs 290 (37.0%), the best LLM configuration on that subset.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add MaxSAT-localized sketches to a basic description-and-test-suite prompt (ablation) | LLM-driven repair · student programs | programs fixed: CodeGemma: 597 (41.7%) -> 682 (47.7%); CodeLlama: 492 (34.4%) -> 573 (40.0%); Gemma: 496 (34.7%) -> 532 (37.2%); Granite | Helped |
| Add a counterexample to the description, test-suite, and sketch prompt (ablation) | CodeGemma · student programs | programs fixed: 682 (47.7%) -> 688 (48.1%) | Helped |
| Add a counterexample to the description, test-suite, and sketch prompt (ablation) | Granite · student programs | programs fixed: 691 (48.3%) -> 681 (47.6%) | Hurt |
| Add a counterexample to the description, test-suite, and sketch prompt (ablation) | LLMs across configurations · student programs | programs fixed: Portfolio (All LLMs): 900 (62.9%) -> 907 (63.4%); CodeLlama: 573 (40.0%) -> 561 (39.2%); Phi3: 547 (38.2%) -> 535 (37.4% | Mixed |
| Add reference implementations to prompts (ablation) | Portfolio (All Configurations) · student programs | programs fixed: 1013 (70.8%) -> 1190 (83.2%) | Helped |
| Add reference implementations to the sketch, description, test-suite, and counterexample prompt (ablation) | Granite · student programs | sum(Distance Score): 533.6 -> 334.5 | Hurt |
| Add reference implementations to the sketch, description, test-suite, and counterexample prompt (ablation) | Granite · student programs | programs fixed: 681 (47.6%) -> 876 (61.2%) | Helped |
| Replace the buggy program with a MaxSAT-localized sketch (ablation) | LLM-driven repair · student programs | programs fixed: The paper reports higher success for sketches than basic prompts across all six LLMs. | Helped |
| Use reference implementations in place of prompts without them (ablation) | LLM-driven repair · student programs | patch size | Hurt |
| Add a counterexample-guided loop (ablation) | LLM-driven repair · student programs | repair accuracy | Helped |
| Use sketch prompts with description and test suite instead of Clara | Granite · student programs where Clara fails due to control-flow issues | programs fixed: 290 (37.0%) vs. 0 | Helped |
| Use sketch-based prompts instead of symbolic semantic repair | LLM-driven repair · student programs | programs fixed: Clara: 495 programs (34.6%); Verifix: 91 programs (6.3%) | Helped |
Surprising findings
- LLMs given a reference implementation often simply copy it, so high repair counts with reference implementations come with large, non-minimal changes.
- Using the best configuration per LLM, the repair rate of CodeGemma drops from 76.5% on simple programs to 14.4% on the most complex programs, and all models struggle above cyclomatic complexity 7.
Limitations
- Relies on open ~7B-8B models quantized to 4-bit; closed models such as GPT not evaluated.
- Results with reference implementation show LLMs often copy the reference, reducing the minimality of fixes.
- Evaluated on a single C introductory programming benchmark with a single FL tool (CFaults).
Experimental setup
Datasets: student C programs from an introductory programming course (1431 semantically incorrect programs)
Benchmarks: 1431 incorrect student C programs
Metrics: number of programs repaired sum of distance score based on tree edit distance repair rate by cyclomatic complexity quartile
Baselines: Clara Verifix Granite CodeGemma CodeLlama Gemma Llama3 Phi3
Builds on: CEGIS CFaults Clara Verifix
Closest papers by meaning
- Less Is More: Adaptive Program Repair with Bug Localization and Preference Learning (AAAI 2025 · similarity 0.90)
- Code Repair with LLMs gives an Exploration-Exploitation Tradeoff (NeurIPS 2024 · similarity 0.88)
- AuPair: Golden Example Pairs for Code Repair (ICML 2025 · similarity 0.86)
- NExT: Teaching Large Language Models to Reason about Code Execution (ICML 2024 · similarity 0.86)
- CoRe: Benchmarking LLMs’ Code Reasoning Capabilities through Static Analysis Tasks (NeurIPS 2025 · similarity 0.85)
- SWT-Bench: Testing and Validating Real-World Bug-Fixes with Code Agents (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.