{"id":"eb48aa5c-9db8-429f-9385-58c6da1679a8","arxiv_id":"2411.12256","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A restructuring algorithm converts structured probabilistic circuits between different variable-order trees in polynomial time for contiguous circuits, enabling tractable multiplication of differently structured circuits and log-depth reduction with modest size growth.","lead":"Probabilistic circuits are tractable AI models whose internal variable structure normally locks in which operations are fast. This paper provides algorithms to restructure such circuits to a different variable order in polynomial time for a broad class, enabling new multiplication and depth-reduction tricks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 5's MinimumSeparator can return observed variables as separators (e.g., on root Z with children X1, X2 it returns {X1} for A={X1}, B={X2}), so Algorithm 2's labels can violate Definition 3.7's latent-only requirement; Proposition 3.10 is unsound as stated.","rationale":"Read in good faith, the paper's core idea—compile a structured PC into a tree-shaped BN, separate target scopes with latent covers, then recurse—is coherent, and the specialized contiguous and depth-reduction applications appear to avoid the problematic subroutine. I isolated the minimum-separator bug because it is concrete, checkable, and sits exactly on the reader's weakest assumption: the validity of Algorithm 2's labelling. The reader's conditional verdict is appropriate; my finding does not move the verdict, but it sharpens the condition: Algorithm 5 must be corrected or supplemented with a latent-parent post-processing step before the general restructuring claim can be accepted. I did not find a flaw in Theorem 3.3's BN conversion or in the specialized label constructions (Claim 4.3, Proposition 4.5, Theorem 5.1), and I credit the paper for providing a detailed proof of the BN equivalence and for giving explicit label constructions in the applications.","tokens_in":21247,"tokens_out":31270,"duration_ms":347524,"concrete_test":"Run Algorithm 5 exactly as given in Appendix B on the GA for n=2: root latent Z, children X1 and X2, A={X1}, B={X2}. The returned separator is {X1}; a correct latent-only minimum separator is {Z}. Then run Algorithm 2 on the same GA with any target vtree whose root has two children and verify every C_w is a subset of the latent variables. If any C_w contains X1 (or any observed variable), Proposition 3.10 as stated is false. A third check: replace observed variables in labels by their latent parent and re-run the restructuring; if the resulting circuit still represents the original distribution, the flaw is repairable as a presentation bug rather than a fundamental obstruction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The general restructuring algorithm depends on Definition 3.7's valid labelling, and Algorithm 2 is the published method for computing it. That method calls MinimumSeparator (Algorithm 5, Appendix B). As written, Algorithm 5 recurses into every child of the current node, including observed-variable leaves, and its base cases return the current root. This lets observed variables enter the separator. For the tree-shaped BN of a 2-variable linear vtree, root Z with children X1 and X2, call MinimumSeparator(Z, {X1}, {X2}): the child call on X1 has B=∅ and returns {X1}; the child call on X2 returns {X2}; the parent then computes CA=CB={X1}, so the returned separator is {X1}, an observed variable. Definition 3.7 requires every C_w to be a subset of latent variables, and Algorithm 1's base case assumes a leaf label is the parent latent in GA. If D_w contains X1, the C_l and C_r computed in Algorithm 2 are not valid conditioning sets; no marginalization over the observed variable is specified, so the recursive construction no longer represents p(X_w | C_w). Proposition 3.10's proof therefore does not cover the algorithm as written. This does not necessarily sink the specialized results: Claim 4.3 and Algorithm 4 define labels directly and do not invoke MinimumSeparator. But the paper's broad claim that Algorithm 1 plus Algorithm 2 restructures an arbitrary smooth structured-decomposable PC to any target vtree is not established until this routine is corrected or shown to have an implicit replacement of observed nodes by their latent parent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":21614,"tokens_out":12208,"duration_ms":114533,"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":[{"comment":"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.","section":"Section 3.3 and Appendix B (Algorithms 2 and 5, Proposition 3.10)"},{"comment":"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.","section":"Section 4.1, Proposition 4.5 and Theorem 4.6"},{"comment":"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.","section":"Section 4, Theorem 4.2"}],"minor_comments":[{"comment":"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).","section":"Section 5, proof of Theorem 5.1"},{"comment":"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.","section":"Section 3.2, Algorithm 1"},{"comment":"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.","section":"Section 4, Figure 3"},{"comment":"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.","section":"Abstract and Section 6"}],"recommendation":"major_revision","confidential_remarks":"The main generic algorithm needs a fix, but the specialized results for contiguous PCs and depth reduction appear to rely on direct label constructions (Algorithm 3 and Algorithm 4) rather than the flawed MinimumSeparator, so the paper's principal applications may survive. Please ask the authors to (i) fix or clearly restrict MinimumSeparator so it cannot return observed variables, (ii) reconcile the 4d/12d bounds, and (iii) provide the missing PCFG construction. If the authors can patch these, the paper would be a strong contribution to the tractable-probabilistic-circuits literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper opens a genuinely new problem—restructuring a structured-decomposable PC to respect a different vtree—and the main conceptual move, reading a PC as a tree-shaped Bayesian network with one latent per vtree node, is elegant. The reader's conditional verdict is about right, and I want to push one concern harder: the general algorithm is not yet correct as written.\n\nAlgorithm 5's MinimumSeparator can return observed variables. On a root latent with two observed children X1 and X2, separating {X1} from {X2} returns {X1}; this violates Definition 3.7's requirement that labels be latent-only and breaks the recurrence in Algorithm 1, whose base case assumes the leaf label is the parent latent. Proposition 3.10 does not cover Algorithm 2 as written. The stress-test note lands. This is a real gap, but it looks fixable: replace observed variables in a separator by their latent parent, which the authors already do in the proof of Proposition 4.5.\n\nWhat is actually new and good: Theorem 3.3's decompilation of structured PCs into tree-shaped BNs is clean and the induced-tree proof is plausible. The contiguous class is a useful definition. The specialized labels for linear vtrees (Claim 4.3), segment covers (Algorithm 3), and balanced depth reduction (Algorithm 4) do not go through the buggy routine. The depth-reduction corollary—any structured PC with hidden state h becomes depth O(log n) and size O(nh^3)—is a real improvement over prior balancing bounds and retains structuredness. Complexity bounds are derived, not fitted; the citation pattern is fine, with self-citations mostly in application paragraphs rather than in load-bearing proofs.\n\nSoft spots, in proportion: Theorem 4.2 (PCFG representation) is only sketched, with no formal construction; the paper says 4d in one place and 12d in another before using 12d; and \"practical\" in the depth-reduction section is unsupported without experiments. These are minor-to-moderate presentation issues, not fatal flaws. The main issue remains the separator routine.\n\nThis paper is for PC theorists and for systems people who care about multiplication and depth. It deserves a serious referee. My recommendation: send it to review; require the authors to repair or restrict Algorithm 2/5, prove or soften Theorem 4.2, and fix the 4d/12d inconsistency. If the general algorithm is patched, this is a solid contribution.","headline":"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.","tokens_in":22136,"tokens_out":5796,"would_cite":true,"duration_ms":61618,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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).","keywords":["probabilistic circuits","structured decomposability","vtree","circuit restructuring","circuit multiplication","depth reduction","contiguity","Bayesian network representation"],"falsifier":"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.","tokens_in":21060,"feed_emoji":"🔀","tokens_out":14559,"duration_ms":125448,"temperature":0.7,"pith_summary":"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.","feed_headline":"Restructuring unlocks exact multiplication of mismatched circuits","feed_subtitle":"A variable-tree rewrite preserves the distribution, enabling fast multiplication and log-depth inference.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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)."],"supporting_citations":[{"why":"Supplies the existing algorithm for multiplying two circuits that respect the same vtree, which the restructured output is fed into.","marker":"Shen et al. (2016)"},{"why":"Establishes that multiplying circuits with different structures is #P-hard in general and frames the multiplication operation the paper extends to mismatched vtrees.","marker":"Vergari et al. (2021)"},{"why":"Gives the d-separation characterization of conditional independence on which the cover and valid-labelling definitions rest.","marker":"Geiger et al. (1990)"},{"why":"Provides the smoothness-decomposability semantics and differential inference framework used to convert a PC to a Bayesian network and back.","marker":"Darwiche (2003)"},{"why":"Supplies the induced-tree expansion used in the appendix proof that the Bayesian-network distribution matches the augmented circuit.","marker":"Zhao et al. (2016)"},{"why":"The prior depth-reduction result for syntactically multilinear circuits whose cubic size bound the paper improves to $O(nh^3)$ for structured circuits.","marker":"Raz and Yehudayoff (2008)"},{"why":"The classical depth-reduction theorem for arithmetic circuits that the paper's structured depth-reduction refines.","marker":"Valiant et al. (1983)"},{"why":"Provides the polynomial-time minimal d-separator computation that Algorithm 2's greedy labelling calls, specialized here to tree-shaped networks.","marker":"Tian et al. (1998)"},{"why":"Defines the probabilistic-circuit framework, smoothness, and decomposability that the paper's notation and constructions presuppose.","marker":"Choi et al. (2020)"}],"fun_headline_variants":["Restructure circuits to match vtrees, then multiply exactly","Tractable restructuring unlocks exact circuit multiplication","Rewrite circuit structure to enable fast exact products","Restructuring makes mismatched circuits multiplyable exactly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Restructure circuits to match vtrees, then multiply exactly","Tractable restructuring unlocks exact circuit multiplication","Rewrite circuit structure to enable fast exact products","Restructuring makes mismatched circuits multiplyable exactly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000483,"raw_usage":{"total_tokens":2387,"prompt_tokens":951,"completion_tokens":1436,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":1390}},"tokens_in":567,"tokens_out":1436,"duration_ms":10488,"temperature":1.0,"reasoning_tokens":1390,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:47:27.968358+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the existing algorithm for multiplying two circuits that respect the same vtree, which the restructured output is fed into."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that multiplying circuits with different structures is #P-hard in general and frames the multiplication operation the paper extends to mismatched vtrees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the d-separation characterization of conditional independence on which the cover and valid-labelling definitions rest."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the smoothness-decomposability semantics and differential inference framework used to convert a PC to a Bayesian network and back."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the induced-tree expansion used in the appendix proof that the Bayesian-network distribution matches the augmented circuit."},{"cited_title":"and Yehudayoff, A","cited_arxiv_id":null,"evidence_quote":"The prior depth-reduction result for syntactically multilinear circuits whose cubic size bound the paper improves to $O(nh^3)$ for structured circuits."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The classical depth-reduction theorem for arithmetic circuits that the paper's structured depth-reduction refines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time minimal d-separator computation that Algorithm 2's greedy labelling calls, specialized here to tree-shaped networks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the probabilistic-circuit framework, smoothness, and decomposability that the paper's notation and constructions presuppose."}],"review_version":1}