Truthful Length Reports for LLM Schedulers When Predictors Fail Unevenly Across Users

Large language model (LLM) serving systems increasingly reserve memory and order their queues before a request runs, using a prediction of how long its answer will be. MAPS runs a small length predictor on the user's own device while the cloud processes the prompt. It turns that prediction into a statistical upper bound and serves short jobs first. The reported gains are large, but they depend on clients telling the truth. In a shared service, anyone who can edit the reported bound can claim a short answer and jump the queue. The standard remedy from queueing theory is to demote jobs that overrun their declared size, with just enough probability that lying stops paying. That remedy has a hidden fairness problem. Some users are honest but still overrun often, because the predictor was trained on data unlike their requests. Those users get punished for the predictor's error.

The genetics literature describes this failure precisely. Instruments built on one population, usually European cohorts, lose their link to the true cause in other populations and quietly bias the result (GSMR; ethnicity-specific diabetes testing). A length predictor fine-tuned on English instruction data is an instrument of the same kind: the prompt features it relies on may predict length poorly for other languages or task types. This proposal asks how to keep a client-assisted scheduler truthful when predictor error differs across user groups. The answer we test is to calibrate the bound separately within each group. When every group's honest bound is overrun at the same rate, one demotion probability deters lying in every group at once, and honest minority users stop paying for predictor error.

Core Claim

In the money-free queue of Incentive Compatible Queues Without Money, a job that exceeds its declared size is sent to the lowest priority with probability $b$. That paper proves the set of $b$ values that make honest reporting optimal is a single connected interval. That interval is computed from one joint distribution of true sizes and reports.

With several user groups, each group $g$ has its own interval $[b_g^{lo}, b_g^{hi}]$. The lower end is the smallest penalty that stops members of $g$ from under-reporting. The upper end is the largest penalty before honest members are driven to over-report as insurance against their own predictor's overruns. A single system-wide penalty works only if

$$ \max_g b_g^{lo} \;\le\; b \;\le\; \min_g b_g^{hi}, $$

that is, only if the groups' intervals overlap.

Our first claim is that, under the pooled calibration MAPS uses, this overlap is often empty. The upper end is set mainly by how often honest reports overrun, and pooled calibration lets that rate differ a lot between well-served and poorly-served groups. Our second claim is that group-conditional conformal calibration fixes this. Conformal calibration turns raw predictions into bounds with a guaranteed coverage rate, and doing it per group guarantees each group's honest bound is exceeded with probability at most $\alpha$. Equalizing honest overrun rates should pull the intervals together and restore a common truthful $b$.

We do not expect equal overrun rates to fully equalize the intervals. The incentive also depends on how far jobs overrun and on each group's job-size distribution. How much of the gap calibration closes is the main empirical question.

Research Program

The theory work extends the SOAP analysis of Grosof and Mitzenmacher to a population that is a mixture of groups. Each group has its own joint distribution of true size and report. We will characterize each group's truthful interval and bound the gap between intervals in terms of differences in the groups' overrun rates and overrun magnitudes. The target result is a sufficient condition for the intervals to overlap that group-conditional coverage at level $\alpha$ provably meets, under a stated assumption about overrun tails. Grosof and Mitzenmacher analyze a single server with discrete size classes, so the theory stays in that setting. Multi-server behavior is handled by simulation, not claimed as a theorem.

The systems work builds the mechanism into a MAPS-style disaggregated serving simulator, where prompt processing and answer generation run on separate machines. It has four parts. The first is a client report of a length bound. The second is a server-side group-conditional conformal layer that rescales reports using held-out residuals from each group. The third is up-front reservation of cache memory for the rescaled bound. The fourth is shortest-bound-first queueing with demotion of any job that overruns its bound.

Groups are defined by features the server can observe without collecting protected attributes, such as prompt language and task type. We also test a label-free variant that clusters requests in the predictor's feature space. This matters because group-conditional methods are only as good as their group definitions.

The ancestry-bias literature constrains the design as well as motivating it. The lesson of cross-ancestry MR on glaucoma is that conclusions should be checked separately in each population rather than pooled. Our evaluation therefore reports every incentive and latency metric per group, not only in aggregate.

Baselines

