Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Restructuring Tractable Probabilistic Circuits

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every structured probabilistic circuit can be rewritten to respect any target vtree; polynomial-time for contiguous circuits, enabling multiplication across different vtrees, and depth O(log n) at size O(nh^3).

desk verdict A novel and mostly convincing paper on restructuring PCs to target vtrees; the general algorithm has a real but likely fixable bug in its separator routine, while the specialized contiguous and depth-reduction results are the stronger part. read the letter →

arxiv 2411.12256 v2 pith:ZMZWXAAE submitted 2024-11-19 cs.AI cs.LG

Honghua Zhang , Benjie Wang , Marcelo Arenas , Guy Van den Broeck This is my paper · ORCID
classification cs.AIcs.LG
keywords probabilisticcircuitsstructureddecomposabilityvtreecircuitrestructuringmultiplicationdepthreductioncontiguityBayesiannetworkrepresentation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Probabilistic circuits are weighted computation graphs that support exact inference, but their tractability is tied to a structural commitment: every product node must split its variables according to a fixed binary 'vtree'. This paper attacks the resulting rigidity by asking whether a circuit can be rewritten to respect a different vtree without changing the distribution it represents. The authors establish that any smooth structured-decomposable circuit can be restructured to any target vtree, and that the cost of the rewrite is governed by the size of certain separating sets of hidden variables attached to the target tree's nodes. The operational payoff is that circuits respecting different vtrees can be multiplied exactly where that was previously infeasible, and any structured circuit can be rebalanced to logarithmic depth with only a mild size increase. If the construction holds, training could use whatever structure is most expressive while inference runs on a restructured, faster one.

What carries the argument

The workhorse is the Bayesian-network reading of a structured circuit: each inner vtree node $v$ becomes a hidden categorical variable $Z_v$ whose value picks a product node in the circuit, turning the circuit into a tree-shaped Bayesian network $G_A$ via Theorem 3.3. On top of it sits the notion of a cover — a set of hidden variables that blocks all paths between a set of visible variables and its complement in $G_A$ — and a valid vtree labelling, which assigns each node $w$ of the target vtree a cover $C_w$ satisfying two additional blocking conditions relating the children's labels. Those conditions are exactly what makes the recurrence $$p(X_w \mid C_w) = \sum_{(C_l \cup C_r)\setminus C_w} p(X_l \mid C_l)\, p(X_r \mid C_r)\, p(C_l, C_r \mid C_w)$$ hold, and Algorithm 1 materializes it as a two-layer sum-product gadget per vtree node. Rounding out the machinery are the labelling procedures: greedy minimum d-separators for arbitrary targets (Algorithm 2), segment-tree covers for contiguous scopes (Algorithm 3), and a balanced-vtree construction (Algorithm 4) whose labels have cardinality at most 3, so that the hidden-state blow-up $h^{M'}$ stays polynomial.

What would settle it

Take a 4-variable hidden Markov model with a linear vtree, restructure it to a balanced binary vtree with Algorithm 1 using labels from Algorithm 2, and compare the two circuits on all 16 assignments: any nonzero difference in probabilities refutes the representational claim. The sharper, more local check is to enumerate every path in the tree-shaped Bayesian network for that example and test the three blocking properties of Definition 3.7 directly on the labelling returned by Algorithm 2, since a single path from the left half of a scope that reaches the right label set without being intercepted would break the factorization that the recurrence requires.

Watch

Extended reading notes

Core claim

The paper's central claim is that restructuring is a tractable, principled operation on structured-decomposable circuits: given any smooth structured-decomposable circuit $A$ over variables $\mathbf{X}$ and any target vtree $W$, Algorithm 1 constructs a new circuit respecting $W$ that represents exactly the same distribution. The route is to read $A$ as a tree-shaped Bayesian network: every inner node $v$ of the original vtree is assigned a fresh categorical latent variable $Z_v$ that selects which product node with that scope is active, and Theorem 3.3 shows the resulting network marginalizes to $p_A(\mathbf{X})$. Restructuring then becomes a labelling problem: assign to each node $w$ of the target vtree a small set $C_w$ of latents that blocks every path between the visible variables of $w$ and the rest, and the conditional distributions $p(X_w \mid C_w)$ compose through a single summation recurrence. The authors prove that for contiguous circuits — those whose every node is an interval in the variable order — the labels stay small (constant or $O(d)$ cardinality), which yields polynomial-time multiplication of circuits with different vtrees, and that a balanced construction reduces any structured circuit to depth $O(\log n)$ with size $O(nh^3)$.

