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

Fanzhe Wei; Li Liu

cs.AIAug 16, 2026

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

Authors: Fanzhe Wei, Li Liu

Organizations: Metask Lab

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.

Figures & tables

Figure 1: The chain this paper machine-checks, and where it stops. Solid boxes and their connecting theorems are proved in Lean with no sorry ; dotted boxes are measured or open. Reading left to right: a per-step moment bound on the rounding draw becomes a bound on expected served-output total variation, Bernoulli domination feeds it to the anytime ledger, and Ville’s inequality closes the request. The lower row is the quantifier: exchangeable history sampling lifts a fixed-history bound to an unseen history, and the one box we cannot fill is that our population is a pool we constructed rather than runtime traffic. The propagation constants that a tensorized proof would need are measured and falsified , not bounded — which is why the top row is stated for an arbitrary step perturbation.

Model	Routing	Experts / top- $k$	Layers	Where it carries the paper
DeepSeek-V4-Flash-FP8	sqrtsoftplus, bias-corrected	$256$ / $6$	$43$	served-output bridge; anytime ledger; physical gate;
				$80$ -history conformal extrapolation
GLM-5.2 (FP8, W4A-FP8)	sigmoid, bias-corrected	$256$ / $8$	$78$	capacity–cost evaluation in the production stack
DeepSeek-V2-Lite	softmax, greedy	$64$ / $6$	$27$	router-margin certificate; flip $\to$ damage arms
Qwen1.5-MoE-A2.7B	softmax, greedy	$60$ / $4$	$24$	cross-model replication of the flip arms
Qwen2.5-7B	dense	—	$28$	activation-geometry precondition (dense control)

Table 1: Model coverage. The served-output line runs on a production-scale fine-grained MoE (

256

experts, top-

6

); the capacity evaluation on a second, architecturally distinct one; the routing-certificate arms on smaller greedy-top-

k

MoEs, treated as a same-family proxy (§ 3 ).

	union	cumloss, by budget $\tilde{B}$
		$5\!\times\!10^{3}$	$2\!\times\!10^{4}$	$5\!\times\!10^{4}$
budget exhaustion	$100\%$	—	—	—
fallback-to-exact rate (median)	$0.315$	$0.842$	$0.339$	$0.0079$
admission calls (armed)	$0$	$641{,}284$	$1{,}336{,}588$	—
judgment cost (s/request)	$344.5$	$339.5$	$357.1$	—
violations	$0$	$0$	$0$	$0$

Table 2: Dual-accounted admission, measured in a production serving stack. The union budget exhausts on every long request; cumulative-loss admission does not — what it buys is a monotone coverage/budget curve, not a free lunch, and each column must be read at its own budget: at

\tilde{B}=2\!\times\!10^{4}

the fallback rate (

0.339

) is worse than the union baseline’s

0.315

, and the pre-registered mechanism control recorded exactly that, so that arm’s adjudication is reported INVALID rather than quoted as a win. The

31.49\%\!\to\!0.79\%

drop is real but belongs to the

2.5\times

wider budget

\tilde{B}=5\!\times\!10^{4}

. Zero authorization violations across all arms. Full adjudication notes (cross-run calibers, non-monotone judgment cost, physical-gate non-vacuity) in Appendix F .

Figure 2: Coverage is bought, not found. Fallback-to-exact rate vs. cumulative-loss budget ( exploratory normalized-

z

arm), union baseline for reference: at Table 2 ’s budget the cumulative account is worse than union; the large gain belongs to a

2.5\times

wider budget.

Figure 3: Valid is not the same as informative. Fraction of captured reads on which each per-read bound exceeds

1

(certifies nothing) as mantissa bits are masked: the inherited e-form degrades from usable to useless; the gate

\tanh

law of ( 18 ) stays non-vacuous. This measurement motivated replacing the bound, not post hoc.

Figure 4: Escaping the

