Lecture 14 · The three inferences

Abduction
at scale.

One observation. Three causes. The inference from effect to cause is not deduction, and it rarely names a unique fault.

6 gates 3 minimal diagnoses 1 hitting-set lab Self-paced
00 · Learning objectivesLecture 14 · Abduction at scale

By the end of this lecture

Four things you can do.

01

Diagnose from consistency

Define a diagnosis, a conflict set, and the model assumptions behind them.

02

Compute minimal hitting sets

Use Reiter’s theorem to turn conflicts into diagnoses, and see why the answer is ambiguous.

03

Rank and cost explanations

Separate subset-minimality from probability, and choose the next test by its value.

04

Check LLM hypotheses

Use a model as a proposal distribution and a symbolic checker as the filter.

S/V · Lecture 14
00 · The hookLecture 14 · Abduction at scale

A circuit, an output, no fault label

The output is 0.
Which gate is broken?

Inputs a = 1, b = 0, s = 0. The healthy circuit gives out = 1, outn = 0, mon = 1. You observe out = 0, outn = 1, mon = 1. The observation rules out the healthy circuit. It does not name the fault.

{N1}

The NOT on the select line outputs 0 instead of 1.

{A1}

The selected AND outputs 0 despite inputs 1 and 1.

{O1}

The output OR outputs 0 despite a 1 input.

S/V · Lecture 14
00 · The hookLecture 14 · Abduction at scale

The circuit

A selector, a complement, a monitor.

a = 1b = 0s = 0 N1NOT A1AND · fault A2AND O1OR N2NOT O2OR ns = 1p = 0q = 0 out = 0outn = 1mon = 1
Schematic. One witness for {A1}: the faulty AND outputs 0, and every downstream value matches the observation. The other diagnoses blame different gates, each with its own witness.
S/V · Lecture 14
00 · The hookLecture 14 · Abduction at scale

The three stories, side by side

Same observation, three witnesses.

DiagnosisFaulty outputPropagated valuesWhat must be true
{N1}ns = 0p=0, q=0, out=0, outn=1, mon=1The NOT inverts s when it should not.
{A1}p = 0out=0, outn=1, mon=1The selected AND outputs 0 despite 1, 1.
{O1}out = 0outn=1, mon=1The output OR outputs 0 despite a 1 input.

Each is subset-minimal: no smaller set of faults explains the observation. The observation cannot choose among them. A prior can rank them; a probe can separate them; nothing in the logic can prefer one.

S/V · Lecture 14
01 · AbductionLecture 14 · Abduction at scale
01 / 08

From effect to cause.

Peirce’s third inference. It is not deduction, it is not induction, and it is not truth-preserving. It is a search for an explanation, followed by a check.

S/V · Lecture 14
01 · AbductionLecture 14 · Abduction at scale

Peirce’s trichotomy

Deduction, induction, abduction.

ModeMoveBeans exampleStatus
DeductionRule + case → resultAll in the bag are white; these are from the bag; so these are white.Truth-preserving
InductionCases → generalizationThese are from the bag and white; so all in the bag are white.Ampliative
AbductionResult + rule → caseThese are white; all in the bag are white; so these are from the bag.Ampliative

Read deductively, the third line is affirming the consequent. Read abductively, it is a candidate explanation: the hypothesis is not entailed, it is proposed, then checked against the model and the next observation.

S/V · Lecture 14
01 · AbductionLecture 14 · Abduction at scale

The selection problem

Explain, then choose.

H* = argmaxH ∈ ℋ score(H; O, K)   subject to   K ∪ {H} ⊨ O,   K ∪ {H} ⊭ ⊥
(1.1)

ℋ · generate

What can be a cause? One gate, any subset, a fault mode, a rule, a program.

⊨ · filter

Does the hypothesis entail the observation under the background knowledge?

score · rank

Parsimony, prior, likelihood, scope, or cost of repair. They can disagree.

S/V · Lecture 14
01 · AbductionLecture 14 · Abduction at scale

The architecture

Generate. Filter. Rank.

01 · generate

Hypothesis space

