What Makes Large Language Models Reason in (Multi-Turn) Code Generation?

We thank the reviewers for the encouraging comments and the time dedicated to this. We address the comments and questions below:

Although this work has solid empirical evaluations and good presentations, the novelty is a bit limited by combining existing works together, including CoT strategies, error-feedback granularities, and Pass n@k.

We thank the reviewer for the assessment of our work. We now clarify where the paper stand:

Existing works in the code generation domain are substantial, but fragmented, on studying CoT and self-repair (multi-turn) individually. It is still an open question of how different CoT prompts perform when entangled with multi-turn execution feedback, and whether the performance differs at scale. We aim to establish a solid empirical baseline with a systematic experimental survey.

This paper introduces novelties including the insights but also the methodology of our empirical survey in the prompting space (as shown in Figure 3) and at scale (pass@100). We go beyond simple prompt engineering as we identify code generation “trajectories” combining different types of prompts but also external tools (Python code execution). The insights, obtained only from extensive experiments across sampling budget and model sizes, are novel. We are glad that the reviewer finds them interesting. We believe they will motivate further work for fine-tuning LLMs as we started with our RFT experiments.

As for the RFT part, although I think it is a novel method used here,I would like to see more details on it to explain it clearly, with details on how it is finetuned with.

We thank the reviewer for acknowledging the novelty of our RFT approach on multi-turn CoT traces.

We have enriched Appendix B to make sure we include the details for each step in the RFT: generation, filtering and post-processing, deduplication and decontamination. This includes not only the experiment configuration but also the statistics of the data we gathered, such as the total number of tokens. We also add more finetuning details such as all the necessary hyperparameters and design choices.

To explain more clearly here, we use the CoT-retry method (multi-turn CoT) to generate 200 samples per problem on all of the DMC training split. Each sample solution will yield different trajectories either:

• problem statement $\rightarrow$ code 1
• problem statement $\rightarrow$ code 1 $\rightarrow$ execution feedback + reasoning prompt $\rightarrow$ code 2
• problem statement $\rightarrow$ code 1 $\rightarrow$ execution feedback + reasoning prompt $\rightarrow$ code 2 $\rightarrow$ execution feedback + instruction prompt $\rightarrow$ code 3

The execution feedback here is based on evaluation on the public tests only. The specific reasoning and instruction prompts are detailed in Appendix G.3. To select which trajectories will be part of the fine-tuning dataset, we evaluate the last code generated (code 1, code 2 or code 3 depending on the number of turns) on the public, private and public tests. We keep trajectories which pass all the tests and discard the rest.

We fine-tune our model on these trajectories by predicting the final code solution based on the context, i.e., problem statement and previous code attempts. The model therefore learns correct code but also how to self-correct based on execution feedback and how to reason based on CoT prompts as highlighted by our results in Section 5.3. I hope this clarifies the RFT approach further.

Limited theoretical analysis of why certain prompting strategies work better than others. Although the authors presented solid empirical results on the prompting strategies ablation, I will still wonder why it works.

Understanding the mechanism and interpretability of CoT prompting from a theoretical viewpoint is an active research field. For example, Li et al. [1] studied the expressiveness of transformers with CoT under computational complexity framework. Our work is orthogonal to this line of work as the scope of this paper is to establish a comprehensive experimental survey of various CoTs at scale in multi-turn code generation domain with empirical insights.

We conduct experiments in which we use explicit prompting on this (namely the “Fixme” and “Analyze” and the combination) after giving the execution feedback. We show the prompts here:

• Retry (default): “Give it another try.” (Used in the paper)
• Fixme: “Generate a fixed version of the program to fix the failing test.”
• Analyze $\rightarrow$ Retry: “Analyze the execution feedback. If runtime exception, identify the source. If wrong answer, simulate and analyze how the input maps to the actual output in your code and where it differs from the expected output. After that, give it another try.”
• Analyze $\rightarrow$ Fixme: “Analyze the execution feedback. If runtime exception, identify the source. If wrong answer, simulate and analyze how the input maps to the actual output in your code and where it differs from the expected output. After that, generate a fixed version of the program to fix the failing test.”

We show the multi-turn results (reported as 1@3 / 100@300) on CodeContests test set below:

As shown in the table. explicitly prompting the model to focus on the failing tests and fix it degrades the performance for the 8B model in 1@3 and 100@300. For the 70B model, the 1@3 increases by 1.1% while the 100@300 drops. This shows an interesting exploration-exploitation trade-off. As we posit in the Appendix C.6, the bottleneck of solving competitive programming problems like CodeContests is rather the algorithmic reasoning ability but not the bug-fixing ability.

We have added this experiment and the analysis in Appendix E.1.

We here share another insight here from what we observe in the experiments: Explicit prompting to fix the failing tests might work in a fully-observable environment (i.e., all the tests are used for feedback), but might encounter challenges in a partially-observable environment (i.e., only public tests as feedback and private tests as evaluation), which is our setting.

For additive reasoning prompts experiment in table 6, what happens if each sample uses a different COT prompt?