Load-bearing premise

The restructured circuit is only guaranteed to represent the original distribution if the hidden-variable label attached to each node of the target tree actually satisfies the three blocking conditions of Definition 3.7; if the two children's labels fail to intercept the right paths in the Bayesian network, the single summation step of the recursion miscounts the distribution and the new circuit quietly represents something else.

Editorial extensions

If this is right

  • Two contiguous structured circuits that respect different vtrees can be multiplied exactly: in polynomial time $O(|A|^2|B|)$ when one of them has a linear vtree (Theorem 4.4), and in quasi-polynomial time when the first has depth $O(\log n)$ (Corollary 4.7).
  • The second circuit need not even be structured: a contiguous PC with a linear vtree multiplies with any contiguous circuit, structured or not, in polynomial time, so an HMM can be multiplied with a probabilistic context-free grammar (Theorems 4.2 and 4.9).
  • Any structured circuit over $n$ variables with hidden-state size $h$ can be rebalanced to an equivalent circuit of depth $O(\log n)$ and size $O(nh^3)$, a sub-quadratic bound that beats the cubic bound of generic depth reduction (Corollary 5.3).
  • Restructuring preserves determinism, so deterministic representations such as OBDDs can be converted to a differently ordered deterministic structure while retaining tractable model counting (Claim 3.12 and Section 3.4).
  • Because the rewrite is exact, a practitioner can train a circuit under a permissive or contiguous structure and switch to a different, faster structure at inference time without retraining (Section 7).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A practical corollary the authors do not push: if the balanced-labelling result holds at the stated constant cardinality, depth reduction is cheap enough to run on an already-trained circuit as a preprocessing step, so the $O(nh^3)$-size log-depth circuit is a concrete recipe for better GPU parallelization of inference, not just a bound.
  • The paper leaves it open whether its greedy labelling minimizes $M'$; one extrapolation is that the minimum labelling cardinality is the true complexity measure of vtree conversion, so finding minimum labellings would both give size-optimal restructuring and characterize exactly which pairs of vtrees admit polynomial-time multiplication.
  • A testable extension suggested by the contiguity results: any family of vtrees whose scopes are laminar or segment-like should admit small valid labellings, which would extend polynomial multiplication to new classes of circuits beyond the contiguous ones and, through the logical-circuit variant, give a reordering primitive for decision-diagram compilers.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces the task of restructuring structured-decomposable probabilistic circuits (PCs) to conform to a target vtree. It represents a structured PC as a tree-shaped Bayesian network over observed variables and one latent variable per vtree node (Theorem 3.3), then recursively constructs a new PC using conditional distributions p(X_w|C_w) for a labelling C_w of each target vtree node (Algorithm 1, Theorem 3.8). A greedy labelling algorithm based on minimum d-separators is claimed to produce valid labellings (Algorithm 2, Proposition 3.10). The paper then applies restructuring to multiply contiguous PCs that respect different vtrees (Theorems 4.4, 4.6, 4.9) and to reduce any structured PC to logarithmic depth with size O(nh^3) (Corollary 5.3).

Significance. If the main claims hold, this is an important step for PC inference: circuit multiplication without a shared vtree is a long-standing obstacle, and the depth-reduction bound O(nh^3) improves on generic balancing results while preserving structured decomposability. The approach of exposing latent variables as a tree-shaped Bayesian network is elegant and likely to stimulate follow-up work. The specialized label constructions for contiguous PCs (Claim 4.3, Algorithm 3) and for depth reduction (Algorithm 4) are concrete and checkable, and the paper includes worked examples. However, because the generic labelling algorithm has a correctness gap (Major Comment 1), the broad restructuring claim is not yet fully supported.

