Unveiling the Magic of Code Reasoning through Hypothesis Decomposition and Amendment

Authors: Yuze Zhao, Tianyun Ji, Wenjun Feng, Zhenya Huang, Qi Liu, Zhiding Liu, Yixiao Ma, Kai Zhang, Enhong Chen
Primary area: foundation or frontier models, including LLMs
Keywords: Code Reasoning, Hypothesis Decomposition, Reflection

Abstract:
The reasoning abilities are one of the most enigmatic and captivating aspects of large language models (LLMs). Numerous studies are dedicated to exploring and expanding the boundaries of this reasoning capability. However, tasks that embody both reasoning and recall characteristics are often overlooked. In this paper, we introduce such a novel task, code reasoning, to provide a new perspective for the reasoning abilities of LLMs.
We summarize three meta-benchmarks based on established forms of logical reasoning, and instantiate these into eight specific benchmark tasks. Our testing on these benchmarks reveals that LLMs continue to struggle with identifying satisfactory reasoning pathways. Additionally, we present a new pathway exploration pipeline inspired by human intricate problem-solving methods. This Reflective Hypothesis Decomposition and Amendment (RHDA) pipeline consists of the following iterative steps: (1) Proposing potential hypotheses based on observations and decomposing them; (2) Utilizing tools to validate hypotheses and reflection outcomes; (3) Revising hypothesis in light of observations. Our approach effectively mitigates logical chain collapses arising from forgetting or hallucination issues in multi-step reasoning, resulting in performance gains of up to $3\times$. Finally, we expanded this pipeline by applying it to simulate complex household tasks in real-world scenarios, specifically in VirtualHome, enhancing the handling of failure cases. We release our code and all of results at https://github.com/TnTWoW/code_reasoning.

Decision: accept (poster)
Reviewer scores: 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1729185863812

thread_type:
official_review

<thread_object>
creator: reviewer_jurk

<content>
summary:
This paper evaluates LLMs on code reasoning tasks, which require both recall and reasoning capabilities. The authors also propose a method RDHA which generally improves their performance in these tasks.

strengths:
originality: RDHA is a novel method. It is interesting to see such a method to be applied to code reasoning and even planning tasks (e.g., Virtual Home).

quality: the paper conducts a systematic investigation of code reasoning tasks and an additional planning task, which is a very comprehensive task setting.

clarity: the paper is generally easy to follow.

significance: it is important to understand LLMs' capabilities and limitations.

weaknesses:
Generally, the contributions of this paper are not strong enough.

1. If the main contribution is the evaluation of LLMs on code reasoning, it is not enough to test only two LLMs. Plus, it is not surprising that LLMs fail in complex reasoning tasks as widely testified in many existing works ([1,2], inter alia). 

2. If the strongest contribution is RHDA, I wonder how it compares to other prompting methods such as self-refine [3].

2. Some arguments are a bit loose or controversial. For instance, the authors "...position the code reasoning task between memory and reasoning" because it requires memory of syntax from pre-training and reasoning about current question and context. In this sense, most, if not all of the reasoning tasks can be put in the middle of the Figure 1 spectrum, which has one extreme of reasoning and another extreme of recall. For instance, math, which the authors put on the reasoning extreme of the spectrum, requires the LLM to understand what operators mean as well (i.e., syntax, which also needs to come from training memory). The authors are encouraged to be more cautious in statements.

[1] Zhuo, T. Y., Vu, M. C., Chim, J., Hu, H., Yu, W., Widyasari, R., ... & Von Werra, L. (2024). Bigcodebench: Benchmarking code generation with diverse function calls and complex instructions. arXiv preprint arXiv:2406.15877.

[2] Dziri, N., Lu, X., Sclar, M., Li, X. L., Jiang, L., Lin, B. Y., ... & Choi, Y. (2024). Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systems, 36.

[3] Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., ... & Clark, P. (2024). Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36.

questions:
1. What is the difference between Sub-Hyp and Chain of Thought?

2. I didn't get the rationale of why the IO prompt is the best in terms of accuracy. More specifically, what does it mean when you say this? On page 6, the end of the paragraph preceding the ablation study says "This may be a misunderstanding... than RHDA."?

3. At the bottom of page 7, "...we present a quantitative...", did you mean qualitative?

