Bit-Shadow Junction Trees: Exact Marginals That Pay Only for Possible States

Exact probabilistic inference adds up a product of local tables over every joint assignment. It is #P-complete in general, and in practice it fails when the tables built for each cluster of variables no longer fit in memory. Many real models, such as genetic pedigrees, diagnostic networks and circuits, contain hard rules that force a large share of those table entries to be exactly zero. Standard junction-tree solvers allocate and multiply those zeros anyway. This proposal splits exact inference into two passes. The first is a cheap logical pass that runs on bit vectors and uses one bit per table entry, processed 64 or 512 at a time with hardware AND/OR and popcount. It computes exactly which entries of every cluster table can be part of a globally possible assignment. The second is the ordinary floating-point pass, run only over the surviving entries and stored in a packed array indexed by counting set bits.

The logical pass is the same message-passing algorithm run in the Boolean semiring (sum becomes OR, product becomes AND), so it inherits the junction tree's guarantees. After its two sweeps, each cluster's bitmap is exactly the projection of the set of nonzero-probability joint assignments onto that cluster. Discarding everything outside these bitmaps therefore leaves the partition function and every marginal unchanged. If the hypothesis holds, the memory wall moves in two ways. The logical pass needs 64× less memory than a dense double-precision table. The numeric pass needs memory proportional to the number of possible states rather than the size of the full Cartesian product.

Core Claim

Exact sum-product inference on deterministic models can be made to cost $O\big(\sum_C d^{|C|}/w\big)$ word operations for structure plus $O\big(\sum_C |S_C|\big)$ floating-point operations for numbers. Here $C$ ranges over junction-tree clusters with domain size $d$, $w$ is the machine word width, and $S_C$ is the set of cluster assignments consistent with at least one nonzero joint assignment. The claim is that this split is exact, not a bound. It is also cheap when there is no determinism: the logical pass adds roughly a $1/w$ fraction of the dense numeric work. Its gains grow with the fraction of zeros that are globally implied rather than only locally visible.

Exactness follows from a one-line argument. $Z=\sum_x \prod_a \phi_a(x_a)$ only receives contributions from assignments $x$ with every factor nonzero. Each such $x$ restricts on cluster $C$ to an entry in $S_C$. Zeroing every entry outside $S_C$ in any intermediate table therefore removes only terms that contribute zero to $Z$ and to every marginal. Boolean two-pass calibration on a junction tree computes $S_C$ exactly, because the tree is acyclic, which is the standard global-consistency property of jointree join/projection.

Relation to Prior Work

Three groups of prior work shape the proposal.

The motivating evidence is that determinism is both common and costly. Gogate shows that zero-probability regions break importance sampling through rejection, and proposes backtracking search to stay inside the feasible space. That is an approximate remedy; we target exact marginals. Dechter and Mateescu prove that variable elimination and AND/OR search explore the same space under a fixed order. They also show that once determinism is present, search with constraint propagation can explore less. Our logical pass is a way to give elimination-style, table-based inference that same benefit without switching to depth-first search.

The closest competitors compress determinism symbolically. Chavira and Darwiche replace tables with algebraic decision diagrams during elimination and compile Bayesian networks into arithmetic circuits. They report circuits "up to 5,000 times smaller" and st-3-2 inference dropping "from over 17 seconds to just 82 milliseconds". Bistaffa replaces tables with finite-state automata in bucket elimination and reports up to $5\times10^4$ speedups. However, that method is restricted to max-product and min-sum (MPE and weighted constraints), and toulbar outperforms it on iscas89. Both methods rely on pointer-based structures with costly canonicalization. We do not compress repeated values. We only remove structurally impossible entries, using flat bitmaps whose operations are single instructions. This is a narrower mechanism, and it applies directly to sum-product.

The bit-level technique comes from constraint satisfaction and graph mining. Li et al. recast arc-consistency filtering for alldifferent as bit-matrix breadth-first reachability and cut runtime by 60.65% on average over XCSP3. Van Kessel et al. show word-RAM traversal reducing $O(d)$ neighborhood scans to $O(d/w)$. Yuan et al. and Qiu et al. use full and truncated bitmaps for SIMD set intersection. None of these touches probabilistic tables. We reuse their machinery: word-aligned AND, OR-reduction along a dimension, and truncated bitmaps for sparse regions. We apply it to cluster supports.

The engineering baseline is Fast-BNI, which flattens junction-tree work across threads and streamlines table index mapping on dense arrays. It is complementary: our packed numeric pass can be scheduled the same way. However, Fast-BNI cannot avoid allocating zeros.

Research Program

We will build a junction-tree engine with three components.

The first is a bitmap support layer. Each factor and each cluster gets a bit array over its local assignment space, laid out in the same mixed-radix order as the numeric table. Extension to a larger scope, conjunction and OR-marginalization are written as strided word operations with AVX-512 inner loops. Truncated bitmaps, following Qiu et al., are used when a cluster's support is concentrated in a few blocks.

The second is the Boolean two-pass calibration itself. Its outcome is the exact $S_C$ for every cluster. We also measure how much of the pruning is already achieved after the upward sweep alone and after local arc consistency alone. This tells us whether global calibration is necessary or whether cheaper filtering suffices.

