CS Paper Radar

Budgeted Admission from Timestamped Capacity Records in Shared Clusters

Andrew Bond, Syed Izhan Khilji

cs.DC math.PR ·submitted 2026-10-20 15:40 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.58
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

Prediction-Robust Service Deployment with Capacity-Aware Edge Admission

cs.DC ·2026-09-01 ·Hailiang Zhao, Ziqi Wang, Yifei Zhang, Mingyi Liu, Xinkui Zhao +2 more
theory similarity 0.57
Abstract

Edge platforms instantiate executable services close to users to reduce request-serving cost, but each instance incurs a one-time deployment cost and remains useful only for a finite time-to-live (TTL). The resulting online decision is both prediction-sensitive and capacity-coupled: an optimistic forecast can waste deployment cost, whereas a delayed decision misses the burst it is intended to serve. We study this problem under a common TTL cost model and propose CAPSUM, a capacity-aware admission policy with an elastic specialization, CAPSUM-E. In the local elastic setting, every node-service trace is exactly a variable-price Bahncard instance. This reduction lets CAPSUM-E inherit PFSUM's tight prediction-error-dependent ratio, including $2/(1+β)$ consistency and $1/β$ robustness for $β>0$. A redirect-aware variant preserves the same local deployment schedule. For finite-capacity nodes, CAPSUM combines size-scaled break-even tests, a utilization-dependent shadow price, and evidence-density eviction; we prove capacity feasibility, scale invariance, and exact agreement with CAPSUM-E under an elastic configuration. We implement an exact local offline dynamic program and compare against direct common-model baselines and documented source-derived adapters for EDP-A, OREO, and uEDC-L. Experiments cover controlled prediction error, three synthetic demand regimes, a causal predictor on a public Globus Compute trace, and joint scaling to 1,024 nodes and 10,000 services. Under the common model, CAPSUM reduces normalized cost by 33.7-42.9% relative to the best source-derived adapter across the synthetic regimes and by 45.5% on the sampled trace.

0.27

ZeroGate: Trust-Preserving Fast Paths for Governed AI Agent Runtimes

cs.AI cs.CRcs.DC ·2026-09-21 ·Zexun Wang
similarity 0.57
Abstract · 47 pages, 11 figures, 13 tables. Full research report with an ancillary archive containing reference code, raw experimental records, and off…

Moving authorization earlier can shorten an agent's dispatch boundary without removing authorization work. It can also admit an action whose payload, authority, or relevant state has changed. ZeroGate separates exact-action approval from durable local admission: an issuer signs a short-lived ActionPass, and a trusted runtime adapter reconstructs the final action before a local gate checks its binding and consumes its nonce. A SQLite transaction couples nonce consumption, applicable quota updates, and an admission receipt. We state a conditional decision-preservation proposition: successful local admission implies that a specified synchronous policy would authorize the same action at the admission point, provided approval is sound, all policy dependencies are represented and current, observations are faithful, and consumption is atomic. The implementation alone establishes neither current-world freshness nor exactly-once remote effects. Evaluation separates authored semantic fixtures, controlled concurrency and crash experiments, and an Azure Blob study comparing synchronous and prepared execution through the same issuer and gate. Both modes mint an exact-action pass; lifecycle latency includes preparation and prepared-batch dwell. Across 4800 cloud attempts, prepared worker-admission-to-dispatch p95 ranges from 9.802 to 11.374 ms, versus 25.018 to 334.000 ms synchronously, across the tested concurrency levels. Prepared mean complete lifecycle is longer at every level: the boundary improvement is not a net speedup. The contribution is an explicit revalidation contract, a durable reference boundary, and an auditable comparison of where authorization cost is paid, not a new cryptographic primitive or a universal performance frontier.

0.44

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

cs.AI ·2026-08-16 ·Fanzhe Wei, Li Liu
code/data similarity 0.57
Abstract · 29 pages (20 pages main text plus appendices), 8 figures, 10 tables. Companion paper: "What to Protect When You Quantize a Mixture of Expert…

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.

0.26

Before Agents Act: Assurance-Aware Semantic Scheduling for Evidence Acquisition in Distributed Systems