The LLM, the fault library, the disease list, the grammar. Coverage is decided here.

02 · filter

Consistency

Conflict sets and hitting sets. The symbolic part can reject a candidate; it cannot invent one.

03 · rank

Preference

A prior, a likelihood, a cost, or a test. The ranking is not implied by the logic.

The hard part is stage 1. If the cause is not in the vocabulary, no amount of consistency checking will find it. A broken trace, a wrong netlist, or a misread sensor is invisible to a gate-level model.
S/V · Lecture 14
02 · Diagnosis & hitting setsLecture 14 · Abduction at scale
02 / 08

The consistency filter.

Reiter’s definition, conflict sets, and the theorem that turns a search over faults into a search over hitting sets.

S/V · Lecture 14
02 · Diagnosis & hitting setsLecture 14 · Abduction at scale

Reiter, 1987

A diagnosis is a consistent story.

SD ∪ OBS ∪ {¬AB(c) : c ∉ Δ} ∪ {AB(c) : c ∈ Δ} ⊭ ⊥
(2.1)

Normal

The component satisfies its model. Its outputs are determined by its inputs.

Abnormal

The component is cut out of the model. Its outputs are unconstrained.

Δ is minimal if no proper subset is a diagnosis. That is subset-minimality — not minimum cardinality, and not maximum probability.

S/V · Lecture 14
02 · Diagnosis & hitting setsLecture 14 · Abduction at scale

The dual view

A conflict is a set that cannot all be normal.

C is a conflict if   SD ∪ OBS ∪ {¬AB(c) : c ∈ C} ⊭ ⊥
(2.2)
C1 · the output path

{N1, A1, O1}

If all three are normal: ns=1, p=1, q=0, out=1, contradicting out=0.

C2 · the complement

{N2}

If N2 is normal, outn = ¬out = 1, but the second observation has outn=0.

The first conflict is the hook observation. The second appears when the observation is out=0, outn=0, mon=1. A diagnosis must hit both.

S/V · Lecture 14
02 · Diagnosis & hitting setsLecture 14 · Abduction at scale

The theorem

Hitting sets are diagnoses.

Δ is a minimal diagnosis  ⇔  Δ is a minimal hitting set of the minimal conflict sets.
(2.4)

If Δ missed a conflict C, every component in C would be assumed normal, contradicting the fact that C cannot be all normal. Conversely, hitting every conflict removes every contradiction that the normality assumptions could produce.

C1 = {N1, A1, O1}, C2 = {N2} → {N1,N2}, {A1,N2}, {O1,N2}

S/V · Lecture 14
02 · Diagnosis & hitting setsLecture 14 · Abduction at scale

Interactive · conflicts ↔ hitting sets

Does it hit both?

C1

{N1, A1, O1}

If all normal, out=1, not 0.

C2

{N2}

If normal, outn=¬out=1, not 0.

Candidate

Choose a candidate to see which conflicts it hits.

Minimal diagnoses
{N1,N2} · {A1,N2} · {O1,N2}

Mode: conflicts. Pick a candidate.

S/V · Lecture 14
02 · Diagnosis & hitting setsLecture 14 · Abduction at scale

The search, step by step

From one conflict to three diagnoses.

C1 = {N1, A1, O1}C2 = {N2} ∅ {N1} {A1} {O1} {N1, N2} {A1, N2} {O1, N2} misses C2 → add N2 misses C2 → add N2 misses C2 → add N2 all three hit both conflicts; none has a hitting proper subset
The incremental construction. Branch on C1; extend any candidate that misses C2; prune supersets. The survivors are the minimal hitting sets.

The search is exponential in the worst case. Five independent two-element conflicts give 32 minimal diagnoses; twenty give over a million. Scale is not a detail.

S/V · Lecture 14
03 · Programs & rankingLecture 14 · Abduction at scale
03 / 08

When the model is a program.

Abductive logic programming generalizes conflict sets. Probability ranks the survivors. Both are ways of making the hypothesis space explicit.

S/V · Lecture 14
03 · Programs & rankingLecture 14 · Abduction at scale

Kakas, Kowalski & Toni, 1992

