# First-Passage Budgeted Adaptive Computation

- ID: 1887
- Canonical URL: https://synthcore.org/idea/1887/first-passage-budgeted-adaptive-computation
- API JSON: https://synthcore.org/api/idea/1887.json
- API Markdown: https://synthcore.org/api/idea/1887.md
- Verification status: unverified
- Source: [arXiv:2608.06368](https://arxiv.org/abs/2608.06368)
- Category: dynamics
- Solves: speedup, stability, scalability
- ML areas: mlp, moe-routing, optimizer, training-dynamics
- Math tags: stochastic-processes, probability, dynamical-systems, optimization
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Represent stochastic layer execution, branching, retries, and early exit as a finite continuous-time Markov chain, with the completed-prediction state absorbing. Learn transition rates jointly with neural-network weights, but use MFPT sensitivities to allocate rate changes according to their available control budget rather than allowing one routing edge to dominate halting-time control.

## Mathematical statement

Let a finite continuous-time Markov chain have transient states i and absorbing completion state B, with directed edge rates k_e>0. Let tau(k)=E_A[T_B] be the mean first-passage time from source A to B. Define the logarithmic rate sensitivity S_e=(partial log tau)/(partial log k_e)=(k_e/tau)(partial tau/partial k_e). The paper's theorem gives |S_e|<=1 for every edge and sum_e S_e=-1, where the sum is over all directed transition rates. For neural routing parameters phi with k_e=exp(phi_e), the chain rule gives partial log tau/partial phi_e=S_e. Construct the transient generator Q, solve Q t=-1 for the MFPT vector t, and set tau=t_A. Sensitivities can be obtained by differentiating this linear solve. The useful mechanism is the exact control boundary: no single rate can produce more than one logarithmic unit of MFPT control, while all rates collectively obey a conserved sensitivity budget.

## Key formulas

- $$Q_{ij}=k_{i\to j}\quad(i\neq j),\qquad Q_{ii}=-\sum_{j\neq i}k_{i\to j},\qquad Qt=-\mathbf{1},\quad \tau=t_A,$$
- $$S_e=\frac{\partial\log\tau}{\partial\log k_e}=\frac{k_e}{\tau}\frac{\partial\tau}{\partial k_e},\qquad |S_e|\leq 1,$$
- $$\sum_e S_e=-1,$$
- $$k_e\leftarrow k_e\exp\!\left[-\eta\,\Pi_{\mathcal B}\!\left(\widehat{S}_e g_\tau+g_e^{\mathrm{task}}\right)\right],\qquad \mathcal B=\{s:\ |s_e|\leq1,\ \sum_e s_e=-1\},$$

## Implementation notes

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.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.