The output is 0. The circuit should have produced 1. Which gate is broken? The question sounds like deduction with a missing premise, but it is not. No rule says which gate failed. The observation is consistent with several faults, and the job is to find them, check them, and rank them — in that order.
00 / The hookOne observation, three causes.
The circuit below is a two-input selector. When the select line s is 0, the output out follows a; when s is 1, it follows b. The complementary output outn is the inverse of out, and the monitor mon is the OR of out and a. Six gates: two NOTs, two ANDs, two ORs.
Set the inputs to a = 1, b = 0, s = 0. The correct outputs are out = 1, outn = 0, mon = 1. Suppose you observe out = 0, outn = 1, mon = 1. The output is wrong; the other two are right.
| Signal | Healthy value | Observed | Agrees? |
|---|---|---|---|
out | 1 | 0 | No |
outn | 0 | 1 | Yes — the complement of the observed out |
mon | 1 | 1 | Yes — mon is 1 because a is 1 |
Three single-gate faults explain the observation: {N1} (the NOT on s outputs 0 instead of 1), {A1} (the selected AND outputs 0 despite inputs 1 and 1), and {O1} (the output OR outputs 0 despite a 1 input). Each is a diagnosis: a set of gates that, if faulty, lets the circuit produce exactly what you saw. The downstream gates then follow: N2 complements 0 to 1, and O2 outputs 1 because a is 1.
{A1}: the faulty gate is free to output 0, and every downstream value matches the observation. The other two diagnoses blame different gates, each with its own witness. The lab lets you select each diagnosis and inspect it.
The observation rules out the healthy circuit. It does not choose among the three repairs.
This is the problem in miniature. The output does not carry a label that says which gate failed; it carries a constraint. The constraint has three solutions, and the engineering question is not “which one is the answer?” but “what would distinguish them, and what does it cost to find out?”
A faulty gate here is one whose output is unconstrained. That is the standard consistency-based abstraction, and it is deliberately weak. A real stuck-at-0 fault is narrower, so a diagnosis under this model is a superset of the components a stuck-at diagnosis would blame. The lab uses the coarse model and says so; §2 returns to the difference.
01 / AbductionInference to the best explanation — and why “best” is doing work.
Peirce distinguished three ways a conclusion can be reached. Deduction applies a rule to a case and derives a result: all beans in this bag are white; these beans are from this bag; therefore these beans are white. Induction generalizes from cases: these beans are from this bag and are white; therefore all beans in the bag are white. Abduction reasons from a result to a case: these beans are white; all beans in the bag are white; therefore these beans are from this bag. Peirce called the third “hypothesis,” and later folded it into retroduction; the modern name is inference to the best explanation (Harman 1965; Lipton 2004). All three are forms of inference; only the first is truth-preserving.
| Mode | Premises | Conclusion | Status |
|---|---|---|---|
| Deduction | All beans in the bag are white; these beans are from the bag. | These beans are white. | Truth-preserving: if the premises are true, the conclusion must be true. |
| Induction | These beans are from the bag and are white; the sample was fair. | All beans in the bag are white. | Ampliative: the conclusion goes beyond the premises; it can be false. |
| Abduction | These beans are white; all beans in the bag are white. | These beans are from the bag. | Ampliative: a candidate explanation; other bags could produce white beans too. |
The logical form is easy to write and easy to misread. Let O be the observation, K the background knowledge, and H a hypothesis. Abduction looks for an H such that K ∪ {H} entails O, and K ∪ {H} is consistent. It does not conclude that H is true. Read deductively, “O; if H then O; therefore H” is the fallacy of affirming the consequent. Read abductively, it is a search for a candidate that would make the observation unsurprising.
Three things are hidden in (1.1). The first is the hypothesis space ℋ: a gate, a fault mode, a disease, a rule, a program. The second is the consistency check: does the hypothesis actually entail the observation? The third is the score: simplicity, prior probability, likelihood, scope, and cost of repair are different scores, and they can disagree.
Abduction is not induction, but the border is porous
Induction produces a generalization; abduction produces an explanation. If the hypothesis is itself a rule — “all failures in this batch come from a cold solder joint” — abducing the rule looks like inducing it. The difference is the check: an inductive generalization is tested on more instances; an abductive hypothesis is tested by entailment against a model, then by the next observation. “A1 is faulty” is confirmed by probing A1, not by finding more circuits.
What “best” can mean
Harman’s formulation is deliberately open: the best explanation makes the observation most intelligible. That is a placeholder for a scoring function. The scores are familiar: consistency (a hard filter), parsimony (fewer faults, shorter programs), likelihood and prior (how well the hypothesis predicts the observation, and how common it is), scope, and actionability (what it costs to test or repair). They can disagree — parsimony prefers one fault, likelihood may prefer two common faults — so the architecture is modular: generate, filter, rank. The score is a design choice, and it should be stated.
Generate a hypothesis space ℋ (gates, fault modes, diseases, rules, programs). Filter to the hypotheses consistent with K and O. Rank the survivors by an explicit score. Abduction at scale is an engineering problem in all three stages; the logic only fixes the middle one.
The circuit makes the first stage visible. “One faulty gate” gives six candidates; “any subset” gives 64; “any stuck-at fault on any wire” gives more. The observation does not choose the space; the engineer does. A cause outside the space — a broken trace, a wrong netlist, a misread sensor — is invisible.
02 / Diagnosis & hitting setsThe consistency filter, and the combinatorics it leaves behind.
Consistency-based diagnosis is the cleanest formal account of “the observation rules out the healthy circuit.” It was introduced by Reiter (1987) and, independently and in a more algorithmic form, by de Kleer and Williams (1987). The setting is a system description SD, a set of components COMPS, and an observation OBS. Each component can be normal or abnormal; AB(c) says that component c is abnormal. A normal component satisfies its model; an abnormal component is unconstrained.
A diagnosis for (SD, COMPS, OBS) is a set Δ ⊆ COMPS such that SD ∪ OBS ∪ {¬AB(c) : c ∉ Δ} ∪ {AB(c) : c ∈ Δ} is satisfiable. It is minimal if no proper subset of Δ is a diagnosis.
AB(c) : c ∉ Δ} ∪ {AB(c) : c ∈ Δ} ⊭ ⊥The definition says: assume every component outside Δ is normal, every component inside Δ is abnormal, and check that the resulting theory has a model. The abnormal components are not required to output a particular value; they are cut out of the model. That is why the diagnosis is a set of components, not a set of fault modes.
Conflict sets
A diagnosis is easier to compute through its dual. A conflict set is a set of components that cannot all be normal at once, given the observation:
AB(c) : c ∈ C} ⊭ ⊥.A conflict is minimal if no proper subset is a conflict. In the circuit, with a = 1, b = 0, s = 0 and the observation above, the minimal conflict is {N1, A1, O1}. If all three are normal, then ns = 1, p = 1, q = 0, and out = 1, contradicting out = 0. No proper subset is a conflict: with any two of the three normal, the third can supply the wrong value. The monitor is not in the conflict because a = 1 forces mon = 1 regardless of out.
Hitting sets and Reiter’s theorem
A set Δ hits a family of sets if it intersects every member. It is a minimal hitting set if no proper subset hits the family.
Reiter’s theorem connects the two notions:
If Δ missed a conflict C, every component in C would be assumed normal, contradicting the fact that C cannot be all normal. Conversely, if Δ hits every conflict and the model is consistent, the components outside Δ cannot produce a contradiction; otherwise their set would contain a conflict that Δ misses. The theorem is about the minimal sets on both sides; larger diagnoses and larger hitting sets can exist.
For the single conflict {N1, A1, O1}, the minimal hitting sets are exactly the singletons {N1}, {A1}, and {O1}. That is the three-way ambiguity from the hook, now derived rather than guessed.
| Diagnosis | Faulty gate’s output | Propagated values | Why it fits |
|---|---|---|---|
{N1} | ns = 0 | p = 0, q = 0, out = 0, outn = 1, mon = 1 | The NOT gate inverts the select line when it should not. |
{A1} | p = 0 | out = 0, outn = 1, mon = 1 | The selected AND gate outputs 0 despite inputs 1 and 1. |
{O1} | out = 0 | outn = 1, mon = 1 | The output OR gate outputs 0 despite a 1 input. |
A second conflict, and the hitting-set tree
Now observe out = 0, outn = 0, mon = 1. The first conflict is unchanged: {N1, A1, O1}. A second conflict appears: {N2}. If N2 is normal, then outn = ¬out = 1, because the observed out is 0; but outn is observed 0. So N2 cannot be normal. The minimal diagnoses are the minimal hitting sets of {N1, A1, O1} and {N2}: they must include N2 and one of the first conflict, giving {N1, N2}, {A1, N2}, and {O1, N2}. Three two-fault diagnoses.
Why the search is expensive
Hitting-set decision is NP-complete — it is the dual of set cover — and the number of minimal diagnoses can be exponential: five independent conflicts of the form {ai, bi} produce 25 = 32 diagnoses; twenty produce over a million. Logic-based abduction is harder still: Eiter and Gottlob (1995) show the basic decision problems complete for the second level of the polynomial hierarchy (Σ₂P), with prioritization sometimes reaching the third. The practical escapes are a fault bound, structural pruning, and measurement selection.
Reiter’s theorem assumes a model: components are normal or abnormal, abnormal means unconstrained, and the observation is explainable by some fault set. If the system description is wrong, the “diagnosis” may be a model revision; if a sensor is faulty but not modeled, its error looks like a fault elsewhere; if the observation is not explainable at all, the right conclusion is that the model is broken.
03 / Abductive logic programmingWhen the model is a program, not a set of gates.
Consistency-based diagnosis assumes a logical system description and a distinguished AB predicate. Abductive logic programming (ALP) generalizes the setting: the knowledge base is a logic program, the hypotheses are arbitrary abducible atoms, and integrity constraints say which combinations of hypotheses are acceptable. The canonical formulation is Kakas, Kowalski, and Toni (1992).
An abductive framework is a triple ⟨P, A, IC⟩, where P is a logic program, A is a set of abducible predicates, and IC is a set of integrity constraints. An explanation for a goal G is a set Δ ⊆ ground(A) such that P ∪ Δ ⊨ G and P ∪ Δ satisfies IC.
The difference from consistency-based diagnosis is expressive. The abducibles can be any predicates — broken(bulb), power_cut, misconfigured(router) — not only AB(c). The program can use recursion, variables, and negation as failure. The integrity constraints can encode domain rules that are not part of the device model: “do not abduce both a power cut and a broken bulb,” or “a patient with a penicillin allergy cannot be explained by penicillin.”
A small example
Consider a lamp. The program has three rules, two abducibles, and a test:
light_on :- switch_on, bulb_ok, power_ok.
bulb_ok :- not broken.
power_ok :- not power_cut.
% abducibles: broken, power_cut
% observation: the light is off, and the switch is on
:- light_on.
switch_on.
% test: the outlet is live
outlet_live.
:- power_cut, outlet_live.
The integrity constraint :- light_on says the observed light is off. With no hypotheses, light_on follows from switch_on, not broken, and not power_cut, violating the constraint. Abducing broken blocks bulb_ok; abducing power_cut blocks power_ok. Both are explanations. Add the test outlet_live — the outlet is live — and the constraint :- power_cut, outlet_live rules out power_cut, leaving broken. The second observation pruned the hypothesis space. That is the whole diagnostic loop in miniature.
The not is negation as failure, not classical negation: not broken succeeds if broken cannot be derived. This is non-monotonic. Adding the hypothesis broken removes the derivation of bulb_ok, which removes light_on, which satisfies the constraint. Adding a hypothesis can invalidate a conclusion — exactly what a diagnostic model needs, and exactly what makes the semantics delicate.
The same program can be read as an answer set program: guess which abducibles hold, enforce the rules and integrity constraints, and collect the stable models. Each stable model is a consistent diagnosis; preferences select the minimal or cheapest ones. That is how a declarative diagnosis system expresses “prefer fewer faults” without hard-coding the search.
What ALP buys, and what it costs
ALP buys a uniform language for device models, domain rules, and hypotheses, with integrity constraints and negation; it costs a restricted hypothesis space, a semantics relative to the program, and a search at least as hard as logic-based abduction.
Negation as failure assumes that what cannot be derived is false. In diagnosis, that is a powerful default: if the model does not derive a fault, the component is assumed normal. It is also a modeling bet. A cause that is not represented in the program — a loose cable, a firmware bug, a mislabeled sensor — is not just unlikely; it is closed out. The explanation is only as good as the program’s vocabulary.
04 / Probabilistic rankingFrom “consistent” to “probable” — and why the two are different.
Consistency gives a set of diagnoses. It does not order them. The natural order is probabilistic: given the observation, how probable is each diagnosis? Bayes’ rule gives the form:
If faults are independent, the prior factorizes. Let pc be the prior probability that component c is faulty. Then
Taking logs turns the product into a sum, and the normalization into a constant:
The first sum is a per-component fault weight. The second is the likelihood: how well the diagnosis predicts the observation. If every consistent diagnosis is assumed to predict the observation equally well, the likelihood is constant and the ranking is by the sum of fault weights. That is the “simple prior” ranking used in the lab.
| Diagnosis | Size | Prior weight | Posterior · component priors | Posterior · uniform |
|---|---|---|---|---|
{A1} | 1 | 0.0420 | 55.2% | 33.3% |
{N1} | 1 | 0.0332 | 43.7% | 33.3% |
{O1} | 1 | 0.0008 | 1.1% | 33.3% |
The numbers are computed from (4.2), including the (1 − p) factors for the gates assumed normal, then normalized. The shape matters more than the values: under component priors, {A1} leads because an AND gate is assumed less reliable than the output OR; under a uniform prior, the three tie because they have the same size. Neither ranking is a proof. The first is a bet on the reliability numbers; the second is a bet that all gates are equally likely to fail.
Minimal is not probable
Minimality and probability are different criteria. A minimal diagnosis is subset-minimal: no proper subset is a diagnosis. A probable diagnosis is the one with the largest posterior. They can disagree in both directions.
Suppose the minimal conflicts are {g1, g2} and {g1, g3}. The minimal hitting sets are {g1} and {g2, g3}. The singleton is minimum-cardinality; the pair is still subset-minimal, because neither {g2} nor {g3} hits the first conflict. If g1 is highly reliable with p = 10−4 and g2, g3 have p = 0.05 each, the pair’s fault weight is about 0.0025 and the singleton’s about 0.0001: the two-fault diagnosis is roughly 25 times more probable. The one-fault answer is “simpler,” and it is also the less likely one.
This is not a paradox. Parsimony is a prior about the world; probability is a calculation over priors and likelihoods. If g1 almost never fails, the calculation can override the simplicity heuristic. State which criterion you are using, and do not call a minimal diagnosis “the most likely” without a prior.
Failure probabilities come from reliability data, manufacturer specifications, fleet statistics, expert elicitation, or a learned model. They are uncertain and often correlated: a shared power supply, a common batch, a common environment. The independent-fault prior in (4.2) ignores those correlations, and a model that ignores them can be badly miscalibrated. A flat prior is not neutral; it is a claim that all faults are equally likely.
Likelihood, fault modes, and explaining away
The independent-fault model is a simplification. Fault modes and correlations can change the ranking; the independent-fault prior cannot represent “explaining away,” where observing one cause lowers the probability of another. Medical diagnosis is the canonical case: diseases are not independent, symptoms are noisy, and the useful output is a posterior over a differential, not a single minimal set.
05 / LLMs & checkersPropose with a model, dispose with a proof.
The hypothesis spaces in real diagnosis are too large to enumerate. A circuit has millions of gates; a software system has thousands of components and configuration parameters; a patient has a history, a medication list, and a physical exam. The symbolic filter is only useful if something can propose good candidates. This is where a large language model earns its place: not as an oracle, but as a proposal distribution.
The architecture has four parts. The LLM reads the observation and the background — a netlist, a log, a clinical note, a bug report — and proposes candidate hypotheses with rationales. A formalizer turns each candidate into the checker’s language, or rejects it as unformalizable. A symbolic verifier tests entailment and consistency against the model. A ranker orders the survivors by prior, likelihood, or cost. If no candidate survives, the conflict sets are fed back to the proposer: “the observation contradicts the assumption that N1, A1, and O1 are all normal; propose a fault in one of them.”
What the evidence says
Abductive language reasoning is hard, and the benchmarks show it. Bhagavatula et al. (2020) introduced ART, a dataset of narrative contexts and explanations; the best model then reached 68.9% on abductive NLI against a human 91.4%. That is a gap in choosing the more plausible explanation, not in producing a formal proof. A model can be fluent at explanations and still fail the constraints that make an explanation adequate.
Later work separates the capabilities. “An Incomplete Loop” (2024) finds a dissociation: language models can learn from few-shot prompts without being able to explain their own prediction rules, and can infer useful task descriptions while failing to learn from human-written descriptions of the same task. “Language Models Can Improve Event Prediction by Few-Shot Abductive Reasoning” (2023) shows the productive version: the LLM proposes possible causes for an event, a search module finds matching past events, and a scoring module combines the evidence. The LLM is inside a larger system, not the final predictor.
The caution is equally clear. “Do Language Models Follow Occam’s Razor?” (2025) evaluates whether LLM hypotheses are both correct and simple, and finds that models handle simple scenarios but struggle with complex world models and with producing high-quality hypotheses, even with in-context learning and reinforcement learning with verifiable rewards. Kambhampati et al. (2024) draw the general lesson: an LLM cannot reliably verify its own output, so it should generate candidates for an external critic. In abduction, the critic is the consistency checker plus the ranking.
Failure modes at the interface
- The cause is outside the checker’s vocabulary. The LLM says “the connection pool is exhausted”; the model has no predicate for it. The hypothesis is dropped or forced into a wrong category.
- The explanation is plausible but insufficient. The LLM says “the server is overloaded”; the observation is a timeout at 03:14. The checker rejects it because it does not entail the timestamp. That is the checker doing its job.
- The checker is incomplete. The true cause is expressible, but the theory is too weak to derive the observation, so the true hypothesis is rejected. Model fidelity, not LLM quality, is the bottleneck.
- The formalization drifts, and anchoring compounds it. The natural-language hypothesis and the formal encoding are not the same claim; the checker verifies the encoding. The first plausible cause also tends to dominate the list, and a correct answer on a public case may reflect memorization. A chain-of-thought may be persuasive, but a rationale is not a proof.
It does not mean the LLM is more likely to be right. It means the proposal step is cheaper and broader, so the checker and the ranker become the bottlenecks. The guarantee is conditional on the model, the formalization, and the checker’s soundness. If any of those is wrong, scale makes the wrong answer faster, not truer.
06 / Ambiguity & costWhy one observation is rarely enough — and what an explanation costs.
The circuit is not a pathological example. Ambiguity is the normal case, for five structural reasons.
- Combinatorics. A diagnosis is a hitting set. Independent conflicts multiply: k disjoint two-element conflicts give 2k minimal diagnoses. The observation constrains each conflict separately; it does not choose which element failed.
- Masking. One fault can hide another. In the lab’s dormant-gate preset, the unselected AND gate
A2is a suspect even though its correct output is 0: a fault that forces it to 1 propagates through the OR. A gate “not on the active path” is not necessarily irrelevant. - Abstraction. The model says “abnormal,” not “stuck-at-0” or “intermittent.” Many fault modes map to one observation; refining to modes needs more tests or a richer model.
- Partial observability. Only some signals are outputs. Internal nodes are free, and a fault upstream can be compensated downstream. The monitor is a deliberate extra observation; remove it and the ambiguity grows.
- The hypothesis language. If the cause is not in the vocabulary — a broken trace, a wrong specification, a mislabeled sensor — no inference will find it. The observation is consistent with the model plus a fault only if the fault is representable.
Four notions of minimality
The word “minimal” is overloaded, and the differences matter for what a system reports.
| Criterion | Definition | What it implies | What it does not imply |
|---|---|---|---|
| Subset-minimal | No proper subset is a diagnosis. | The diagnosis has no redundant faults. | It need not have the smallest cardinality. |
| Minimum cardinality | No diagnosis has fewer faults. | It is subset-minimal. | It need not be the most probable or the cheapest to repair. |
| Minimum cost | No diagnosis has a smaller weighted sum. | It reflects repair or test costs. | It need not be subset-minimal if costs are non-monotone. |
| Most probable | Largest posterior under a prior and likelihood. | It reflects the assumed failure model. | It need not be minimal at all. |
Reiter’s theorem is about subset-minimal diagnoses. The lab reports subset-minimal sets. The ranking is a separate layer. If you want the minimum-cardinality diagnosis, you can filter the minimal sets by size; if you want the most probable, you need a prior; if you want the cheapest repair, you need costs. None of these is the “correct” definition in the abstract; each answers a different question.
The cost of explanation
An explanation has computational, cognitive, and action costs. Enumeration and ranking can be exponential; a six-fault diagnosis is harder to act on than a one-fault diagnosis; and the best next step is the test that most reduces the expected cost of the remaining uncertainty, not necessarily the most probable diagnosis. In the circuit, a probe on ns separates {N1} (0) from {A1} and {O1} (1); a probe on p then separates {O1} (1) from {A1} (0). A probe on outn does not distinguish any of them, because all three produce the same outn. The value of a test is how much it changes the diagnosis set.
If a common cause is not in the hypothesis language, the minimal diagnosis will posit several independent faults instead of one shared cause. Two symptoms from a shared power rail look like two gate faults when the rail is not a component. Minimality is relative to the model; a missing abstraction can make the “simplest” explanation structurally wrong.
07 / CasesMedicine, circuits, software — and what each one trains.
The same architecture appears in domains that share almost no vocabulary. The differences are the hypothesis language, the fidelity of the checker, and the cost of a wrong answer.
Medical diagnosis
Expert systems were the first large-scale abductive machines. MYCIN (Shortliffe 1976) used rules and certainty factors to recommend antibiotics for bloodstream and meningitis infections. It chained backward from a goal, asked for evidence, and could explain which rules fired. It was not consistency-based: its certainty factors were not calibrated probabilities, and its knowledge was compiled from experts. But the shape is abductive — hypothesize an organism, gather evidence, revise — and the explanation facility made the reasoning inspectable.
INTERNIST-1/QMR (Miller, Pople, and Myers 1982) made the combinatorial problem explicit: its hypotheses were diseases, its knowledge base covered much of internal medicine, and its hard part was the interaction of multiple diseases. A modern LLM triage assistant has the same skeleton: the model proposes a differential, a checker tests it against lab ranges and guidelines, and a clinician ranks and acts. The guarantee is consistency with the guideline and the record, not diagnostic truth; missing data, base rates, and inequities are outside the checker.
Circuit and board diagnosis
The circuit here is a toy version of a mature practice. De Kleer and Williams’ GDE (1987) introduced conflict recognition and candidate generation for multiple faults, and made measurement selection part of the loop: after generating candidates, choose the probe that best discriminates them. In industry, the same ideas appear in test-pattern generation, board test, and scan-chain diagnosis. The difference is scale and noise — millions of gates, vectors of test responses, timing and layout — but the logic and the caveat are the same: a diagnosis is relative to the model.
Software and configuration
Delta debugging (Zeller and Hildebrandt 2002) is abduction without an explicit logical model. A program fails on an input; the input is reduced by bisection until every remaining element is necessary for the failure. The result is a 1-minimal failing input: removing any single element makes the failure go away. The “cause” is a minimal set of input elements, and the procedure is a search rather than a proof. Abduction requires a notion of consistency and a way to test it, not necessarily a first-order theory.
Log and dependency diagnosis adds the model back: an anomaly detector flags a symptom, a dependency graph computes the components that could reach it, and a ranker orders them. An LLM can propose causes from the logs, while the graph checks reachability. The checker is cheap and incomplete: it knows the service graph, not the code paths inside a service. Configuration repair is the cleanest analogue of hitting sets: a dependency solver returns a minimal unsatisfiable core, and the repair is a hitting set of the cores.
| Domain | Observation | Hypothesis space | Checker | Ranking | Guarantee |
|---|---|---|---|---|---|
| Circuit | Inputs and output values | Faulty gates, fault modes | Gate-level model; SAT or propagation | Prior, cost, measurement value | Consistency relative to the netlist |
| Medicine | Symptoms, labs, history | Diseases, syndromes, drug effects | Guidelines, lab ranges, causal model | Prevalence, likelihood, urgency | Consistency relative to the guideline and record |
| Software | Logs, traces, failing input | Services, commits, configs | Dependency graph, delta debugging | Recency, prior, blast radius | Reachability or 1-minimality |
| Science | Measurements | Mechanisms, parameters, laws | Simulator, statistical model | Likelihood, simplicity, scope | Fit relative to auxiliary assumptions |
The table makes the pattern visible. The checker is always a model, and the guarantee is always relative to it. The ranking is always a choice. The output that is honest is a set of explanations with their assumptions and the tests that would discriminate them — not a single confident cause.
08 / RecapWhat you should be able to do now.
Distinguish deduction, induction, and abduction, and state why abduction is ampliative rather than truth-preserving.
Define consistency-based diagnosis as a set of components whose abnormality makes the system description, observation, and normality assumptions satisfiable.
Compute minimal conflict sets, and explain why a diagnosis must hit every one of them.
Use Reiter’s theorem: minimal diagnoses are the minimal hitting sets of the minimal conflicts.
Write an abductive logic program with abducibles and integrity constraints, and show how a new observation prunes the explanations.
Rank diagnoses by a prior, and distinguish subset-minimality from minimum cardinality and from maximum posterior probability.
Describe the LLM-proposes/symbolic-checker pattern, and state exactly what the checker guarantees and what it does not.
Explain why one observation rarely identifies a unique cause, and name the five structural reasons.
Exercises
- Add a gate. Add a seventh gate to the lab (or reason about one) and recompute the conflicts for the hook observation. Does the diagnosis set grow, shrink, or stay the same?
- Find the unique case. The lab has a preset where the observation pins a single gate, and presets with three diagnoses. What property of the conflict family explains the difference?
- Minimal versus minimum. Give a conflict family with a minimal diagnosis of size 2 and a different minimal diagnosis of size 1. Prove the size-2 set is subset-minimal, then assign priors that make it more probable.
- ALP the lamp. Add a second bulb and a rule that at most one bulb is broken. Observe that both are off; enumerate the explanations; add a power-rail test and show how the set shrinks.
- Probe value. For the hook observation, compute which single probe —
ns,p,q, orout— reduces the three diagnoses most. Justify with the sets before and after the probe; no single probe identifies one diagnosis. - Ask a model, check it. Take a failing unit test and ask an LLM for five possible causes. Write each as a formal hypothesis. Which ones can a checker test? Which are unformalizable? Report the set that survives.
Check your understanding
Ten questions, with explanations. The score is not the point; the questions you cannot answer are the reading list.
Reading list
The first five are the spine. The rest are the next layer, including the LLM-abduction work that is still moving.
A Theory of Diagnosis from First Principles
Reiter · Artificial Intelligence 32(1), 1987 · the definition, the theorem, the algorithm
Diagnosing Multiple Faults
de Kleer & Williams · Artificial Intelligence 32(1), 1987 · GDE, conflicts, measurement selection
Abductive Logic Programming
Kakas, Kowalski & Toni · Journal of Logic and Computation 2(6), 1992 · the ⟨P, A, IC⟩ framework
The Complexity of Logic-Based Abduction
Eiter & Gottlob · Journal of the ACM 42(1), 1995 · why abduction is harder than deduction
The Inference to the Best Explanation
Harman · The Philosophical Review 74(1), 1965 · the philosophical frame
Abductive Commonsense Reasoning
Bhagavatula et al. · ICLR 2020 · ART, αNLI, the 68.9% vs 91.4% gap
An Incomplete Loop: Deductive, Inductive, and Abductive Reasoning in Language Models
2024 · the dissociation between explaining and predicting
Language Models Can Improve Event Prediction by Few-Shot Abductive Reasoning
2023 · LAMP: LLM proposals inside a search-and-score loop
Do Language Models Follow Occam’s Razor?
2025 · parsimony in inductive and abductive hypotheses
LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks
Kambhampati et al. · 2024 · generate, then verify externally
Simplifying and Isolating Failure-Inducing Input
Zeller & Hildebrandt · IEEE TSE 28(2), 2002 · delta debugging
INTERNIST-1: An Experimental Computer-Based Diagnostic Consultant
Miller, Pople & Myers · NEJM 307, 1982 · multiple diseases and the perfect-model problem
The circuit, the hitting-set trace, and the propose-check loop are schematics drawn for this lecture, not reproductions of paper figures. The diagnosis sets and the ranking tables are computed from the six-gate model by exhaustive enumeration; the priors are illustrative and labeled as such. The only empirical numbers quoted are from the cited papers: the 68.9% and 91.4% figures are Bhagavatula et al.’s reported ART results. No benchmark was run for this lecture.