PaperlayerView exact revision on arXiv

Source-linked AI summary

ThinkRepair: Self-Directed Automated Program Repair

Xin Yin, Chao Ni, Shaohua Wang, Zhenhao Li, Limin Zeng, Xiaohu Yang

arXiv:2407.20898v1cs.SE

TL;DR

APR approaches have limitations on bugs requiring analysis and reasoning about program logic, while LLM repair depends on prompt quality and manually constructing high-quality prompts is costly. ThinkRepair collects chains of thought into a knowledge pool, selects examples for few-shot learning, and interacts with an LLM using optional testing feedback. ThinkRepair fixed 98 bugs on Defects4J V1.2, improving baselines by 27%∼344.4%, and fixed 12∼65 more bugs than SOTAs on Defects4J V2.0.

  • Problem

    APR approaches have limitations on bugs requiring analysis and reasoning about program logic, while LLM repair depends on prompt quality and manually constructing high-quality prompts is costly.

    Source: §1 · p. 1, §2.1 · p. 2

  • Method

    ThinkRepair collects chains of thought into a knowledge pool, selects examples for few-shot learning, and interacts with an LLM using optional testing feedback.

    Source: §1 · p. 2

  • Results

    ThinkRepair fixed 98 bugs on Defects4J V1.2, improving baselines by 27%∼344.4%, and fixed 12∼65 more bugs than SOTAs on Defects4J V2.0.

    Source: §1 · p. 2

  • Takeaways & Limitations

    ThinkRepair's results are described as comparable and complementary to other APR directions, including bugs that SOTAs could not fix.

    Source: §1 · p. 2

    The authors caution that effectiveness observed with ThinkRepair may not apply across different repair datasets.

    Source: §6.2 · p. 11

Abstract

from arXiv · show

Though many approaches have been proposed for Automated Program Repair (APR) and indeed achieved remarkable performance, they still have limitations in fixing bugs that require analyzing and reasoning about the logic of the buggy program. Recently, large language models (LLMs) instructed by prompt engineering have attracted much attention for their powerful ability to address many kinds of tasks including bug-fixing. However, the quality of the prompt will highly affect the ability of LLMs and manually constructing high-quality prompts is a costly endeavor. To address this limitation, we propose a self-directed LLM-based automated program repair, ThinkRepair, with two main phases: collection phase and fixing phase. The former phase automatically collects various chains of thoughts that constitute pre-fixed knowledge by instructing LLMs with the Chain-of-Thought (CoT) prompt. The latter phase targets fixing a bug by first selecting examples for few-shot learning and second automatically interacting with LLMs, optionally appending with feedback of testing information. Evaluations on two widely studied datasets (Defects4J and QuixBugs) by comparing ThinkRepair with 12 SOTA APRs indicate the priority of ThinkRepair in fixing bugs. Notably, ThinkRepair fixes 98 bugs and improves baselines by 27%-344.4% on Defects4J V1.2. On Defects4J V2.0, ThinkRepair fixes 12-65 more bugs than the SOTA APRs. Additionally, ThinkRepair also makes a considerable improvement on QuixBugs (31 for Java and 21 for Python at most).

1 Introduction

ThinkRepair addresses the difficulty of repairing bugs that require reasoning by automating the collection and use of few-shot chains of thought. It reports stronger benchmark results than state-of-the-art APRs across Defects4J and QuixBugs.

1 Introduction

  • ThinkRepair collects chains of thought into a pre-fixed knowledge pool, selects examples for few-shot learning, and interacts with an LLM with optional testing feedback.The authors identify prompt quality as important to reasoning and manual construction of high-quality prompts as costly.Source: §1 · pp. 1–2
  • 98 bugs were fixed on Defects4J V1.2, improving baselines by 27%∼344.4%; on Defects4J V2.0, ThinkRepair fixed 12∼65 more bugs than SOTAs.It also exclusively fixed 32 bugs that SOTAs could not fix, and fixed 19 of 44 RWB V1.0 bugs and 10 of 29 RWB V2.0 bugs.Source: §1 · p. 2
  • The evaluation compares ThinkRepair with 12 state-of-the-art APR approaches on Defects4J and QuixBugs.The contribution list includes evaluation against both NMT-based and LLM-based tools, plus a further study of data leakage using real-world projects.Source: §1 · p. 2
  • ThinkRepair is presented as an LLM-based APR approach that can produce results comparable and complementary to other APR directions.Its automated reasoning contribution combines few-shot CoT, automated chain-of-thought collection, example selection, and interaction feedback.Source: §1 · p. 2

