From Code to Correctness: Closing the Last Mile of Code Generation with Hierarchical Debugging

The simulated execution is not only more effective but also more flexible than real execution

What is the reason of leveraging LLMs instead of directly executing the targeted code to obtain the execution results?

Thanks for the insightful question. We conducted an ablation study where we replace the simulated code execution with real code execution like in LDB (Zhong et al., 2024) to extend the results of Table 2:

Effectiveness:

We can observe that the simulated execution performs better than the real execution. This is because that the collected real execution steps from the Python interpreter are often long and contain all the detailed changes in the variables and the execution of code (Zhong et al., 2024), which may introduce noise and make the MGDebugger focus on irrelevant information.

However, during the simulated execution, the MGDebugger will naturally focus on the key variables and express the debugging steps in a more understandable way to itself. These execution traces encourage the MGDebugger to analyze the functionality of the code and the relationships between variables, which also serves as its reasoning process. In this way, the MGDebugger can better understand the code and provide more accurate debugging steps.

Flexibility:

In addition, the proposed simulated execution is also more flexible and can be easily extended to other more complex programming environments, where the execution environment is not easily accessible (Li et al. 2023). For example, some programming environments may have a large number of dependencies or require specific hardware configurations, which makes it difficult to collect real execution traces. In contrast, the simulated execution can be easily implemented by simulating the execution with the reasoning ability of the LLMs [7]. This benefit extends the applicability of the MGDebugger to a wider range of complex programming scenarios.

[7] NExT: Teaching Large Language Models to Reason about Code Execution. ICML 2024

Clarification on Algorithm 1

In Algorithm 1: 1) why conduct MGDebugger before execution, i.e., you might conduct debugging on a correct one?

Sorry for the confusion. We assume that the MGDebugger will take an incorrect code snippet as input. We will clarify this in the revised version of the paper in light of your feedback.

2. what is the definition of Line 13 "f^{'} \gets DEBUG(f, ...)"?

Thanks for pointing this out. The DEBUG function stands for the "Debugging Subfunctions with LLM-simulated execution" process as described in Section 3.4. We will provide a clear definition of this function in the revised version of the paper.

Thanks again for your positive feedback and insightful questions. We are excited to incorporate these clarifications and updates into the revised version of the paper. If you have any further questions or suggestions, please feel free to let us know.

We thank the reviewer for the positive feedback on the clarity and motivation of our paper. We appreciate your insightful comments and suggestions, and we are glad to address your concerns as follows:

Our work mainly sheds lights on the core reasoning ability of LLMs in debugging tasks

Similar with the "weakness" section, what is reason of choosing HumanEval/MBPP/HumanEvalFix instead of Defect4J?

Thank you for raising this important question about evaluating MGDebugger on Defects4J. We would like to clarify the deliberate scope of our current study and explain why we focused on self-contained programming tasks following prior works (Chen et al., 2023b; Zhong et al., 2024; Ding et al., 2024).

Self-contained programming tasks and real-world software engineering (like in Defects4J) present distinct challenges - while programming tasks challenge algorithmic complexity and logical correctness, software engineering tasks (like those in Defects4J) involve additional complexities like incomplete specifications, long-range dependencies, and repository-level context understanding [5,6].

Our study specifically focuses on debugging logically and algorithmically complex code, isolating this capability from other challenges in software engineering. Approaches like Agentless addressing SWE-bench require multiple components beyond debugging, including repository-level fault localization, patch generation, and patch validation pipelines. By focusing on self-contained programs, we can isolate and thoroughly evaluate our hierarchical debugging approach without the need for these additional components.

This focused scope allows us to discover non-obvious relationships in debugging effectiveness across different algorithmic complexity levels that might be obscured in a full software engineering pipeline. And we've successfully revealed the effectiveness of MGDebugger against lengthier and more complex code snippets in Figure 3,7,8. These findings are valuable in understanding the potential of MGDebugger to improve the LLMs' core reasoning ability in the debugging process in software engineering tasks.

[5] Is Self-Repair a Silver Bullet for Code Generation? ICLR 2024. https://openreview.net/forum?id=y0GJXRungR