\ell_{\infty}

wall. The cumulative served total variation realized by the deployed compressor (top) against three sound upper bounds, per-request medians over eight requests on the armed model. The bound inherited from the per-read theory,

\tanh\|\Delta\mathrm{logit}\|_{\infty}

, is vacuous at

0.996

: it prices the worst logit coordinate, which sits on a low-probability token. Total variation instead prices mass movement , and both a mass-overlap bound (Bhattacharyya,

0.159

) and a pure-variance bound (sub-Gaussian,

0.230

) are non-vacuous and machine-checked. All quantities come from the same verdict artifact as the prose. Caliber: these are computed post hoc from paired exact and compressed logits, so the figure certifies the geometry — which functional can bound realized served TV at all — not a certificate the online witness emits today; supplying the same bound from the witness alone is Theorem 1 ’s a-priori branch, whose open constant we state in § 10 .

Route to the step budget	What it prices	Value
Global Lipschitz envelope (weights)	worst case over $\mathbb{R}^{d}$	$10^{221}$
Local operator norm, as a supremum	worst direction, rank $42$	$\sigma_{\max}\!\approx\!16.0$
Per-layer, per-token empirical MGF	assumes layer-local additivity	$0.0390$ (model-dep.)
Empirical Bernstein on it	worst-case range $e^{c}$	$7.64$ (vacuous)
Joint scalar, betting CS	the functional itself	$\mathbf{0.0322}$
on deployed rounding	no surrogate	$\mathbf{0.0552}$

Table 3: Five routes to the same number (the surviving one shown at two operating points). The first four fail for one reason stated four ways: each prices a worst case — over inputs, over directions, over a modelling assumption, over a range — while the theorem asks for an expectation over rounding draws. The bounded differences behind rows three and four we did measure (

c_{\max}=3.81

, per-token, gauge-centred), and they are diagnostics, not budgets: rows three and four rest on layer-local additivity, which our own saturation measurement rejects. Only the fifth route — the last two rows — bounds the quantity the theorem consumes.

Figure 5: The measurement that shaped the theorem. Per-layer propagation ratios

\rho_{\ell}=\|\Delta h\|^{2}/\|\delta\|^{2}

from random probes (

43

layers, noise floor exactly zero). A first-order response would make the two injection scales superpose; they separate by an order of magnitude at every layer, and the pre-registered linearity gate fails by a median factor of

14.1

(

86

layer–probe pairs, consistent with a saturated response:

\rho\propto\varepsilon^{-2}

gives

16

). We therefore do not report these as sound propagation constants; Theorem 1 is stated so no layer-local assumption enters it — the measurement rules out the cheap route to its constants, not the theorem.

Figure 6: Eighty histories, one certificate each. (a) Realized mean served-output shift, sorted: five orders of magnitude separate the extremes, so the choice of history decides a single-history answer. (b) Certificates, each threshold against its own caliber:

\mu_{\mathrm{cal}}

