Reasoning Planning for Language Models

We’re grateful for the reviewer’s positive feedback and appreciate the opportunity to address the remaining concerns:

Moving Section 3 to the Appendix and the experiments about code generation to the main paper

Thanks for your constructive comments on our paper presentation.

• We agree that the code generation experiments deserve more visibility and have made adjustments accordingly. In the revised manuscript, we’ve moved most of the experimental setup details to the Appendix and shortened the description in the main text. Additionally, Table 1 has been resized to half-page width. These changes create space to bring the code generation results into the main paper, placing them alongside Table 1 for easier comparison and improved clarity.

• As for Section 3, it contains the core theoretical results that are exploited for the regularization term used in our loss function (introduced in Section 4). Keeping these results in the main body is crucial for preserving the logical flow of the paper and highlighting our main contributions. To conserve space, we’ve kept only the key results in the main text, with all detailed proofs moved to the Appendix.

The specific configurations for the best-performing approaches (i.e., EPIC-1.0) on MATH500 and LiveCodeBench

Thank you for the question. The configurations of EPIC-1.0 differ between the MATH500 and LiveCodeBench benchmarks, as they are tailored to the unique characteristics of each task.

• For MATH500, EPIC-1.0 is configured with an embedding dimension of 64, a regularization strength of $\tau = 10^{-3}$, and a trade-off parameter $\lambda = 1.0$, which prioritizes accuracy. It uses the Qwen2.5-Math-7B-Instruct model as the base generator and math-shepherd-mistral-7b-prm as the reward model. The method pool includes 81 reasoning strategies covering diverse decoding and aggregation configurations.

• For LiveCodeBench, EPIC-1.0 is configured with an embedding dimension of 64 and no regularization ($\tau = 0$), as aggregation methods are not considered in code-generation tasks. The trade-off parameter is again set to $\lambda = 1.0$, favoring accuracy. The base models are Qwen2.5-Coder-3B-Instruct and Qwen2.5-Coder-7B-Instruct, which share the same set of hyperparameters as mentioned above. The method pool consists of a custom set of 11 decoding strategies designed for code generation, including Chain of Thought - Greedy (CoT-G) and Best-of-N sampling strategies.

Thank you for valuing our contributions. Below, we address the remaining concerns you’ve raised:

The presentation of Table 1

Thanks for your comments on this point. We agree that the table needs better clarification, especially regarding the line separations. Although we provided some explanation in the table caption, we would like to elaborate further here.

• The rows above the blue line show the performance of frontier models on the same test set, along with our upper bound, which is calculated as the proportion of questions that can be solved by any method in our reasoning pool.
• The rows above the green line correspond to individual single-reasoning configurations. Since there are many such configurations, we report only the best accuracy achieved by tuning some parameters. For example, the "Best-of-2" row shows the highest accuracy across different temperature settings and aggregation methods.
• The rows above the brown line include methods that do not support accuracy–cost trade-offs. RA is a simple baseline, while Offline Ada-BoK is a baseline taken from a different paper.
• Finally, the last two groups present the results of our method and its ablated variants under two trade-off settings: $\lambda = 0.25$ and $\lambda = 1.0$.

No limitation section

Thank you for pointing that out. We will include a Limitations section in the revised manuscript.

The question “What are the current failure points that you have observed?”

• We are unsure about the reviewer's question, but we assume it refers to the failure cases discussed in our three theoretical results in Section 3. We want to emphasize that many questions fall into the failure branch predicted by our theories. Failure branch means if we try to generate more answers from the base model for aggregation, the probability of having a correct final answer tends to 0. Recognizing and understanding these cases is key to the better performance of our method compared to other baselines.

• To illustrate this further, we consider the Best-of-N sampling configuration with temperature 0.2 on the MATH500 dataset. We generate $N$ solutions for each question using the model and apply an aggregation method to derive the final answer. This process is repeated 10 times, and the accuracy is tracked. If increasing $N$ (e.g., from 2 to 80) causes the pass rate for a question to decrease, we categorize that question as belonging to the failure branch of the aggregation method. Alternatively, we can predict whether a question lies in the failure branch of an aggregation method by using its bound condition, estimated from 80 samples. The table below reports the percentage of questions that fall into the failure branch (measured empirically), along with the accuracy of our theoretical prediction (in parentheses) for two generators and five aggregation methods considered in our paper:

We draw three key takeaways from this analysis:

• Our theoretical predictions closely match the empirical results, confirming the correctness and reliability of our findings.
• In Table 1 of our main paper, the best configuration, Best-of-16, with PRM_Vote_Min, achieves 86.8% accuracy. The empirical failure branch rate here is 15.8%, and further analysis shows that 92.4% of the failed questions fall into the failure branch. This confirms that most errors of aggregation methods are due to fundamental limitations captured by our theory. Increasing to Best-of-32 with the same aggregation method only slightly improves accuracy (87.0%), while the failure branch rate for the remaining errors grows to 96.8%. This suggests the model is already operating close to its theoretical upper bound.
• The 1.5B model exhibits a higher failure rate than the 7B model, reflecting the superior reasoning ability and stability of the larger model.

Does the approach scale well with the increased number of methods as it increases?

Yes, our approach is specifically designed to scale efficiently as the number of reasoning methods grows.

• In EPIC, each reasoning method is represented as an embedding vector in a shared low-dimensional space. Adding a new method during training simply introduces a small number of additional learnable parameters (e.g., $d = 64$), resulting in linear parameter growth with respect to the number of methods. This design ensures that scalability is maintained without significantly increasing model complexity. At inference time, selecting the best method for a given question involves a similarity search in this embedding space. This search remains fast and efficient even when the method pool is large.

• To empirically test scalability, we conducted an experiment (Appendix D.4.1), expanding the method pool from 81 to 162 by including 81 additional methods generated from a smaller model (Qwen2.5-Math-1.5B), alongside the original techniques from the 7B model. Despite the pool doubling in size, EPIC’s overall accuracy remained nearly unchanged, confirming its ability to maintain performance. More importantly, the larger method pool allowed EPIC to assign simpler questions to the lower-cost 1.5B methods. This significantly reduced overall computational cost without compromising accuracy, demonstrating that EPIC scales effectively in both performance and efficiency as more methods are added.

Is there an over-reliance on a few? If we remove those, how does the performance update compared with other selection approaches?

• We thank the reviewer for the insightful question. Indeed, our method tends to choose some reasoning methods more frequently. However, we argue that this behavior reflects a strength rather than a weakness. The goal of our approach is to leverage the diversity and complementary strengths of reasoning methods to optimize the trade-off between cost and accuracy. When a particular method aligns well with this objective, it is expected to be selected more frequently. For example, Table 1 shows that the cheapest method, CoT-G, achieves an accuracy of 83.2%. If minimizing cost is a priority, it is intuitive for our policy to prioritize this method. Only the remaining harder questions should be routed to more expensive reasoning strategies.

• To further examine the impact of this potential over-reliance, we conducted a control experiment. We first ran EPIC-0.25 on the test set to record how frequently each reasoning method was selected. Then, we removed the top 5%, 10%, and 15% most frequently used methods (corresponding to the top 4, 8, and 12 methods, respectively), and re-ran the selection process. The results are shown below with the baseline results in the main paper, so that you can compare more easily. The notation EPIC-0.25 (-Top k%) refers to the variant where the top k% most frequently used reasoning methods were excluded from the selection pool.

These results show that our approach remains highly competitive even after removing the most frequently selected methods. In fact, the accuracy slightly improves, and the cost increases. This is because, under a trade-off parameter of 0.25, the policy still emphasizes cost more than accuracy. As a result, the most frequently used methods are those with lower cost. When they are removed, some questions are routed to higher-cost methods that offer better accuracy. Despite this shift, EPIC-0.25 continues to outperform all baselines in terms of both cost and accuracy. This result highlights the robustness of our learned selection policy and representation, rather than a mere dependence on a few reasoning methods.

We thank the reviewer for constructive and insightful comments. We address your remaining concerns about our work as follows:

The impact of the number of samples used to estimate bounds for training

Thank you for the opportunity to clarify this point in our paper.

• We conducted an ablation study to address your question by varying the number of samples used to estimate the bounds, selecting from the set of 20, 40, and 80. In this experiment, we fixed the trade-off parameter to 1.0 and the regularization weight to $10^{-3}$, while keeping all other settings consistent with the main experiment. The results are summarized in the table below:

We observe that reducing the number of samples used to estimate the bound slightly decreases EPIC's accuracy, which can be attributed to the increased noise in the estimation when using fewer samples.