[6] Large language model-based agents for software engineering: A survey. arXiv:2409.02977

Differences between MGDebugger and existing APR approaches on ASTs

What is the difference between your approach and existing APR approaches on ASTs, e.g., KNOD (maybe some explanation is necessary)?

Thanks for the insightful question. We mainly follow the stream of works after to focus on self-debugging of LLM-generated codes (Chen et al., 2023b; Zhong et al., 2024; Ding et al., 2024). And the proposed MGDebugger is designed to improve the reliability of LLM-generated code through fine-grained bottom-up debugging.

ChatRepair [1] introduces a conversational approach using ChatGPT that iteratively learns from test failures and successful patches to improve repair quality, while Repilot [2] enhances patch generation by combining LLMs with completion engines to ensure token-level validity. KNOD [3] focuses on incorporating domain knowledge through a three-stage tree decoder and rule distillation for generating valid patches using Abstract Syntax Trees, and TARE [4] proposes a type-aware approach integrating typing rules through specialized grammar and graph representations. Unlike these approaches that treat debugging as a holistic or single-level problem, MGDebugger introduces a hierarchical debugging strategy that isolates and addresses algorithmic complexity at different granularity levels, enabling a more systematic discovery of non-obvious relationships in debugging effectiveness across varying complexity levels. And the proposed simulated execution also serves as the reasoning process of the MGDebugger to better understand the code and provide more accurate debugging steps.

We will update the related work section to better clarify the differences between MGDebugger and existing APR approaches on ASTs according to your suggestion.

Clarification of accuracy and RSR

What is the difference between accuracy and RSR? Why is accuracy higher than RSR in the experimental results?

Sorry for the confusion caused. The accuracy is the overall success rate of the LLM-based code generation & debugging process. So it will have an initial value of >70 before debugging. As the debugging process proceeds, the overall success rate will be

$$Accuracy = \frac{Correctly\ Generated\ Programs + Correctly\ Debugged\ Programs}{Total\ Programs}$$

The RSR (Repair Success Rate) is used to more explicitly measure the success rate of debugging. The initial RSR will be 0 before debugging, and will equal to the percentage of correctly debugged programs from all buggy programs after the first code generation stage:

$$RSR = \frac{Correctly\ Debugged\ Programs}{Total\ Buggy\ Programs}$$

These two metrics are related but focus on different aspects of the generation and debugging process.We will clarify the definitions of these metrics better in the revised version of the paper.

Our work focuses on a different problem domain than Defects4J

What is the performance of MGDebugger when applying it in program repair such as Defects4J?

Thank you for raising this important question about evaluating MGDebugger on Defects4J. We would like to clarify the deliberate scope of our current study and explain why we focused on self-contained programming tasks following prior works (Chen et al., 2023b; Zhong et al., 2024; Ding et al., 2024).

Self-contained programming tasks and real-world software engineering (like in Defects4J) present distinct challenges - while programming tasks challenge algorithmic complexity and logical correctness, software engineering tasks (like those in Defects4J) involve additional complexities like incomplete specifications, long-range dependencies, and repository-level context understanding [1,2].

Our study specifically focuses on debugging logically and algorithmically complex code, isolating this capability from other challenges in software engineering. Approaches like Agentless addressing SWE-bench require multiple components beyond debugging, including repository-level fault localization, patch generation, and patch validation pipelines. By focusing on self-contained programs, we can isolate and thoroughly evaluate our hierarchical debugging approach without the need for these additional components.

This focused scope allows us to discover non-obvious relationships in debugging effectiveness across different algorithmic complexity levels that might be obscured in a full software engineering pipeline. And we've successfully revealed the effectiveness of MGDebugger against lengthier and more complex code snippets in Figure 3,7,8. These findings are valuable in understanding the potential of MGDebugger to improve the LLMs' core reasoning ability in the debugging process in software engineering tasks.

However, we are also actively exploring the application of hierarchical debugging in software engineering tasks like Defects4J and SWE-bench. We believe that MGDebugger can be extended to address these challenges by integrating additional components like fault localization and patch generation. We will update the discussion about future work to include this direction in the revised version of the paper.

