{"id":"14d3c799-c12e-4843-978c-b50860d252da","arxiv_id":"2412.07883","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Squared circuits whose input layers are orthonormal and whose sum layers are semi-unitary are automatically normalized and admit a faster marginalization algorithm.","lead":"This paper shows how to build squared probabilistic circuits so that they are already normalized and can answer marginal queries faster. The trick is a parameterization with orthonormal input functions and semi-unitary sum matrices, borrowed from tensor network canonical forms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's polynomial-time orthonormalization is unsupported: nested Hadamard layers make Algorithm 1's output width grow exponentially, so the 'no expressiveness loss' claim needs a substantial restriction or a new proof.","rationale":"The reader's weakest assumption was exactly the missing size bound in Theorem 2. I agree with that identification, and the manuscript text itself flags the issue: Appendix B.3 says Case (iii) is 'the only case accounting for a polynomial increase in the size of the layer,' but no proof is supplied and the increase is not analyzed under iteration. My concrete check shows the increase is exponential for a natural structured-decomposable circuit family, even when the circuit is not already orthonormal. Thus the paper's headline claim of no expressiveness loss is unsupported as written. I would keep the CONDITIONAL verdict: Proposition 1 and Theorem 1 appear sound and give a genuine speed-up for circuits that are already orthonormal or belong to classes where the orthonormalization blow-up can be controlled. However, the paper should not be accepted in current form without either (i) a correct proof of a polynomial size invariant for Algorithm 1, or (ii) a scoped version of Theorem 2 excluding or restricting Hadamard product layers, with an explicit statement of which circuit classes are covered. The revision needed is substantial but localized, so REJECT would be too strong given that the core marginalization result stands.","tokens_in":16832,"tokens_out":19055,"duration_ms":195882,"concrete_test":"Implement Algorithm 1 exactly as written on the following family for d=1,...,8: take 2^d binary variables, each with an input layer of K=2 orthonormal delta functions; precede each variable by a non-unitary 2x2 sum layer; combine the resulting 2-dimensional vectors in a balanced tree of Hadamard product layers over disjoint scopes; finish with a 1x2 root sum layer. Track the output width of the orthonormalized root child returned by ORTHONORMALIZE. If the width follows 2^{2^d} while the input circuit has Theta(2^d) layers of constant size, Algorithm 1's output size and runtime are exponential, contradicting the polynomial-time claim in Theorem 2. An analytical version is to derive the recurrence width_{t+1}=width_t^2 for nested Hadamard layers and observe that its closed form is width_t=2^{2^t}.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The practical bridge from 'orthonormal circuits are convenient' to 'we can always orthonormalize without losing expressiveness' is Theorem 2, proven only by Algorithm 1. The proof in Appendix B.3, Case (iii), replaces every Hadamard product layer by a Kronecker product layer and pushes residual matrices upward. The text asserts this is only a polynomial increase in layer size, but no invariant bounds the output width of the orthonormalized subcircuit. The increase compounds: in a balanced Hadamard-product tree of depth d, with K-dimensional orthonormal input functions, orthonormalizing a layer whose children have orthonormalized width w produces a Kronecker layer of width w^2. Starting from w=K, the width at the root is K^{2^d}, whereas the original circuit has only O(2^d) layers of size O(K^2). This is not an artifact of already-orthonormal circuits: inserting non-unitary sum layers under each leaf makes the input circuit non-orthonormal, and Algorithm 1 still performs the same Hadamard-to-Kronecker replacement. The stated complexity O(Lsum J^3 + Lprod J^4), with J the original maximum layer size, is therefore not a valid bound for the circuit actually built by Algorithm 1. Consequently Theorem 2, as stated and as proved, does not establish polynomial-time orthonormalization, and the faster marginalization algorithm of Theorem 1 cannot be applied to arbitrary squared circuits via Theorem 2. Proposition 1 and Theorem 1 themselves are not implicated by this concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes orthonormal tensorized circuits, defined by orthonormal input functions and (semi-)unitary sum-layer matrices, as a parameterization of squared probabilistic circuits. Proposition 1 argues that squaring a structured-decomposable orthonormal circuit yields a normalized distribution, and Theorem 1 gives a marginalization algorithm whose complexity O(|phi_Y|S + |phi_Y,Z|S^2) improves on the prior O(LS^2) for squared circuits. Section 5 then claims, via Theorem 2 and Algorithm 1, that any circuit with orthonormal input layers can be converted to an orthonormal circuit in polynomial time up to a global constant, so the parameterization has no expressiveness loss. The normalization and marginalization results are argued in detail; the orthonormalization theorem is the main weak point.","tokens_in":17066,"tokens_out":18795,"duration_ms":175777,"significance":"If the main results stand, the paper makes a useful conceptual transfer from tensor-network canonical forms to squared circuits: Proposition 1 and Theorem 1 are carefully argued, the identity-matrix propagation argument in Appendix B.1 is convincing, and Algorithm B.1 is a non-trivial contribution that can speed up marginals when many layers depend only on the marginalized variables. The paper also provides concrete algorithms rather than only existence statements. However, Theorem 2 is the only bridge from 'orthonormal circuits are convenient' to 'we can always orthonormalize without losing expressiveness', and that bridge is currently not established; the practical significance of the paper is therefore conditional.","major_comments":[{"comment":"The proof of Theorem 2 does not bound the size of the orthonormalized circuit. In Case (iii), an Hadamard product layer is replaced by a Kronecker product layer: if the two recursively orthonormalized children have output widths w1 and w2, the new Kronecker layer has width w1*w2, and the returned residual R1•R2 has K1 rows and K2*K3 columns. No invariant in the proof prevents widths from compounding across nested Hadamard layers. For example, a balanced Hadamard-product tree of depth d over K-dimensional orthonormal leaves has O(2^d) layers each of size O(K), but Algorithm 1 produces a Kronecker layer of width K^{2^d}, and the final QR decomposition at the output sum then acts on a vector of that length. The stated complexity O(Lsum*J^3 + Lprod*J^4), with J the original maximum layer size, is therefore not a valid bound for the circuit actually built by Algorithm 1. The 'polynomial time' and 'no expressiveness loss' claims in Section 5 need either a new proof with an explicit output-size invariant or a substantial restriction on the circuit class.","section":"Appendix B.3, Theorem 2 / Algorithm 1"},{"comment":"The scalar-case algebra at the end of the proof is inconsistent with the QR convention used earlier. From V† = QR with Q†Q = 1, the 1x1 factor R has modulus ||V†||, so the residual R† returned by Algorithm 1 is ||V||, not ||V||^{-1}. The proof first writes 'r11 such that ||r11 V†||2 = 1', then states beta = r11 = Z^{-1/2}, and concludes Z = sum_i |v_i1|^2; only one of these relations can be correct. The intended relation is that the orthonormalized output satisfies c' = Z^{-1/2} c, so the returned scalar residual is sqrt(Z) rather than Z^{-1/2}. This needs to be corrected, since it directly affects the statement of Theorem 2.","section":"Appendix B.3, Case (iv)"},{"comment":"Definition 1 allows product layers with N inputs, and the size formulas explicitly depend on N, but Algorithm A.1, Algorithm 1, and the proofs in Appendices A and B treat every product layer as having exactly two inputs. The paper should either restrict all definitions and theorems to binary product layers, or provide a reduction from N-ary layers that does not change the claimed complexity. This is not merely cosmetic: for N > 2, the orthonormalization width blow-up in Case (iii) interacts with the number of product layers, and the binary decomposition changes the layer count and sizes used in the complexity statements.","section":"Definition 1 / Algorithm A.1 / Algorithm 1"}],"minor_comments":[{"comment":"The proof writes 'ℓ2_1(y′) = ℓ1(y′) ⊙ ℓ1(y′)∗'; the operation should be the Kronecker product, since squaring a layer produces ℓ ⊗ ℓ∗. The surrounding formula uses the correct ⊗ operation, so this appears to be a typo.","section":"Appendix B.2, Hadamard product case"},{"comment":"The line defining the variable partitions repeats 'Y′2 = X′2 ∩ Y' twice; the second occurrence should be 'Z′2 = X′2 ∩ Z'. This makes the subsequent case analysis harder to follow.","section":"Appendix B.2, Case (ii)"},{"comment":"The theorem statement says 'Let c be a tensorized circuit', while Algorithm 1 and the proof assume c is structured-decomposable. The statement should include the structured-decomposability assumption explicitly, as is done for Proposition 1 and Theorem 1.","section":"Theorem 2 statement"}],"recommendation":"major_revision","confidential_remarks":"The central speedup claim in Theorem 1 appears sound for circuits that already satisfy the orthonormal parameterization. The reason for major revision is Theorem 2: as stated and proved, it does not establish polynomial-time orthonormalization, and the Hadamard-only tree example in my report shows the output width can become exponential in the depth of product-only subtrees. I would encourage the authors to restrict Theorem 2 to a class with a provable width invariant, or to present it as a conditional result with an explicit size bound. If such a restriction still covers practically relevant circuit classes, the paper could be acceptable after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: Proposition 1 and Theorem 1 are sound and genuinely useful, but Theorem 2, the piece that makes the whole thing apply to arbitrary squared circuits, is not proven and as stated is likely false. The stress-test note is right: Algorithm 1 replaces Hadamard layers with Kronecker layers and pushes residual matrices upward, and there is no invariant bounding the width of the orthonormalized subcircuit. On a balanced Hadamard-product tree of depth d, starting from width K, the output width becomes K^(2^d) while the original circuit has only O(2^d) layers. That is exponential, not polynomial. The paper's complexity statement O(Lsum J^3 + Lprod J^4) uses the original layer size J, so it does not apply to the circuit actually built. This is load-bearing because the abstract promises \"no expressiveness loss\" for many circuit classes; that claim rests entirely on Theorem 2.\n\nWhat the paper does well: the orthonormal parameterization idea is clean, the automatic normalization result (Prop 1) is proved carefully via identity propagation, and Algorithm B.1 for marginalization on already-orthonormal circuits is a real improvement over O(LS^2) for structured cases where |phi_{Y,Z}| is small. The connection to tensor network canonical forms is apt and not just decorative. The paper is also honest about being theoretical: no experiments, and the limitations of the marginalization speed-up in practice are acknowledged implicitly.\n\nOther soft spots: the algorithm and proof treat product layers as binary, while Definition 1 allows N-ary; that needs clarification. And the practical value of Theorem 1 depends on obtaining orthonormal circuits, which is exactly what Theorem 2 was supposed to provide. So the two main advertised contributions are coupled; the paper overstates its reach.\n\nBottom line: this deserves a serious referee. If Theorem 2 is either repaired with a real size invariant or scoped to circuit classes where the Hadamard-to-Kronecker blow-up is controlled, the paper becomes a solid contribution to the squared circuit literature. As is, I would not cite the expressiveness claim, and I'd be cautious relying on the polynomial-time orthonormalization. Worth a reading group discussion on how a plausible-sounding algorithmic proof can miss a size bound.","headline":"Theorem 1 and Proposition 1 are sound and useful, but Theorem 2's polynomial-time orthonormalization is unproven and likely false as stated due to exponential Hadamard-to-Kronecker width blow-up.","tokens_in":17655,"tokens_out":3605,"would_cite":false,"duration_ms":31859,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Orthonormal squared circuits are automatically normalized and their marginalization cost drops from quadratic in layer size to a mixed linear-plus-quadratic bound that can be much smaller.","keywords":["squared circuits","probabilistic circuits","orthonormal circuits","semi-unitary matrices","tensor networks","tractable marginalization","normalized distributions","structured decomposability"],"falsifier":"Run the orthonormalization algorithm on a family of deep circuits built only from Hadamard product layers with orthonormal inputs, and track the width of the residual matrix returned at each recursive level; the polynomial-time claim fails if that width grows exponentially in depth while the input width stays polynomial.","tokens_in":16560,"feed_emoji":"🧮","tokens_out":7404,"duration_ms":65889,"temperature":0.7,"pith_summary":"Squaring a probabilistic circuit—multiplying it by its complex conjugate—is a flexible way to build expressive distributions, but it makes marginalization quadratic in layer size. This paper claims that if a structured-decomposable tensorized circuit is orthonormal, meaning its input layers encode orthonormal functions and its sum layers use (semi-)unitary matrices, then the squared distribution is already normalized. The authors then give an algorithm that computes any marginal by squaring only the layers whose scopes mix kept variables with marginalized ones, yielding time $O(|\\phi_Y| S + |\\phi_{Y,Z}| S^2)$ instead of the previous $O(L S^2)$. They also prove that this orthonormal parameterization can be enforced in polynomial time on any tensorized circuit whose inputs are orthonormal, up to a normalizing constant, so it costs no expressiveness for many circuit classes.","feed_headline":"Orthonormalized squared circuits compute marginals faster","feed_subtitle":"A tensor-network-inspired parameterization makes squared probabilistic circuits automatically normalized and cheaper to marginalize.","key_machinery":"The load-bearing object is the orthonormal tensorized circuit: a computational graph whose input layers output orthonormal function vectors and whose sum layers are parameterized by matrices with orthonormal rows. Because squaring turns each layer into $W \\otimes W^*$ products, integrating a squared input layer over its whole domain yields the vectorized identity $\\mathrm{vec}(I_K)$, and (semi-)unitarity carries identities through sum layers. Two algorithms do the work: the marginalization algorithm skips layers that depend only on marginalized variables, evaluates layers that depend only on kept variables without squaring them, and squares only the mixed layers; the orthonormalization algorithm QR-factorizes the effective weight matrix at each sum layer, pushes the residual upper-triangular factor upward, and replaces Hadamard products by Kronecker products. Structured decomposability—disjoint scopes at product layers and a tree-structured factorization—is what lets the integrals factor and identity propagation hold.","core_discovery":"The central claim is that orthonormal circuits—structured-decomposable tensorized circuits whose input layers form orthonormal function vectors and whose sum layers use (semi-)unitary matrices—encode, after squaring, a distribution with partition function equal to 1. The proof works by propagating identity matrices upward through the squared circuit: integrating the squared input layers gives $\\mathrm{vec}(I_K)$, and unitary sum weights and decomposable products preserve that identity structure, so the whole integral collapses to 1. For marginals, the paper's algorithm shows that layers whose scope lies entirely inside the marginalized set never need to be evaluated, layers whose scope lies entirely in the kept set are evaluated without squaring, and only the mixed layers in $\\phi_{Y,Z}$ are squared, yielding Theorem 1's complexity. Finally, Theorem 2 claims a bottom-up QR-based orthonormalization: residual triangular factors are pushed toward the output, Hadamard product layers are replaced once by Kronecker product layers, and the result is an orthonormal circuit equal to the original up to the scalar $Z^{-1/2}$, computable in polynomial time.","pith_inferences":["A natural testable extension is to learn sum layers under the semi-unitary constraint via manifold gradient methods and compare density-estimation quality and marginalization wall-clock time against unconstrained squared circuits on high-dimensional image data.","When the marginalized set is spatially scattered, the mixed layer set $\\phi_{Y,Z}$ can include many branches, so the speedup over $O(L S^2)$ shrinks; quantifying how $\\phi_{Y,Z}$ grows with the query pattern would let practitioners predict when the algorithm pays off.","The construction suggests a unified marginalization recipe for tensor networks that are not in a known canonical form: orthonormalize the circuit counterpart first, then apply the marginalization algorithm, instead of deriving a separate canonical form for each network topology.","Because the complexity of orthonormalization depends on the sizes of the residual matrices after face-splitting products, a closed-form bound on the orthonormalized circuit's size as a function of depth and width is the cleanest way to decide in advance whether conversion is worthwhile."],"forward_implications":["For an already-orthonormal circuit, computing the partition function becomes free: $Z = 1$, so the normalizing constant no longer costs $O(L S^2)$.","Marginalizing a variable subset costs $O(|\\phi_Y| S + |\\phi_{Y,Z}| S^2)$, which for tree-structured circuits with a localized query set can be close to linear in the circuit size rather than quadratic.","Layers whose scope depends only on the marginalized variables are skipped entirely during inference, not merely evaluated faster.","Since any tensorized circuit with orthonormal input functions can be orthonormalized in polynomial time up to the normalizing constant, the faster marginalization applies to the whole representable class, not only to models already built with unitary parameters.","The orthonormalization algorithm returns the reciprocal square root of the partition function as a byproduct, so normalization and orthonormalization happen in one pass."],"supporting_citations":[{"why":"Supplies the squaring construction and the previous $O(L S^2)$ marginalization baseline that Theorem 1 improves.","marker":"Loconte et al. (2024a)"},{"why":"Provides the normalization algorithm for monotonic probabilistic circuits that the orthonormalization algorithm is dual to.","marker":"Peharz et al. (2015)"},{"why":"Establishes the smoothness and decomposability conditions used to integrate squared circuits tractably.","marker":"Vergari et al. (2021)"},{"why":"Defines probabilistic circuits and the tractable marginalization requirements that the paper builds on.","marker":"Choi, Vergari, and Van den Broeck (2020)"},{"why":"Establishes squared and sum-of-squares circuits as expressive distribution estimators, motivating faster marginalization.","marker":"Loconte, Mengel, and Vergari (2024)"},{"why":"Supplies the tensor-network canonical-form viewpoint, with unitary matrices, that inspires the orthonormal parameterization.","marker":"Schollwoeck (2010)"},{"why":"Provides the matrix-product-state canonical form that ensures normalization, the tensor-network analogue of Proposition 1.","marker":"Pérez-García et al. (2007)"}],"fun_headline_variants":["Orthonormal squared circuits compute marginals faster","Fast marginals via orthonormalized squared circuits","Squared circuits orthonormalization cuts marginal cost","Automatic normalization speeds up squared circuit marginals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every tensorized circuit whose inputs are orthonormal can be reparameterized in polynomial time into an orthonormal circuit without the intermediate steps blowing up the circuit's size; without that bound, the faster marginalization result only helps circuits that are already given in orthonormal form.","fun_headline_variants_meta":{"raw":{"variants":["Orthonormal squared circuits compute marginals faster","Fast marginals via orthonormalized squared circuits","Squared circuits orthonormalization cuts marginal cost","Automatic normalization speeds up squared circuit marginals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1505,"prompt_tokens":911,"completion_tokens":594,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":533}},"tokens_in":527,"tokens_out":594,"duration_ms":5420,"temperature":1.0,"reasoning_tokens":533,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:30:56.179665+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the orthonormalization algorithm on a family of deep circuits built only from Hadamard product layers with orthonormal inputs, and track the width of the residual matrix returned at each recursive level; the polynomial-time claim fails if that width grows exponentially in depth while the input width stays polynomial.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the normalization algorithm for monotonic probabilistic circuits that the orthonormalization algorithm is dual to."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the smoothness and decomposability conditions used to integrate squared circuits tractably."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines probabilistic circuits and the tractable marginalization requirements that the paper builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the tensor-network canonical-form viewpoint, with unitary matrices, that inspires the orthonormal parameterization."}],"review_version":1}