To clarify, in table 6 we tried to understand whether adding reasoning and instruction prompts would further boost performance; however, we keep the same prompt combination for all samples. We pick the best performing CoT candidates from the single-turn 8B setup; +1 reasoning we add a second turn of reasoning before code generation and +1 instruction we add an instruction prompt at the second turn of multi-turn. We clarify this further in the Appendix Table 7.

Obtaining the Oracle best number would require 9x7x9x7 prompt combinations multiplied by the number of samples. Our results for table 6 are obtained from a smaller grid search where we select CoT prompt candidates that perform well on a smaller scale, e.g., single-turn setting or 8B model.

However, for single-turn, 1 reasoning x 1 instruction, we provide the upper bound estimation (obtained from a grid search of 63 runs) of choosing the best reasoning and instruction prompts per sample in a post-hoc manner. This increases the performance significantly while the prompts would be heavily cherry-picked per sample and the test set performance is exposed.

We update this in Appendix K.1.

We thank the reviewer for the constructive review and the time and effort dedicated to understanding our paper and to the review. We address the comments and questions below:

Limited novelty: There is substantial existing research on CoT and self-repair in the code domain, which somewhat limits the paper's originality.

We thank the reviewer for acknowledging the novelty of our categorization of existing CoT prompts into reasoning, instruction and execution feedback and we are glad that the reviewer finds this interesting.

We acknowledge that there is substantial research on CoT and self-repair in the code generation domain. This breadth of existing work underscores the importance of our study: To the best of our knowledge, existing research focuses either individually on CoT or individually on self-repair (often using pass@k metrics, not comparable to single turn). Besides, empirical studies on CoT in a systematic way are mostly done in the math reasoning domain, e.g., [1].

With prior work being abundant but fragmented, our study addresses the lack of systematic evaluation and comparison with a large-scale experimental survey of single-turn CoT and multi-turn code generation entangled, and conducts a fairer comparison under pass n@k, as highlighted by Reviewer 8tPn. Our work contributes both methodological clarity and novel insights:

1. Interactions of CoT and self-repair in multi-turn context, through our new categorization of the prompting space into reasoning, instruction and feedback.
2. Comparison at scale of multi-turn and single-turn with a fixed metric. To the best of our knowledge, there has not been a large-scale (with 6 models of size ranging from 8B to 405B, up to 200 samples per problem), systematic experimental survey that entangles single-turn CoT and multi-turn CodeGen under a consistent evaluation metric, such as pass n@k. We adopted this metric to ensure fairer comparisons, as highlighted by Reviewer 8tPn.
3. Novel RFT method on multi-turn CoT data to internalize both reasoning abilities and capacity for the model to self-correct between turns which further boosts performance.

Beyond novelty in the methods studied, we also provide key insights (3 from single turns, 3 from multi turns) from our extensive experiments at scale worth sharing with the community.

COT-Retry prompts seem like an arbitrary combination of prompts. Why this particular combination? The paper lacks any chain of thought prompting specific to reasoning about why the test failed or how to fix the test.

We separate this comment into 2 parts to answer:

1. Regarding the CoT-retry:

Thank you for pointing this out, we have detailed this further in Appendix G.3 (updated version). We use this combination as our experiments show that it’s the most generalizable across models and sample sizes. For all reasoning and instruction prompts combinations on the CodeContest test set, we calculated the delta of pass rate improvement with respect to the baseline, i.e., $\text{delta} = (x - \text{baseline})/ \text{std}(x)$ where the baseline is the pass rate without any CoT prompt, $x$ is the pass rate for a combination with a specific model. We average this delta across all models (Llama 3.0 series, Llama 3.1 series and GPT-4o) and look at the Top 3 best performing combinations for each sample size (i.e. $k$ in pass@$k$). We empirically tested the combinations that appear the most often in the Top 3 and the “code solution” reasoning with “weak solution” instruction performed the best the DMC and TACO datasets.

2. Regarding the prompt to reason and fix test failure:

We did not include a specific prompt to reason about why the test failed as we found that capable models, such as Llama 3.1 series, already exhibit basic ability to analyze the failing public tests and fix them without explicitly prompting to do so. With our CoT-retry, the first turn is the model’s first attempt to a solution then second turn the model adapts the first solution to edge cases to make sure it generalizes, and finally in the third turn we induce diversity by making the model give up on its current attempt and try a naive solution instead.

Q5: Transferability of the Findings to Other LLM Architectures: The paper experiments primarily with the Llama series and GPT-4o models. To what extent do the authors believe that the findings, especially related to prompt configurations and RFT, would transfer to other LLM architectures with different pretraining characteristics? For instance, would models with fewer parameters or more domain-specific training exhibit similar responses to the same prompting strategies?

We experimented with 3 different model series (llama 3.0, llama 3.1 and gpt4o) as well as 6 different architectures to make sure our results would be generalizable. This diversity was chosen to ensure that our findings are robust and not limited to a single model. Based on this experimental breadth, we are confident that the observed patterns in prompt configurations and RFT applicability hold across architectures with similar design principles.