[1] Is Self-Repair a Silver Bullet for Code Generation? ICLR 2024. https://openreview.net/forum?id=y0GJXRungR

[2] Large language model-based agents for software engineering: A survey. arXiv:2409.02977

Thank you for your valuable feedback, and we sincerely hope that you find our responses satisfactory. We look forward to any further suggestions you may have to support the acceptance of our work!

Thank you for your constructive feedback. We are grateful for your positive comments on the novelty and effectiveness of MGDebugger. We hope to address your concerns and suggestions in the following sections:

The usage of LLMs in MGDebugger makes it effective and flexible

One of the major concerns in this work is that it relies on LLMs heavily. Using LLMs for decomposition, test case generation, and execution. I am confused about the effectiveness of each component when using LLMs. Also, as LLMs are black-box, whether to use some traditional program analysis tools for replacement. Some relevant experiments to compare with traditional tools are needed.

Thank you for your insightful comments. Overall, we hope to build a flexible and effective debugging system that can be applied to a wide range of LLMs and scenarios. Here we will justify each component of MGDebugger and explain the effectiveness and necessity of using LLMs in each step:

• Decomposition: By leveraging the LLM's ability to understand the code, we can effectively decompose the code into smaller, more manageable parts. This decomposition process is crucial for isolating and fixing bugs in complex code. And we've shown that MGDebugger significantly outperforms the LDB baseline (Zhong et al., 2024), which analyzes the Control Flow Graph (CFG) of the code to split it into smaller blocks.
• Test case generation: In order to effectively verify the correctness of subfunctions after debugging, we generated test cases for subfunctions conditioned on the public test cases of the original main function. Since the original code is buggy, we cannot access the desired output of each subfunction directly by analyzing the execution traces of the original code. So we propose to utilize the reasoning ability of LLMs to achieve this goal.
• Simulated execution: The simulated execution is used to analyze the functionality of the code and the relationships between variables, which also serves as the reasoning process of MGDebugger. The ablation study below shows that the simulated execution performs better than the real execution. This is because the real execution steps from the Python interpreter are often long and contain all the detailed changes in the variables and the execution of code, which may introduce noise and make the MGDebugger focus on irrelevant information. In contrast, the simulated execution encourages the MGDebugger to focus on the key variables and express the debugging steps in a more understandable way to itself. This also facilitates the potential of MGDebugger to more complex programming environments where real execution traces are hard to collect.

In conclusion, the use of LLMs in MGDebugger is essential and also effective in each component. These components gracefully complement each other to form a powerful debugging system to push the boundaries of LLMs in code debugging. We will further clarify the effectiveness of each component in the revised version of the paper in light of your feedback.

Thank you for the detailed review and insightful comments. We appreciate your feedback and suggestions. And we are glad to hear that you found our work promising and the results significant. We will address your concerns and suggestions in the following.

MGDebugger is also effective on more closed-source models like GPT-4o

Could you please provide the comparison results on some advanced models (GPT, Claude, etc.) or some open-source models with better natural language capabilities?

Thanks for this insightful suggestion. To address your concern, we've also conducted experiments with other latest LLMs, including GPT4o, Claude 3.5 Sonnet, and LLaMA 3.1 70B. Here are the results on HumanEval:

• GPT4o:

• Claude 3.5 Sonnet:

• LLaMA 3.1 70B:

These results show that the MGDebugger is also effective on more powerful models like GPT-4o, Claude 3.5 Sonnet, and LLaMA 3.1 70B. We will include these results in the revised version of the paper.

In-depth analysis of MGDebugger's components

The paper proposed methods that highly depend on LLMs' reasoning and language analysis capabilities, which I have concerns about.

Thank you for your insightful comments. Overall, we hope to build a flexible and effective debugging system that can be applied to a wide range of LLMs and scenarios. Here we will justify each component of MGDebugger and explain the effectiveness and necessity of using LLMs in each step:

LLM-based code decomposition benefits debugging by isolating logically independent units

It could be great if the authors could provide a comparison experiment for compare the proposed method with directly decomposing program into syntax-level functions by static analysis.

