CS Paper Radar

Pricing the Risk of Runtime Compression: Anytime-Valid Admission and a Served-Output Law for Compressed Serving State

Fanzhe Wei, Li Liu

cs.AI ·submitted 2026-08-16 15:37 UTC · v1
code/data

Abstract

Runtime compression of serving state trades quality for capacity with no priced guarantee: systems adapt precision on load signals with no soundness statement, and certified approaches budget request-level risk by a union bound over a pre-declared event count. We show the union budget exhausts on every long request in a production serving stack (100% of requests), and replace it with an anytime-valid, physically accounted ledger whose bound holds at every one of 352,333 admission calls on live traffic and which, in a pre-registered held-out confirmatory round, halves the exact-fallback rate at matched risk (0.30 -> 0.14) -- coverage is bought at a price the account states. We then price the remaining distance from the certified witness to what a user experiences: a machine-checked design law (TV <= tanh(a_q w_thr)) turns the served-TV target into a threshold knob, and a three-layer audit of its instantiation -- an operator-norm query envelope measured 1.5x from tight, a measured-ellipsoid replacement for the Cauchy-Schwarz ball that buys nothing (0.89x, held-out sound), and the gate's operating point (~700x) -- localizes the entire 1064x gap to the operating point, a price the law now states rather than an unknown. A priced bound is worth nothing on a request one has not seen, so the third link is the quantifier: exchangeable extrapolation across 80 serving histories replaces binary conformal prediction's vacuous certificates with order-statistic bounds that discriminate (0.41 against 0.51 calibration risk). All probabilistic kernels are Lean 4-checked (228 exported theorems, no sorry); which object deserves this machinery at all is settled empirically in a companion paper that adjudicates -- and rejects -- the natural alternative of certifying routing. What ships is an account: risk you can spend, a gap you can read off a law, and a bound that survives the request you have not seen.

Comment
29 pages (20 pages main text plus appendices), 8 figures, 10 tables. Companion paper: "What to Protect When You Quantize a Mixture of Experts", submitted concurrently. Lean 4 development (228 exported theorems, no sorry) and all artifacts released

Closest papers

Nearest neighbours by meaning across the whole index.

Protocol Compression Changes Which Party Pays: Bilateral Cost in Cross-Organization LLM Agent Communication

cs.CL ·2026-09-05 ·Janghoon Lee
similarity 0.58
Abstract · 30 pages, 3 figures, 27 tables

Agents that talk across organizations exchange long messages billed by the token. A shorter notation therefore looks like a saving that costs nothing but an agreement to use it. Recent work reports the saving is conditional. Compressed notation can instead raise total tokens by 8% to 11% over a JSON baseline, when parsing failures force extra model calls. That is measured for one payer. Between two organizations neither side can install a decoder at the other end, and each pays under its own tokenizer, price, and cache state. We measure both sides. A preregistered token-level study covered 198 content-matched item pairs across six vendors, for 2,376 native-usage cells. We then overlay an English baseline, runtime schema negotiation followed by compression, and injected-schema compression on a two-party procurement bargain with an exactly enumerated feasible set. The overlay covers 1,053 completed dialogues of a 1,215-cell grid across 3 model pairs, plus a 405-dialogue rerun of the negotiated condition. Compression amplifies cross-vendor cost dispersion by a factor of 1.078, with a 95% CI of [1.066, 1.091], and two vendor pairs reverse which endpoint is cheaper. Runtime negotiation succeeds as a protocol and fails as a bargain. The parties agree a schema in 121 of 135 headline dialogues, none of them the schema we would have supplied. They settle the task in only 9 of those dialogues, and they reach impasse in 106 of them. The negotiated sessions average 10.8 turns against 17.6, and cost 52% of the English total because sessions end sooner, not because the handshake is repaid. Break-even horizons run from 20 to 70 turns, the low end only under the conditional accounting, and all of them lie above every observed English session. On one cross-vendor pair both parties keep about half their cost. On the other the receiving party pays more at a high cache-hit rate.

0.23

Spot Markets for AI Inference: Dynamic Capacity Allocation and Pricing on a Shared Accelerator Fleet

eess.SY ·2026-11-08 ·Quanyan Zhu
similarity 0.58
Abstract · 39 pages, 12 figures, 4 tables

Inference providers size their accelerator fleets for the interactive peak and sell spare capacity through fixed discounts, such as batch tiers at half price. However, inference differs from conventional cloud capacity in four respects: capacity depends on the latency tier through batching, moving weights between models is slow and costly, spot demand can wait until its deadline, and power can bind. In this paper, we develop a framework for dynamic capacity allocation and pricing of AI inference on a shared accelerator fleet. We consider a provider that serves several models under a power cap and sells each model in an interactive tier with a speed promise and in a spot tier for preemptible work with a deadline. In each period, the provider chooses how many replicas of each model to keep loaded and what spot price to quote. We show that one interactive token displaces a fixed number $ρ_m>1$ of spot tokens, and that the optimal spot price lies midway between the interactive price and the effective cost of capacity in the deadline window, which is close to the prevailing half price only when the fleet is slack. We further show that a spot tier raises the optimal reliability of the interactive tier, and that placement should follow persistent demand shifts while prices absorb transients. Building on these results, we design a model predictive controller based on a linear program with explicit approximation bounds, which solves each period in milliseconds. Numerical experiments on a simulated week with a measured daily demand profile, a flash crowd, and a grid curtailment show that the controller raises profit by 7.4% over fixed half-price practice, captures 93% of the gain available with perfect forecasts, keeps the interactive promise through both events, and leaves spot buyers better off.

