Course / Act III · The five interfaces Lecture 11

Logic as a verifier.

A learned policy proposes an action because it scored well. It does not know what must never happen. A verifier is the part of the system that does — and the first question to ask about any guarantee is: relative to what?

~50 min read 5 worked examples 4 kinds of check 1 interactive lab Updated 2026-11-17

The previous four lectures put logic inside learning: as a loss, an architecture, data, search. This one puts it outside the model, at inference time, where it can refuse a candidate. That buys a checkable condition on behaviour — and costs a condition only as good as the model, the specification, and the monitor beneath it.

00 / The hookThe policy says go. The shield says no.

Six-by-six grid: start top-left, goal bottom-right, hazard at (1,1). At (0,1), a policy trained to reach the goal scores “down” highest, because it shortens the Manhattan distance by one. It is also forbidden: the successor is a hazard. Without a verifier the agent enters it; with a verifier, the proposal is checked, rejected, and the best safe alternative executed. A policy proposes; a shield disposes.

at = κ(st, π(st))    where   κ(s, a) = a if T(s, a) ∉ H, else a safe replacement
(0.1)

This is the verifier interface in miniature: a neural policy proposes; a transition model, hazard predicate, and decision procedure check; the interface is a filter between model and actuator. The weights do not change; the set of executable actions does.

A proposal into a hazard, blocked by a shield A six by six grid with a start at the top-left, a goal at the bottom-right, and a hazard at row one, column one. An orange dashed arrow shows the policy proposal into the hazard. A teal solid arrow shows the shielded action continuing right instead. H start G π: right π: down κ: right, safe grid cell hazard H policy proposal shielded action specification: □¬H successor: T(s, a) = (1,1) verdict: blocked monitor: intervention logged
Fig. 0.1 A schematic of the hook: the policy prefers down, into the hazard; the shield evaluates the successor, rejects the action, and selects a safe one; the monitor logs the intervention. The guarantee is conditional on the grid model and the hazard predicate.

The shield does not guarantee world safety. It guarantees that if the model, hazard predicate, state estimate, and action path are right, then the next state is not a hazard. That is a conditional theorem, useful because its conditions can be written down and tested.

The checks are easy to conflate: a specification says what must hold; a monitor decides whether a prefix satisfies it; a shield filters an action; a conformal predictor wraps a prediction in a set; a network verifier proves a property over a region. The table separates them.

Table 0.1 · The checks and their referents. “Relative to” is the load-bearing column.
CheckObject checkedWhenRelative to
SpecificationA property of tracesDesignThe language and its semantics
MonitorA trace prefixRuntimeThe specification and the trace
ShieldA proposed actionBefore the actuatorThe model, hazard set, state estimate
Conformal predictorA predictionRuntime or offlineExchangeability and the calibration sample
Network verifierA network over a regionDesignThe network, region, output property
Definition · verifier

A verifier takes a candidate — action, plan, label, prediction, or proof — with a specification, and returns accept, reject, or unknown, with a reason. A sound verifier never accepts a violation; a complete one never rejects a satisfying candidate. Most are sound and incomplete: they can say “unknown” even when the candidate is fine.

Caveat · what the hook does not show

A grid with one hazard and deterministic transitions is the easiest case. The hard cases are partial observability, continuous dynamics, a learned hazard predicate, a slow shield, and a policy that leaves the modeled regime. Each is an assumption in §6.

01 / SpecificationsSay what must never happen — and what must eventually happen.

A specification is a constraint on an execution. Fix states S, actions A, transition T : S × A → S, and labelling L. An execution is a sequence σ = s0a0s1a1…; a property is a set of infinite executions, and the system satisfies φ if every execution is in it.

σ = s0 a0 s1 a1 s2 a2 …
(1.1)

This is a semantic notion: the same syntax means different things under different models.

Safety and liveness

A safety property says nothing bad ever happens; every violating execution has a finite prefix no continuation can repair. A liveness property says something good eventually happens; every finite prefix can be extended to a satisfying execution. Alpern and Schneider showed every property is the intersection of a safety and a liveness property (1985). Safety can be violated on a finite prefix; liveness generally cannot be decided on one.

