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.
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.
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.
| Check | Object checked | When | Relative to |
|---|---|---|---|
| Specification | A property of traces | Design | The language and its semantics |
| Monitor | A trace prefix | Runtime | The specification and the trace |
| Shield | A proposed action | Before the actuator | The model, hazard set, state estimate |
| Conformal predictor | A prediction | Runtime or offline | Exchangeability and the calibration sample |
| Network verifier | A network over a region | Design | The network, region, output property |
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.
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.
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.
| English | LTL | Kind | Finite witness? |
|---|---|---|---|
| Never enter a hazard | □¬H | Safety | Yes, the step that enters |
| Eventually reach the goal | ◇G | Liveness | No |
| Respond within 3 steps | □(req → ◇≤3resp) | Safety (bounded) | Yes, after three steps |
| Respond eventually | □(req → ◇resp) | Liveness | No |
| Visit the charger infinitely often | □◇charge | Liveness | No |
“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.
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).
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.
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.
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.
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.
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.
The theorem is conditional on the model and the state estimate; §6 lists the rest.
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.
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−α)⌉.
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%.
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.
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 α.
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.
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:
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.
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.
“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.
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.
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.
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.
| Assumption | Meaning | How it fails | How to test it |
|---|---|---|---|
| Model fidelity | T matches the world on reachable states | Unmodeled dynamics, stale map | Compare predictions to logs |
| Spec completeness | H covers every hazard that matters | A hazard outside the predicate | Red-team the spec |
| Monitor coverage | Every variable in φ is observed | Blind spot, stale reading | Fault injection |
| Action authority | The shield’s output is executed | Bypass, delay, unsafe fallback | End-to-end trace; timing audit |
| Distribution | The system stays in the modeled regime | Shift; novel objects | Online 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.
| Rung | Claim | Assumes | Evidence |
|---|---|---|---|
| 1 · None | A benchmark score | The benchmark is representative | A test set and a leaderboard |
| 2 · Empirical | Performance on a held-out distribution | Rough exchangeability with deployment | Confidence intervals, ablations |
| 3 · Statistical | Coverage ≥ 1−α | Exchangeability and a valid score | Calibration set, empirical coverage |
| 4 · Conditional formal | □¬H given the model and spec | Model fidelity, monitor coverage, authority | A shield invariant |
| 5 · Unconditional formal | A theorem from axioms | The logic, formalization, kernel | A 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.
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.
| Pattern | When to use | Guarantee | Cost |
|---|---|---|---|
| Preemptive shield with fallback | A model exists; violations are costly | Invariant relative to model and spec | Conservatism; a safe fallback |
| Post-hoc monitor + review | Actions cannot be blocked | Sound verdicts on the trace | No prevention; response cost |
| Conformal triage | A predictor exists; coverage is the claim | Marginal coverage under exchangeability | Set size; no conditional guarantee |
| Offline network verification | A release gate for a small network | Property of the network on the region | Scale; region fidelity; composition |
| Generate-and-check | Candidates are hard to produce, easy to check | The checker’s soundness, if it is sound | Search cost; checker coverage |
| Hierarchical envelope | A neural controller inside a safety layer | Invariant relative to the envelope model | Integration; 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
- Write the property. Safety, liveness, or both; in a formal language; check vacuity, satisfiability, and alphabet coverage.
- Name the monitor. What it observes, at what rate, with what latency, and what it does when a variable is missing.
- Name the fallback. A shield without a safe fallback can deadlock; prove it safe in the model, or say that it is not.
- State the model fidelity assumption. Which states, dynamics, and horizon; how you will test it against logs.
- Measure the shield tax. Intervention rate, detour cost, goal-reaching rate.
- For statistical claims, state exchangeability. Report coverage, set size, and behavior under shift.
- For network verification, state the region. Verify the pipeline, not just the network.
- 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.
Define a verifier as a decision procedure; distinguish soundness from completeness.
Write a specification as a property of traces; classify it as safety or liveness.
Explain why a bounded response is safety for a monitor.
Define a shield as a filter; state its invariant and assumptions; measure its conservatism.
Explain conformal prediction: exchangeability, scores, quantile, marginal coverage.
Distinguish a sound, complete verifier from an incomplete bound; state what the region does not cover.
Separate an LLM critic from a checker.
State a guarantee with its assumptions, and identify the weakest link.
Exercises
- 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?
- 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?
- 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?
- 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.
- 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
AI Safety Gridworlds
Leike et al. · 2017 · safety diagnostics
A Gentle Introduction to Conformal Prediction
Angelopoulos & Bates · 2021 · coverage, scores, and the variants
Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks
Katz et al. · CAV 2017 · verification
LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks
Kambhampati et al. · ICML 2024 · generate and check
Towards Guaranteed Safe AI
Dalrymple, Skalse, Bengio, Russell et al. · 2024 · world model, spec, verifier, proof
Adaptive Conformal Inference Under Distribution Shift
Gibbs & Candès · NeurIPS 2021 · coverage when exchangeability fails
The Temporal Logic of Programs
Pnueli · FOCS 1977 · the original temporal turn
Monitoring Temporal Properties of Continuous Signals
Maler & Nickovic · FORMATS/FTRTFT 2004 · STL
Algorithmic Learning in a Random World
Vovk, Gammerman & Shafer · Springer 2005 · the conformal theory
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.