Thank you for your insightful comments. By leveraging the LLM's ability to understand the code, we ask the model to decompose the code into subfunctions that represent the minimal logical units. This decomposition is based on the model's understanding of the code's structure and logic. On the one hand, existing LLMs have been able to understand basic syntax and static information effectively [1-3]. On the other hand, comparing with the baselines using static analysis for line-level, block-level, or function-level decomposition of LDB (Zhong et al., 2024) in Table 1 (maximum of 84.1), results from Table 2 show that all the ablation variants of MGDebugger outperform these static analysis-based baselines by a large margin (minimum of 89.0). Compared to the rule-based decomposition with static analysis, the LLM-based decomposition is more flexible and can help to isolate the logical units more effectively, thus improving the debugging performance.

[1] CodeMMLU: A Multi-Task Benchmark for Assessing Code Understanding Capabilities of CodeLLMs. arXiv:2410.01999

[2] CodeHalu: Investigating Code Hallucinations in LLMs via Execution-based Verification. arXiv:2405.00253

[3] NExT: Teaching Large Language Models to Reason about Code Execution. ICML 2024

Test case generation for subfunctions is effective for debugging

It would be great to see the accuracy of test case generation. For example, given the same test input, how many test outputs generated by LLMs are the same as the ground truth test outputs (which can be obtained from running the canonical solution of the task).

We use the visible test cases from the original code for the main function. And in order to effectively verify the correctness of subfunctions during debugging, we generate test cases for subfunctions conditioned on the public test cases of the original main function. Since there is no ground canonical solution or test cases for the decomposed subfunctions, it is not directly feasible to evaluate the accuracy of the test cases generated for subfunctions.

To address your concern on the accuracy of test case generation, we sampled 20 problems from HumanEval and converted the canonical solutions from HumanEval to hierarchical structures. Then we executed the golden test cases and compared the outputs with the generated test cases manually. The results show that the test cases generated by LLMs are correct in 142/151=94% of the cases, demonstrating the effectiveness of the test case generation process.

Furthermore, the ablation study in Table 2 shows that the MGDebugger with test case generation (RSR 76.3%) performs better than the MGDebugger without test case generation (RSR 60.5%). This indicates that the test cases generated by LLMs are effective in verifying the correctness of the subfunctions, enabling MGDebugger to identify and fix bugs more accurately.

We will further clarify the effectiveness of test case generation in the revised version of the paper in light of your feedback.

Simulated execution by LLMs is not only effective but also flexible

Also, why to avoid the program execution in MGDebugger is not fully motivated in this paper. It would be great to see a comparison of the time and computational resources required for LLM-based simulation versus actual execution.

Thanks for pointing this out. First, for normal python codes, the real execution (usually measured by ms) is way faster than the simulated execution by LLMs (usually measured by s). However, the simulated execution yields better debugging results (effectiveness) and has the potential to be extended to more complex programming environments (flexibility). Here, we provide more detailed explanations:

• Effectiveness: We conducted an ablation study where we replace the simulated code execution with real code execution like in LDB (Zhong et al., 2024) to extend the results of Table 2:

  Method	HumanEval Acc. (%)	Δ Acc. (%)	RSR (%)	MBPP Acc. (%)	Δ Acc. (%)	RSR (%)
  MGDebugger with Simulated Execution	94.5	+17.7	76.3	80.0	+12.8	39.0
  MGDebugger with Real Execution	92.7	+15.9	47.4	78.2	+11.0	33.5
  No-Debugging	76.8	-	-	67.2	-	-

  We can observe that the simulated execution performs better than the real execution. This is because that the collected real execution steps from the Python interpreter are often long and contain all the detailed changes in the variables and the execution of code (Zhong et al., 2024), which may introduce noise and make the MGDebugger focus on irrelevant information. However, during the simulated execution, the MGDebugger will naturally focus on the key variables and express the debugging steps in a more understandable way to itself. These execution traces encourage the MGDebugger to analyze the functionality of the code and the relationships between variables, which also serves as its reasoning process. In this way, the MGDebugger can better understand the code and provide more accurate debugging steps.

