Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation

Thank you for your review. We address your concerns point by point:

Metrics

Unlike methods that report Pass@k which attempts k solutions on testset (e.g. LDB and Self-Repair use ground-truth test cases which can be considered contamination), our Pass@1 measures attempting only 1 solution on testset. We only generate and execute multiple codes during reasoning on self-generated test cases. The final code (one per problem) is evaluated on the actual test set (unless marked "w/ T"). In fact, although baselines like LDB report Pass@k where k solutions are tested against testset cases, they sample much more code and debug on test cases from testset to obtain each solution. Thus it's still a fair comparison if we control the attempts on the full testset cases for all methods. Furthermore, we report metrics beyond Pass@1 as shown in Table 5.

PRM Training

We report training details in Appendix A.4. While we used 81 problems for PRM training to avoid contamination, we collected a larger dataset by beam search with 20 reasoning steps each. This generated 5414 steps with GPT-4o labels for training. To further address your concern on label quality, we trained 2 new line-level PRMs:

1. PRM-GPT: A larger GPT-4o labeled dataset (13644 steps).
2. PRM-Human: To obtain better reward labels, we sampled 400 reasoning chains with GPT labels and ask 3 authors to spend 12hrs each, to classify if the chains and rewards are valid. We got an average inter-annotator agreement of 0.44(Cohen's Kappa,AB=0.27,AC=0.61,BC=0.44). We kept 209 valid chains from 261 chains that annotators agree on each other and extracted 836steps for PRM training.

Cost

We add controlled experiments on LBPP with Qwen7B limiting LLM calls(Details in Rebuttal DEgP) with 2 new PRMs and REx[4].

Results show repair-based methods (LDB, Reflexion) fail to scale effectively. LDB focuses on fixing code blocks in a single solution, which works for simple bugs but fails when the algorithmic approach is suboptimal, while ORPS improves significantly. REx may appear advantaged as it generates code every call while others generate code every 2 calls, attempting twice as many solutions given the same calls. Given the same compute budget, ORPS consistently generates better solutions without training or test cases from testset.

Novelty and Contributions

ORPS fundamentally challenges the assumption in process supervision(OmegaPRM,MathShepherd) that specially trained PRMs are necessary for reasoning guidance. Compared to trained PRMs, although increasing training data quality(which is expensive) could lead to improvements, combining verifiable rewards with existing LLMs without training outperforms trained PRMs as compute increases. This is significant conceptual advancement for process supervision that eliminates the overhead of PRM training while improving results.

Unlike Self-Repair, REx, LDB that focus on repairing code or specific blocks, ORPS reasons about solution strategies at a higher level to avoid local optima. Instead of incrementally fixing specific solutions to pass more tests, ORPS explores different algorithms with extensive reasoning, even on solutions that pass all generated cases for improvement.

Compared to REx which focus on selecting best nodes to explore by solving arm-acquiring bandit problem from exec outcomes, we propose LLMs are capable of directly generating high quality process rewards given some feedback to select and expand certain reasoning chains. In fact REx might be used in conjunction with ORPS process rewards since REx focus on selecting better nodes while we try to produce better rewards but is out of the scope of this work.

Besides, previous methods require testset cases, which is practically hard to obtain(as pointed out by DEgP and LiveCodeBench), while ORPS relies on self-generated cases(for unit-test generation, please refer to Rebuttal DEgP).

For notation issues, we will fix them in revised version. We will also cite, discuss and compare with works you listed that we missed previously,like REx and Self-Repair.

Given these clarifications and new results demonstrating ORPS's superior performance, we respectfully and strongly request reconsideration of your score.

Thank you for your positive review and recognition of our work's effectiveness. We appreciate your thoughtful questions and address them below.

Q1: Does the proposed approach composed of components which already exists in the literature? If yes, how do the authors see the novelty of the work?

Regarding novelty, while we integrate some established concepts, we introduce several key innovations rather than merely combining existing components:

1. Prior process supervision approaches (OmegaPRM, Math-Shepherd, etc.) assume specially trained Process Reward Models are required for effective reasoning guidance. ORPS challenges this assumption and studies necessity of training PRMs, by combining execution feedback as verifiable rewards with existing LLMs to guide reasoning. Results show that ORPS, as a pure inference-time method, produces better reasoning guidance than trained PRMs.
2. Unlike repair-based approaches (e.g., Self-Repair, LDB) that incrementally fix specific code blocks, ORPS reasons at a higher abstraction level about solution strategies. This enables exploring different algorithms rather than being trapped in local optima when the initial approach is suboptimal. Moreover, unlike previous works, we also aim to generate code solutions that are correct, efficient, easy to understand and maintain, instead of focusing solely on correctness.
3. ORPS effectively operates without access to ground truth test cases from benchmark testsets. ORPS utilizes self-generated unit tests during reasoning - a practical advantage in real-world scenarios where test cases are unavailable.

Q2: I am a bit confused but wanted to confirm, during inference, does the proposed approach iterative generation? I mean does it generate and then refine the generation?

Yes, ORPS is an iterative generation approach. It maintains multiple solution trajectories simultaneously through beam search, where each iteration involves reasoning, code generation, execution, and self-critique. This iterative process allows for strategic pivots when initial approaches prove suboptimal.

Q3: If I understand correct, the proposed method does not require any training, right? It is an inference-only approach?

Correct, ORPS requires no training whatsoever. It's a fully inference-time framework that leverages an LLM's existing capabilities for reasoning, code generation, and self-critique. Our experiments in Table 4 and additional analyses (in our response to Reviewer 4j6r) confirm that this inference-only approach outperforms methods requiring PRM training, especially as compute budget increases.

Thank you again for your supportive review. We believe ORPS represents a significant step forward in unifying process and outcome supervision for complex code generation tasks.

Thank you sincerely for your thoughtful review and constructive feedback. We deeply appreciate your recognition of our work and we address your questions and concerns point by point:

Q1: What initial LLM inputs (system prompts) used in each call to the LLM, if any. If system prompts exist, is it possible to include them in the appendix.

We sincerely appreciate your emphasis on reproducibility. Reproducibility is our first priority and thus we have anonymously open-sourced all implementation details, including code, prompts, setup instructions, commands to run and reproduce our experiments in our anonymous repository. The repository contains all prompts used in ORPS. We attach our prompts at the end of this response. However, due to space constraints of rebuttal, we cannot paste everything here, but we will make sure to include all prompts in our revised appendix. For the new experiments and data involved in rebuttal, we will also add them to our repository.

Q2: What's the current SOTA for LBPP? Is it ORPS?

To the best of our knowledge, ORPS currently achieves SOTA performance on the LBPP benchmark. Moreover, this improvement requires no additional model training and can be applied to any sufficiently capable base LLM. As demonstrated in our experiments, ORPS consistently outperforms other baselines across multiple models given the same compute budget.

W2: The paper can be somewhat handwavy with terminology and some claims. A description or definition of concepts and terms before their usage would be preferable. Examples include "reasoning", "reasoning space", "finer reasoning", "intrinsic reasoning", and so on.

Thank you for pointing out our presentation issues. We acknowledge the need for clearer definitions and will revise the paper to explicitly clarify key terms and provide more explanation to our notations. We will ensure all technical terms are clearly defined before their first use.

We are very grateful for your expertise and time in evaluating our work. Thank you again for your contributions to improving this work.

The system prompt of model for reasoning and generating codes:

You are a Python programmer in a code interview. You're solving a coding problem while sharing your thoughts and discussing with an critic. Always follow the format below for each round:
1. First, share your thoughts as comments:
   - Your current approach (or an analysis of the problem and your plan if you haven't written any code yet)
   - What you learned from previous feedback (if there is any previous feedback, otherwise think about your plan, what might be missing from your previous plan)
   - Why you chose this approach (or how you plan to tackle the problem), do you need to shift your approach?
   - Be clear, concise, detailed and pay attention to the comments given by the critic, no chit-chat, no small talk.
   - Always use first person, e.g. I, we, our, etc.
2. Then write your solution:
   - Clean, efficient Python code that follows requirements exactly
   - No test cases in code, just the solution
   - Your code will then be tested by the critic, so do not include any test cases in your code, this is very important
Format your response as:
# === BEGIN PROGRAMMER THOUGHTS ===
# [Your response to previous feedback]
# === END PROGRAMMER THOUGHTS ===
# === BEGIN SOLUTION ===
```python
[Your code]
```
# === END SOLUTION ===
Output strictly as shown above.

The system prompt for the self-critic role:

You are a technical critic reviewing a programmer's Python code. Provide clear, constructive feedback and suggest improvements or propose a new approach. The programmer's thoughts, code, execution analysis will be provided to you each round and you need to give constructive feedback to the programmer.
Here are some rules you need to follow:
1. First, share your thoughts:
   - How did the code perform in the execution, did any test cases fail?
        - If any case failed, why it failed? If all passed, think about performance improvement.
   - Key observations on the code, e.g. what's good or bad, what's the most important thing to improve, etc.
        - Potential improvements: time / space complexity, a different algorithm, strategy, etc.
   - Think about the programmer's thoughts, propose a new direction if you have any better idea, or give some advice to the plan, or give additional analysis of the problem
   - Your thought process should be clear and concise, no chit-chat, no small talk. Guiding the programmer to improve their code is your main goal, you do not write any code.
  - Always use first person, e.g. I, we, our, etc.

...
<omitted due to character limitation of rebuttal, please refer to our open-source repository for details>

Thank you for your valuable feedback.

Answers to Questions

Q1: Currently, there's an assumption in process supervision and test-time scaling research (e.g. OmegaPRM, Math-Shepherd, Let's Verify Step by Step, Deepseek-Math, etc.) that a specially trained Process Reward Model is required to guide reasoning (during training with RL or inference with search algorithms like MCTS). ORPS fundamentally challenges this assumption and study necessity of training PRMs, by combining execution feedback as verifiable rewards with existing LLMs to generate high quality process rewards to guide reasoning. We compare ORPS with trained PRMs by using different methods to guide LLM reasoning during inference (Table 4) and we now add 2 new experiments (in rebuttal for 4j6r) to extensively validate our claims. Results indicates ORPS produce better rewards than trained PRMs to guide reasoning and consistently performs better given the same compute budget.

Regarding S*[1], this work was made public one month after the ICML submission deadline which further validates our approach.

Q2: We agree that the certain phrasing suggest a focus on efficiency over correctness. To clarify: our framework prioritizes optimizing correctness as the primary objective, while considering comprehensive metrics involving efficiency, code quality, complexity, etc. In all our experiments we report correctness metrics along with efficiency for comprehensive comparison. Our motive here is that a good solution should be correct, efficient (evaluated with dynamic analysis), easy to read and maintain (static analysis). Furthermore, we study how dynamic and static analysis metrics affects overall performance(Figure 6 in Appendix D) and this should also address Weakness 2.

Unit Test Cases

Thank you for raising the concern on the scarcity of ground truth test cases in practical scenarios. We agree quality of test cases might significantly affect the performance of all approaches that utilize execution feedback to debug or improve the code. Our baseline Reflexion points out "they rely upon ground truth test cases that invalidate pass@1." However, we have explicitly addressed this concern, and the test cases used in ORPS are not the ground truth from test sets. Instead, we follow Reflexion to prompt the LLM given the problem and example tests and filter invalid cases. These self-generated, weak tests are then used during reasoning, and only one final solution will be tested against the actual ground truth cases. To ensure fairness and reproducibility, we cached the cases generated by Qwen 7B and used the same cases in all our experiments. While the quality of generated cases are suboptimal compared to ground truths, ORPS performs better, even compared to the baselines using ground truth cases. Notably, we also evaluate ORPS with ground truth test cases (ORPS (w/T) in Table 1) in comparison. We will be including all system prompts in revised Appendix.

Computational Cost

The bottleneck of computational cost of ORPS and baselines is LLM Inference Calls instead of dynamic and static analysis, as this require GPU computing and introduce the majority of latency. Although we compared ORPS with BoN in Figure 4 by allocating the same number of samples per problem, we now include a new experiment for other baselines given the same number of LLM calls.

To be precise, we analyze the worst case cost for each method: ORPS requires $2\times N \times (K \times T + 1)$ Calls, where N = Candidate Samples, K = Beam Size, T = Reasoning Steps. Reflexion requires $2\times T$ calls, where T = Steps. LDB requires $1 + P×T×(2+B×N)$ where P = pass_at_k, T = max_iterations, B = number of blocks in code control flow graph, N = max_trials. For trained PRMs, we swap the self-critic LLM call with the PRM and thus the calls are identical. Please refer to rebuttal for 4j6r for PRM training details.

Results indicate that even we use weaker, self-generated test cases, ORPS consistently outperform baselines that use ground truth test cases given the same compute budget and scales up consistently.

We sincerely appreciate your time and constructive feedback, which has helped us strengthen our work. Given these these clarifications and new results, we respectfully request reconsideration of your score.