Table 1.1 · Five specifications, classified. ◇≤3 abbreviates a three-step disjunction; a bounded response is safety because its violation has a finite witness.
EnglishLTLKindFinite witness?
Never enter a hazard□¬HSafetyYes, the step that enters
Eventually reach the goal◇GLivenessNo
Respond within 3 steps□(req → ◇≤3resp)Safety (bounded)Yes, after three steps
Respond eventually□(req → ◇resp)LivenessNo
Visit the charger infinitely often□◇chargeLivenessNo

“Within three steps” turns liveness into safety: if no response has arrived by step three, the violation is determined. A bounded liveness property is safety, and its monitor needs only three steps of memory.

The temporal language

Linear temporal logic (LTL) is the standard language; its semantics is evaluated at a position t in an execution.

φ ::= p | ¬φ | φ ∧ φ | φ ∨ φ | ○φ | φ U φ | □φ | ◇φ
(1.2)
(σ, t) ⊨ ○φ   iff   (σ, t+1) ⊨ φ
(1.3)
(σ, t) ⊨ φ U ψ   iff   ∃k ≥ t. (σ, k) ⊨ ψ   and   ∀j, t ≤ j < k. (σ, j) ⊨ φ
(1.4)
□φ ≡ ¬◇¬φ,    ◇φ ≡ true U φ
(1.5)

Robustness

LTL talks about propositions; an altitude is a real number with a margin. Signal temporal logic (STL) extends the language to real-valued signals and replaces Boolean semantics with a quantitative robustness degree ρ: positive means satisfied with margin, negative violated. Maler and Nickovic introduced the logic (2004); Donzé and Maler developed robustness semantics (2010).

ρ(f(x) ≥ c, t) = f(xt) − c
(1.6)
ρ(□[a,b]φ, t) = mint′ ∈ [t+a, t+b] ρ(φ, t′)    ρ(◇[a,b]φ, t) = maxt′ ∈ [t+a, t+b] ρ(φ, t′)
(1.7)

Negation flips the sign; conjunction takes the minimum; disjunction the maximum. Always takes the minimum, because a chain is as strong as its weakest link; eventually takes the maximum. For h = [3.1, 2.4, 1.8, 2.2] and □[0,3](h ≥ 2.0), the robustness is min(1.1, 0.4, −0.2, 0.2) = −0.2: violated at t = 2. The specification ◇[1,3](h ≥ 2.0) has robustness 0.4: the same trace satisfies it.

An altitude trace against a lower bound, with STL robustness A step plot of altitude over four time steps: 3.1, 2.4, 1.8, and 2.2 metres. A dashed line marks the bound at 2.0. The segment at time two is below by 0.2, so the robustness of the always-inside specification is minus 0.2. 3.2 2.4 1.6 0.8 0 1 2 3 4 t h ≥ 2.0 −0.2 m at t=2 +1.1 +0.4 +0.2
Fig. 1.1 The altitude trace from the worked example. Robustness for □[0,3](h ≥ 2.0) is the minimum margin, −0.2 at t = 2. Robustness is a signed margin, not a probability: it says how far the trace is from the boundary, not how likely a violation is.

When the specification fails

Specifications fail too. A specification is vacuous when true for trivial reasons: □(h ≥ 2 → h ≥ 2) is a tautology, and a monitor always reports safe. It is unsatisfiable when no execution satisfies it: □(h ≥ 2) ∧ □(h < 1) has no model, and a shield built on it has an empty safe set. It is incomplete when its alphabet omits a variable: a hazard predicate that cannot see a sensor cannot protect against that hazard. The fix is a better alphabet, not a better solver.

Caveat · the spec is a model

LTL is discrete, infinite, and propositional. STL is continuous but still assumes a signal and a semantics for each predicate. Neither knows whether the predicate is measured correctly, whether the state estimate is biased, or whether the hazard set is complete. Vacuity, unsatisfiability, and alphabet coverage check the specification, not the system.

02 / Monitoring & shieldingCheck the prefix; filter the action.

Monitors

A monitor is a decision procedure over a finite trace prefix. For a safety property the interesting verdict is violated; for liveness, satisfied; everything else is unknown.

μ : (S × A)* → {⊤, ⊥, ?}    with   μ(w) = ⊥ ⇒ every extension of w violates φ,   μ(w) = ⊤ ⇒ every extension satisfies φ
(2.1)

A monitor that returns unknown is uninformed, not wrong. One that returns violated when a satisfying extension exists is wrong, and that is the bug to test for. Bauer, Leucker, and Schallhart give automata constructions for the three-valued semantics (2011).

