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
Venue: ICLR 2025 Poster (2025)
Keywords: Code Reasoning
Hypothesis Decomposition
Reflection
Primary area: foundation or frontier models, including LLMs
TL;DR: Solve code reasoning tasks using reflective hypothesis decomposition and amendment method

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.

Published as a conference paper at ICLR 2025
UNVEILING THE MAGIC OF CODE REASONING THROUGH REFLECTIVE HYPOTHESIS DECOMPOSITION AND AMENDMENT
Yuze Zhao', Tianyun Ji Wenjun Feng'.*, Zhenya Huangh.21, Qi Liu!i2
Zhiding Liu Yixiao Ma Kai Zhang', Enhong Chen
SState Key Laboratory of Cognitive Intelligence.
University of Science and Technology of China
Instiituee of Artificial Intelligence, Hefei Comprehensive National Science Center yuze weeehaccmaiil ustc. edu. en huangzhy@ustc.eer wew.:uuuuuttccc.....o.o.oe
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 em- body both reasoning and recall characteristies are often overlooked. In this paper, we introduce such a novel task, code reasoning, to provide a new perspective for the reasoning abilities LLMs. We summarize three meta-benchharks based 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 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 per- formance gains of up 3x. Finally, we expand this pipeline by applying simulate complex household tasks in real-world scenarios, specifically in Virtu- alHome, enhancing the handling of failure cases. We release our code and results at httttt::/ggthhhhi httpg/.tth...o..o..oee www.TT.Twwo//oe....oooooo.oooeao http://///././///od...eer.aoooo.
INTRODUCTION
Large Language Models (LLMs), which are trained on billions of tokens, have demonstrated im- pressive reasoning abilities in complex tasks (Brown et al.) 2020 Wei et al. 2022 Kojima al.)
2022 OpenAT 2023). However, is evident that as potential fuzzy retrieval systems or parame- terized (nowledge compression systems (Xie et al. 2021), LLMS perform better System tasks than on System 2 tasks (Kahneman] 2011 Bengio 2019 Yao et al. 2023a Weston & Sukhbaatar 2023 Liu et al., 2023a). Specifically, LLMs excel intuitive memory retrieval lasks, but continue 10 face significant challenges with tasks requiring rational reasoning (Kambhampati 2024).
From the perspective of human cognitive psychology. reasoning can be viewed as process of memory retrieval, in which people retrieve relevant information from memory and use it to make inferences (Kyllonen & Christal 1990, SüB et al., 2002) Hayes al. 2014, Feeney son 2014 Hardman & Cowan 2015). For example, Haidt (200T) proposed that when individuals engage in moral reasoning. they typically draw on their prior knowledge from social and cultural contexts. Similarly, studies involving animal lesions and human neuroimaging have confirmed that the hippocampus, which is primarily associated with memory, also plays crucial role in reasoning
Thomp-
Equual contribution
Corresponning author

---

Published as a conference paper at ICLR 2025
SYSTEM 1
EMOTIONAL
SYSTEM
LOGICAL
REFLECTIVE
INTUITIVE
RATIONAL
INSTINCTUAL
DELIBERATE
UNCONSCIOUS
FAST / AUTOMATIC
SLOW EFFORTFUL
Recall
Reasoning
pythce
tiinge blodo
flee:
soue touare the
scei
X Arithmetic
Translation
Summarization
cythee Code Reasoning
fioc: bin Symbolic
Figure I: Code reasoning is category of tasks that incorporates logical reasoning into code, aiming to solve programming problems through logical reasoning. These tasks require balance between background knowledge and thinking span, placing greater emphasis on the collaborative functioning of both System and System 2 thinking.
abilitics Zeithamova et al. 2012). Therefore, memory and reasoning are interdependent, with con- siderable overlap between the two, rendering the distinction between them somewhat arbitrary (Heit et al. 2012. Liu et al. 2023b).
We believe that, similar to humans (Strachan et al. 2024 Liu al. 2024b Lin al. 2024). LLMs
do not exhibit a clear boundary between memory and reasoning (Schaefter et al. 2024; Razeghi al., [022]. However, tasks that lie at this intersection are often overlooked in research. Here, we propose a novel task to explore the capability boundaries of LLMs: Code Reasoning. Code reasoning encompasses a category tasks that demonstrate logical reasoning through code and address problems in a systematic manner. As illustrated in Figure [ we position some tasks along an axis that reflects 1) the degree of reliance on prior knowledge (Recall) and 2) the extent which prior knowledge is applied to the current context (Reasoning). We position the code reasoning task between memory and reasoning. On one hand, the highly structured nature of code requires the model to learn syntax from pre-training data, enabling it to recall relevant information during solving a problem. the other hand, generating code solutions necessitates the model's ss understanding of the problem and context, involving reasoning to produce appropriate solutions.
In this paper, we introduce code reasoning, a task that formalizes reasoning steps into programming language and offloads the computation process to the compiler. To explore different aspects of code reasoning, we summarize three meta- betchbennc based on existing forms of logical reasoning: inductive code reasoning, deductive code reasoning, and abductive code reasoning.
Inductive code reasoning involves deriving broad generalizations from a series of observations, demonstrating the ability to infer rules from examples and generate programs meet input-output mapping. Deductive code reasoning starts from premises and derives valid conclusions, focusing on the model's capacity to understand a program's intermediate states and reasoning step by step. Ab- ductive code reasoning seeks the simplest and most likely explanation based on set of observations, highlighting the model's ability to abstractly understand a function's purpose.
We concretize these three meta-benchmarks into eight specific benchmarks. Based on these eight benchmarks, we evaluate the performance of existing models in code reasoning. Due to data sparsity, we find that current state-of-the-eee LLMs still struggle to achieve satisfactory results in solving such problems. To enhance the reasoning process, we implement a Reflective Hypothesis Decomposition and Amendment (RHDA) pipeline. This pipeline is iterative, encompassing hypothesis decomposi- tion, execution verification, and amendment submission. Specifically, we first guide the LLM to for- mulate initial hypotheses based on complex observations and decompose these into sub-hypotheses. These bybthyyst are then compiled into executable functions through a translator, enabling di- rect application to the observations, followed by validation using external tools. Subsequently. based on the execution results and observations, the LLM submits amendments to reflect on and refine the issues within the sub-hypotheses.
2

---

