Pith.

Systems and Control · arXiv:2610.16865 v2 · submitted 12 Oct 2026

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

Ali Baheri, Peng Wei

The paper says

“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.”

more of the abstract

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.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 14 Oct 2026 · of version 1 of the paper; version 2 is newer · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up. Rigorous distribution-free shield for LLM agents, but the core Markov assumption remains a practical uncheckable condition. This line is wrong

1 major objection · 7 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the references say.

The paper says, at §II-A, Assumption 1, and §V Experiment 4

The review did not quote this passage.

A classifier read this sentence of the paper as acknowledging the concern (probability 0.85):

“The main assumption is that the Boolean predicates defining the abstract state make the loop Markov, which the logs can test but not prove.”

Pith says: Objection 1 of 1 · major

The central guarantee (Theorem 1) is conditional on Assumption 1 (abstract Markovness), which requires that the predicate abstraction φ makes the state transitions Markovian. The paper provides a diagnostic test (Experiment 4) that can refute, but never certify, this assumption.

more of objection 1

The authors acknowledge this clearly: 'The test can refute a predicate set, never certify one' and 'Dependence this context cannot see is invisible, and failing to reject is not evidence of Markovness.' Proposition 2 bounds the cost of a violation by an unknown η, but the paper does not provide a statistical method to estimate η with confidence from data. In practice, a user must rely on engineering judgment to decide whether the predicates are 'rich enough,' which weakens the statistical coverage claim. While this does not invalidate the mathematical theorem, it is a significant practical obstacle that deserves a more extensive discussion—ideally with suggestions for how to select or verify predicates (e.g., using domain knowledge, cross-validation against held-out logs, or data-driven abstraction refinement) to increase confidence in the Markov assumption.

7 minor objections

The paper says, at §III-A, Lemma 2 proof sketch

Pith says: minor objection 1 of 7

The proof sketch mentions martingale differences and Azuma–Hoeffding but does not explicitly state that the budget n0(s,a) is fixed a priori. This point is critical and could be made more prominent in the main text, not just in the sketch.

The paper says, at §I, Related work (Table I)

Pith says: minor objection 2 of 7

Table I lists 'distribution-free L1 balls' as the uncertainty set. It would be helpful to note that the radius depends on the candidate-set size ks,a, which is a known structural prior, not a free parameter from data.

show 5 more

The paper says, at §V-A, Experiment 1

Pith says: minor objection 3 of 7

The sentence 'Recomputing this shield’s certificate from more logs shows how fast the bound tightens' reports a log–log slope of −0.70, faster than the parametric rate M^{-1/2}. The authors attribute this to the shield forbidding fewer actions as data increase. A brief explanation of why the empirical rate exceeds the worst-case bound would improve readability.

The paper says, at §V-B, Table III

Pith says: minor objection 4 of 7