Shields

A shield does more than observe. Given state s, proposal a, model T, and forbidden states H, it returns an action whose successor is safe. A permissive shield keeps a safe proposal; otherwise it returns the best safe action by a ranking, or a fallback.

Asafe(s) = { a ∈ A | T(s, a) ∉ H }
(2.2)
κ(s, a) = a if a ∈ Asafe(s);   else argmaxa′ ∈ Asafe(s) r(s, a′);   else astop
(2.3)

The one-step invariant is easy to prove and easy to misstate. If s0 ∉ H and every action the shield returns has a successor outside H, then no reachable state is in H.

s0 ∉ H   ∧   ∀t. T(st, κ(st, π(st))) ∉ H   ⇒   ∀t. st ∉ H
(2.4)

The theorem is conditional on the model and the state estimate; §6 lists the rest.

The monitor and shield loop A state feeds a policy, which proposes an action. The shield checks the proposal against a transition model and a hazard predicate. The accepted action reaches the environment; the next state feeds a monitor. The monitor history is available to the shield when the specification has memory. state sₜ observation policy π proposal a shield κ A_safe(s) = {a : T(s,a) ∉ H} fallback a_stop environment T next state sₜ₊₁ monitor μ consumes the trace; verdicts are logged history, if φ has memory
Fig. 2.1 The runtime loop. The dashed path is the subtle one: when the specification has memory — “after a warning, never enter a hazard” — the shield must consult the monitor state, not only the physical state. A one-step shield that ignores history is not a shield for a temporal property.

Three designs are often called “shielding”. A preemptive shield runs before the actuator, so the unsafe transition never happens. A post-hoc monitor runs after and records a verdict; it can alarm or trigger recovery, but cannot undo the past. A post-hoc enforcement that filters the next action is preemptive with a one-step delay — and the delay is part of the guarantee. A synthesized shield is a winning strategy for a game built from the model and the specification (Bloem et al., 2015); it is correct for the game, which is still a model.

A shield that allows only actions whose entire future is safe can be too restrictive. One that checks only the immediate successor can walk into a dead end: every step is safe, and every path from there eventually violates the specification. The set of states from which the specification can be maintained is the winning region; a good shield stays inside it, and computing it is a game.

What it costs

The price of conservatism is what this lecture calls the shield tax: intervention rate, detour cost, and goal-reaching cost. A shield that blocks everything is safe and useless; one that blocks nothing is useful and not a shield. If the policy ranks a hazard above two safe actions, a shield that preserves the policy’s order returns the first safe one; a separate safety score could return the other. Neither is “the” shield; the choice is a design decision.

Caveat · partial observability and latency

The invariant assumes the shield knows st. Under partial observability it knows a belief, and the guarantee becomes “for every state in the belief” (strong, often infeasible) or “with probability p” (weaker, and needs a belief model). If the shield computes for 80 ms and the deadline is 50 ms, the action applies to a state the shield did not see.

03 / Conformal predictionA guarantee with a rate.

Conformal prediction is a different kind of verifier. It does not check an action against a model; it wraps a predictor in a set-valued output and guarantees that the true label is in the set at a chosen rate. The guarantee is statistical: over draws from a distribution, under an assumption. It is useful where a formal model is unavailable, and dangerous where the rate becomes a per-case certificate.

The assumption is exchangeability: Z1, …, Zn+1 are exchangeable if their joint distribution is invariant under permutations of the indices. IID data is exchangeable; exchangeable data need not be independent. The assumption is about order, not shape, which is why the method is distribution-free.

A calibration set of n examples defines a nonconformity score s(x, y); higher means a worse fit. The score can be an absolute residual, a quantile, or any ranking of how unusual a candidate is. The split-conformal quantile is the k-th smallest score, k = ⌈(n+1)(1−α)⌉.

q̂ = the k-th smallest of { s(Z1), …, s(Zn) },    k = ⌈(n+1)(1−α)⌉
(3.1)
C(x) = { y : s(x, y) ≤ q̂ }
(3.2)
ℙ( Yn+1 ∈ C(Xn+1) ) ≥ 1 − α
(3.3)

The proof is a rank argument: under exchangeability, with ties broken arbitrarily, the rank of the test score among the n+1 scores is uniform, so the test score is at most the k-th smallest with probability at least k/(n+1) ≥ 1−α. The argument is finite-sample and exact. Angelopoulos and Bates give the derivation and variants (2021); Vovk, Gammerman, and Shafer develop the theory (2005).

