acceptodds
Under review as a conference paper at ICLR 2027

Structure-Aware Compute Allocation for Multi-Step AI Reasoning

Abstract

An error in a shared intermediate result can invalidate many downstream outputs. We derive a rule for allocating inference compute according to these unequal consequences. For dependent sub-problems with partial credit, downstream reach weights a separable upper bound on expected invalidated work. Under independent node errors and exponential error curves, optimizing this bound gives a water-filling allocation with a finite guarantee relative to the true-loss optimum. For homogeneous rates and unclipped allocations, its surrogate gain over uniform is exactly the arithmetic-to-geometric-mean ratio of the reach weights. On synthetic trees, median excess loss over the exact optimum is 1.3%–7.3%, a separate timing study finds – faster allocation than exact optimization. On selected, moderate-difficulty arithmetic trees at tight budgets, reach-weighted allocation outperforms an equally adaptive structure-blind policy in all three models (paired gain –). On code, idealized reference-code repairs show that reach times a local failure signal obtains 71–88% of the best single repair's benefit, versus 43–68% for the signal alone, among states where a repair helps. Actual code savings largely come from adaptive stopping; reach adds setting-dependent gains and degree performs similarly. The framework connects an efficient allocation rule to measurable gains and explicit conditions for when dependency information is useful.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Hierarchical weighing, wisdom of crowds, problem decomposition

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_cdVmOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.
  2. 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 wv/(av+2)w_v/(a_v+2) 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
  1. 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?
  2. Motivation and sensitivity of the code allocation heuristic. What motivates the specific choice of wv/(av+2)w_v/(a_v+2) 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?
  3. 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.
  4. 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?
  5. 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