The 'policy-spec.' row reports a certificate of 0.00 but is marked with a dagger stating 'Logging controller only.' The text says it 'certifies zero risk, forbids nothing and fails the same way' as the plug-in MDP. Clarify how this baseline is constructed and why its certificate is invalid for other controllers (the paper's own argument about uniformity).

The paper says, at §V, Experiment 4 (Table V)

Pith says: minor objection 5 of 7

Table V shows that with the pair context (state, action) on the grid, there are 0 testable rows. The explanation is that '|S||A| contexts exhaust the data.' This is a known degeneracy; it would be helpful to mention that this constraint is expected when the number of (s,a) pairs is large relative to the number of visits, and that the primary diagnostic (previous state alone) is a practical compromise.

The paper says, at §II-B, Lemma 1

Pith says: minor objection 6 of 7

The lemma states that the worst-case value is produced by a deterministic Markov policy. Consider adding a brief note that this is standard for finite-horizon reach–avoid under A1–A3, and referencing [16] is sufficient.

The paper says, at §III-C, Corollary 2

Pith says: minor objection 7 of 7

Corollary 2 asserts that the shield can be synthesized from the same data that certifies it, with no sample splitting, because the event E is independent of D. This is a clever observation and deserves emphasis; it is currently stated in one sentence. A short remark on why this does not suffer from post-hoc selection (the bound holds for all shields simultaneously) would help readers.

What would settle it

For each row with sufficient data in the sandbox experiment, compute empirical successor distributions conditioned on the previous two abstract states (or the previous state+action) and conduct a permutation test comparing these distributions (as in Experiment4 but with two-step context). Report the maximum L1 distance and compare to the 95% null quantile. Additionally, for each row, compute the L1 distance between empirical distributions conditioned on the previous abstract state vs. conditioned on the previous two states; if the difference exceeds 0.1 for any row, the Markov assumption is suspect and the certificate may be invalid.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 14 Oct 2026

  1. Reader holds up confidence high
  2. Skeptic agrees 28 s · 16,925 tokens read, 3,361 written
  3. Editor wrote the verdict above 9 s · 17,775 tokens read, 782 written
  4. Referee minor revision: 1 major objection, 7 minor 23 s · 17,358 tokens read, 2,839 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

This paper builds a runtime safety filter for LLM-based tool-using agents. The idea is simple and sensible: abstract the transcript to a finite set of boolean predicates, use logs to build distribution-free confidence intervals around each row of the transition kernel, then run robust value iteration to get a PAC bound on the worst-case reach-probability that holds uniformly over every controller the filter admits. The math is clean, the committed-budget trick for handling adaptively collected data is neat, and the controller-agnostic property is a genuine practical win—you can swap the LLM without recomputing the certificate. The empirical work, though small, checks out: the grid experiment with known ground truth validates the coverage claims, and the file-system sandbox shows the shield blocks hazards the logs never saw, while the plug-in baseline fails.

The biggest soft spot is the one the authors flag themselves: Assumption 1 (abstract Markovness). The whole certificate rests on the predicates making the loop Markov. The diagnostic can only refute, never confirm, and it tests only a one-step context. The paper honestly says "failing to reject is not evidence of Markovness" and tells you to keep development and certification logs separate if you refine φ. That is the right attitude, but it means the user has no statistical guarantee that the assumption holds in deployment. Proposition 2 bounds the violation by an unestimated η, so in practice you are relying on engineering judgment. That does not make the paper wrong—it makes the guarantee conditional on an untestable premise, which is worth stating clearly.

The paper is a serious contribution: it takes a well-understood robust-MDP framework and adapts it to a genuinely hard new domain with care and rigor. The limitations are stated, not hidden. I would send this to a decent controls or safety venue. The work is not yet a finished engineering solution—the predicate design and Markovness testing remain open—but as a principled first pass it deserves to be seen.

The strongest objection

The central guarantee (Theorem 1) requires Assumption 1: the abstraction φ makes the loop Markov. The authors provide a diagnostic (Experiment 4) that tests only one-step context (previous abstract state) and can only refute, never certify. As they acknowledge, 'Dependence this context cannot see is invisible, and failing to reject is not evidence of Markovness.' Proposition 2 bounds the violation cost by an unknown η, but η is not estimated with confidence from data. In practice, if the abstraction fails to capture relevant history (e.g., two-step dependencies or longer), the robust value iteration (7) may not dominate the true worst-case reach probability, invalidating the certificate. The paper's own examples show that omitting a predicate (confirmation obtained) causes rejection, but for correctly chosen predicates, the test may still miss subtle history effects. Without a method to bound η or to certify Markovness to a given tolerance, the user must rely on engineering judgment, not statistical guarantee. This does not undermine the mathematical soundness under the assumption, but it makes the claim 'PAC controller-agnostic safety' contingent on an untestable condition in deployment. The reader correctly flagged this as the weakest assumption.

The reader's weakest_assumption correctly identifies Assumption1 as the most fragile premise. The stress-tester reinforces this by highlighting that the diagnostic test is limited and η is unknown. The paper is theoretically sound under the assumption, and the limitations are transparently stated. No internal inconsistency or misrepresentation is found. The verdict should remain ACCEPT as per the reader, since the concern is acknowledged and the contribution is novel. However, the correctness risk is correctly rated medium, and the concern is genuine but not a reason to reject. Therefore verdict_should_be is UNCHANGED.

The referee's report

If the assumptions are met, this is the first method to provide a distribution-free, controller-agnostic PAC safety certificate for tool-using LLM agents from ordinary logged episodes. The committed-budget construction of confidence sets for adaptively collected data is a technically clean solution to a known difficulty in data-driven control. The empirical validation—especially the file-system sandbox with multiple LLMs under prompt injection—demonstrates practical relevance. The paper is clearly written, all theoretical claims are proved in the appendix, and the limitations (especially Assumption 1) are honestly discussed.

Pith's reading of the paper (a machine's summary, not the authors')

This paper presents a method to wrap any language-model-based tool-using agent in a thin runtime filter (a shield) that guarantees the probability of an irreversible harmful action stays below a chosen threshold. The shield is constructed entirely from ordinary logs of the agent's past interactions, without any knowledge of the agent's internal weights or architecture. The guarantee is probably approximately correct (PAC) and holds uniformly across every controller that respects the shield, so the agent can be swapped without recomputing the certificate. The key assumptions are that a small set of Boolean predicates makes the agent-environment loop Markovian and that the environment does not adapt to the agent's identity. Experiments on a grid and a file-system sandbox show the certificate holds even when the logs barely cover the actual hazard, and it kept seven different language models (including three open-weight models) at zero unsafe outcomes over 1050 episodes.

What carries the argument. The central object is the robust reach–avoid value iteration (Equation 7) acting over distribution-free L1 confidence sets (Equation 6), which are built from logs using a budgeted-sample-size martingale inequality (Lemma 2). The confidence sets are intersected with a known candidate successor set K_{s,a} and, for rows with insufficient data, become the entire simplex, ensuring the certificate never relies on under-sampled rows. The worst-case value for any admissible controller collapses to a deterministic Markov policy (Lemma 1), and the robust value iteration computes an upper bound that dominates the true worst-case value with high probability (Theorem 1).

Core claim. The paper establishes that a data-driven, controller-agnostic safety certificate can be built for language-model agents by abstracting their interaction history into a finite Markov chain via Boolean predicates, estimating the transition kernel from passively collected logs, surrounding each estimate with a distribution-free L1 confidence ball (using a committed-budget martingale argument), and then running robust reach–avoid value iteration over these balls. The resulting bound on the worst-case unsafe-reach probability holds with probability at least 1−δ over the logs, for every admissible controller, and the shield can be synthesized greedily to minimize restrictions while meeting a risk budget. The certificate remains valid even when the logs never show the hazardous action because the confidence set treats unseen successor states as maximally uncertain.

The premise it rests on. The loop must become Markovian after the chosen Boolean predicates: the next abstract state must depend only on the current abstract state and action, not on any other part of the past transcript, and this assumption can only be tested, never proven, from data.

If the paper is right (Pith's inferences, not the authors')

Language models can be swapped without re-certification: the certificate belongs to the interface (predicate abstraction and permitted actions), not the model, as long as the environment, abstraction, and risk budget are unchanged.

The method provides a principled way to bound risk from rare but catastrophic tool calls: because unseen outcomes are treated as maximally uncertain, the shield can block hazards that never appeared in the training logs.

The greedy shield-synthesis algorithm (Algorithm 1) can be computed in seconds on a single CPU core, making it practical for deployment with dozens of abstract states and actions.

The certificate can be tightened by collecting more logs that cover the relevant rows, with the gap shrinking as O(T/√M) when the minimal budget on those rows scales with M.

The approach suggests a new division of labour: the safety engineer specifies predicates and successor sets; the agent developer provides logs; the shield is computed once and reused across model releases.

The requirement that the predicate abstraction makes the loop Markovian (Assumption 1) is the hardest constraint in practice; the paper's own diagnostic (Experiment 4) can only refute, not confirm, this assumption, so any real deployment would need a careful human review of whether unmodeled history (e.g., the exact prompt or the agent's internal reasoning) could affect transitions.