major comments (3)
  1. [Section 3.3 and Appendix B (Algorithms 2 and 5, Proposition 3.10)] Algorithm 5 (MinimumSeparator) can return observed variables as part of the separator, which violates the requirement in Definition 3.7 that every C_w be a subset of latent variables. Concretely, on the tree-shaped graph with root Z and children X1, X2, MinimumSeparator(Z, {X1}, {X2}) returns {X1}: the recursion descends into the observed leaf X1, and the base case 'B = ∅' returns {X1}. Because Dw in Algorithm 2 then contains the observed variable X1, the sets Cl and Cr are not valid conditioning sets for the recurrence in Algorithm 1, and Proposition 3.10's proof does not cover this case. The generic restructuring result stated in Section 3 is therefore not established as written. This is fixable, e.g., by restricting MinimumSeparator to latent nodes or by replacing any observed variable in its output by its latent parent, as already done for Algorithm 3 in the proof of Proposition 4.5; please make the correction and update the proof.
  2. [Section 4.1, Proposition 4.5 and Theorem 4.6] The proposition states |C_w| ≤ 4d, but the text immediately after it says 'the cardinality of C_w is bounded by 12d', and Theorem 4.6 states an O(|A|^{12d}|B|) bound. These numbers must be reconciled; if the correct bound is 4d, Theorem 4.6's exponent should be 4d, and if 12d is intended, Proposition 4.5 and the appendix proof should be corrected accordingly.
  3. [Section 4, Theorem 4.2] The PCFG representation theorem is only sketched ('in spirit similar to the CYK algorithm') with no construction of the sum/product/leaf nodes or proof of correctness. Since this theorem is stated as a formal result and used to motivate applications (e.g., multiplying HMMs with PCFGs), please supply the full construction and proof, or downgrade the statement to a conjecture with a clear proof sketch.
minor comments (4)
  1. [Section 5, proof of Theorem 5.1] The formula 'Cr = {Zv(w)} ∪ Sl' appears to contain a typo; by symmetry with Cl and from Algorithm 4, it should likely be 'Cr = {Zv(w)} ∪ Sr' (with appropriate conventions for empty sets).
  2. [Section 3.2, Algorithm 1] The notation L_Cl and L_Cr denotes vectors of sum nodes, but this is not defined in the pseudocode; a one-sentence explanation of the tensor interpretation (one sum node per assignment to C_w) would make the recurrence and Figure 2 much easier to follow.
  3. [Section 4, Figure 3] The arrow from 'Log-Depth & Contiguous' to 'Any Log-Depth Contiguous' is labeled 'Quasi-Polynomial'; please ensure this matches the conditions of Corollary 4.7 (depth O(log n) source) or clarify the statement.
  4. [Abstract and Section 6] The word 'decomposibility' is misspelled in the abstract; also 'less expressive efficient' in Section 6 (referring to de Colnet and Mengel) should be rephrased for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the restructuring derivation is self-contained; self-citations appear only in applications and related work and are not load-bearing.

full rationale