Published as a conference paper at ICLR 2025
Our experimental results indicate that RHDA methods effectively mitigate reasoning failures caused by data sparsity. With the same or even lower overhead, this method achieved performance im- provements of up three times compared baseline methods. Finally, extend this pipeline to complex, simulated real-world household tasks VirtualHome (Puig et al. 2018 2020), guiding the LLM to complete series of intricate operations.
META-BENCHEN BENCHMARK
We describe the general process of code reasoning as the transformation from Input I and Program P to Output O represented as I _,, O. Inductive code reasoning is concretized as the Programming by Example (PBE) task. this task, a neural program synthesis model M searches the execution space find program that best satisfies all given input-output specifications. We donate this meta- benchmark as M(I, O) P. Deductive code reasoning is exemplified in tasks that simulate the program execution process. In this task, a neural simulation compiler model M tracks the program's execution and records intermediate states, gradually deriving the final valid output. We denote this hetthbencchmak as MMI. P) - Ô. Abductive code reasoning is concretized as input prediction tasks. This task requires the neural understanding model M to form an abstract-level understanding of function's 's behavior and perform abductive inference based on given program and output. We represent this benchmrknc as MMO, - I. The details of the benchmarks are provided in the Appendix C
2.1 INDUCTIVE CODE REASONING
Inductive code reasoning can be represented as M(I P and is concretized as a PBE task QQu al., 2024 Shi et al. 2024). PBE a program synthesis task designed to help end-users, particu- larly non-programmers. create scripts automate repetitive tasks (Gulwani] 2016). Based on input- output specifications, PBE systems can synthesize program in either general-purpos language (GPL) or domain-specifie language (DSL). Inductive code reasoning encompasses four challeng- ing PBE tasks, two which are GPL tasks: List Function (Rule| 2020) and MiniARC (Kim et al.] 2022). while the other are DSL tasks: RobustFill (Devlin et al.] (017) and DeepCoder (Balog et al. 2016). GPL tasks are relatively complex, allowing the model to solve problems in a more flex- ible manner. In contrast, DSL tasks require the model quickly learn the syntax of DSL through few-shot learning and address relatively simpler problems.
List Function. The List Function task was originally designed to investigate how humans learn the concept of computable functions that map lists to lists. Given input and output specifications in the form of lists, the model generates GPL rules that conform to these specifications. For example, with input specification of 22, 4, 8, 10] and an output specification of [3, 5, 9, 11]. we expect the resulting rule to be lambda x x
compressed 5x5 version of the Abstraction and Reasoning Cor- pus (Chollet 2019 Moskvichev et al. 2023). designed to assess imaginative and reasoning abil- ities. MIniARC balances the length of the input-output pairs with the difficulty of the problems. The specifications are 5x5 2D grids, where the numbers represent blocks of specific colors. The model must find valid problem-solve paths (such as color swapping, row flipping) achieve the transformation from input to output.
MiniARC. MiniARC
RobustFill. RobustFill is a string manipulation task where the model is expected to perform combination of atomic operations, such extracting a substring from position ky by ing SubString(ks k1), to achieve generalization. As an example, a program ToCase (Lower, SubStr (1, converts full month names (January, April) their abbreviations (jan, apr).
The DeepCoder task involves using DSL to perform operations integer lists. In DeepCoder, each line represents subroutine that performs atomic operations on previous vari- ables and assigns the results to new variables. The result of the final line is the program's out-
DeepCoder.
For conciseness while maintaining generality, we will lambda expressions represent program.
3

---

Published as a conference paper at ICLR 2025
put. For example, program f- [int] D FILTER (<0)
MAP (*4)
f- SORT c e + REVERSE b (where "I" denotes subroutine separator.) transforms the imput [-17, -3, 4, 11, 0, -5, -9, 13, 6, 6, -8, 11] into the output [-12, -20, -32, -36, -68]. We provide detailed RobustFill and Deepcoder DSLs Appendix A
2.2 DEDUCTIVE CODE REASONING
Deductive code reasoning refers to the process of deriving a sound inference O by reasoning from the given premise I, assuming the validity of the argument P. Deductive code reasoning can be instantiated as an output prediction task (Gu et al. 2024). Based on the given premise, the out- put prediction requires the LLM simulate compiler (Kim et al.] 2024b), executing step by step until it arrives at a valid conclusion. For example, given a program P lambda text, value: " join (list (text) [value]] ) and inputs text 'beksrut', 'q', the output prediction from LLM should be 'bcksrutq'.
2.3 ABDUCTIVE CODE REASONING
Starting from existing facts P and O deriving the most reasonable and optimal explanation referred to as abductive code reasoning. This meta-benchmark can be framed an input prediction task. Given the provided facts, the input prediction requires the LLM to backtrack through the program's 's execution process to recover the potential inputs. In cases where multi- ple possible inputs exist, the model should apply Occam's 's Razor and return the simplest input. For example, given program range (len (nums) ) ] and outputs [-1, 0, 0, 1, 1, -1, 0, -1, 0, -11, the input prediction from LLM should be [-1, 0, 0, 1, 1].
lambda nums: nums + [nums [i 2] for
Deductive code and abductive code reasoning can be regarded as opposite processes; therefore, we selected two identical and representative datasets, CRUXEval (Gu et al. 2024) and Live- CodeBench (Jain et al. 2024), as benchmarks to validate these two capabilities.
CRUXEval. CRUXEval is a benchmark designed to evaluate code understanding and execution. Many models that achieve high scores on HumanEval (Chen al.) 202T) do not show the same level of improvement on the CRUXEval benchmark. This benchmark includes 800 functions along with their corresponding inputs and outputs.
LiveCodeBench. LiveCodeBench is dynamically updated benchmark soureed from competi- tion platforms. Each problem is timestamped, and we selected data from October 2023 (later than GPT-4o training) to March 2024 (the most recent), ensuring there is no data leakage and thereby guaranteeing the model's generalization performance.
3 CODE REASONING WITH HYPOTHESIS DECOMPOSITION AND AMENDMENT
We aim to generate a reliable reasoning process for problem-solving by establishing a problem- solving pathway f : X' + y. For a given task and the seen specifcaatonssooservaiino X,, the pathway f. should lead to a seen valid solution Y" through chain of reasoning. We expect this pathway f to have sufficient generalization capabilities to handle unseen speiifiations/bbbervviinss X². To this aim, we employ a process involving hypothesis decomposition, execution verification, and amendment submission to iteratively explore and refine the reasoning pathway. We first establish an initial hypothesis nt E Σ" based on observations x; E X, where Σ' is the closure form of LLM's vocabulary. This initial hypothesis ht serves as preliminary solution pathway to the problem. Given the complexity of many problems, we decompose the hypothesis 1,2 into simpler aub-hypotheses oo > the hypothesis space Σ' into an executable function space Σg, is then used to 'compiled' the sub- hypotheses 1o into an executable function e This executable function is directly applicable to the observations xf, allowing for the derivation of conclusions Vf, that is:
[h6 hº, A. ..... A translator function g Σ* Σg. which maps
T = ((²))(a²)
4

---

Published as a conference paper at ICLR 2025
Task: Inductive
(a) Hypothesis Deco recomposition
(b) Execute & Verify
Example
Hypothosis
Example
Decomposition
Executable function
[Seep Identily position Translator
Stop 3: Adjust the cotumn count volaes
of in the input matrix:
Example
[Step 2): Count the number of
solumn.
aéjusted counts
for count colurn, colurn_counts. áf count en adjusted www.tttstttpppo. (opeett)
Example
(Step the
count values.
(Step 4]: each row the output grid with the adjusted
wlif count 3: adjusted_ cesssted_contsttot append())
elset
Actual
Expected Output
Seen Observation
adjisted
countscoocsooooom Selistte__cunts.orre
osperdd())
Output
(c) Amend ment Submission
(d) Feedback N
(f) Validation
Polished
Exocutable function e
Example
Example
Hypothesk
[Step 1): identifythee the posiion
adjusted_com
o in the input matrix
[Step Count
of
columnn.
(append())
Example
[Step 3) Adjust the column vouutvallus,, possibly by
Example
agpundd))))))
increasing decreasing
specific
aappend())
[Step each row outputgiin grld with the adjustsdd column counts.
adjusted_ counts-ppendd
Actual
Expected
Unseen Observation
adjustod, (gpend))))
Output
Output
Figure 2: An overview of pipeline to solve code reasoning task. We decompose the hypothesis and generate executable functions step by step. After comparing the results with the seen observations and receiving feedback, we propose amendments, reflect potential errors at each step, and gener- ate revised hypotheses. This process is repeated until a valid problem-solving pathway is discovered. For concise expression, show partial code snippets.
Feedback Fly;, TT) ] is used to evaluate the conclusions drawn from the current hypothesis, guiding the LLM reflect on its sub-hypotheses. Through this iterative process of reflection, the model gen- erates new hypothesis h² for the next iteration. Finally, the problem-solving pathway f is applied unseen observations X,, and the model's generalization performance is assessed by measuring its accuracy:
Σ [ffx=)) y. EEE
acc,
X
The preceding section presents unified framework for the hypothesis decomposition and amend- ment method. However, the implementation specifics differ across various tasks. In the following sections, will introduce these task-specific variations in detail.
Hypothesis Decomposition. We recognize that complex logical reasoning problems difficult to encapsulate a single reasonable hypothesis, which can adversely affect the performance of LLMs. Therefore, require the LLM to decompose its hypotheses. Specifically, given obser- vation x;, the LLM gradually presents corresponding hypotheses step by step. For inductive code reasoning, ho represents the step-by-step hypothesis of the input-to-output transformation rules. For deductive and abductive code reasoning, ho refers to the step-by-step hypothesis regarding the func- tionality of the program.
Execution Verification. After obtaining the hypothesis, need to apply it to the observations. However, hypotheses are often not directly usable, so we need to convert the decomposed hypothesis into executable function through translator g. For inductive code reasoning, the executable function is a program; for deductive and abductive code reasoning, the executable function is the predicted output and input, respectively. These three types of task then obtain the actual execution results, and the feedback generated by the compiler is provided to the LLM help further refine and adjust the sub-hypotheses.
compiler to
Amendment Submission. During the amendment submission stage, there significant dif- ferences in handling the three tasks. The LLM receives validation feedback from the tools and generates amendments based on this feedback, reflecting possible issues in the previous hypothe-
5

---

