- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper investigates test-time compute allocation for multi-step AI reasoning tasks with dependencies among subproblems, where errors at different nodes can have different downstream consequences. The authors first construct a reach-weighted surrogate loss based on the number of downstream nodes affected by each node and establish an approximation bound relating it to the expected number of corrupted nodes. Under an exponential error-decay model, they derive an optimal water-filling and characterize its potential advantage over uniform allocation through an AM/GM ratio. They also identify conditions under which graph structure becomes irrelevant under an all-or-nothing loss. To bridge theory and practice, the authors address unknown node difficulties and develop adaptive allocation strategies for arithmetic reasoning and code generation, using structure weights and feedback-based heuristics to approximate marginal benefits. Experiments on synthetic dependency trees, arithmetic tasks, and code generation evaluate allocation quality, practical performance, and the effects of dependency structure, including comparisons with uniform, structure-blind, degree-based, and oracle baselines.
Critical strengths
-
A coherent theoretical framework with a careful characterization of its applicability. The paper provides a well-structured formulation of comupte allocation under dependency-driven error propagation. Beyond deriving a reach-weighted allocation rule and its approximation guarantee, the authors examine several important boundary cases, including all-or-nothing loss, irreducible error floors, and approximate structural weights. In particular, the analysis of degree-based approximations provides useful insight into when simpler local structural information may be sufficient.
-
Systematic experimental evaluation with informative comparisons and transparent discussion of limitations. The experiments cover synthetic dependency trees, arithmetic reasoning, and code generation, with comparisons against exact or oracle references where applicable. The inclusion of structure-blind, degree-based, and shuffled-weight baselines helps distinguish the contribution of dependency information from general adaptive allocation. The authors also report uncertainty estimates and carefully examine cases where the proposed approach offers limited improvements. These analyses, together with the discussion of underlying assumptions and experimental limitations, help clarify the conditions under which structure-aware allocation is beneficial and provide a more nuanced understanding of the method's applicability.
Critical weaknesses
- Several key elements of the theoretical analysis, including importance-weighted reliability objectives, probability bounds, and water-filling-based resource allocation, are closely related to classical reliability optimization techniques. While the paper provides a coherent formulation for dependency-aware reasoning and derives useful approximation guarantees and boundary cases, the distinction between these contributions and existing work on reliability allocation and failure propagation is not sufficiently clear. A more explicit discussion of what is theoretically new in this setting would help establish the paper's contribution.
- The connection between the theoretical allocation principle and the practical code allocation heuristic is not sufficiently justified or evaluated. The theoretical allocation rule is guided by reach-weighted marginal error reduction, whereas the practical code strategy uses as a heuristic score. Although this captures the intuition of diminishing returns, the paper provides limited justification for this particular functional form and does not examine its sensitivity to alternative approximations. Moreover, the incremental improvements of reach-weighted allocation over equally adaptive structure-blind baselines are relatively small or inconsistent in the realistic code experiments. Without a comparable oracle allocation reference under the same experimental protocol, it is difficult to determine whether these results reflect limitations of the heuristic or limited opportunities for improvement in the underlying tasks.
Questions for authors
- Theoretical novelty and related work. While the paper acknowledges its connections to classical reliability allocation and water-filling techniques, could the authors further clarify which theoretical contributions are new in the context of dependency-driven inference? In particular, how do the path-limited approximation guarantee and the characterization of loss-dependent structural importance differ from or extend existing reliability optimization results?
- Motivation and sensitivity of the code allocation heuristic. What motivates the specific choice of for code allocation? While this heuristic captures diminishing marginal returns, its relationship to the theoretical marginal error reduction is not entirely clear. Have the authors considered alternative functional forms, such as exponential or parameterized power-law decay? How sensitive are the results to this choice?
- Oracle references and interpretation of the limited gains in realistic code experiments. Unlike the arithmetic experiments, the main realistic code experiments do not include a comparable oracle or exact-optimum allocation reference under the same evaluation protocol. While the idealized single-repair analysis in Table 5 provides useful evidence for the value of structural information, it does not directly quantify the attainable improvement in realistic code allocation. Could the authors provide a stronger oracle reference or an estimate of the achievable improvement under the same candidate pools and compute budgets? This would help distinguish whether the relatively limited gains over structure-blind allocation arise from the approximation used in the practical heuristic, the limited potential benefit of reach-based allocation itself in this setting, or the characteristics and repairability of the evaluated tasks.
- Robustness to imperfect dependency graphs. The proposed approach relies on a given dependency graph to compute structural weights. How sensitive is the allocation strategy to missing or spurious dependency edges? Could the authors evaluate its robustness under moderate perturbations of the graph structure?
- Generalization to realistic dependency-driven tasks. Given that the main arithmetic experiments use constructed dependencies, while the executed-propagation and real-repository studies are relatively small or inconclusive, could the authors provide further evidence or discussion on whether the benefits of structure-aware allocation generalize to naturally occurring multi-step reasoning tasks with genuine error propagation?
2 comments
Comment from Authors
We thank you for the time you have put into reviewing this work. Please let us know if you have any other questions. We will keep working on the manuscript to make it more clear and incorporate any further suggestions you give us.
Response to Reviewer cdVm
Thank you for the careful review. Your questions led to three new analyses (Appendix D of the revised PDF), which reuse the cached candidates and tests with no new generation. We have revised the paper (the new sections are in blue).
Q1.
We do not claim that water-filling is new; it is classical for weighted sums of exponentials. The closest reliability problem is redundancy allocation in a series system, which maximizes the probability that every component works. That corresponds to our all-or-nothing loss, where the graph disappears from the objective (Theorem 5).
Our setting instead measures the expected number of corrupted nodes: a node is corrupted if it or any ancestor fails. This loss is not separable. We therefore optimize a separable, reach-weighted surrogate and show that the resulting allocation is within a factor of optimal for the true loss. The factor depends on error accumulated along a dependency path in a tree, or across a node's ancestors in a DAG---not on graph size (Lemma 1, Corollary 2, Proposition 10). We are not aware of an equivalent result in the reliability literature we cite, though our search was not exhaustive.
The loss also matters empirically: on the same twelve trees, reach-weighted allocation gains 1.22--2.61$\times$ under partial credit but does worse than uniform (0.48--0.97$\times$) under all-or-nothing loss (\S7.4). Revised \S2 now makes this distinction explicit.
Q2.
Here, w is the number of dependents of a component, including itself, and a is the number of extra attempts after the first. If candidates independently passed at an unknown fixed rate under a uniform prior, Laplace's rule would assign the next candidate a success probability of 1/(a+3). This has the same general form as our score, up to an offset. Our setting differs (finite candidate streams, generated dependencies, acceptance by development tests), so this is motivation, not a derivation.
We also tested alternatives to a+2: (a+2)1/2, (a+2)2, and 2a, the last matching the theoretical marginal reduction for rate ln2. At 3$\times$ budget, the reach-versus-blind whole-task-success difference was unchanged with the square-root rule and declined under faster decay. On Llama validation libraries it fell from +7 points to +4 and +3; on the Llama suite, from +3.1 to +2.5 and +1.9. It remained +1 on Qwen validation libraries and 0 on the Qwen suite. All sixteen estimates were nonnegative, but intervals were wide and ClassEval was not rerun (Appendix D.1).
Q3.
We could not compute the proposed oracle: it would need to search over combinations of generated implementations, which interact. Instead, we report a diagnostic using the same candidate streams and token costs: for each component, we identify the first candidate that passes final tests when paired with reference dependencies.
In 25--66% of task runs, at least one component has no such candidate. At 3$\times$ budget, this diagnostic is within 0.01--0.06 of observed whole-task success on ClassEval and Qwen validation libraries, but 0.13--0.20 above observed success elsewhere (Appendix D.3, Table 21). Because it uses a different dependency context and relaxed selection rules, it is neither an upper bound nor a way to separate candidate scarcity from heuristic weakness, so it only partly answers the question. A true assembled-program oracle under the same protocol remains open.
Q4.
The theory gives the cost of incorrect weights: if allocation uses estimated reaches d rather than true reaches w, then, under equal rates, the extra surrogate loss is exactly AM(w/d)/GM(w/d) (Corollary 7, for allocations that do not clip at zero). This can be computed for any proposed graph error.
Empirically, we recomputed reach after randomly dropping or adding 20% of edges. The reach-versus-blind difference changed by at most two points, within the intervals. This check is too limited to support a broad robustness claim, and we do not make one (Appendix D.2).
Q5.
Our evidence for natural propagation comes mainly from the code study, where an incorrect helper makes its callers fail. We also ran a small executed-arithmetic study in which an incorrect parent changes the child's problem; with the same stopping rule, reach-based caps corrupted 0.082 of nodes versus 0.096 with uniform caps, though this comparison was unpaired.
RepoClassBench is inconclusive: an ideal single repair helped in at most 3 of 30 states. Limited candidate quality, interface errors, or repairs that must be made jointly could all explain this result. We have no broader evidence for naturally occurring multi-step reasoning. The real-world scenario in our response to kZsH (Q2) is one where the method should help; directing costly repairs, such as stronger models or human review, is the most promising next test.