When several hidden causes can each produce the same observed effect, seeing the effect makes the causes compete. Confirming one cause makes the others less likely. This is called explaining away. In large diagnostic networks such as the Quick Medical Reference (QMR) model, where hundreds of diseases link to thousands of symptoms, explaining away produces a posterior over diseases with several separate peaks: "disease A explains these twelve symptoms" and "disease B explains them" are both plausible, while states in between are much less so. Standard samplers flip one disease at a time. To travel from one explanation to the other, such a sampler must pass through a state where both rare diseases are present, or neither is. Those states have tiny posterior probability, so the sampler stays in whichever explanation it found first.
We propose a Markov chain whose basic move is to exchange explanations. It removes an active disease and adds an inactive one, or a pair, chosen because it covers exactly the symptoms the removed disease was solely responsible for. The candidates are found with word-level bit operations, the trick constraint solvers use to filter domains (the set of values a variable may still take) a whole machine word at a time. Each disease's symptom set is stored as a bitset, and current coverage is kept as bit-sliced counters. A single AND plus a population count then scores every candidate replacement in a few machine instructions. The move is accepted with an exact Metropolis–Hastings ratio, so the chain targets the true posterior. The claim is that this one targeted move removes the mixing barrier that explaining away creates, at a cost of $O(Dm/w)$ machine operations per move. Here $D$ is the number of diseases, $m$ the number of positive findings, and $w$ the word width. The intended regime is cases with too many positive findings for exact inference and too much ambiguity for variational bounds.
Core Claim
Exact inference by Quickscore is exponential in the number of positive findings. Negative findings factor out exactly into the disease priors, so all the difficulty comes from positive findings tying causes together. That coupling is the dense moralized graph that Variational Probabilistic Inference and the QMR-DT Network identifies as the source of intractability.
For a single-site sampler, the rate of escape from explanation $A$ to a competing explanation $B$ is controlled by the posterior mass of the "bridge" states:
$$ \text{escape rate} \approx \frac{P(d_A{=}1, d_B{=}1 \mid F)}{P(d_A{=}1, d_B{=}0 \mid F)}. $$
Here $d_A, d_B$ are the disease indicators and $F$ is the full set of findings. In words, this is the posterior ratio between the over-explained state and the current mode. The form follows from the fact that a single-site chain must visit $\{A,B\}$ or $\varnothing$ on the way. The $\varnothing$ route costs a factor of the leak probability for every symptom that $A$ alone explained. The over-explained route costs the prior odds of $B$ times its penalty from negative findings.
Theory-Based Causal Inference argues that rare causes need much stronger evidence to survive being explained away. Read in sampling terms, that is exactly when this ratio is small. Our swap move jumps directly from $\{A\}$ to $\{B\}$, so its escape rate is set by the posterior ratio of the two explanations themselves. This yields a falsifiable prediction. Single-site samplers get worse as disease priors shrink and as negative findings attached to competing causes accumulate. The swap chain's integrated autocorrelation time should stay roughly flat along both axes.
How the Pieces Fit
Explaining away is the phenomenon, and the posterior of a Noisy-OR network is the target. A Noisy-OR model treats each symptom as present if any of its active parent diseases, or a background "leak", independently triggers it. Three lines of prior work motivate the proposal.
Search-Based Methods to Bound Diagnostic Probabilities in Very Large Belief Nets bounds posteriors by best-first search over disease hypotheses. It uses negative product synergy, the formal condition under which one cause lowers another's posterior. Its search ranks hypotheses by "marginal explanatory power" and runs out of memory on dense symptom sets. We reuse its central insight, that a disease's value lies in the symptoms only it explains, but put it inside a Markov chain move rather than a search tree.
Jaakkola and Jordan replaced search with variational bounds, which were too wide to be useful in about half of difficult clinical cases. Structured Recognition for Generative Models with Explaining Away shows that factorized recognition models cannot represent competition between causes. It fixes this only for continuous Gaussian latents, whereas our latents are binary diseases.
Bit-parallel filtering supplies the method. Optimizing Simple Tabular Reduction with a Bitwise Representation updates the validity of whole word-sized blocks of constraint tuples with AND/NOT operations. We apply the same representation to coverage. Each disease $j$ has a bitset $B_j$ over the positive findings. Two global bitsets mark findings covered at least once ($C_1$) and at least twice ($C_2$). The findings explained only by $j$ are then $B_j \wedge C_1 \wedge \neg C_2$. Scoring a replacement $k$ takes one AND and one popcount.
Discrete state-space mixing supplies the evaluation setting and the competitors. Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints and Uniform Solution Sampling Using a Constraint Solver As an Oracle showed that local samplers get trapped by barriers and that solver-guided global moves escape them. Both target uniform distributions over hard-constraint solutions, not weighted posteriors with leak terms.
Exponential proof complexity enters as a constraint on design, not as the core mechanism. We could hand arbitrary-size, coverage-preserving swaps to a SAT oracle, or use a hashing-based sampler that adds random parity (XOR) constraints to cut the space into small cells. Both choices put a resolution-based solver in the inner loop. Hardness of Random Reordered Encodings of Parity for Resolution and CDCL proves that randomly ordered parity encodings have linear treewidth with high probability. This forces exponential resolution proofs, which clause-learning (CDCL) solvers cannot avoid. Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling reports that XOR handling consumed over 99% of runtime in earlier tools, before native Gaussian elimination. We therefore cap swap size, which keeps the move solver-free. We then test empirically whether a hashing sampler with native Gaussian elimination still slows down as positive findings grow, because the covering part of the formula remains even after the parity part is handled.
Research Program
We will build a sampler over disease vectors $d \in \{0,1\}^D$. Negative findings are absorbed exactly into per-disease prior odds. Positive findings enter through the exact Noisy-OR likelihood $1-(1-\ell_i)\prod_j q_{ij}^{d_j}$, where $\ell_i$ is the leak of finding $i$ and $q_{ij}$ is the probability that disease $j$ fails to trigger it.
The chain mixes three kernels. The first is ordinary single-site Gibbs updates. The second is one-for-one explanation swaps. The proposal picks an active disease $j$ and then an inactive $k$, with probability proportional to a tempered overlap score $\exp(\beta \cdot \mathrm{popcount}(B_k \wedge U_j))$, where $U_j$ is the set of findings only $j$ explains. The third is one-for-two split moves and their reverse two-for-one merge moves. A split chooses its second replacement disease to cover the bits of $U_j$ that the first replacement misses. Every kernel computes its reverse proposal probability with the same bit operations, so detailed balance holds exactly. Coverage counters update incrementally in $O(m/w)$ words per changed disease.
On the analysis side, we will prove the bridge-ratio statement above for a two-explanation family with planted, overlapping bitsets. We will show that the swap kernel's spectral gap on that family does not depend on the prior odds. We will also characterize when one-for-two moves are needed, namely when one cause is explained away by the conjunction of two others. On the engineering side, we will measure how much of the gain comes from bitwise scoring rather than from the move design. To do that we compare against a scalar implementation of the same proposals.
Baselines
The naive reference point is single-site Gibbs sampling on the disease variables with exact Noisy-OR conditionals. This is the method practitioners would reach for first. It is run with the same likelihood code, the same initialization (from the prior and from a greedy cover), and the same wall-clock budget. Beating it means lower total-variation error on disease marginals at equal time, plus correct mode proportions on ambiguous cases.
The strongest generic competitor is replica-exchange (parallel-tempering) Gibbs, which also targets multimodality. No paper in our file evaluates it on diagnostic networks. We give it the same number of CPU cores as the swap chain has parallel chains, and we tune its temperature ladder on held-out cases with a fixed budget of twenty configurations. Beating it means higher effective samples per second of the mode indicator.
For exactness we use Quickscore wherever positive findings are few enough. The reported reference is that exact Quickscore took 27 seconds on tractable CPC cases, while variational approximation took 0.3 to 0.8 seconds (Variational Probabilistic Inference and the QMR-DT Network). Above that threshold, exact Quickscore is the method we must replace, not beat.
The strongest bounding method is Henrion's TopN search. It reports an average of 18 seconds to bound posteriors on 12 SAM cases, against 94 minutes for stochastic sampling, with a mean standard error of 1.2% against exact Quickscore (Search-Based Methods to Bound Diagnostic Probabilities in Very Large Belief Nets). We will reimplement it under the same memory cap. Beating it means matching 1.2% marginal error in less time on cases where it fits in memory, and continuing to produce estimates on dense cases where it does not.
Jaakkola–Jordan variational bounds are the deterministic competitor. Beating them means informative intervals, from posterior quantiles across independent chains, on the cases where their bounds are vacuous.
The solver-based competitor is a hashing sampler: UniGen3 with BIRD2's native Gaussian elimination (Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling). It runs on a weight-discretized CNF encoding of the same posterior, with the same timeout. Two ablations isolate the key ingredient. One keeps the swap moves but chooses replacements uniformly at random rather than by bitset overlap. The other keeps targeted moves but computes the overlap scores with scalar loops. We found no reported result on Lacuna for posterior sampling error on aQMR-DT or Noisy-OR topic graphs by any of these methods. All numbers on our metric will therefore be produced in this study.
Why not just…?
Why not just run parallel tempering? Tempering is the most serious threat, because heating the chain flattens the bridge states. Its weakness here is that explaining-away barriers come from many small prior and leak factors multiplying together. The temperature needed to flatten them may melt the posterior's structure, and the needed ladder length grows with the number of findings involved. This is a prediction, not an established result. The tempering-versus-swap comparison at matched cores, with the ladder tuned, is the experiment that settles it. If tempering matches the swap chain's effective samples per second, we will report that and narrow the claim to cost per move.
Why not just use variational bounds or a structured recognition model? Jaakkola and Jordan report vacuous bounds on roughly half of hard cases. Factorized posteriors cannot represent competing causes at all, as Structured Recognition for Generative Models with Explaining Away demonstrates. Its structured fix assumes Gaussian latents, and binary diseases on separate modes violate that assumption. We will still report variational intervals on every case, so that the cases where they are informative are visible.
Why not just run Quickscore, or TopN search? Quickscore is exact and should be used whenever positive findings are few, so we treat that regime only as ground truth. TopN's best-first frontier grows with symptom density, which is the failure its author reports. We will plot both methods' runtime and memory against positive-finding count to locate the crossover.
Why not just use a hashing sampler with native Gaussian elimination? BIRD2 removes the parity bottleneck that Hardness of Random Reordered Encodings of Parity for Resolution and CDCL explains. On its own suite of 1,896 instances, it solved 77 more counting and 51 more sampling instances than its predecessors. Two costs remain. The covering clauses still have to be refuted by resolution inside each cell, and weight discretization adds variables. We predict runtime will still climb with the number of positive findings. If it does not, the hashing sampler is the better tool, and we will say so.
Proposed Experiments
We use the anonymized QMR knowledge base (aQMR-DT) studied in Unsupervised Learning of Noisy-Or Bayesian Networks. Cases are generated by forward sampling, so planted diseases are known, and we stratify them by number of positive findings, from about 10 to over 60. To test scale, we use the large Noisy-OR topic graphs on DBLP and Yelp from Variational Training for Large-Scale Noisy-OR Bayesian Networks. We also construct synthetic planted-ambiguity networks in which two or three disjoint disease groups have identical finding bitsets, so exact mode proportions are known in closed form.
The metrics are as follows. We measure total-variation and KL error of disease marginals against Quickscore where it is tractable, and against agreement of very long multi-chain runs elsewhere. We record the integrated autocorrelation time of a mode indicator, along with effective samples per second. We count the fraction of planted posterior modes visited, and report memory use.
The decisive check is the rare-cause sweep on the planted networks. We hold the likelihood fixed and lower the disease priors over four orders of magnitude. The bridge-ratio analysis predicts that single-site Gibbs autocorrelation time grows roughly inversely with the prior odds, while the swap chain's stays flat. If the swap chain also degrades, the targeted move is not doing the work the claim says it does.
The second check is the random-replacement ablation. If uniformly chosen swaps mix as well as overlap-targeted ones, then bitset filtering contributes nothing beyond what generic block moves already provide. The third check plots hashing-sampler runtime against the number of positive findings, and against the measured treewidth of the CNF-plus-XOR encoding. It tests whether resolution-hard covering structure, rather than parity alone, is what keeps solver-in-the-loop samplers from serving this regime.
References
- Variational Probabilistic Inference and the QMR-DT Network
- Theory-Based Causal Inference
- Search-Based Methods to Bound Diagnostic Probabilities in Very Large Belief Nets
- Structured Recognition for Generative Models with Explaining Away
- Optimizing Simple Tabular Reduction with a Bitwise Representation
- Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints
- Uniform Solution Sampling Using a Constraint Solver As an Oracle
- Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
- Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling
- Unsupervised Learning of Noisy-Or Bayesian Networks
- Unsupervised Learning of Noisy-Or Bayesian Networks
- Variational Training for Large-Scale Noisy-OR Bayesian Networks