Real patients often have more than one thing wrong at once. When a language model diagnoses such a case, it has to do two different jobs. The first is recalling domain facts: which findings each candidate disease produces, and which findings rule it out. The second is combining those facts: choosing the smallest set of diseases that together account for everything observed, without double-counting a symptom or ignoring a contradiction. Logic research has long shown that the second job, called abductive assembly (building one joint explanation out of several partial ones), is NP-complete even in very simple rule languages. In such languages the forward, deductive direction runs in linear time. Current medical language model work nonetheless handles the two jobs together inside one free-text reasoning trace, or scores each candidate disease on its own.
This note proposes to split the jobs. The model is asked only small, local questions: for disease $h$ and finding $f$, does $h$ explain $f$, contradict it, or neither? The answers form an explicit table. An exact optimizer then searches that table for the most plausible set of diseases. The claim is that much of what looks like a domain knowledge gap on multi-condition cases is really an assembly failure. The model often knows the local facts but cannot combine them reliably. If that is right, an explicit table plus a solver should beat end-to-end reasoning models, and the advantage should grow with the number of co-occurring conditions. The table also yields an auditable rationale, which targets the "right answer, wrong reason" problem.
Core Claim
On diagnostic cases with $k \ge 2$ co-occurring conditions, two predictions follow. First, the accuracy of end-to-end language models falls sharply as $k$ and the overlap between candidates' findings grow. Second, a pipeline that asks the same model for local disease–finding judgments and hands assembly to an exact solver loses much less accuracy over the same range. The test that separates the explanations is an audit of the local judgments. If clinicians find the local table entries largely correct on cases the end-to-end model gets wrong, the failure lies in assembly, not in missing knowledge. That would change what the field should build for expert domains: more careful combination, not more retrieval.
Position Relative to Prior Work
The motivation comes from two unconnected bodies of work. On the theory side, Towards a Functional Architecture for Intelligence Based on Generic Information Processing Tasks named the exponential blowup of combining sub-hypotheses as the core difficulty of diagnosis. On Computing all Abductive Explanations proved that joint explanation of multiple observations is NP-complete even for Horn theories. Abductive and Default Reasoning: A Computational Core showed that selecting support for a hypothesis stays NP-hard even when the explanation is unique. Compilability of Abduction showed that preprocessing the background knowledge does not remove this hardness at query time. These results constrain the design. We should not expect any fixed model, retrieval store, or precompiled knowledge base to make assembly easy in general.
They also point to where exactness is affordable. Abduction with Bounded Treewidth shows that when the interaction structure has small treewidth (roughly, it decomposes into small, loosely linked pieces), abduction runs in linear time in practice. There, a Datalog-based solver handled 301-node instances in about 6 ms while an automata tool ran out of memory. A differential diagnosis usually involves tens of candidates and tens of findings. That size is small enough for exact search, and treewidth gives a principled way to measure how hard each instance is.
On the empirical side, the closest work is Closing the Abductive Gap. It scores each candidate disease against the patient using Tversky's feature-contrast model, which penalizes missing expected findings, contradictions, and unexplained findings, and it uses the score both in prompting and as a reinforcement learning reward. It evaluates hypotheses one at a time ($H_i$ against the observations) and explicitly leaves multi-disease assembly and complexity analysis open. Our proposal reuses its idea of penalizing unexplained and contradicted findings. It differs in three ways: it scores sets of diseases jointly, it hands the combinatorial search to a solver rather than the model, and it measures instance hardness.
Two other papers diagnose the failure we target. MedCaseReasoning shows that strong models get correct labels while recalling only part of clinicians' reasoning points. Diagnostic Reasoning in Natural Language (STRICTA) finds that model–expert agreement is high on extracting facts and breaks down at steps that integrate background knowledge. STRICTA also finds that models let a single negative observation propagate unchecked, which is an assembly-style error.
The knowledge-graph abduction systems are the other methodological neighbors. Controllable Logical Hypothesis Generation and Abductive Logical Reasoning on Knowledge Graphs show that frontier models produce "vibe-based" hypotheses that fail when executed as formal queries. They also show that execution-checked training fixes this. We take the lesson that hypotheses should be checked by execution. We do not take their setting, which requires formal entity identifiers and general-domain graphs.
Research Program
The pipeline has three stages. First, the model reads the case presentation, extracts a list of findings $F$, and proposes a candidate pool $C$ of up to about 20 conditions. We will test widening the pool with a second sampling pass so that a missed candidate is measured rather than hidden.
Second, for every pair $(h, f)$ with $h \in C$ and $f \in F$, the model is asked a single short question. The answer is a label $c(h,f) \in \{\text{explains}, \text{neutral}, \text{contradicts}\}$ with a one-sentence justification. The model also gives a coarse prior for each $h$, and flags any interaction pairs, for example "treatment of $h_1$ masks finding $f$," as constraints over pairs of diseases. Where the domain has a curated graph, table entries can be cross-checked against it. We treat the graph as a secondary signal, because Towards Medical Machine Reading Comprehension with Structural Knowledge and Plain Text attributes 44% of its errors to knowledge missing from both text and graph and 32% to retrieval noise.
Third, an integer program chooses the diagnosis set $S \subseteq C$ by minimizing
$$ J(S) = \sum_{h \in S} \big(\lambda - \log p(h)\big) + \alpha \,\big|\{f \in F : \text{no } h \in S \text{ explains } f\}\big| + \beta \,\big|\{(h,f) : h \in S,\ c(h,f) = \text{contradicts}\}\big|, $$
subject to the pairwise interaction constraints. Here $p(h)$ is the elicited prior, $\lambda$ is a per-disease parsimony cost that discourages adding diseases, and $\alpha, \beta$ weight unexplained findings and contradictions. The three weights are tuned on the training split and nowhere else. The chosen $S$ comes back with the table cells that justify it, which serve as the rationale.
Alongside the pipeline we compute, for every test case, the treewidth of the bipartite disease–finding graph induced by the "explains" entries, together with $k$ (the number of gold conditions) and the amount of finding overlap among gold conditions. These are our measures of assembly hardness.
The data will come from three sources. From MedCaseReasoning we take the 897 test cases and extract a subset whose final diagnosis names two or more conditions; its 13,092 training cases are used for tuning. From DiReCT, whose MIMIC-IV notes often carry several discharge diagnoses, we take a second multi-condition set; the file reports no numbers on it, so we will establish baselines ourselves. For controlled stress tests, we build composite cases by merging presentations of two or three single-diagnosis cases from different organ systems, then have clinicians review them for plausibility. These composites are marked as artificial and reported separately. The file lists no public multi-fault benchmark for the second domain we would want, cloud incidents; the Microsoft dataset in Recommending Root-Cause and Mitigation Steps for Cloud Incidents is internal. We therefore leave that domain as future work rather than overclaim.
Baselines
The naive reference is a single-pass prompt to the same base model that the pipeline uses: "list all diagnoses." This anchors how much any structure buys.
The strongest end-to-end competitor is a frontier reasoning model with long chain-of-thought. On single-diagnosis MedCaseReasoning, the best reported figure is diagnostic accuracy of 64.5% for OpenAI o3 in the 10-shot setting, with reasoning recall of 64.2% for DeepSeek-R1 (MedCaseReasoning). On MedXpertQA, o1 reaches 49.89% overall (MedXpertQA). No reported result was found on Lacuna for any model on multi-condition subsets or on DiReCT, so we run these models ourselves. For fairness, the reasoning model receives at least the total token budget the pipeline spends on elicitation, and it is prompted with the same parsimony instructions.
The strongest structured competitor is the feature-contrast scorer of Closing the Abductive Gap. Its paper reports up to 26% accuracy gains in its reinforcement learning setting but no absolute multi-condition number. We run it in two forms: as published, which picks the top single hypothesis, and extended to multiple conditions by scoring every pair and triple of candidates as a combined hypothesis. The extended form is the real threat, because it assembles by brute-force enumeration of combinations.
Three ablations isolate the key ingredient. The first gives the elicited table to the model and asks it to assemble, which isolates the solver. The second uses greedy set selection instead of exact optimization, which checks whether exactness matters. The third fills the table from a knowledge graph only, which isolates the model's local knowledge.
Beating the field means two things on the multi-condition sets, measured as set-level F1 over conditions: the pipeline beats the reasoning-model baseline and the enumerated feature-contrast scorer at matched compute. It also means the pipeline's accuracy drop from $k=1$ to $k \ge 3$ is significantly smaller than theirs. Matching at $k=1$ while winning at larger $k$ is the predicted pattern.
Why not just…?
Why not just use a stronger reasoning model with more test-time compute? Reasoning models do explore hypotheses. However, the evidence in Controllable Logical Hypothesis Generation is that even GPT-5/Thinking reaches only 18.7 execution Jaccard on FB15k-237 abduction, against 64.3 for a dedicated method, because its hypotheses are thematically right but fail when executed. That result comes from a different domain. The hardness-stratified experiment below tests directly whether the same pattern holds in diagnosis. If the reasoning model's curve is flat in $k$, the premise of this proposal is wrong and we will report that.
Why not just retrieve guidelines or knowledge-graph facts into the prompt? TheoremQA found that supplying theorem definitions gave no significant gain, because models could not apply the rules to the specific instance. The medical question-answering paper above traces most of its errors to missing or noisy retrieved knowledge. Retrieval addresses recall of facts. It does not address combining them, which the compilability result says stays hard even with preprocessed knowledge. We still include a retrieval-augmented variant of the reasoning baseline so that this is measured rather than asserted.
Why not just enumerate combinations with the existing feature-contrast scorer? With about 20 candidates there are 190 pairs, so enumeration is feasible and could match our accuracy. This is the most serious alternative. Three things favor the table. First, it needs one query per disease–finding cell rather than one holistic judgment per combination, and those holistic judgments may be inconsistent with one another. Second, its cost does not grow with the size of the combination. Third, it produces cell-level rationales that clinicians can check. If enumeration matches us at $k=2$ and $k=3$ at similar cost, our contribution shrinks to auditability, and we will say so. The composite cases with $k=3$ are where the two approaches should separate.
Why not just fine-tune on clinician reasoning traces? MedCaseReasoning reports 29% relative accuracy gains from fine-tuning on expert rationales, so this is a strong baseline for single diagnoses. We will fine-tune the same base model on the training split. The open question is whether the fine-tuned model's gains hold as $k$ grows, given that almost all training cases carry one diagnosis.
Decisive Experiments
The central experiment plots set-level F1 against $k$ and against the treewidth of each instance for every system. The hypothesis is supported if end-to-end systems degrade steeply with these hardness measures while the pipeline degrades gently. It is refuted if all curves are parallel.
The second experiment is a clinician audit of about 2,000 sampled table cells, drawn from cases the reasoning model gets wrong. If local cell accuracy is high on those cases, the error is in assembly. If it is low, the domain knowledge gap is real at the local level, and the solver cannot help. Either way we learn where the failure lies, which no current benchmark reports.
The third experiment reuses the adversarial pivot-removal and negation tests from Closing the Abductive Gap on multi-condition cases. The test is whether deleting a finding changes the pipeline's output only when the table says that finding was decisive. That is a direct check that the answer rests on the stated reasons.
Finally, rationale quality is scored with MedCaseReasoning's reasoning-recall metric applied to the justifications of the selected cells. This tests whether explicit assembly also narrows the gap between right answers and right reasons.
References
- Towards a Functional Architecture for Intelligence Based on Generic Information Processing Tasks
- On Computing all Abductive Explanations
- Abductive and Default Reasoning: A Computational Core
- Compilability of Abduction
- Abduction with Bounded Treewidth: From Theoretical Tractability to Practically Efficient Computation
- Closing the Abductive Gap: Cognitive Feature Matching to Evaluate Hypotheses in Medical Diagnosis
- MedCaseReasoning: Evaluating and learning diagnostic reasoning from clinical case reports
- STRICTA: Structured Reasoning in Critical Text Assessment for Peer Review and Beyond
- Controllable Logical Hypothesis Generation for Abductive Reasoning in Knowledge Graphs
- Advancing Abductive Reasoning in Knowledge Graphs through Complex Logical Hypothesis Generation
- Towards Medical Machine Reading Comprehension with Structural Knowledge and Plain Text
- Recommending Root-Cause and Mitigation Steps for Cloud Incidents using Large Language Models
- MedXpertQA: Benchmarking Expert-Level Medical Reasoning and Understanding
- TheoremQA: A Theorem-driven Question Answering Dataset