DISC: Dynamic Decomposition Improves LLM Inference Scaling
Authors: Jonathan Light
Wei Cheng
Benjamin Riviere
Yue Wu
Masafumi Oyamada
Mengdi Wang
Yisong Yue
Santiago Paternain
Haifeng Chen
Venue: NeurIPS 2025 poster ()
Keywords: Inference scaling
search
decomposition
LLM
Primary area: deep_learning
TL;DR: We propose DISC, a dynamic decomposition method that adaptively adjusts step sizes during LLM inference to allocate compute more efficiently, significantly improving performance and sample efficiency across reasoning and code generation benchmarks.

Abstract: Inference scaling methods for LLMs often rely on decomposing problems into steps (or groups of tokens), followed by sampling and selecting the best next steps. However, these steps and their sizes are often predetermined or manually designed based on domain knowledge. We propose dynamic decomposition, a method that adaptively and automatically partitions solution and reasoning traces into manageable steps during inference. By more effectively allocating compute -- particularly through subdividing challenging steps and prioritizing their sampling -- dynamic decomposition significantly improves inference efficiency. Experiments on benchmarks such as APPS, MATH, and LiveCodeBench demonstrate that dynamic decomposition outperforms static approaches, including token-level, sentence-level, and single-step decompositions, reducing the pass@10 error rate by 5.0%, 6.7%, and 10.5% respectively. These findings highlight the potential of dynamic decomposition to improve a wide range of inference scaling techniques.