2 Motivation

The Closure-56 example illustrates why some repairs require understanding function logic and adding new code; ThinkRepair addresses this by guiding LLM reasoning with collected and selected examples.

2.1 A Motivation Example

  • Closure-56 incorrectly returns null in a boundary case; its developer fix checks whether pos exceeds the string length before returning null.The function is intended to return the requested line, and the paper frames this example as requiring code understanding and reasoning about logic.Source: §2.1 · p. 2
  • The authors argue that NMT-based APRs struggle to fix bugs requiring new logic when similar repair patterns are absent from training data.The example requires adding code, which the paper describes as more challenging than modifying or deleting code.Source: §2.1 · p. 2

2.2 Key Ideas

  • ThinkRepair combines few-shot CoT with automated collection of reasoning chains and selection of effective examples for repair prompts.The approach targets LLMs that can understand code but may not fix a bug when the prompt does not guide deeper reasoning.Source: §2.1 · p. 2, §2.2 · p. 3
  • ThinkRepair is an LLM-based APR approach that does not rely on training with a large amount of historical bug fixes.The paper contrasts this with specifically designed NMT-based APR models and describes LLMs as pretrained on text and code tokens.Source: §2.2 · p. 3

3 Our Approach: ThinkRepair

ThinkRepair has a collection phase that builds a chain-of-thought knowledge pool and a fixing phase that uses CoT-based prompting and few-shot learning.

3 Our Approach: ThinkRepair

  • The collection phase gathers chains of thought to form pre-fixed knowledge, while the fixing phase repairs bugs using CoT-based prompts and few-shot learning.The paper names ChatGPT, CodeLlama, DeepSeek-Coder, and StarCoder as backend LLMs and says the framework can include other state-of-the-art LLMs.Source: §3 · p. 3
  • ThinkRepair uses four backend LLMs: ChatGPT, CodeLlama, DeepSeek-Coder, and StarCoder.The framework is described as flexible enough to include other state-of-the-art backend models.Source: §3 · p. 3
  • The two phases are illustrated in Figure 2 and Algorithm 1.The passage identifies the collection and fixing phases as the framework's main stages.Source: §3 · p. 3

3.1 Collection Phase

The collection phase prepares a prompt, gathers candidate chains of thought and fixes, then filters the outputs through tests to build its knowledge pool.

3.1 Collection Phase

  • The collection phase addresses prompt preparation, chains-of-thought collection, and function verification.The algorithm describes generating a CoT and fixed function from each buggy function, then retaining valid functions in the knowledge pool.Source: §3.1 · p. 3, §3.1.1 · p. 3

3.1.1 Task 1: Prompt Preparation.

  • Prompt preparation uses a role instruction, a task description, the buggy function, and a chain-of-thought indicator.The paper gives “Let’s think step by step” as its CoT indicator.Source: §3.1.1 · p. 3

3.1.2 Task 2: Chains of Thoughts Collection.

  • CoT collection produces samples containing the buggy function, its fixed version, and the reasoning chain generated from the decorated prompt.The passage's example describes reasoning about integer overflow and changing the multiplication result to a long type.Source: §3.1.2 · p. 4

3.1.3 Task 3: Function Verification.

  • Function verification runs the dataset's test suite and retains only generated fixes that pass the entire suite.The collection process makes at most 25 attempts for each bug.Source: §3.1.3 · p. 4

3.2 Fixing Phase

ThinkRepair’s fixing phase selects examples from its collected knowledge pool, prompts an LLM to repair the target function, and iteratively uses test feedback to refine candidate fixes.