Nine calibration points give sorted residuals 0.10, 0.22, 0.31, 0.45, 0.52, 0.60, 0.71, 0.88, 1.05. With α = 0.10, k = 9, so q̂ = 1.05, and a test residual of 0.93 is covered. With α = 0.20, k = 8, q̂ = 0.88, and the same point is outside. That is allowed: the guarantee at 0.20 is 80%, and a miss is part of the 20%. Coverage is over the joint draw of calibration and test; for one calibration set it is a random variable, and with nine points it can fall below 90%.

A conformal band around a one-dimensional predictor A scatter of calibration points around a fitted line, a shaded band of constant width, and a test point with a vertical interval. The band width is set by the calibration quantile, not by a Gaussian assumption. y x 0 1 test x: interval q̂ sets the half-width calibration points · fixed band · marginal coverage 1−α
Fig. 3.1 A schematic of split conformal regression. The band has constant half-width q̂ because the score is the absolute residual; adaptive scores produce variable-width bands. The band is a statement about the calibration distribution, not a physical envelope.

What coverage does not mean

The guarantee is marginal: it averages over the test features. It does not say that for a particular x the coverage is at least 1−α. A predictor can have 90% marginal coverage and 50% on a subpopulation. Group-conditional conformal prediction restores per-group coverage, but needs the group label at calibration and test time.

ℙ(Y ∈ C(X)) ≥ 1−α    does not imply    ℙ(Y ∈ C(x) | X = x) ≥ 1−α for every x
(3.4)

Coverage is not robustness to distribution shift. If the test distribution differs — a new hospital, city, or sensor — scores are no longer exchangeable and the guarantee can fail. Adaptive conformal inference updates the quantile online and tracks coverage under drift (Gibbs and Candès, 2021), but the guarantee becomes an online, long-run statement. Coverage is also not usefulness: compare coverage and set size at the same α.

Caveat · conformal is not a safety verifier

Conformal prediction covers a label, not a policy. You can conformalize a predictor of “will this action cause a collision?” and get a set of labels with a coverage rate, but the decision to act is a separate rule, and coverage is not a bound on the probability of collision. Treating a conformal interval as a safety certificate is a category error.

04 / Network verificationFor all inputs in a region.

Neural-network verification asks a precise question. Given network f : ℝn → ℝm, input region X, and output property Y, is f(x) ∈ Y for every x ∈ X? Equivalently, does f(X) intersect the complement of Y? A non-empty intersection is a counterexample; an empty one is a proof. This is a reachability question.

f(X) ⊆ Y   ?    where   f(X) = { f(x) : x ∈ X }
(4.1)

The region is part of the claim. “The network is robust” is not a property. “For every image within an L∞ ball of radius 2/255 around this image, the top class is unchanged” is a property. None of that says the network is robust to fog, rain, occlusion, a different camera, or a different object.

The methods form a ladder. SMT solvers such as Reluplex and Marabou encode the network and property, treat each ReLU as a lazy case split, and are sound and complete for the encoding, with exponential worst cases. MILP is complete and scales poorly. Abstract interpretation (AI², DeepPoly, CROWN) propagates intervals or polyhedra, producing a sound over-approximation; it is fast and incomplete. Lipschitz bounds are sound and often loose. Randomized smoothing certifies a probabilistic radius, not the original classifier.

ReLU verification is NP-complete (Katz et al., 2017): each neuron is active or inactive, and the number of linear regions grows with depth. The practical frontier is a small network, a small region, or an incomplete bound — not a proof of a foundation model.

A worked example

Take f(x) = ReLU(x − 0.25) − ReLU(0.5 − x) on [0, 1]. The function is piecewise linear with breakpoints at 0.25 and 0.5:

f(x) = x − 0.5 on [0, 0.25];   2x − 0.75 on [0.25, 0.5];   x − 0.25 on [0.5, 1]
(4.2)

The range is [−0.5, 0.75]. The specification f(x) ≥ 0 is false on [0, 0.375), so a verifier must return a counterexample; x = 0.3 gives −0.15. Interval arithmetic also returns [−0.5, 0.75] here, but that is a coincidence. For g(x) = x − x on [0, 1], interval arithmetic gives [−1, 1] while the true range is {0}: sound and useless.

