{"id":"56bdd6d7-ff97-45a5-b877-33399dea5c82","arxiv_id":"2506.12383","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Structured Monarch matrices, derived from circuit multiplication, let probabilistic circuits scale to larger hidden sizes and beat prior tractable models at lower FLOP cost.","lead":"This paper proposes replacing the dense weight matrices inside probabilistic circuits with sparse structured Monarch matrices, which cuts memory and compute costs. The resulting models reach better likelihoods than prior tractable models on Text8, LM1B, and ImageNet, while matching dense models with far fewer operations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The scaling advantage rests on the unverified transfer of the dense-versus-Monarch gap-closing trend to token-level LM1B; a matched-size dense baseline there would settle it.","rationale":"I agree with the reader's weakest_assumption. The theoretical construction in Section 3 is internally consistent: the Kronecker-product circuit-multiplication derivation, the generalized Monarch definitions, and the FLOP/memory counts in Tables 3 and 6 are plausible. The single-run reporting and the abstract's unqualified 'state-of-the-art' wording are real issues, but they are secondary to the scaling claim. The decisive empirical pillar is the gap-closing trend, because without it the argument reduces to the tautology that structured matrices use fewer FLOPs; the nontrivial content is that this does not cost likelihood at scale. That trend is demonstrated on Text8 and ImageNet but not on LM1B, where a matched-size dense baseline is infeasible. A targeted dense-versus-Monarch scaling run on LM1B would directly test whether the trend transfers. Until that test is done, the reader's CONDITIONAL verdict remains appropriate, and my read does not change it.","tokens_in":17765,"tokens_out":19283,"duration_ms":234871,"concrete_test":"On LM1B, train a dense HMM at the largest feasible hidden sizes (e.g., h=2^15 and h=2^16, using smaller batches to fit memory) and a Monarch-HMM at the same two hidden sizes, then plot perplexity versus FLOPs per token as in Figure 4. If the dense-versus-Monarch gap at fixed h does not shrink from h=2^15 to h=2^16, or if the dense scaling curve stays below the Monarch curve at equal FLOPs, the LM1B headline does not support the central scaling claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that Monarch-structured sum blocks win by letting hidden size grow, because the likelihood gap between a dense block and a fixed Monarch block shrinks as h increases. This is verified only where a matched-size dense baseline fits: Text8 up to h=2^15 (Table 6, Figure 5) and ImageNet (Figure 7). The headline LM1B result (Table 4) compares a Monarch-HMM against a single dense HMM at a much smaller feasible hidden size, so the gap at matched h cannot be inspected. The text says LM1B uses the same setup as the Text8 experiments, where the Monarch model uses h=2^19, while the dense HMM baseline is presumably at the largest hidden size that fits in memory. If the gap does not close on token-level data, the perplexity gain from 320.78 to 190.34 could be mostly capacity, not Monarch structure, and the 'superior scaling behavior' claimed in the abstract would not transfer to LM1B. The authors' own Hypothesis 3 in Section 4 ('Increasing model size induces sparsity') is explicitly empirical, making this a load-bearing assumption rather than a peripheral detail.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes replacing the dense sum-block matrices in tensorized probabilistic circuits with Monarch-structured matrices. Section 3 derives the construction from circuit multiplication: multiplying two sum blocks yields a Kronecker-product weight matrix that can be materialized with O(m^3) rather than O(m^4) edges (Eq. 1), and the d-layer extension in Definition 3.2 connects generalized Monarch matrices to butterfly matrices (Theorem 3.4). Section 4 discusses initialization by multiplying smaller dense PCs and training via stochastic EM. Experiments on Text8, LM1B, ImageNet32, and ImageNet64 report improvements over PC baselines and better FLOPs-versus-likelihood scaling than dense circuits.","tokens_in":17937,"tokens_out":13246,"duration_ms":159517,"significance":"The core derivation is correct, and the paper's empirical scaling comparisons on Text8 (Figure 4 and Table 6) and ImageNet (Figure 7) directly support the main efficiency claim: at matched FLOPs, Monarch-structured circuits reach lower BPC than dense circuits. If the results hold, this is a practically important step for scaling tractable probabilistic models, reducing per-layer cost from O(h^2) to O(h^{3/2}) while providing a principled circuit-multiplication initialization. The paper's strengths include a public code release, exact FLOP reporting, and a falsifiable scaling comparison.","major_comments":[{"comment":"The paper does not specify how the Monarch factor tensors A and B are constrained so that the resulting sum blocks form a valid, normalized PC. Definition 2.1 requires non-negative sum weights that sum to one per sum node, but no parameterization or EM update is given for the factorized weights; without such a description, the 'likelihoods' reported in Tables 1, 4, and 5 and the stochastic-EM training described in Section 4 are not well-defined. Please state the normalization constraint on the slices of A and B (e.g., row-normalize each slice) and give the corresponding EM updates, or explicitly describe a global renormalization procedure.","section":"Section 4 / Definition 3.1"},{"comment":"The LM1B experiment compares Monarch-HMM against a single dense HMM at a much smaller hidden size, so the perplexity gain from 320.78 to 190.34 conflates increased hidden capacity with the Monarch structure. Because Section 5.1 states that dense HMM uses the largest hidden size that fits in memory while the Monarch model uses h=2^19, the 'superior scaling behavior' claim in the abstract is not directly verified on token-level data. Please add a matched-FLOP or matched-parameter dense (or alternative structured) baseline on LM1B, or explicitly qualify the scaling claim as an extrapolation from the Text8 and ImageNet experiments.","section":"Section 5.3, Table 4"},{"comment":"Hypothesis 3 ('Increasing model size induces sparsity') is load-bearing for the paper's central scaling argument, but it is only supported indirectly by the closing gap between dense and Monarch BPC as hidden size grows. No direct measurement of weight sparsity in trained dense sum blocks is provided, and the pruning experiment in Figure 6 concerns hidden-state activations rather than sum-block weights. Please provide a more direct test of the sparsity hypothesis or soften the claim that larger models are 'inherently more sparse'.","section":"Section 5.2, Figure 5"}],"minor_comments":[{"comment":"There are typos in Section 5.2: 'dimish' should be 'diminishes' and 'differernt' should be 'different'; Section 5.3 contains 'tims' instead of 'times'.","section":"Section 5.2"},{"comment":"The complexity expression 'O(dhd+1/d)' in the text should read O(d h^{(d+1)/d}) or O(d h^{1+1/d}) to be consistent with Table 3.","section":"Section 5.2, Table 3"},{"comment":"Figure 7's caption says 'Results for Training on ImageNet32 Dataset,' but the corresponding text discusses ImageNet64; please verify the intended dataset.","section":"Figure 7"},{"comment":"Tables 1 and 4 use the header 'Time (s) (↓)' for sampling time; the captions should state this consistently to avoid ambiguity.","section":"Tables 1 and 4"},{"comment":"Table 3 reports GPU memory in GB without stating the assumed bytes per element or the treatment of parameter caching versus hidden-state caching; please add these details for reproducibility.","section":"Table 3"}],"recommendation":"major_revision","confidential_remarks":"This is a solid and timely paper; the theoretical derivation and the main scaling evidence are convincing. The missing normalization/training details and the overbroad LM1B scaling claim are fixable in revision, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The math checks out, and this is a real advance for the probabilistic circuits subfield. The observation that circuit multiplication gives sum-block weights as a Kronecker product (Eq. 1) is clean, and the explicit materialization as interleaved sums and permutations is genuinely new. The generalization to multi-layer Monarch matrices and the butterfly connection (Theorem 3.4) are correct. The initialization by multiplying two smaller trained circuits is a practical trick that Table 2 shows works. On the empirical side, the scaling plots (Figures 4, 5, 7) support the main claim: at matched FLOPs, Monarch-HMM beats dense HMM, and the gap closes as hidden size grows. That is real evidence, not just a plausible story.\n\nThe soft spots are three, in increasing order of importance. First, the abstract overstates. The state-of-the-art claim is only among tractable models; the paper's own numbers are far from diffusion or flow models. The language should say that explicitly. Second, all headline numbers are single-run, with no error bars or seed variation. This is common in the PC literature, but given the size of the LM1B gap, a couple of seeds would help. Third, the load-bearing assumption is that the dense-versus-sparse gap shrinks as hidden size grows. The paper demonstrates that on Text8 and ImageNet with matched-size dense baselines, but not on LM1B, where the dense HMM baseline runs at a much smaller hidden size. The stress-test note makes a fair point: the LM1B improvement could be mostly capacity, not structure. The authors themselves flag this as Hypothesis 3, so it is not hidden, but the abstract's “superior scaling behavior” should be scoped to the data where it was actually tested.\n\nNone of this sinks the paper. The core mathematical contribution is sound, the code is released, and the practical gains in memory and FLOPs are real. The main fix is editorial: qualify the abstract, add seed variation, and either provide a smaller-scale token-level matched comparison or explicitly disclaim transfer to LM1B. I would send this to serious referees, and I would cite it in any work on scaling tractable models.","headline":"A mathematically sound and practically useful way to scale PCs with structured Monarch sum blocks; the main caveat is that the headline scaling claim isn't fully verified where it matters most (LM1B).","tokens_in":18547,"tokens_out":2043,"would_cite":true,"duration_ms":26293,"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":"This paper claims that replacing the dense matrices in probabilistic-circuit sum blocks with sparse Monarch-structured matrices turns the quadratic scaling bottleneck into a surplus that can be spent on hidden size, yielding better…","keywords":["probabilistic circuits","Monarch matrices","structured sparsity","density estimation","circuit multiplication","tractable generative models","hidden Markov models","FLOP scaling"],"falsifier":"Train a dense HMM and a Monarch-HMM on the same dataset at hidden sizes where both fit in memory (for example Text8 at $2^{12}$ through $2^{15}$) and measure the bits-per-character gap; if the gap does not shrink monotonically as hidden size increases, or if a dataset is found where the gap remains large even at the largest feasible hidden size, the central scaling claim fails. A second check is to train a Monarch-HMM at a hidden size whose FLOP budget matches a smaller dense HMM and verify that the Monarch model's likelihood is no better than the dense model's at equal FLOPs.","tokens_in":17469,"feed_emoji":"🧮","tokens_out":7909,"duration_ms":99866,"temperature":0.7,"pith_summary":"This paper claims that the quadratic cost of dense sum-block matrices is the main obstacle to scaling probabilistic circuits, and that replacing those matrices with sparse Monarch-structured ones removes much of that obstacle while keeping exact likelihood and marginal computations intact. The authors derive the Monarch parameterization from circuit multiplication: multiplying two sum blocks produces a sum block whose weight matrix is their Kronecker product, and that Kronecker map can be executed and materialized as interleaved sums and permutations rather than a dense matrix. In hidden Markov models and hidden Chow-Liu trees, this lets them push hidden sizes to $2^{19}$ while cutting per-layer operations from $O(h^2)$ to $O(h^{1.5})$. The resulting Monarch-HMM reaches 1.57 bits per character on Text8 and 190.34 perplexity on LM1B, and Monarch-HCLT reaches 4.01 bits per dimension on ImageNet32, better than the compared tractable baselines and with better likelihood per FLOP than dense circuits. The paper's point is that structure, not just raw size, is what lets tractable generative models scale.","feed_headline":"Monarch matrices scale probabilistic circuits past dense limits","feed_subtitle":"Cutting sum-block cost from quadratic to sub-quadratic lets PCs beat prior tractable models on text and image benchmarks.","key_machinery":"The load-bearing object is the generalized Monarch matrix, a structured linear map $M\\colon \\mathbb{R}^{p q}\\to \\mathbb{R}^{r s}$ defined by tensors $A\\in \\mathbb{R}^{r\\times p\\times q}$ and $B\\in \\mathbb{R}^{s\\times q\\times r}$ through $(Mx)_{kl} = \\sum_{i,j} A_{kij} B_{ljk} x_{ij}$, which is a batched contraction, a transpose, and a second batched contraction. The $d$-layer version is the same construction iterated $d$ times, and Theorem 3.4 shows that with all factors equal to $2\\times 2$ the result is exactly a butterfly matrix, so the family interpolates between Butterfly cost $O(h\\log h)$ and standard Monarch cost $O(h^{1.5})$ against the dense baseline $O(h^2)$. The identity $(A\\otimes B)x=(B(Ax)^{\\mathsf{T}})^{\\mathsf{T}}$ carries the argument: it shows the Kronecker product produced by multiplying two sum blocks can be materialized as a circuit with $O(m^3)$ edges instead of $O(m^4)$, and it motivates initializing large Monarch circuits by multiplying smaller dense circuits that were trained separately.","core_discovery":"The central claim is that the linear maps inside sum blocks of a probabilistic circuit do not need to be dense matrices, and that choosing them to be generalized Monarch matrices converts the main computational bottleneck of tensorized PCs into a surplus that can be spent on hidden size. Formally, multiplying two sum blocks with matrices $A$ and $B$ yields a sum block whose map is $A \\otimes B$, and the identity $(A\\otimes B)x = (B(Ax)^{\\mathsf{T}})^{\\mathsf{T}}$ shows this map can be executed with batched contractions instead of being materialized as a dense product. When the parameters are untied, this circuit-level fact becomes a family of Monarch linear layers, and multiplying $d$ circuits gives $d$-layer Monarch matrices that interpolate between Monarch and Butterfly sparsity. On Text8, LM1B, ImageNet32, and ImageNet64, PCs built with these layers outperform all compared tractable baselines and close part of the gap to less tractable diffusion and flow models, with better likelihood per FLOP than dense circuits at matched sizes.","pith_inferences":["Editorial inference: if the dense-versus-Monarch likelihood gap keeps shrinking with hidden size, dense sum blocks in PCs may become unnecessary at scale, and the practical ceiling on PC size becomes memory for hidden-state caching rather than parameter cost.","Editorial inference: the same circuit-multiplication derivation that produces Monarch matrices could be used to derive other structured matrix families, such as block tensor-train layers, inside PCs with a probabilistic initialization semantics.","Editorial inference: the pruning result suggests combining Monarch layers with learned pruning of hidden states could remove the remaining memory bottleneck and push to even larger hidden sizes.","Editorial inference: a testable extension is Monarch-structured sum blocks in downstream applications such as controllable generation, where the exact tractability that PCs retain over diffusion models is the payoff."],"forward_implications":["Monarch-HMM with hidden size $2^{19}$ reaches 1.57 bits per character on Text8, improving on the dense HMM baseline whose hidden size is capped at $2^{15}$ by memory, while sampling about 200 times faster than the compared diffusion models.","On LM1B, Monarch-HMM attains 190.34 test perplexity, where no prior PC model could scale, versus 320.78 for the dense HMM baseline.","Monarch-HCLT attains 4.01 bpd (lossy) and 4.62 bpd (lossless) on ImageNet32, and 3.74 and 4.33 bpd on ImageNet64, outperforming prior PC models including LVD-PG.","At every FLOP budget tested on Text8, Monarch-HMM gives better bits per character than dense HMM, and sparser structures with more Monarch layers scale even better in FLOP efficiency, though at higher memory cost.","Up to 90% of Monarch-HMM hidden states can be pruned with no significant likelihood drop, indicating that the learned representations are sparse."],"supporting_citations":[{"why":"Establishes the circuit-multiplication construction that yields Kronecker-product sum blocks and reports the quadratic size bound that the paper sharpens.","marker":"Vergari et al., 2021"},{"why":"Provides the earlier tractability result for multiplying structured-decomposable circuits that the paper's local product analysis builds on.","marker":"Shen et al., 2016"},{"why":"Introduces Monarch matrices, the structured matrix family the paper adapts to sum blocks.","marker":"Dao et al., 2022"},{"why":"Supplies the tensorized dense-circuit implementation that is the main architecture baseline and the source of the $O(h^2)$ cost.","marker":"Peharz et al., 2020"},{"why":"Provides the empirical observation that learned PC weights are sparse, motivating structured sparsity.","marker":"Dang et al., 2022"},{"why":"Supplies the Text8 benchmark used for character-level language modeling.","marker":"Mahoney, 2011"},{"why":"Supplies the LM1B benchmark used for token-level language modeling.","marker":"Chelba et al., 2013"},{"why":"Supplies the ImageNet32 and ImageNet64 benchmarks used for image density estimation.","marker":"Deng et al., 2009"}],"fun_headline_variants":["Monarch matrices make probabilistic circuits scale further with less compute","Sparse Monarch layers push probabilistic circuits to new scale and speed","Probabilistic circuits get a monarch-sized speedup from sparse matrices","Scaling PCs with sparse Monarch matrices: better performance, lower FLOPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method relies on the empirical pattern that, as models get bigger, the accuracy lost by using a fixed sparse pattern instead of a dense one shrinks fast enough that bigger sparse models beat smaller dense ones.","fun_headline_variants_meta":{"raw":{"variants":["Monarch matrices make probabilistic circuits scale further with less compute","Sparse Monarch layers push probabilistic circuits to new scale and speed","Probabilistic circuits get a monarch-sized speedup from sparse matrices","Scaling PCs with sparse Monarch matrices: better performance, lower FLOPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000862,"raw_usage":{"total_tokens":3729,"prompt_tokens":928,"completion_tokens":2801,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":2727}},"tokens_in":544,"tokens_out":2801,"duration_ms":105997,"temperature":1.0,"reasoning_tokens":2727,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:51:45.769038+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a dense HMM and a Monarch-HMM on the same dataset at hidden sizes where both fit in memory (for example Text8 at $2^{12}$ through $2^{15}$) and measure the bits-per-character gap; if the gap does not shrink monotonically as hidden size increases, or if a dataset is found where the gap remains large even at the largest feasible hidden size, the central scaling claim fails. A second check is to train a Monarch-HMM at a hidden size whose FLOP budget matches a smaller dense HMM and verify that the Monarch model's likelihood is no better than the dense model's at equal FLOPs.","supporting_citations":[],"review_version":1}