Systems that route each query to one of several language-model strategies (a small model answering directly, a larger model, a model that reasons step by step before answering) usually charge each strategy a fixed cost, typically its theoretical floating-point operation count (FLOPs). That hides two facts. First, how long a step-by-step answer takes is random and heavy-tailed. The same query can yield a 150-token or a 2,000-token reasoning trace, much as the same SAT instance can take a millisecond or an hour. Second, a generated token costs far more wall-clock time per FLOP than a prompt token, because generation on a GPU is limited by memory bandwidth rather than arithmetic. We propose a router that predicts, for each query and strategy, the full distribution of output length. It converts that distribution to a wall-clock latency distribution with a calibrated hardware model, and it assigns strategies to maximize the chance a query is answered correctly before its deadline.
The core idea fits in two sentences. Under a latency deadline, a strategy's useful accuracy is the probability that it is both correct and finished in time, and that quantity depends on the tail of the runtime distribution, not its mean. Estimating that tail requires modeling both the instance-level randomness of reasoning length and the ways real GPU latency departs from FLOPs.
Core Claim
The closest existing work is CONCUR, which routes queries across Qwen-2.5 and LLaMA-3.1 models with and without chain-of-thought. It uses per-strategy predictors and a knapsack-style dynamic program over a global budget. It measures cost in theoretical FLOPs and concedes that KV-cache handling, memory bandwidth, and accelerator latency make real costs deviate. It also treats each strategy's cost as a point estimate. Our claim is that fixing only the cost unit, by swapping FLOPs for profiled mean latency, is not enough.
We write $T_{q,s}$ for the random number of tokens strategy $s$ generates on query $q$, and $C_{q,s}$ for correctness. The router should maximize
$$\sum_q \Pr\big(C_{q,s(q)}=1,\; \ell_{s(q)}(T_{q,s(q)}, B) \le \tau\big),$$
where $\ell_s$ is the hardware latency model mapping output length and concurrent batch load $B$ to seconds, and $\tau$ is the deadline. Correctness and length are correlated because long traces are disproportionately wrong. Traces cut off at the deadline yield no answer. For both reasons, this objective can rank strategies differently from mean-cost routing whenever length has large spread within a query. We expect the gap to be largest at tight p95/p99 service-level targets, on hard math and multi-hop queries, and under batched serving, where a static batch finishes only when its longest member does.
Research Program
The work has three components, each borrowing from a different line of prior work.
Length-distribution predictor. The first component is a distributional predictor of generated length, conditioned on query and strategy. It follows DistNet, which maps solver-instance features to lognormal or inverse-normal runtime-distribution parameters by likelihood, and Bayes DistNet, which adds a survival-function term so that timed-out runs still contribute information. Generations truncated at the maximum-token limit are exactly such right-censored observations, so we reuse the survival term. We depart from both papers in two ways. The research file notes they assume a single-peaked parametric family, while chain-of-thought lengths may be bimodal (answer quickly versus reason at length), so we use a small mixture of lognormals. We also predict length jointly with correctness, as a two-head model with correctness conditioned on a length bucket, because the objective needs their joint probability. Training data come from drawing several generations per query per strategy. Statistical Regimes and Runtime Prediction shows that single runs give unstable rankings, so one sample per query would be too noisy.
Calibrated hardware latency model. The second component converts length to time. This is where the FLOPs-latency discrepancy enters as a measured quantity rather than an assumption. ShuffleNet V2 shows memory traffic dominates runtime for low-arithmetic operations. Towards Latency-aware DNN Optimization shows GPU latency moves in discrete steps as work fills or partially fills waves of thread blocks, so it is not linear in FLOPs. Compute-Optimal Is Not Cluster-Optimal builds an operator-level model calibrated by kernel microbenchmarks. We follow that paper's method: benchmark prefill and per-token decode latency on a grid of prompt length, KV-cache length and concurrent batch size, per model and per GPU, then interpolate within the measured steps rather than across them. The research file notes that such models are specific to their hardware. We therefore calibrate on two GPU types and report how much a model calibrated on one mispredicts the other.
Deadline-aware assignment. The third component replaces CONCUR's budget knapsack with an assignment that maximizes the objective above under a p95 or p99 deadline. For static batches, the batch deadline constraint involves the maximum of member latencies, which we estimate by Monte Carlo sampling from the predicted distributions. Yggdrasil supplies the guiding lesson: replacing an algorithmic proxy (average accepted draft length) with a hardware-profiled latency objective changed which designs win, yielding up to 3.98x over SpecInfer. Yggdrasil targets single requests, whereas our setting is batched.
The motivation for tails rather than means comes from two sources. Heavy-Tailed Distributions in Combinatorial Search shows that real-time failures in search are driven by rare, very long runs. Empowering Adaptive Early-Exit Inference with Latency Awareness is the closest dynamic-inference method with a latency constraint, and it constrains only average latency. Our method differs from that paper in constraining a percentile and in modeling concurrent load.
Baselines
The naive reference points are the best single strategy and the always-cheapest strategy, each served under the same deadline with truncation at $\tau$. CONCUR reports the best single strategy, Qwen-7B-CoT, at 74.3% average in-distribution accuracy at 41.63 FLOPs (CONCUR).
The strongest existing method is CONCUR itself, which reports 75.2% average accuracy at 36.50 FLOPs on its in-distribution suite of MMLU, GSM8k and 2WikiMultiHop. No reported result found on Lacuna for latency-constrained or tail-constrained routing on these benchmarks. We will therefore reimplement CONCUR on our strategy pool, confirm we land near its reported accuracy-FLOPs point, and then evaluate it under wall-clock deadlines. All routers share the same queries and cached generations, the same text embeddings, the same number of training samples per query, and the same hyperparameter-search budget.
The fair version of the obvious fix is CONCUR with FLOPs replaced by profiled mean latency per strategy. A stronger variant predicts each query's expected output length with a point regressor and passes it through our hardware model.
Two ablations isolate our ingredients. The first keeps our distributional predictor but uses a FLOPs-proportional time model instead of the calibrated hardware model. The second keeps the hardware model but predicts only mean length, with no censoring and no correctness-length coupling. An oracle that knows each query's realized length and correctness bounds the attainable gain. Following Bias in Algorithm Portfolio Performance Evaluation, we will score the oracle on held-out samples rather than the ones it selected on, so that it is not overly optimistic.
Beating the baselines means strictly higher deadline-met accuracy than the strongest non-oracle baseline at matched p95 and p99 latency, across three seeds. It also means lower service-level violation rates at matched accuracy.
Why not just…?
Why not just keep FLOPs, as CONCUR does? FLOPs charge a prompt token and a generated token nearly alike, yet decode is bandwidth-bound. Prior work shows FLOP rankings can invert on hardware: higher-FLOP dense models run faster in Searching for Fast Model Families on Datacenter Accelerators, and FLOP-optimal MoE sparsity loses 0.031 nats to a cluster-optimal point under a fixed wall-clock budget in Compute-Optimal Is Not Cluster-Optimal. Our first decisive check measures whether such inversions occur among the routing strategies. If they do not, the hardware model is unnecessary and we will say so.
Why not just profile each strategy's mean latency offline and plug it into the knapsack? This fixes the unit but not the spread. A lookup by strategy or input size cannot capture the within-query variability that The Backdoor Key documents for same-size solver instances. It also cannot capture the correlation between long traces and wrong answers. The mean-latency CONCUR baseline tests this directly.
Why not just predict each query's expected output length? This is the real threat. If the length of a strategy's output on a given query has low spread, then a good point estimate plus the hardware model captures nearly all the benefit, and the distribution adds only complexity. We will measure the within-query coefficient of variation of chain-of-thought length from repeated samples. If it is small, or if the point-length baseline matches our method at p99, we will abandon the distributional claim and report the hardware-model result alone. DistNet's finding that joint distribution fitting beats separate summary-statistic predictors was obtained on CPU solvers, so it is suggestive but not transferable evidence.
Why not just cap output tokens? A cap bounds the tail but silently converts slow correct answers into wrong ones. Our objective already includes truncation, so a cap tuned per strategy is a special case we will include within the mean-latency baseline.
Proposed Experiments
We use CONCUR's strategy pool (Qwen-2.5 and LLaMA-3.1 models, direct answering versus chain-of-thought). We use its in-distribution benchmarks MMLU, GSM8k and 2WikiMultiHop, and its out-of-distribution transfer sets HotpotQA, GPQA and SVAMP. We draw 8 to 16 generations per query and strategy. Serving runs on two GPU types, A100 and A40 as in Yggdrasil's evaluation, under both single-request and batched load, with deadlines swept from loose to tight.
Metrics are deadline-met accuracy, p95 and p99 latency, and violation rate. For the predictor we report negative log-likelihood, quantile coverage, and hardware-model prediction error; ScalePlan's under-15% MFU error serves as a reference level.
Three results would decide the proposal. The first is whether strategy rankings by FLOPs and by measured latency invert on these benchmarks. The second is whether within-query length dispersion is large enough to separate our method from the point-length baseline. The third is whether that separation widens, as predicted, at tighter percentiles and larger batches, and whether it holds out of distribution, where Bayes DistNet's uncertainty estimates should flag queries for conservative routing.
References
- CONCUR: A Framework for Continual Constrained and Unconstrained Routing
- Neural Networks for Predicting Algorithm Runtime Distributions
- Bayes DistNet - A Robust Neural Network for Algorithm Runtime Distribution Predictions
- Statistical Regimes and Runtime Prediction
- ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design
- Towards Latency-aware DNN Optimization with GPU Runtime Analysis and Tail Effect Elimination
- Compute-Optimal Is Not Cluster-Optimal: Systems-Aware Scaling for Sparse Mixture-of-Experts
- Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding
- Heavy-Tailed Distributions in Combinatorial Search
- Empowering Adaptive Early-Exit Inference with Latency Awareness
- Bias in Algorithm Portfolio Performance Evaluation
- Searching for Fast Model Families on Datacenter Accelerators
- The Backdoor Key: A Path to Understanding Problem Hardness