0.28

Cap-and-Track: Optimizing LLM Inference Request Dispatch Across Shifting Capacity

cs.LG ·2026-11-18 ·Benjamin Novotny, Doug Szeto, Chang Wang, Shicheng Chen, George Zhihua Yuan +4 more
similarity 0.57
Abstract · 20 pages, 6 figures, 2 tables. Includes appendices

A fixed dispatch rate for LLM inference becomes stale as serving fleets resize and request sizes change. Generative output length is unknown at admission, and shared provider pools can lose capacity. We present Cap-and-Track, a design for asynchronous inference across provider capacity and internal GPUs. Meta's traffic shaper implements Cap-and-Track for post and live-video understanding. Refusals signal the backend's current admission ceiling. Durable priority queues hold excess work outside execution, including refused requests for retry. Cap is a fail-fast admission check at the saturated resource that refuses work before a long wait. Using only those refusals, the Track dispatcher probes upward and backs off. It follows the ceiling without output-length prediction or a fleet-level rate to retune. In a concurrent same-traffic production A/B, the shaper ran per-replica Cap plus Track. It served a classifier on 43% fewer H100s than its queued, fixed-rate precursor, though lower-priority work waited longer at backfill peaks. In steady-capacity real-engine replay, Track ran within 1% of the goodput of a fixed rate tuned above measured capacity, with about a quarter of that rate's refusal share. The shaper carries more than 300 million online requests and hundreds of terabytes of media a day. During a backfill, it handled 1.1 billion requests in its busiest 24 hours. Lessons include keeping queues inside inference engines just long enough to fill batches, steering dispatch by capacity refusals alone, keeping dispatch stateful, and sizing fleets by how long low-priority work can wait.

0.28

Seal, Then Sample: Sampled Layerwise Proofs for Verifiable LLM Inference from GPT-2 to 70B

cs.CR cs.IR ·2026-09-23 ·Youki Lim, Sam Yong
code/data similarity 0.57
Abstract · 15 pages, 4 figures, 8 tables. Raw experiment logs and data tables: https://github.com/TrueOpen/slp-experiments

Verifying outsourced language-model inference requires a precisely identified computation and an audit whose cost a service can afford. We present Sampled Layerwise Proofs (SLP), a protocol and prototype that commits the boundary activations of every chunk of an inference trace, absorbs all commitments before any challenge is drawn, and then proves a verifier-selected subset of chunks together with the chunks that bind the prompt and the answer. Audit coverage becomes a runtime parameter over one set of commitments: on a TinyLlama-1.1B trace, proving seven of 47 chunks takes 22.0% of the time and 6.8% of the proof size of proving all 47. Because proof cost is dominated by weights rather than tokens, SLP packs concurrent requests into one trace under a block-diagonal causal mask and binds the prompt and answer of each request to its slot. Twelve packed requests are proved in 181.9 s, 6.5 times less than twelve separate proofs at the measured single-proof cost, and a simulated service proves twelve requests at 30.6 s per request with 0.6 s of verification each, rejecting a tampered answer. Disk-backed integer weights and streamed polynomial commitments let a single Llama-2-70B run complete on a 2 TB CPU host: 163 chunks sealed, five proved, a 4.34 MiB proof in 1,259 s, verified in 46.3 s without the weights. The proven object is a fixed-point canonical model; we trace a severe fidelity loss to the residual-stream bit width, repair it with an LLM-aware observer, and measure 84.8-84.9% argmax agreement with the floating-point reference over 334,705 WikiText-2 test positions. The limits are stated as precisely: guarantees cover proven chunks only, a fixed invalid chunk in the 70B setting is covered with probability 3/161, a manifest-only Fiat-Shamir schedule can be ground at 12.5 ms per attempt and needs an externally ordered challenge, and all measurements use a test reference string.

0.59

Budgeted Admission from Timestamped Capacity Records in Shared Clusters

cs.DC math.PR ·2026-10-20 ·Andrew Bond, Syed Izhan Khilji
similarity 0.57
Abstract

A cluster admission gate can receive a capacity record that no longer matches current schedulability. We study one exogenous binary schedulability unit under a bound on the joint probability of admission and unavailability. For a symmetric Markov state, we derive the stationary admission frontier for a fixed observation delay and apply finite likelihood allocation to a delay-tagged delivered record. A one-sided exact binomial endpoint calibrates each fitted policy, and exact enumeration confirms the per-policy confidence target in every tested parameter cell. A separate deterministic guard charges every unresolved admission against the realized allowance and bounds unavailable-state admissions at every prefix under truthful outcome feedback. An executable admission procedure composes the allocation and guard. The controlled system binds source sampling, NATS delivery, randomized admission, Kubernetes objects, and API-derived outcomes in one append-only record. Independent audit finds no missing event, identity mismatch, or state mismatch in the completed functional block. A separate CPU request-accounting check preserves Job and Pod identity across an unschedulable-to-complete transition.