The two-ReLU function and its zero crossing The piecewise linear function f equals x minus 0.5 on the first interval, 2x minus 0.75 on the middle, and x minus 0.25 on the last. It crosses zero at 0.375. The region to the left of the crossing violates the specification. 0.8 −0.6 0 0.5 1 0 zero at 0.375 f < 0: counterexample x=0.3 f > 0: satisfied
Fig. 4.1 The two-ReLU network as a piecewise-linear function. The input region is [0, 1]; the output range is [−0.5, 0.75]. The specification f(x) ≥ 0 fails on the red segment, so the verifier must return a counterexample; x = 0.3 is one.

Verification does not compose automatically. A verified network is verified for one property, one region, one network. The detector feeds a tracker, the tracker a planner, the planner a controller, and each stage has its own assumptions; a verified perception network can sit in an unsafe pipeline because properties get lost at the interfaces. Scale is the other wall: ACAS Xu has 45 small networks, and verifying all of them was a research result; a modern vision model has millions of parameters. Incomplete bounds and runtime monitoring are the practical alternatives: a bound is a sound statement about a relaxed problem, a monitor a check on the actual trace.

Caveat · verified ≠ safe

“Verified” means the property holds for every input in the region, according to the verifier. It does not mean the region covers deployment, the property is the one intended, the network is the one deployed, or the pipeline is correct. Each is an assumption, and the assumption is where the interesting failure lives.

05 / LLM verifiersWho checks the checker?

“LLM verifier” names two very different things. An LLM-as-judge is a learned model that reads a candidate and a rubric and returns a score. It has no formal semantics and no soundness theorem; its agreement with human labels is an empirical statistic on a benchmark. A checker is a decision procedure with a formal system: an SMT solver, a proof kernel, a type checker, a simulator, a unit test. A checker can be sound relative to its logic; a judge cannot, because it has no logic to be sound relative to.

This does not make judges useless; it makes them critics, not verifiers. A critic can guide search or filter candidates, but it cannot certify. A safety claim that depends on “the LLM said it was safe” is empirical, whatever the architecture looks like.

Generate and check

The productive pattern is to let the LLM generate and a checker decide. In LLM-Modulo, the LLM produces candidates, external critics check them, and the LLM revises (Kambhampati et al., 2024). The guarantee lives in the critics. If they are sound and complete, an accepted candidate is correct relative to the specification and checker; if they are heuristic, the loop is a search with an empirical filter.

Generate, check, and repair A language model generates a candidate. A checker accepts it or rejects it with a reason. Accepted candidates leave the loop; rejected ones return to the generator. A dashed box marks the guarantee as living in the checker. LLM generator plan · proof · program a proposal, not a truth checker solver · kernel · test sound relative to its logic the guarantee lives here accept candidate + proof or counterexample reject with a reason: repair, retry, or stop
Fig. 5.1 Generate and check. The LLM is a search heuristic over candidates; the checker is the decision procedure. If the checker is heuristic, the loop is still useful, but the guarantee is empirical. If the checker is sound, the accepted candidate is correct relative to the specification and the checker’s logic — not relative to the world.

The trusted base

A proof assistant kernel is the strongest checker in common use: it checks a proof term against small rules, and acceptance means the theorem follows from the axioms and definitions. The trusted base is the kernel, the logic, and the axioms — not the LLM. But the kernel checks that the proof proves the stated theorem, not that the theorem is the one you meant. An LLM can prove a vacuous statement, introduce an inconsistent axiom, or leave a `sorry`, and the kernel will accept the proof of the wrong theorem. AlphaGeometry is the case study: the model proposes constructions, the symbolic deduction engine closes the proof, and the proof is checkable (Trinh et al., 2024). The LLM’s contribution is search; the guarantee is the proof, relative to the formalization.

The economic version is a verifier’s dilemma: a weak verifier is cheap but can be gamed, a strong one is expensive. If the generator is optimized against the verifier, it finds the blind spots. The defense is a stronger, independent checker with a known trusted base, plus an audit of what it does not cover.

Caveat · correlated errors

An LLM judge and generator often share pretraining data, tokenizer, and biases, so their errors are correlated: “the generator and the judge agree” is weak evidence. A checker in a different formalism is more independent, but it can share the specification bug. Independence is a property of the whole stack.