vs. Bonferroni-corrected upper bounds (

\bullet

\alpha^{\prime}=1.25\times 10^{-4}

\mu_{\mathrm{conf}}

vs. conformity scores (

\blacktriangle

\alpha=0.01

, no Bonferroni owed). Every held-out history clears both; held-out points never entered either threshold.

Figure 7: Same measurements, two instruments. Counting held-out pass/fail yields a single point; the order statistic yields a frontier, and the counting point is dominated on both axes. Moving along the frontier trades a looser certified budget for a smaller failure probability at no extra measurement.

Proved	Measured	Open, declared
per-step moment $\to$ request tail, ( 5 )–( 7 ); Doob form with no layer-local hypothesis; Bernoulli domination ( 8 ); conformal extrapolation ( 12 )	$\mathbb{E}_{\omega}[\mathrm{TV}]\leq 0.0552$ on deployed rounding; $16/16$ held-out histories certify; $133{,}849\times$ cross-history spread; $+3.8\%$ judgment cost	propagation constants (probe falsifies the first-order surrogate); $a_{q}$ and $w_{\mathrm{thr}}$ from one gated run; population $=$ our pool, not runtime traffic

Table 4: What this paper does and does not claim. The middle column is evidence, not proof; the right column is what a deployed certificate still needs. Keeping these three apart is the discipline the paper argues for, and four of our own retractions came from letting them blur.

Arm	acc	clean	risk ledger	fallback
FP8 safe (endpoint)	$1.000$	✓	none (no compression)	—
aggressive, no gate (endpoint)	$1.000$	✓	none	—
gated, union budget	$1.000$	✓	exhausts ( $99.4\%$ burned)	$59.3\%$
gated, cumulative (phys)	$1.000$	✓	bounded ( $99.97\%$ peak)	$56.3\%$
gated + shadow audit	$1.000$	✓	as union + reconciliation	$57.5\%$

Table 5: Five-arm equal-quality table on the serving stack (DeepSeek-V4-Flash, tp8, three independent restarts per arm, medians; zero authorization violations anywhere). Caliber: the two endpoints bound the axis and are not co-axial with the gated arms; the gate acts on the write-side mantissa-mask layer while the packed compression itself runs identically in all four compressed arms; quality is stated only under the provably-clean caliber (zero evictions and zero ring-page recycling, both directly counted); fallback is reported as a rate because absolute event counts vary with batch composition. Throughput is a different caliber (concurrent clients) and is deliberately not a column of this table — and we disclose why: under mixed concurrent workloads (a benchmark warm-up preceding evaluation) the prototype’s c4-tier sparse-read path exhibits a localized defect (deep-position retrieval degrades while stored content verifies intact against the reference pool), traced to unresolved key-space translations and under repair. The quality column here is measured without such preceding traffic and is unaffected.

	Per-	Sound	Adaptive-	In serving
Line of work	request	(not avg.)	valid	stack
PTQ / second-order weighting	✗	✓	—	✗
GPTQ, AWQ, QERA, YAQA, WaterSIC
MoE quantization (expert/router-aware)	✗	✗	—	✗
MoEQuant, GEMQ
Dynamic-precision serving	✓	✗	✗	✓

Table 6: Why the gap is structural rather than incremental. “Adaptive-valid” means the guarantee survives the feedback of quantized state into later queries — a union budget over a pre-declared event count does not, which is the deficit § 4 removes. “—” marks lines that make no per-step claim, so adaptivity does not arise. The routing column is absent by design: no prior line certifies routing, and § 3 is our evidence that certifying it would not have helped.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

GLM-5.2, identical hardware	FP8	W4AFP8	ratio
Aggregate throughput, $C{=}128$ (tok/s)	$1{,}789$	$1{,}834$	$1.03\times$
Aggregate throughput, $C{=}512$ (tok/s)	$1{,}827$	$1{,}869$	$1.02\times$
KV-cache capacity (resident tokens)	$291{,}968$	$1{,}087{,}808$	$3.7\times$
Errors, full $1..128$ sweep	$0$	$0$	—

Appendix

Table 7: Throughput is flat to within single-run spread at both concurrencies — we report the spread rather than claim equivalence, since no restart confidence intervals were collected — while configured resident-token headroom grows

3.7\times

. On this short-context workload neither arm reaches its KV wall. Table 8 pressure-probes the headroom and reports what it does and does not convert to. The capacity figure here is configuration-derived, not an OOM limit.

	no prefix reuse	session reuse
$26$ k-token requests, GLM-5.2, W4AFP8 vs FP8	(worst case)	(agent-shaped)
Configured KV capacity	$3.73\times$
$\rightarrow$ concurrent requests	$2.0\times$	$2.24\times$
$\rightarrow$ warm-prefix hits	— (none)	$1.93\times$
$\rightarrow$ throughput	$\mathbf{0.96}$ – $\mathbf{1.01\times}$	$\mathbf{1.07}$ – $\mathbf{1.27\times}$
$\rightarrow$ TTFT (p50)	—	$1.08$ – $1.20\times$ ( $0.92\times$ at $C{=}256$ )

Appendix

Table 8: What

3.7\times

of KV capacity converts to, pressure-probed in two workloads. Left : every request is a fresh slice of text, so the prefix cache never hits (peak cached tokens

2{,}560

and

0

against a

26{,}000

-token prompt). FP8 runs at

100\%

pool occupancy and W4AFP8 at

58\%

, so the capacity does buy

2\times

the in-flight requests — and buys nothing in throughput, because at this prompt length the work is prefill-bound and the GPU is already saturated. Right : each session keeps its own long context and reuses it across turns, the shape a coding agent has. Now capacity decides how many sessions stay cache-warm : FP8 is pinned at

10

–

11

resident sessions per rank (its pool holds

291{,}968/26{,}500=11.0

) at

100\%

occupancy, while W4AFP8 holds

23

–

24

54\%

. Every link in the chain attenuates, and the last one attenuates hardest — what a hit saves is prefill, while steady-state throughput is still set by decode and compute. Two caveats we state rather than bury: the TTFT gain reverses at

C{=}256

, where W4AFP8’s larger running batch leaves each request less compute, so the throughput is bought with per-request latency; and each session completes only

\approx 1.9

turns inside the measurement window, so

1.19\times

is a lower bound on what a real multi-turn session would show — we do not extrapolate it. Protocol: per-level prefix namespaces and a

90

s warm-up per level; without both, prefixes carry across levels and the measurement reports a spurious

1.58\times

Model	Stream	$\rho_{90}$	Held-out	Verdict
Qwen2.5-7B	attn-in	$0.034$	$0.829$	concentrated
Qwen2.5-7B	o-proj-in	$0.0332$	$0.742$	concentrated
Qwen2.5-7B	mlp-in	$0.0444$	$0.660$	gray
DeepSeek-V2-Lite	attn-in	$0.0044$	$0.946$	concentrated
DeepSeek-V2-Lite	o-proj-in	$0.0264$	$0.844$	concentrated
DeepSeek-V2-Lite	moe-in	$0.0444$	$0.792$	concentrated

Appendix

Table 9: Gate W2-a: activation second-moment spectra with held-out validation.

\rho_{90}

= fraction of eigendirections carrying

90\%

of energy (prefill, per-layer median).

Arm	Hypothesis under test	Verdict	Key number
Gate quantization	router survives INT4	killed	$63.2\%$ flips
Upstream margins	exact gate suffices	killed	$93.7\%$ binding
Flip $\to$ damage	flips predict damage	dissociated	RR $0.71$ – $0.84$
Natural text	damage is average-case	killed	$\Delta$ NLL $0.0002$
Value-transport	condemned reads rescuable	killed	$0$ / $1{,}528$
Served-output tail	the object that survives	adopted	TV $0.118$ /bd. $0.159$

Appendix

Table 10: Every design hypothesis we tested, including the ones aimed at our own proposals. The companion paper’s five pre-registered arms eliminate routing invariance as the certified object; the served-output tail is what survives, and is what Theorem 1 bounds. The last row is the measurement that falsified the first-order propagation surrogate and thereby fixed the form of the theorem. Numbers are the same artifacts cited in the text.

Figure 8: What the instrument costs in histories, at the marginal caliber and in the large-population limit. Number of exchangeably sampled histories needed to certify a given bound on next-history failure, splitting the budget evenly between the two terms; the Clopper–Pearson curve is the zero-event requirement at

99\%

confidence. A training-conditional guarantee costs more, and a finite pool costs more still — our own

80

-history run reaches

0.0254

marginally but

0.0933

conditionally. The two follow different scaling laws, so the gap widens as the target tightens — which is the long-run argument for the order statistic, independent of the factor we measure at

80

histories (

\star

Explore similar work

Sep 28, 2026cs.LG

Preferent Compression Bounds Are Tight

The lack of rigorous safety and performance certificates remains a key bottleneck to the deployment of modern learning-based methods. Sample compression has recently emerged as a powerful tool for deriving such certificates, with particularly sharp bounds available for algorithms satisfying a so-called preference property -- also known as stability in the learning theory literature. These bounds find direct application across domains as different as the Scenario Approach, Pick-to-Learn, and Support Vector methods. However, whether they are tight has remained an open problem. In this paper we resolve this question affirmatively and show that the state-of-the-art bound for preferent compressions is provably tight. We establish this by exhibiting an explicit construction based on the uniform distribution and order statistics that attains the bound in the limit. Along the way, we also provide a considerably shorter and more accessible proof of this bound, requiring only elementary counting arguments and no infinite-dimensional duality.

Dario Paccagnan, Marius Tirlea

Department of Computing, Imperial College London, London, UK

Statistical Learning Theory Generalization Bounds Algorithmic Stability

Ask PDF

Oct 9, 2026stat.ML

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity

\boldsymbol{k}

, defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order

O(\sqrt{\ln N/N})

above

\boldsymbol{k}/N

. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level

1-δ

, the risk is bounded with probability at least

1-δ

\frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right),

uniformly over all possible values of

\boldsymbol{k}

. Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term

\boldsymbol{k}/N

is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the

O(1/\sqrt{N})

convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the

O(1/\sqrt{N})

rate.

Simone Garatti, Marco C. Campi

Dipartimento di Elettronica, Informazione e Bioingegneria - Politecnico di Milano, piazza Leonardo da Vinci 32, 20133 Milano, Italia. · Dipartimento di Ingegneria dell’Informazione - Universit`a di Brescia, via Branze 38, 25123 Brescia, Italia.

Statistical Learning Theory Information-Theoretic Generalization Bounds

Ask PDF

Jul 30, 2026cs.AR

WitCert: Sound Runtime Risk Observability and Gating for KV-Cache Quantization

KV-cache quantization is validated today by offline benchmark averages; a deployed system cannot tell whether compression is damaging the request it is serving right now. We give it a provably sound runtime meter -- a "DTrace for KV quantization": a per-(layer, head, step) upper bound on the total variation between exact and compressed attention. The meter has two tiers: a deterministic band-norm-witness bound, sound for any cache-preserving black-box quantizer and for any query (adaptive-safe, worst-case Cauchy--Schwarz plus RoPE band-unitarity), and a tighter probabilistic certificate for a controlled subtractively-dithered INT8 quantizer under an explicit request-level failure budget (stated for non-adaptive queries; core theorems machine-checked in Lean 4). Three results. Observability: the meter enters SGLang through an env-guarded patch, and any scheme registered as one tensor function is measured in live serving. Repair: meter-driven gating -- risk-ranked where the witness is saturated, certified where it is informative -- empirically restores the quality floor at benchmark scale, e.g. raw-cast fp8 from 22.8 back to 79.7 on hard RULER tasks with the difference from uncompressed bounded at

[+0.0,+0.8]

by a paired test. Analysis: aggressive schemes survive on cross-layer error cancellation, not per-step fidelity -- in a 28-layer sweep, no single layer's pollution alone loses anything (0/28) -- and the certified int8 cache serves

1.88\times

more KV tokens at the same memory in SGLang. All artifacts, guards, and the Lean development are released at https://github.com/metask-ai/witcert-kv-certificates; every number regenerates from the shipped artifacts by one command.

Fanzhe Wei, Li Liu, Ziyang Wang +1

Metask Lab

KV Caching Memory-Efficient Inference Formal Verification Attention Quantization KV-Cache Quantization Runtime Verification

Ask PDF