3.2.1 Task 1: Few-Shot Selection.

  • Two examples are selected from semantic clusters to compose the repair prompt alongside the target buggy function.ThinkRepair selects diverse examples because few-shot examples can affect generalization and the conversation window is limited.Source: §3.2.1 · p. 4, §3.2 · p. 4
  • Semantic-based selection embeds buggy functions with UniXcoder, clusters them using K-means, and selects the most similar example from each cluster.Contrastive-based selection further fine-tunes UniXcoder with R-Drop; IR-based selection uses BM25, while random selection samples from the pool.Source: §3.2.1 · p. 4

3.2.2 Task 2: Automatic Fixing.

  • The LLM receives the selected examples and target function, then returns its reasoning and a candidate fixed function for verification.The fixing phase comprises few-shot selection, automatic fixing, and interaction verification.Source: §3.2.2 · p. 4, §3.2 · p. 4

3.2.3 Task 3: Interaction Verification.

  • Test feedback is appended to the original prompt after a candidate fails, and interactions continue until the full suite passes or five interactions are exceeded.Failure messages cover compile failures, timeouts, syntax errors, and failing tests; the five-interaction cap balances effectiveness and cost.Source: §3.2.3 · pp. 4–5

4 Experimental Design

The experimental design evaluates ThinkRepair on filtered Defects4J and QuixBugs benchmarks, against twelve APR baselines, using patch counts and a specified implementation and repair budget.

4.1 Datasets

  • Defects4J 1.2 contains 391 bugs across six Java projects, and Defects4J 2.0 contains 438 new bugs across nine additional projects; evaluation filters for single-function bugs.The two Defects4J versions have no overlapping bugs.Source: §4.1 · p. 5

4.2 Baselines and Evaluation Metrics

  • Twelve state-of-the-art baselines include eight NMT-based and four LLM-based APR approaches; evaluation counts correct and plausible patches.A plausible patch passes all tests but is not semantically equivalent to the actual fix; plausible patches were manually checked for equivalence.Source: §4.2 · p. 5, Table 2 · p. 5

4.3 Implementation

  • The baseline table organizes approaches by category, fine-tuning, time or patch limit, and venue.NMT-based baselines require fine-tuning, whereas the listed LLM-based baselines do not.Source: §4.3 · p. 5, §4.2 · p. 5
  • ThinkRepair uses gpt-3.5-turbo with two few-shot examples, up to five interactions per session, and 25 independent repair attempts per bug.The default end-to-end timeout is five hours per bug, while the reported average total time is under 20 minutes.Source: §4.3 · p. 5

5 Experimental Results

ThinkRepair outperformed the studied LLM- and NMT-based APRs in the reported benchmark comparisons. Its ablations found benefits from combining CoT few-shot learning with interaction feedback, and from semantic example selection.

5.1 RQ-1: Compare with LLM-based APRs

  • With perfect fault information, ThinkRepair fixed 98 single-function Defects4J V1.2 bugs, 22 more (28.9%) than ChatRepair.On QuixBugs, both tools fixed all Python bugs and missed one Java bug.Source: §5.1 · p. 6, Table 4 · p. 6
  • With perfect fault information, ThinkRepair auto-fixed 46.3% more bugs than AlphaRepair; with only method-level fault information, it auto-fixed 17 (27%) and 62 (344.4%) more than Codex and GPT-NeoX, respectively.Source: §5.1 · p. 7

5.2 RQ-2: Compare with NMT-based APRs

  • 98 fixes on Defects4J V1.2 gave ThinkRepair the best result over eight NMT-based APRs, 46.3% (67 of KNOD)–164.9% (37 of DLFix) more than baselines.ThinkRepair also performed best across all six projects; ThinkRepair* fixed 3–33 more bugs than SOTA APRs.Source: Table 6 · p. 8, §5.2 · p. 8
  • ThinkRepair fixed 107 bugs on Defects4J V2.0, 60–65 (127.7%–154.8%) more than NMT-based SOTAs, and improved on them across both QuixBugs languages.It fixed 14–26 more bugs on QuixBugs-Java and 19–21 more on QuixBugs-Python.Source: §5.2 · p. 8, Table 7 · p. 9