06 / The guaranteeWhat it depends on — and the weakest link.

Every guarantee here is conditional. For a shield: if the model agrees with the environment on reachable states, if the hazard predicate is correct and complete, if the monitor observes every variable in the specification, if the shield’s output is executed, and if the system stays in the modeled regime, then the trajectory never enters a hazard.

(A1 ∧ A2 ∧ A3 ∧ A4 ∧ A5) ⇒ □¬H
(6.1)

The assumption ledger

A1 is model fidelity; A2, specification correctness and completeness; A3, monitor coverage; A4, action authority and a safe fallback; A5, the distribution.

Table 6.1 · The assumption ledger. Each row is a liability; each test is how you would find out it failed.
AssumptionMeaningHow it failsHow to test it
Model fidelityT matches the world on reachable statesUnmodeled dynamics, stale mapCompare predictions to logs
Spec completenessH covers every hazard that mattersA hazard outside the predicateRed-team the spec
Monitor coverageEvery variable in φ is observedBlind spot, stale readingFault injection
Action authorityThe shield’s output is executedBypass, delay, unsafe fallbackEnd-to-end trace; timing audit
DistributionThe system stays in the modeled regimeShift; novel objectsOnline coverage; drift detection

The weakest-link principle follows: the guarantee is a conjunction, so one false assumption falsifies it. State the assumptions, monitor the ones that can be monitored, and give the guarantee a referent. An unstated guarantee cannot be audited.

Table 6.2 · Five rungs. Each buys a stronger claim and costs a stronger assumption.
RungClaimAssumesEvidence
1 · NoneA benchmark scoreThe benchmark is representativeA test set and a leaderboard
2 · EmpiricalPerformance on a held-out distributionRough exchangeability with deploymentConfidence intervals, ablations
3 · StatisticalCoverage ≥ 1−αExchangeability and a valid scoreCalibration set, empirical coverage
4 · Conditional formal□¬H given the model and specModel fidelity, monitor coverage, authorityA shield invariant
5 · Unconditional formalA theorem from axiomsThe logic, formalization, kernelA checked proof

Dalrymple et al. propose four artifacts — a world model, a safety specification, a verifier, and a proof — and call the result guaranteed safe AI (2024). The hard parts are the fidelity of the world model and the completeness of the specification, not the verifier. A perfect verifier for the wrong model proves the wrong theorem.

Caveat · formal is not real

A formal guarantee is a proof about a model. The model is software, the world is not. The value of the guarantee is that it makes the gap explicit and testable: you can ask which assumptions are load-bearing, which can be monitored, and which are aspirational. The failure is to treat the proof as a property of the world and stop looking.

07 / Patterns & casesWhere to put the check.

The four checks are placements, not alternatives. A system can use a runtime shield, a conformal wrapper, an offline verifier at release time, and an LLM-plus-checker loop at design time. The design question is which check carries which claim.

Table 7.1 · Six patterns. The cost is the price of the guarantee, not the price of the code.
PatternWhen to useGuaranteeCost
Preemptive shield with fallbackA model exists; violations are costlyInvariant relative to model and specConservatism; a safe fallback
Post-hoc monitor + reviewActions cannot be blockedSound verdicts on the traceNo prevention; response cost
Conformal triageA predictor exists; coverage is the claimMarginal coverage under exchangeabilitySet size; no conditional guarantee
Offline network verificationA release gate for a small networkProperty of the network on the regionScale; region fidelity; composition
Generate-and-checkCandidates are hard to produce, easy to checkThe checker’s soundness, if it is soundSearch cost; checker coverage
Hierarchical envelopeA neural controller inside a safety layerInvariant relative to the envelope modelIntegration; latency; mismatch

Cases

Two cases show the pattern and its limit. Alshiekh et al. synthesize a shield for an RL agent from a model and a safety specification (2018); the shield blocks unsafe actions, and the guarantee is relative to the MDP and the specification. If the model is wrong, the shield is safe in the model and unsafe in the world. Leike et al.’s AI Safety Gridworlds are the diagnostic complement: small environments that make side effects and interruptibility observable (2017).

Reluplex and ACAS Xu show verification at its strongest and most bounded (Katz et al., 2017): the property is about a network over a region, and the verifier returns a proof or a counterexample. The limit is the region: an L∞ ball around an image is not the set of images an aircraft will see. AlphaGeometry and LLM-Modulo show generate-and-check (Trinh et al., 2024; Kambhampati et al., 2024); the limit is the checker’s coverage and the specification’s intent. Conformal prediction is the pattern for a different claim: a label is in a set at a rate, not a decision that is safe.