However, we acknowledge that certain characteristics, such as pretraining data distribution, scale, and domain-specificity, can influence a model’s response to prompting strategies. More empirical evidence is needed to investigate the influence of these factors, especially data distribution, on model’s behavior / performance.

To address the reviewer’s specific point, while we believe that our findings are generalizable within the family of large, general-purpose LLMs, the performance of smaller or more specialized models using our proposed strategies warrants further investigation. We plan to explore these dimensions in future work and encourage the community to extend these findings to different model types.

Q6: Given the current results, what specific directions do the authors see as most promising for advancing multi-turn reasoning capabilities? Are there any particular technical approaches, benchmarks, or modifications to current LLM architectures that the authors believe could improve multi-turn performance on reasoning-heavy tasks?

We acknowledge that current LLMs are trained on code infilling loss, therefore they are capable of generating code blocks of coherent code, but training them to reason about code execution and to understand execution feedback remains a challenge. We believe that better understanding of execution feedback is necessary for LLMs to benefit the most from the multi-turn setup. This could be improved by training a specialized code world model.

Also, as the reviewer points out, adaptive prompt selection could be a promising path forward given the encouraging upper pound we give in the previous response.

Although out of scope for this paper, we could see agentic code generation such as SWE-Bench as a more challenging multi-turn setup and an interesting benchmark for evaluating reasoning. In this paper, we focus on an empirical survey to maximize current LLM performance with a fixed budget at inference. We hope the limits we find with LLM reasoning can motivate further work on bridging the gap.

We thank the reviewers for the detailed, encouraging and thought-provoking review and the time dedicated to this. We here address the comments and questions below:

Q1: Diversity in Rejection Sampling Fine-Tuning: The paper fine-tunes the model on correctly generated trajectories. Given the potential for this approach to bias the model towards successful solutions, would the authors consider including near-correct or diverse trajectories to introduce a broader range of reasoning paths? This could enhance the model’s adaptability to different problem-solving strategies.

Including near-correct trajectories for fine-tuning as well as more complex loss functions could be interesting extensions of our work and has been explored with other reasoning tasks. Our efforts for encouraging diverse trajectories include:

• We use a high temperature 1.0 for sampling.
• Amongst the correct trajectories, we conduct finetuning on multi-turn trajectories, in which diverse incorrect solutions in the previous turns are also included.
• We conduct downsampling using LSH-based deduplication to encourage diverse samples being kept, with details in Appendix B.2 (updated version).

We did not include incorrect trajectories in this paper as we focus on understanding inference techniques and view our RFT method as a way to explore the removal of the need for explicit prompting. Simple finetuning on correct trajectories with the LLama 3.1 70B already displayed the key results we wanted: performance boost in contrast with inference-only CoT (Table 1), better self-repair capacities (Figure 8 and 9), and generalization to other benchmarks (Table 4).

A way we think of including near-correct trajectories is to encourage correct reasoning even though final solutions are incorrect. For filtering these trajectories, a Process-Reward Model (PRM) or a “critic” LLM could be used to rate the reasoning correctness of CoT, in order to promote “progress” besides “correctness”. This is an interesting research direction; we added it as a suggestion in section 7 (Limitation) of our paper.

Q2: Adaptive Prompt Selection for Reducing Computational Requirements: The extensive grid search across prompt types and model configurations is resource-intensive. Have the authors explored adaptive or meta-learning techniques to streamline prompt selection, reducing computational demands while still achieving optimal prompt configurations? Such techniques could make the framework more accessible for settings with limited computational resources.

We agree that the extensive grid search, especially at scale presented in this paper, is computationally expensive. However it yields insights regarding a wide range of models in the fields of code generations. These insights should help the community identify promising reasoning and instruction prompts, number of turns to use for multi-turn and feedback granularity in their experiments. We also emphasize the pass n@k metric rather than pass@k to take into account the computational budget with all our experiments. Also, several insights can transfer from one experimental setting to another. For example, the optimal prompt strategy generalizes from one model to another, or from one benchmark to the other:

• In Appendix C.3, we show that the best CoT, i.e. reasoning and instruction prompt combination, found with Llama 3.0 8B on TACO could be directly ported to Llama 3.1 8B and 70B models.
• In Table 4, we show that the best multi-turn CoT found on CodeContests can be directly used on TACO test set. We also evaluated the RFTed model trained on CodeContest training set on TACO test set.

A model to select the best prompt can eventually reduce the computational cost in inference time, while training such a model could be expensive. As the reviewer mentioned, adaptive prompt selection could be done either through black-box optimization, such as bayesian optimization, or through optimizing the prompt directly by gradient, such as the line of work of prompt tuning. We cover this discussion in section 7 (Limitation) of the revision.

However, we provide an upper bound estimation of the performance for the adaptive prompt selection from our grid search. This is done by a post-hoc selection of the CoT per problem by the best performance it induces. We here show the single-turn performance on CodeContests test set under this setting. We do not intend the number presented here to be compared with existing numbers as the test set performance is exposed, and therefore should be treated as an upper bound estimation to show how large the room for improvement.