The naive reference point is first-come-first-served queueing with memory reserved for the maximum output length. It gives no one a reason to lie and no one any benefit from prediction. It sets the latency ceiling and memory cost that everything else must beat.

The strongest existing method is MAPS as published (MAPS): client-side predictors, pooled conformal calibration and shortest-job-first routing, with no penalty for misreporting. MAPS reports a 42.6% reduction in average end-to-end latency and up to 84.8% lower P99 latency versus vLLM and SGLang on BurstGPT and ShareGPT with six GPUs. It is the strongest competitor because it is the system whose honesty assumption we remove.

We run MAPS twice. The first run uses honest clients, where it should win or tie. The second uses a fraction of best-responding clients who minimize their reported bound. Beating MAPS means matching its latency within a few percent under honest clients while keeping honest users' latency close to the honest-world level when manipulators are present.

The second baseline is MAPS plus a single demotion probability $b$ tuned on pooled data, which applies Grosof and Mitzenmacher directly. This is also the ablation that isolates our key ingredient, group-conditional calibration. We tune its $b$ by grid search using the same simulator time and the same calibration split we use for our own method.

The third baseline is a hard cutoff: requests that exceed their bound are stopped or re-queued from scratch. It is the obvious rule-based alternative.

All methods share traces, predictor weights, GPU count and tuning budget.

Why not just…?

Why not just use first-come-first-served, which removes any reason to lie? Because it gives up the scheduling gain that motivates prediction in the first place. MAPS's reported latency reductions over schedulers that do not use length predictions, and Grosof and Mitzenmacher's finding that trust-based policies beat FCFS even with imperfect estimates, both say the loss is large. We will measure the loss directly in our setting rather than assume it.

Why not just predict length on the server so clients cannot lie? This is a real alternative, and we include it as a variant. It does not remove the need for a penalty. Users can still write prompts that look short but produce long answers, so overruns still need a consequence, and the uneven-error problem is unchanged because a server predictor is equally biased toward its training distribution. Server-side prediction also gives up the overlap with prompt processing that MAPS gains by running the predictor on the client. We run the full mechanism with a server-side predictor too. If the group-conditional penalty helps equally there, that supports the claim that the contribution is in the penalty, not the placement of the predictor.

Why not just tune a separate penalty for each group? If each group's interval is known, per-group $b$ values trivially restore truthfulness, so this is a serious competitor. It is also exploitable: users can switch to the group with the mildest penalty, for example by changing prompt language. The per-group intervals must also be re-estimated whenever the predictor changes. Group-conditional calibration keeps one penalty and moves the group adaptation into a coverage guarantee that can be recomputed cheaply. We run the per-group-$b$ variant with a group-switching attacker. If it performs as well as our method under switching, we will report that the simpler scheme suffices.

Why not just stop jobs that overrun? Harsh penalties push honest users to over-report as insurance, especially users the predictor serves badly. That wastes the memory reservation that prediction was meant to shrink. The hard-cutoff baseline measures this reservation waste per group.

Proposed Experiments

We use ShareGPT conversations to supply prompts and true lengths and BurstGPT arrival patterns to supply burstiness, both as in MAPS. Predictors are fine-tuned on Alpaca as MAPS does, which deliberately creates an English-instruction training bias. The groups are ShareGPT's non-English and non-chat requests. We will first report how the predictor's under-prediction rate differs across groups; if the differences are negligible, the premise fails and we say so.

The strategic-user model lets a chosen fraction of clients in each group pick the report that minimizes their expected latency given the policy. Metrics are average and P99 latency for honest users within each group, the latency a best-responding user gains by lying, the rate at which honest users in each group are demoted, preemption counts, and reserved-but-unused memory.

The first decisive check is whether the per-group truthful intervals, estimated by simulation, fail to overlap under pooled calibration but do overlap under group-conditional calibration. That result is the core claim. A null result would falsify it.

The second check is whether our method brings the gain from lying below a small threshold in every group while holding pooled latency near honest-world MAPS.

The third check is whether the label-free clustering variant recovers most of the benefit of the labeled groups. This decides whether the method is usable where group labels are unavailable.

Grosof and Mitzenmacher report no mean response-time numbers, so no reported result was found on Lacuna for their policy on LLM traces. We will produce that number ourselves.