4. Did you conduct a full-scale experiment on Virtual Home? It seems that you only present two examples in the paper, which I'm not sure can generalize to the conclusion that RHDA is scalable and flexible.

5. What is the cost of RHDA? Does it generalize to other non-symbolic domains?

6. How does your method compare to self-refine?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730545610176

thread_type:
official_review

<thread_object>
creator: reviewer_fkt4

<content>
summary:
The paper presents "code reasoning" as a novel task requiring both reasoning and memory to explore the capabilities and boundaries of LLMs. The authors propose three new meta-benchmarks based on different forms of logical reasoning, namely: inductive code reasoning (predicting program from input-output pairs), deductive code reasoning (predicting output from input-program), and abductive code reasoning (predicting input from output-program). They instantiate these meta-benchmarks into eight concrete benchmarks: List Function, MiniARC, RobustFill, and DeepCoder for inductive reasoning, and CRUXEval and LiveCodeBench for both deductive and abductive reasoning. They propose a novel pipeline, "RHDA" (Reflective Hypothesis Decomposition and Amendment), that iteratively decomposes complex problems into simpler steps, verifies the results, and based on this feedback proposes amendments. This pipeline leads to as much as 3× performance gains over baseline models.

strengths:
1. Novel formulation and pipeline:
    - The paper introduces an intermediate task between reasoning and recall, giving us the ability to understand LLMs more deeply
    - RHDA pipeline demonstrates robustness in handling complex reasoning tasks
    
2. Comprehensive Evaluation: 
    - Three types of meta-framework with 8 specific benchmarks
    - Evaluation across different model types (GPT-4o and Claude 3.5)
    - Thorough ablation studies show the importance of each component.
3. Strong Results:
    - On inductive reasoning: RHDA outperforms baselines by 18.45% (List Function), 5.89% (MiniARC), 33.31% (RobustFill), and 12.02% (DeepCoder)
    - On deductive reasoning: Achieves 90.62% on CRUXEval and 84.16% on LiveCodeBench
    - On abductive reasoning: Achieves 83.75% on CRUXEval and 71.57% on LiveCodeBench
4. Extensibility: Successfully demonstrated application to VirtualHome environment, showing the framework can handle real-world complex scenarios like household tasks.

weaknesses:
1. Limited Theoretical Analysis: 
  - While the paper positions code reasoning between memory and reasoning tasks, it lacks a deeper theoretical analysis of why this intermediate position is beneficial or how it relates to existing theories of reasoning.
2. Limited Real-World Validation: 
 - While they show the program is capable of performing in VirtualHome, having quantitative benchmarks and more complex scenarios would be helpful to understand real-world applicability.
3. Incomplete Error Analysis: 
- Additional discussion on the failure modes of the RHDA pipeline would be helpful. Analysis of whether failures occur due to incorrect hypothesis formation, ineffective amendment etc is missing.
4. Complexity Overhead: 
- The paper doesn't analyze the computational cost of running multiple iterations of RHDA compared to single-pass methods like CoT or PoT. This is particularly important given the iterative nature of the approach.

questions:
1. Example analysis is said to be shown in Appendix E, but Appendix E is empty. 
2. How sensitive is the method to the quality of the initial decomposition? Are there cases where poor initial decomposition cannot be recovered through amendments?
3. When and why does the RHDA pipeline fail - are the failures primarily due to poor initial decompositions, ineffective amendments, or do different tasks exhibit different failure patterns?
4. The computational overhead analysis is missing:
 -  What is the computational cost compared to baseline methods? 
 -  What is the trade-off between the number of iterations and performance gains?
5. While VirtualHome examples demonstrate RHDA's potential for real-world tasks, can you provide quantitative metrics and more complex scenarios (e.g., handling multiple interdependent tasks or recovering from failures) to better evaluate its practical capabilities?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730669996122

thread_type:
official_review

<thread_object>
creator: reviewer_773h

<content>
summary:
This article presents a dynamic prompting method that automatically adjusts the number of prompting steps based on task complexity and model performance in real time.

strengths:
The approach taken has significant potential. The provided benchmark can be instrumental in understanding the boundaries between reasoning and recall.

weaknesses:
The paper contains  arguments that "are a bit loose or controversial". I request that the authors make their arguments more precise, and address the ICLR audience rather than assuming that this audience knows cognitive science, and terms like System 1 and System 2 tasks.

It is helpful to learn that System 1 and System 2 tasks have been explored technically, but the authors must introduce these tasks from the ML perspective and provide the references  [5, 6, 7] to ensure readers have the proper context.

  From a computer science point of view, an LLM can be viewed either as performing a mathematical function or as a software artifact.  Claims made about LLMs thus need to be validated either mathematically or empirically. The responses in the rebuttal help significantly to make things more precise.

Further, the goal to "explore the boundaries of LLM capabilities" can be presented in a more precise way. Many ML practitioners don't care about whether an LLM corresponds to some theoy of mind or human reasoning, but want to know in a precise sense what it's capabilities are.

The paper starts off in line 42 with "From the perspective of human cognitive psychology, reasoning can be viewed as a process of memory retrieval," and this is the perspective taken. There is insufficient mathematical theory or implementation to show results relevant to ICLR.

There are several claims made without defintion and/or validation. Some of these issues have been addressed in the rebuttal, but the authors must revise the article paying attention to ensuring clarity for an ML researcher.

questions:
Can you provide any empirical evidence to back up the many claims made in the article?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732539718685

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank each reviewer for their thorough and valuable feedback. Guided by the reviewers' comments, we have incorporated additional experiments and discussions. While ensuring full consistency with the original contributions and conclusions of the paper, we have made appropriate modifications to enhance its comprehensiveness. These revisions have been highlighted in blue for clarity. Below is a brief summary of the main changes we made:

| Changes | Section | Related Reviewers |
|---|---|---|
| More Base LLM: Llama3.1-70B-Instruct and Qwen-max | Appendix B | Reviewer JURK |
| Additional Baseline:Self Refine | Section 4 | Reviewer JURK |
| Human evaluation results on VirtualHome | Appendix D | Reviewer FKt4,Reviewer JURK |
| Layout optimization and more case studies | Appendix E.1 | Reviewer FKt4 |
| Failure analyse | Section 4 and Appendix E.2 | Reviewer FKt4 |
| Additional Cost Report | Appendix F | Reviewer FKt4,Reviewer JURK |
| Additional analysis of accuracy over iterations | Appendix G | Reviewer FKt4 |
| More references for recall and reasoning | Section 1 | Reviewer 773h, Reviewer FKt4,Reviewer JURK |

All additional experiments are included in the appendix, which is organized as follows:  

- Appendix A: Detailed description of the DSL syntax.  
- Appendix B: Extended experimental results for more LLM base models.  
- Appendix C: Specific details of the benchmarks.  
- Appendix D: Qualitative and quantitative analyses of the RHDA process framework on VirtualHome.  
- Appendix E: Presentation and analysis of both successful and failure cases.  
- Appendix F: Detailed explanation of experimental costs.  
- Appendix G: Trade-off analysis between the number of iterations and performance gains.  
- Appendix H: Prompts used in the experiments.  

If you have additional questions, please let us know.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper concerns code reasoning using LLMs. Thereby, the LLMs require both recall and reasoning capabilities, rendering the underlying task rather complex.

In more detail, the paper presents "code reasoning" as a novel task requiring both reasoning and recall to explore the capabilities and boundaries of LLMs. Three tasks of logical reasoning are presented: inductive code reasoning (predicting program from input-output pairs), deductive code reasoning (predicting output from input-program), and abductive code reasoning (predicting input from output-program). 

These tasks yield eight concrete benchmarks: List Function, MiniARC, RobustFill, and DeepCoder for inductive reasoning, and CRUXEval and LiveCodeBench for both deductive and abductive reasoning. The novel pipeline "RHDA" (Reflective Hypothesis Decomposition and Amendment) iteratively decomposes such complex problems into simpler steps, verifies the results, and proposes amendments. This pipeline leads to as much as 3× performance gains over baseline models.

The strengths of the paper as identified by the reviewers center around the novel problem formulation to understand LLMs' complex reasoning in a better way, with a good benchmark evaluation across different LLM models. Even real-world scenarios are not out of reach. The paper is generally very well written. 

The reviewers have, in addition, listed several weaknesses, such as more precise explanations and definitions or a missing real-world evaluation. Yet, after the discussion phase, the reviewers agreed that the paper might be accepted.