0.27

Finite-Calendar Admission and Deadline-Aware Pruning for UWB Audio

eess.AS cs.MM ·2026-10-17 ·Fengyun~Zhang
unusual similarity 0.57
Abstract

Isochronous ultra-wideband (UWB) audio transport must deliver a complete service data unit (SDU) before its presentation deadline; fragment reception rate and aggregate throughput do not directly characterize this objective. We formulate admission and online service over a periodic calendar of finite exchange opportunities, explicitly accounting for fragmented SDUs, bounded attempts, calendar alignment, and timing uncertainty. For equal-duration, freely assignable opportunities, an interval-demand condition characterizes finite-job reservation feasibility, and an earliest-deadline-first construction realizes a feasible reservation. A separate necessary capacity bound identifies loads that cannot sustain complete-SDU delivery even with no transmission errors. For online overload control, we study a deadline-aware policy that discards an SDU when its outstanding fragments exceed the remaining eligible opportunities. Across 3,456 replicated scheduling runs and 432 supplemental sensitivity runs, pruning raises eight-stream burst-loss timely completion from 45.441\% to 59.399\%, a paired difference of $13.958\pm2.080$ percentage points (pointwise 95\% interval). At four streams, round robin instead attains slightly higher completion, while heavy overload causes pronounced per-stream imbalance. A finite design enumeration and an evaluated multi-stream fragmentation envelope quantify the interaction among scheduling, payload overhead, and capacity. These findings distinguish provable admission conditions from online deadline salvage and expose the aggregate-throughput versus per-stream-service tradeoff in UWB audio scheduling.

0.22

The Shadow Price of Intelligence: Quality Degradation in LLM Inference as a Supply Chain Problem

cs.AI math.OCcs.PF ·2026-08-25 ·Elioth Sanabria
similarity 0.55
Abstract · 28 pages, 12 figures. Numerical instances calibrated to public benchmark data for five LLM providers

Large language model providers are compute constrained, and a common response to congestion is to degrade service. A degraded answer fails with some probability, and a failed answer either returns as a retry or departs as churn, destroying LTV on an unaccounted ledger. We model inference allocation as a newsvendor whose stockout cost is churned lifetime value, a geometric retry multiplier in which the recycled product is dissatisfaction, and a two-regime transient fluid queue whose arrival rate is made endogenous by retries. Statically, there is a regime in which a cheaper model saves energy per initiated task while consuming strictly more capacity per initiated task, so the discount inverts when capacity binds. Dynamically, a reactive throttle fired during a surge can cross an ignition threshold beyond which it manufactures more traffic than it sheds, and a release rule set below the degraded equilibrium converts a transient surge into a permanent degraded regime. With heterogeneous customers, throttling is a transportation problem in retry-inflated load whose optimal policy rations intelligence by critical ratio, and whose dual, the shadow price of intelligence, prices a marginal query by class and by hour. Under congestion, throttling is not a cost lever but a demand lever.

0.26

VelServe: Taming Decode Jitters in LLM Inference with Tail-Calibrated Scheduling

cs.AI ·2026-11-13 ·Ishaan Datta, Alind Khare, Koushik Kumar Dey, Ratnesh Jamidar, Anand Kumar Singh
similarity 0.55
Abstract

Interactive LLM services must meet latency service-level objectives (SLOs) for the time to first token (TTFT) and the time between tokens (TBT), as streaming and soft real-time applications require predictable token delivery. We identify decode jitters in both aggregated and disaggregated serving. A jitter delays every request in the batch, and long responses span hundreds of steps, so even rare overruns cause many SLO violations. In aggregated serving, SLO-aware schedulers set each step's prefill budget until its predicted latency just meets the TBT target, leaving no room for mispredictions or host stalls. Disaggregation meets average TBT targets at a cost in capacity, yet the steps that admit new requests still run late. We present \sysname, a scheduler that calibrates how much prefill work each decode step carries using the measured tail of its own iteration latency. The SLO determines how rare a late step must be, and \sysname leaves enough headroom in each iteration to prevent overruns and meet the target decode latency. This headroom slows prefill, so \sysname serves the shortest waiting prompt first. When TTFT deadlines grow with prompt length, the long prompts it delays have the most time to spare. Under disaggregation, it spaces admissions so that no request waits on more slow admission steps than its P99 target allows. On three attention families and varying workloads, \sysname sustains 2.4--2.9$\times$ the SLO goodput of the strongest baseline on Qwen3-8B and DeepSeek-V4-Flash, and at least 4.4$\times$ on DeepSeek-V2-Lite. With prefill and decode disaggregated on eight GPUs, \sysname meets the SLO for more than twice as many requests as state-of-the-art baselines.

0.19