# Free-boundary neural halting

- ID: 2175
- Canonical URL: https://synthcore.org/idea/2175/free-boundary-neural-halting
- API JSON: https://synthcore.org/api/idea/2175.json
- API Markdown: https://synthcore.org/api/idea/2175.md
- Verification status: unverified
- Source: [arXiv:2608.12291](https://arxiv.org/abs/2608.12291)
- Category: architecture
- Solves: speedup, accuracy, sample-efficiency
- ML areas: transformer, training, inference-speedup
- Math tags: probability, stochastic-processes, optimization, dynamical-systems
- Ratings: usefulness 6/10; difficulty 5/10; novelty 5/10

## Idea description

Replace a fixed confidence-threshold early-exit rule with a finite-horizon optimal-stopping policy over the model's evolving posterior confidence. The controller stops when the calibrated expected terminal error is no greater than the cost plus expected value of executing another neural block, permitting time-dependent and nonmonotone stopping regions.

## Mathematical statement

The paper defines the win-martingale $\Pi_s=\mathbb{P}(\theta=1\mid\mathcal{G}_s)$, where $\theta\in\{0,1\}$ is the final outcome and $\mathcal{G}_s$ is the information observed by time $s$. For a binary neural classifier, let $p_t\in[0,1]$ be the calibrated probability of class 1 after block $t$, let $T$ be the maximum number of blocks, and let $c_t\geq0$ be the measured cost of executing block $t+1$. Immediate Bayes classification has expected 0-1 loss $g(p)=\min(p,1-p)$. Let $P_t(\mathrm{d}p'\mid p)$ be an empirically estimated transition kernel for the next-block confidence. The discrete optimal-stopping value satisfies the Bellman obstacle recursion $V_T(p)=g(p)$ and $V_t(p)=\min\{g(p),c_t+\mathbb{E}_{p'\sim P_t(\cdot\mid p)}V_{t+1}(p')\}$. The stopping set is $\mathcal{S}_t=\{p:g(p)\leq c_t+\mathbb{E}[V_{t+1}(p')\mid p]\}$; the continuation set is its complement. This comparison, rather than an imposed monotone threshold, is the transferable free-boundary mechanism. A differentiable approximation can use $\operatorname{softmin}_\tau(a,b)=-\tau\log(e^{-a/\tau}+e^{-b/\tau})$ and a stopping probability based on the Bellman advantage $A_t(p)=g(p)-c_t-\mathbb{E}[V_{t+1}(p')\mid p]$.

## Key formulas

- $$\Pi_s:=\mathbb{P}(\theta=1\mid\mathcal{G}_s),\qquad \theta\in\{0,1\}.$$
- $$V_T(p)=g(p),\qquad V_t(p)=\min\left\{g(p),\ c_t+\mathbb{E}_{p'\sim P_t(\cdot\mid p)}\left[V_{t+1}(p')\right]\right\},\qquad g(p)=\min(p,1-p).$$
- $$\mathcal{S}_t=\left\{p\in[0,1]:g(p)\leq c_t+\mathbb{E}_{p'\sim P_t(\cdot\mid p)}[V_{t+1}(p')]
ight\},\qquad \mathcal{C}_t=[0,1]\setminus\mathcal{S}_t.$$
- $$\widetilde V_t(p)=-\tau\log\left(\exp\left[-g(p)/\tau\right]+\exp\left[-\left(c_t+\mathbb{E}[V_{t+1}(p')\mid p]\right)/\tau\right]\right).$$

## Implementation notes

(1) Integration point: attach a lightweight classification head after every Transformer block. For a binary task, convert each head logit to a calibrated probability $p_t=\sigma(z_t)$; for a multiclass task, use $p_t=\max_k\operatorname{softmax}(z_t)_k$ and replace $g(p)$ by $1-p$. Evaluate the stopping decision after block $t$, before paying the compute cost of block $t+1$.

(2) Pseudocode:
```
run the full model on a calibration set and save p[t] after every block
fit P_t(.|p) from pairs (p[t], p[t+1])
make a confidence grid p_grid
V[T,p] = g(p)
for t = T-1,...,1:
    continuation[p] = c[t] + E_{pprime~P_t(.|p)} V[t+1,pprime]
    V[t,p] = min(g(p), continuation[p])
    stop[t,p] = (g(p) <= continuation[p])
for a test example:
    run block t and compute p_t
    stop if g(p_t) <= c[t] + E[V[t+1,pprime] | p_t]
```
Estimate $P_t$ with confidence bins, Gaussian-kernel regression, or a small conditional density model. Use measured milliseconds or FLOPs for $c_t$, and multiply all costs by a tunable scalar to trace the accuracy-compute Pareto curve. For end-to-end learning, define $A_t(p)=g(p)-c_t-E[V_{t+1}(p')|p]$, set $h_t=\sigma(\alpha A_t(p_t))$, and train with straight-through or Gumbel-sigmoid halting; initially keep the policy detached from the backbone to avoid unstable joint optimization.

(3) Computed directly from the mathematics: the posterior-state representation, terminal Bayes loss, Bellman recursion, and stopping/continuation sets. Estimated empirically: confidence transition kernels $P_t$, calibration of every exit head, block costs $c_t$, and conditional expectations over next confidence. Temperature-scale each exit head on held-out data, because the terminal-loss formula $g(p)$ assumes calibrated posterior probabilities.

(4) First cheap experiment: train a six-layer small Transformer on SST-2 or AG News with exits after every layer. Compare full-depth inference, a standard fixed confidence-threshold exit, and the Bellman policy. Sweep the cost multiplier and report accuracy, average executed layers, wall-clock latency, and empirical objective $\mathbf{1}[\hat y\ne y]+\sum_{t<\tau}c_t$. The main success criterion is at least 20% fewer executed layers at matched accuracy, or higher accuracy at matched average layers. Include an ablation forcing one global monotone confidence threshold; improvement from independently learned $\mathcal{S}_t$ sets would test the paper's prediction that time-dependent, potentially nonmonotone boundaries can outperform conventional early-exit rules.

## Disclaimer

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