The third is a packed numeric layer. Surviving entries are stored contiguously. An entry's position is the popcount of the bitmap prefix, computed with precomputed block counts in the standard rank-structure style. This makes extension and marginalization index maps computable without hashing. When a cluster's support density falls below a threshold, storage switches to a hash map of tuples. A bitmap costs one bit per possible entry, while a hash entry costs on the order of a hundred bits, so the crossover is near density $1/100$. We will measure the crossover rather than assume it.

The analysis component characterizes when the method helps, as a function of one quantity: the fraction of dense entries that are globally impossible. This is reported per instance alongside the speedup. A secondary analysis covers clusters too large for even the bitmap. There we test whether computing supports cluster by cluster, with only separator bitmaps resident, keeps peak memory near $\max_C |S_C|$.

Baselines

The naive reference point is the same engine with the logical pass disabled, which is a dense-table junction tree with identical elimination order, code paths and compiler flags. Any speedup is then attributable to pruning and packing, not to implementation quality.

The strongest dense competitor is Fast-BNI (Jiang et al.), run from its released configuration on the same machine, thread count and junction tree. On Munin4 it reports finishing in "less than one hour", against "nearly three days" for UnBBayes and "between 3 and 6 hours" for prior parallel methods. Beating it means matching its Munin4 time within a small overhead, since Munin4 is not expected to have heavy global determinism, and being clearly faster or solving instances it cannot fit on deterministic networks.

The strongest determinism-aware competitor is ADD-based compilation (Chavira and Darwiche), whose reported st-3-2 time is 82 milliseconds. We will compare total compile-plus-query time and peak memory under the same order and memory cap. Beating it requires lower end-to-end time on a majority of the high-determinism networks, or solving instances where diagram compilation runs out of memory. Matching it while being simpler would be a weaker but still reportable result.

FABE is excluded from marginal tasks because it does not do sum-product. For the partition function on the UAI/PIC suite we report IBIA (Bathla and Vasudevan) as an approximate reference: 1705 of 1717 instances within 8GB. This is not a competitor on accuracy. It shows how many instances an exact method would need to reach before approximation stops being the only option. We found no reported exact-partition-function coverage on UAI/PIC in Lacuna to compare against.

Two ablations isolate the key ingredient. The first replaces Boolean calibration with arc-consistency domain filtering followed by dense tables. The second keeps calibration but stores supports as hash sets instead of bitmaps. Every system gets the same 8GB cap used by IBIA and a fixed time limit, and none is tuned per instance.

Why not just…?

Why not just run arc consistency as preprocessing and keep dense tables? Local consistency removes impossible values of single variables. It does not remove impossible combinations inside a cluster, which are what fill high-width tables. Li et al.'s bitwise filtering shows this step can be made fast, but speed does not change what it removes. The first ablation measures the gap directly. If domain filtering captures most of the pruning on pedigree and circuit networks, the global pass is unnecessary and we will say so.

Why not just use decision diagrams or arithmetic-circuit compilation, which already exploit determinism? This is the real threat. Chavira and Darwiche's diagrams also merge equal nonzero values, which our method never does. They may therefore win outright on networks dominated by repeated parameters. Our bet is narrower: when the zeros are the redundancy, flat bitmaps with single-instruction operations beat pointer diagrams on both compile time and memory. The head-to-head on the Bayesian network repository decides this. A loss there would restrict our contribution to instances outside the reach of compilation.

Why not just use sparse hash tables of nonzero entries, as a database join would? For very sparse supports this is the right answer, and the engine falls back to it. The bitmap's case rests on intermediate densities, roughly above $1/100$, where it is both smaller and faster. The second ablation, plotted against measured support density, shows whether that regime actually occurs in real benchmarks.

Why not just accept approximation, as IBIA does? For linkage analysis, and for verifying circuit properties, users need exact posteriors. Zhou et al. document the same requirement for exact optima in protein design. Our method is aimed at that exact regime. It does not compete with IBIA on instances where approximation is acceptable.

Proposed Experiments

The suites are three. The first is the standard Bayesian network repository (alarm, water, Hailfinder, Pathfinder, Diabetes, Pigs, Munin2, Munin4, st-3-2), used for exact marginals. The second is the UAI/PIC set of 1717 instances, used for exact partition-function coverage within 8GB. The third is the pedigree and iscas89 families, used for marginals under heavy determinism. For pedigree marginals, no reported result was found in Lacuna, so we establish our own dense and diagram baselines there.

Metrics are wall time, peak memory, number of instances solved under the cap, the per-instance fraction of globally impossible entries, and agreement with the dense engine to floating-point tolerance as an exactness check.

The decisive checks are three. First, on Munin4 and the grid-like networks, which have little determinism, logical-pass overhead should stay within a few percent of dense time, as the $1/w$ cost model predicts. If it is larger, the layout is wrong. Second, across all instances, speedup should track the fraction of globally impossible entries. If speedup is flat while that fraction varies, the mechanism is not doing what we claim. Third, the method must solve instances under 8GB that the dense engine and Fast-BNI cannot. Without that, the contribution reduces to a constant-factor optimization that the diagram baseline may already match.