Early automated program repair (APR) systems operated under a convenient but limiting assumption: that a software bug could be fixed by modifying a single line, statement, or bytecode instruction. While this single-location constraint made the problem computationally tractable, it created a massive disconnect from real-world software engineering.
As Anil Koyuncu et al. demonstrated in Impact of tool support in patch construction, production-level software defects rarely accommodate trivial, single-line fixes; instead, they frequently require complex, multi-line, and multi-hunk modifications. When an APR tool is optimized exclusively for single-statement changes, it remains fundamentally incapable of resolving architectural flaws, cross-component dependencies, or distributed logical errors, as noted by Shalini Kaleeswaran et al. in MintHint: Automated Synthesis of Repair Hints.
To bridge this gap, modern APR research has shifted toward multi-hunk repair—the synthesis of synchronized, non-contiguous code modifications spanning multiple methods, files, or modules.
The Combinatorial Explosion of Multi-Location Search Spaces
Why is fixing a multi-hunk bug so much harder than fixing a single-line bug? The core challenge lies in the exponential growth of the search space.
In a traditional single-line repair scenario, an algorithm identifies a likely faulty line and evaluates alternative token sequences or templates for that specific location. If the search space of valid code replacements for a single line is $S$, extending the repair target to $N$ non-contiguous lines doesn't just multiply the difficulty—it raises it exponentially to $S^N$. As Xiang Gao 0012 et al. pointed out in Crash-avoiding program repair, this multi-line extension drastically inflates the size and complexity of the patch search space, making brute-force or unguided search impossible.
Single-Hunk Repair (Search Space: S)
[Line 10: Buggy Statement] ---> Try replacements from space S
Multi-Hunk Repair (Search Space: S × S × S ...)
[Line 10: Change A] ---\
[Line 52: Change B] ----> Must be perfectly synchronized and
[Line 89: Change C] ---/ semantically compatible across the codebase
Furthermore, multi-hunk patches require strict coordination. If a defect requires an interface change in one file and corresponding updates to its callers in another, generating a correct patch for one location while leaving the others untouched results in uncompilable or broken code. Shangwen Wang et al. emphasized in Multi-Location Program Repair Strategies Learned from Successful Experience (S) that real-world bugs demand these synchronized edits across disparate parts of the codebase.
When evaluated against large-scale, repository-level benchmarks like those introduced by Zhengran Zeng et al. in CoderUJB: An Executable and Unified Java Benchmark for Practical Programming Scenarios and Tao Sun et al. in RepoFixEval: A Repository-Level Program Repair Benchmark From Issue Discovering to Bug Fixing, traditional localized models falter because they cannot reason about complex interdependencies between distant code modules.
Constraining the Space via Structure and Semantics
To make multi-hunk repair viable, researchers use structural and semantic constraints to prune the search space, ensuring that distributed changes remain coordinated and valid.
Graph-Level and Tree-Based Transformations
Instead of treating code as a flat sequence of text tokens—where multi-line deletions or structural additions often break syntax rules (Alex Groce et al. in An extensible, regular-expression-based tool for multi-language mutant generation)—advanced frameworks model code structurally.
In Hoppity: Learning Graph Transformations to Detect and Fix Bugs in Programs, Elizabeth A Dinella et al. framed program repair as a sequence of graph transformations on an augmented Abstract Syntax Tree (AST). This allows the model to execute complex structural changes, such as adding or deleting entire blocks of logic across non-contiguous nodes, while preserving core syntactic relationships.
Similarly, Michihiro Yasunaga et al. introduced Graph-based, Self-Supervised Program Repair from Diagnostic Feedback, which constructs a unified program-feedback graph. By linking compiler error messages directly to the specific, multi-line locations causing them, the model learns to coordinate simultaneous fixes across disparate sections of the codebase based on diagnostic feedback.
To ensure that these multi-hunk patches actually compile, Nan Jiang et al. developed KNOD: Domain Knowledge Distilled Tree Decoder for Automated Program Repair. KNOD distills formal programming rules directly into a tree-based decoder, preventing the model from generating illegal syntax when navigating the vast search space of multi-hunk transformations.
Fusing Language Models with Completion Engines
Large Language Models (LLMs) possess strong statistical intuition for code but often struggle with global semantic correctness when generating multi-file or multi-hunk patches (Yi Wu 0023 et al. in How Effective Are Neural Networks for Fixing Security Vulnerabilities).
To counteract this, Yuxiang Wei et al. proposed Copiloting the Copilots: Fusing Large Language Models with Completion Engines for Automated Program Repair. Their framework, Repilot, couples an LLM with a semantic completion engine. During token generation, the completion engine dynamically prunes tokens that are statistically probable but semantically invalid given the broader project context. This real-time filtering prevents the model from generating multi-hunk patches that violate global type systems or project dependencies.
LLM Token Proposal: [ Token X (Prob: 85%) ] [ Token Y (Prob: 12%) ]
| |
Semantic Engine Filter: Is Token X valid in Is Token Y valid in
global context? NO. global context? YES.
| |
Action: [ PRUNED ] [ ACCEPTED ]
Contextual Guidance: Retrieval, Templates, and Cloze Tasks
Another major strategy for scaling APR to multi-hunk defects involves guiding generative models with historical context or structural templates.
- Retrieval-Augmented Generation: In RAP-Gen: Retrieval-Augmented Patch Generation with CodeT5 for Automatic Program Repair, Weishi Wang et al. demonstrated that retrieval mechanisms can mitigate the difficulty of multi-hunk generation. By fetching structurally similar multi-location bug-fix examples from an external repository, the system provides the underlying model with a concrete blueprint of how distributed changes should be coordinated.
- Template-Based Masking: Chunrong Fang et al. combined human expertise with neural generation in GAMMA: Revisiting Template-based Automated Program Repair via Mask Prediction. GAMMA leverages reliable, human-defined fix templates to anchor the patch structure, and then uses language models to fill in the specific, distributed logical gaps via mask prediction.
- Zero-Shot Cloze Formulations: Moving away from rigid sequence-to-sequence translation models—which struggle with complex algorithmic changes (Rahul Gupta et al. in DeepFix: Fixing Common C Language Errors by Deep Learning)—Chunqiu Steven Xia et al. pioneered a zero-shot, fill-in-the-blank approach in Less Training, More Repairing Please: Revisiting Automated Program Repair via Zero-shot Learning. The authors noted that extending these cloze-style methodologies to handle non-contiguous code sections is essential for unlocking true multi-hunk repair capabilities.
Downstream Bottlenecks: Localization and Human Verification
Expanding the scope of automated program repair to multiple locations introduces severe downstream complications in both fault localization and developer verification.
Before a tool can fix a multi-hunk bug, it must accurately locate all the faulty components. Traditional fault localization algorithms are designed to pinpoint a single problematic line. In Can automated program repair refine fault localization? a unified debugging approach, Yiling Lou et al. highlighted a circular dependency: to refine fault localization for complex defects, an APR tool needs to generate valid multi-line candidate patches to gather execution feedback; however, generating those candidates in the first place is incredibly difficult without precise multi-location fault signals.
Once a multi-hunk patch is generated, it faces the hurdle of human review. Developers are naturally skeptical of automatically generated code, and this skepticism intensifies when a patch alters multiple files or non-contiguous blocks.
Ruixin Wang et al. addressed this cognitive overload in Show Me Why It's Correct: Saving 1/3 of Debugging Time in Program Repair with Interactive Runtime Comparison. They observed that visualizing program repairs becomes significantly more complex when patches span multiple files, as standard diff interfaces fail to convey how distributed changes interact at runtime. Providing clear reasoning traces—such as the hypothesis-testing approach proposed by Jian-Guang Lou et al. in Explainable automated debugging via large language model-driven scientific debugging—is vital for helping developers understand and trust multi-hunk patches.
Key Foundational Work
MintHint: Automated Synthesis of Repair Hints (2013) — contributed 1 concept elements to this direction.
Staged program repair with condition synthesis (2015) — contributed 1 concept elements to this direction.