⟨P, A, IC⟩: program, abducibles, constraints.

P ∪ Δ ⊨ G   and   P ∪ Δ ⊨ IC,   Δ ⊆ ground(A)
(3.1)

Why it matters

Abducibles can be any predicate, not only AB(c). The program can use recursion, variables, and negation as failure. Integrity constraints encode domain rules.

What it costs

The hypothesis space must be finite or restricted; negation as failure is relative to the program; the search is at least as hard as logic-based abduction.

Closed world. “Cannot be derived” becomes “false.” A cause outside the program’s vocabulary is not unlikely — it is closed out.
S/V · Lecture 14
03 · Programs & rankingLecture 14 · Abduction at scale

A small abductive program

The light is off. Why?

light_on :- switch_on,
            bulb_ok, power_ok.
bulb_ok  :- not broken.
power_ok :- not power_cut.

% abducibles: broken, power_cut
% observation: light is off, switch is on
:- light_on.
switch_on.

Δ = {broken}

bulb_ok fails; the light is off. The constraint is satisfied.

Δ = {power_cut}

power_ok fails; same observation. A second explanation.

Add the test outlet_live

The power-cut explanation is ruled out. Only {broken} survives.

S/V · Lecture 14
04 · RankingLecture 14 · Abduction at scale

From consistent to probable

Consistency gives a set.
Probability gives an order.

P(Δ | OBS) ∝ P(OBS | Δ) · P(Δ)
(4.1)
P(Δ) = ∏c ∈ Δ pc · ∏c ∉ Δ (1 − pc)
(4.2)

The rank is only as good as the priors and the likelihood. A flat prior is not neutral; it is a claim that all faults are equally likely.

S/V · Lecture 14
04 · RankingLecture 14 · Abduction at scale

Three diagnoses, two priors

Minimal is not the same as probable.

DiagnosisSizePrior weightPosterior · componentPosterior · uniform
{A1}10.042055.2%33.3%
{N1}10.033243.7%33.3%
{O1}10.00081.1%33.3%
Same size, different prior. Component priors separate A1 from O1. Uniform priors tie all three.
Different size, different answer. With conflicts {g1,g2} and {g1,g3}, the minimal sets are {g1} and {g2,g3}. If g1 is very reliable, the two-fault set wins.

Priors: N1 .04, A1 .05, O1 .001, A2 .05, N2 .03, O2 .05. Illustrative, not measured.

S/V · Lecture 14
05 · LLMs & checkersLecture 14 · Abduction at scale

Abduction at scale

Propose with a model, dispose with a proof.

LLM proposercandidate causesfrom text + model formalizerhypothesis → logicor “not expressible” symbolic checkerK ∪ H ⊨ O?K ∪ H ⊭ ⊥? rankerprior · likelihood· cost diagnoses no survivor: return the conflict sets
The LLM changes coverage. The checker changes soundness relative to the model. The ranker is a separate choice.

LLMs are good at proposing causes from text, logs, and code. They are not oracles. The verifier can reject a plausible story that does not entail the observation.

S/V · Lecture 14
05 · LLMs & checkersLecture 14 · Abduction at scale

The guarantee is conditional

Sound relative to the model, not to the world.

The checker can

Reject a hypothesis that does not entail the observation. Reject a hypothesis that violates an integrity constraint. Localize the contradiction in a conflict set.

The checker cannot

Guarantee that the hypothesis is true. Guarantee that the model is right. Guarantee that the hypothesis language is complete. Rank the survivors.

Scale changes the bottleneck. A cheaper, broader proposal step makes the checker and the ranker the limiting parts. If the model is wrong, scale makes the wrong answer faster, not truer.

Evidence: ART abductive NLI 68.9% vs human 91.4% (Bhagavatula et al. 2020); LLM parsimony gaps (2025).

S/V · Lecture 14
06 · Ambiguity & costLecture 14 · Abduction at scale

Why one observation is rarely enough

Five structural reasons.

01 · Combinatorics

k independent two-element conflicts give 2k diagnoses. The observation constrains each conflict; it does not choose.

02 · Masking

