Lecture 11 · The verifier interface

Logic as a verifier.

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 check 5 worked examples 1 interactive shield Self-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.

H G π: down → H κ: right, safe specification □¬H · monitor logs every intervention

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.

FormReads asSemantics 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.

3.22.4 1.60.8 01 23 4t h ≥ 2.0 −0.2 at t=2
□[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.

DesignRunsCan prevent?Guarantee relative to
Preemptive shieldBefore the actuatorYesModel + hazard set + estimate
Post-hoc monitorAfter the transitionNo; it reportsSpecification + trace
Post-hoc enforcementAfter, then filters the next actionOnly the next stepThe same, plus delay
Synthesized shieldOffline, from a gameYes, for the gameThe 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.

a2 · hazard a1 · safe a3 · safe filtered returned available
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.

q̂ = k-th smallest score
k = ⌈(n+1)(1−α)⌉
C(x) = { y : s(x,y) ≤ q̂ }
P(Y ∈ C(X)) ≥ 1−α

The score is any ranking of how unusual a candidate label is. The quantile is the calibration correction.

S/V · Lecture 11
03 · Conformal predictionLecture 11 · Logic as a verifier

A worked calibration

The rate is the guarantee.

αkq̂Test 0.93
0.1091.05covered
0.2080.88outside

Nine residuals: 0.10, 0.22, 0.31, 0.45, 0.52, 0.60, 0.71, 0.88, 1.05.

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.

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

Methods: SMT (Reluplex, Marabou), MILP, abstract interpretation (AI², DeepPoly, CROWN), Lipschitz, randomized smoothing.

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}.
0.8−0.6 00.51 zero 0.375 f < 0: x=0.3
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.

MethodSoundCompleteScaleReturns
SMT · Reluplex, MarabouYesYesSmallProof or counterexample
MILPYesYesVery smallProof or counterexample
Abstract interpretationYesNoLargeBound, or unknown
Lipschitz boundYesNoLargeRadius (often loose)
Randomized smoothingProbabilisticNoLargeRadius 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.

LLM generator plan · proof · program a proposal, not a truth checker solver · kernel · test the guarantee lives here accept candidate + proof or counterexample reject with a reason: repair, retry, or stop

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.

RungClaimAssumesEvidence
NoneA benchmark scoreThe benchmark is representativeA test set
EmpiricalPerformance on held-out dataRough exchangeability with deploymentConfidence intervals
StatisticalCoverage ≥ 1−αExchangeability and a valid scoreCalibration set, size
Conditional formal□¬H given model and specModel, monitor, authorityA shield invariant
Unconditional formalA theorem from axiomsThe logic, formalization, kernelA 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.
5 · Generate-and-check. LLM proposes, checker decides; cost: search and coverage.
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.

H H G start

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.

Lab 11 · Shielded grid → open the lab

S/V · Lecture 11
Speaker notes