Published as a conference paper at ICLR 2025
Table 1: RHDA method inductive code reasoning task. T refers to the maximum number of iterations. N refers to the number of candidates.
Accuracy
Task Accuracy
Method
List Func
MiniARC.
RobustFill
Despcoder
List Func
MiniARC
RobustFill
Deepcoder
IO CoC
64.85
28.21
61.74
23.78
38.00
13.08
21.74
10.42
44.90)
10.90
37.39
30.90
33.60
21.74
19.79
42.45
10.90
31.30
26.39
34.40
4.62
13.04
13.54
SC (N-))
52.95
12.31
46.09
37.85
41.20
9.23
26.09
26.04
SR (1-b)
51.10
10.26
41.74
36.81
41.60
21.74
w/o Sub-Hyp
42.45
7,95
40.87
18.05
33.20
4.62
21.74
9.37
w/o Amend
47.10
8,46
35.65
30.21
36.40
6.92
17.39
19.79
T-2, N=1
51.05
12.56
43.48
38.89
41.20
10.77
30.43
23.
Tw3,
53.20
47.83
38.
30.43
26.04
T=2, N=3
N=3
58.35
19.74
54.78
43.06
48.80
13.85
34.78
29.17
ses. The reflection process involves revising each sub-hypothesis individually, forming an updated hypothesis fı + { fi " - This process ensures that each sub-hypothesis is adjusted better align with the observations and validation results, gradually improving the reasoning path- way's 's coherence and accuracy.
EXPERIMENTS
Experimental Setup. We utilize the latest and most advanced model, gpt-40-2024-088-06 as the backbone LLM for all our experiments. We report the results using
Qwen-
max
2024-09-199 (Bai et al. (202)), Claude 3.5 (laude-3-5-sonne--2224440
in Ap-
pendix B Following the methodology of Qiu al. 2024 set the temperature to 0.7. We report
results using several methods: input-output (IO) prompting, standard prompting, Chain of Thought
(CoT) (Wei al. 2023), Program of Thought (PoT) (Chen al. 2023). Chain of Code (CoC) LLi
ct al. 2024). Self-Consistency (SC) (Wang et al. (023c) and Relf-Refine (SR) (Madaan et al.) 2024). all implemented with 2-shot learning For our proposed process, employ 0-shot prompts, allow- ing the LLM to explore boblem-solving pathways in a more flexible manner. We provide detailed prompt templates in Appendix
4.1 INDUCTIVE CODE REASONING
For inductive code reasoning, we establish four baseline methods. The Input-Output (IO) prompt- ing requires the LLM to predict outputs based all seen observations and unseen input. The Program of Thought (PoT) method generates and executes programs to derive outputs. The CoC method prompts the LLM to utilize pseudocode for reasoning in output prediction. The SC method builds upon PoT by sampling multiple programs and selecting the one that demonstrates optimal performance on seen observations. Furthermore, since each example may contain multiple unseen observations, we adopt the approach from (Qiu et al.) (2024) to define task accuracy externally. An example is deemed passed only when all unseen observations within pass; thus, the proportion of passed examples reflects the task accuracy. The experimental results are presented in Table [
The results demonstrate that the RHDA method achieves optimal performance across four bench- marks, with task accuracy exceeding that of the second- best methods by 18.45%, 5.89%, 33.31 %, and 12.02%, respectively. However, we observe that RHDA appears to underperform compared to IO prompting. This is because the IO prompt does not generate hypothesis that satisfies all ob- servations but instead predicts the output for single input. successful prediction for a single instance does not generate a hypothesis that satisfies all observations, resulting in high prediction accuracy but a relatively low task accuracy.
Ablation Study. We introduce two variants to separately validate the effectiveness of hypothesis decomposition and amendment submission. The first variant does require the I.LM to decompose
Not all methods are suitable for these three meta-henchmarks, thus we selected the most appropriate meth- ads for each benchmark.

---

Published as a conference paper at ICLR 2025
hypotheses, referred to as w/o Sub-Hyp. The second variant, termed w/o Amend, indicates that the model no longer modifies its hypotheses through reflection. The experimental results presented in Table show that the performance of these two variants declined by 25.39% 67.88% and 19.28% to 57. 14%, respectively. This finding suggests that the introduction of sub-hypotheses is a critical step, it simplifies complex problems, reducing the workload for the subsequent translator g while also enabling individual amendments to each sub-hypothesis, Nonetheless, the reflection process is equally important. Our results align with previous research (Zhao et al. 2024;Olausso al. 2024
Peng et al. 2023) indicating that rational reflection can significantly enhance performance.
4.2 DEDUCTIVE CODE REASONING
For deductive code reasoning, we select standard prompting, COT, SC, SR and CoC as benchmark methods. The experimental results are presented in Table These results indicate that the CoT and CoC methods significantly enhanced the accuracy of reasoning outcomes by guiding the model to think step-by-step about function capabilities. Our proposed method advances this further, achiev- ing optimal performance with a single round of amendments, resulting in an improvement of up to 104.37% compared with baseline method. A horizontal comparison of the two datasets revealed that, due to the absence of LiveCode in internet corpora, the performance with standard prompts showed marked advantage, with the SC method amplifying this gap. Notably, the com- bination of COT, CoC, and hypothesis decomposition and amendment enabled the LLM to exhibit substantial degree of reasoning and generalization ability, nearly solving all presented problems.
Table 2: RHDA method on deductive code rea- soning task. I refers to the maximum number of iterations. N refers to the number of candi- dates.
CRUXEval
LiveCodeBench
Standard CoT
68.75
41.18
89.12
83.14
SC (N=3)
71.12
36.27
SR (T=2)
80.38
63.73
CoC
85.62
81.37
w/o Amend T=2, N=1
86.62
71.29
90.62
84.16
data
4.3 ABDUCTIVE CODE REASONING
For abductive code reasoning, we employ the same baseline methods as those used for de- ductive reasoning. The experimental results are
CRUXtral LiveCodeBesch
00
10.00
NL12
presented in Figure 3 Compared deduc- tive reasoning, abductive reasoning involves reverse thinking process, which presents sig- nificant challenges. The LLM cannot derive program's s intermediate states through de- duction and must first establish an abstract- level understanding of the function's behav- ior before proceeding with abduction. On the CRUXEval dataset, the performance decline for abductive reasoning ranged from 8.20% to 25.52%. However, the hypothesis decomposi- tion and amendment approach demonstrate ro- bustness, as the change in reasoning modes re- sulted in only minimal performance degrada- tion (8.20%) while still outperforming baseline methods by 10.02% to 31. 31.89% on the CRUX- Eval dataset and 7.35% to 40.39% on the LiveCodeBench dataset. A horizontal comparison of the two datasets revealed a trend similar to that observed in deductive reasoning, with an overall perfor- mance decline on the LiveCodeBench dataset, suggesting complex relationship between reasoning and recall.
20
H4.4
60
Accuary (%)
50
40-
30-
20-
104
Standurd
Cot
(8+3) (f=2)
Sub
Figure 3: RHDA method on abductive code rea- soning task. T refers to the maximum number of itcrations. N refers to the number of candidates.
4.4 QUALITATIVE ANALYZE
We select some cases to conduct in-depth exploration of the quality of RHDA.
7

---

Published as a conference paper at ICLR 2025
Table 3: We compare the results obtained using the sub-hypothesis decomposition method with those obtained without it. The results without hypothesis decomposition are presented at the top of the table, while those with hypothesis decomposition are shown below. Benchmark: MiniARC-ID26. Observations
Hy Hypthsssi
Executable Function
No Sub Hypothesis:
def Eornatelac
For a given 5x5 matrix input,
Len (eackisk to or any coou for Fox in macelae cuise WaiosErezii"ooo russ be bxb natcisff
first
last row,
the second row to the fourth row. third row to the third row
seeutt (10)+5
"ygaty the now chirting mate
(unchanged), the fourth row to the
=waoll(k] maLtiki31
cwaol:10] - rattiii21
Foudta cow
Thiee zou to dleat zou
con
second row, and the fifth row first row. This rotates
result[3]
matrix]0]
Fiiner faurch
24301114]
maLrixik]
Second zow 221ch
the rows by two positions.
returs zeault
def (g(11)))
/Stup 21 Jountaty non vazu zova
Sub Hypothesis: Step I: Identify the non
non_ierrs_oos Lror for pow as geid it any troel arep Reverse the ander of con-dero FoN
Step 2: Move non-zero rows to the bottor, grid.
Step Shift all ruws down
nur saroo rows lenigzial - len (noo, pero rowss i Stee 4t create the aee goid with seco zowa as the top saso_pow = 199) Santerid(0]] for in rangeioun__eess_ee arep doskiine
Step 4: Repeat steps for next input.
non-zerro
gold zutuzn awvgerid
Hypothesis Decomposition Reduces Task Complexity. In Table we present a qualitative anal- ysis of the MiniARC benchmark, comparing the effects of using hypothesis decomposition versus not using it. As illustrated in the examples above, without hypothesis decomposition, the descrip- tions require a substantial amount of language, which ultimately leads to severe hallucinations in the program and results in failure. In contrast, the examples below, which utilize hypothesis decom- position, present clear and executable objectives, enabling the translator to easily write executable functions and achieve successful solutions as instructed.
Table 4: We present the additional improvements resulting from the use of amendments. The results shown above are those obtained after the initial hypotheses, while the results displayed below reflect the outcomes following the submission of amendments and subsequent reflections. Benchmark: List Function-ID29.
Observations
Rounds
Executable Function
Round 1:
def fnllsti it
Coaok ie Lie dize hax Zwooz than Eve siuoentz
Step I: Remove elements from the of the input list until a "9' is encountered. Step If '9' present. remove all elements after the last occurrence of '9', Step If "9" not present, remuve the last elements of the list.
retura
7. Conce de rgr Se presest do the 2ier
at in Luks
Pinn Lie zust oocuermnce
(0, B, 3, 91 (0, B] [8, 2]
iast_nton_indden
Raturn the liee up and instustngg the Lart (p*
14, 8, 71 (4)
Step 4: If the list hus fewer than two
elae:
return 1st (ilast_,nise wtt.eniee___eeeeeeee (xdexx1)
22 tpr not prezent.
elements, return an empty
1st[1-2]
Round 2:
det čn intiipu__Listr:
Step 1: Remove the last two elements from the input list.
Recone the iaze two el elscenta from the iepur Ziet noditind_iaar sspor_]ise [i=2]
the 219t has ceser chan two eicoents cecurn return Std
Step 2: If the resulting list has fewer than two elements, retur an empty
Amendments Guide LLM Towards Correct Pathway. We present qualitative analysis of the use of amendments in the List Function benchmark in Table 4 The upper section displays the ini- tialization of the hypothesis, where the LLM generates a potential guess based on the observations and translates it into an executable program. After offloading the execution to the tool (e.g.. Python executor) and receiving feedback, amendments are proposed to modify the initial hypothesis. Fol- lowing this reflection, the I.LM re-optimizes the rules, ultimately yielding the correct execution results. More qualitative analyse examples please refer to Appendix E.I
Failure Analyse. We also conduct an in-depth analysis of the reasons behind process failures in RHDA, detailed in Appendix E.2 Our findings reveal that the primary limitation arises from the stricted intrinsic reasoning capabilities of LLMs, which continue to face challenges in understanding and addressing complex problems. These limitations are primarily reflected in two aspects:
8

---

Published as a conference paper at ICLR 2025
Task
Initial decomposed hypothesis Ag:
The Generated Scripts
Executor
g
1. I need to take the pie.
[grab the pie] Igo fiidge open fridge, store the pie)
Store the Pie in Fridge.
2. I need to store the pie in fridge.
Updated hypothesis h;:
.9
1. need to get to the pie, and take the pie.
[welk to the pie, grab the pie] [go to fridge, open fridge, store the pie)
2. need store the pie fridge
Walk to the Pie
Grab the Pie
Open Fridge
Store the Pie
Figure 4: We demonstrate how RHDA can extended to the VirtualHome framework to success- fully complete the task of storing the pie in fridge.
Difficulty in Generating Accurate Sub-Hypotheses: The generation of sub-hypotheses dur- ing the reasoning process often proves inaccurate, leading subsequent breakdowns in reasoning chains.
Sensitivity to Initial Hypotheses: The model exhibits a pronounced dependency on its ini- tial hypotheses. Even when feedback provided through amendment submissions, the model struggles to break free from its original thought framework, constraining its reason- ing capabilities.
4.5 RHDA IS A FLEXIBLE AND SCALABLE PROBLEM-SOLVING PATHWAY
We consider extending the RHDA pipeline more complex scenarios. To this end, select Vir- tualHome (Puig et al. 2018 2020). sophisticated multi-agent platform for simulating household activities,
exploration subject. VirtualHome comprises tions and objects that can be combined into high-level instructions. For example, '(char0) [walk] (salmon)' describes character 0 walking to the salmon. Given a specific scenario, the LLM tasked with completing concrete housework using a series of high-level instructions. As depicted in Fig- ure 4 and guided by the RHDA process, we demonstrate how the LLM successfully accomplishes the task of storing pie in the fridge through the methods of hypothesis decomposition, execution verification (offloading to VirtualHome engine), and reflection. we show another example App- neidx D
of predefined atomic
LIMITATION AND DISCUSSIONS
Benchmark Selection. This paper represents the first systematic exploration of the code reasoning task, focusing on the analysis of three forms of logical reasoning: inductive, deductive, and abduc- were unable collect all benchmarks for testing. Our aim is to stimulate in-depth discussion on this topic and inspire meaningful follow-up research. While several excellent studies utilize code address logical reasoning tasks (Zelikman al., 2023) Hu et al. 2023 Srivastava et al. 2024 Liu et al. 2024a), we did not include them here due to their differing starting points from this paper.
tive. Due time and cognitive constraints,
Hyperparameters. The goal this paper is to explore the potential LLMs in code reasoning, rather than solely improving the performance of specific code reasoning task. The RHDA frame- work serves as preliminary exploration process; therefore, we didn' fully optimized the prompt templates specific hyperparameters (such temperature, T, and N) utilized. In the inductive code reasoning task, we examined a broader range of hyperparameter settings to illustrate that ex- ploring multiple pathways aids in effectively solving problems.