The committed-budget trick (using only the first n0 visits per row) avoids the closed-loop dependence in the logs but wastes data; a natural extension is to use time-uniform confidence sequences that allow sequential testing and can incorporate all observations without a pre-committed budget.

The shield treats the environment as static (Assumption 4); if the environment adapts to the agent's identity (e.g., a service that blocks a known attacker), the certificate may lose validity, and the paper explicitly excludes such environments.

The synthesis algorithm (Algorithm 1) is greedy and suboptimal; for larger state spaces a more principled combinatorial optimization (e.g., integer programming) might yield fewer restrictions, though at higher computational cost.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

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.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-10-14

The authors' main claim, as the classifier picked it out 0.95

“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.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.56 · human participants 0.04 · controlled comparison 0.86 · randomized assignment 0.02 · states quantitative result 0.98 · compares with prior results 0.93 · mentions code or data availability 0.04

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
Software agents built on large language models act by issuing tool calls, some of which cannot be undone. background 1.00 0.08 0.02 asserted 0.96
To control theory the model is an opaque feedback controller, replaced every few months, whose closed loop cannot be analyzed directly. background 0.92 0.12 0.02 asserted 0.99
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. contribution 0.99 0.70 0.25 asserted 0.93
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. method 1.00 0.85 0.07 asserted 0.99
The certificate is probably approximately correct and uniform over controllers respecting the filter, so one model may replace another without recomputation. interpretation 0.65 0.79 0.27 asserted 0.56
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. result 1.00 0.95 0.64 asserted 1.00

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from observation or experiment 0.84

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-14: 1 request, 5,033 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (1)
Figure 1 of the paper
Figure 1. The grid benchmark and the shield of Experiment 1. (a) Each of the 7 × 7 cells is an abstract state of a tool-using agent; the red block is the unsafe set Su, s0 the start and the star the goal. (b) Color: the certified worst-case probability V¯ T (s) of reaching Su from each cell. Black segments: forbidden moves. The shield fences the hazard instead of walling in the start, so a route to the goal remains, and the risk from s0 is certified below the budget (ε = 0.10, M = 12,000, T = 16). (ii) Keeping the task reachable. A fence removes one action at one state, never a state. Every st

Figures are the authors', reproduced from the paper.

Cited by 1 Pith paper

Reviewed papers on Pith that cite this one. The full citation record

  1. Bellman Language Models: Solving the Recurring Decisions of LLM Agents cs.AI · Oct 2026

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment