CS Paper Radar

Generator-Independent Runtime Assurance under Partial Observation

Guangxi Wan, Yongbo Xie, Yuqi Liu, Qingwei Dong, Qingxin Li, Hongfei Bai, Peng Zeng

cs.AI ·submitted 2026-09-05 11:40 UTC · v1
theory

Abstract

Proposal-based controllers---learned policies, language-model planners, and other black-box \emph{generators}---are increasingly deployed behind runtime verification gates. We ask when the closed-loop safety guarantee decouples from the generator. The prevailing per-candidate certification pattern does not compose: under retry or best-of-$k$ selection a per-candidate false-admission level $α$ can inflate to $1-(1-α)^{k}$. Our main theorem shows that \emph{simultaneous setwise soundness}---certifying a set of admissible proposals containing no nonviable action---is necessary and sufficient for generator-independent \emph{admission soundness}, the worst case over all generators of executing a nonviable proposal equalling the probability of setwise failure; together with a design-time certificate and a no-bypass rule it is sufficient for \emph{contract safety}, with violation bound $Γ+\sum_t\varepsilon_t+η$ invariant under arbitrary, even adversarial, replacement of the generator. A second theorem bounds every admission mechanism under partial observation: for a fixed probing and admission policy, if two state hypotheses whose information laws lie within total-variation distance $δ$ require different safe decisions, then $\abar+β+δ\ge1$. A sequential risk ledger makes the guarantee implementable with time-uniform confidence tubes, and shows that deterministic admission computations concentrate all statistical risk in state estimation. Simplex-style runtime assurance and control-barrier-function filtering are recovered as degenerate cases.

Closest papers

Nearest neighbours by meaning across the whole index.

A Contract-Grade Verifier for LLM-Generated GPU Kernels, and a Native Blackwell Backward for the Gated-Linear-Recurrence Family

cs.LG cs.ARcs.DC ·2026-08-13 ·Rishi Shah, Rishav Shrestha
benchmark similarity 0.68
Abstract · 20 pages, 3 figures. Also archived at doi:10.5281/zenodo.21563213

Systems that generate GPU kernels with language models report high correctness rates. Those rates come from a single loose test: run the kernel on a few random inputs at one fixed shape and accept it if the output is close to a reference. A kernel can pass that test and still be silently wrong. It can return an ordinary number where the true answer is a NaN or an infinity, differ from run to run, break when the shape changes, or accumulate in fp16 where the reference keeps an fp32 total. We build the instrument that checks correctness properly: a contract-grade verifier of twelve adversarial gates, each a property a correct kernel must satisfy, several of them tolerance-free, so no choice of threshold can explain a failure away. Aimed outward, the verifier audits 2,638 machine-generated kernels that a public system's own harness had already accepted as correct. It finds 39.5% broken beyond any tolerance argument and 62.1% carrying at least one violation. The field's standard test accepts 1,487 kernels the verifier rejects, against only 14 the other way. We defend the finding four independent ways: a 7/7 positive control, a threshold-calibration sweep, 98.5% agreement with the reference benchmark's own correctness code, and a stratified hand-audit. Aimed inward, the verifier judges a kernel of our own: the first native Blackwell tcgen05 training backward for the gated-linear-recurrence (GDN) family, including the reverse-state stage the field still runs on a fallback. We establish its correctness independently, against a double-precision oracle, and train five family members through it. The correctness signal behind reported progress in kernel generation is far weaker than the numbers suggest, and a set of tolerance-free contracts would close most of the gap.

0.48

Certifying Almost-Sure Reachability in Unknown MDPs

cs.LO cs.AI ·2026-10-13 ·S Akshay, Suguman Bansal, Gaurav Mahla
theory similarity 0.66
Abstract

{\em Specification-Guided Reinforcement Learning (RL)} has largely concerned itself with \emph{learning} an optimal policy against a formal specification in an unknown {\em Markov Decision Process (MDP)}. We take up the dual question. Given a policy already in hand, can one \emph{verify} that it is correct against a formal specification in an unknown MDP, using sampling access alone? Such a question arises naturally in safety-critical systems. We investigate it for the {\em almost-sure reachability property}, whose correctness is witnessed by a {\em ranking supermartingale (RSM)} certificate. Our first finding is negative. In the absence of any further information about the MDP, one can neither learn such a certificate nor verify a candidate one with probabilistic guarantees. On the positive side, we show that, under a mild restriction, a known lower bound $p_{\min}$ on nonzero transition probabilities, a correct certificate \emph{can} be learned with PAC-style guarantees. To the best of our knowledge, this is the first study of learning and verifying certificates for almost-sure reachability in unknown MDPs from sampling access alone. Finally, our experiments show that the $p_{\min}$-based sufficient condition, while sound, is conservative: the learned certificate often remains valid on the true MDP even when the condition fails.