---

Published as a conference paper at ICLR 2025
Task Assessment. We propose novel code reasoning task, and experimental results indicate that current of-te-of-the-eee art LLMs exhibit limitations in tackling this task. In the future, we aim to further explore this challenging area and investigate the boundaries of human capabilities in similar tasks.
RELATED WORK
2023). LLaMA Touvron al., 2023 and Claude (Anthropic 2024), demonstrate impressive reasoning capabilities across various NLP tasks (Zhang et al. 2024). However, due to the problems of direct reasoning with LLMs such as hallucinations (Ji al.) (023), researchers have proposed several methods to enhance the reasoning power of LLMs. For example, (Zhou et al., 2023 Xue et al., 2025) decompose complex tasks into sequential subproblems, while (Sun et al. 2024) refine reasoning through environment feedback.
Reasoning with LLMs. LLMs such as GPT (OpenAT
Moreover, intermediate representations, such as graphs (Jiang et al. 2024). planning domain defini-
tion languages (PDDL.) (Guan et al.) 2023), and triples (Wang al. 2023a), have been employed to enhance LLM's reasoning. Most recently, OpenAl ol (OpenAl (024)) demonstrates strong reason- ing capabilities and broad world knowledge. Upon further contemplation, it is capable of reasoning through complex tasks and addressing challenges that exceed those faced by previous scientific,
coding, and mathematical models.
Simultaneously, Nomain-specifie reasoning with LLMs has gained attention. Kimm et al. 2024a) enhance reasoning outputs in computer tasks through recursive critique. In case study using Minecraft, (Wang et al., (023d) introduce a Describe, Interpret, Plan, and Select framework for open-world multitasking. In computer vision, (Gupta Kembhavi| employ Python-like mod- ular programs to tackle complex tasks. Nonetheless, reasoning in code remains area yet to be thoroughly explored.
Improvement with Reflection. Reflective ability is regarded as a crucial metric for evaluating LLMs as agents. Reflection can be categorized into internal and external based its feedback source (Pan et al. 2024). Internal reflection relies feedback from the model's own knowledge and parameters (Huang al. 2022), while external feedback comes from various sources, including humans WWag et al. 2023b), other models (Paul et al. 2024), external tools (Gou et al. 2024 Chen
et al. 2024), knowledge bases (Yo al. 2023b [ssa al. 2024). (Huang et al. (024) find that LLMs struggle to self-correct their responses without external feedback, and in some cases, their
performance may even decline following self-correction. Our work focuses on leveraging external
tools, such as compilers, to generate feedback and enhance the performance of LLMs.
7 CONCLUSION
In this paper, we emphasized that the reasoning capabilities of LLMs still depend recalling prior knowledge and highlighted that code reasoning has not been sufficiently explored as novel perspec- tive for examining the boundaries of LLM capabilities. Based on this consideration, we designed three merra-benchmark--inddee reasoning- drrwwing on established forms of logical reasoning, and instantiated these benchmarks into eight specific tasks. Experimental results indicated that these benchmarks present significant challenges for current state-of-the- LLMs. To initially explore code reasoning tasks, we proposed a method involving Reflective Hypothesis Decomposition and Amendment (RHDA). This method was iterative: L.MSs need to generate decomposed initial hypotheses based on observations and employ a translator to interpret these into executable functions that can be directly applied to the observations. After obtaining the executable functions, we performed execution verification and submit amendments, allowing for reflection and refinement of the sub-hypotheses. Experimental results demonstrated that this approach, which integrated the principles divide-and-congee and reflection, can flexibly solve complex code reasoning problems, achieving performance improve- ments of to 3 times compared to baseline methods. Finally, we extended this process to simulate household tasks in real-world complex scenarios to validate its scalability and transferability.
code reasoning, deductive code reasoning, and abductive code
10

---

Published as a conference paper at ICLR 2025
8 ACKNOWLEDGMENT
This research was partially supported by the Key Technologies R&D Program of Anhui Province (No. (to.202243K090220039, the National Natural Science Foundation of China (Grants No. N0.62477 62406303), Anhui Provincial Natural Science Foundation (No. 2308085QF229), the Fundamental Research Funds for the Central Universities (No.WK21501 10038, WK2150110034).
REPRODUCIBILITY STATEMENT
Our code, datasets and experimental results are available at ltttps://github: htt.hhu...ommm// www..ooooooooii... TnTWow/ code_ ree_reesonnigg Additionally, Appendix H contains details about pipeline and prompts used
method.
REFERENCES
Anthropic. Claude 3.5 sonnet, 2024. URL httpss:/www.anthrrgic..oo////
claude-3- 3-oooe-e---sonnet
Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. Self-RAG: Learning to retrieve, generate, and critique through self-reflection. In The Twelfth International Confer- ence on Learning Representations, 2024. URL hSyW5go0v8
fort/forum?dd
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. arXiv preprint arXiv:2309. 16609, 2023.
Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. arXiv preprint arXiv:1611.01989, 2016.
Yoshua Bengio. From system 1 deep learning to system deep learning.. 2019. URL https:
7/rips. htt.:/pscc.c/ooooeenceeeeeee/eee https//////ecccccccceoe/eeeeeere
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Mark Chen et al. Evaluating large language models trained on code, 2021. arxiv.org/ale Frx....org/abs//2000.03
URL https://
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. Program of thoughts prompting:
Disentangling computation from reasoning for numerical reasoning tasks, 2023. URL https:
//axxiv.org/abs//222 httpaa////........
12588
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. In The Twelfth International Conference Learning Representations, 2024. URL
htttss:/copenrevieee www.teeetotunnte forummid=KuPP. did=kiidiiiii Pttckuuixxqqiqg
François Chollet. On the measure of intelligence, 2019. URL https://acxiv.orgg
01547
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, pp. 990-998. PMLR, 2017.
A. Feeney and V.A. Thompson. Reasoning as Memory. Current Issues in Thinking and Reasoning. Taylor & Francis, 2014. ISBN 9781317820130. URL htttts:///oookk gwogle..ooooooooooooooooooo..... com. hk/
books? 1=
Zhibin Gou, Zhihong Shao. Yeyun Gong. Yelong Shen, Yujiu Yang, Nan Duan, and Weizhu Chen. Critie: Large language models can self-correct with tool-interactive critiquing, 2024. URL
https://arxiss wttp:ii...rgaaa//////o//
11738

---

Published as a conference paper at ICLR 2025
Alex Gu, Baptiste Rozière, Hugh Leather, Armando Solar-Lezama, Gabriel Synnaeve, and Sida I. Wang. Cruxeval: A benchmark for code reasoning, understanding and execution, 2024. URL
wwtgg/bb////e ritpss///ariiie org/ abs 2401. 03065
Lin Guan, Karthik Valmeekum, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pre- trained large language models to construct and utilize world models for model-based task plan- ning. Advances in Neural Information Processing Systems, 66:79081-79099 2023.
Sumit Gulwani. Programming by examples-and its applications in data wrangling. In Dependable Software Systems Engineering, pp. 137-158. IOS Press, 2016.
Tanmay Gupta and Aniruddha Kembhavi. Visual programming: Compositional visual reasoning without training. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14953-14962, 2023.
Jonathan Haidt. The emotional dog and its rational tail: a social intuitionist approach to moral judgment. Psychological review, 108(4):814, 2001.
Kyle Hardman and Nelson Cowan. Reasoning and memory: People make varied use the informa- tion available in working memory. Journal of experimental psychology. Learning, memory, and cognition, 42, 11 2015. doi: 10.10377xlm0000199
Brett K Hayes, Evan Heit, and Caren M Rotello. Memory, reasoning, and categorization: Parallels and common mechanisms. Frontiers in psychology, 5:529, 2014.
Evan Heit, Caren M. Rotello, and Brett K. Hayes. Chapter two relations between memory and reasoning. In Brian H. Ross (ed.), The Psychology of Learning and Motivation, volume 57 of Psychology of Learning and Motivation, pp. 57-101. Academic Press, 2012. doi: https://doi. org/10. 01010:00066B777700--9999999---90 00002-9. URL ht tps::p////// www. www.wsciiinn scieeedieeede...ctt..... com/ Beieance/arriccee///1////7738312
Yi Hu, Haotong Yang, Zhouchen Lin, and Muhan Zhang. Code prompting: a neural symbolic method for complex reasoning in large language models. arXiv preprint 2rx.v:2305./8500 2023.
Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yucxin Wu. Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models can self-improve, 2022. URL https://azxi..rr////
2210. 11610
Jie Huang. Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet. In The Twelfth International Conference Learning Representations, 2024. hoLlhttts////pereeeee
fiet/forum?id=e Idm.iiddIIdmm
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and lon Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint, 2024.
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of ballucination in natural language generation. ACM Computing Surveys, 55(12): 2023.
Song Jiang, Zahra Shakeri, Aaron Chan, Maziar Sanjabi, Hamed Firooz, Yinglong Xia, Bugra Aky- ildiz, Yizhou Sun, Jinchao Li, Qifan Wang, et al. Resprompt: Residual connection prompting advances multi-step reasoning in large language models. In Proceedings of the 2024 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume Long Papers), pp. 5784-5809, 2024.
D. Kahneman. Thinking, Fast and Slow. Penguin Books Limited, 2011. ISBN 9780141918921. URL [tllhhttss://booo googoooooooooooo com. hh htt/bookks http:/bboooka...odllttt....
d= goC
Subbarao Kambhampati. Can large language models reason and plan? Annals of the New York
Academy of Sciences, 1534(1):15-18, 2024.
12

---

Published as a conference paper at ICLR 2025
Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks. Advances in Neural Information Processing Systems, 36, 2024a.
Schoon Kim, Suhong Moon, Ryan Tabrizi, Nicholas Lee, Michael W. Mahoney, Kurt Keutzer, and Amir Gholami. An Ilm compiler for parallel function calling, 2024b. URL /tttps://arxils
org/ 2312. 04511
Subin Kim, Prin Phunyaphibarn, Donghyun Ahn, and Sundong Kim. Playgrounds for abstraction and reasoning. In NeurlPS 2022 Workshop on Neuro Causal and Symbolic Al (nCSI), 2022.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 13-22199-22213, 2022.
Patrick C. Kyllonen and Raymond E. Christal. Reasoning ability is (little more than) working- memory capacity?! Intelligence, 14(4))389-433, 1990. ISSN 0160-2896. doi: https://doi.or//
URL https: htpp:///ww.r www.e/cceeeeeeecccooeeeeeeeeeeee
axticlee/p11/0010229966600
Chengshu Li, Jacky Liang. Andy Zeng, Xinyun Chen, Karol Hausman, Dorsa Sadigh, Sergey Levine, Li Fei-Fei, Fei Xia, and Brian Ichter. Chain of code: Reasoning with a language model- augmented code emulator, 2024. URL
04474.
Xin Lin, Zhenya Huang, Hongke Zhao, Enhong Chen, Qi Liu, Defu Lian, Xin Li, and Hao Wang. Learning relation-enhanced hierarchical solver for math word problems. IEEE Transactions on 2024.
Neural Networks and Learning Systems, 13(10))13830-13844
Changshu Liu, Shizhuo Dylan Zhang. Ali Reza Ibrahimzada, and Reyhaneh Jabbarvand. Code- mind: A framework challenge large language models for code reasoning. arXiv preprint arXiv:2402.09664 2024a.
Jayy Liu, Zhenya Huang, Zhiyuan Ma, Qi Liu, Enhong Chen, Tianhuang Su, and Haifeng Liu. Guiding mathematical reasoning via mastering commonsense formula knowledge. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, pp. 1477-1488. Association for Computing Machinery, 2023a. ISBN 9798400701030. doi: 10.1145/ 3580305.3599375 URL htttps:///oi. 10 wtt..///.....11113330303333.00.. 3599375
Jayy Liu, Zhenya Huang, Chengxiang Zhai, and Qi Liu. Learning by applying: A general frame- work for mathematical reasoning via enhancing explicit knowledge learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4497-4506, 2023b.
Jiayu Liu, Zhenya Huang. Tong Xiao, Jing Sha, Jinze Wu, Qi Liu, Shijin Wang, and Enhong Chen. SocraticLM: Exploring socratic personalized teaching with large language models. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024b. URL https:
7/ //openreview.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with seef-feee Advances in Neural Information Processing Systems, 36, 2024.
Arseny Moskvichev, Victor Vikram Odouard, and Melanie Mitchell. The conceptare benchmark: Evaluating understanding and generalization in the are domain, 2023. URL AtRLhttts://axxi
org/abs 2305. 07141
Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar- Lezama. self-repair silver bullet for code generation? In International Conference on Learning Representations (ICLR), 2024.
OpenAl. Gpt-4 technical report, 2023.
OpenAI. Introducing openai o1, 2024. URL httthtttp://peeaaii compo1/
13

---

Published as a conference paper at ICLR 2025
Liangming Pan, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. Automatically correcting large language models: Surveying the landscape of diverse automated correction strategies. Transactions of the Association for Computational Linguisties. 12:484-506,
2024. doi: 10.1162/tacl a 00660. URL https: / wwnthooloy..rrrro.ooooo
27
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. REFINER: Reasoning feedback on intermediate representations. In Yvette Graham and Matthew Purver (eds.), Proceedings of the 18th Conference of the European Chap- ter of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1100-1126, St. Julian's, s, Malta, March 2024. Association for Computational Linguistics. URL https:
Baolin Peng, Michel Galley, Pengcheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Liden, Zhou Yu, Weizhu Chen, et al. Check your facts and try again: Improving large language models with external knowledge and automated feedback. arXiv preprint arXiv:2302. 12813, 2023.
Xavier Puig, Kevin Ra. Marko Boben, Jiaman Li. Tingwu Wang, Sanja Fidler, and Antonio Tor- ralba. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8494-8500 2018.
Xavier Puig, Tianmin Shu, Shuang Li, Zilin Wang. Joshua B. Tenenbaum, Sanja Fidler, and Antonio Torralba. Watch-and-help: A challenge for social perception and human-ai collaboration, 2020.
Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yejin Choi, Nouha Dziri, and Xiang Ren. Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis refinement, 2024. URL
https://arxtt owg.or///a.........oo abs /ww./222300 2310 08559
Yasaman Razeghi, Robert Logan IV, Matt Gardner, and Sameer Singh. Impact of pretraining term frequencies on few-shot numerical reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 840-854, 2022.
Joshua Stewart Rule. The child as hacker: building more human-like models of learning. PhD thesis, Massachusetts Institute of Technology, 2020.
Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are emergent abilities of large language models a mirage? Advances in Neural Information Processing Systems, 36, 2024.
Kensen Shi, Joey Hong. Yinlin Deng, Pengcheng Yin, Manzil Zaheer, and Charles Sutton. ExeDec: Execution decomposition for compositional generalization in neural program synthesis. In The Twelfth International Conference on Learning Representations, 2024.
Saurabh Srivastava, Annarose M B, Anto P V au2, Shashank Menon, Ajay Sukumar, Ad- waith Samod T, Alan Philipose, Stevin Prince, and Sooraj Thomas. Functional benchmarks for robust evaluation of reasoning performance, and the reasoning gap, 2024.
James WA Strachan, Dalila Albergo, Giulia Borghini, Oriana Pansardi, Eugenio Scaliti, Saurabh Gupta, Krati Saxena, Alessandro Rufo, Stefano Panzeri, Guido Manzi, et al. Testing theory of mind in large language models and humans. Nature Human Behaviour, pp. 1-11, 2024.
Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adaptive plan- ning from feedback with language models. Advances in Neural Information Processing Systems, 36, 2024.
Heinz- Martin SüB, Klaus Oberauer, Werner W Wittmann, Oliver Wilhelm, and Ralf Schulze. Working- capacity explains reasoning ability-ann and a little bit more. Intelligence, 30(3):261-288, 2002. ISSN 0160-2896. doi:
00100-3.
URL http://wwww..aaaeeeeee.....oo//r
S01 612886660000
0033
14

---

Published as a conference paper at ICLR 2025
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXtv:230..3397, 2023.
Jianing Wang. Qiushi Sun, Xiang Li, and Ming Gao. Boosting language models reasoning with Shain-of-knowlede prompting. arXiv preprint ar XXiv:2306.06427 2023a.
Tianlu Wang. Ping Yu, Xiaoqing Ellen Tan, Sean O' Brien, Ramakanth Pasunuru, Jane Dwivedi- Yu, Olga Golovneva, Luke Zettlemoyer, Maryam Fazal-Zarandi, and Asli Celikyilmaz. Shepherd: A critic for language model generation, 2023b.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models, 2023c.
abtp//33../////...//////// 11171
Zihao Wang, Shaofei Cai, Guanzhou Chen, Anji Liu, Xiaojian Ma, Yitao Liang, and Team Craft- Jarvis. Describe, explain, plan and select: interactive planning with large language models enables open-world multi-task agents. Proceedings of the 37th International Conference on Neural In- formation Processing Systems, pp. 34153-34189, 2023d.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24837, 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models, 2023. URL URL https::/aaxxi..o////////o/////// wttp://ggaaaa///e/ee wttp:/o///.bb//...1111...
Jason Weston and Sainbayar Sukhbaatar. System attention (is something you might need too), 2023. URL https:
11829
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. arXiv preprint arXiv:2111.02088 2021.
Shangzi Xue, Zhenya Huang, Jiayu Liu, Xin Lin, Yuting Ning, Binbin Jin, Xin Li, and Qi Liu. Decompose, analyze and rethink: Solving intricate problems with human-like reasoning cycle. Advances in Neural Information Processing Systems, 37:357-385, 2025.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of Thoughts: Deliberate problem solving with large language models, 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023b.
Dagmar Zeithamova, Margaret L Schlichting, and Alison R Preston. The hippocampus and inferen- tial reasoning: building memories to navigate future decisions. Frontiers in human neuroscience, 6:70, 2012.
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. Parsel: Algorithmic reasoning with language models by composing decompositions. In Thirly-seventh Conference on Neural Information Processing Systems, 2023. URL [d==d9gcbVAwQ]
net. wweee/forree forum?
Yadong Zhang, Shaoguang Mao, Tao Ge, Xun Wang, Adrian de Wynter, Yan Xia, Wenshan Wu, Ting Song, Man Lan, and Furu Wei. Llm mastermind: A survey of strategic reasoning with large language models. arXiv preprint arXiv:2404.01230. 2024.
Yuze Zhao, Zhenya Huang, Yixiao Ma, Rui Li, Kai Zhang, Hao Jiang, Qi Liu, Linbo Zhu, and Yu Su. RePair: Automated program repair with process-based feedback. In Lun-Wei Ku, An- dre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Lin-
guistics ACL 2024, pp. 16415-16429, Bangkok, Thailand and virtual meeting, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/2224 2.0.2...nnings-acl.993. URL
https://acl antho ogy. fi ndi mndings-acc 973
15

---

Published as a conference paper at ICLR 2025
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuur- mans. Claire Cui, Olivier Bousquet, Quoe Le, et al. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Rep- resentations, 2023.
16

---

Published as a conference paper at ICLR 2025
A DSL GRAMMARS
RobustFill is a string manipulation task using the DSL. Figure illustrates the DSL syntax for
RobustFill. Our implementation is based on the works of ExeDec (Shi al. 2024 and Robust- Fill (Devlin et al. 2017).
Deepcoder is list transformation task using the DSL. Figure 6 This implementation is based the works of ExeDec (Shi et al. 2024) and DeepCoder (Balog et al. 2016).
Program P = (e1cat(e1,,22....
Expression
m Conststz(c)
Compose o
mi (m²) m(s)
Substring s = SubStr(k,, k2) GeetSpan((r, in, 12, GetTokenn(,
| (etUptoor)) GetFrom(r)
Modification m = ToCase(a) Replacleppi Trim() GetFirst(r::) GetAAl(r))
Substätuteer,i.e) /ubstituteelll Remove RemoveAll
Regex NUMBER WORD ALPHANUM ALL.CAPS PROFER_CASE LOWER DIGIT CEAR
Casc a
ALL_CAPS PROPER_CASE LOWER
Position & = 100 | 99 ... - 1 ... 15
1
1
1 2
100
Index = 5 -
Boundary b = START END
Character
A
Z /
01 1915
Delimiter 5 &, 6 ()8))=284 "'
Figure 5: The DSL syntax for string manipulation tasks in the RobustFill domain.
Program P
iz; in di; azi...
Initialization
INPUT
Assignment a = V + f -u
First-Order Operation f = Head(() | Last(() Accesss(n.)) Minnimmm(() Maximum(I) Sum([)
[ake(n, Drop(n,() Reverse(() Sert(()
Higher-Order Operation h
Count [ Zippith((E,1.) Scaa11(E,))
int int Lambda A
(-1) (+2) (/2) (+(-1)) (*+2) (+3) (/3) (+4) (/4)
int -> bool Lambda B = (> (x(0) (%2 == 0) (%2 = 1)
(int, int) + int Lambda 2 = (-) [m))
(min)
(max)
Integer Variable n
=
List Variable =
Variable Name
Figure 6: The DSL for integer and list manipulation tasks in the DeepCoder domain.
B EXPERIMENTAL RESULTS USING MORE LLMS
We report the performance of Llama3. 11-70--Instruee Qwen-max (gwen-max-2024-09-11, Claude 3.5 souude-----oonet-2222
using the RHDA method and compare them with GPT-4o (gpt- 40-2024-0806). The results for inductive code reasoning are shown in Table 5 The experimental results indicate that GPT-4o performs better in solving DSL problems, while Claude 3.5 excels in General Propose Language (GPL) tasks. Compared to closed-source models, the open-source model
Llama still exhibits relatively limited reasoning capabilities. However, list manipulation tasks (List Function and Deepcoder), Ilama demonstrates stronger programming abilities. In Table T
17

---

Published as a conference paper at ICLR 2025
Table 5: Performance comparison of Llama3. Instuct Qwen-max, Claude 3.5 and GPT--4o on the PoT and RHDA methods in inductive code reasoning task. T refers to the maximum number of iterations. N refers the number of candidates.
Accuracy
Task Accuracy
Model
Method
MiniARC
List Func
RobustFill
DeepCader
MiniARC
List Func
RobustFill
DeepCoder
PoT
3.08
35.25
14.78
22.92
1.54
26.80
8,70
11.46
Sub-Hyp
3.33
13.04
18.06
T=2, Ne1
3,85
32.35
20.87
11.46
3.85
26.40
13.04
7.29
PoT
6.41
41.75
36.32
25.35
3.85
30.00
21.74
14.58
Owen-max
Sub-Hyp
5.90
46.25
26.09
17.36
3.08
36.40
8.70
5.21
T=2, N=1
6.41
46.60
33.91
24.64
3.08
41.60
13.04
10.42
PoT
11.79
$1.30
30.43
39.20
27.14
13.54
Claude-3.5
Sub Sub-Hyp Hyp
12.56
53.55
22.61
33.33
9.23
42.40
8.70
16.67
Tw2, Na1
18.21
57.95
33.91
29.86
13.85
48.40
17.39
20.83
GPT-4o
Sub-Hyp
8.46
47.10
35.65
24.65
6.92
36.40
17.39
12:50
Table 6: Performance comparison of Llama3. 1omin3.1-7000 1-70B-Insttruut,, Qwen-max, Claude 3.5 and GPT-4o on the CoT and RHDA methods in deductive and abductive code reasoning tasks. T refers to the maximum number of iterations, refers to the number of candidates.
Deductive
Abductive
Model
Method
CRUXEval
LiveCodeBench CRUXEval
LiveCodeBench
CoT
40,25
53.12
38.24
Llama3.1
Sub-Hyp
30.75
6,86
50.88
8,82
T=2, N=1
45.62
10.78
59.62
40.20
CoT
81.12
86.27
75.12
58.82
Qwen-max
Sub-Hyp
78.25
81.37
72.25
59.80
T=2,
81.62
88.24
79.38
66.67
CoT
82.75
77.45
73.62
61.76
Claude-3.5
Sub-Hyp
77.75
65.69
74.75
53.92
T=2. N=1
86.88
80.39
83.38
61.76
CoT
89.12
83.14
71.00
66.67
GPT-4o
Sub-Hlyp T=2, N=1
86.62
71.29
77.12
60.78
90.62
84.16
83.75
71.57
report the performance the models in deductive and abductive code reasoning together. The ex- perimental results show that GPT-4o outperforms Claude 3.5 in of program understanding and execution capabilities. These results suggest that RHDA is framework- aggnsstic general process that can achieve optimal performance through single reflection, applicable to both Llama, Qwen, Claude and GPT series models.
C BENCHMARK DETAILS
List Function. We use the original dataset (Rule, 2020), which consists of total 250 tasks. Due to the limited context lengths of LMs, only use the first 16 examples from BIG-Bench (bench authors, 2023): 8 for seen examples and for un- seen examples. We manually examined the exem- plars and found examples are generally sufficient to describe the pattern.
Table 7: The number of tasks per dataset, the numbers seen examples per task, and unseen examples per task.
Dataset
Tasks
# Seen
# Unseen
List Function
250
8
MiniARC
130
3
RobustFill
22
5
5
Deepeoder
96
3
CRÜXEval
800
MiniARC. We the data from Qiu al.)
LiveCodeBench
102
2024). Such tasks are typically difficult to describe in natural language at abstract level. Therefore,
18

---

Published as a conference paper at ICLR 2025
did not consider them for our evaluations. As only evaluate textonly models, textual representations of the original visual grids by mapping each cell to a corresponding integer.
RobustFill. RobustFill is a string manipulation task where the model is expected to perform combination of atomic operations, such as extracting a substring from position kj to k2 us- ing SubString(k,, k1), to achieve generalization. As an example, program ToCase (Lower, SubStr (1, 3) converts full month names (January, April) to their abbreviations (jan, apr).
DoepCoder. The DeepCoder task involves using DSL to perform operations integer lists. In DeepCoder, each line represents subroutine that performs atomic operations on previous vari- ables and assigns the results to new variables. The result of the final line is the program's out- put. For example, program a f [int] b +- FILTER (<0) a c + MAP (+4) REVERSE b (where "I" denotes subroutine separator.) transforms the
+ SORT input [-17, -3, 4, 11, 0, -5, -9, 13, 6, 6, -8, 11] into the output [-12, -20, -32, -36, -68]
D RHDA ACTING AS AN AGENT IN VIRTUALHOME
Task
Initial decomposed hypothesis Ag:
The Generated Scripts
Executor
need to get the towel.
[open the cabinet, grab towel]
2. need to open the faucet for water.
[walk to facuet, open facuet] [walk to shampoo, grab shampoo)
Clean the Bathr 0om.
3. need to get shampoo.
Updated hypothesis hy:
1. need to get the towel.
[open the cabinet, grab towel]
2. need to switch on the faucet for water.
[walk to facuet, switch on facuet] [walk to shampoo, grab shampoo]
3. need to get shampoo.
Open Bathroom Cabinet
Grab Towel
Switch on Faucet
Get Shampoo
Figure 7: We illustrate how the RHDA framework can be extended to the VirtualHome environment
to effectively accomplish the task of cleaning the bathroom.
We utilized the RHDA framework to drive agent actions in the VirtualHome environment powered by LLMss. Figure illustrates a task of cleaning the bathroom.
Table Execution Error Rate on VirtualHome
native GPT-4o
w/o Sub-Hyp
w/o Amend
RHDA
Error Action L Avg. Err per Step +
92
84
84
52
0.84
0.35
0.20
0.16
Avg. Err per Task $
2.09
1.83
1.75
1.08
We also provided some quantitative metrics validate the potential of RHDA a agent in Vir- tualHome. Specifically, we selected a total of 52 tasks across two scenarios in VirtualHome and manually tested their execution error rates. The test results are shown in Table which indicate that native GPT-4o struggles to handle simulated real-world scenarios effectively. The primary cause of failure lies in generating scripts that, while semantically similar to correct actions, are not executable within the environment (e.g., 'open the tap' invalid action, whereas 'touch the tap' is valid action). By employing the RHDA method, which incorporates step-by-step solutions and effective feedback mechanisms, the error rate was significantly reduced.
19

---

firee Published as a conference paper at ICLR 2025
E EXAMPLES ANALYSES
E. EFFECTIVE CASE STUDY
Table 9: We compare the results obtained using the sub-hypothesis decomposition method with those obtained without it. The results without hypothesis decomposition are presented at the top of the table, while those with hypothesis decomposition are shown below. Benchmark ARC-ID37. Observations
Rounds
Executable Function
ded intgridl
comecity the taxed zow
Stee 2: Check foz zequeace theee acze idention non-zaco nusbaza Jen cthited 2043
while nz
Round 1:
thiod_rool=] of the seguetie of Edseetost mumbere
Step Identily third row
start
Step 2: Check for nem-zerm numbers in the third row.
while i.c. i and [hanLtoe[)) =- thinnLow(ssar..e
Step 3: Replace the number
12 zeguence chroe
replace ie
Jengts be 31
the center position of the sequence.
4 sStep Jr Suplace the sequerce vich the nister Zrom the second zoe censer__iddxx stast Zength /7
Step 4: Change numbers
moptssrarm_ttibbe [0] ioenter_iadaal third rox
in rows 4 and 5 to zero.
the eeetre
third rox neleeenee (ndex) replacement nimber
kzeak Assusing only aoe sequence needr to be euplaced
elve:
Sthe Jer all nimbers do
grintsl 10.
gein]4] 10. +.a.
returs geid
fnegridt
Laizd_rev <qAd(2)
Stee 21 chiect for seguence of three or zore Edsectoxt non-tero notters (tnnntit
Round 2:
thitr__roess) Dz 7 /Pind che langth of che sequeace of Edactsiot nusbere
Step Identify the third row
stazt
Step 2: Check for non-zero numbers the third row.
while and Chird rowil) tndes_rowtstarsl
lsnqth stazt
Step 3: Replace identical numhers
J T.e segpence is chree or eore, replace it.
in the third row with the
lenge? 31
correspoading non-zero number from the first row.
-Stap Duplace the auquanee
roplaceeerr..om nomber gridio) [start]
r Replace rhe seguence with the reptaceeace nochor
thael (abaritd) tá). Leepisemeen pownoe) [0) Longgh 21 elmes
Stee Change all murbarze nove and zero for now in ranget3, grid [6] +
retuzs grid
Table 10: We compare the results obtained using the sub-hypothesis decomposition method with those obtained without it. The results without hypothesis decomposition are presented at the top of the table, while those with hypothesis decomposition are shown below. Benchmark List Function- ID2.
Observations
Hypothesis
Executable Function
No Sub Hypothesis:
del in intirput_ Lisiis
The output the element from the inpat list that is exactly in the middle of the list.
Check of the Ziet in expty or hiee only ane eteneor 1f Jan tanper___attt] <- 1a
[I + ()
resuen
siddle indor
91
iiddie_indec (3an (inper_1iat) neturn che xidile alenato aa 1ist
//
[1, 5, 0, 6, 2, 9, 31 201
return Eingur Woot/widdl Index.
16, 3,
7, 2,
9,
0,
81
Sub Hypothesis:
Step 1: If the list has fewer three elements.
rover than chree eieventa
the output is empty list.
LisEX
Step 2:10 the list has three elements,
ruturn
elam:
Recurn Tiee conratadig the tnreger
the ourput is a list containing
only the integer at the third position.
We validated the effectiveness of the proposed method using examples from various benchmarks. For instance, as shown in Table the MiniARC task example with ID 37 highlights how the LLM, after receiving feedback, successfully reflects on its errors and submits revised solution.
20

---

Published as a conference paper at ICLR 2025
Table 11: We compare the results obtained using the sub-hypothesis decomposition method with those obtained without it. The results without hypothesis decomposition are presented at the top of the table, while those with hypothesis decomposition are shown below. Benchmark Livecodebench Input-II337.
Observations
Hypothesis
Executable Function
No Sub Hypothesis:
The function 'minOperations" atiempts
to determine the minimum number of swaps needed to casure that for each index 'i', neither 'a[i]" nor 'bli]" greater than the last elements of their respective lists.
assert minnppraations((,, 1. 3. 2.) =
def mindperratt ona 311
ded 111:
bb a1:1. bI-1
For: in zange 1n31
A8 aisl al-il on DEE oE-2lx
arAl,
Sub Hypothesis:
wts: a--f- SEA S1-21
Step I: Function Purpose
raturn tnd
The goal of "minOOerations"
Step Inner F Function
attempts to that for each T....
assert assert minn0praations((222 [3, 2))
ane 111
<i-1ia Mi-3) bi-lle w1-1
Step Main Logic
It calculaties "ams" by calling 'f"
2/223
Step 4: Objective
To find inpul such that...
Table 12: We present the additional improvements resulting from the use of amendments. The results shown above are those obtained after the initial hypotheses, while the results displayed below reflect the outcomes following the submission of amendments and subsequent reflections. Benchmark CruxEval Output-ID328.
Observations
Rounds
Executable Function
Round
Step Base Case Check:
The function checks 'L' less than equal to 0. If true, it simply returns array
Step 2 Recursive Extension:
If length of "array" is less than I., it then calls itself recursively Step Return Arryy:
assert 2,(1, 4) (1,2,
veturn stray
WEDRY.
weccaay-xtteendddi.. CAEzay, (anteccup)1)
If the array is already of
length 'L' longer, the
function simply aeturns the armyy without any modifications.
Round 2:
Step 1 Base Case Check:
Step Recursive Extension:
Step 3 Return Arry:
assent (11.),3)) (1.22,,,,
Step 4 Example Check: original
extends '11 2, 3J' by 'II 2, 3J resulting 11, 3. 2,
In Table 10, hypothesis decomposition reveals that the output number determined not only by its position at the middle of the input array but also by being the third character.
In Table 11 compared to models without hypothesis decomposition, those utilizing this approach progressively analyze the function's 's behavior, ultimately achieving an abstract understanding of the program and making accurate assertions. In Table [2 for complex recursive function, while the LLM accurately grasped the overall functionality of the function through hypothesis decomposi- tion, encountered difficulties during the detailed analysis of specific instances. Following the submission of revised solution, the LLM reflected on its errors and successfully resolved the is- sue, addressing the collapse of the overall logical chain caused by a failure in a single step during multi-step reasoning.
21

---

Published as a conference paper at ICLR 2025
Table 13: Failure case study. The observations indicate that the hypotheses proposed by the LLM are overly simplistic, rendering it difficult to account for all possible cases. Additionally. manual inspection and efforts summarize these hypotheses proved challenging. This limitation is one of the primary factors contributing to the LLM's failure in this task. Benchmark: List Function-ID9.
Observations
Rounds
Executable Function
del Intingut_.isttr
Recovea the diees adeaent from the Mipue 3scepero.
Round I:
B] [8]
Remove the first element
Chack ix the znput 1lat La expty if not saper_atat: veturn
(T, 5, 8, 4) -1 15,
from the input list.
[8, ... 9] [2, .... 91
Rlst
13, 2, 1, 9, 7, 81 (2, C1
kacad simnool raturn [nper_atae]1:]]
def Intingutt
Feom: the input list.
Round 2:
Remove the first and the last elements from the input list.
Check riee Frer as lees that sceawsty
Lapp...___A
zeturn
Aeesrn the Ziez exclading the sicat and Just wzunenco
retumn Aatt.__aattttt-s
Table 14: Failure case study. The LLM make some redundant hypotheses, which led to failure. Even after amendments, was unable to break free from its original thought framework, resulting a failure to reflect effectively. Benchmark: ARC-IDS.
Observations
Rounds
Executable Function
def dn (ccidi:
12 not geid not qxid[0):
return grin
(g
Create goid inatialleed with pezsa
Round 1:
neu_grid 1131 non_actl for in cange((rrn_ross)
for cat. zange (nin_esse)
Step I:
Identify non-zero elements the input grid.
Cxilest noo s9zo eisentt da cuzzent culaan
Iosadleow] (o01. 1f gridizov) [so1] 1-
bange Inmerross)
Step 2: Shift all non-zero elements down one row.
22 chare are non-zero
elesedes, abift chee doen by coe 2oV
non 2e50 eleeences
by
wrop-around
Step Repeat the process for each input-output pair to verify consistency.
sler in sousezate new row 11 15 & now rous
sbifced leleeeeeeess frex rool elee
Find the susanse waiee wnong the atillted stunmit
FEEE the ancire eatuse in the new grid kieh the naxteus valse for row in cange (nnup nex www.g:idlooo (co1] Pak_value
nev_arid
def tr
crid grid]o1:
zecurs geid
rowr, cole lenigridi, Senigrsd(0:)
arap Idearify sen_cccoppsattinn for sangeltowe): for in zanga (ocke): 1f cristz] [c] 1e di non
paeseione
Round 2:
Step I-ieetify non-zero elements the input grid.
Step 2: Shift all non-zero
positions.ageendii it, 01
one row. Step 3: In the resulting grid, fill each row with the maximum value from its respective column.
elements
# seppp 21 shizt nst-2eze ezusenta donn mideossLronitiinn 11 12 + 13 1 cowa, 8) foe An 13 son, san__aro_paaationa
drap 3/ neterenn the asstoue valce for each coluen J Ezze the anilted posicions
considering only the shifted elements.
(Mn.rrlio = [E] usla
for E, aitteed ass_uslunsje)
Step 4: Repeat the process for each oulput pair verily consistency.
jesoossssttoetee geidte1/e1
I stop ei conatruct the new grid
sekLizid a (10) cola for in zange [ccnel] tor E, anifteslpccitionn gridiviicl valuesio!
roturn 2enLgzid
E.2 FAILURE ANALYZE
We analyze RHDA's performance in numerous failure cases and summarize the underlying causes of these failures. Our findings suggest that the primary reason can be attributed to the insufficient
22

---

Published as a conference paper at ICLR 2025
intrinsic capability of LLMs in code reasoning tasks. This limitation is specifically reflected in two aspects:
Sub-hypotheses fail to address the problem: For tasks that are overly complex or abstract (e.g., cases shown Table (3), even though hypothesis decomposition attempts reduce task complexity, LLMs still struggle to handle them effectively.
Amendments fail correct sub-hypotheses: While amendments leverage external feed- back to help LLMs reflect on their mistakes, the models often remain confined to their existing thought framework, even after recognizing errors (e.g., cases shown in Table 14. This results in the correction failing to resolve the issue.
These observations indicate that for tasks exceeding the intrinsic capabiliitess of LLMs, relying solely on reflective hypothesis decomposition and amendment may not be sufficient to improve the model's performance.
F COSTS
Table 15: Avg. API calls and Total Cost using GPT-4o.
Method
Avp. CPlls
Total Cost (vent)
List Fune
MiniARC
RobustFill
Despodeer
List Fune
MiniARC
RobusiFill
Deepoddrr
IO
4.0
5.0
3.0
10.2
4,6
2.0
3.3
PoT
3.7
1.2
CoC
1.0
1.0
1.0
1.D
11.0
9.0
1.1
1.4
SC (Nm3)
3,0
24,0
15.0
9.0
5.3
3,7
0.6
1.2
T-2, N-3
5,9
5.6
8.6
4.0
3.1
4.7
Method
Deductive
Abductive
Deductive
Abdlative
CRUXEval
LiveCodaBench
CRUXEval
LiveCodeBench
CRUXEval
LiveCodeBench
CRUXEval
LiveCodeBench
Standand
1.0
1.0
1,0
1.D
2.9
0.5
3.1
1.5
CoT
1,0
1,0
1,0
1.0
19.4
3.7
19.5
3.3
3.3
1.5
SR (T=2)
1.6
1,7
1,4
1,5
3.8
3.4
1.6
CoC
1.0
L.0
L.0
LD
18.3
4,1
19.0
3.4
N-2
19.0
4.4
18.8
In Table 15| we present the average number of API calls and the total cost for each task. We used GPT-4o, with an input cost of $0.0025/1K tokens and an output cost of $0.01/1K tokens. The results indicate that our approach still demonstrates high cost-effectiveness for certain tasks.
G TRADE OFF BETWEEN NUMBER OF ITERATIONS AND PERFORMANCE GAIN
(b)
RobustFil
DespCoder
Ascurayy
Beration
Berabss
Berallan
Staratian
Figure 8: In the inductive code reasoning tasks, as the number of iterations increased, the perfor- mance continued to improve.
In this section, we investigate the impact of iteration count on the performance of three types of reasoning tasks, with experimental results illustrated in Figure X and Figure 9 For inductive and abductive code reasoning tasks, performance consistently improved as the number of iterations in- creased. However, the rate of improvement diminished, with marginal gains becoming less sig- nificant at higher iteration counts. Conversely, for deductive code reasoning tasks, performance followed rise-and-fal anll trend, initially improving but declining with excessive iterations. These findings suggest that while increasing the number of iterations can enhance performance for general code reasoning tasks, is crucial to balance iterative gains against potential performance instability.
23

---

Published as a conference paper at ICLR 2025
CRUXEval
LiveCodeBench
Arcuracy (9))
10
70
70
20
Deductive
Itoration
Iteration
Figure 9: In the deductive code reasoning tasks, the performance slightly decreased as the number of iterations increased. Conversely, in the abductive code reasoning tasks, the performance consistently improved with an increasing number of iterations.
H PROMPTS
Table 16: Prompts used in our study. () refers to a placeholder.
Type
Prompt
Generace a rule that maps the following inputs to their corresponding outputs step by steps. (Task description)
Hypothesis Generation
(Examples)
Please format your
follows:
[Rule format)
Your rule: (Rule)
This rule does not work for the follewing examples.
[Feedback]
Amendment Submission
Please careful ly reconsides each of your steps to ensure that the rules are correct. systematically generate new rules, step by step. (Feedback description) Please format your rule follows:
(Rule format)
You are expert Python programmer. Write Pyther
function 'fr.' for the following rule. (Translation Example description]
Ilyothhsss Translation
Rule: (Rule}
Generate an output correspondirg to the given input based on the rule. (Application Example description)
Rule Application
Rule:
(Rule)
Input: (Test input]
Output:
24


Reviews:
[{"review_id": "yPRPMNZuUp", "reviewer": "Reviewer_773h", "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.", "questions": "Can you provide any empirical evidence to back up the many claims made in the article?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n\nIt 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.\n\n  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.\n\nFurther, 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.\n\nThe 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.\n\nThere 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oUHrwjxkc6", "reviewer": "Reviewer_FKt4", "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.", "questions": "1. Example analysis is said to be shown in Appendix E, but Appendix E is empty. \n2. How sensitive is the method to the quality of the initial decomposition? Are there cases where poor initial decomposition cannot be recovered through amendments?\n3. 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?\n4. The computational overhead analysis is missing:\n -  What is the computational cost compared to baseline methods? \n -  What is the trade-off between the number of iterations and performance gains?\n5. 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel formulation and pipeline:\n    - The paper introduces an intermediate task between reasoning and recall, giving us the ability to understand LLMs more deeply\n    - RHDA pipeline demonstrates robustness in handling complex reasoning tasks\n    \n2. Comprehensive Evaluation: \n    - Three types of meta-framework with 8 specific benchmarks\n    - Evaluation across different model types (GPT-4o and Claude 3.5)\n    - Thorough ablation studies show the importance of each component.\n3. Strong Results:\n    - On inductive reasoning: RHDA outperforms baselines by 18.45% (List Function), 5.89% (MiniARC), 33.31% (RobustFill), and 12.02% (DeepCoder)\n    - On deductive reasoning: Achieves 90.62% on CRUXEval and 84.16% on LiveCodeBench\n    - On abductive reasoning: Achieves 83.75% on CRUXEval and 71.57% on LiveCodeBench\n4. Extensibility: Successfully demonstrated application to VirtualHome environment, showing the framework can handle real-world complex scenarios like household tasks.", "weaknesses": "1. Limited Theoretical Analysis: \n  - 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.\n2. Limited Real-World Validation: \n - 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.\n3. Incomplete Error Analysis: \n- 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.\n4. Complexity Overhead: \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KUVkcvcSUg", "reviewer": "Reviewer_JURK", "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.", "questions": "1. What is the difference between Sub-Hyp and Chain of Thought?\n\n2. 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.\"?\n\n3. At the bottom of page 7, \"...we present a quantitative...\", did you mean qualitative?\n\n4. 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.\n\n5. What is the cost of RHDA? Does it generalize to other non-symbolic domains?\n\n6. How does your method compare to self-refine?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "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).\n\nquality: the paper conducts a systematic investigation of code reasoning tasks and an additional planning task, which is a very comprehensive task setting.\n\nclarity: the paper is generally easy to follow.\n\nsignificance: it is important to understand LLMs' capabilities and limitations.", "weaknesses": "Generally, the contributions of this paper are not strong enough.\n\n1. 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). \n\n2. If the strongest contribution is RHDA, I wonder how it compares to other prompting methods such as self-refine [3].\n\n2. 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.\n\n[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.\n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)