• To more deeply examine this effect, we conduct an additional analysis. Specifically, we consider the Best-of-N sampling configuration with temperature 0.2 on the MATH500 dataset. For each question, we generate $N$ solutions using the model and apply an aggregation method to derive the final answer. This process is repeated 10 times, and the accuracy is tracked. If increasing $N$ (e.g., from 2 to 80) causes the pass rate for a question to decrease, we categorize that question as belonging to the failure branch of the aggregation method.

Alternatively, we can predict whether a sample lies in the failure branch of an aggregation method by using its bound condition, estimated from 20, 40, or 80 samples. The table below reports the accuracy of these bound-based predictions across three aggregation methods:

We observe that the bound conditions in Theorems 3.1 and 3.2 for aggregation methods Majority_Vote and PRM_Vote_Min, respectively, achieve high accuracy even with just 20 samples, whereas the bound condition in Theorem 3.3 for PRM_Max_Min requires more samples for accurate estimation. This analysis explains why EPIC maintains strong performance with fewer samples. It benefits from the fact that Majority_Vote and PRM_Vote bounds do not require many samples to yield accurate estimates.

The impact of the regularization weight

We address your concern by reporting the results of a grid search over the regularization weight, selecting from the set $\{10^{-4}, 10^{-3}, 10^{-2}\}$. The results in the table below for EPIC-0.25 and EPIC-1.0 are evaluated on 500 validation questions split from the training set.

The regularization term enforces consistency within a group of reasoning methods that share the same parameters, except for the number of generated answers. In contrast, the contrastive loss encourages a broader separation in routing across all reasoning methods. So the regularization weight regulates the trade-off between capturing local structure (within-group) and global structure (across all methods in the universe). When either component is underweighted, overall performance tends to degrade.

Application of EPIC to other tasks like multi‐modal, retrieval‐augmented generation, open‐ended QA, or real‐world dialog

EPIC can be extended to these tasks with suitable modifications. For multi-modal inputs, we can replace the question encoder with a multi-modal embedding model to process cross-modal information. In retrieval-augmented generation, EPIC applies naturally by treating different retrieval and synthesis configurations as reasoning methods. For open-ended QA and real-world dialog, EPIC can reduce computational cost by routing questions to different models or decoding strategies based on utility, while preserving output quality. Appendix D.4.1 includes an experiment demonstrating EPIC’s effectiveness in selecting reasoning methods associated with different generation models. In addition, EPIC can incorporate surrogate utility signals such as toxicity or truthfulness scores by treating them as PRM scores. This allows EPIC to encourage safer and more reliable outputs.

Computation resources for the training process. Are there ways to amortize the cost (e.g caching scores)?

Our training process consists of two stages: data generation and model training.

• In the data generation phase, we run 81 reasoning methods over 7,500 training questions, generating and scoring 80 answers per question. This step takes approximately 410 GPU hours on an A5000 and requires around 28GB of VRAM to load both the 7B generation model and the 7B score model. This procedure is expensive but essential to know the capabilities of reasoning methods.
• Once the data is generated, the training phase is lightweight. We train a small transformer-based model with only 22.6 million parameters, requiring just 80MB of VRAM and completing in under 0.3 GPU hours on the same hardware.

We are considering two approaches to reduce the cost of the data generation step:

• Score caching as you suggested: Since some generation patterns repeat across multiple samples, caching their PRM scores can reduce redundant computations. However, due to the inherent randomness of sampling, the cache hit rate might be relatively low.
• Fewer samples for bound estimation: As discussed in our response to the question about sample efficiency, some of the probability bounds used for regularization can be accurately estimated with fewer samples. By selectively using fewer samples for these bounds during training, we can reduce the generation cost without significantly affecting performance.

We appreciate the reviewer’s comments on the strengths of our work. However, we would like to raise two concerns:

1. Citation to a Work Posted After Submission

The reviewer requests comparison with Route to Reason (RTR) [arXiv:2505.19435], which was posted on 26 May 2025, after the NeurIPS submission deadline of 15 May 2025. As such, this work was not accessible to us at the time of submission and should not be used as a basis for criticism, following NeurIPS reviewer guidelines.

2. Possible Fabricated Citation

The reviewer cites the following paper:

Olivier Germain, Amaury Habrard, and Édouard Marchand. “PAC-Bayesian C-bounds for Majority Vote.” In Proceedings of ICML, 2009.

We have thoroughly searched online repositories and Google Scholar, but could not locate any publication matching this citation. We postulate that this may be a fabricated or misattributed reference, possibly conflating the following two real works:

• Pascal Germain et al., PAC-Bayesian Learning of Linear Classifiers, ICML 2009.
• Pascal Germain et al., Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm, JMLR 2016.

We respectfully request that these issues be considered in the review evaluation.

Regardless, we would like to address the reviewer’s concerns below:

Weakness 1: There is no comparison with various strategy selection techniques such as MRP, RTR, or TATA frameworks. Insufficient discussion of how EPIC differs from existing routing approaches.

Meta-Reasoning Prompting (MRP) [1] relies on GPT-4 to select from 7 prompting strategies. At test time, MRP performs an additional call to GPT-4 using a meta-reasoning-prompt that describes the available prompting techniques and determines which one to apply. A key limitation of MRP is its reliance on an advanced and proprietary model (e.g., GPT-4), whereas our EPIC operates without such constraints.

Teaching LLMs According to Their Aptitude (TATA) [2] adopts a more complicated three-stage framework: (1) data preparation: For each question in the dataset, TATA generates both a Chain-of-Thought (CoT) and a ToRA [3] response. (2) data selection: TATA selects either the CoT or ToRA response for each question by evaluating its effectiveness. To do so, TATA inserts the question-response pair as a one-shot example and measures LLM performance on a validation set of 100 questions. (3) Instruction Finetuning: TATA then finetunes LLM on this selected dataset, aiming to internalize the decision of when to apply CoT or ToRA reasoning. Despite this complexity, TATA only supports two reasoning methods and appears to be more challenging to scale up the number of reasoning methods due to the complicated framework. Meanwhile, EPIC provides much wider coverage of up to 81 methods and is easily extensible without modifying any cost function.

We empirically compare EPIC with MRP and TATA on MATH500 as follows:

EPIC vs MRP

EPIC vs TATA:

We conducted best-effort reproductions of both MRP and TATA baselines despite limited access to their full implementations (MRP lacks released code and provides only partial prompts, while TATA publishes part of the code only for its second stage). For MRP, we use GPT-4o-mini as the backbone model for both prompt selection and answer generation. To ensure a fair comparison between TATA and EPIC, we use the same generation model (i.e., QwenMath2.5-1.5B-Instruct) for both methods. EPIC outperforms both MRP and TATA by a wide margin, achieving up to 13.6% absolute improvement over the best baseline.

Baseline reproducibility notes: Our reproduction of MRP aligns with the original paper, which reports only marginal improvements of 0.05% gain in macro average (Table 1). When evaluated with GPT-3.5 (Table 2), MRP even underperforms the basic CoT baseline. This shows that MRP is fragile and lacks robustness.

For TATA, we instruction-finetuned (using the code in [5]) two models (QwenMath2.5 - 1.5B and QwenMath2.5 - 1.5B-Instruct) on their partially published dataset [2], observing an increase in performance in the Base model but not the Instruct model.

the aggregation bound is a known results from probability theory

Regarding the work “Olivier Germain, Amaury Habrard, and Édouard Marchand. “PAC-Bayesian C-bounds for Majority Vote.” In Proceedings of ICML, 2009.“, the issue with this citation is mentioned above. As for the [4], we do indeed cite one of their result from Theorem 5.10 in our Lemma A.2. This is used to establish a Poisson approximation that supports a small part of our broader theoretical development. However, the main aggregation theorems in our work, Theorems 3.1 to 3.3, go significantly beyond these results. Deriving these bounds required non-trivial extensions, including carefully analyzing majority vote, PRM sum, and PRM max aggregation under Gaussian assumptions with detailed probabilistic and optimization-based arguments. We hope this clarifies our theoretical novelty and the specific role of previously known results in our overall derivation.

References:

[1] Gao, Peizhong, et al. "Meta reasoning for large language models." arXiv preprint arXiv:2406.11698 (2024).

[2] Xu, Xin, et al. "Teaching llms according to their aptitude: Adaptive reasoning for mathematical problem solving." arXiv preprint arXiv:2502.12022 (2025).

[3] Gou, Zhibin, et al. "Tora: A tool-integrated reasoning agent for mathematical problem solving." arXiv preprint arXiv:2309.17452 (2023).

[4] Michael Mitzenmacher and Eli Upfal. “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis.” Cambridge University Press, 2017

[5] Tong, Yuxuan, et al. "Dart-math: Difficulty-aware rejection tuning for mathematical problem-solving." Advances in Neural Information Processing Systems 37 (2024): 7821-7846.