The paper's core derivation is not circular. Theorem 3.3 converts a structured PC into a tree-shaped Bayesian network using an explicit construction over the augmented PC and the standard induced-tree decomposition, citing external prior work (Zhao et al. 2016) for the induced-tree identity; the proof is supplied in the appendix and does not rely on the paper's own results. The recursive restructuring recurrence in Algorithm 1 is derived in the main text from the conditional-independence properties required by Definition 3.7, and the labelling algorithms (Algorithms 2, 3, 4) are custom constructions whose correctness is argued directly rather than imported from a self-citation. No parameters are fitted to data, and no prediction is statistically forced by fitted inputs. Existing self-citations (e.g., Zhang et al. 2024 for HMM-DFA multiplication, Liu and Van den Broeck 2021 for compiling tree-shaped BNs) appear only in motivation, applications, or related work, and none of these citations is the load-bearing justification for the restructuring theorems. The skeptical concern that MinimumSeparator may return observed variables and hence violate Definition 3.7 would be a soundness or correctness issue with Algorithm 5/Proposition 3.10, not a circularity: it does not make the conclusion equivalent to the assumptions. The paper even acknowledges a related minor issue for Algorithm 3 in the proof of Proposition 4.5 ('Cw may contain variables in X, but we can replace them by their parent in GA without affecting the validity'), showing the authors are aware of such edge cases; that is an internal correctness note rather than a self-referential argument. Overall, the claimed restructuring algorithm and complexity bounds are derived from the construction itself and from external, checkable graphical-model facts, so there is no circular step.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The central claims rest on standard results in circuit semantics (marginalization, induced trees) and graphical models (d-separation), plus domain assumptions about the PC class (smooth, structured-decomposable, alternating, binary). The latent variables Z_v are auxiliary proof devices with no independent empirical content. No free parameters are fitted to data.

assumptions (5)
  • standard math Correctness of standard PC marginalization (Darwiche, 2003; Choi et al., 2020).
    Used in the proof of Proposition 3.2 to argue that marginalizing the latents from the augmented PC recovers the original distribution.
  • standard math d-separation criterion (Geiger et al., 1990).
    Used in Proposition 3.6 to justify that a blocking set C_w induces conditional independence, and throughout Section 3 to reason about valid labellings.
  • standard math Induced-tree representation of smooth decomposable PCs (Zhao et al., 2016).
    The proof of Theorem 3.3 in Appendix A relies on the fact that a PC's function is the sum over its induced trees.
  • domain assumption PCs are assumed smooth, structured-decomposable, alternating sum/product, and with binary products.
    Section 2 states these assumptions 'for simplicity'; they are not universal for all PCs, and converting a general PC to this form can incur a polynomial blow-up that is not analyzed.
  • domain assumption Size of a structured PC is O(nh^2) where h is the hidden state size.
    Stated at the start of Section 3.1; used in all complexity bounds (e.g., Theorem 4.4, Corollary 5.3).
invented entities (1)
  • Latent variables Z_v (one per vtree node v)
    purpose: To represent a structured PC as a tree-shaped Bayesian network so that conditional independencies can be read off via d-separation and used to build a restructured PC.
    The Z_v are mathematical auxiliary variables introduced by the augmented PC construction (Definition 3.1); they are not observed in data and carry no evidence outside the paper. They are a standard latent-variable interpretation technique (cf. Zhao et al., 2015), so they do not add unsupported physical content.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Restructuring Tractable Probabilistic Circuits." pith.science (2026). https://pith.science/paper/ZMZWXAAE

@misc{pith2026241112256,
  author       = {Pith},
  title        = {Pith review of: Restructuring Tractable Probabilistic Circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZMZWXAAE}},
  note         = {Machine review of arXiv:2411.12256}
}
read the original abstract

Probabilistic circuits (PCs) are a unifying representation for probabilistic models that support tractable inference. Numerous applications of PCs like controllable text generation depend on the ability to efficiently multiply two circuits. Existing multiplication algorithms require that the circuits respect the same structure, i.e. variable scopes decomposes according to the same vtree. In this work, we propose and study the task of restructuring structured(-decomposable) PCs, that is, transforming a structured PC such that it conforms to a target vtree. We propose a generic approach for this problem and show that it leads to novel polynomial-time algorithms for multiplying circuits respecting different vtrees, as well as a practical depth-reduction algorithm that preserves structured decomposibility. Our work opens up new avenues for tractable PC inference, suggesting the possibility of training with less restrictive PC structures while enabling efficient inference by changing their structures at inference time.

Figures

Figures reproduced from arXiv: 2411.12256 by the authors.

Figure 1
Figure 1. Fig. 1a shows a vtree V for some contiguous PC A ; Fig. 1b shows a Bayesian network representa￾tion GA for A ; Fig. 1c shows a valid labelling of vtree W with respect to GA . p ∗ (X, Z), based on the augmented PC, that factor￾izes as required by the Bayesian network structure. There are three cases to consider: (i) the root node p ∗ (Zroot(V )), (ii) the leaf nodes p ∗ (Xv|Zp), and (iii) other nodes p ∗ (Zv|Zp) (whe… view at source ↗
Figure 2
Figure 2. Recursive construction of vectors of sum [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Summary of restructuring results; the top/bottom rows indicate the source/target struc￾tures. Blue and bold arrows indicate novel complex￾ity results. For the two other arrows that were known to be polynomial-time, our approach yields more ef￾ficient algorithms amenable to practical implementa￾tion. 4 PC MULTIPLICATION One important application of restructuring PCs is cir￾cuit multiplication: given two PCs A and B, … view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: GA for A with a linear vtree resented as a contiguous yet non-structured PC A of size O(mn3 ); i.e. pA (x) computes the probability of x being derived from G, for all x of length n. The algorithm for constructing the PC representa￾tion for a PCFG is in spirit similar t…
Figure 5
Figure 5. Figure 5: Example of restructuring labeling. to Definition 3.7 as {Z2} is a cover for both {X1, X2} and {X3, X4}, and the second and third conditions in the definition are satisfied as e.g. {Z2} blocks paths between {X1, X2} and {Z2} (trivially). We further show an explicit exam…
Figure 6
Figure 6. Figure 6: Example of original and restructured PC for the structures in Figure 5. [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scaling Probabilistic Circuits via Monarch Matrices

    cs.LG 2025-06 conditional novelty 6.0 of 10

    Structured Monarch matrices, derived from circuit multiplication, let probabilistic circuits scale to larger hidden sizes and beat prior tractable models at lower FLOP cost.

Reference graph

Works this paper leans on

66 extracted references · 60 canonical work pages · cited by 1 Pith paper

  1. [1]

    and Bl \"a ser, M

    Agarwal, S. and Bl \"a ser, M. (2024). Probabilistic generating circuits-demystified. In International Conference on Machine Learning , pages 329--342. PMLR

    work page 2024

  2. [2]

    Ahmed, K., Teso, S., Chang, K.-W., Van den Broeck, G., and Vergari, A. (2022). Semantic probabilistic layers for neuro-symbolic learning. Advances in Neural Information Processing Systems , 35:29944--29959

    work page 2022

  3. [3]

    Amarilli, A., Arenas, M., Choi, Y., Monet, M., Broeck, G. V. d., and Wang, B. (2024). A circus of circuits: Connections between decision diagrams, circuits, and automata. arXiv preprint arXiv:2404.09674

    arXiv 2024

  4. [4]

    Amarilli, A., Bourhis, P., Jachiet, L., and Mengel, S. (2017). A Circuit-Based Approach to Efficient Enumeration . In Chatzigiannakis, I., Indyk, P., Kuhn, F., and Muscholl, A., editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , volume 80 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 111:1-...

    work page 2017

  5. [5]

    Bova, S. (2016). Sdds are exponentially more succinct than obdds. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 30

    work page 2016

  6. [6]

    Broadrick, O., Zhang, H., and Van den Broeck, G. (2024). Polynomial semantics of tractable probabilistic circuits. In Proceedings of the 40th Conference on Uncertainty in Artificial Intelligence (UAI)

    work page 2024

  7. [7]

    P., Willig, M., Seng, J., Kersting, K., and Dhami, D

    Busch, F. P., Willig, M., Seng, J., Kersting, K., and Dhami, D. S. (2024). net: Efficient causal modeling at scale. In International Conference on Probabilistic Graphical Models , pages 452--469. PMLR

    work page 2024

  8. [8]

    S., and Peharz, R

    Butz, C., Oliveira, J. S., and Peharz, R. (2020). Sum-product network decompilation. In International Conference on Probabilistic Graphical Models , pages 53--64. PMLR

    work page 2020

Show all 66 references
  1. [9]

    and Darwiche, A

    Chavira, M. and Darwiche, A. (2008). On probabilistic inference by weighted model counting. Artificial Intelligence , 172(6-7):772--799

    2008

  2. [10]

    Choi, A., Van den Broeck, G., and Darwiche, A. (2015). Tractable learning for structured probability spaces: A case study in learning preference distributions. In Proceedings of 24th International Joint Conference on Artificial Intelligence (IJCAI)

    2015

  3. [11]

    Choi, Y., Dang, M., and Van den Broeck, G. (2021). Group fairness by probabilistic modeling with latent fair decisions. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 35, pages 12051--12059

    2021

  4. [12]

    Choi, Y., Vergari, A., and Van den Broeck, G. (2020). Probabilistic circuits: A unifying framework for tractable probabilistic models

    2020

  5. [13]

    Cocke, J. (1969). Programming languages and their compilers: Preliminary notes . New York University

    1969

  6. [14]

    D., and de Campos, C

    Conaty, D., Maua, D. D., and de Campos, C. P. (2017). Approximation complexity of maximum a posteriori inference in sum-product networks. In The 33rd Conference on Uncertainty in Artificial Intelligence (UAI) . AUAI

    2017

  7. [15]

    H., Leiserson, C

    Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to algorithms . MIT press

    2022

  8. [16]

    Dang, M., Khosravi, P., Liang, Y., Vergari, A., and Van den Broeck, G. (2021). Juice: A julia package for logic and probabilistic circuits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (Demo Track)

    2021

  9. [17]

    Dang, M., Liu, A., and Van den Broeck, G. (2022a). Sparse probabilistic circuits via pruning and growing. In Advances in Neural Information Processing Systems 35 (NeurIPS)

    2022

  10. [18]

    Dang, M., Liu, A., Wei, X., Sankararaman, S., and Van den Broeck, G. (2022b). Tractable and expressive generative models of genetic variation data. In Proceedings of the International Conference on Research in Computational Molecular Biology (RECOMB)

    2022

  11. [19]

    Dang, M., Vergari, A., and Broeck, G. (2020). Strudel: Learning structured-decomposable probabilistic circuits. In International Conference on Probabilistic Graphical Models , pages 137--148. PMLR

    2020

  12. [20]

    Darwiche, A. (2003). A differential approach to inference in bayesian networks. Journal of the ACM (JACM) , 50(3):280--305

    2003

  13. [21]

    Darwiche, A. (2011). Sdd: A new canonical representation of propositional knowledge bases. In Twenty-Second International Joint Conference on Artificial Intelligence

    2011

  14. [22]

    and Marquis, P

    Darwiche, A. and Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research , 17:229--264

    2002

  15. [23]

    and Mengel, S

    de Colnet, A. and Mengel, S. (2021). A compilation of succinctness results for arithmetic circuits. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning , volume 18, pages 205--215

    2021

  16. [24]

    L., Zhang, H., Ahmed, K., Wang, B., and Van den Broeck, G

    Geh, R. L., Zhang, H., Ahmed, K., Wang, B., and Van den Broeck, G. (2024). Where is the signal in tokenization space? In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing (EMNLP)

    2024

  17. [25]

    Geiger, D., Verma, T., and Pearl, J. (1990). d-separation: From theorems to algorithms. In Machine intelligence and pattern recognition , volume 10, pages 139--148. Elsevier

    1990

  18. [26]

    P., and Koivisto, M

    Harviainen, J., Ramaswamy, V. P., and Koivisto, M. (2023). On inference and learning with probabilistic generating circuits. In Uncertainty in Artificial Intelligence , pages 829--838. PMLR

    2023

  19. [27]

    Kasami, T. (1966). An efficient recognition and syntax-analysis algorithm for context-free languages. Coordinated Science Laboratory Report no. R-257

    1966

  20. [28]

    Khosravi, P., Choi, Y., Liang, Y., Vergari, A., and Van den Broeck, G. (2019). On tractable computation of expected predictions. In Advances in Neural Information Processing Systems 32 (NeurIPS)

    2019

  21. [29]

    Kisa, D., Van den Broeck, G., Choi, A., and Darwiche, A. (2014). Probabilistic sentential decision diagrams. In Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning

    2014

  22. [30]

    Liang, Y., Bekker, J., and Van den Broeck, G. (2017). Learning the structure of probabilistic sentential decision diagrams. In Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI)

    2017

  23. [31]

    Liu, A., Ahmed, K., and Van den Broeck, G. (2024a). Scaling tractable probabilistic circuits: A systems perspective. In Proceedings of the 41th International Conference on Machine Learning (ICML)

    2024

  24. [32]

    Liu, A., Niepert, M., and Van den Broeck, G. (2024b). Image inpainting via tractable steering of diffusion models. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR)

    2024

  25. [33]

    and Van den Broeck, G

    Liu, A. and Van den Broeck, G. (2021). Tractable regularization of probabilistic circuits. In Advances in Neural Information Processing Systems 34 (NeurIPS)

    2021

  26. [34]

    Loconte, L., Di Mauro, N., Peharz, R., and Vergari, A. (2023). How to turn your knowledge graph embeddings into generative models. Advances in Neural Information Processing Systems , 36

    2023

  27. [35]

    Loconte, L., Mari, A., Gala, G., Peharz, R., de Campos, C., Quaeghebeur, E., Vessio, G., and Vergari, A. (2024a). What is the relationship between tensor factorizations and circuits (and how can we exploit it)? arXiv preprint arXiv:2409.07953

    2024 arXiv

  28. [36]

    Loconte, L., Mengel, S., and Vergari, A. (2024b). Sum of squares circuits. arXiv preprint arXiv:2408.11778

    2024 arXiv

  29. [37]

    Loconte, L., Sladek, A., Mengel, S., Trapp, M., Solin, A., Gillis, N., and Vergari, A. (2024c). Subtractive mixture models via squaring: Representation and learning. In International Conference on Learning Representations (ICLR)

    2024

  30. [38]

    and de La Higuera, C

    Marzouk, R. and de La Higuera, C. (2022). Marginal inference queries in hidden markov models under context-free grammar constraints. arXiv preprint arXiv:2206.12862

    2022 arXiv

  31. [39]

    and Belle, V

    Papantonis, I. and Belle, V. (2023). Transparency in sum-product network decompilation. In European Conference on Artificial Intelligence , pages 1827--1834. IOS Press

    2023

  32. [40]

    Peharz, R., Gens, R., Pernkopf, F., and Domingos, P. (2016). On the latent variable interpretation in sum-product networks. IEEE transactions on pattern analysis and machine intelligence , 39(10):2030--2044

    2016

  33. [41]

    Peharz, R., Lang, S., Vergari, A., Stelzner, K., Molina, A., Trapp, M., Van den Broeck, G., Kersting, K., and Ghahramani, Z. (2020). Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In Proceedings of the 37th International Conference on Machine ...

    2020

  34. [42]

    and Darwiche, A

    Pipatsrisawat, K. and Darwiche, A. (2008). New compilation languages based on structured decomposability. In AAAI , volume 8, pages 517--522

    2008

  35. [43]

    and Domingos, P

    Poon, H. and Domingos, P. (2011). Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops) , pages 689--690. IEEE

    2011

  36. [44]

    Rabiner, L. R. (1989). A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE , 77(2):257--286

    1989

  37. [45]

    Rahman, T., Kothalkar, P., and Gogate, V. (2014). Cutset networks: A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 1...

    2014

  38. [46]

    and Yehudayoff, A

    Raz, R. and Yehudayoff, A. (2008). Balancing syntactically multilinear arithmetic circuits. Computational Complexity , 17:515--535

    2008

  39. [47]

    and Yehudayoff, A

    Raz, R. and Yehudayoff, A. (2009). Lower bounds and separations for constant depth multilinear circuits. Computational Complexity , 18:171--207

    2009

  40. [48]

    and Lowd, D

    Rooshenas, A. and Lowd, D. (2014). Learning sum-product networks with direct and indirect variable interactions. In International Conference on Machine Learning , pages 710--718. PMLR

    2014

  41. [49]

    Roth, D. (1996). On the hardness of approximate reasoning. Artificial Intelligence , 82(1-2):273--302

    1996

  42. [50]

    Shen, Y., Choi, A., and Darwiche, A. (2016). Tractable operations for arithmetic circuits of probabilistic models. Advances in Neural Information Processing Systems , 29

    2016

  43. [51]

    and Ermon, S

    Shih, A. and Ermon, S. (2020). Probabilistic circuits for variational inference in discrete graphical models. Advances in neural information processing systems , 33:4635--4646

    2020

  44. [52]

    and Natarajan, S

    Sidheekh, S. and Natarajan, S. (2024). Building expressive and tractable probabilistic generative models: A review. arXiv preprint arXiv:2402.00759

    2024 arXiv

  45. [53]

    Tian, J., Paz, A., and Pearl, J. (1998). Finding minimal d-separators . Citeseer

    1998

  46. [54]

    Valiant, L., Skyum, S., Berkowitz, S., and Rackoff, C. (1983). Fast parallel computation of polynomials using few processors. SIAM Journal on Computing , 12(4):641--644

    1983

  47. [55]

    Vergari, A., Choi, Y., Liu, A., Teso, S., and Van den Broeck, G. (2021). A compositional atlas of tractable circuit operations for probabilistic inference. In Advances in Neural Information Processing Systems 34 (NeurIPS)

    2021

  48. [56]

    and Kwiatkowska, M

    Wang, B. and Kwiatkowska, M. (2023). Compositional probabilistic and causal inference using tractable circuit models. In International Conference on Artificial Intelligence and Statistics , pages 9488--9498. PMLR

    2023

  49. [57]

    and Van den Broeck, G

    Wang, B. and Van den Broeck, G. (2024). On the relationship between monotone and squared probabilistic circuits. In Proceedings of the UAI Workshop on Tractable Probabilistic Modeling (TPM)

    2024

  50. [58]

    Yang, Y., Gala, G., and Peharz, R. (2023). Bayesian structure scores for probabilistic circuits. In International Conference on Artificial Intelligence and Statistics , pages 563--575. PMLR

    2023

  51. [59]

    and Zhao, H

    Yin, L. and Zhao, H. (2024). On the expressive power of tree-structured probabilistic circuits. In Advances in Neural Information Processing Systems 37 (NeurIPS)

    2024

  52. [60]

    Younger, D. H. (1967). Recognition and parsing of context-free languages in time n3. Information and control , 10(2):189--208

    1967

  53. [61]

    Ze c evi \'c , M., Dhami, D., Karanam, A., Natarajan, S., and Kersting, K. (2021). Interventional sum-product networks: Causal inference with tractable probabilistic models. Advances in neural information processing systems , 34:15019--15031

    2021

  54. [62]

    Zhang, H., Dang, M., Peng, N., and Van den Broeck, G. (2023). Tractable control for autoregressive language generation. In Proceedings of the 40th International Conference on Machine Learning (ICML)

    2023

  55. [63]

    Zhang, H., Juba, B., and Van den Broeck, G. (2021). Probabilistic generating circuits. In Proceedings of the 38th International Conference on Machine Learning (ICML)

    2021

  56. [64]

    Zhang, H., Kung, P.-N., Yoshida, M., Broeck, G. V. d., and Peng, N. (2024). Adaptable logical control for large language models. arXiv preprint arXiv:2406.13892

    2024 arXiv

  57. [65]

    Zhao, H., Melibari, M., and Poupart, P. (2015). On the relationship between sum-product networks and bayesian networks. In International Conference on Machine Learning , pages 116--124. PMLR

    2015

  58. [66]

    Zhao, H., Poupart, P., and Gordon, G. J. (2016). A unified approach for learning the parameters of sum-product networks. Advances in neural information processing systems , 29

    2016

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.