0.07

No finite rulebook can certify every safe program: an impossibility theorem for gatekeeping AI agents

cs.AI cs.CR ·2026-11-09 ·Tomas Perez-Acle
theory similarity 0.66
Abstract · 34 pages, 4 figures

An AI assistant writes small programs, and a gatekeeper must decide, from the code alone, whether each one may run. Suppose the rules are fixed: never perform a forbidden action, never let the output depend on a secret, always answer eventually. Can two rulebooks, one listing what is allowed and one listing what is not, both be complete, if every rule must be backed by evidence that a machine can check in finite time? We prove that they cannot. Checkable evidence can only establish what a finite record settles, and ``never'' and ``eventually'' are never settled by a finite record. For prohibitions the failure is one-sided: every violation can be caught by watching, but no safe program can be cleared for good. For confidentiality and responsiveness, neither side can be. We characterise exactly which rules about visible behaviour evidence can confirm, and we show that any sound rulebook of $n$ bits omits a compliant program of about $n$ bits. A time limit makes everything checkable, but only by running the program for essentially the whole limit, so a finite machine is not a feasible one. Finally, we show what a gatekeeper can still guarantee: not a verdict on every program, but a checkable list that contains everything it must allow and nothing it must refuse. Simulations on 2.2 million random programs and on self-referential adversaries show that the obstruction is adversarial rather than typical, and that the one error a longer test never removes is the liveness part of confidentiality.

0.16

Certify, Then Select: Viability-Aware Runtime Steering of Frozen Diffusion Policies

cs.RO cs.LGeess.SY ·2026-11-14 ·Angelo Moroncelli, Loris Roveda
theorycode/data similarity 0.64
Abstract · Under review

Diffusion policies, which generate short action sequences by denoising random noise, are a leading way to learn robot skills from demonstrations. Once deployed, they meet constraints the demonstrations never contained, and retraining for each is impractical. A safety filter edits the policy's action to satisfy them, but the edit ignores the task, and a large edit can leave the policy where it cannot continue. We propose CAST (Certified Action Selection at Test time): draw a few action chunks from the frozen policy, certify each with a barrier condition, and execute the certified chunk that a learned value ensemble ranks highest. We prove that a certified step is safe whatever the critic does; that, whenever a certified sample exists, the executed chunk stays within log N nats of the policy conditioned on feasibility, while a safety-filter projection can be singular to it; and that an exact closed-loop identity splits the gain of ranking into availability, spread and the critic's target. Certifying the next chunk is not enough: a generative controller can have safe actions available now and none later. We characterise the safe control authority of a frozen policy under finite sampling, and CAST-V preserves it through a policy-conditioned viability, estimated with a model under a finite-sample guarantee or learned from the controller's own logs (CAST-VL). On robomimic manipulation, a planar quadrotor, a MuJoCo humanoid and a unicycle, with frozen policies, CAST raises joint task-and-constraint success above the output filter in nearly every setting; certifying before ranking is decisive where a filter's edit is large, and viability removes most dead ends that one-step certification cannot see. Project page: https://clmoro.github.io/cast.

0.25

Limits of Statistical Assurance for Embodied and Agentic AI under Adaptive Adversaries

cs.CR cs.LGstat.ML ·2026-10-13 ·Inderjeet Singh
similarity 0.63
Abstract · 66 pages, 10 figures

Finite safety assessments cannot exclude an adversary that preserves unattacked behavior until certification and activates afterward. We characterize this limitation for embodied and tool-use AI. An adversary that matches the complete observation law until observable, irrevocable certification and retains intervention access afterward attains $v\mathbb{E}[(n-S_0)_+]$ expected post-certification events over $n$ trials, where $v$ is the active event probability and $S_0$ the unattacked certification time. The result covers adaptive and privately randomized evaluators. Switching at certification is exactly optimal for a fixed likelihood-ratio test under memoryless, event-increasing interventions without a binding intervention budget. A positive clean-certification requirement forces linear worst-case expected excess when intervention raises event rates over an authorized deployment horizon, even if certification is deferred to the deadline. In simulated RoCo collaboration, switching yields commanded-separation violations in 34 of 36 post-certification episodes. Preregistered randomized AgentDojo trials estimate 1.98 additional security violations per four-task continuation (95% interval [1.67, 2.29]). An adversarial language-model controller infers hidden certification from noisy evaluation receipts and times intervention accordingly. With permanent revocation, a mixture likelihood-ratio monitor bounds cumulative excess above a prespecified reference rate at square-root order, up to logarithmic factors, on every sample path. A single fixed alternative can permit linear expected excess under stationary attacks. Against a controller observing the monitor's rule and statistic, live mixture monitoring reduces violations from 12.00 to 3.81 per 24 assigned task opportunities. Revocation also reduces tasks executed.

0.24

Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

cs.CR cs.CL ·2026-09-26 ·Chao Feng, Burkhard Stiller
similarity 0.63
Abstract

When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is \NP-complete and deterministic certification is \coNP-complete. Exact stochastic certification is $\coNP^{\PP}$-complete at every fixed rational cutoff in $(0,1)$. Restricting the computation can change these bounds. For example, certification is in \coNP\ when all randomness is a terminal draw from an efficiently computed finite probability table. Attention models admit polynomial-time certification when local dependency windows of logarithmic length precede one global head, given deterministic decoding, fixed vocabulary, exact rational weighted means, a direct binary affine readout and finite-automaton prompt domains. A construction with two global layers instead makes certification \coNP-complete over template domains, with one head per layer, polynomial width, logarithmic precision and an inverse-polynomial logit margin. Planted-secret experiments measure what finite audits miss relative to complete references. Among 30 secret--model-state pairs that leak under greedy single-prompt execution on their secret's 4,096-prompt domain, uniformly selecting 256 recorded evaluations per pair misses every leak for an expected $41.06\%$ of these pairs. Batched and single-prompt checks disagree on one complete-domain decision among all 48 fine-tuned pairs, while a same-order repeat reproduces every single-prompt output. These results distinguish computational conditions for certification from the coverage and execution conditions needed to interpret a negative audit.

0.33

Runtime Assurance Under Measurement Attack: Necessary and Sufficient Observability Conditions for Learned Control in Radio Access Networks

eess.SP cs.CR ·2026-09-25 ·Yasser Al Eryani
similarity 0.63
Abstract · 17 pages, 6 figures, 9 tables

Runtime assurance pairs a verified fallback with an untrusted controller and a switching monitor, and is the leading route to admitting learned policies into safety-relevant network control. Its guarantee rests on a condition it assumes rather than requires: that the monitor's estimation error is zero, or at worst stochastic with a characterisable rate. In mobile networks many measurements originate at untrusted endpoints, where the error is neither. We state this assurance precondition and prove it: at zero measurement noise the guarantee survives an adversary controlling $q$ channels if and only if the plant is $2q$-sparse observable with respect to the safety-relevant output. This is functional observability over attack supports, strictly weaker than full-state observability: on our topology a per-cell outage condition doubles the budget and one stated over total offered load triples it. The converse is a constructive attack making a safe and an unsafe trajectory observationally identical; it defeats every monitor on those channels, not one detector, at any noise level. As the trust split is static and known before deployment, confining the adversary to one family yields a confinement threshold, above which trusted channels alone resolve the state and all untrusted channels may be corrupt at once. Three uninfluenceable counters cross it here, lifting the budget from two to six and making placement the dominant lever. Below the precondition the monitor faces a frontier, not a dichotomy; a set-valued monitor is optimal and carries sufficiency into non-zero noise at the residual test's false-rejection rate. An adversary reaching the trigger radius owns the switch regardless. The same argument bounds any monitor reading agent messages rather than measurements. A rank test decides the budget and identification does not preserve it, so a published budget must name its margin floor.

0.20

Controller-Agnostic Runtime Safety Certificates for Tool-Using AI Agents via Data-Driven Robust Reachability

eess.SY ·2026-10-12 ·Ali Baheri, Peng Wei
published similarity 0.63
Abstract

Software agents built on large language models act by issuing tool calls, some of which cannot be undone. To control theory the model is an opaque feedback controller, replaced every few months, whose closed loop cannot be analyzed directly. We propose a runtime filter, or shield, between any such controller and its environment that certifies a bound on the probability of reaching an unsafe condition during a bounded task. Given a predicate abstraction and candidate successor sets, everything else comes from logs: the loop becomes a finite controlled Markov chain, the estimated kernel is surrounded by a distribution-free confidence region, and robust reach-avoid value iteration runs over it. The certificate is probably approximately correct and uniform over controllers respecting the filter, so one model may replace another without recomputation. In all tested datasets the true risk stayed within certificate and budget; in a file-system sandbox the filter stays sound against a hazard the logs barely covered, where a plug-in baseline certifies safety and fails; and it holds seven controllers, three of them open-weights models, to zero unsafe outcomes in 1050 episodes.

0.28