# Deadline-Aware Fair-to-Greedy Router

- ID: 872
- Canonical URL: https://synthcore.org/idea/872/deadline-aware-fair-to-greedy-router
- API JSON: https://synthcore.org/api/idea/872.json
- API Markdown: https://synthcore.org/api/idea/872.md
- Verification status: unverified
- Source: [arXiv:2607.13648](https://arxiv.org/abs/2607.13648)
- Category: architecture
- Solves: speedup, accuracy, stability
- ML areas: moe-routing, inference-speedup, training
- Math tags: probability, optimization, stochastic-processes, control-theory
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Use deadline objectives to train or control a router that explicitly trades off completion probability against completed work by a fixed horizon. Begin with fair allocation for robust exploration, then anneal toward a feedback-greedy rule once per-item difficulty estimates have sufficient evidence.

## Mathematical statement

The paper studies deadline-based objectives, including maximizing clearance probability by deadline $\tau$ and maximizing effective assignments before deadline, in addition to minimizing clearance time. Under the geometric completion model, an item with failure probability $q_i$ survives $k$ independent allocated attempts with probability $q_i^k$ and completes by then with probability $1-q_i^k$. For an allocation vector $a=(a_1,\ldots,a_n)$ satisfying $\sum_i a_i=C\tau$, the independent completion probability for all items by the deadline is $\prod_i(1-q_i^{a_i})$. The adaptive neural version uses this quantity as a differentiable scheduling objective, with $q_i$ predicted from the item’s current state. The fair baseline is $a_i\approx C\tau/n$; the greedy controller selects slots using the marginal improvement $\Delta_i(a_i)=q_i^{a_i}(1-q_i)$. A confidence-gated interpolation uses fair allocation when posterior uncertainty is high and greedy allocation when difficulty estimates are stable. Here $n$ is the number of active items, $C$ is calls per round, $\tau$ is the deadline, $a_i$ is item $i$’s total calls, and $q_i$ is its estimated per-call failure probability.

## Key formulas

- $$\Pr(L_i>k)=q_i^k,\qquad \Pr(L_i\le k)=1-q_i^k$$
- $$P_{\mathrm{all}}(a;\tau)=\prod_{i=1}^{n}\left(1-q_i^{a_i}\right),\qquad \sum_{i=1}^{n}a_i=C\tau$$
- $$\Delta_i(a_i)=\left(1-q_i^{a_i+1}\right)-\left(1-q_i^{a_i}\right)=q_i^{a_i}(1-q_i)$$
- $$a_i^{\mathrm{mix}}=(1-\lambda)a_i^{\mathrm{fair}}+\lambda a_i^{\mathrm{greedy}},\qquad \lambda=\operatorname{clip}\left(\frac{\operatorname{Var}(\hat q)}{\operatorname{Var}(\hat q)+\epsilon},0,1\right)$$

## Implementation notes

Use this as a controller for adaptive computation with a hard deadline of tau rounds. At round t, the model produces a state embedding h[i] for every active item and a small difficulty head outputs p_hat[i]=sigmoid(wᵀh[i]+b), with q_hat[i]=1-p_hat[i]. Maintain Beta-count statistics or an exponential moving average to calibrate q_hat from actual completion feedback. Compute the fair allocation by distributing C slots evenly among active items. Compute the greedy allocation by repeatedly assigning each slot to the active item with the largest score q_hat[i]**a[i]*(1-q_hat[i]); optionally multiply this score by an urgency or value factor. Interpolate the two allocations using lambda: when posterior uncertainty or recent prediction disagreement is high, lambda should be near zero so the router explores fairly; when estimates are stable, lambda approaches one. During training, use either straight-through top-k assignment or a soft relaxation with softmax(score/temperature), while evaluation uses hard integer slots. Optimize a deadline loss such as -log(prod_i(1-q_hat[i]**a[i])+delta), plus a penalty for violating the call budget. Start with CIFAR-100 using an adaptive classifier or a small language-model verifier task with heterogeneous difficulty strata, C fixed calls per round, and tau in {2,4,8}. Compare fair, always-greedy, confidence-only, and uncertainty-gated policies at equal FLOPs. The expected signal is a higher fraction completed by tau and lower p95 compute at equal accuracy, while the mixture should avoid greedy instability when difficulty estimates are noisy.

## Disclaimer

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