Deadline-Aware Fair-to-Greedy Router
Implementation & benchmark of arXiv:2607.13648 — Meeting Uncertain Threats with Feedback
Source paper: Meeting Uncertain Threats with Feedback arXiv:2607.13648 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
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.
Formulas
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.
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.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.