Structure-Aware Compute Allocation for Multi-Step AI Reasoning

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 $34$–$1,300\times$ 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 $1.08$–$1.13\times$). 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.