A policy proposes. A shield checks. A monitor remembers. The guarantee is real — and it is always relative to a model, a specification, and a check.
4 kinds of check5 worked examples1 interactive shieldSelf-paced
00 · Learning objectivesLecture 11 · Logic as a verifier
By the end of this lecture
Four things you can do.
01
Write a specification
Safety, liveness, LTL, STL — and the failure modes of a spec.
02
Monitor and shield
Check a prefix, filter an action, and state the invariant and its price.
03
Separate the bounds
Conformal coverage is not network verification, and neither is a shield.
04
Audit the guarantee
Name the model, the spec, the monitor — and the weakest link.
S/V · Lecture 11
00 · The hookLecture 11 · Logic as a verifier
A proposal, a check, a refusal
The policy says go. The shield says no.
At (0,1), “down” is the policy’s highest-scoring action: it shortens the distance to the goal. It is also forbidden, because the successor is a hazard.
Without a verifier, the agent enters it. With one, the proposal is rejected and the best safe alternative is executed.
The interface. A neural policy proposes; a transition model, hazard predicate, and decision procedure check; a filter sits between model and actuator.
S/V · Lecture 11
00 · The hookLecture 11 · Logic as a verifier
Before any claim of safety
What is checked, when, and relative to what?
What
A trace, an action, a prediction, a network. The object decides the method. A property of traces needs a monitor; a property of an action needs a shield.
When
Design time or runtime. A verifier can gate a release or sit in the control loop. The later it sits, the more it can prevent — and the tighter its deadline.
Relative to
A model, a specification, a sample. No guarantee is unconditional. The referent is the first thing to ask for.
The four checks in this lecture differ along all three axes. Conflating them is the most common mistake in the literature — and in product decks.
S/V · Lecture 11
01 · SpecificationsLecture 11 · Logic as a verifier
01 / 08
Say what must never happen.
And what must eventually happen. A specification is a property of traces, not a label on one output.
S/V · Lecture 11
01 · SpecificationsLecture 11 · Logic as a verifier
Two families, one decomposition
Safety has a finite witness. Liveness does not.
Safety · □¬bad
Every violating execution has a finite prefix that no continuation can repair. “Never enter a hazard.” A monitor can say violated on a finite trace.
□¬H · □(temp < 80) U closed
Liveness · ◇good
Every finite prefix can be extended to a satisfying execution. “Eventually reach the goal.” A finite monitor can say so far so good or already satisfied, not never.
◇G · □◇charge
Bounded response is safety. “Respond within 3 steps” has a finite violation witness: three steps with no response. “Respond eventually” does not.
S/V · Lecture 11
01 · SpecificationsLecture 11 · Logic as a verifier
Linear temporal logic
Four operators, one trace.
Form
Reads as
Semantics at t
○φ
next
φ holds at t+1
φ U ψ
φ until ψ
ψ at some k ≥ t; φ at every j < k
□φ
always
φ at every t′ ≥ t; □φ ≡ ¬◇¬φ
◇φ
eventually
φ at some t′ ≥ t; ◇φ ≡ true U φ
□¬H — never enter a hazard. A safety property; one bad step is the whole counterexample.
□(req → ◇≤3 resp) — every request gets a response within three steps. Safety, because the deadline is finite.
S/V · Lecture 11
01 · SpecificationsLecture 11 · Logic as a verifier
Signals, not propositions
Robustness is a margin, not a probability.
□[0,3](h ≥ 2.0): ρ = min(1.1, 0.4, −0.2, 0.2) = −0.2. The same trace satisfies ◇[1,3](h ≥ 2.0) with ρ = 0.4.
ρ > 0 means satisfied with margin. ρ < 0 means violated with margin. The magnitude is distance from the boundary.
STL is how a continuous signal meets a temporal spec. It is still a model: the predicate must mean what you think it means.
S/V · Lecture 11
01 · SpecificationsLecture 11 · Logic as a verifier
The spec is software too
Three ways a specification lies.
Vacuous
True for trivial reasons. □(h ≥ 2 → h ≥ 2) is a tautology; the monitor always reports safe.
Unsatisfiable
No execution can satisfy it. □(h ≥ 2) ∧ □(h < 1) has no model; a shield has an empty safe set.
Incomplete
The alphabet omits a variable. A hazard predicate that cannot see a sensor cannot protect against it.
The fix is not a better solver. It is a better alphabet, a satisfiability check, and a red team that tries to make the spec true for the wrong reason.
S/V · Lecture 11
02 · Monitoring & shieldingLecture 11 · Logic as a verifier
02 / 08
Check before the action.
A monitor can only report. A shield can refuse. The difference is authority — and the guarantee is conditional on the model.
S/V · Lecture 11
02 · Monitoring & shieldingLecture 11 · Logic as a verifier
A decision procedure over a prefix
Three verdicts: true, false, not yet.
μ : (S × A)* → {⊤, ⊥, ?}
⊥ — every extension of the prefix violates φ. Sound violation.
⊤ — every extension satisfies φ. Sound satisfaction.
? — the prefix does not decide. Uninformed, not wrong.
The bug to test for: a monitor that says violated when a satisfying extension exists. That is unsound, and it is worse than saying unknown.
For a safety property, the violation verdict is the useful one. For liveness, the satisfaction verdict is. A finite trace rarely proves “never”.
S/V · Lecture 11
02 · Monitoring & shieldingLecture 11 · Logic as a verifier
The filter
Keep the proposal if it is safe. Otherwise replace it.
Asafe(s) = { a ∈ A | T(s, a) ∉ H }
(2.2)
κ(s, a) = a if a ∈ Asafe(s); else argmaxa′ r(s, a′); else astop
(2.3)
Permissive
Keep a safe proposal unchanged. Minimal interference, maximum trust in the policy.
Ranked
If the proposal is unsafe, return the best safe action by a score. The score is a design choice.
Fallback
If no safe action exists, stop. A fallback that is not safe in the model is not a guarantee.
S/V · Lecture 11
02 · Monitoring & shieldingLecture 11 · Logic as a verifier
Authority and delay
Four designs, four guarantees.
Design
Runs
Can prevent?
Guarantee relative to
Preemptive shield
Before the actuator
Yes
Model + hazard set + estimate
Post-hoc monitor
After the transition
No; it reports
Specification + trace
Post-hoc enforcement
After, then filters the next action
Only the next step
The same, plus delay
Synthesized shield
Offline, from a game
Yes, for the game
The game model + spec
Delay is part of the guarantee. A post-hoc filter that acts one step later was unsafe for one step. If the spec has memory, the shield must consult the monitor state, not only the physical state.
S/V · Lecture 11
02 · Monitoring & shieldingLecture 11 · Logic as a verifier
Safety is not free
The shield tax.
Intervention rate. How often the shield overrides the policy. A high rate is a policy problem, not a shield success.
Detour cost. Extra steps on the safe path. The lab shows a seed where the safe path is longer.
Goal-reaching cost. How often the shield prevents the goal entirely. A shield that blocks everything is safe and useless.
The winning region is the set of states from which the specification can be maintained. A one-step check stays outside H; a winning shield stays inside the region. Computing it is a game.
S/V · Lecture 11
03 · Conformal predictionLecture 11 · Logic as a verifier
A different kind of guarantee
Coverage, under exchangeability.
Exchangeability. The joint distribution of the calibration and test examples is invariant under permutations. IID implies it; independence is not required.
Distribution-free. No Gaussian noise, no linear model. The guarantee is finite-sample and exact, not asymptotic.
What it covers: a label. What it does not: a policy, a decision, or the world.
A miss at α = 0.20 is allowed. The guarantee is 80% coverage. A single calibration set is a random variable; with nine points it can fall below the nominal rate.
The theorem is over the joint draw of calibration and test. It is not a promise for this particular calibration set, and it is not conditional on x.
S/V · Lecture 11
03 · Conformal predictionLecture 11 · Logic as a verifier
Three category errors
Marginal, not conditional. Not robust. Not useful by itself.
Marginal
90% average coverage can be 50% on a subpopulation. Group-conditional conformal needs the group label.
Shift
Exchangeability is the assumption. A new hospital, city, or sensor can break it; adaptive conformal tracks drift with a weaker, online guarantee.
Size
A huge set covers the label and is useless. Report coverage and set size together.
Not a safety certificate. Conformal covers a label. The decision to act is a separate rule, and coverage is not a bound on the probability of collision.
S/V · Lecture 11
04 · Network verificationLecture 11 · Logic as a verifier
For all inputs in a region
Reachability, not a test set.
Given f : Rⁿ → Rᵐ, region X, property Y: is f(x) ∈ Y for every x ∈ X?
A counterexample is a point. A proof is the whole region. The region is part of the claim: an L∞ ball of radius 2/255 is not “fog”.
Verified ≠ safe. Verified for this network, this region, this property. The pipeline has other stages.
Sound vs complete. Fast vs tight. Small network vs foundation model.
S/V · Lecture 11
04 · Network verificationLecture 11 · Logic as a verifier
A worked reachability problem
Two ReLUs, one counterexample.
f(x) = ReLU(x − 0.25) − ReLU(0.5 − x) x ∈ [0, 1]
Piecewise: x − 0.5 on [0, 0.25], 2x − 0.75 on [0.25, 0.5], x − 0.25 on [0.5, 1].
Range [−0.5, 0.75]. Spec f(x) ≥ 0 fails on [0, 0.375); x = 0.3 gives −0.15.
Interval arithmetic is sound, not tight. For g(x) = x − x, it gives [−1, 1]; the true range is {0}.
The specification fails on the red segment. A verifier returns the counterexample; a bound would return the interval.
S/V · Lecture 11
04 · Network verificationLecture 11 · Logic as a verifier
Sound, complete, scalable — pick two
The verification ladder.
Method
Sound
Complete
Scale
Returns
SMT · Reluplex, Marabou
Yes
Yes
Small
Proof or counterexample
MILP
Yes
Yes
Very small
Proof or counterexample
Abstract interpretation
Yes
No
Large
Bound, or unknown
Lipschitz bound
Yes
No
Large
Radius (often loose)
Randomized smoothing
Probabilistic
No
Large
Radius with confidence
NP-complete for ReLU networks (Katz et al., 2017). The hardness is the ReLU phase combinations; linear regions grow with depth.
Unknown is not safe. An incomplete verifier may fail to prove a property that holds. Report the method, the region, and the result.
S/V · Lecture 11
05 · LLM verifiersLecture 11 · Logic as a verifier
05 / 08
Who checks the checker?
A judge is not a verifier. A proof kernel is. The difference is a formal system — and a trusted base.
S/V · Lecture 11
05 · LLM verifiersLecture 11 · Logic as a verifier
Two things with one name
A judge scores. A checker decides.
LLM-as-judge
Learned scorer. No formal semantics, no soundness theorem. Agreement with human labels is an empirical statistic on a benchmark.
Cheap, flexible, good at ranking. A critic, not a verifier.
Checker
SMT solver, proof kernel, type checker, simulator, PDDL validator, unit test. Sound relative to a formal system.
Can certify. Its trusted base is the kernel and the logic — not the model.
The sentence to audit: “The LLM verifier checked the plan, so the plan is safe.” If the verifier is a judge, the claim is empirical. If it is a checker, ask for the spec.
S/V · Lecture 11
05 · LLM verifiersLecture 11 · Logic as a verifier
Where the guarantee lives
Generate, check, repair.
Sound checker: an accepted candidate is correct relative to the spec and the checker. Search may still fail to find one.
Heuristic critic: the loop is a search with an empirical filter. It can improve quality; it does not certify.
S/V · Lecture 11
06 · The guaranteeLecture 11 · Logic as a verifier
Write the condition down
No guarantee is unconditional.
(A1 ∧ A2 ∧ A3 ∧ A4 ∧ A5) ⇒ □¬H
(6.1)
A1 · Model fidelity. T matches the world on reachable states.
A2 · Specification. H is correct, complete, satisfiable, non-vacuous.
A3 · Monitor coverage. Every variable in φ is observed, in time.
A4 · Action authority. The shield’s output is executed; the fallback is safe.
A5 · Distribution. The system stays in the modeled regime.
One false assumption falsifies the conjunction. That is the weakest-link principle.
S/V · Lecture 11
06 · The guaranteeLecture 11 · Logic as a verifier
Five rungs
From a benchmark to a proof.
Rung
Claim
Assumes
Evidence
None
A benchmark score
The benchmark is representative
A test set
Empirical
Performance on held-out data
Rough exchangeability with deployment
Confidence intervals
Statistical
Coverage ≥ 1−α
Exchangeability and a valid score
Calibration set, size
Conditional formal
□¬H given model and spec
Model, monitor, authority
A shield invariant
Unconditional formal
A theorem from axioms
The logic, formalization, kernel
A checked proof
UP buys a stronger claim and costs a stronger assumption. The ladder is not a total order of usefulness: a well-tested empirical system can beat a formally verified toy.
S/V · Lecture 11
07 · Patterns & casesLecture 11 · Logic as a verifier
Placements, not alternatives
Seven ways to put a check in a system.
1 · Preemptive shield. Runtime invariant; cost: conservatism and a safe fallback.
2 · Monitor + review. Accountability without prevention; cost: response and logging.
3 · Conformal triage. Coverage for a predictor; cost: set size.
4 · Offline verification. Release gate; cost: scale and region fidelity.
6 · Specification as tests. Executable property; cost: test coverage and oracle quality.
7 · Hierarchical envelope. Neural controller inside a symbolic layer; cost: integration and latency.
Pick by claim, not by fashion. The check that carries the claim also carries its assumptions.
S/V · Lecture 11
07 · Patterns & casesLecture 11 · Logic as a verifier
Pattern and limit
Four cases, four referents.
Shielding · Alshiekh et al.
Shield synthesized from an MDP and a safety spec. Relative to: the MDP. If the model is wrong, safe in the model, unsafe in the world. arXiv:1708.08611
Gridworlds · Leike et al.
Small environments that make side effects and interruptibility observable. Relative to: the test scenario. Diagnostics, not certificates. arXiv:1711.09883
Reluplex · ACAS Xu
A property for every input in a region. Relative to: the network and the region. The region is not the world. arXiv:1702.01135
LLM-Modulo · AlphaGeometry
LLM proposes; a symbolic engine or proof kernel decides. Relative to: the checker and the formalization. arXiv:2402.01817
The pattern repeats: a neural proposal, a symbolic check, and a guarantee that is only as good as the referent. The referent is the contribution.
S/V · Lecture 11
07 · InteractiveLecture 11 · Logic as a verifier
A fixed proposal sequence, a real filter
Shield on, shield off.
Press Step to run the first proposal.
—
The sequence is fixed: R, D, R, D, D, R, D. The shield is a real filter over the transition function, not an animation. Reset returns to the same start and the same sequence.
S/V · Lecture 11
08 · RecapLecture 11 · Logic as a verifier
What you should be able to do
Four moves, one question.
Specify
Write a property of traces; classify it as safety or liveness; read LTL and STL.
Shield
Filter the action; state the invariant; measure the shield tax.
Separate
Coverage, network verification, and a runtime invariant are three claims.
Audit
Name the model, the spec, the monitor — and the weakest link.
The question: what does the guarantee depend on?
S/V · Lecture 11
08 · RecapLecture 11 · Logic as a verifier
Next · hands-on
Run it with the shield off.
Open the shielded grid lab. Run the same seed with and without the shield. Then find a seed where the safe path is longer.