A dormant gate can force the output. In the lab, the unselected A2 is a suspect when it should output 0.

03 · Abstraction

“Abnormal” is not “stuck-at-0.” Many fault modes map to one observation.

04 · Partial observability

Internal nodes are free. A fault upstream can be compensated downstream. The monitor is an extra observation; remove it and ambiguity grows.

05 · The hypothesis language. A broken trace, a wrong netlist, or a misread sensor is invisible if it is not in the vocabulary.
S/V · Lecture 14
06 · Ambiguity & costLecture 14 · Abduction at scale

The word “minimal” is overloaded

Four criteria, four answers.

CriterionDefinitionImpliesDoes not imply
Subset-minimalNo proper subset is a diagnosis.No redundant faults.Smallest cardinality.
Minimum cardinalityNo diagnosis has fewer faults.Subset-minimal.Most probable or cheapest.
Minimum costSmallest weighted sum.Reflects repair/test costs.Subset-minimal if costs are non-monotone.
Most probableLargest posterior.Reflects the assumed model.Minimal at all.

Reiter’s theorem is about subset-minimality. The lab reports subset-minimal sets. The ranking is a separate layer. Say which criterion you are using.

S/V · Lecture 14
07 · CasesLecture 14 · Abduction at scale

Four domains, one skeleton

The checker is always a model.

DomainObservationHypothesis spaceCheckerGuarantee
CircuitInputs, outputsFaulty gates, modesNetlist; SAT or propagationConsistency to the netlist
MedicineSymptoms, labsDiseases, drug effectsGuidelines, lab rangesConsistency to the record
SoftwareLogs, failing inputServices, commits, configsDependency graph; delta debuggingReachability or 1-minimality
ScienceMeasurementsMechanisms, parametersSimulator, statistical modelFit relative to assumptions
MYCIN · INTERNIST-1. Rules and certainty factors; diseases and multiple causes. Explanation was a feature, not an afterthought.
GDE · delta debugging. Multiple faults and measurement selection; 1-minimal failing input without an explicit theory.
S/V · Lecture 14
08 · RecapLecture 14 · Abduction at scale

What you should be able to do

Four moves.

Diagnose

A diagnosis is a set of components whose abnormality makes the model, observation, and normality assumptions consistent.

Hit

Minimal diagnoses are minimal hitting sets of the minimal conflicts. The search is exponential; ambiguity is normal.

Rank

Minimal is not probable. Priors, likelihoods, and costs are separate choices; say which one you are using.

Check

An LLM proposes; a symbolic checker disposes. The guarantee is relative to the model, not to the world.

S/V · Lecture 14
08 · RecapLecture 14 · Abduction at scale

Next · hands-on

Break the circuit.

Open the lab. Flip an observation. Watch the conflict sets change, and the minimal diagnoses change with them. Then rank them.

Lab 14 · circuit diagnosis → open the lab

S/V · Lecture 14
08 · RecapLecture 14 · Abduction at scale

The spine

Six sources, one caveat.

Reiter, “A Theory of Diagnosis from First Principles,” Artificial Intelligence 32(1), 1987.

de Kleer & Williams, “Diagnosing Multiple Faults,” Artificial Intelligence 32(1), 1987.

Kakas, Kowalski & Toni, “Abductive Logic Programming,” Journal of Logic and Computation 2(6), 1992.

Eiter & Gottlob, “The Complexity of Logic-Based Abduction,” Journal of the ACM 42(1), 1995.

Bhagavatula et al., “Abductive Commonsense Reasoning,” ICLR 2020, arXiv:1908.05739.

Kambhampati et al., “LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks,” 2024, arXiv:2402.01817.

Reading order: Reiter for the definition, de Kleer and Williams for the algorithm, Kakas et al. for ALP, Eiter and Gottlob for the complexity, Bhagavatula et al. for the benchmark.

Sources and honesty. The circuit, the trace, and the loop are schematics. The diagnosis sets are enumerated; the priors are illustrative. The only empirical numbers quoted are the ART results (68.9% model, 91.4% human).
S/V · Lecture 14
Speaker notes