AuthorsOpenReview ↗

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, ww is the number of dependents of a component, including itself, and aa 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)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+2a+2: (a+2)1/2(a+2)^{1/2}, (a+2)2(a+2)^2, and 2a2^a, the last matching the theoretical marginal reduction for rate ln⁡2\ln 2. 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 dd rather than true reaches ww, then, under equal rates, the extra surrogate loss is exactly AM(w/d)/GM(w/d)\mathrm{AM}(w/d)/\mathrm{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.

AuthorsOpenReview ↗

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.

Reviewer_zh5LOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The authors study effort allocation in multi-step DAG-structured tasks. Tasks are split into subproblems (nodes) with edges indicating subproblem dependencies (i.e., (u,v)(u, v) means the answer to uu is needed to get the answer to vv). Subproblems are assumed to be retry-able, with independent error probabilities across runs. Given a budget for total attempts across a DAG, the authors derive an optimal budget allocation under an assumption about the attempt-count-to-error-probability distribution. When the difficulty of subproblems is unknown, the authors propose using the "reach" of a node (the number of descendants) as an importance weight. Part of their analysis includes deriving a computable surrogate loss that they use to bound the expected number of failing nodes. They test their approach against multiple baselines on coding and arithmetic tasks, finding significant improvements from clever effort allocation.

Critical strengths
  1. The problem studied is interesting: the DAG task decomposition is natural, and a theoretical model providing better effort allocation under retries is a nice contribution. The problem is also studied in multiple settings: known vs unknown node difficulties and multiple models of aggregating retries (voting, selecting based on test cases). I did not check the appendix proofs, but the results in the main text (to the extent that I could understand them) seem coherent and reasonable.
Critical weaknesses
  1. The writing quality and clarity are low. It's very difficult for a human reader to follow the sentence structure, paper layout, and jargon. The purpose of a paper is to effectively communicate interesting ideas -- there are some interesting ideas here, but the paper's writing needs to be significantly improved to make these ideas useful and shareable. This is serious enough that, in my view, it blocks publication-readiness. The paper should be substantially rewritten with a focus on clarity, motivation, and explanation, so that an unfamiliar reader can grasp the important concepts.

Comments

  • The title of the paper in OpenReview and the PDF paper title do not match. The OpenReview title is much clearer, since it places the paper in "multi-step AI reasoning"
  • Examples of clarity issues (very incomplete list):
    • The first sentence of the abstract does not contextualize the paper: what is a shared intermediate result? A result for what?
    • The third abstract sentence is extremely hard to understand -- what is downstream reach and what does it mean for it to weight a separable upper bound on expected invalidated work?
    • The first paragraph of the intro should provide clear context for the work. The current version requires the reader to understand an overly detailed example without understanding what about the example is important. The key things a reader needs: (1) the tasks studied are multi-part workflows with DAG-structured dependencies, (2) the paper considers agents solving such tasks under a global budget for the number of attempts, (3) the mechanism used is per-node voting: the problem is to allocate attempts over nodes of the graph such that, by voting over the best solution at each node, the overall workflow is given the best chance of success. Understanding this required significant effort and combining multiple parts of the paper
    • Section 4 results need to explained intuitively. Why do they hold and what is the implication?
    • Despite reading multiple times, I don't understand what proposition 6 is trying to say or what its implications are. The term "probe" is not used until Proposition 6, and is not explained.
    • The Theorem titles are not helpful. "Path-limited sandwich" and "Allocation under two loss functions" do not tell us what the results say.
    • The experiments section doesn't describe what the tasks are, what models are being used, how attempts are evaluated, how trees are generated, or how different tasks depend on each other. 7.1 jumps immediately into numerical results
    • "Unknown difficulties" is a confusing section title?
Questions for authors
  1. It was difficult to understand the arithmetic problem experiment setup. What is the relationship between nodes? What does "votable" mean in line 321 and what is the "calibration-only difficulty filter"?
  2. How are coding subproblems defined? What is the difference between the pilot and validation sets?
  3. What kind of DAG structures and difficulty distributions make the approximation/surrogate least accurate?
3 comments
AuthorsOpenReview ↗

Response to Reviewer zh5L

Thank you for the detailed review. Following your suggestions, we have worked to improve the paper's clarity. Our answers to your questions follow. We have revised the paper (the new sections are in blue).

Q1: Every node is an ordinary multiplication problem with one true answer. For example, the root might be 47×8647 \times 86, whose correct answer is 4042. The model samples several answers, and the node keeps the most common one, which is right or wrong. The tree represents steps that use earlier results: the children build on the root, and the leaves build on the children. In this experiment the problems do not actually use each other's answers. The tree is a scoring rule: whenever a node's kept answer is wrong, that node and every node below it count as corrupted, as if they had been computed from a wrong input, and we measure the number of corrupted nodes. A separate experiment (\S7.4) uses trees in which a child's problem really is computed from its parent's answer.

To choose problems, we first drew 8 calibration answers per candidate problem, used only for selection and for the policies' prior, never for scoring. The calibration-only difficulty filter keeps problems with 3 to 7 correct answers out of 8. Problems answered correctly every time or almost never leave nothing for an allocation to improve: on an earlier pool that included them, every policy was within 2% of uniform. ``Votable'' means that at least 5 of the 8 calibration answers are correct, so that a majority vote can recover the right answer. Together, the two conditions keep problems with 5 to 7 correct answers out of 8. We then drew 16 new evaluation answers per kept problem, and only these score the policies. Because selection never used the evaluation answers, they cannot leak into it. The result therefore applies to problems on which voting can help, and the revised \S7.2 says so.

Q2: A coding task is a small library or a class, and each subproblem is one function or method that the model writes from its description. An attempt is one model-written implementation of that function. For example, a function that parses a configuration file might be called by two others, one that loads settings and one that validates them. The graph is the call graph: the parser is the root, with reach 3 (itself and its two callers), and a function that nothing calls has reach 1. For ClassEval, we use the benchmark's declared dependencies between methods. During allocation, a policy tests each function against its current generated versions of the functions it calls, so a bug in the parser also makes the tests of its callers fail. Separate final tests, which the policy never sees, score the finished program.

Pilot versus validation. The pilot reuses tasks from our earlier analyses: 16 libraries we wrote (90 functions) and 53 ClassEval classes. We used it to build and examine the method, and its token costs are approximate because raw completions were not stored. The validation set is ten new libraries of seven functions each. We wrote and froze them before generating any candidate, recorded exact token counts, and fixed the endpoints before the first full run. It exists to check the pilot's conclusions on tasks we had not looked at.

Q3: The surrogate's error comes from counting a corrupted node more than once, which happens when several errors fall on the same dependency path. The theory therefore says it is least accurate for deep graphs whose nodes are error-prone, because errors accumulate along long paths, and, on a DAG, for nodes with many ancestors. In our exact synthetic comparisons, every node had the same difficulty and the trees had 8 to 127 nodes. The surrogate cost at most 6.4%, in the 32-node chain, which has the longest paths, and it was small elsewhere (\S7.1 and Appendix D.4). The largest gap between our allocation and the exact optimum, 25.4%, came from a different source: approximating the majority-vote error curve by an exponential, on bushy trees at high accuracy. We have not tested unequal difficulty, so our expectation that a path of hard nodes makes the surrogate less accurate follows from the theory but is not measured.

Title. We agree that the OpenReview title is clearer; the revised PDF now uses it.

Changes in the revised PDF. The first sentences of the abstract and \S1 now state the setting: a task split into dependent sub-problems, a fixed budget of attempts, and one kept answer per sub-problem; "reach" is defined before it is used. Lemma 1 is now titled ``The surrogate is within a path-dependent factor of the true loss'' and Theorem 5 "Under all-or-nothing loss the graph does not affect the optimum"; short explanations follow Lemma 1, Theorem 3, and Proposition 6. \S6 is now titled "Learning difficulty from the same budget" and defines "probe" before Proposition 6. \S7.1--7.3 now open with the task setup.

AuthorsOpenReview ↗

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.

Thanks for the clarifications, I found this response much clearer than the paper itself. The blue updates to the paper are a reasonable start, but I think the paper needs a more complete rewrite to be readable.

Reviewer_kZsHOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies how to distribute repeated samples across the steps of a task with a given dependency graph. An incorrect step is assumed to invalidate all steps that depend on it, while unaffected results retain value. The authors derive a weighted upper bound on the expected number of invalidated nodes and optimize it using a classical water-filling allocation under exponential error curves. They provide a conditional approximation guarantee and evaluate the allocation on synthetic trees, arithmetic problems, and code tasks. The main empirical gains are in selected arithmetic problems and idealized code repair selection; savings in actual code generation largely come from adaptive stopping.

Critical strengths

S1. The experiments compare adaptive policies with and without dependency weights, showing that much of the code-generation saving comes from stopping rather than the graph. This comparison helps identify what the proposed allocation actually adds

Critical weaknesses

W1. The task setting is overly idealized. Which step deserves more compute depends on the task and the importance of that step. Ten simple preparatory actions need not matter more than one final complex calculation. The paper does not adequately explain when the number of downstream nodes is a meaningful measure of the cost of an error in a real task.

W2. The allocation method remains removed from how models actually reason. Additional compute mainly means generating more answers for predefined subproblems. The paper does not clearly establish how producing these extra candidates helps a model reason more deeply, or how the method applies beyond this fixed sampling workflow.

W3. The premise that voting improves reliability is not sufficiently convincing. Agreement across answers does not make them correct: if the model repeatedly makes the same error, more sampling and voting may not help. The main arithmetic gains also come from problems selected to benefit from voting, further limiting the applicability of this setting.

W4. The paper does not adequately establish what substantive advance the formal analysis delivers. Upstream errors affecting downstream steps is a familiar observation. What matters is which practical problem the resulting allocation method solves. In code, most savings come from adaptive stopping, while reach adds inconsistent gains and performs similarly to simple degree weights. Its demonstrated advantage over simpler strategies remains limited.

Questions for authors

Q1. In the evaluated tasks, why does the number of downstream steps reflect how important it is to get a step right? In particular, how does this objective capture a task in which simple preparation steps lead to one crucial final calculation?

Q2. Which practical reasoning task benefits from this allocation, beyond generating more candidates for predefined subproblems? Please use an existing experimental example to explain what the method improves over a simple sampling strategy.

Q3. The main arithmetic gains rely on problems selected to benefit from voting. What evidence supports using the method when the model repeatedly makes the same error and agreement is not a reliable sign of correctness?

4 comments
AuthorsOpenReview ↗

Response to Reviewer kZsH

Thank you for the detailed and careful review. We have revised the paper (the new sections are in blue). Please see our responses to the questions and comments below:

Q1 / W1.

In our formulation, the task's loss determines how important a step is, and how much another attempt reduces that step's error determines how much budget it gets. Counting downstream nodes is the simplest case, where every correct intermediate result has the same value.

For a task where results have different values, let νu\nu_u be the value of a correct result at node uu. An error at node vv then destroys the value of vv and every result that relies on it, so its weight is wv=∑u∈subtree(v)νuw_v=\sum_{u\in\mathrm{subtree}(v)}\nu_u. The theory extends to these nonnegative weights. Thus, a simple preparatory step receives credit for protecting a valuable final calculation, but it does not automatically receive most of the budget. The other part of the decision is how much another sample can help. Theorem 3 balances the value protected by each step against how quickly extra samples reduce its error. An easy preparation step becomes reliable quickly and needs little further effort. A step whose error cannot be reduced offers no benefit from extra samples. Thus, a large downstream weight alone does not determine the budget.

If only the final answer has value, all of its ancestors have the same value: an error at any one of them makes the final answer wrong. This is the all-or-nothing case. Under the paper's assumptions, the graph no longer changes the optimal allocation (instead, difficulty does). Please see the revised paper, which now defines this value-weighted loss and its all-or-nothing case (\S3, ``Unequal values''; proof in Appendix A.2), and \S4 explains the trade-off between reach and difficulty after Theorem 3.

Q2 / W2.

The paper studies a narrower problem than reasoning as a whole. The paper's sole focus is how to distribute effort after a task has been decomposed. It does not show how to create the decomposition, nor does it demonstrate a new form of reasoning beyond sampling candidates for a fixed workflow. A planner can supply the graph, or the graph can already exist, as in a codebase's call graph. We expect this work to be paired with systems that produce the decomposition, such as language models or causal-graph generators. Studying allocation given a fixed decomposition has three advantages. First, the rule applies to any graph, whatever its source, so the planner can be replaced without changing the allocator. Second, the planner and the allocator can be evaluated separately, which makes it possible to measure what structure contributes to allocation without confounding it with decomposition quality. Third, the allocator can be tested against imperfect graphs before any particular planner is chosen (Appendix D.2 is a first, small test).

Regarding examples to show the relevance of this work:

Consider a financial-analysis agent that extracts figures from a report, computes derived quantities such as total revenue and margins, and writes a summary. Total revenue is reused by many later ratios, and a typo in a table caption is used by nothing. A wrong total revenue spoils every ratio built on it. A wrong caption spoils one line. With a fixed number of model calls or human checks, equal effort per step wastes some of them, so the extra checks should go mainly on the shared total, and fewer on the caption.

In an experiment we ran (arithmetic trees, \S7.2), a ``simple sampling strategy'' gives every step the same number of votes, or stops early on each step but ignores dependencies. Our policy gives more votes to steps that many others depend on. On the same trees and budget, it leaves 7--12% fewer wrong nodes than the policy that stops early equally but ignores dependencies. Shuffling the weights removes the gain, so the improvement comes from the dependency structure.

AuthorsOpenReview ↗

Response to Reviewer kZsH

Q3 / W3.

We agree that agreement is not evidence of correctness when the model makes the same mistake repeatedly. A persistent error limits the value of more votes. In the model, an additive error floor reduces the gain available from reallocation. A node receives no extra effort once its remaining reducible error is too small to justify it. We observed this in our first arithmetic pool experiment, which was drawn without any difficulty filter, and most of its problems were solved either always or almost never. On it, every policy, including ours, is within 2% of uniform (Appendix C.1, Table 7). The paper's claim is therefore conditional: it characterizes when allocation helps and when it does not.

The code experiments do not rely on agreement. A policy tests each generated implementation inside its current generated program, and separate final tests, which the policy never sees, score the result. After repeated failures the policy lowers a component's priority, but this is a heuristic and does not guarantee that it detects systematic errors.

The theory also does not require voting. The guarantee that the surrogate is close to the true loss holds for any per-node error curve; the exponential curve is only what gives the closed-form allocation. Other decreasing convex curves can be optimized by marginal gains when every unit of effort costs the same, and the exact tree program accepts arbitrary error tables. The budget can also count any unit of effort, not only votes (\S4.1, ``Costs and other forms of effort, and DAGs'').

Furthermore, there are situations in which voting is expected to reduce error, as studied in the wisdom-of-crowds literature. Surowiecki lists diversity of opinion, independence, decentralization, and aggregation as the conditions under which crowds judge well. Our work hopes to build on this literature.

W4.

Deployed systems often split a task into steps and then check, retry, or review each step. Many of them spend the same effort on every step, or tune it by trial and error. Our contribution is a principled way to decide where the extra effort should go. The answer depends on two things per step: how much of the task relies on it, and how much more effort would improve it. The practical value is that the analysis tells a practitioner, before running anything, when this is worth doing and when it is not.

If every step must be correct, equal effort is already best. If a model's mistakes are systematic, extra effort helps little anywhere. If a simple count of direct dependents captures most of the structure, the full graph analysis is unnecessary.

``Upstream errors affecting downstream steps is a familiar observation.''

We agree that this is a well-established observation. What it does not tell you is what to do with it. Knowing that upstream errors matter does not say how much more effort an upstream step deserves, and the intuitive rule, ``give more to whatever the most steps depend on'', fails in three cases that our analysis identifies. An easy step needs little effort however much depends on it. A step that extra effort cannot fix deserves none. And if the task counts only when every step is correct, dependency does not matter at all. Our contribution is a rule for dividing a fixed budget of attempts across dependent steps that accounts for all three, together with experiments showing where it helps. On arithmetic trees it cut corrupted steps by 7--12% against an equally adaptive policy that ignores dependencies. To our knowledge, this has not been done for allocating test-time compute.

AuthorsOpenReview ↗

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.

Reviewer_kZsHOpenReview ↗

Follow-up on Authors' Response

Thank you for the detailed response and revisions. I appreciate the generalization to non-negative node values (νu\nu_u) and the clearer boundary conditions. However, my core concern regarding practical feasibility remains. The framework assumes tasks already follow a fixed dependency graph with well-defined, separable step values (νu\nu_u) and predictable error decay. In practice, constructing this upstream parameterization is far harder and more ambiguous than solving the downstream allocation itself. Crucially, as Theorem 5 acknowledges, the graph structure vanishes entirely under standard all-or-nothing objectives. Treating these idealized upstream parameters as given bypasses the primary bottleneck of multi-step reasoning, leaving the method's practical utility unconvincing. Therefore, I maintain my rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.