DISC: Dynamic Decomposition Improves LLM Inference Scaling
Jonathan Light Wei Cheng Benjamin Riviere', Yue Wu Masafumi Oyamada',
Mengdi Wang", Yisong Yue Santiago Paternain Haifeng Chen Rensselaer Polytechnic Institute, NECC Laboratories America, *Princeton University, California Institute of Technology, NNEC Corporation
disc-search. github. io
Abstract
Inference scaling methods for LLMs often rely on decomposing problems into steps (or groups tokens), followed by sampling and selecting the best next steps. However, these steps and their sizes are often predetermined manually designed based on domain knowledge. We propose dynamic decomposition, a method that adaptively and automatically partitions solution and reasoning traces into manageable steps during inference. By more effectively allocating com- pute particularly through subdividing challenging steps and prioritizing their sampling dynamic decomposition significantly improves inference efficiency. Ex- periments on benchmarks such as APPS, MATH, and LiveCodeBench demonstrate that dynamic decomposition outperforms static approaches, including token-level, sentence-level, and single-step decompositions, reducing the pass by 5.0%, 6.7%, and 10.5% respectively. These findings highlight the potential dynamic decomposition to improve a wide range of inference scaling techniques.
@ 10 error rate
Introduction
Scaling inference efficiency remains fundamental challenge for large language models (LLMs). Many existing approaches improve inference by decomposing problems into smaller steps and systematically exploring different solutions [1 2 5 g 10] Some decomposition
methods often rely on domain-specific heuristics and hand-crafted rules [II 12 [3]. However, manually partitioning problems or designing task-specific heuristics is costly and lacks generalization. Moreover, identifying critical steps for an LLM can be non-trivial for humans. LLMs may assign importance seemingly trivial words (e.g., therefore or which), which, while counterintuitive to humans. play crucial role in autoregressive generation [14). Other approaches employ fixed, uniform step sizes, such as token- or sentence-level decomposition [ 15). All these methods rely on static decompasition strategies, where step sizes are predefined or determined via heuristics. Such rigidity risks overusing compute on steps that are easy for the L.LM (but potentially difficult for humans) while undersampling more challenging steps.
To overcome these limitations, we propose DISC (Dynamic decomposition Improves Scaling Compute), a recursive inference algorithm that dynamically partitions solution steps based on diffi- culty. Unlike prior methods, DISC adapts decomposition granularity during inference based on both the available budget and problem complexity, ensuring finer granularity for more difficult steps. By leveraging the autoregressive nature of LLMs, DISC efficiently locates difficult steps through dynamically proposing step sizes, focusing compute on challenging regions rather than wasting
Work done during the part-time internship at NEC Laboratories America. *Corresponding author. *This work was partially supported by IBM through the IBn-sllseleerr Future of Computing Research Collaboration.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Prompt: How far does train with speed 60 mpg travel in 3.5 hours?
Single step generation
Enfire generation is a single step
The train travels 60 mph. \n 3.5 hours, the distance trovels is:yn 60miles/hour>3 Shours- 2mmile.
yb
Token level decomposition
Each token is a step
The train Travels 60 mph. \n 3.5 hours, the distance travels Vs 60milas/hourx3 Shours-210milan
yo y1 y2
y19 y20 y21
Sentence level decomposition
Period or newline characler marks end of slep
The train travels 60 mph. \n 3.5 hours, the distance travels is 60miles/hour>3 Shours 2imilsss.
yo Dynamic decomposition
y2
Dynamically adjusted steps and step sizes
The frain trovels at 60 mph. In 3.5 hours, the distance travels in 60milas/hourx3 Shours 210miles..
yo
y2
Figure 1: Comparison of automatic decomposition strategies based on step size. Coarser steps accelerate the search process but risk skipping over optimal solutions and committing to suboptimal prefixes. In contrast, finer steps ensure more precise decisions but lead to slower search. A dynamic strategy that adapts step size based on LLM feedback offers balanced approach, combining the efficiency of coarse steps with the precision of fine-grained decomposition.
resources on trivial steps. DISC is generalizable, requires no human supervision, domain-specific heuristics, prompt engineering, or process annotations, and is easily parallelizable, making it widely applicable across tasks. Furthermore, DISC is plug-and aad--ndd-lly play with off-the-shelf search algorithms and can be naturally integrated with greedy, beam, Monte Carlo Tree Search.
Our main contributions are:
We introduce DISC, method for dynamically adjusting step sizes and decomposing solutions during inference without human supervision, domain-speciff heuristics, or process reward models.
We demonstrate how DISC integrates decomposition directly into inference-time search, allocating compute more effectively toward high-potential solution prefixes.
We show that DISC improves inference scaling in terms of both sample efficiency, token efficiency, and runtime, achieving up to (0% reduction in error relative to the baselines and up to 4x increase in accuracy over the base model, with just 10 samples, including with reasoning models.
We provide both empirical and theoretical insights into LLM reasoning, including identifying critical intermediate steps and analysis how DISC helps discover optimal solutions.
2 Preliminaries
2.1 Problem Setting
We consider a reasoming and code generation setting where we are given: a dataset X' = (x) a pretrained, autoregressive LLM ı that generates solutions y E D, and a reward model R X y + [0, 1] that evaluates the generated solutions. The goal is to find inputs to the LLM that produce solutions with high reward. This setting includes program synthesis, where correctness verified using ground-truth tests [6 [17, and mathematical reasoning, where solutions are validated numerically [18 19 The reward model can be a ground-truun -truth verifier, a trained heuristic [20), self-consistency (21). an a--aaas--juude [22) and because focus is decomposition rather than verification, we use the ground- -ruth reward model where available.
Ji=1:
We use the following hierarchical token notation: y is token, is a prefix that starts at the prompt and concatenates multiple steps, s suffix that concatenates multiple steps and ends with the EOS token, and is a complete solution that starts at the prompt, concatenates multiple steps. and ends at the end of sequence token EOS. We denote concatenation of two tokens or token sequences with ; e.g. p 8 is the concatenation of prefix p and suffix to form a complete solution y. We denote the sampled suffix from prefix p using the LLM policy as: T(-Ip). We denote an optimal solution with y and optimal suffix as s* where there exist multiple optimal solutions. For analysis,

---

we use the convention that ( (p) = 0 if there does not exist completion s* such that s" is
optimal. The size of a string ly), refers its length in tokens or characters.
2.2 Existing Decomposition Methods
Single-step generation. In single-step generation, the entire solution is generated in one pass from the prompt to the EOS token, treating it as a single action. This approach underlies the widely used inference scaling method best of n (BoN) [19 23 5 224,, where n complete solutions are sampled.
and the highest-scoring one is selected. Single-step generation also plays role in alignment and fine-tuning methods such as DPO 25 and RLOO [6]]
Token-level decomposition. At the opposite end of the spectrum, token-level decomposition treats each atomic token individual step. While this approach dramatically increases search complexity, it enables -rninnr search that can yield higher performance gains given sufficient compute [.
Newline and sentence-level decomposition. A commonly used decomposition method segments LLM generations into sentences or lines based on delimiters such as periods or newlines [ Typically, each newline corresponds to paragraph, equation, or line of code, which often encapsulates a distinct reasoning step.
Challenge: Automatic and scalable decomposition
Existing decomposition methods are static and manually designed, resulting in either slow convergence to good performance or fast convergence to poor performance. We propose adaptive decomposition for fast convergence good performance.
2.3 Search for Inference Scaling
We differentiate between decomposition and search, where decomposition controls the number of steps between new branches and search is the process of selecting which branch to explore. In other words, decomposition is the construction of nodes and edges, and search is process that occurs on that structure. In this work, we propose decomposition method that is plug-and-play with different search methods. In our experimental results in Sec. 4.1] we compare decomposition methods: token- level decomposition, sentence-level decomposition, and DISC with the search methods: greedy. beam (28), and Monte Carlo Tree Search [ 29 Implementation details are provided in App.
3 Methodology
The DISC algorithm uses LLM rollout data dynami- cally decompose reasoning steps, adjust step sizes, and allocate sampling compute. In Sec. 3.2 we present DISC paired with greedy search strategy, shown Alg. and Fig. 3 In Sec. S.4. present the general case of DISC as a nodal expansion operator which is used for pairing with beam search and MCTS.
base profix
advanae
candidate prefix step
cottrod
3.1 High-level Overview
At high level, DISC with Greedy Search advances base prefix pd forward by iteratively concatenating promis- ing steps to it. The core intuition is to dynamically allo- cate compute by adjusting the step size: a prefix shows promising reward improvement, we take large step for- ward; if not, we contract the step and concentrate sampling around that prefix. This adaptive behavior focuses the LLM's effort on regions the search space that are more likely yield high-reward completions.
Low probabiliy
High probability
Sampling
Figure Multiple iterations of Alg. [ DISC dynamically refines its step sizes across iterations, advancing and contracting the prefix at which samples from.
Fig illustrates single iteration this decision process, where candidate prefix either accepted and extended or rejected and contracted. Over multiple iterations, this process yields full solution

---

Sompling prefix
Iterate: Candidate prefix becomes base prefix and reset fractoon
New bose
New condidate
Base
Candidate
Pb
accept
commà
Compare the scores prefixes and P. based rollouts
Og
Points prefixes
sdudion
New base
New condidate
Reward
reject
refine
contro
1,0
VS.
0.8
prefix
Condidate profix
"greedy-DiS DISC always revises candidate staps solution
Iterate: Keep base prefix and fighten fraction
Figure 3: DISC with Greedy Search. One iteration of Alg. We start with base prefix A and candidate prefix We compare the sample statistics of each by evaluating a scoring function (e.g.. z-score). If the candidate prefix B demonstrates higher likelihood of reward improvement compared to continuing from base prefix A, we accept B, commit it as the new base, and extend the candidate to further step (e.g., BD) the best sampled solution. If B is not better, reject it and propose shorter candidate (c.g., AC), contracting the step size. This process repeats until a new candidate is accepted or all options exhausted. The algorithm thus adaptively advances contracts the step size and search horizon based on the relative quality of completions from each prefix.
composed several such accepted steps. Fig shows how the prefix is incrementally constructed: displays the number of steps DISC has committed to the prefix, and how the prefix used for sampling dynamically changes over time. Together, these figures highlight the local step-wise decision decision-making making and the global trajectory of prefix refinement throughout the search.
Assumptions. DISC makes minimal, broadly applicable assumptions, enabling generality and ease of deployment. avoids handcrafted prompts, process-level reward models, and domain-specific heuristics. Its only requirement access a scalar outcome reward model (ORM) to guide search. In the absence of a ground-truth ORM, self-supervised signals-like LLM critiques or unit tests-serve serve effective substitutes (30 31 32 also assumes the underlying policy can generate continuations
from any prefix standard feature of decoder-only language models.
3.2 DISC with Greedy Search Algorithm
We now describe Alg. The algorithm takes input LLM n, a reward model R. prompt æ, initial partition frac- tion ag, threshold a, and sample budget N. It initializes the base prefix as Р, = x and sets a ag-
Max
Samplas
Area Dc Zacore
At each iteration, the algorithm samples from Ps to gen- erate completions y² = Pp 8², computing rewards R(y"). Sampling stops when the cumulatíve reward exceeds a: M min (m E Z>o E R(y') 2 a). This balances sample quantity and quality. The solutions and their wards are stored in Y, and the best suffix 8* and z-score computed.
Reward distribution for prefixl
Meon
Samples
Area Zecore
Reward distribution prefix
candidate prefix P, is then formed by appending the first fraction (token-wise) of s* to Ps- It is accepted if its reward z-score 2, is lower than current 2s, Assuming rewards follow location-scale family distribution (e.g., Gaussian), a lower 7-score implies higher probability of improvement, since Pr(R > max (R(s))
Figure 4: Reward distribution of rollouts sampled from two different prefixes. The probability sampling a higher rollout from prefix is higher than that of prefix 1.

---

(2.() where CDF is the cumulative distribution function. Fig. 4 displays how we can estimate the probability of improvement from reward distribution. A location-scale distribution of rewards is supported empirically (see App. C.5
If the candidate is accepted, the algorithm updates the hase prefix Ps <- Pe. resets Okg, and updates the base z-score and best suffix. If rejected, the partition fraction contracts: f a -kg- This contraction implements DISC's recursive refinement mechanism, focusing the search on more promising regions. The process repeats until the sample budget is exhausted or a correct solution is found.
3.3 Analysis of DISC with Greedy Search
Algorithm DISC with Greedy Search
DISC exhibits two important properties: (i) the z-score decreases monotonically over the course of algorithm iterations, and (ii) the best candi- date solution always has higher reward than the best base solution. We leverage these proper- ties, together with assumptions about the quality of π. to establish the following result. We also develop motivating theoretical example in App.
Require: LLM т, Reward model R, prompt z,
initial partition fraction og, negative binomial threshold a, sample budget N
// initialize base prefix and current partition fraction
1: Ps σ, a ap
// compute base prefix statisties (_b)
2: So (Ps s² s T( ((-1pp)) 1=
3: 2b maxess, (I((a) meun.e e. (M((a))
sdges, S, (R([=)
4: Ps 8 = argmax ses, R((8)
Theorem (Optimality of DISC) Consider
5: while n N do
Alg. 7 Suppose that for some problem æ, the optimal solution is in the support of nt. x)) Then at some n. > 0, the base prefix contains EOS token, the algorithm terminates, and this solution is an optimal solution. See App. Gfor proof.
// get candidate prefix (_c)
6:
P. = Ps split(sf,.0) a)
// sample and compute candidate prefix
statisties (_c)
7:
S. {P. 8² st~ x(
Ze maxors, (R(a)) mean (Ria)
8:
sto (R(a))
Remark Our analysis is dependent on strong policy assumption, which is "reverse en- gineered" be the weakest assumption on the policy such that our algorithm terminates at optimality. In other words, this assumption de- pends on an instance-dependee must be checked empirically. The purpose of our analysis is not to provide universal guarantee,
9:
P. s argmax, EES. R(s)
n + M
// accept reject the candidate prefix
11:
if 2. 2b or |s]] S then
12:
Ps Per 8 8
property that
13:
a ag, 2h t Ze
14:
else
15:
a + aga
but rather to understand how adaptive decom-
16: end if
position method can control real-time inference compute without sacrificing optimality.
17:
end while
18: yield Ps $6
3.4 DISC for Plug-and-Play with Search Algorithms
In the previous section, presented DISC with greedy search complete algorithm. However, the core of DISC is the decomposition that controls from which token prefixes to query the model and dynamically adjusts step sizes, which can be plug-and-play Beam search and MCTS. The DISC EXPANDNODE and MAKECHILDREN are presented in Alg. 3 These methods are conceptually similar to the DISC with greedy search, except that in the general search context, each node stores its own base prefix, and so when a node is expanded it computes its candidate prefix from the suffix that node instead of from the best existing suffix. During the expansion operator, multiple sets of children are generated, but only the children from the final prefix kept for search.
with other search algorithms like
3.5 Example Decomposition
Using a sampling budget of N = 100 I.IM calls, the decomposition of a representative MATH problem is shown below. Each step is enclosed in brackets and color-coded based the z-score of
5

---

sampling a better suffix conditioned on the current prefix. Brighter colors indicate lower z-scores, signaling higher importance.
DISC example decomposition
[ [et the length of the rectangle be / and the width of the rectangle be w. Since the
perimeter of the rectangle is 24 inches, have that 2/ + 2w 24, 1++ w 12. We wish to maximize the area of the rectangle, which is A = lw. Let I = 12 and plug into the area:
= (12 w)w
A = 12w w²
Now, we differentiate A with respect to w:
A'(w) = 12 2w
We wish maximize A, we set A')w) and solve for
12 2w 0
6
Since = 12 w. we have that | = 12 = 6. Therefore, the area of the rectangle is
A Iw 6 6 36
DISC identifies the first step as highly important, which aligns with intuition-eaal reasoning forms the foundation for all subsequent steps. In contrast, the final step, although large, is marked as low- importance, indicating that DISC allocated minimal compute toward refining it. This suggests that once earlier reasoning is fixed, there is limited opportunity for improvement in the final conclusion using additional sampling. Interestingly, the third step, beginning with "which", assigned high importance and receives substantial attention from DISC. This step appears act pivotal decision point that shapes the direction of the remaining solution. This observation supports the idea that certain tokens sub-sequences function as critical reasoning forks pivols-consistent with findings from prior work 33 34..
Autoregressive models require autoregressive decomposition
While transition words such as 'which', 'therefore', 'wait', etc. may not appear significant to human readers, our decomposition frequently identifies them as critical decision points for autoregressive LLMs trained next-token prediction, where selecting different token these junctures can substantially alter the downstream reasoning and final outcome, Therefore, it is essential for inference algorithms allocate more compute toward sampling these steps, and to identify these steps automatically through I.IM data rather than through human design.
4 Experimental Results
4.1 Main Results
Benchmarks. We evaluate DISC on three benchmarks: APPS, MATH, and LiveCodeBench.
to assess its impact on inference scaling for both coding and reasoning. APPS [88] consists of 5000 competitive programming problems across three difficulty levels, with the competition-level subset being the hardest. We evaluate on 200-problem subset due to computational constraints. MATH (35] comprises 12,500 math problems. Since the ground-truth verifier provides only binary rewards, we use pretrained ORM [36], trained via the method in [37], with Llama-3.1-8 8B--nstruct the base model. We test 500-problem subset (MATH500), identical to prior work [37 23). LiveCodeBench [38] a continuously updated dataset from Leetcode, AtCoder, and CodeForces, ensuring LLMs have not been exposed to test problems. We evaluate on the 108 problems uploaded between 10/01/2024 and 12/01/2024 to prevent contamination.
Baselines. We compare DISC against three prior decomposition methods: TokenSplit (token-level decomposition), LineSplit (newline-basee decomposition), BoN (treating the entire solution as single step). These all standard and the most commonly used methods (see Sec. 2.2

---

Pass/ttoken Scaling APPS
Pass@rtoken Scaling MATH
Patsgitokeen scaling curves on LiveCodellech
Preser ooneee PPougooen
2.86
0.00
0.02
0:43
CESC Uieepp
0.32
0.00
0.3
TeaeSppl
91N
5002
Aumberoo sutbut TOkees 1003 Heleen))
20205
1503E
30000
25000
Numbbr
4302
(4 toners use (okees)
8020
B506
10303
12000
Norder cuu salons aood
Figure 5: Token-level comparisons across benchmarks using gpt-4o-mini. (Left) APPS competition level (Middle) MATH500 (Right) LiveCodeBench. DISC achieves superior inference scaling over baselines on all three benchmarks.
Metrics. We evaluate two key metries: Pass@k, the proportion of problems solved within a sample budget k and Pass @token the proportion solved within a given token budget. Note that k refers to the sample budget, not thousands of samples, and error proportion refers to proportion not solved. We 0.15, 1.0, and temperature т = 0.2 by default for DISC unless otherwise specified.
use Ogg
Performance. Across all benchmarks, DISC consistently delivers stronger performance and better scaling under both fixed token budgets (Fig. 5) and fixed sample budgets (Fig. [8. For example, on APPS, the pass@ 10 error proportion decreases from 0.50 to 0.475; on MATH500, from 0.15 to 0.14; and on LiveCodeBench, from 0.57 to 0.51. These correspond to 5.0% 6.7 % and 10.5% reduction in error relative to the best baseline, respectively. These improvements are particularly meaningful on more challenging benchmarks, where performance gains are harder to achieve, demonstrating DISC is effectiveness in guiding search toward high-reward regions. Extended results and analyses
provided in App. D.I D.4 and D.5 D.5
Passilk ng open source models
Pass@k scaling for
Taken scaling at low budget for R1
Jampiinii (8boe))
2.00
Ceepleec
6.35-
Vabul-B-00
8.1
1448-1148
Qwen-22-m1
2.35
0.03
2000 1000 1900
1990 R0co
Number ofooziora garareted
Number of soret ded
Numbur cad hocural
Figure 6: Inference scaling for different models, including reasoning models, on APPS. (Left Pass@) for open-source models. Colors correspond different models, with Pass being the base model performance. (Middle) @ass@k for RI, with green line as base Pass @ performance. (Right) Pass@tokes token for R1. DISC almost doubles base performance across all models.
Model Generality. DISC also provides substantial gains across range of models, including open-source LLMs. For instance, it improves LLaMA's pass @ 10 rate from 0.01 to 0.04 a 300 % relative increase. Similarly, it boosts Mistral's performance from 0.0 to 0.02, and Qwen's 's from 0.095 to 0.17, representing a 79% relative increase. As shown in Fig. 6 (left), these improvements hold consistently across sampling budgets, including in low-budget regimes. This demonstrates DISC general applicability and effectiveness even for weaker resource-constrainee models. Additional results and analyses are provided in App.
Reasoning Models. DISC also yields substantial gains when applied to strong long- form chain-of- thought (CoT) reasoning models such as RI [5] 39]. As shown in Fig. 6 (middle), DISC improves accuracy by over 85% % relative the base RI model using just 10 samples. Notably, Fig. 6 (right) shows that even under a constrained token pudget-matciinn DISC still achieves over 33% relative improvement. This demonstrates that DISC not only scales well with more samples but is also highly effective at identifying and prioritizing critical reasoning steps, leading stronger performance even in low-resource settings.
to that of a single sample from the base
Computational Overhead. DISC introduces negligible runtime overhead compared to standard decoding baselines, as shown Fig. 7 The vast majority of compute time-over 90% across all settings-be is still dominated by LLM token sampling, with only minor fraction spent on auxiliary
7

---

operations such as candidate management, z-score normalization, and recursive branching. Despite its dynamic control flow, DISC maintains runtime composition nearly identical that of methods like BoN and LineSplit. Moreover, because DISC achieves higher success rates with fewer tokens (Fig. 5), its effective runtime per correct solution is even lower. In practice, this makes DISC both algorithmically efficient and computationally scalable, offering improved search performance without additional inference cost. We provide a detailed runtime discussion in App. D.6
Tavesqir
Ewcteed
AY2
FL
TAXE
MIS
ALTS
Figure 7: Percentage of runtime spent on overhead vs LLM token generation. DISC does not increase the runtime overhead significantly.
Scaling by samples
Different decompasition methods on APPS (camp)
Passgik for differont search methods
0:50
2.55
230
8.45
0.43
035
Uredok Beaddrr
Lividit Takerplt
20C Crredd DeCCescam
0:30
2.55
2.5
50
7.5
10.0
12.5
15.0
175
23.0
20
Number ge
Figure 8: Comparison of @ass@k performance on APPS using gpt-4o-mini. (Left) self generated validation tests, (Middle) with ground truth tests, (Right) with different search methods.
Self-Generated Validation. We further evaluate DISC in a self- generated validation setting, where ground truth reward models or curated tests are unavailable (30 40 4T. Here, the LLM generates its own unit tests from the problem description, which serve as proxy reward model for evaluating candidate solutions. This setup offers scalable alternative to costly manual test curation in real- world code generation tasks.
As shown in Fig. 8 DISC scales effectively under this protocol, achieving a 54% relative improve- ment over the base model. This demonstrates that DISC leverages decomposition-based reasoning produce higher-quality code even when supervision is noisy or incomplete.
However, self- eeffggenratte validation has limitations: generated tests may be incomplete, inconsistent, narrow in coverage, potentially biasing performance estimates. While these issues do not affect the observed scaling trends, improving test reliability and robustness remains an important direction. Additional details and results are provided in App. D.3]
Search. We demonstrate that search strategies such as MCTS and beam search can be naturally integrated with DISC using the approach described in Sec. 3.4 As shown in Fig. 46 greedy search tends to explore deeper partitions within the same search budget due to its myopic nature, while MCTS and beam search explore more diverse but shallower paths. Despite similar depth, MCTS outperforms beam search by allocating its search budget more strategically foouuuin exploration on more promising candidates-resut unlike greedy search, which irrevocably commits to prefixes as they are accepted, MCTS maintains flexibility by exploring committing multiple candidate prefixes in parallel. Additional details and analysis are provided in App. F
in superior overall performance,
in Fig. | Furthermore,
4.2 Ablation Studies
Temperature. Typically, inference scaling methods achieve optimal performance at temperatures around 0.6-0.8, as increased temperature promotes sample diversity
42.. Surprisingly, however, DISC performs better at lower temperatures, shown in Fig. 9 This trend is in stark contrast to
8

---

Pass@k scaling curves by temporature
Pass@l scal ing for differentt priontyy metrics
Ablation on portition traction
0,59
6.95
0.4
0.45
0.33
DS5 4atms
1.43
DSCA
D560
D562
DSC ab27am22
DSC dlat 20
Mats-33
0.55
0.35
DSC 1270
DSC
splt 1.10
6.25
2.5
6.2 3,5 18n 125 18 13. M0
Numberr of wwwninnt orneated 30 Figure 9: Ablation study of DISC on APPS with gpt-4o-mini. (Left) Effect of temperature: unlike BoN and other inference scaling methods. DISC achieves higher performance at lower temperatures. (Middle) effect of acceptance method (Right). Effect of partition fraction ou: The range 0.15 S co S 0.25 appears optimal.
Number ddaaaai garerniss X
Number of coutions prnerates
BoN (Fig. [6). where higher temperatures are generally beneficial. We believe this phenomenon arises because DISC depends on estimating the z-score each step using sample statistics. Lower temperatures reduce sample variance, leading to more reliable estimates, which in turn improves step selection. This is further supported by Fig. [4 which shows that lower temperatures yield lower standard deviations per step, indicating increased sampling consistency. Additional details and analyses can be found in App. C.T
Acceptance Method. We perform ablation study to evaluate whether using the z-score is an effective criterion for accepting candidate prefixes. Specifically, we compare our standard z-score- based acceptance method, DISC-Z, against four alternative baselines: DISC-R, which accepts candidates uniformly at random; DISC-Q, which accepts if the candidate prefix has lower mean value; DISC-negQ, which accepts if the candidate has a higher mean; and DegC-negZ, which accepts the candidate has a higher Z-score (rather than a lower onc). As shown in Fig. 9 the choice of acceptance criterion substantially influences performance. Among all methods, DISC-Z achieves the highest performance, while DiSC-negZ. performs worse than random selection, underscoring the importance of prioritizing candidates with higher probability of improvement. Additional details and analysis are in App. C.2
Partition Fraction ag. As shown in Fig. 9 and Fig. 25 performance is highest when the partition fraction lies in the range 0.15 S an S 0.25. Smaller values of an generally yield better results because they lead to more conservative proposals- -i.., shorter candidate prefixes. This conservatism is beneficial due to the high cost of prematurely committing to suboptimal prefix: once a candidate prefix is accepted (in greedy-DISC), it becomes fixed and cannot be revised. By keeping candidate prefixes short, the algorithm retains more flexibility to correct course in future steps. Additional analysis is provided in App.
4.3
Analysis and Interpretation
Mean wewrr step
Standard deviation rewards per stop
Frequency (actual) partioons
0.8
Tecnripht
0.12
Stan
Panttor treq reequrnny
345c
Moan roverd
prrtppet
Rowaad 213
0.38
Un uneiph
ueetpe.
0.00
0.c
0.
0.4
14
Step number
Step number
Number pontiionn
Figure 10: Analysis of decompasition methods. Dotted lines fit linear model to indicate the trend. (Left) Average reward per step: From step onward, higher step counts strongly correlate with increased average reward, demonstrating the effectiveness of decomposition. The dip between steps I and 3 likely occurs because simple problems are solved early, preventing further search. (Middle) Standard deviation of rewards per step: Decomposition reduces sampling variance, improving precision at deeper search depths. (Right) Frequency of the number of partition steps that the search algorithm committed to the prefix during the search process.
Our results strongly suggest that decomposition whether line-based, sistently improves sample quality. Fig. (left and middle) shows how the mean and variance of sampled rewards evolve with the step number, i.e., the number of steps committed to the prefix during search. As the step number increases, the mean reward improves, indicating that longer committed prefixes lead to higher-quality solutions. At the same time, the variance of rewards
or DISC con-

---

decreases, suggesting that committing to a longer prefix also improves the precision of sampling. These trends highlight the benefits of finer-grained decomposition and incremental commitment in guiding the search process more effectively.
Furthermore, DISC achieves higher performance using fewer committed prefix steps-and thus fewer sampling stages-under a fixed sampling budget. Fig. [O] (right) shows the distribution of actual partitions, i.e., the number of steps effectively committed under a finite budget. As shown, DISC typically requires only 1-5 actual partition steps, whereas other methods commit to significantly more. This indicates that DISC is more efficient identifying high-impact prefixes, enabling better performance with fewer sampling decisions.
Limitations. While DISC demonstrates strong empirical performance, several limitations remain (see Appendix E for a detailed discussion). In particular, DISC assumes access to reasonably accurate reward model. For example, in code generation tasks, this requires that either ground-trute validation tests are available or the model can self-generate sufficiently reliable ones. Addressing these limitations throoughh improved test generation, learned verifiers, and more robust evaluation pressentss promising directions for future work.
Decomposition and Sample Quality
DISC enables more efficient exploration by identifying high-impact prefixes with fewer steps. Incremental prefix commitment not only improves sample quality moality-yielding higher average rewards-but but also reduces reward variance, leading to more stable and reliable outputs under fixed sampling budget.
5 Related Work
Inference scaling. Inference scaling has emerged as a dominant paradigm, driven by the introduction of ol- and rl ri-like ofainnof-tthough reasoning models [5] 6
43, 44). Several works examine the
trade-off between inference compute and training compute 45 46 LLM inference often relies on decomposing complex problems into intermediate reasoning steps, as seen in chain-of-thougle (CoT)
prompting [47 48 49 and its variants [50
51
52
53
We extend inference scaling by introducing a
new approach for adaptive compute allocation
43
54
55
LLM reasoning and code generation. LLM reasoning and code generation are central tasks for inference scaling. Evolutionary inference scaling methods have been explored in program
generation [56] 57 58 59
60]. Domain Domain-specific decomposition strategies have been applied in code generation, such as function- based decomposition [61 62 63 More broadly, decomposition often
involves prompting LLMs to generate subtask completions
64
66], which differs from methods
that refine a single I.M generation.
Reinforcement learning and Monte Carlo methods. Unlike standard RL,, setting resembles a search problem where the goal to identify the single highest-reward path. Nested Monte Carlo search can accelerate optimal pathfinding (67). Under the bandit setting, this can be formulated as identifying the arm with the highest maximum reward rather than the highest mean reward (68 69
6 Conclusion
We introduce DISC, a dynamic decomposition framework that adaptively partitions solution steps based on first order statistics that capture potential for improvement, improving inference scaling by directing compute toward critical steps while balancing exploration and resource allocation. DISC naturally integrates with search-based methods such as MCTS and beam search, further enhancing performance. also identifies challenging steps for LLMs, aiding curriculum learning, fine-tuning, and dataset augmentation. By dynamically adjusting partitioning and step sizes based available compute, DISC enables more adaptive and efficient reasoning in large language models, with broad implications for both training and inference optimization.
10

---

References
[1] Xidong Feng, Ziyu Wan, Muning Wen, Stephen Mareus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tre-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17173 2023.
[2] Zhiyuan Zeng. Qinyuan Cheng, Zhangyue Yin, Bo Wang, Shimin Li, Yunhua Zhou, Qipeng Guo, Xuanjing Huang, and Xipeng Qiu. Scaling of search and learning: A roadmap to reproduce ol from reinforcement learning perspective, 2024.
[3] Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models, 2024.
[4] Harsha Nori, Naoto Usuyama, Nicholas King, Scott Mayer McKinney, Xavier Fernandes, Sheng Zhang, and Eric Horvitz. From medprompt to ol: Exploration of run-time strategies for medical challenge problems and beyond, 2024.
[5] Charlic Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute opti- mally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.0.3: 03314,, 2024.
[6] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V Le. Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:
2024.
[7] Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah Goodman. Stream of search (sos): Learning to search in language. arXiv preprint 2rXiv:2404.0368. 2024.
[8] Kuang-Huce Huei Lee, Ian Fischer, Yuch-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schuur- mans, and Xinyun Chen. Evolving deeper Ilm thinking, 2025.
[9] Jonathan Light, Min Cai, Weiqin Chen, Guanzhi Wang, Xiusi Chen, Wei Cheng, Yisong Yue, and Ziniu Hu. Strategist: Learning strategic skills by ilms via bi-level tree search. arXiv preprini a40iv:2408. 10635, 2024.
[10] Evan Wang. Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, and Hugh Zhang. Planning natural language improves LLM search for code generation. In The Thirteenth International Conference Learning Representations, 2025.
[11] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 36, 2024.
[12] Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. Parsel: Algo- rithmic reasoning with language models by composing decompositions. Advances in Neural Information Processing Systems, 36:31 16:31466-31533, 2023.
[13] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625. 2022.
[14] Zicheng Lin, Tian Liang, Jiahao Xu, Qiuzhi Lin, Xing Wang, Ruilin Luo, Chufan Shi, Siheng Li, Yujiu Yang, and Zhaopeng Tu. Critical tokens matter: Token-level contrastive estimation enhances Imm's reasoning capability, 2025.
[15] Daya Guo. Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprint arXiv:2501.12945 2025.
[16] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et Evaluating large language models trained on code. arXiv preprint 1312:22007.03374 2021.
11

---

[17] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint 2exiv::208.07777 2021.
[18] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprini wwriv::210.03388 2021.
[19] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert. Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10..:.188, 2021.
[20] Lunjun Zhang, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. Generative verifiers: Reward modeling as next-token prediction, 2024.
[21] Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoc Le. Ed H. Chi. Sharan Narang, Aakanksha Chowdhery, and Denny Zhou, Self-consistnney improves chain of thought reasoning in language models. In The Eleventh International Conference on Learming Representations, 2023.
[22] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing. Hao Zhang. Joseph E. Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt-hench and chatbot arena, 2023.
[23] Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.200500 2023.
[24] Zhenwen Liang, Ye Liu, Tong NIu, Xiangliang Zhang, Yingbo Zhou, and Semih Yavuz. Im- proving Ilm reasoning through scaling inference computation with collaborative verification. arXiv preprint 2410:22410.05318, 2024.
[25] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024.
[26] Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzich Fadace, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to basics: Revisiting reinforce style optimization for learning from human feedback 11ms. arXiv preprint 14X14:2402.14740, 2024.
[27] Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong. Zhen Wang. Daisy Wang, and Zhiting Hu, Rea- soning with language model is planning with world model. In Empirical Methods in Natural Language Processing, pages 8154 8173, 2023.
[28] Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, James Xu Zhao, Min- Yen Kan, Junxian He, and Michael Xie. Self-evaluation guided beam search for reasoning. Advances in Neural Information Processing Systems, 36, 2024.
[29] Jonathan Light, Yue Wu, Yiyou Sun, Wenchao Yu, Xujiang Zhao, Ziniu Hu, Haifeng Chen, Wei Cheng, al. Scattered forest search: Smarter code space exploration with llms. arXiv preprint arXiv:2411.05010, 2024.
[30] Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. Codet: Code generation with generated tests. arXiv preprint arXiv:2207. 10397, 2022.
[31] Nat McAleese, Rai Michael Pokomny, Juan Felipe Ceron Uribe, Evgenia Nitishinskaya, Maja Trebacz, and Jan Leike. Llm critics help catch Ilm bugs, arXiv preprint arXiv:2407.00275, 2024.
[32] Jiawei Gu, Xuhui Jiang, Zhichao Shi, Hexiang Tan, Xuehao Zhai, Chengjin Xu, Wei Li, Yinghan Shen, Shengjie Ma, Honghao Liu, et al. A survey on llm-as-a-judge. arXiv preprint arXiv:2411. 155554 2024.
[33] Eric Bigelow, Ari Holtzman, Hidenori Tanaka, and Tomer Ullman. Forking paths in neural text generation. arxiv preprint arXiv:2412.07961, 2024.
12

---

[34] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Perey Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv preprint arXiv:2501. 19393, 2025.
[35] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint 103.03874, 2021.
[36] Wei Xiong, Hanning Zhang, Nan Jiang, and Tong Zhang. An implementation of generative prm. Reward-Mode
https://g: https:///gihhb.....m cww/
2024.
[37] Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 9426-9439, 2024.
[38] Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Ar- mando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint urXiv:2403.07974 2024.
[39] Qiguang Chen, Libo Qin, Jinhao Liu, Dengyun Peng, Jiannan Guan, Peng Wang, Mengkang Hu, Yuhang Zhou, Te Gao, and Wanxiang Che. Towards reasoning era: A survey of long chain-of-though for reasoning large language models. arXiv preprint arXiv:2503.0956) 2025.
[40] Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128 2023.
[41] Andy Zhou, Kai Yan, Michal Shlapentokh-RRothnn Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. ICML, 2024.
[42] Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, and Hugh Zhang. Planning in natural language improves 11m search for code generation. arXiv preprint arXiv:2409.03755 2024.
[43] Rohin Manvi, Anikait Singh, and Stefano Ermon. Adaptive inference-time compute: Lims can predict if they can do better, even mid-generation. arXiv preprint arXiv:2410.00725, 2024.
[44] Kuang-Huei Leea, Ian Fischera, Yueh-Hua Wue, Dave Marwood, Shumeet Baluja, Dale Schuur- mans, and Xinyun Chen. Evolving deeper Ilm thinking. Gen, 2:3, 2025.
[45] Xinyu Guan, Li Lyna Zhang, Yifei Liu, Ning Shang, Youran Sun, Yi Zhu, Fan Yang, and Mao Yang. rstar-math: Small Ims master math reasoning with self-evolved deep thinking, 2025.
[46] Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu, Mengfei Zhou, Zhuosheng Zhang, Rui Wang. Zhaopeng Tu, Haitao Mi, and Dong Yu. Do not think that much for 2+3=? on the overthinking of ol-kike 1lms, 2024.
[47] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. NeurlPS, 35:24824-24837, 2022.
[48] Zayne Sprague, Fangcong Yin, Juan Diego Rodriguez, Dongwei Jiang, Manya Wadhwa, Prasann Singhal, Xinyu Zhao, Xi Ye, Kyle Mahowald, and Greg Durrett. To cot or not to cot? chain-of- thought helps mainly on math and symbolic reasoning. 2024.
[49] Xuezhi Wang and Denny Zhou. Chain-of-thought reasoning without prompting, 2024.
[50] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are shoo reasoners. Advances in neural information processing systems, 55:22199-222 22213, 2022.
13

---

[51] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuur- mans, Claire Cui, Olivier Bousquet, Quoe V Le, al. Least-to-most prompting enables complex reasoning in large language models. In International Conference on Learning Representations, 2023.
[52] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations, 2023.
[53] Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pages 5315-5333, 2023.
[54] Ibrahim Alabdulmohsin and Xiaohua Zhai. Recursive inference scaling: A winning path to scalable inference in language and multimodal systems. arXiv preprint arXiv:2502.07503, 2025.
[55] Fei Wang, Xingchen Wan, Ruoxi Sun, Jiefeng Chen, and Sercan Ô Ari.. Dynscaling: Ef- ficient verifier-free inference scaling via dynamic and integrated sampling. arXiv preprint wMXiv:2506.16443 2025.
[56] Vadim Liventsev, Anastasiia Grishina, Aki Härmä, and Leon Moonen. Fully autonomous programming with large language models. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1146- 155, 2023.
[57] Angelica Chen, David Dohan, and David So. Evoprompting: Language models for code-level neural architecture search. Advances in neural information processing systems, 36:7787-7817, 2023.
[58] Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang. Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468 475, 2024.
[59] Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O Stanley. Evolution through large models. In Handbook of Evolutionary Machine Learning. pages 331-366. Springer, 2023.
[60] Erik Hemberg, Stephen Moskal, and Una-May O' O'Reilly. Evolving code with a large language model. Genetic Programming and Evolvable Machines, 25(2):21, 2024.
[61] Jingchang Chen, Hongxuan Tang, Zheng Chu, Qianglong Chen, Zekun Wang, Ming Liu, and Bing Qin. Divide-and-conquer meets consensus: Unleashing the power of functions in code generation. arXiv preprint arXiv:2405.20092. 2024.
[62] Janis Zenkner, Lukas Dierkes, Tobias Sesterhenn, and Chrisitan Bartelt. Abstractbeam: En- hancing bottom-up program synthesis using library learning. arXiv preprint arXiv:2405.175/4 2024.
[63] Kyla H Levin, Kyle Gwilt, Emery D Berger, and Stephen N Freund. Effective lim-driven code generation with pythoness. arXiv preprint arXiv:2501.02 138, 2025.
[64] Sergio Hernández-GGutiinn Recursive decomposition with dependencies for generic divide-and and--cnquer reasoning. The First Workshop on System-2 Reasoning at Scale, NeurlPS 2024.
Minttu Alakuijala, Alexander V Nikitin, and Pekka Marttinen.
[65] Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. arXiv preprint arXivv2210.02406, 2022.
[66] Dheeru Dua, Shivanshu Gupta, Sameer Singh, and Matt Gardner. Successive prompting for decomposing complex questions. arXiv preprint arXiv:2212.0 22000099,,, 2022.
14

---

[67] Tristan Cazenave. Nested monte- search. In Twenty-Fivg International Joint Conference on Artificial Intelligence, 2009.
[68] Vincent A Cicirello and Stephen Smith. The max k-armed bandit: A new model of exploration applied to search heuristic selection. In The Proceedings of the Twentieth National Conference on Artificial Intelligence, volume 3, pages 1355-1361, 2005.
[69] Alexandra Carpentier and Michal Valko. Extreme bandits. Advances in Neural Information Processing Systems, 27, 2014.
15

---

Contents
Introduction
Preliminaries
2.1
Problem Setting
2.2
Existing Decomposition Methods
2.3
Search for Inference Scaling
3
Methodology
3.1
High-level Overview
3.2
DISC with Greedy Search Algorithm
Analysis of DISC with Greedy Search
3.4
DISC for Plug-and-Play with Search Algorithms
3.5
Example Decomposition
4
Experimental Results
Main Results
Ablation Studies
Analysis and Interpretation
5
Related Work
10
6
Conclusion
10
Code implementation of DISC
18
Pseudocode for DISC
19
Ablation studies
21
Ablation on Temperature
Acceptance Method
23
Model Ablation
25
Ablation on Partition Fraction d
26
Reward Distribution
26
D Main Results Extended
28
D.1 APPS
28
D.2
Additional Examples
29
D.3
APPS with Self-generated Validation Tests
29
D.4
MATH500
31
D.5
LiveCodeBench
32
D.6
Computational Overhead
33
16

---

Limitations
34
Search and Scaling
35
F11
DISC Plug-and-Play Search
35
F.2
Monte Carlo Tree Search (MCTS)
35
................................
E2.1
Selection
35
F2.2
Expansion
35
F2..3
Simulation
36
F2.4
Backpropagation
36
F2.5
Combining Dynamic Decomposition with MCTS
................................
36
Beam Search
36
F R.4
Additional Results and Analysis
37
Theoretical analysis
Main Theorem
39
G.2
A Motivating Example DISC
41
Compute Resources Used
43
Impact Statement
43
17

---

A Code implementation of DISC
To aid reproducibility and practical adoption, we provide Python-style pseudocode in this section that closely mirrors our actual implementation. The pseudocode abstracts away low-level engineering details while preserving the core logic, function names, and control flow used in our codebase. This alignment ensures that readers can easily translate the pseudocode into a working implementation or modify it for their own use cases. All key components of the DISC seerithmminnluddng dynamic step refinement, z-score-based acceptance, and integration with search strategies- reflected in this pseudocode with minimal deviation from the actual code.
Python implementation of DISC
semamic_decommaattion (enomppattonnpprbbllatt nodel, revard_nodas nodel, aplit_atr, complete solutiionn fraction, solution_ budget, split_ _uetric, stop, ("ootdd"dd stop.sun_score-1. stop_if..olveedFaale.
Decomposes the solution using dynamic binary search approach
Args:
problem (Problea): problen generation model (Model): The model to use for revard_nodel (function): The revard nodel split_atr (function): The function to use for splitting string
scoring
complete, atllttttoooi (function): The function to use for completing solution fraction split solution_ budget (int): The naximum nunber of solutions to generate split_metric (function): The netric
fraction (float):
string
aplitting
stop_threshole (float): The threshold to stop splitting
stop_eum prop_eu_eccor (flost):
stop generating completions
stop soop_if_solved (bool):
stop the problem
# Initielize reaulta and decomposition stepa decoup_
snberrated_ooutioonn 0,
"dacomposttion":
while len (deconpp reture "essttrnlgggneeeeeee ("generated_ solptttion__luiinn solution_budee budget:
Combine all previous stepe into an intermediate solution
aetemmediateeeelutiinn "","", "..join([etep("stepp. for step in decomp_ decompooition ']])
nev_scores []
best, complationnn Mone best_acore -float ("int(")nf")
sun_acore
Generate completions score:
generate enough samples
split netric
while sum, score < stop__uu__sea
aapossed_cmppettin complete_solutiont (protion cetmeeiiate_oouuttie model) proposed_completion
propoeed_ selution iaternediate_eolln (poooedpropped__eooo soluttoon)
decomp_retural weweurrrreeeeereeeeeee wew.eeetee.oouueeeeeeeeeeeeeeeee
Update scores
proposed_acom revard madel proopssed_solutionn
sew_scores. ces_scores.appendprree (ppood
+- proposed_score
Track the best solution
proposed_score best_acore:
beat_ proposed_soluttee
best_score proposed_score best_couplett propoeed_completion
Stop early problen if stop_if_ aolvevd and proposed_acore 1.0:
deconp_raturn [" dddoopossstion lapppnd proposed__cmmpeeiinn)) return decomp_retura
nev_netric split_ settt_eetricnee., (nee__coress)
last_netric decomp_retura (ataoppreeurraddeeeppppooo ("decoaposition] [-1] ["metric"] if deccap_ return wttp:reeetuutdreeeeaa ("decamposition
Deternine the split target. We alvays split the with the highest netric ja_split__ev__ee last_metric split_targes decomp_ return ["dccomposition compoosttiionoooo [-1] ["stap_atr"] it not is_split_nex_step else best_completion
or neu_nete noutrriiic last_metric
18

---

Attempt split the paiitrresutt split__tr(eplit_tatt if not split_result: If can't split the target, we're done decomp_ decomp. returet decooppiicoooiiio append best_completion, "netric"; nev sev_netric)) recoup_return
fraction)
Update dacompasition based split
parti, part2 aplit_rreult
if st_split_nex.atep:
decomp_rretual cecopprreturaadecooppe "eturaa(dcccpociitioo [appen((""tep__tt")) parti, "notric": nev_notric))
Stopping condition based on threshold
if nev_metric thp_sbbes:ood::
decomp_returnl (anrrrnddecompppi ("decompssitioa" .sppend(""ttp_ssttt) part2))
retura decoup_reture
["decosposiiioon"] [-1] ("step_atx"; parti, "metric"; last_netric)
return decurn
B Pseudocode for DISC
19

---

Algorithm 2 Dynamic Decomposition
1: Input: Problem instance reward model r, partition function /. LLM policy model partition
fraction a, solution budget B, priority metric h, metric stopping precision 6, sampling stopping threshold d, is inference mode Dinference
2: Output: Final decomposition D
3: Initialize D
snnnerated_soluttinnn Ø decomposition Ø
4: # Decompose the solution recursively until we reach the desired precision or run out of budget
B
5: while D D.generated__ee soluution B do
6:
Vintermediate Concatenate ([tepp.step_s)) _ttrsstrr step D. d.dccomposition)
7:
> Concatenate previous steps to form intermediate solution
8:
Raew
D> Record rewards of completions
9:
best. Viinal <- None, best. Doumpltionn f- None, best.7 & -00 D Track the best completion
Step 1: Generate completions until we have enough samples to estimate the splitting metric. Here we use geometric sampling distribution
11:
while sum (Rew)) < do
12:
Vcompletion < (-|ar, Vintermediate)
13:
Mproposed f Vittermdiate + /completion
14:
Append Vppropoee D. -ecnerated_solutionss
15:
Pproposed f 7 (3propooeed)
16:
Append proppsed Raew
17:
"proposed
> best. then
18:
best.yiinal 3proposed= best. Dcompletion
Vcompletion
19:
best.r f pproposed
20:
end if
21:
Dinference and "proppoee = 1.0 then
22:
Append (step_str: |Joopplttonn to Dedccomposition
23:
Return
Exit if problem is solved
24:
end if'
25:
end while
26:
Step 2: Compute splitting metric
27:
Blass Dddecompositionn-111
D. decoomposition * else 00
29:
Step 3: Split the step with the higher metric
30:
Deplit step
f-
Znew 2 Plast
31:
Uuarget step
bes... Vcompletion if Deplit new step else D.decomposition[11] -1t.stt
32:
VI, 82
[Mturget step; 0x)
33:
if 21
None or 3/2 None then
34:
Append {step_str Ycompletion: metric: knew to D.decomposition
35:
Return
Exit if we cannot do finer split
36:
end
37:
if split new stop then
38:
Append {step_ str 1/1 metric Enew to Deccomposiiion
> Add new step
39:
if Snew < 9 then
40:
Append (step_str: y2) to D.decomposition Return
41:
Exit if all metrics are smaller than precision
42:
end
43:
else
44:
D. deccomposition|11| +- istep_str: y1, metric 3
D Split last step
45:
end if
46:
end while
Return D
20

---

C
Ablation studies
C.1 Ablation on Temperature
We conduct an ablation study to analyze the effects of temperature on DISC and BoN. Temperature controls the randomness of token sampling in autoregressive models, influencing both exploration and consistency. Higher temperatures encourage more diverse outputs, whereas lower temperatures yield more deterministic generations. To examine its impact, we evaluate DISC and BoN on 100-problem subset of APPS (the first 100 problems) using gpt-4o-mini.
Figure I presents the Pass@toker scaling curve for DISC across different temperatures. The results indicate that lower temperatures lead to improved performance, as DISC benefits from more deterministic step selection. Unlike BoN, which relies broad solution sampling, DISC dynamically refines steps, making stable token probabilities advantageous.
Figure 12 illustrates the frequency of actual partitions made by DISC different temperatures. As temperature increases, the number of partitions fluctuates more, suggesting that high temperature introduces instability in step selection. Lower temperatures provide more structured decomposition, reducing unnccessary subdivisions.
In Figure 1 we visualize the mean reward per step. The trend shows linear increase in reward as step number grows, demonstrating that deeper decomposition results in progressively better solutions. This reinforces that DISC effectively allocates computation towards refining difficult steps.
The mean standard deviation per step is shown in Figure 14 Lower temperatures yield lower standard
deviations, confirming that DISC benefits from reduced variability in sample quality. This consistency allows for reliable prioritization of difficult steps, enhancing overall inference efficiency.
For comparison, Figure 16 and Figure I5 display Pass@ token and Pass@ scaling curves for BoN across different temperatures. Unlike DISC. BoN achieves peak performance at temperature around 0.6-0.8, balancing diversity and consistency. Higher temperatures increase exploration but degrade precision, while lower temperatures hinder sample diversity, reducing the probability of obtaining high-quality completions.
These findings highlight the fundamental difference between DISC and BoN: DISC benefits from lower variance and stable decomposition, while BoN relies on broader exploration facilitated by moderate temperature settings. As a result, optimal temperature settings differ significantly between these methods, with DISC favoring deterministie sampling and BoN requiring a balance between diversity and coherence.
21

---

Pass@token scaling curves
Frequency of (actual) partitons
Progortion (Pass@token)
2tcmp
0.55
Partition frequency
DISC-0.4K8 40e-0.
DISC-0. Dtempp
0.50
0.4
DISC-0, 8temp
DISC-1
Dise-0.2temp
0.3
DISC-1 2oemp
0.45
DISC-0.4temp
0.2
0.40
DISC-0,8temp
DIBC-1.0temp
0.1
0.35
DISC-1.2temp
0.0
15000
20000
2
8
10
12
14
Number of output tokens used (tokens)
Number partitions
Figure II: Pass@ token scaling curve for dif- ferent temperatures on APPS using gpt-4o- mini The lower the temperature, the stronger the DISC performance.
Figure Partition frequency of DISC with
different temperatures on APPS using gpt-4o- mini.
Mean reward per step
Standard deviation of rewards per step
0.9
DiSC-0.2temp
reward
0.8
DISC-0. 6temm
4tempp
0.15
DISC-0.4temp
DISC-D.BC Btemm
Reward std
DisC-o,atemp
0.7
Dise-1.0cemp
DISC-1.0temp
DISC-1. 2temp
0.10
DISC-1 2temp
0.6
0.05
0.5
0.00
6
10
12
14
2
10
12
14
Step number
Step number
Figure 13: Mean reward per step of DISC with different temperatures on APPS using gpt-4o-mini. The mean reward scales linearly with step number.
Figure Mean standard deviation per step of DISC with different temperatures on APPS using gpt-4o-mini. Lower temperature means lower average standard deviation.
Pass@k scaling curves
Pass@token scaling curves
0.55
Propartion correct (Pasgttkken)
0.50
0.50
0.45
0.40
BoN 0.temp
4oemp
0.45
BoN-O. temp
0.4temp
0.35
0.6temp
BoN 0.6temp
BoN 0.Stemp
BoN-o. Stemp
BoN- 1teemp
0.35
BoN-3 BoN-1.0temp
0.25
BoN-1.2temp
BoN--12temp
75002000022500
Number of solutions generated [k]
Number of output tokens used (tokens)
Figure 15: @ass@k scaling curve for different temperatures APPS using gpt-4o-mini for BoN. temperature around 0.6-0.8 leads to the best performance and balance between diversity and consistency.
Figure 16: Pass@ token scaling curve for differ- ent temperatures on APPS using gpt-4o-mini for BoN. temperature around 0.6-0.8 leads to the best performance and balance between diver- sity and consistency.
22

---

C.2 Acceptance Method
Frequency of (actual) partitons
Pass@token scaling for different priority metrics
DISC-R
Propurtion correct (Pasilotee))
Partition frequency
0.5
DISC-Q
0.55
0.4
DISC-negO
0.3
DISC-neg2
0.45
0.2
DISC-Q
DISC-Z
0.1
DISC-negQ
0.35
4000
12000
Number of outpur takens used (tokans)
Number partitions
Figure 17: Token level comparison of difffernnt priority metries on DISC in the APPS setting with gpt-4o-mini. Both Q and Z based priority metrics perform well.
Figure 18: Partition frequeney of DISC with different priority metrics on APPS using gpt- 4o-mini.
Mean reward per step
Standard deviation of rewards per step
DISC-R
0.8
DISC-Q
0.12
Mean reward
DISC-Z
0.10
DISC-negO
Reward std
0.7
DISC-negZ
0.08
0.6
0.06
0.04
DISC-Q
DISC-2
0.02
DISC-negQ
DISC-negZ
12
2
10
12
Step number
Step number
Figure 19: Mean reward per step of DISC with different priority metrics on APPS using gpt-4o-mini. All metries display strong correla- tion between step depth and the mean reward.
Figure 20: Mean standard deviation per step of DISC with different priority metrics on APPS using gpt-4o-mini. All metrics display correlation between step depth and the standard deviation.
We analyze the impact of different acceptance methods on DISC's performance. These meth- ods govern whether a candidate prefix accepted for further decomposition, directly influencing efficiency, stability, and final solution quality.
We begin by introducing notation to characterize the distribution of rewards obtained when sampling completions from given prefix p. Let Rp denote the random variable of the reward of completion sampled from the LLM policy æ conditioned on prefix p:
Rp = R(p 8), where 7(- p).
Let Fp, Mp, and op be the cumulative distribution function (CDF), mean, and standard deviation of Rp, respectively.
To estimate these quantities in practice we sample M completions from the policy:
Yp (p s', R(s))) s' ~ I(- p)] -
From these samples, compute the empirical mean and standard deviation:
M
1
R(s'),
(R(s²) 1pp)²
Hp
Op
M
M
23

---

(1) Let Tp max; R(s') denote the sample maximum reward observed for prefix p. at fixed
We evaluate DISC on the first 200 competition- level APPS problems using temperature of 0.8. The following acceptance methods are compared:
DISC-Z: accepts if the candidate prefix has lower 7-score than the base prefix b.
DISC-Q: accepts if the candidate prefix has lower mean reward, i.e., Me. lbb.
DISC-negZ: accepts if the candidate has higher z-score.
DISC-negQ: accepts if the candidate has higher mean reward.
DISC-R: accepts candidate uniformly at random.
Z-score Based Acceptance (DISC-Z). For a base prefix b and candidate prefix estimate the z-score of the sample maximum (1) as:
(1)
Ze
Fe
Hec
so P > 1 )
=
de
We accept e if ze chance improvement.
=b- A lower 7-score implies a greater tail probability mass and thus higher
Q-based Acceptance (DISC-Q). This method accepts if its sample mean is lower than that of
Pe < Pb-
While simple, this method compares absolute expected values without accounting for reward variance, making it less robust to noise in i''s samples.
Empirical Comparison. Figure 17 shows token-level performance across methods. DISC-Z
significantly outperforms alternatives, highlighting the value of normalizing reward advantage by variance.
Figure 18
shows that DISC-Z produces fewer but more meaningful partitions, suggesting better allocation of compute.
Figure 19 shows that DISC-Z achieves sharper reward gains early on, indicating better prioritization of impactful refinements.
Figure 20 reports sise reward variance. DISC-Z yields the most stable and consistent improve- ments.
Why Z-score Works Best
Z-score based acceptance balances the mean and variance of reward samples, estimating the probability of improvement in a statistically grounded way. This leads to more reliable and efficient decomposition decisions.
Overall, our results confirm that acceptance method design is critical for dynamic decomposition. Among all tested methods, DISC-Z consistently delivers the best performance and compute efficiency.

---

C.3 Model Ablation
Token scaling for open source models
Frequency of (actual) partitons
0.6
Mistral-
0.05
Partition frequency
Liama-3. 3.1-8331-88
0.04
0.3
0.03
0.2
Proportion
0.1
0.02
Mistral-78-vdl -0-0.3
Llama-3. -.1ma-3.1-88
10000
15000
20000
25000
Number of sutput tokens used (tokens)
Number partitions
Figure 21: mass@tokent scaling curve for open source models with DISC on APPS. DISC also demonstrates strong performance gains with open source models.
Figure 22: Partition frequency of DISC with open source models on APPS.
Mean reward per step
Standard deviation of rewards per step
0.4
Mistral-7B-v0.3
Mistral-7B-v..3
Liama 3.1-88
0.25
Llmma-311-88
Mean reward
Reward std
0.20
0.15
0.10
0.05
0.00
2
3
4
4
8
Step number
Step number
Figure 23: Mean reward per step of DISC with open source models APPS.
Figure 24: Mean standard deviation per step of DISC with open source models on APPS.
We investigate how different LLMS perform when used with DISC 200 competition-level APPS problems, given a sample budget of 30. The groundtruth reward model was used to evaluate correctness, and all models were set to a temperature of 0.8. Due the challenging nature of the benchmark, open-source models struggled to achieve strong performance independently. However, when paired with DISC, their performance significantly improved.
Figure presents the Pass Pass@token scaling curve for open-source models using DISC. The results demonstrate that DISC substantially enhances the capabilities of these models, closing the gap between them and proprietary alternatives.
Figure 22 visualizes the partition frequency of DISC with different open-source models. Compared their standalone performance, the use of DISC led more structured and effective decomposition, highlighting its adaptability to different architectures.
The mean reward per step is shown Figure 23 Similar to prior findings, we observe that deeper decomposition leads to increasingly higher rewards. Notably, even lower-capacity models benefit from DISC ability iteratively refine their solutions.
Finally, Figure 24 presents the mean standard deviation per step. With DISC, the variance in performance significantly reduced, resulting in more stable and reliable inference.
Overall, these findings emphasize that DISC a robust framework capable of enhancing inference performance across diverse LLMs, particularly those with limited standalone capabilities.
25

---

C.4
Ablation on Partition Fraction a
Ablation partition fraction
Ablation partition fraction
poportonn (Passttoken
0.55
Proportion correct (Pass@N) (Passct
0.50
0.50
0.45
0.45
DISC alpha-0.10
DISC alpha-0.38
0.40
DISC alpha=0.15
0.40
DISC alpha=0:25
elpha=0.20
DISC
0.35
DISC alpha-0.25
DISC alpha
DISC alpha-000
DISC alpha-
0.30
0.30
5000
10000
15000
20000
Number of output tokens used (tokens)
Number of solutions generated (k)
Figure 25: Token level comparison of different DISC splitting fraction Og APPS compe- tition level. 0.15 < oxp < 0.25 seems to be optimal.
Figure 26: Effect partition fraction on in DISC on APPS with gpt-4o-mini. The range 0.15 I ao S 0.25 appears optimal.
We include additional analysis the effect of the initial partition fraction ao. which determines the fraction the best suffix used to propose new candidate prefix at each iteration. As shown in Figures 25 and 26 we observe that performance peaks in the range 0.15 I ap I 0.25, with both leken-level and Pass @k metrics favoring this region.
This behavior aligns with the underlying motivation of DISC: a smaller results in more conser- vative candidate proposals-shorter steps that allow for finer-grained refinement. This is beneficial because committing suboptimal prefixes early in the search can lead to irrevocable errors, especially greedy search variants. Smaller values of ag give the algorithm more flexibility to adjust course later on, while still making meaningful progress toward a complete solution. Conversely, large ag values (c.g., ag > 0.3) result in overly aggressive expansions that risk committing to noisy or premature completions, leading to reduced accuracy and inefficient use of sampling budget.
Therefore, the optimal range of ag reflects balance between exploration and commit- ment proposing candidate steps that are informative enough to guide search, yet cautious enough to preserve the ability refine future decisions. This ablation confirms that adaptive decomposition benefits from conservative, incremental prefix extension when navigating complex reasoning or program synthesis tasks.
C.5 Reward Distribution
Distribution of rewards for 100 samples
Frequency
15
5
0.05
0.06
Reward value
Figure 27: Reward distribution for 100 samples on given MATH500 problem. The rewards appear to be roughly normal shaped.
26

---

A key assumption in our algorithm is that the distribution of rewards for sampled completions from a given prefix follows location-scaal scale family, such as the Gaussian distribution. This assumption enables the use of 7-scores to estimate the relative quality of candidate prefixes and to guide step acceptance. As shown in Figure 27 the empirical reward distribution for 100 samples on a rep- resentative MATH500 problem appears approximately Gaussian, with a unimodal and symmetric shape. While we do not assume exact normality, this empirical observation supports the use of z-score-based comparisons, the Gaussian approximation provides a reliable proxy for estimating tail probabilities and potential for reward improvement. We observe similar patterns across other problems and benchmarks, further validating this modeling choice.
27

---

D Main Results Extended
D.I APPS
Frequency of sampling different steps
Average sampling frequency
0.4
TokenSplit
LineSplit
0.3
0.2
0.0
12
Step number
Figure 28: Sampling frequency of each step averaged over the problems on APPS with gpt-4o- mini. DISC seems to have slight preferences for spending more compute on earlier found steps.
Frequency of (actual) partitons
Frequency of (planned) partitons
DISC
DISC
Partition frequency
0.5
TakenSpiit LineSplit
Partition frequency
TokenSpli
LineSplit
0.4
0.3
0.2
0.1
0.0
10
24
10a
101
102
10
Number of partitions
Number of partitions
Figure 29: Comparison actual and planned partitions on APPS. DISC outperforms other methods with fewer partitions by efficiently identifying critical steps. Unlike token and line split methods, which plan many partitions but search only subset, DISC dynamically adjusts partitioning based on budget.
We provide extended analysis of DISC 's behavior on the APPS benchmark using gpt-4o-mini. Figure 2 exhibits slight preference for allocating more sampling budget carlier-discoverer steps. This behavior reflects the intuition that early steps in a solution often set the structure for later reasoning, and refining these foundational steps yields more downstream improvements.
2 shows the average sampling frequency per step across all problems. Interestingly. DISC
Figure 29 compares the number of actual partitions (i.e., accepted and committed steps) with the number of planned partitions (i.c., proposed candidate splits) across decomposition methods. Token- level and line-based methods typically predefine many steps but only explore a subset due to budget constraints, leading inefficient allocation. In contrast, DISC adaptively proposes and accepts partitions in real time based on sample statistics and reward feedback, resulting in significantly fewer actual partitions while maintaining exceeding performance. This efficiency demonstrates DISC ability to identify and focus on high-impact steps, avoiding wasted compute on unnecessary refinements and enabling stronger performance within the same sampling budget.
28

---

D.2 Additional Examples
Below is another computed decomposition for the same problem as the one shown in the main text:
DISC example decomposition (Lagrange method)
Let be the length and y be the width of the rectangle. Since the perimeter is 24 inches, we have 2x + 2y = 24 + + y = 12. Therefore, we must maximize the area zy subject to this constraint. [ We use the method of Lagrange multipliers. The Lagrangian is
((x, y, A) = zy - A(x + y 12).
We differentiate with respect v, y, and obtain
0C
Uc
0C
y A 0,
X 0,
+ y 12 0.
Ox
Dy
0x
We find that y >. so x = y is 6 6 = 36
12 6. Therefore, the maximum area of the rectangle
2
DISC again highlights how initial constraint formulation is of medium importance providing essential structure but not representing a reasoning fork. The token "Therefore," " marked as high-importance, capturing a critical conceptual transition from constraint setup the optimization approach. Notably, the bulk of the mathematical machinery involving partial derivatives and substitu- tions receives low importance, consistent with the idea that such computations are largely mechanical once the decision to use Lagrange multipliers is made. Interestingly, the final step involving the boxed answer is also marked low, suggesting DISC allocates minimal compute here once earlier reasoning is coctled-unddescoriigg the idea that key inference pivots lie upstream in the decision flow.
D.3 APPS with Self-generated Validation Tests
We examine DISC performance APPS when using self-generated validation tests. All methods utilized the same set of self-generated validation tests to ensure fair comparisons. Each problem received 5-10 validation tests, with the exact number determined dynamically by the LLM. We evaluated a subset of 100 APPS problems, generating samples until the sample budget was exhausted found.
correct solution
Figure ilusttrtes the Pass@ sealing curve, showing that DISC maintains strong scaling performance in this setting, though at a slightly lower rate compared ground-truth verification.
Figure 32 and Figure 33 compare actual and planned partition frequencies, respectively. The results indicate that DISC continues to make structured decompositions even with self-generate validation, preserving its efficiency.
The mean reward per step, shown in Figure 34 follows a similar trend as in previous experiments, reinforcing that DISC effectively allocates compute resources for iterative refinement.
Lastly, Figure 35 demonstrates that DISC maintains lower standard deviations in performance, indicating stable quality improvements across steps.
29

---

Scaling curves by number of samples
Scaling curves by output takens
Propartion correct (Parsigtoken)
Proportion (Pass88k)
0.50
0.525
0.500
0.45
0.475
0.450
DISC
DISC
0.35
LineSplit
0.425
LineSplit
0.30
BoN
TokenSplit
0.400
BoN
Teken
0.375
3000
Number of solutions generated (k]
Number of output tokens used (tokens)
Figure 30: Pass@k on APPS with gpt-4o-mini using self-generated validation tests.
Figure 31: Token level comparison of different decomposition methods on APPS with gpt- 4o-mini and self-generated validation tests. DISC still scales better than other methods in this setting, albeit at lower rate.
Frequency of (actual) partitons
Frequency of (planned) partitons
0.5
DISC
DISC
Partition frequency
0.4
Line5pi
Split
Partition frequency
0.4
TokenSplit
LineSplit
0.3
0.3
0.2
0.1
0.0
12
10a
10a
10a
Number of partitions
Number of partitions
Figure 32: Actual partition frequency of differ- ent decomposition methods on APPS with gpt- 4o-mini and self-generated validation tests.
Figure 33: Planned partition frequency of different decomposition methods on APPS with gpt-4o-mini and self-generated valida- tion tests.
Mean reward per step
Standard deviation of rewards per step
0.14
Mean reward
0.12
Reward std
0.60
0.10
0.55
0.50
DISC LineSpiit
0.06
DISC
LineSplit
0.45
TokenSpiit
0.04
TokenSplit
10
12
14
1.0
12
14
Step number
Step number
Figure 34: Mean reward per step of different decomposition methods APPS with gpt-4o- mini and self-generated validation tests.
Figure 35: Mean standard deviation different decomposition methods APPS with gpt-4o- mini and self-generated validation tests.
30

---

D.4 MATH500
Completions for MATH500 include both the reasoning steps and the final answer. Since MATH500 contains problems than APPS200 and MATH problems tend to be relatively easier, solution quality saturates quickly. Therefore, we use a lower sample budget 10 for these experiments.
Figure pojpreeents the Pass@k performance for different decomposition methods on MATH500. We observe that all decomposition- approaches achieve similar Pass@k performance, consistently outperforming BoN. This indicates that the structured nature of MATH problems allows multiple decomposition strategies to be effective.
Despite similar @ass@k results, the true advantage of DISC lies in its token efficiency, shown Figure 5 DISC significantly reduces the number of tokens required reach correct solutions compared to alternative methods, demonstrating its ability to allocate computational effort efficiently mathematical reasoning tasks.
Additionally, we analyze the partitioning behavior of DISC on MATH500. Figure 37 illustrates the actual partition frequency for different decomposition methods. The planned partitioning behavior, shown in Figure 38, further highlights how DISC effectively balances exploration and refinement.
Finally, we present the mean standard deviation per step in Figure 39 Lower variance suggests that DISC produces more stable and reliable decompositions over multiple runs, reinforcing its robustness in both mathematical and program synthesis domains.
Pass@k scaling curves on MATH
Frequency of (actual) partitons
0.86
DISC
0.8
TakenSplit
Partition frequency
Taken Split
0.84
LineSplit
LineSpiit
BoN
0.82
0.4
Proportion
0.80
0.2
0.78
2
10
Number of solutions generated (k)
Number partitions
Figure 36: Pass@k performance compari- son for different decomposition methods on MATH500. DISC consistently outperforms BoN across different sampling budgets.
Figure 37: Observed partition frequency of dif- ferent decomposition methods on MATH500. DISC effectively segments problems into mean- ingful subcomponents.
Frequency of (planned) partitons
Standard deviation of rewards per step
0.06
DISC
Partition frequency
TokenSpilt
TakenSpilt
LineSpli
0.10
LineSplit
0.04
Reward sld
0.08
0.06
0.02
0.04
0.00
0.00
10a
10a
10a
2.5
4.0
4.5
Number of partitions
Step number
Figure 38: Planned partitioning strategy of dif- ferent decomposition methods MATH5000. DISC structured approach leads to more effi- cient problem breakdowns.
Figure 39: Mean standard deviation per
step for different decomposition methods MATH500, Lower variance in DISC suggests more stable and reliable problem-solvin steps.
31

---

D.5 LiveCodeBench
We evaluate DISC on LiveCodeBench, benchmark designed for code generation tasks with a focus on real-world software development challenges. LiveCodeBench presents unique set of problems requiring both reasoning and structured decomposition, making suitable testbed for evaluating DISC's ability to refine and improve intermediate steps.
Figure 40 shows the Pass @ comparison of different decomposition methods LiveCodeBench DISC consistently scales better than other decomposition methods, highlighting its ability to refine intermediate steps more effectively complex coding scenarios.
Figure 4 illlstrrates the observed partition frequency of different decomposition methods. The struc- tured approach of DISC results in well-balanced decomposition across steps, reducing unnecessary partitioning while maintaining sufficient granularity for improved solution refinement.
Figure 42 displays the planned partition frequency across methods. DISC dynamically determines the most effective partitions based on the evolving problem state, leading to more targeted and efficient decompositions.
Finally, 43 presents the mean standard deviation per step across decomposition methods. Lower variance in DISC suggests that it produces more stable and reliable decompositions, reinforcing its robustness for solving LiveCodeBench problems.
Frequency of (actual) partitons
Pass@k scaling curves LiveCodeBench
DISC
(Pargg))
Partition frequency
Token
0.45
0.40
0.35
0.2
BoN
0.25
TokenSplit UneSplit
0.0
0.20
5
10
15
20
25
30
generated
Number partitions
Figure 40: @ass@k performance comparison different decomposition methods on Live- CodeBench. DISC consistently outperforms other methods in structured problem refinement.
Figure 41: Observed partition frequency of different decomposition methods on Live- CodeBench. DISC effectively balances prob- lem segmentation while avoiding excessive par- titioning.
Frequency of (planned) partitons
Standard deviation of rewards per step
0.8
DISC
0.30
Partition frequency
TokenSplit
0.6
LineSpii
0.25
Reward std
0.20
0.4
0.2
0.05
TokenSplit
0.0
0.00
Lineppitt
10a
10a
10a
10a
10.0
12.5
Number of partitions
Step number
Figure 42: Planned partitioning strategy of different decomposition methods on Live- CodeBench. DISC dynamically adapts its parti- tioning optimize search efficiency.
Figure 43: Mean standard deviation per step for different decomposition methods Live- CodeBench. Lower variance in DISC suggests more stable and reliable problem-sol solving steps.
32

---

D.6 Computational Overhead
We analyze the computational overhead of DISC by measuring the runtime breakdown between actual LLM token generation and all auxiliary operations (e.g.. Z-score computation, candidate prefix management, and recursive decomposition logic). Since token generation is the dominant cost LLM inference, reporting relative percentages of runtime-raie a more meaningful and consistent comparison. Absolute runtime can vary significantly across hardware configurations, backend optimizations, or batching strategies, whereas percentage-based measurements isolate algorithmic overhead from infrastructure-deeendee variance.
than absolute wall-clock time-offie
As shown in Figure 7 the proportion of runtime DISC spends on LLM token generation versus auxiliary logic closely matches that baseline methods such as BoN and LineSplit. This indicates that DISC introduces negligible additional overhead despite its dynamic behavior and internal scoring computations. practice, more than 90% of total runtime is still dominated by LLM token sampling across all methods.
Furthermore, because DISC achieves better performance with fewer tokens (i.e., improved token efficiency), its effective runtime per successful solution is actually lower than that of less efficient baselines. This combination-minite highly practical method for real-world inference settings, where total compute cost is often tightly constrained.
added overhead and superior token scaling- makes DISC
33

---

E
Limitations
While DISC demonstrates strong empirical performance and generality across tasks and models, several limitations merit discussion.
Reliance on LLM-Generated Test Validation. Our evaluation framework employs self- generated test validation, where the LLM is prompted to produce its own unit tests for given code generation task, and these tests are used as a proxy reward model. This approach enables scalable evaluation in the absence of ground-truth test cases, but its effectiveness depends critically on the quality of the generated tests. particular:
The LLM's ability to produce meaningful and comprehensive tests directly impacts evalua- tion fidelity. Poor coverage or semantically shallow tests may overestimate correctness.
The framework assumes that most generated tests are correct and executable. For complex or underspecified tasks, this assumption may fail, leading to false positives or noisy reward signals.
Since generated tests may not align with reference solutions, cross-method comparison become inconsistent.
These issues are consistent with observations in prior work such as CodeT 30 which highlights tradeoffs between scalability and reliability in test-based self-evaluation.
Dependence on Reward Model Availability. DISC requires access scalar reward signal to guide step-wise decomposition. While tasks like code generation or math reasoning naturally provide verifiers (e.g., test cases or numerical checks), applying DISC to domains lacking explicit reward signals necessitates constructing auxiliary reward models or LLM- M.M--asedd critics, which introduces additional complexity and potential bias.
Scope Limited to Single- Mingle-Turn Turn Generation. The current formulation of DISC is designed for single- pass generation tasks. It does not yet handle multi-tur -ur or interactive settings where intermediate reasoning steps can elicit feedback or modify the problem context. Extending DISC to such interactive regimes remains an important direction for future work.
Reduced Benefit in Trivial or Von-Compositionall Tasks. DISC allocates computational budget adaptively across reasoning steps. When a task trivially solvable or lacks compositional struc- ture-such that early reasoning does not meaningfully constrain the final outcome- the gains from decomposition and step-wise control diminish.
Despite these limitations, we believe that DISC provides a strong foundation for adaptive, reward- driven reasoning. Future extensions could integrate learned verifiers, support multi-turn interaction, and explore joint evvalluttnnv co-evolution.
34

---

Search and Scaling
F.1 DISC Plug-and-Play Search
Algorithm 3 DISC: Decomposition for Plug-and-Play Search
Require: LLM v, Reward model R, prompt æ, initial partition fraction og, negative binomial threshold o, total budget N, current budget n
1: function EXPANDNoDE<(paeen prefix Ps. parent 2,, suffix to child s,)
2:
a 0g
3:
while n N do
4:
P. - Pp; split((e,, a)
5:
Y. -MAKECHILDREND.)
6:
Ze = (max(Y.) - mean (s))/s)
7:
n M
8:
if 2e < then
9:
break
10:
else
+ aga
12: end if
end while
14:
return Per Y
15:
function MAKECHILDREN(pace) prefix pb)
16:
Y= ((p: 8", ((())) ~ T--(P,)]
17:
return Y
F.2 Monte Carlo Tree Search (MCTS)
Monte Carlo Tree Search (MCTS) is widely used algorithm for sequential decision maainng in large search spaces, particularly applications such as game playing. planning, and inference scaling. The algorithm builds search tree incrementally by simulating different sequences of actions and updating estimates state quality. key advantage of MCTS is ability to balance exploration (discovering new states) and exploitation (refining promising ones) using data-driven search process. The MCTS pipeline consists of four fundamental steps: selection, expansion, simulation, and backpropagation.
F.2.1 Selection
Starting from the root node representing the current state s. MCTS iteratively traverses the search tree by selecting child nodes based selection policy. The most commonly used selection criterion the Upper Confidence Bound for Trees (UCT), which balances exploration and exploitation:
In (E n(s n(ssd)
UCT(s, ((s,))))(sss)))))s)s)
(s. + +
where Q(s, d) represents the estimated value of selecting action d from state 8, nss d) is the visit count for this action, and e is hyperparameter controlling the trade-off between exploring new actions and favoring those with high past rewards.
F.2.2 Expansion
Once leaf node (a previously unexplored state) reached, the algorithm expands the tree by adding one more nodes. These new nodes represent potential future states s' generated by sampling an action from a predefined policy. This step broadens the search space and allows MCTS to evaluate new possibilities.
35

---

F.2.3 Simulation
Following expansion, the algorithm conducts a simulation (or rollout) from the newly added state. This step involves generating a sequence actions according to a predefined policy until reaching a terminal state or an evaluation horizon. The outcome of the simulation, denoted as v(s'), ), provides an estimate the quality of the new state. Depending on the application, this could represent a game result, optimization score, or inference accuracy metric.
F.2.4
Backpropagation
The final step involves propagating the results of the simulation back up the search tree to refine the estimated values of prior states and actions. Fach node along the trajectory {80, d1, 82,-..: updated iteratively:
(s., d(+1)
a, m do+1) Q(.+1 (++2)(+1)) (2)
where On, is learning rate that depends on the visit count, and the maximum function ensures that the best-performing trajectories are emphasized.
MCTS has been widely adopted in inference scaling techniques due to its ability to efficiently allocate computational resources, focusing more high-reward states while avoiding unnecessary exploration of unpromising regions. In later sections, we explore how MCTS can be combined with dynamic decomposition to further optimize inference scaling.
F.2.5
Combining Dynamic Decomposition with MCTS
MCTS can be enhanced by integrating dynamic decomposition, where each node in the search tree represents a decomposition of the problem into steps. Instead of treating states as atomic decisions, we recursively decompose reasoning steps, dynamically adjusting granularity based difficulty.
In this framework:
Each node in the MCTS tree represents partial decomposition of the problem, with child nodes corresponding to alternative step partitions.
Branching occurs by generating candidate next steps using dynamic decomposition, allowing finer steps for complex regions while maintaining efficiency for simpler ones.
The selection step prioritizes nodes that represent more promising decompositions, dynami- cally refining challenging areas through recursive subdivision.
The backpropagation step ensures that decompositions leading to high-qualit solutions
reinforced, helping the search tree converge toward optimal inference paths.
By integrating dynamic decomposition with MCTS, we efficiently allocate compute the most critical reasoning steps, improving inference quality while maintaining computational efficiency.
F33
Beam Search
Beam search is heuristic search algorithm commonly used in inference tasks where computational efficiency is a priority. Unlike exhaustive search methods, beam search maintains only the top best candidates at each step, making an effective strategy for structured prediction problems and sequential decision-making
At each iteration:
The algorithm selects the k most promising partitions from the previous step based on an evaluation metric.
Each selected partition is expanded by generating possible next-step samples.
The newly generated partitions ranked, and only the top k candidates retained for the next iteration.
This process continues until a stopping criterion is met, such as reaching predefined depth finding sufficiently high-quality solution.
36

---

Beam search provides a computationally efficient way to explore structured solution spaces while maintaining high-quality search trajectories. By integrating beam search with dynamic decomposition. we ensure that inference computation is allocated efficiently, focusing on the most promising reasoning paths at each step.
F.4
Additional Results and Analysis
Pass@k for different search methods
Pass@token different search methods
Prspartion correct (Pacs@tolon))
0.550
0.50
0.525
0.45
0.500
0.475
0.40
0.450
0.35
DisC+Greedy
0.425
DISC+Greedy DISC-MCTS
0.30
DiSC+Beam
0.400
DIBC+MCTS
0.375
2500
10000 12500 15000 17500 Number of output tokens used (tokens)
5000
7500
Number of solutions generated (k)
Figure 44: Pass@k on APPS with gpt-4o-mini using different search methods. MCTS scales best, followed by greedy search, followed by beam search.
Figure 45: Token level comparison of differ- ent decomposition search methods combined with DISC on APPS with gpt-4o-mini. MCTS scales best, followed by greedy search, followed by beam search.
Frequency of (actual) partitons
Standard deviation of rewards per step
Partition frequency
0.6
0.7
DISC+Greedy DISC+Beam
0.15
DISC+Beam
DiSC+Grendy
DISC*MCTS
0.5
Reward std
0.10
0.4
0.3
0.05
0.2
0.1
0.00
0.0
10a
10a
2
4
10
12
14
16
Number partitions
Step number
Figure 46: Actual partition frequency of differ- ent decomposition search methods combined with DISC APPS with gpt-4o-mini. Greedy is able to search to higher depths given the same
Figure 47: Mean standard deviation of differ- ent decomposition search methods combined with DISC on APPS with gpt-4o-mini. All search methods display decreasing standard de- viation with search depth.
sampling budget.
Experiments comparing different search methods were conducted on 100-problem subset of the APPS dataset (first 100 problems) using GPT-4o-mini. All methods used a temperature of 0.2, with 0.15, Q priority metric, and a 1.0.
Token-level comparison: As shown in Figure 45 MCTS scales best among the tested methods,
demonstrating superior efficiency in identifying promising partitions. Greedy search follows closely, while beam search exhibits the slowest scaling.
Partition frequency analysis: Figure reveals that greedy search explores to greater depths within the same sampling budget. This suggests that greedy search prioritizes deep refinements, whereas MCTS and beam search balance depth with breadth.
37

---

Step variance analysis: Figure 47 illustrates that all search methods display decreasing standard deviation with increasing search depth. This trend indicates that deeper searches converge towards stable, high-quality partitions, reinforcing the benefits of dynamic decomposition.
These results highlight the trade-offs between search methods: MCTS offers robust exploration- exploitation balance, greedy search favors depth-first refinement, and beam search provides a struc- tured yet computationally constrained approach. The integration of dynamic decomposition further enhances these search strategies by adaptively allocating computational resources to critical reasoning steps.
38

---

G Theoretical analysis
G.1 Main Theorem
We begin by introducing notation to characterize the distribution of rewards obtained when sampling completions from given prefix
Let Rp denote the random variable of the reward of completion sampled from the LLM policy conditioned on prefix p:
Rp = R(p 8), where ~ (()1p).
Let P. Mp. and op be the cumulative distribution function (CDF), mean, and standard deviation of Rp, respectively.
We define a solution y as correct if it achieves a reward of at least r" 1, i.e., R(y") 2 1. Then, the probability that random sample from T(- p) yields correct solution is given by:
P 2 1] Fp()).
For given set of M independent samples from .|- p), let max denote the maximum observed reward among them, i.e., the sample maximum.
We make the following problem assumption:
Assumption A correct solution exists in the support of the policy xty" >> 0 and the length of the correct solution finite: ly'l = K co.
We make the following assumptions about the policy m:
Assumption We assume Rp belongs to location-scale family with base CDF FR.
Remark 2 The location-scale family includes common distributions such the Normal, Cauchy, and Logistic distributions. which are characterized by being affine transformations of a fixed base distribution. Specifically, random variable X belongs to a location-scale family if it can be written as = p + a Z, where Z Fn is standardized random variable, and μ E IR. and a >> O are the location and scale parameters, respectively. We observe empirical evidence supporting this modeling choice for Rp in Appendix C.3
Assumption 3 (Reward distribution converges with prefix) Consider some base prefix b and some candidate prefix is complete solution (it ends in EOS token) then 0.
x for any token sequence æ. Then, ae ab. Furthermore, if
This assumption reflects the intuition that as more tokens are appended to a prefix, the LLM becomes increasingly committed to a narrower set of likely continuations, leading to lower uncertainty in the reward distribution. In the limit, once complete solution is formed (i.e.. the sequence ends with an EOS token), the reward becomes deterministic. and the variance collapses to zero.
Remark
We emphasize that this assumption is not required for proving the optimality of DISC. However, the greater the difference between de Tb. the faster the convergence, as DISC will be able prune suboptimal paths more confidently with fewer samples.
Assumption 4 (Reward distribution converges slowly) If Algorith) 7 c over a base prefix b, then we assume the standard deviation of the reward distribution under c is a lower bounded:
Jaccepts candidate prefix
11 1
dor
2
where -=-"-pph -- max the optimality gap between the true maximun reward r" and the current -max best sample under prefix b, and mea--pa man -pe- is the z-score drop, which quantifies the change in how surprising the best sample is under each distribution.
do
de
39

---

Remark 4 This assumption enforces that if we transition from base prefix b to candidate prefix c, the standard deviation (spread) of the reward distribution under с cannot shrink too drasti- cally-especially when: (i) we are still far from the optimal reward (i.e., A is large), and (üi) the improvement in sample quality is not significant (i.e., 8 is small). Intuitively, this prevents committing to a sharp but unreliable prefix unless there is strong evidence of progress. If c. does not yield sufficiently better samples or has low variance, may hinder further exploration. This assumption ensures that accepted prefixes preserve enough reward diversity to support continued search.
While we list the confidence property Assumption f as an assumption, it can also be enforced directly as explicit acceptance criterion in Algorithm 7 Specifically, the algorithm could be modified to accept a candidate prefix over base b only if both 5 2 0 and: (1 (1- 6de where A can computed becuuse
Remark 5
(1- Tb S Te.
Combining Assumptions 3 and we can write: with exploitation.
du dn
[[1 50x) .]. This balances exploration
Assumption 5 (Accurate estimates of Up and op) ) We assume that we sample Rp enough times to get accurate estimates of the true mean Ui R Up and standard deviation 6n R Tp. Because estimates of mean and standard deviation are accurate, the estimates of the 2-scores are also accurate.
Next we prove that Alg. D will never commit candidate prefix that with a lower probability of sampling a correct solution than the base.
Lemma Consider Algorithm 7 applied to a base prefix and a candidate prefix e, with corre- sponding reward distributions Fb and F Then, the probability of sampling correct suffix from π does not decrease after accepting e:
7t8" (b) S 1 (c).
Proof 1 A candidate prefix is accepted by Algorithm [ if either of the two conditions are true: (i) the standardized score (z-score) of e lower than that of b: ze < Eb or (ii) the first a fraction of tokens in the best suffix contains tokens, and the prefix is accepted by default. In case (ûi): if is the empty prefix, then c = b, and the distributions are unchanged. so the result follows trivially.
It remains to show case (i): if ze < 24 then, T(s" |)) (c)2m00 x(s"
b).
First, define the z-score change 8 > 0 as as
re - and the optimality gap A 0 de
de Then, note that our algorithmic implementation initializes the set of candidate samples with the best solution, i.e. mY,(Y))) E Y.. Therefore, we have that the sample max of the candidate rewards is greater than or equal that of the base: rmax 2 bb
Using this information, we can rewrite the z-score inequality:
1bb
r" -M Hice
(6- ac
20
Gc
where we first plug in the definitions of 5 and A, do algebraic manipulation, and then apply assumption 4 The final inequality implies Fe(r*) < Fo(r"), which implies π rss" c) > 7(s" b)
because P Rp (p2rr== ==1==1- 1 Fp(r*) and Fp is monotonic in z score.
Theorem 2 (Optimality of DISC) Consider Algorithm aaplied problem input and assume
Assumptions 1, 2, 4, and 5 hold. Then, with probability 1, there exists finite number of accepted prefixes k > and algorithm iterations > such that the algorithm terminates, and the best solution y found is a correct solution: R(yr) 1
Proof We define the base prefix by as the result of appending k accepted candidate prefixes. We now proceed with the induction.
We first prove by induction that the probability of sampling a correct suffix remains strictly positive after each accepted prefix.
Base Case (k = 0): Initially, bo x. By assumption, there exists at least one correct solution
y" x 8* such that a( x)) > and R(y") 2 1. Hence, there is a non-zero probability of sampling correct suffix from bu.
40

---

Inductive Step: Assume that after lo accepted prefixes, the base prefix by satisfies:
(
b&) >
0 and R(by 8*) 21
for some correct suffix s*. Let b by c be the base prefix after appending the (k+1))-t accepted candidate prefix c. By Lemma
| the probability of sampling correct suffix does not decrease:
TTs" (k+1) 2 x(s"
by) O.
Therefore, every accepted prefix dy. the probability of sampling a correct suffix remains bounded below by some & > O, where 2 xly" x)).
Termination:
Let Mg be the number of samples from accepted candidate prefix by. Since sample from the accepted candidate prefix by least once (Mx. 2 1), samples are independent, and the
probability of sampling correct suffix is at least xly" x:) > 0, the probability of not sampling correct solution after accepting lo prefixes is at most
(1 1-=x(y" ()))
Hence, the probability of never sampling correct solution after infinittly many accepted prefixes is
lim (1 - Tyy" x))) =0 k
which implies that, with probability 1, the algorithm will eventually sample correct suffix.
Furthermore, this implies that the number of accepted prefixes ls before obtaining correct solution is almost surely finite. This follows from the fact that the number of independent trials before the first success with fixed success probability p == xyy" " x)) > 0 is geometric random variable, which is finite with probability 1.
Therefore, there exists a finite number of accepted prefixes k such that the algorithm terminates and returns a correct solution y² satisfying R(y") 1.
Since the algorithm either accepts candidate prefix contracts it by factor (0, 1) until the prefix length is 0, there can only be finitely many contractions before the candidate prefix is rejected or accepted. Therefore the algorithm must accept a candidate prefix in finite number of iterations, and so the total number of algorithm iterations n. before finding a correct solution is also finite.
Remark Unlike Best-of-N (BoN), where the probability of sampling correct solution remains constant across samples, DISC dynamically refines the sampling distribution by appending infor- mative prefixes. As established in Lemma 7 the probability of generating correct solution under DISC non-decreasing across iterations. Consequently, DISC achieves faster convergence correct solution in expectation compared to BoN. This theoretical advantage is corroborated by our empirical results Figure 5 which show that DISC consistently outperforms BoN in terms of efficiency and scalability with respect to token budget.
G.2 A Motivating Example DISC
We use the Wiener process W (t) as an example where there are intractably many actions and steps. Suppose we start at = 0 with (00) 0. At each round the algorithm choose of the two options:
1. samples a trajectory and observe the final value W(T) at time f T, as the reward signal. Denote the whole trajectory as wx(-)
2. chooses one trajectory from the previous rounds (denoted (t( for round s), and time to: then sample a trajectory at to with W = w. w.(()). Denote the concatenated trajectory as wx()) with (t) (t) when to.
Note that we are only able to observe the final reward W(t). At any intermediate time E (0. T). the current value W(t) is not observable. The goal is to design an algorithm that can reach the highest reward among the K trajectories. Formally speaking, we aim to maximize the maximum:
max wy (T).
41

---

One naive solution is to call option 1 for K times and return the best-of- K reward, each following:
W(T) ~ (),
Alternatively, suppose there is promising path w(-) with high final reward w(T) R. It natural to consider starting at some midpoint o? (0 < a < 1) and perform more completions to obtain an higher reward than R. The reward distribution sampled this way is
(T) ~ (ww(aT)), a))).
The remaining question is which a we should choose. One option is to maximize the probability that the newly sampled reward is higher than R:
R w(aT)
(TW R) =1
(11 a)
42

---

H
Compute Resources Used
All evaluations involving OpenAI proprictary models (e.g., GPT-4o-mini, GPT-3.5) were performed via the OpenAI API. These API calls were made from standard desktop machines using CPU-only inference and incur no dependency on local GPU availability, making the method broadly accessible for replication.
For open-source model experiments (e.g.. LLaMA-3.1-B--Inttnee Mistral, Qwen), inference was conducted on a single NVIDIA A100 GPU. All such experiments were executed sequentially on this GPU, which has 80GB of memory, ensuring consistent and reproducible runtime characteristics across model families.
This setup reflects the lightweight computational overhead of our method and demonstrates that DISC can scale effectively even in constrained or CPU-only environments when using hosted APIs.
Impact Statement
Positive Societal Impacts This work introduces a general and lightweight Seathod-Dnamic Decomposition (DIsC)-that significantly improves inference efficiency for large language models (LLMs) without requiring additional training, domain-specific engineering, or specialized hardware. By enabling better performance using fewer samples and tokens, DISC reduces the cost and envi- ronmental footprint associated with LLM deployment, making advanced reasoning models more accessible to research groups and developers with limited compute budgets.
Additionally, DISC's ability prioritize critical reasoning steps has the potential improve the transparency and interpretability of L.M outputs, which is beneficial in high-stakes applications such as education, scientific reasoning, and assistive tools for programming mathematics. Its plug-and-play compatibility with open-source models also democratizes access to high-performance inference techniques.
Negative Societal Impacts As with all improvements in LLM inference capabilities, this work may accelerate the deployment of models in settings where societal risks are not fully mitigated-suul as the automated generation of persuasive misinformation, cheating in educational contexts, or manipulation via high-fidelity language generation. Furthermore, by making LLM inference more efficient, DISC could contribute to increased usage of models without corresponding increases in ethical oversight or alignment safeguards.
Careful integration of this method should therefore include responsible use policies, limitations on deployment domains, and alignment with values such transparency, faireess, and accountability.
43

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately reflect the paper's contributions and scope. The paper introduces novel framework for decomposing behavior in sequential Docision-makinng using value-based segmentation, proposes an instantiation via a modified value iteration algorithm, and demonstrates empirical results across diverse domains includ- ing control, navigation, and language modeling. These contributions are clearly outlined in both the abstract and introduction and are elaborated upon in Sections 2 (Framework), (Method), and 4 (Experiments).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals not attained by the paper.
44

---

2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations are discussed in Section 3.1, where the authors acknowledge that the value-based decomposition relies on having access to a value function, which may not always be readily available accurate in real-world settings. They also note that while the method is general, its effectiveness can depend on the specific domain and value structure. These points transparently address the boundaries of the current approach.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper presents a clear set of theoretical results in Section 3, supported by assumptions which are stated explicitly. Lemma 1 and Theorem build directly on these assumptions and are accompanied by informal but complete proofs that are consistent with the problem setting. The paper also explicitly states the limitations of its theoretical analysis, acknowledging that some assumptions are empirically motivated rather than rigorously provable, which is standard in empirical LLM research. The justification is sufficient and appropriate for a NeurIPS submission. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
45

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
The paper provides detailed descriptions of the experimental setup, in- cluding datasets (APPS, MATH500, and LiveCodeBench), evaluation metrics (pass@k pass mass@token), model configurations (e.g.. LLLMA-3.1----Immmtte temperature (T = 0.2), and DISC hyperparameters (e.g., to 0.15, 0 = 1.0). The algorithm is specified in pseudocode (Alg- and 2), and ablation studies conducted to analyze sensitivity to temperature, acceptance criteria, and partition fraction. While code is not included in the paper, the level of detail is sufficient reimplement the approach and verify the core findings.
Justification:
GPT-4o-mini), sampling
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel urchitecture, describing the architecture fully specific model and empirical evaluation, may
might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
46

---

reproducible, they Justification: The code and data are not yet publicly available at submission time due to anonymity constraints. However, we commit to releasing the full popplementationnnncllee scripts for running DISC, benchmark evaluation, and reproduction of all figures and ta- bles-upon publication. The code will be made available on GitHub with comprehensive instructions to ensure faithful reproduction of results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. ctcips.cc/publcc/uuutc httpp///iiiiciiico/////eeebbibii ponoddeSumisssoooPo.e
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e-g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper clearly specifies test set sizes and evaluation protocols for each benchmark: a 200-problem subset APPS, the MATH500 subset of MATH, and 108 LiveCodeBench problems from specified date range to avoid contamination. It also details hyperparameters for DISC (e.g.. how these were selected via ablation studies. Since the work focuses on inference rather than training, training details such as optimizers are not applicable. Pretrained models (e.g.. LLaMA-3.1 (B-Inssruct) are used directly without further fine-tuning.
0.15, 0 = 1.0, temperature
0.2), and discusses
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
The paper follows standard field practice by providing statistical variation where appropriate. These conventions are consistent with accepted norms in the LLM inference scaling literature.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
47

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The paper includes dedicated section in the appendix detailing the compute resources used. Evaluations involving OpenAl proprietary models (e.g., GPT-4o-mini, GPT-3.5) were conducted via the OpenAl API from standard desktop machines with CPU- only inference. For open-source models such as LLaMA-3.1 1---..1-8--11 I-8B-Instr Mistral, and Qwen, inference was run on single NVIDIA A100 GPU with 80GB of memory. This setup demonstrates that DISC is lightweight and can be reproduced under modest compute conditions. The disclosure is sufficient to support replication of experimental results.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://eerripppccccuiceeeeeeeeee
Answer: [Yes]
Justification: The paper adheres to the NeurIPS Code of Ethics by utilizing publicly available datasets (APPS, MATH500, LiveCodeBench) that do not contain personally identifiable information, thereby respecting privacy and consent considerations. The research does not involve human subjects, surveillance, or any form of deceptive practices. The proposed DISC method aims enhance the efficiency of large language model inference, potentially reducing computational resources and associated environmental impact. The paper also includes discussions on limitations and potential biases, aligning with the ethical standards outlined by NeurIPS.
Guidelines:
48

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The paper includes dedicated Impact Statement in the appendix that dis- cusses both positive and negative socictal impacts. On the positive side, DISC improves inference efficiency for LLMSs without additional training hardware, lowering costs and environmental impact while enhancing accessibility. also promotes interpretability and aligns well with open-source use cases. On the negative side, the paper acknowledges that increased efficiency could accelerate deployment of LLMs in settings with insufficient ethical oversight, potentially contributing misuse such as misinformation academic dishonesty. These trade-offs are explicitly addressed in alignment with responsible AI practices.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release any new pretrained models, image generators, or scraped datasets that would pose high risk of misuse. The work builds upon existing, publicly available models and datasets, and focuses solely on inference-time methods. Therefore, this question is not applicable.
Guidelines:
The answer NA means that the paper poses such risks.
49

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper publicly available datasets (APPS, MATH, LiveCodeBench) and models (c.g., GPT-4o-mini via OpenAI API, LLaMA-3.1-8B --S--t-rtt,, Instruct, Mistral, Qwen) and appropriately cites their original sources. These assets were used in accordance with their respective licenses and terms of use. The paper does not redistribute any of these assets and respects the usage guidelines set by their creators.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
The paper does not introduce new assets such as datasets, pretrained models, novel codebases at submission time. The proposed method, DISC, is described in detail in the paper and appendix, and the authors commit to releasing the code with full documentation upon publication.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
50

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
The research does not involve any crowdsourcing experiments or human subjects. All results derived from automated evaluation of LLM-generated outputs using standard benchmarks and computational metrics.
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The study does not involve human participants or any form of user study. Therefore, there were no risks to disclose, and IRB approval was not required.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMS if it is an important, original, or non-standard component of the core methods in this research?
Answer: [Yes]
Justification: The paper centrally focuses improving inference-time performance for LLMs through a novel method called Dynamic Decomposition (DISC). It clearly describes how L.MSs are used in both the methodology and experiments, including the of autore- gressive LLMs like GPT-4o-mini and LLAMA-3.1-44 1.3.1-8BB-nnttuue DISC interacts with these models by dynamically querying continuations from intermediate prefixes, making the LLM usage both critical and fully documented throughout the paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non sta-standard components.
Please refer to our LLM policy for what should or should not be described.
51


Reviews:
[{"review_id": "d2Tpu270CP", "reviewer": "Reviewer_WYfN", "summary": "The paper introduces DISC, a dynamic decomposition approach to inference in large language models that adaptively introduces partitions among the solution steps to reflect the estimated difficulty of the solution, instead of using a fixed and hand-designed set of solution steps or uniform steps. The recursive reward-based process used by DISC decides to dedicate more compute to difficult reasoning steps and less to easy ones and fits naturally with standard search algorithms (greedy, beam, MCTS). On various benchmarks of code generation and mathematical reasoning (APPS, MATH, LiveCodeBench), DISC achieves on average large improvements in inference efficiency and correctness compared to static decomposition baseline results.", "questions": "Could the authors clarify the 3 points raised in the Weaknesses section?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-motivated and tackles a meaningful problem in LLM reasoning\n2. Extensive experiments on multiple benchmarks with strong improvements \n3. Ablation studies are thorough \n\nWeaknesses:\n1. The theoretical results are built on strong assumptions that may not necessarily hold in practice. Moreover, insights that DISC will eventually find the optimal solution as the search budget increases are fairly straightforward and hold for any flexible search algorithm. \n2. The z-score acceptance criterion needs further justification\n3. The paper lacks analyses of any failure modes or empirical limitations of DISC", "was_revised": true, "final_justification": "I lean towards acceptance of the paper. The authors provided sufficient responses to all concerns that I raised.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. As NeurIPS does not permit the inclusion of PDFs or anonymous external links in the rebuttal this year, we apologize in advance that we are unable to provide annotated figures or visual clarifications. We have done our best to clearly describe figure content and visual changes. We hope our written explanations are sufficiently clear, and we are happy to incorporate any additional clarifications into the camera-ready version if the paper is accepted.\n\n> The theoretical results are built on strong assumptions that may not necessarily hold in practice. Moreover, insights that DISC will eventually find the optimal solution as the search budget increases are fairly straightforward and hold for any flexible search algorithm.\nGot it—here’s another take that brings the “DISC *provably* converges faster than BoN” claim forward, tucking it right after we state the goal of the analysis (so readers see the practical payoff before diving into the technical assumptions). Everything else is left essentially intact.\n\nWe agree that our theoretical results rely on strong assumptions, and verifying their validity in practice is problem-specific—a nuance we explicitly discuss in the paper \\[Section C.5, Supplementary material and line 159]. Problem-specific verification is a necessity in any analysis of large models. Our analysis seeks to identify the *minimal* conditions under which real-time inference with adaptive decomposition remains viable. **Crucially, it also shows that DISC *provably* converges faster than BoN—the most widely adopted inference scaling method—demonstrating tangible gains from dynamic decomposition even in compute-limited settings.** In particular, the analysis motivates Assumption 4 (Reward distribution converges slowly), which was included in the **updated Appendix as part of the Supplementary Materials submission**. This assumption is both natural and practical: it posits that if the candidate prefix does not significantly improve sample quality, then the reward distribution must remain sufficiently broad to avoid prematurely collapsing exploration. In other words, the algorithm should not commit to a sharp but unreliable prefix unless there is strong evidence of progress. This condition aligns with how LLMs behave in practice—early prefixes often exhibit noisy or uncertain completions, and overly narrow sampling can stunt further search. Assumption 4 effectively encodes a safeguard against overconfident commitment and can even be implemented as an **explicit acceptance criterion**, as described in Appendix F.3: a candidate prefix could be accepted only if both the reward improvement is significant *and* the distributional variance has not collapsed. Although we do not enforce this explicitly in Algorithm 1 for simplicity, doing so would only strengthen DISC’s robustness guarantees.\n\nMoreover, DISC’s convergence is categorically different from that of conventional search algorithms because DISC is not, in itself, a search policy—it is a *representation refinement process*. Rather than deciding *which* branches to explore (as in classical search), DISC determines *how far* to extend the current branch before committing to further sampling, with any sampling strategy one wishes. This design enables DISC to defer commitment until confidence is higher, which in turn reduces the likelihood of prematurely discarding high-reward completions—an issue that plagues greedy and beam search under static decomposition.\n\nImportantly, many commonly used inference strategies—such as greedy search and beam search—**do not guarantee convergence** to the optimal solution when paired with static decomposition. For instance, both can prematurely commit to suboptimal prefixes under static decomposition, irreversibly pruning paths that would have led to higher-reward completions. DISC avoids this pitfall by dynamically refining step sizes based on rollout statistics, allowing it to course-correct and focus compute on promising regions. Our theoretical analysis helps formalize this behavior and provides a conceptual explanation for DISC’s observed monotonic improvement (Sec. 3.3). Furthermore, we empirically validate key assumptions used in our analysis, such as the location-scale nature of reward distributions (App. C.5), reinforcing the practical relevance of our framework.\n\n> The z-score acceptance criterion needs further justification\n\nThank you for raising this important point. The choice of z-score as the acceptance criterion is theoretically motivated and empirically validated in our work.\n\nFrom a theoretical standpoint, the z-score quantifies the standardized distance between the maximum reward of a candidate prefix and the mean of its sampled rewards, normalized by their standard deviation. Under the common assumption that rollout rewards approximately follow a location-scale family distribution (e.g., Gaussian or sub-Gaussian)—a property we verify empirically in Appendix C.5—this z-score allows us to estimate the probability that further sampling from a prefix will yield a better solution. Thus, minimizing the z-score corresponds to prioritizing prefixes with a higher estimated probability of improvement.\n\nThis criterion is central to our optimality guarantee (Theorem 1 in Section 3.3), which ensures that DISC converges to an optimal solution at least as efficiently as non-decomposed sampling strategies (e.g., BoN), provided that the LLM policy assigns nonzero probability to the optimal completion. The proof relies on Lemma 1 in the supplementary material (Appendix F), which shows that accepting a candidate prefix only when its z-score is lower than that of the base ensures that the probability of sampling the optimal suffix does not decrease. In other words, each accepted prefix refinement either maintains or improves the likelihood of discovering an optimal solution. This monotonicity is key to establishing that the search will not prematurely exclude optimal completions and will eventually reach them given sufficient budget. Without such a decision rule, the algorithm could regress into lower-probability regions of the search space and fail to converge.\n\nEmpirically, we further justify this choice through an ablation study (Figure 8, middle), where we compare DISC-Z (our method) to several alternatives such as accepting based on raw mean reward (DISC-Q), random acceptance (DISC-R), and even reversed z-score (DISC-negZ). Among these, DISC-Z performs best, while DISC-negZ underperforms even random selection—underscoring the importance of z-score for effective decomposition.\n\n\n\n\n> The paper lacks analyses of any failure modes or empirical limitations of DISC\n\nWe thank the reviewer for the valuable suggestion. In response, we propose the following limitations section to add to the revised manuscript. While DISC demonstrates strong empirical performance and generality across tasks and models, we acknowledge several limitations:\n\n1. **Dependency on Reward Model Availability**: DISC requires access to a scalar reward model to guide step-wise decomposition. While many tasks such as code generation and math reasoning provide natural verifiers (e.g., test cases or numerical checks), applying DISC in tasks lacking clear outcome signals may require additional engineering, such as constructing LLM-based critics or learned heuristics.\n\n2. **Most Effective for Single-Turn Generation**: Our current formulation assumes a single-turn generation setting, where a full solution is produced in a single pass. DISC does not directly account for multi-turn dialogue or settings where intermediate steps trigger dynamic interactions with the environment or user. Extending DISC to such settings would require new mechanisms for handling interactive feedback loops.\n\n3. **Failure to Improve in Trivial or Non-Compositional Tasks**: DISC allocates sampling budget to steps that appear difficult based on prefix statistics. If the task is trivially solvable (e.g., many simple MATH problems) or if early reasoning does not meaningfully constrain the final answer (e.g., hallucinated completions), the benefits of decomposition may be minimal. \n\nWe hope this detailed discussion clarifies the scope of DISC and our interest in future extensions to broader task formats and evaluation protocols."}, {"review_id": "CwXJWjlLKE", "reviewer": "Reviewer_1o4h", "summary": "The paper addresses a timely and important challenge in large language model (LLM) inference: how to dynamically allocate compute by adaptively decomposing reasoning steps during decoding. The proposed DISC method introduces a dynamic step-size adjustment algorithm guided by statistical reward estimations (e.g., z-scores).", "questions": "1.\tInclude explicit compute-efficiency metrics\n2.\tProvide more concrete visualizations or case studies showing how DISC reallocates compute dynamically in real examples.\n3.\tMore questions can be seen in the Weakness part.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "1. The paper proposes a seemingly effective decomposition mechanism that aims to reduce redundant sampling and better allocate compute across reasoning steps.\n2. The experimental evaluation is relatively thorough.\n\n\n## Weakness：\n1.\tAlthough the paper claims DISC performs dynamic step selection based on reward distribution statistics, it lacks a principled theoretical justification for this dynamic behavior. It is unclear what precisely governs the dynamic adaptation—apart from the z-score of a small number of sampled candidates.\n\n2.The method depends strongly on hyperparameters such as the initial partition ratio, the reward normalization scheme, and update rules. Therefore, this dynamic decomposition is fundamentally similar to simply pre-setting a static decomposition strategy.\n\n3.A key premise of the paper is to dynamically allocate compute based on the difficulty of different steps in the decomposition. However, the notion of step difficulty is never formally defined, measured, or validated. There is no metric to demonstrate that the method is indeed allocating more compute to harder reasoning steps.\n\n4.The method is claimed to improve inference efficiency, however, no concrete analysis of runtime is provided. Figure 5 reports only task accuracy metrics such as Pass@token or Pass@k, which do not isolate computational cost. While the authors vaguely claim negligible runtime overhead (Sec. 4.1 and Appendix Fig. 40), no detailed comparison of actual time or resource usage is shown. This significantly weakens the credibility of the efficiency claim.\n\n5.\tThe method is only compared against a few relatively simple and static decomposition schemes. The paper omits recent and stronger baselines from the literature on adaptive inference and multi-step reasoning with LLMs.", "was_revised": true, "final_justification": "After several-round rebuttal, the authors have mostly addressed my concern. Considering the feedback and the comments from the other reviewers', I would like to upgrade the final rating to BA, and expect the authors to include the entire response in the final version to imporve the overall quality of the content.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. As NeurIPS prohibits PDFs and anonymous external links in rebuttals this year, we regret being unable to provide annotated figures. We have instead described visual content through text and hope our explanations are clear.\n\n> The paper lacks a principled theoretical justification for dynamic step selection, and it is unclear what precisely governs the dynamic adaptation.\n\nWe clarify the intuition behind how DISC’s dynamic adaptation works with a concrete example, and explain why it is theoretically necessary for guaranteeing optimality.\n\n### Walkthrough of Adaptation Behavior\n\nConsider the example in Sec. 3.5:\n**“What's the maximum area of a rectangle with a 24 inch perimeter?”**\n\nDISC starts by prompting the model with this question and sampling multiple full solutions (Step 1 in figure 2). It selects the best one (e.g., the full derivation involving variables, equations, and a final numeric answer) and tries to reuse the **first few tokens** of that best solution to form a new “candidate prefix.”\n\nInitially, it proposes a candidate prefix like:\n\n> **“Let the length of the rectangle be l and the width of the rectangle be x.”**\n\nDISC samples completions from this prefix and computes its *z-score*, which measures how promising it is (lower is better). In this case, the completions from the candidate prefix were **less helpful** than completions from the original question alone, so DISC **rejects the prefix** (Step 2 in Figure 2). It reduced the step size (i.e., used a shorter snippet) and tries again with a shorter prefix (Step 3 bottom, Figure 2):\n\n> **“Let the length of the rectangle be l”**\n\nThis shorter prefix yielded significantly better completions, so DISC **accepted it and committed** to it as the first step (Step 3 top, Figure 2). This **reject-then-contract loop** is key to DISC’s behavior. Each rejection triggers a smaller step size (shorter prefix), and each acceptance locks in a useful piece of reasoning that future completions build on. \n\nThis dynamic mechanism also avoids wasting compute on easy steps. For instance, in the *final step*—solving for the area—DISC quickly accepted the candidate prefix, as the model easily produced high-quality completions without needing resampling.\n\n### Theoretical Justification\n\nOur theoretical analysis (Sec. 3.3, Supplementary material F.1) proves that DISC converges to an optimal solution—faster than BoN, the most widely adopted scaling method. Crucially, this guarantee **requires** comparing prefixes using a criterion like the z-score. The z-score acts as a proxy for whether committing to a prefix increases the likelihood of finding a better solution. If we accepted prefixes arbitrarily or used a non-adaptive rule, this guarantee would not hold.\n\nIn short, DISC’s dynamic step adaptation is not just a practical design choice—it is essential for theoretical optimality.\n\n> The method depends on hyperparameters like the initial partition ratio and reward normalization scheme, making it akin to using a fixed decomposition strategy.\n\nWe thank the reviewer for this insightful comment. We clarify that DISC introduces only one new hyperparameter—**the initial partition ratio** $\\alpha_0$—on top of existing parameters used by search algorithms. This parameter is *not tuned per problem or model*, and is held fixed across all problems and model types (Sec. 4.1, App. C.3), demonstrating robustness and generality. \n\nImportantly, while $\\alpha_0$ sets an initial *granularity guess*, it **does not define the decomposition itself**. Instead, DISC launches a **feedback-driven refinement process**, dynamically adjusting decomposition boundaries in response to observed rollout statistics. This stands in contrast to static schemes (e.g., token-level or sentence-level splitting), which impose fixed segmentations regardless of task structure or model behavior.\n\nAs illustrated in Section 3.5 and Appendix D.2, DISC can yield *entirely different decompositions for the same problem* depending on which reasoning path the model follows (e.g., solving via Lagrange multipliers vs. first-order derivatives). Static methods, by contrast, produce identical partitions and miss reasoning-path sensitivity. In contrast, DISC adapts segmentation based on model uncertainty—something static methods inherently lack.\n\nEmpirically, we show that DISC performs robustly across a wide range of $\\alpha_0$ values (0.10–0.30; Fig. 8, right), and improves performance **without any per-task tuning** across diverse models including GPT-4o-mini, LLaMA, Mistral, and DeepSeek-R1. \n\nFinally, **Theorem 1 (Sec. 3.3)** provides a formal guarantee that DISC converges to the optimal solution. In contrast, **static decomposition** can provably fail to reach the optimal solution when used with search algorithms such as greedy or beam search.\n\n**In summary**, DISC is not a static decomposition strategy—it’s a dynamic, feedback-driven process with theoretical backing and strong empirical robustness.\n\n> Step difficulty is undefined, and it's unclear if harder steps receive more compute. Add visualizations or case studies on compute allocation.\n\nWe would like to clarify on what we mean by step difficulty:\n\n**1. Defining Step Difficulty.**\nWe define a step’s difficulty operationally as the likelihood that additional sampling will yield better completions from that prefix. Under our scale-free reward assumption (Appendix C.5), the z-score of reward samples serves as a proxy: higher z-scores imply lower odds of improvement and thus greater difficulty. This is formalized in Section 3.2 and illustrated in Figure 4.\n\n**2. How DISC Allocates Compute.**\nDISC is explicitly designed to adaptively allocate more sampling to difficult steps via contractive refinement. When a proposed prefix exhibits a high z-score—signaling a challenging step—DISC contracts the step size and samples more finely around that region to explore improved continuations. Conversely, when the z-score is low, indicating an easier step, DISC proceeds with coarser granularity and fewer samples. This recursive refinement mechanism is implemented via a simple rejection step (Algorithm 1, Lines 11–15): if a candidate prefix exhibits a higher z-score than the base prefix, it is rejected and the step size is reduced. As such contractions are more frequent on harder steps, DISC naturally concentrates sampling—and hence compute—on regions with higher z-scores. \n\n\n**3. Empirical Evidence.**\nTo address the reviewer’s suggestion for additional concrete evidence:\n\n* We have created a new **scatter plot** showing a **positive correlation** between prefix z-score and number of samples of at that step, directly validating that DISC concentrates effort on harder steps.\n* As a case study, **Section 3.5 and Appendix D.2** present decompositions of real examples, with each step color-coded by z-score. These illustrate that DISC devotes more sampling (i.e., compute) to steps like \"which\" and \"therefore\"—short but pivotal reasoning points for LLMs, in line with prior observations on autoregressive generation sensitivity.\n* For example, in the MATH problem shown in Section 3.5, DISC allocated 35 out of 100 calls to the first step and 49 to the third step (both with higher z-scores), while the second step received 12 calls and the final step received only 4 calls, demonstrating targeted compute allocation.\n\n\n> The method omits comparisons against recent baselines in adaptive inference and multi-step reasoning.\n\nThank you for the suggestion. We have implemented and evaluated two recent adaptive inference baselines—**AdaPrune** (Zhao et al., 2024) and **S1** (Muennighoff, 2025). As shown below, **DISC continues to outperform both under a fixed compute budget of 10,000 output tokens** using GPT-4o-mini on APPS:\n\n| Method   | Pass\\@10,000 Tokens |\n| -------- | ------------------- |\n| DISC     | **0.550**               |\n| AdaPrune | 0.500               |\n| S1       | 0.460               |\n\nThese results further support the effectiveness of dynamic decomposition for inference scaling.\n\nWe also clarify that DISC addresses a complementary goal to prior work: rather than improving *how to search*—via algorithmic design (Wang, 2025), prompt or plan optimization (Feng, 2023), or reward-based inference (Zhang et al., 2024)—DISC introduces a dynamic *decomposition* mechanism that adaptively controls branching granularity and timing. As shown in Section 3.4 and Appendix E, DISC is agnostic to the underlying search policy and works plug-and-play with methods from Zhang et al. (2024), Feng (2023), and Wang (2025). \n\n\n> The absence of explicit runtim timing or resource comparisons weakens the efficiency claim. Include explicit compute-efficiency metrics.\n\nThank you for highlighting the need for explicit compute-efficiency evaluation. In response, we conducted a new experiment comparing methods under a fixed 3-minute wall-clock budget on APPS using GPT-4o-mini:\n\n| Method     | Pass\\@3min |\n| ---------- | ---------- |\n| LineSplit  | 0.530      |\n| TokenSplit | 0.515      |\n| BoN        | 0.525      |\n| DISC       | **0.555**  |\n\nThis result supports our claim: **DISC yields better performance within the same runtime constraints**.\n\nWe also wish to clarify that LLM inference latency is heavily influenced by environment-specific factors such as batching, caching, hardware, and API response times from the model provider. As discussed in Sec. 4.1 and Appendix D.6 (Fig. 43), the majority of runtime is dominated by LLM generation latency, not the overhead introduced by our method. Because wall-clock time can vary widely across platforms and deployment contexts, token- and query-based metrics—such as Pass@token and Pass@k—are widely adopted in the literature (e.g., (Snell, 2024)) as platform-agnostic and reproducible proxies for compute cost. Moreover, tokens are the standard unit of billing and compute cost used by inference providers."}, {"review_id": "akrwOFa9AC", "reviewer": "Reviewer_HBjZ", "summary": "The paper presents a novel framework for dynamic decomposition in modern reasoning or code generation LLMs, named DISC. DISC extends search strategies like MTCS and beam search by adaptively partitioning solution steps to put more computational resources on harder parts, thus improving effectiveness of inference. The authors performed experiments on APPS, MATH, and LiveCodeBench benchmarks against several static baselines, including token-level, sentence-level, and single-step decomposition. achieving up to 10% reduction in error relative to the baselines.", "questions": "- Figure 6a present open-source models. It is unclear which version of the model is base (if any) and which one is DISC (if any). Please clarify.", "limitations": "The paper should contain a clearly marked list of limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* The paper rests on a simple yet effective idea to change the problem decomposition steps based on the insight that prefix statistics (which correlate with the promising reward improvement) can aid the split, leading to larger or smaller steps. The paper also shows that the DISC technique integrates with the state-of-the art LLMs, including open source and commercial ones. \n\n* Evaluation shows reasonable improvements over various baselines, given pass@k and pass@token metrics. Overall, I found the results in this section convincing, suggesting that DISC's adaptive partitioning improves correctness with the same token/sample budget over the alternative simple baselines. While the improvements are not enormous, they are significant enough to merit publication of this work and the overhead of the technique is low (assuming an appropriate reward model exists). \n\n* Several ablation studies show the impact of several parameters on the quality of the search, strengthening the main results. The authors further support their arguments with an extensive appendix with additional experimental studies and mathematical derivations.\n\n\nWeaknesses:\n\n* The paper does not explicitly discuss the limitations of the proposed approach. For instance, the presentation of how self-generated test validation proceeds is currently terse and the details should be clarified both in the evaluation section and discussed as a limitation. \n\n* (minor) Algorithm: In Algorithm 1, Y_b is a set whose elements are pairs of elements. However the next line is applying the functions max and argmax (presumably on 2nd and 1st element, respectively). Update the presentation so that the computation is mathematically well-defined. \n\n* (minor) Formatting: try to keep the colors consistent. For instance, Fig 7 has different colors for DISC across different benchmarks. Figure 9 would be more understandable if it had means with standard deviations as bars. Also, the figure caption should explain the dotted lines on that plot.", "was_revised": true, "final_justification": "The discussion clarified some concerns. Keeping the original score. Ok if paper accepted.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. As NeurIPS does not permit the inclusion of PDFs or anonymous external links in the rebuttal this year, we apologize in advance that we are unable to provide annotated figures or visual clarifications. We have done our best to clearly describe figure content and visual changes. We hope our written explanations are sufficiently clear, and we are happy to incorporate any additional clarifications into the camera-ready version if the paper is accepted.\n\n    \n> The paper does not explicitly discuss the limitations of the proposed approach. For instance, the presentation of how self-generated test validation proceeds is currently terse and the details should be clarified both in the evaluation section and discussed as a limitation.\n\nWe appreciate the reviewer’s thoughtful feedback and agree that an explicit discussion and marked list of limitations, particularly around self-generated test validation, is important. Per the reviewer's suggestion, we will (1) add a dedicated limitations section, and (2) expand our explanation of the self-generated test evaluation setting in Section 4.1 and Appendix D.3.\n\nSpecifically, we now clarify that self-generated test validation refers to a setup where the LLM is prompted to produce its own unit tests for a given code generation problem, and these tests are then used as a proxy reward model for inference-time evaluation. This approach has gained traction due to the high cost or unavailability of ground-truth test cases in many real-world tasks.\n\nThere are several interesting limitations of our framework.\n\n* **Reliance on LLM Test Generation Abilities**: The effectiveness of this evaluation depends critically on the LLM’s ability to produce meaningful and comprehensive unit tests. If the generated tests fail to cover edge cases or are semantically shallow, the evaluation may overestimate the correctness of completions.\n\n* **Assumption of Test Set Precision**: The framework assumes that the majority of self-generated tests are themselves correct and executable. In practice, this may not always hold—especially for complex or ambiguous problem specifications—potentially leading to false positives or unreliable reward signals.\n\n* **Comparison to Ground Truth Is Not Guaranteed**: Unlike evaluation with a ground-truth verifier, self-generated tests are not guaranteed to align with the reference solution, which can introduce inconsistencies in scoring across different methods.\n\nThese challenges are documented in prior work, including \\[1], which systematically studies the tradeoffs and failure cases of using generated tests for code evaluation. We now refer readers to \\[1] and related literature for a more comprehensive discussion of the strengths and limitations of this approach.\n\nWe also discuss additional limitations in the newly added section, including DISC’s reliance on a reward model, its current design for single-turn generation tasks, and scenarios where early reasoning does not meaningfully influence the final answer.\n\nWe hope this clarification and expansion address the reviewer’s concern, and we thank them again for helping us improve the clarity and completeness of the paper.\n\n**Reference**\n\\[1] Chen, Bei, et al. *\"Codet: Code generation with generated tests.\"* arXiv preprint arXiv:2207.10397 (2022).\n\n> (minor) Algorithm: In Algorithm 1, Y_b is a set whose elements are pairs of elements. However the next line is applying the functions max and argmax (presumably on 2nd and 1st element, respectively). Update the presentation so that the computation is mathematically well-defined.\n\n> (minor) Formatting: try to keep the colors consistent. For instance, Fig 7 has different colors for DISC across different benchmarks. Figure 9 would be more understandable if it had means with standard deviations as bars. Also, the figure caption should explain the dotted lines on that plot.\n\nWe thank the reviewer for their helpful suggestions regarding the algorithm presentation and figure formatting.\n\nTo address the first point, we have revised the notation in Algorithm 1 to ensure the computation is mathematically well-defined. Specifically, we now explicitly define the elements of the set $Y_b = \\{ (s_i, R(s_i)) \\}$ as pairs of completions and their associated rewards. We also clarified that we use $\\max_{(s, R(s)) \\in Y_b} R(s)$ and $\\arg\\max_{(s, R(s)) \\in Y_b} R(s)$ to compute the maximum reward and the corresponding completion, respectively, for cleaner and unambiguous mathematical notation.\n\nFor the second point regarding formatting, we have made several updates for clarity and consistency. We standardized the color palette across figures so that DISC is represented with a consistent color throughout all benchmark plots, including Figure 7. In Figure 9, we have updated the plots to make the trends and variability clearer. Additionally, we expanded the figure caption to explain the meaning of the dotted lines, which indicate baselines or comparative trends depending on the subplot.\n\nWe appreciate the reviewer’s careful attention to detail and believe these changes improve the clarity and presentation of the manuscript.\n\n> Figure 6a present open-source models. It is unclear which version of the model is base (if any) and which one is DISC (if any). Please clarify.\n\nWe thank the reviewer for their thoughtful feedback and apologize for any lack of clarity in Figure 6a. The left panel of Figure 6 displays the inference scaling performance of DISC applied to three different open-source base models at varying budgets: Llama-3.1-8B, Mistral-7B-v0.3, and Qwen-2.5-7B. Each line color corresponds to a specific model, and we have revised the figure caption and legend in the updated manuscript to make this distinction explicit. As shown in the figure, DISC consistently improves performance across all three models. Notably, while the *relative* accuracy improvements are more substantial for weaker models such as LLaMA (from 0.01 to 0.04; a 300% relative increase) and Mistral (from 0.0 to 0.02), the *absolute* gain is highest for the stronger Qwen model (from 0.095 to 0.17; a 7.5 percentage point increase), as detailed in Section 4.1. These results underscore DISC’s robustness and general applicability, yielding meaningful gains even under limited compute budgets. We thank the reviewer again for bringing this to our attention and have clarified the figure and surrounding text accordingly."}, {"review_id": "ZMLZJA3xiD", "reviewer": "Reviewer_PSiF", "summary": "This paper presents a novel test-time inference strategy called DISC, which adaptively decomposes the generation process of large language models (LLMs) by dynamically adjusting the step granularity. Instead of relying on static token-level or sentence-level generation, DISC estimates the “difficulty” of each step and decides whether to accept or further expand it using a z-score-based criterion. The method is model-agnostic, requires no additional training, and is compatible with various search paradigms such as greedy decoding, beam search, and MCTS. Experiments across multiple reasoning benchmarks (APPS, MATH, LiveCodeBench) demonstrate notable performance gains under constrained compute budgets.", "questions": "Please refer to Weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is motivated by a practical problem and is clearly written, making it easy for readers to follow.\nDISC is easy to plug into existing inference pipelines, and doesn’t require training or model changes.\n2. Solid evaluation across tasks and models, and good ablations around its design choices (e.g., temperature, thresholds).\n\nWeaknesses:\n1. A number of recent papers (e.g., DynScaling [1], RINS [2]) also explore ways to adapt compute usage during inference. They differ in method—e.g., using multi-armed bandits, recursive refinement, or heuristic difficulty estimates—but share a similar motivation. The paper doesn’t really discuss these. It would help to clearly highlight what DISC does differently (especially around the level of granularity or how compute decisions are made), and what the practical gains are. \n2. The current z-score–based decomposition decision appears to be heuristic. Is there any theoretical justification or learned variant that could better adapt to different task domains or model behaviors?\n3. While DISC is compatible with search methods like beam or MCTS, the interaction mechanisms are not well explained. Does DISC affect search efficiency, or introduce redundancy in rollouts?\n[1] Wang F, Wan X, Sun R, et al. DynScaling: Efficient Verifier-free Inference Scaling via Dynamic and Integrated Sampling[J]. arXiv preprint arXiv:2506.16043, 2025.\n[2] Alabdulmohsin I, Zhai X. Harnessing Language's Fractal Geometry with Recursive Inference Scaling[J]. arXiv preprint arXiv:2502.07503, 2025.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. As NeurIPS does not permit the inclusion of PDFs or anonymous external links in the rebuttal this year, we apologize in advance that we are unable to provide annotated figures or visual clarifications. We have done our best to clearly describe figure content and visual changes. We hope our written explanations are sufficiently clear, and we are happy to incorporate any additional clarifications into the camera-ready version if the paper is accepted.\n\n\n> A number of recent papers (e.g., DynScaling [1], RINS [2]) also explore ways to adapt compute usage during inference. They differ in method—e.g., using multi-armed bandits, recursive refinement, or heuristic difficulty estimates—but share a similar motivation. The paper doesn’t really discuss these. It would help to clearly highlight what DISC does differently (especially around the level of granularity or how compute decisions are made), and what the practical gains are.\n\nWe thank the reviewer for this excellent suggestion. We will include a dedicated discussion in **Section 5 (Related Work)** to highlight how DISC differs from recent adaptive compute methods like DynScaling, RINS, and MetaScale. These works indeed share a similar motivation—efficiently allocating inference-time compute—but differ in *what granularity* they operate on, *how compute decisions are made*, and *where adaptation occurs*.\n\n* **DISC (ours)** performs *intra-query*, *span-level* dynamic decomposition. It adaptively partitions a single solution into reasoning steps of varying lengths, refining only where needed using a local, binary refine/stop decision. This allows DISC to focus compute on hard reasoning regions while skipping trivial ones. DISC is model-agnostic, inference-time only, and integrates directly with search algorithms such as greedy, beam, and MCTS.\n\n* **DynScaling** (Wang et al., 2025) operates at the *inter-query* level and uses a multi-armed bandit to allocate more samples to harder queries. Within a single query, it leverages an integrated sampling policy (parallel then sequential) to manage sample reuse, but does not dynamically adjust step sizes or decomposition within responses. Thus, DynScaling adapts compute *across queries*, while DISC does so *within a single query* at the granularity of solution spans.\n\n* **RINS** (Alabdulmohsin & Zhai, 2025) introduces *recursive inference*, repeatedly applying the model itself to refine outputs—akin to reprocessing the entire generation in a self-similar manner. It adapts compute by repeating inference passes globally, rather than targeting specific spans or prefixes. In contrast, DISC adaptively selects which local spans to refine, avoiding redundant work on already confident segments.\n\n* **MetaScale** (Liu et al., 2025) performs *strategy-level adaptation* within a query. It maintains a pool of diverse \"meta-thought\" prompts or personas and uses UCB-style sampling to pick among them based on a reward model. MetaScale adapts *how* to reason (via prompt strategy) rather than *where* to focus compute in a given reasoning chain.\n\n**Practical implications:** These differences imply complementary strengths. DISC is well-suited for tasks requiring fine-grained correction (e.g., mathematical reasoning or code synthesis), while DynScaling is beneficial for triaging a large batch of mixed-difficulty queries. RINS can improve outputs through recursive refinement, and MetaScale enhances diversity through strategic prompting. DISC's lightweight, *plug-and-play* design enables compatibility with a variety of search methods (Sec. 3.4) and its gains stem from directly identifying critical reasoning junctures (Sec. 3.5). We believe combining these techniques could be a promising future direction, and we appreciate the reviewer’s prompt for this comparison.\n\n> The current z-score–based decomposition decision appears to be heuristic. Is there any theoretical justification or learned variant that could better adapt to different task domains or model behaviors?\n\nThank you for this perceptive question. Yes, there is a theoretical justification for using the z-score as the decision metric in DISC. As detailed in Section 3.3 of the main paper and Section F of the supplementary material, our optimality analysis relies critically on z-score–based comparisons to guide decomposition decisions. Note that **we updated the Appendix as part of the supplementary material after the full paper submission to strengthen our theoretical justification**—specifically, by adding Lemma 1 and clarifying its role in the proof of Theorem 1—to formally show that z-score–based acceptance ensures monotonic improvement in the likelihood of discovering optimal completions.\n\nSpecifically, we assume that rollout rewards approximately follow a location-scale family distribution (e.g., Gaussian or sub-Gaussian)—an assumption we empirically support in Appendix C.5. Under this assumption, the z-score of the maximum sampled reward provides a standardized estimate of how promising a given prefix is, in terms of the tail probability of achieving higher-reward completions. Selecting the prefix with the lower z-score thus corresponds to choosing the one with the highest estimated probability of improvement over the current base prefix.\n\nThis acceptance rule plays a central role in our optimality guarantee (Theorem 1, Section 3.3). The key step in the proof is Lemma 1 (Section F of supplementary material), which shows that accepting a candidate prefix only when its z-score is lower than that of the current base ensures that the probability of sampling the optimal suffix does not decrease. In other words, each accepted candidate maintains or improves the likelihood of discovering an optimal solution. This monotonicity is essential for proving that DISC will, under mild assumptions on the LLM policy (i.e., that the optimal solution lies in the support of the model), eventually commit to the optimal solution and terminate successfully, with faster convergence than BoN in expectation. Without this property, the algorithm could regress to less promising regions of the search space and fail to converge.\n\nFurthermore, our ablation study (Figure 8, middle) shows that replacing the z-score with alternative acceptance metrics—such as mean reward (DISC-Q), random selection (DISC-R), or even reversed z-score (DISC-negZ)—substantially degrades performance. Notably, DISC-Z (our method) outperforms all alternatives, while DISC-negZ underperforms even random selection, underscoring the importance of using z-score as the acceptance criterion.\n\n\n> While DISC is compatible with search methods like beam or MCTS, the interaction mechanisms are not well explained. Does DISC affect search efficiency, or introduce redundancy in rollouts? \n\nThank you for this insightful question. We address your concerns below.\n\nFirst, we clarify that DISC is designed to be *plug-and-play* with a wide range of search algorithms—including greedy, beam, and Monte Carlo Tree Search (MCTS)—by modularly handling the **decomposition logic** that determines *how far* to extend a node’s prefix during search. Rather than altering the core mechanics of the search algorithm (such as beam ranking, MCTS selection, or backpropagation), DISC acts as a drop-in replacement for the static rule that typically governs when to branch (e.g., after a token or a line). During the node expansion phase—regardless of the specific search method—DISC proposes a candidate step by appending a fraction of the best sampled suffix to the current prefix, and evaluates whether to accept or contract this step using rollout statistics (e.g., z-score comparisons). Because DISC only modifies *when* a node is expanded (i.e., step size) and *not* how nodes are selected or evaluated, it can be seamlessly incorporated into existing search pipelines without changes to the core search logic. This separation of concerns ensures that DISC enhances search granularity and adaptivity without introducing architectural complexity or engineering overhead.\n\nThis dynamic step sizing significantly improves *search efficiency* by focusing compute on challenging regions of the reasoning trace. For example, instead of expanding the tree one token at a time (token-level) or by fixed segments (e.g., line-level), DISC adapts step sizes based on rollout statistics, effectively skipping trivial segments while zooming in on uncertain or error-prone areas. This accelerates the search without sacrificing fidelity.\n\nImportantly, DISC does **not introduce redundancy in rollouts**. Rather, it is designed to *reuse the rollout data already collected by the underlying search algorithm*—such as the completions sampled for evaluating candidate nodes in beam search or MCTS. These same completions are jointly used by DISC to compute statistics (e.g., z-scores) for determining whether to accept a proposed step size or to contract it. In this way, DISC leverages the model outputs already required for node evaluation, avoiding duplicated sampling or unnecessary recomputation. This shared use of rollout data ensures that DISC remains efficient and tightly integrated with the existing search pipeline. We have clarified this point further in Appendix E.1.\n\nWe will update Appendix E.1 to more explicitly describe how DISC integrates with beam search and MCTS, and thank the reviewer's feedback."}]

Author rebuttal:

Meta-review: The paper introduces DISC, a dynamic decomposition approach for inference in large language models (LLMs). Instead of using fixed, static steps, DISC adaptively partitions the solution process. It uses a reward-based statistical criterion (a z-score) to estimate the "difficulty" of a reasoning step. Based on this, it dynamically decides whether to commit to a generated prefix or to shorten the step and dedicate more computational effort to that challenging part. This method is model-agnostic, requires no extra training, and integrates with standard search algorithms like beam search and MCTS. Experiments on code generation and mathematical reasoning benchmarks show that DISC improves inference efficiency and correctness compared to static decomposition methods.

The introduced approach has a clear motivation and it is simple and effective. The experimental results are strong -- showing consistent improvement over multiple benchmarks. Reviewers originally criticised the work for insufficient justification and analysis of the theoretical assumption, e.g. the choice of the z-score criterion, the definition of "step difficulty," and the lack of runtime efficiency metrics. They also concerned about the missing comparisons with the baseline models. However, these concerns were well addressed by the authors during rebuttal, which led to the final consensus from the reviewers that the paper is acceptable. 

I agree with the reviewers final assessment and therefore recommend this paper to be accepted.
Decision: Accept (poster)