cs.DC cs.AIcs.CR ·2026-09-28 ·Jun He, Deying Yu
hot direction similarity 0.55
Abstract · 30 pages, 5 figures, 3 tables. Extended manuscript with formal proofs and operation catalogue

Tool-using agents can initiate consequential infrastructure changes, yet evidence required for admission may expire while other checks run or depend on a shared fault domain. We formulate evidence acquisition as joint witness selection and scheduling under quorum, diversity, freshness, deadline, and resource constraints. Assurance-Aware Semantic Scheduling (AAS) combines integer-program selection, dispatch-aware temporal scheduling, bounded diagnostic expansion, and receipt-aware repair. Formal results state the assumptions needed for dispatch-time freshness and finite diagnostic expansion. In three generated infrastructure workloads, AAS produces 1,075/1,200 valid candidates versus 647/1,200 for constraint-aware forward scheduling; stale candidates fall from 440 to 12. Paired sensitivity studies reuse the same instances and operation latency draws across parameter settings. A corrected timeout intervention finds 18/20 admissions with repair or full resynthesis versus 0/20 for a static plan, with lower committed cost when receipts are reused. On 20 constructed cases requiring a certified decomposition cut, refinement recovers an oracle-matching feasible plan every time. These are controlled simulation results; the bounded oracle shares a temporal search component, and transfer to deployed systems remains untested.

0.58

Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows

cs.CR ·2026-09-07 ·Alper Alimoglu
similarity 0.55
Abstract

Compound AI pipelines chain LLM calls, retrievers, and tools and are nondeterministic: sampling, model updates, and volatile tool responses make one input yield different outputs across runs. Such pipelines increasingly run across edge, cloud, and orbital nodes owned by no single party, whose optimizations discard intermediate results before inspection. Verifying reproduction there means tolerating nondeterministic outputs, a node that may not report honestly, and intermittent access to any shared record; existing work addresses at most two at once. We give a protocol covering all three: it commits digests of each stage's inputs, outputs, and context under a policy digest pinning the metric and threshold, anchors them without trusting the executing node, defers under partition, and decides a challenge on the median of $k$ re-executions, with no quorum. Where that procedure breaks is the main result. On a synthetic HotpotQA pipeline a calibrated fixed threshold accepts 44 of 45 honest reproductions and rejects 104 of 105 divergent pairs, yet lets same-input fabrication through in 27 of 29 trials at k=5, more samples being no help since sampling sharpens an estimate without moving it. Holding that metric and this pipeline's re-execution spread fixed, the binding constraint is the threshold rather than the sample size: one derived per execution detects 19 of 29 where the best constant matched to the same zero honest rejections reaches 9, rejects no honest commitment at k=5 though 3 of 15 at k=3, and catches 11 of 15 of an attacker built against it, which has to aim at a target drawn only after its commitment exists. That rule is measured rather than deployed.

0.25

Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete

cs.CC cs.DC ·2026-08-20 ·Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro
similarity 0.54
Abstract

Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

0.33

CheckCo: Checkpoint-Coordinated Load Balancing for Skewed Event Streams at Scale

cs.DC ·2026-11-17 ·Muhammad Anis Uddin Nasir, Reza Sadraei
similarity 0.54
Abstract · This paper is submitted to ICDE 2027 Industry and Application Track

Event streams are rarely uniform: a few dominant keys can generate orders of magnitude more events than the rest, overloading the workers that receive them and capping throughput. We present CheckCo, a checkpoint-coordinated load-balancing algorithm built on a dynamic oracle that estimates per-key frequencies from the live stream, with no prior statistics. Workers count events per key locally; at each checkpoint barrier, the counts are merged into a partitioning function that divides each key into a number of splits roughly proportional to its estimated frequency and packs the splits onto workers, and this function routes the next checkpoint window. We derive approximation bounds on the resulting load imbalance from classical scheduling results and bound its total key fan-out. On a production pipeline processing over 100 billion events per day, the most loaded worker receives only 9.8% more events than the average over a day (imbalance ratio 1.10), against 8.03 for key-based routing in simulation; in simulation, CheckCo also needs less than half the fan-out of earlier partitioners that reach comparable balance. Shifts in the key distribution are reflected in routing from the next checkpoint on, and the load stays balanced through job restarts.

0.17