# UCB Drift Router for Cheap-or-Expert Inference

- ID: 457
- Canonical URL: https://synthcore.org/idea/457/ucb-drift-router-for-cheap-or-expert-inference
- API JSON: https://synthcore.org/api/idea/457.json
- API Markdown: https://synthcore.org/api/idea/457.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.06017](https://arxiv.org/abs/2607.06017)
- Category: dynamics
- Solves: speedup, stability, accuracy
- ML areas: moe-routing, inference-speedup, rl, batching
- Math tags: optimization, probability, dynamical-systems, online-learning
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace a fixed confidence threshold in cascaded inference or mixture-of-experts routing with a queue-aware UCB-DPP controller. The controller sends an input to a cheap model when its optimistic estimated success is sufficiently high and the expert backlog is large, while escalating uncertain or high-value inputs when the penalty for an error dominates congestion. This should reduce expensive-model utilization without allowing latency or escalation queues to diverge.

## Mathematical statement

For task type k in [K], arrivals have probability lambda_k, the cheap model has unknown success probability p_k, Q_{t,k} is the fallback queue length, A_{t,k} is the number of new fallback jobs, and S_{t,k} is completed expert service. Queue stability is represented by Q_{t+1,k}=[Q_{t,k}+A_{t,k}-S_{t,k}]^+, where [z]^+=max(z,0). After n_k observations with s_k successes, estimate cheap-model success using hat{p}_k(t)=s_k(t)/max(1,n_k(t)) and the optimistic upper confidence bound U_k(t)=min(1,hat{p}_k(t)+sqrt(2 log(t)/max(1,n_k(t)))). For candidate routing action a, drift-plus-penalty minimizes V times immediate compute cost minus quality reward plus the backlog-weighted expected new fallback work, sum_k Q_{t,k} E[A_{t,k}|a]. Here V>0 controls the quality/compute tradeoff. This comes from the quadratic Lyapunov function L(Q)=1/2 sum_k Q_k^2: large queues increase the score of actions that create additional fallback work, providing negative feedback. UCB optimism prevents under-explored request types from being permanently assigned to the wrong route.

## Key formulas

- $$Q_{t+1,k}=\left[Q_{t,k}+A_{t,k}-S_{t,k}\right]^+,\qquad [z]^+=\max\{z,0\}.$$
- $$\hat p_k(t)=\frac{s_k(t)}{\max\{1,n_k(t)\}},\qquad U_k(t)=\min\left\{1,\hat p_k(t)+\sqrt{\frac{2\log t}{\max\{1,n_k(t)\}}}\right\}.$$
- $$a_t=\arg\min_{a\in\mathcal A_t}\left\{V\big(c(a)-r(a)\big)+\sum_{k=1}^{K}Q_{t,k}\,\mathbb E\left[A_{t,k}\mid X_t,a,U(t)\right]\right\}.$$
- $$L(Q_t)=\frac12\sum_{k=1}^{K}Q_{t,k}^2,\qquad \Delta L_t\approx\sum_{k=1}^{K}Q_{t,k}\,\mathbb E\left[A_{t,k}-S_{t,k}\mid a_t\right].$$

## Implementation notes

Integrate the controller at the inference gateway immediately after request classification and before model execution. Partition requests into K buckets using an existing difficulty classifier, prompt-length bin, predicted value, or domain label. For every bucket maintain n[k], s[k], and a virtual backlog q[k]. Increment n[k] whenever the cheap model is evaluated; increment s[k] when its answer passes a task-specific verifier, delayed expert label, or large-model judge. At request t compute ucb[k]=clip(s[k]/max(1,n[k]) + sqrt(2*log(t)/max(1,n[k])), 0, 1). Enumerate candidate actions such as cheap-only, cheap-then-expert, and direct-expert. For cheap-then-expert, estimate fallback probability as 1-ucb[k]; for cheap-only, use the estimated probability of an uncorrected failure as its quality loss; for direct-expert, use zero fallback arrivals but higher compute cost. Score each action as V*(compute_cost - quality_reward) + sum_k q[k]*expected_fallback_arrivals[k], and select the minimum. After execution update q[k]=max(0, q[k]+observed_fallback[k]-completed_expert_service[k]); service can be measured per request or per fixed time window. The formulas determine the confidence radius, queue recursion, and objective; empirical calibration supplies costs, rewards, verifier labels, and service capacity. First test on a GSM8K or CIFAR-100 cascade with a small model and larger verifier, comparing fixed confidence thresholds, greedy cheap-only routing, and UCB-DPP at matched accuracy. Record expert-call rate, p95 latency, queue length, accuracy, and cumulative compute. Success means at least 20% fewer expert calls at equal accuracy while queue length remains bounded under sustained load.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a toy UCB-DPP cascade simulator with queue recursion, DPP routing scores, UCB updates, stability sweeps, and baseline comparisons. The math checks succeeded: queue drift changed sign at lambda*fallback=service, the observed DPP switching backlog was 121 versus predicted 120, and UCB radii followed the predicted n^-1/2 scaling exactly. However, the router never escalated in the mini-experiment because optimistic UCB made fallback risk zero; it matched cheap-only at 65.0% accuracy rather than preserving expert-level quality, so the promised practical win was not demonstrated.

### Mechanism check

- Verdict: Built a toy UCB-DPP cascade simulator with queue recursion, DPP routing scores, UCB updates, stability sweeps, and baseline comparisons. The math checks succeeded: queue drift changed sign at lambda*fallback=service, the observed DPP switching backlog was 121 versus predicted 120, and UCB radii followed the predicted n^-1/2 scaling exactly. However, the router never escalated in the mini-experiment because optimistic UCB made fallback risk zero; it matched cheap-only at 65.0% accuracy rather than preserving expert-level quality, so the promised practical win was not demonstrated.
- Confidence: 9/10
- Limitations: Synthetic Bernoulli toy rather than GSM8K/CIFAR or a production cascade. It does not test multiple task buckets, delayed verification, batching, real latency, calibrated confidence, or a corrected quality-aware UCB policy.

## Artifacts

- [report.md](https://synthcore.org/code/231/report.md)
- [results.json](https://synthcore.org/code/231/results.json)
- [router_experiment.py](https://synthcore.org/code/231/router_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/231)

## Disclaimer

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