Budget-Obedient Hysteretic Gating for LLM Inference

This preprint specifies and analyzes BOSC (Budget-Obedient Spark Controller), a lightweight, audit-first controller for LLM inference/serving that enforces operational budgets for tail latency, time-to-first-token (TTFT), and KV-cache memory. Unlike many dynamic routing / conditional-compute methods that optimize averages, BOSC treats budget obedience as a verifiable contract under distribution shift, partial telemetry loss, cancellation gaming, and misconfiguration. BOSC uses a pre-decision difficulty signal (constant-cost or amortized O(1)) to decide whether to permit optional “spark” compute (e.g., speculative decoding components, extra verification, additional routing). Budget compliance is tracked with virtual queues (dual variables) updated from telemetry using fail-closed imputation and explicit eligibility sets. A hysteretic gate with cooldown suppresses chattering, keeping controller overhead O(1) per decision event and controller state O(1) per active request. Because this document is a theory + specification paper (not an empirical benchmark report), it prioritizes operational completeness and reproducibility: a normative telemetry contract (metric semantics, join rules, denominators), a wrapper-enforced actuator interface with SAFE latch semantics, and a deterministic offline verifier (replay) designed to avoid floating-point drift and to detect contract violations. A key hardening contribution is an exact reflected-queue certificate (Skorokhod reflection) that turns queue levels into a verifier-checkable worst-suffix-window excess diagnostic. The paper also formalizes constructive infeasibility witnesses: under an explicit action-dominance envelope, SAFE-only segments with excess violations certify that the corresponding budget cannot be met within that envelope on that segment. The result is an audit-grade control/specification layer intended to sit atop modern LLM serving stacks (batching, scheduling, disaggregation) while making budget accounting, fail-state behavior, sampler denominators, and cross-log consistency externally verifiable from telemetry.