Banking Expiring Compute: How Reuse Shapes the Value of Prediction

Knowing the expected work of every feasible preparation need not reveal which one is most likely to finish within a fixed budget. We study banking expiring compute: using a temporary allowance to retain intermediate results, reusable while their inputs remain unchanged, under limited storage. For ordered associative computations, both the learner and an informed comparator may choose the evaluation tree and stored results. Under ideal reuse, individual interval-validity probabilities exactly characterize all feasible mean work; joint validity of collections that fit preparation and storage budgets characterizes full work distributions. We construct laws agreeing on every feasible mean, yet even randomized mean-only decisions have exponentially smaller worst-case completion probability than informed decisions with the same resources. On this family, increasing only the execution budget makes a history-free randomized policy exponentially close to optimal in a specified slack range. Logarithmically many complete i.i.d. histories from the same update law recover an optimal preparation with high probability. More generally, physical reuse capacity bounds the sample complexity of near-optimal preparation, with matching worst-case bounds in identified ideal-interface regimes. The upper bound has no additional input-count dependence beyond resource parameters and survives fixed nonnegative checking and restoration costs. Together, these results tie the value of predictive information and the statistical cost of learning a preparation to feasible reuse and execution budgets.