First-Passage Budgeted Adaptive Computation

1. Exact integration point: build a stochastic adaptive-computation network with a small finite routing state space. A state can encode the current layer, expert, retry count, or confidence bin. Each transition either applies a neural block and moves to another state or enters absorbing state B, which emits the prediction. Parameterize every transition rate as k_e=softplus(phi_e)+epsilon. Train the network with the task loss plus lambda_tau times the MFPT tau=t_A, and optionally penalize disagreement between predicted and observed stopping times. 2. Pseudocode: construct Q from the current rates; solve Qt=-ones; set tau=t[source]; differentiate log(tau) with respect to phi using automatic differentiation, or use dt=-Q^{-1}(dQ)t; combine the task gradient and latency gradient; update phi with Adam. Log S_e and optionally project the sensitivity vector toward the budget set |S_e|<=1 and sum_e S_e=-1. A simpler controller increases rates with favorable latency/task gradients and decreases redundant rates. 3. Computed from the paper: Q, t, MFPT sensitivities, the per-edge bound, and the conserved sum. Estimated empirically: accuracy, wall-clock latency, stopping-time distribution, and finite-difference sensitivities. 4. First cheap experiment: use a 6-layer MLP on MNIST or CIFAR-10 with stochastic layer skipping and one absorbing early-exit state. Compare ordinary learned exit rates, uniform rates, and the budget-aware controller at matched accuracy. The falsifiable signature is that generator sensitivities satisfy |S_e|<=1 and sum_e S_e=-1, while finite perturbations obey Delta log(tau) approximately equal to S_e Delta log(k_e) for perturbations below 0.05. Under global scaling k_e->c k_e, measured tau must scale as tau/c. A single-edge perturbation must not produce a logarithmic MFPT change larger than the logarithmic rate perturbation, up to numerical error.