• Flexibility: In addition, the proposed simulated execution is also more flexible and can be easily extended to other more complex programming environments, where the execution environment is not easily accessible (Li et al. 2023). For example, some programming environments may have numerous dependencies or require specific hardware configurations, which makes it difficult to collect real execution traces. In contrast, the simulated execution can be easily implemented by simulating the execution with the reasoning ability of the LLMs [3]. This benefit extends the applicability of the MGDebugger to a wider range of complex programming scenarios.

# Original buggy implementation
def main():
    for t in range(int(input())):
        x, n = map(int, input().split())
        if n > 100:
            delta = n % 4
            if delta == 3:
                if x % 2 == 0:
                    print(x - (n - 2) + (n - 1) + n)
                    continue
                else:
                    print(x + (n - 2) - (n - 1) - n)
            elif delta == 2:
                if x % 2 == 0:
                    print(x - (n - 1) + n)
                    continue
                else:
                    print(x + (n - 1) - n)
                    continue
            elif delta == 1:
                if x % 2 == 0:
                    print(x - n)
                    continue
                else:
                    print(x + n)
                    continue
        else:
            for i in range(1, n + 1):
                if x % 2 == 0:
                    x -= i
                else:
                    x += i
            print(x)
            continue

main
├── process_large_n
│   └── handle_delta_case
└── process_small_n
    └── jump

def main():
    for _ in range(int(input())):
        (x, n) = map(int, input().split())
        if n > 100:
            print(process_large_n(x, n))
        else:
            print(process_small_n(x, n))

def jump(point, meters):
    if point % 2 == 0:
        return point - meters
    else:
        return point + meters

def process_large_n(x, n):
    delta = n % 4
    if delta == 3:
        return x - (n - 2) + (n - 1) + n if x % 2 == 0 else x + (n - 2) - (n - 1) - n
    elif delta == 2:
        return x - (n - 1) + n if x % 2 == 0 else x + (n - 1) - n
    elif delta == 1:
        return x - n if x % 2 == 0 else x + n
    else:  # delta == 0
        return x

def process_small_n(x, n):
    for i in range(1, n + 1):
        x = jump(x, i)
    return x

Thank you for the valuable feedback! We appreciate your positive comments on the potential of MGDebugger and the clarity of our presentation. We hope to address your concerns and suggestions in the following sections:

Difference between MGDebugger and Agentless

How does MGDebugger’s approach differ from the hierarchical debugging framework in Agentless [1]?

We are grateful for this insightful question. MGDebugger and Agentless differ fundamentally in their objectives, granularity definitions, and methodologies:

Objective

• MGDebugger focuses specifically on debugging LLM-generated code (Chen et al., 2023b; Zhong et al., 2024; Ding et al., 2024) by decomposing individual functions into subfunctions and analyzing their correctness.

• Agentless's hierarchical approach is used for fault localization in repository-level software engineering tasks, moving from files to classes/functions to specific edit locations.

Hierarchy Granularity

• MGDebugger: Operates on function-internal granularity, breaking down individual functions into a tree of semantic units (subfunctions) for independent debugging.

• Agentless: Works at repository-level granularity, starting with file-level analysis and progressively narrowing down to specific code sections requiring modification.

Methodology

• MGDebugger: Uses a bottom-up strategy with LLM-simulated execution to debug each subfunction independently, focusing on correctness at each level before moving up.

• Agentless: Combines LLM-based and information-retrieval-based localization to identify fault locations, followed by separate repair and validation phases. And the final localized fault is treated as a whole when debugging.

These differences reflect our systems' distinct goals: MGDebugger aims to improve the reliability of LLM-generated code through fine-grained bottom-up debugging, while Agentless focuses on solving repository-level software engineering tasks through systematic fault localization and repair. Hope this clarifies the distinction between MGDebugger and Agentless, and we will include this comparison in the revised version of the paper.

MGDebugger focuses on a different problem domain to SWE-Bench

Could the authors extend their experiments to include additional datasets like SweBench to further validate MGDebugger’s robustness?

Thank you for this valuable suggestion. While extending experiments to SWE-bench is an interesting direction, we would like to clarify the deliberate scope of our current study and explain why we focused on self-contained programming tasks following prior works (Chen et al., 2023b; Zhong et al., 2024; Ding et al., 2024).