5.3 RQ-3: Configurations of ThinkRepair

  • Combining CoT few-shot learning and interaction feedback yielded 80 correct fixes, versus 36 for ChatGPT with few-shot prompting.Knowledge collection with few-shot selection raised the count from 36 to 57; interaction feedback raised it from 36 to 62.Source: Table 8 · p. 9, §5.3 · p. 9
  • Contrastive-based and semantic-based selection fixed 27 and 13 more bugs, respectively, than random selection; Contrastive-based Selection performed best overall.The authors attribute its performance potentially to UniXcoder fine-tuned with contrastive learning.Source: Table 9 · p. 9, §5.3 · pp. 9–10
  • Increasing interactions improved performance from 57 fixes after one interaction to 80 after five, while later gains diminished as interaction cost increased.The reported increase from two to five interactions was 75→80; the authors chose five as the default balancing performance and communication cost.Source: §5.3 · p. 9, Figure 9 · p. 10

6 Discussion

The discussion examines how generated patches relate to developer fixes, evaluates ThinkRepair on real-world bugs, and addresses data leakage and external validity.

6.1.1 Similarity between generated patches and the ground-truth.

  • Only 24 of 98 correct patches (24.5%) lexically match the Defects4J V1.2 ground truth; the others are reported as semantically equivalent.ThinkRepair's example fix differs textually from the developer fix but is semantically equivalent.Source: §6.1.1 · p. 10

6.1.2 Study on Real-World Projects.

  • RWB V1.0 and V2.0 contain 44 and 29 single-function bugs, respectively, extracted from bug-fixing commits in Defects4J projects.The datasets were assembled using commits after October 2021 and March 2023, respectively.Source: §6.1.2 · p. 10
  • ThinkRepair and ThinkRepair* both outperform AlphaRepair on RWB, and the authors conclude ThinkRepair can fix bugs beyond Defects4J and QuixBugs.The authors also conclude data leakage will not significantly affect ThinkRepair's performance.Source: §6.1.2 · p. 10, Table 10 · p. 10

6.2 Threats to Validity

  • The authors identify manual validation of plausible patches and possible training-data leakage as internal validity threats.They report that 24.5% of correct patches align lexically with reference fixes, while ThinkRepair still fixes 29 unique bugs after excluding those 24 patches.Source: §6.2 · pp. 10–11
  • The authors caution that ThinkRepair's observed effectiveness may not apply to repair datasets beyond those evaluated.They evaluate on Defects4J and QuixBugs to examine generalizability.Source: §6.2 · p. 11

7 Related Work

The related work reviews LLMs and APR approaches, tracing a shift from prompting and fine-tuning to direct LLM patch generation. ThinkRepair is positioned as a way to address prompt-quality dependence through a self-directed knowledge pool and few-shot selection.

7.1 Large Language Model

  • LLMs can be adapted through fine-tuning or prompting; fine-tuning requires additional training and has limited use when sufficient task data are unavailable.ChatGPT is described as fine-tuned using RLHF, which trains a reward model from human-reordered outputs and updates model parameters through reinforcement learning.Source: §7.1 · p. 11

7.2 Automated Program Repair

  • APR research moves from template and NMT methods, which have pattern or historical-data constraints, toward LLM patch generation and ThinkRepair's self-directed knowledge pool.The passage describes AlphaRepair, Codex-based tools, LLM studies, and ChatRepair before presenting ThinkRepair's goal of selecting few-shot examples from knowledge it constructs through self-reflection.Source: §7.2 · p. 11

8 Conclusion

ThinkRepair is a single-function APR tool with collection and fixing phases. It reports state-of-the-art performance on Defects4J V1.2 and V2.0, exceeding baselines by 17–62 and 12–65 bugs, respectively.

8 Conclusion

  • ThinkRepair is a single-function APR tool that collects thought processes for later few-shot selection and interacts with an LLM, optionally using test feedback, during fixing.It reports state-of-the-art performance on Defects4J V1.2 and V2.0, surpassing baselines by 17–62 and 12–65 more bugs, respectively.Source: §8 · p. 11

Related papers

Loading 2407.20898v1…