A design checklist

  1. Write the property. Safety, liveness, or both; in a formal language; check vacuity, satisfiability, and alphabet coverage.
  2. Name the monitor. What it observes, at what rate, with what latency, and what it does when a variable is missing.
  3. Name the fallback. A shield without a safe fallback can deadlock; prove it safe in the model, or say that it is not.
  4. State the model fidelity assumption. Which states, dynamics, and horizon; how you will test it against logs.
  5. Measure the shield tax. Intervention rate, detour cost, goal-reaching rate.
  6. For statistical claims, state exchangeability. Report coverage, set size, and behavior under shift.
  7. For network verification, state the region. Verify the pipeline, not just the network.
  8. Log every intervention. The log is the evidence; without it, the guarantee is a story.

If you remember one question from this lecture, make it the title of §6: what does the guarantee depend on? A verifier that cannot answer it is a filter with a good vocabulary; one that can is an artifact you can test and improve.

08 / RecapWhat you should be able to do now.

01

Define a verifier as a decision procedure; distinguish soundness from completeness.

02

Write a specification as a property of traces; classify it as safety or liveness.

03

Explain why a bounded response is safety for a monitor.

04

Define a shield as a filter; state its invariant and assumptions; measure its conservatism.

05

Explain conformal prediction: exchangeability, scores, quantile, marginal coverage.

06

Distinguish a sound, complete verifier from an incomplete bound; state what the region does not cover.

07

Separate an LLM critic from a checker.

08

State a guarantee with its assumptions, and identify the weakest link.

Exercises

  1. Translate and classify. Write LTL for: (a) never enter a hazard and eventually reach the goal; (b) after a warning, leave the zone within five steps; (c) visit the charger infinitely often. Classify each; which can a finite monitor violate?
  2. Compute robustness. For h = [3.1, 2.4, 1.8, 2.2], compute the STL robustness of □[0,3](h ≥ 2.0), ◇[1,3](h ≥ 2.0), and □[0,3](h ≥ 2.5). Which fails first?
  3. Calibrate by hand. With the nine residuals in §3 and α = 0.10, compute q̂. Repeat for α = 0.20. A test residual is 0.93. Covered in each case? What exactly does the guarantee say?
  4. Verify a tiny network. For f(x) = ReLU(x − 0.25) − ReLU(0.5 − x) on [0, 1], compute the range, find a counterexample to f ≥ 0, and compare with interval arithmetic. Then do g(x) = x − x.
  5. Run the lab. Run the grid with the shield off and on at the same seed. Record violations, interventions, and steps. Find a seed where the shield’s path is longer, and explain the shield tax.

Check your understanding

Ten questions, with explanations; the ones you cannot answer are the reading list.

Reading list

The first five are the spine of this lecture. The rest are the next layer.

Safe Reinforcement Learning via Shielding

Alshiekh et al. · AAAI 2018 · the shield, with a model and a spec

Shielding

AI Safety Gridworlds

Leike et al. · 2017 · safety diagnostics

Diagnostics

A Gentle Introduction to Conformal Prediction

Angelopoulos & Bates · 2021 · coverage, scores, and the variants

Uncertainty
Verification

LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks

Kambhampati et al. · ICML 2024 · generate and check

Language

Towards Guaranteed Safe AI

Dalrymple, Skalse, Bengio, Russell et al. · 2024 · world model, spec, verifier, proof

Framing

Adaptive Conformal Inference Under Distribution Shift

Gibbs & Candès · NeurIPS 2021 · coverage when exchangeability fails

Shift

The Temporal Logic of Programs

Pnueli · FOCS 1977 · the original temporal turn

Logic

Monitoring Temporal Properties of Continuous Signals

Maler & Nickovic · FORMATS/FTRTFT 2004 · STL

Signals

Algorithmic Learning in a Random World

Vovk, Gammerman & Shafer · Springer 2005 · the conformal theory

Book
Source note · what is a schematic

All figures are redrawn schematics, not reproductions. The grid, altitude trace, monitor loop, conformal band, two-ReLU plot, and generate-check loop are ours. The conformal numbers in §3 are a worked example, not a benchmark result.