Distinct Challenges

Self-contained programming tasks and real-world software engineering present distinct challenges - while programming tasks challenge algorithmic complexity and logical correctness, software engineering tasks (like those in SWE-bench) involve additional complexities like incomplete specifications, long-range dependencies, and repository-level context understanding [2,3].

Complexity Isolation

Our study specifically focuses on debugging logically and algorithmically complex code, isolating this capability from other challenges in software engineering. Approaches like Agentless addressing SWE-bench require multiple components beyond debugging, including repository-level fault localization, patch generation, and patch validation pipelines. By focusing on self-contained programs, we can isolate and thoroughly evaluate our hierarchical debugging approach without the need for these additional components. This focused scope allows us to discover non-obvious relationships in debugging effectiveness across different algorithmic complexity levels that might be obscured in a full software engineering pipeline. And we've successfully revealed the effectiveness of MGDebugger against lengthier and more complex code snippets in Figure 3,7,8. These findings are valuable in understanding the potential of MGDebugger to improve the core debugging process in software engineering tasks.

Future Work

We strongly agree that extending to SWE-bench would be valuable future work, particularly to address handling ambiguous specifications and missing context, debugging difference levels of issues in repository codebases, and integrating MGDebugger's hierarchical debugging with repository-level fault localization and repair. We will revise our paper to better clarify these scope considerations and explicitly discuss the potential extension to software engineering tasks as important future work. And we are also actively exploring the integration of our hierarchical debugging approach with repository-level fault localization and repair in ongoing research.

[2] Is Self-Repair a Silver Bullet for Code Generation? ICLR 2024. https://openreview.net/forum?id=y0GJXRungR

[3] Large language model-based agents for software engineering: A survey. arXiv:2409.02977

Thank you for raising the concern. We appreciate that you consider our work as a novel fashion and a timely contribution. We would like to clarify the points you raised and address your questions as follows:

The performance of MGDebugger is statistically significant and robust against the stochasticity of LLMs

This is especially important considering the stochasticity of LLMs and even further increased variability for multi-step approaches. The results lack error bars.

We present the results of our experiments following previous work in the field (Chen et al., 2023b; Shinn et al., 2023; Zhong et al., 2024; Ding et al., 2024). We agree with you on the importance of awareness of the stochasticity of LLMs. We repeated each experiment 10 times and conducted a Wilcoxon rank sum test to verify the statistical significance of the results, finding that the proposed approach significantly outperforms the baselines (p < 0.01). This result verifies the robustness of our approach against the stochasticity of LLMs.

The simulated execution is not only more effective but also more flexible than real execution

As mentioned above, various components come together for the proposed approach, but it would be good to better understand the effects of those through more ablation studies (I know that authors present an ablation study but I propose some extensions to it below as part of Questions). How do the results compare if you swap simulated code execution with real code execution?

Thanks for your suggestion. We conducted an ablation study where we replace the simulated code execution with real code execution like in LDB (Zhong et al., 2024) to extend the results of Table 2:

Effectiveness:

We can observe that the simulated execution performs better than the real execution. This is because that the collected real execution steps from the Python interpreter are often long and contain all the detailed changes in the variables and the execution of code (Zhong et al., 2024), which may introduce noise and make the MGDebugger focus on irrelevant information.

However, during the simulated execution, the MGDebugger will naturally focus on the key variables and express the debugging steps in a more understandable way to itself. These execution traces encourage the MGDebugger to analyze the functionality of the code and the relationships between variables, which also serves as its reasoning process. In this way, the MGDebugger can better understand the code and provide more accurate debugging steps.

Flexibility:

In addition, the proposed simulated execution is also more flexible and can be easily extended to other more complex programming environments, where the execution environment is not easily accessible (Li et al. 2023). For example, some programming environments may have a large number of dependencies or require specific hardware configurations, which makes it difficult to collect real execution traces. In contrast, the simulated execution can be easily implemented by simulating the execution with the reasoning ability of the LLMs [1]. This benefit extends the applicability of the MGDebugger to a wider range of complex programming scenarios.

[1] NExT: Teaching Large Language Models to Reason about Code Execution. ICML 2024