Paper deep dive
SymCircuit: Bayesian Structure Inference for Tractable Probabilistic Circuits via Entropy-Regularized Reinforcement Learning
Y. Sungtaek Ju
Intelligence
Status: succeeded | Model: anthropic/claude-sonnet-4.6 | Prompt: intel-v1 | Confidence: 97%
Last extracted: 3/24/2026, 2:58:31 AM
Summary
SymCircuit is a Bayesian structure learning framework for probabilistic circuits (PCs) that replaces greedy algorithms with a learned generative policy trained via entropy-regularized reinforcement learning. The framework instantiates the RL-as-inference paradigm in the PC domain, showing the optimal policy is a tempered Bayesian posterior. It introduces SymFormer, a grammar-constrained autoregressive Transformer with tree-relative self-attention, option-level REINFORCE for improved gradient SNR, a hybrid Adam/Anemone optimizer, and a three-layer uncertainty decomposition. On the NLTCS benchmark, SymCircuit closes 93% of the gap to LearnSPN with 33x sample efficiency gain, with preliminary scalability results on the Plants dataset (69 variables).
Entities (37)
Relation Signals (33)
Y. Sungtaek Ju โ affiliatedwith โ University of California, Los Angeles
confidence 99% ยท Y. Sungtaek Ju Department of Mechanical and Aerospace Engineering University of California, Los Angeles
SymCircuit โ applies โ Entropy-Regularized Reinforcement Learning
confidence 99% ยท SymCircuit replaces greedy search with a learned generative policy trained via entropy-regularized reinforcement learning.
Y. Sungtaek Ju โ authored โ SymCircuit
confidence 99% ยท SymCircuit: Bayesian Structure Inference for Tractable Probabilistic Circuits via Entropy-Regularized Reinforcement Learning โ Y. Sungtaek Ju
SymCircuit โ comparedto โ LearnSPN
confidence 99% ยท On NLTCS, SymCircuit closes 93% of the gap to LearnSPN.
SymCircuit โ evaluatedon โ NLTCS Dataset
confidence 99% ยท On NLTCS, SymCircuit closes 93% of the gap to LearnSPN.
SymCircuit โ introduces โ Option-Level REINFORCE
confidence 99% ยท We introduce option-level REINFORCE, restricting gradient updates to structural decisions rather than all tokens.
Sum-Product Networks โ isa โ Probabilistic Circuits
confidence 99% ยท Probabilistic circuits (PCs), including Sum-Product Networks (SPNs), Cutset Networks, and related structures
LearnSPN โ proposedby โ
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Probabilistic circuit (PC) structure learning is hampered by greedy algorithms that make irreversible, locally optimal decisions. We propose SymCircuit, which replaces greedy search with a learned generative policy trained via entropy-regularized reinforcement learning. Instantiating the RL-as-inference framework in the PC domain, we show the optimal policy is a tempered Bayesian posterior, recovering the exact posterior when the regularization temperature is set inversely proportional to the dataset size. The policy is implemented as SymFormer, a grammar-constrained autoregressive Transformer with tree-relative self-attention that guarantees valid circuits at every generation step. We introduce option-level REINFORCE, restricting gradient updates to structural decisions rather than all tokens, yielding an SNR (signal to noise ratio) improvement and >10 times sample efficiency gain on the NLTCS dataset. A three-layer uncertainty decomposition (structural via model averaging, parametric via the delta method, leaf via conjugate Dirichlet-Categorical propagation) is grounded in the multilinear polynomial structure of PC outputs. On NLTCS, SymCircuit closes 93% of the gap to LearnSPN; preliminary results on Plants (69 variables) suggest scalability.
Tags
Links
- Source: https://arxiv.org/abs/2603.20392v1
- Canonical: https://arxiv.org/abs/2603.20392v1
Trouble viewing inline? Open PDF directly โ
Full Text
37,784 characters extracted from source content.
Expand or collapse full text
1 SymCircuit: Bayesian Structure Inference for Tractable Probabilistic Circuits via Entropy-Regularized Reinforcement Learning Y. Sungtaek Ju Department of Mechanical and Aerospace Engineering University of California, Los Angeles Abstract. Probabilistic circuit (PC) structure learning is hampered by greedy algorithms that make irreversible, locally optimal decisions. We propose SymCircuit, which replaces greedy search with a learned generative policy trained via entropy-regularized reinforcement learning. Instantiating the RL-as-inference framework in the PC domain, we show the optimal policy is a tempered Bayesian posterior, recovering the exact posterior when the regularization temperature is set inversely proportional to the dataset size. The policy is implemented as SymFormer, a grammar-constrained autoregressive Transformer with tree-relative self-attention that guarantees valid circuits at every generation step. We introduce option-level REINFORCE, restricting gradient updates to structural decisions rather than all tokens, yielding an SNR (signal to noise ratio) improvement and >10 times sample efficiency gain on the NLTCS dataset. A three-layer uncertainty decomposition (structural via model averaging, parametric via the delta method, leaf via conjugate DirichletโCategorical propagation) is grounded in the multilinear polynomial structure of PC outputs. On NLTCS, SymCircuit closes 93% of the gap to LearnSPN; preliminary results on Plants (69 variables) suggest scalability. 1. Introduction Probabilistic circuits (PCs), including Sum-Product Networks (SPNs), Cutset Networks, and related structures, are a family of tractable probabilistic models that support exact, polynomial-time inference for a wide class of queries including marginals, conditionals, and maximum a posteriori assignments [Darwiche 2003; Choi, Vergari & Van den Broeck 2020]. Their tractability derives from two structural properties: decomposability (each product nodeโs children have disjoint variable scopes) and smoothness (each sum nodeโs children cover the same scope). These properties ensure that the circuit output is a multilinear polynomial in its parameters, a fact we exploit heavily in our uncertainty quantification framework. 2 The primary bottleneck in PC methodology is structure learning. The dominant algorithms โ LearnSPN [Gens & Domingos 2013], ID-SPN, Strudel [Dang, Vergari & Van den Broeck 2020] โ are greedy: they partition variables and data using independence tests or clustering heuristics, grow the circuit top-down, and commit irrevocably to each structural decision. Greedy approaches cannot recover from early partitioning errors, do not naturally express uncertainty about structure, and do not generalize their search strategies across datasets. The natural alternative is to learn a generative policy over circuits from data, analogous to how neural program synthesis learns to generate programs. Several recent works explore Transformer-based approaches for symbolic structures [Park et al. 2026 (SymPlex); Liu et al. 2025 (Tracformer)], but none have directly addressed PC structure learning through a policy gradient framework with a clear Bayesian interpretation. This paper makes the following contributions: 1. Theoretical: Applying the RL-as-inference framework of Levine (2018) to the discrete, grammar-constrained setting of PC structure generation, we derive that the optimal policy under entropy-regularized expected log-likelihood is a tempered Bayesian posterior ํ โ (ํฎ)โํ 0 (ํฎ)โ ํ(ํ|ํฎ) 1/(ํํผ) , recovering the exact posterior at ํผ=1/ํ. The novelty is the specific instantiation โ PC structures as the hypothesis space, data log-likelihood as the reward, and the identification of the 1/ํ scaling that governs the posterior temperature โ rather than the underlying variational derivation, which is standard. 2. Algorithmic: We introduce option-level REINFORCE with structural decision masking, which improves the signal-to-noise ratio of the policy gradient by the ratio of total tokens to structural decision token, empirically 3 times on NLTCS. We analyze the SNR of both estimators formally. 3. Architectural: SymFormer implements tree-relative self-attention, dynamic grammar masking for structural validity, and traversal-aware positional encoding, all within a standard autoregressive Transformer framework. 4. Optimization: A hybrid Adam/Anemone optimizer leverages flow-weighted EM for sum weights and Adam for leaf parameters. The split is motivated by the known equivalence between full-batch EM and natural gradient descent for mixture models, and by empirical evidence that applying EM to leaf parameters causes divergence in early training. 5. Uncertainty quantification: A three-layer decomposition assigns structural, parametric, and leaf uncertainty to distinct mechanisms. The leaf layer is exactly closed-form under the conjugate DirichletโCategorical model; the parameter layer is asymptotically valid via the delta method; the structural layer is an approximation dependent on both the amortization gap and the training temperature. 3 6. Empirical: Near-optimal performance on NLTCS (93% gap closure to LearnSPN), 33x sample efficiency gain, and preliminary scalability results on Plants (69 variables). 2. Background 2.1 Probabilistic Circuits A probabilistic circuit ํ over variables ํ=(ํ 1 ,...,ํ ํ ) is a rooted directed acyclic graph with three node types: โข Leaf nodes compute univariate distributions ํ โ (ํ ํ (โ) ) over a single variable ํ ํ (โ) . โข Product nodes ํ with children ํ 1 ,...,ํ ํ compute ํ ํ (ํฑ)= โ ํ ํ ํ ํ ํ=1 (ํฑ ํ ํ ํ ), where ํ ํ ํ โํ is the scope of child ํ ํ . โข Sum nodes ํ with children ํ 1 ,...,ํ ํ and weights ํ ํ โฮ ํโ1 compute ํ ํ (ํฑ)= โ ํ ํ,ํ ํ ํ=1 ํ ํ ํ (ํฑ). Decomposability: For every product node ํ with children ํ 1 ,...,ํ ํ , the scopes are pairwise disjoint: ํ ํ ํ โฉํ ํ ํ =โ for ํโ ํ. Smoothness: For every sum node ํ with children ํ 1 ,...,ํ ํ , all children have the same scope: ํ ํ 1 =โฏ=ํ ํ ํ . Under these two properties, the circuit output ํ ํ (ํฑ) is computable in ํ(|ํ|) time, where |ํ| denotes the number of edges in the circuit. Marginal inference for any subset of variables also runs in ํ(|ํ|). A foundational observation [Darwiche 2003; Broadrick et al. 2024] is that ํ ํ (ํฑ), viewed as a function of the sum-weight parameters ํฝ, is a multilinear polynomial โ each ํ ํ,ํ appears at most once in any monomial. This implies that partial derivatives โํ ํ (ํฑ)/โํ ํ,ํ are computable exactly in ํ(|ํ|) via a single forward-backward pass, and the Fisher information matrix is block-diagonal with blocks indexed by sum nodes. 2.2 Structure Learning Baselines LearnSPN [Gens & Domingos 2013] greedily partitions data by independence tests (G-test or ํ 2 ) and recursively builds an SPN top-down. It is the standard benchmark for tractable PC structure learning on density estimation benchmarks. Strudel [Dang, Vergari & Van den Broeck 2020] learns structured-decomposable circuits by sharing a single computational graph across mixture components for efficient ensemble learning. It achieves strong results but is specific to the structured decomposability circuit class. 4 Both are one-shot, non-amortized procedures: given a dataset ํ, they produce a single circuit with no ability to express structural uncertainty. 2.3 RL as Inference The connection between entropy-regularized RL and probabilistic inference has been established in the control theory literature [Levine 2018; Rawlik et al. 2012; Ziebart et al. 2008]. We adapt this framework to the discrete, combinatorial setting of PC structure generation, where actions are token selections and the reward is data log-likelihood. 2.4 SymFormer and SymPlex SymPlex [Park et al. 2026] demonstrated that a structure-aware Transformer with tree- relative attention and grammar-constrained generation can effectively search symbolic spaces (PDEs) via curriculum RL. A universality theorem establishes that SymFormer can represent any grammar-compatible generation policy over bounded-depth trees given sufficient capacity. We adapt this architecture directly to the PC domain. 3. The SymCircuit Framework 3.1 Problem Formulation Let ํข be a context-free grammar over PC structures that enforces decomposability and smoothness. Concretely, ํข generates labeled ordered trees via productions of the form: Scope(ํ) โ Sum ํ (Scope(ํ) ํ ) | Prod(ํ 1 ,...,ํ ํ ) | Leaf(ํฃ) with the constraint that โจ ํ ํ ํ =ํ for product rules and ํ 1 =โฏ=ํ ํ =ํ for sum rules. Every sentence generated by ํข is a valid PC by construction. We represent structures as sequences of tokens via depth-first (pre-order) traversal. The token vocabulary consists of sum-arity tokens Sum 2 ,Sum 3 , fixed-arity product tokens Factorize ํ :ํโ[2,ํ], and leaf tokens Leaf(ํฃ):ํฃโ[ํ]. Fixed-arity tokens (rather than dynamic-arity tokens) are essential for unambiguous parsing: the effective arity of Factorize ํ is baked into its type, eliminating scope-assignment ambiguities that arise with a single dynamic-arity token (a lesson learned through implementation). The structure learning problem is as follows: given i.i.d. training data ํ=ํฑ (1) ,...,ํฑ (ํ) , find a policy ํ ํ over ํข-generated structures that maximizes expected data log-likelihood. 5 3.2 SymFormer Architecture SymFormer is an autoregressive Transformer ํ ํ :ํฑ โ โฮ |ํฑ| that generates token sequences representing PC structures. Three design choices distinguish it from a standard language model: Tree-relative self-attention: Standard positional encodings (absolute or relative) encode sequence position but not structural relationships. SymFormer augments the attention bias term with a learned scalar offset ํ ํ,โ (tree) for each relation type ํโ parent, child, sibling, ancestor, other and attention head โ: ํด ํํ (โ) = (ํช ํ (โ) ) โค ํค ํ (โ) โ ํ ํ +ํ ํ(ํ,ํ),โ (tree) where ํ(ํ,ํ) denotes the tree relation between tokens at positions ํ and ํ in the partial circuit. This is a scalar-per-relation-per-head rather than vector-per-relation design, reducing memory from ํ(|ํฑ|โ ํ 2 โ ํ ํ ) to ํ(ํปโ |โ|) โ a crucial efficiency gain when sequences reach 200+ tokens. Dynamic grammar masking: At each generation step, the grammar state ํ ํก tracks the current open scope and partial parse tree. The set of valid next tokens ํฑ(ํ ํก )โํฑ is computed in ํ(|ํฑ|). Logits for invalid tokens are set to โโ before softmax, enforcing ํ ํ (ํโฃํ ํก )=0 for all ํโํฑ(ํ ํก ). This guarantees that every sampled structure is a valid PC. Traversal-aware positional encoding: A sinusoidal encoding of depth-in-tree (not sequence position) is added to token embeddings, helping the model distinguish structurally similar but contextually distinct nodes at different depths. Theorem 4.1 of Park et al. (2026) establishes that SymFormer can realize any grammar- compatible generation policy over bounded-depth trees with sufficient parameters. The implication for our setting is that the architecture is not a representational bottleneck: if a good structure-generation policy exists within the grammar, SymFormer can approximate it. 3.3 Entropy-Regularized RL as Bayesian Structure Inference We train SymFormer by maximizing the entropy-regularized expected reward: ํฝ(ํ)=ํผ ํฎโผํ ํ [ 1 ํ โlog ํ ํ=1 ํ ํฎ,ํ ฬ (ํฎ) (ํฑ (ํ) )]โํผโ ํท KL (ํ ํ โฅํ 0 ) where ํ ฬ (ํฎ) are parameters optimized for structure ํฎ (via Anemone, Section 3.4), ํ 0 is a prior policy over structures, and ํผ>0 is a temperature parameter. 6 Proposition 1 (Optimal policy as tempered posterior; instantiation of Levine 2018). Let ํ (ํฎ)โ 1 ํ โ log ํ ํ=1 ํ ํฎ,ํ ฬ (ํฎ) (ํฑ (ํ) ) denote the empirical average log-likelihood. The unique maximizer of ํฝ(ํ) over all distributions on ํข is: ํ โ (ํฎ)= ํ 0 (ํฎ)โ exp ( ํ (ํฎ)/ํผ ) ํ(ํผ) , ํ(ํผ)=โํ 0 ํฎโํข (ํฎ)โ exp ( ํ (ํฎ)/ํผ ) . Since ํ (ํฎ)= 1 ํ logํ(ํโฃํฎ), this can be written as: ํ โ (ํฎ)โํ 0 (ํฎ)โ ํ(ํโฃํฎ) 1/(ํํผ) , a tempered (annealed) Bayesian posterior with temperature ํํผ. At ํผ=1/ํ, the exponent equals 1 and ํ โ recovers the exact Bayesian posterior: ํ โ (ํฎ)| ํผ=1/ํ =ํ(ํฎโฃํ)= ํ 0 (ํฎ)โ ํ(ํโฃํฎ) โ ํ 0ํฎ โฒ(ํฎ โฒ )โ ํ(ํโฃํฎ โฒ ) . For general ํผ, the optimal policy interpolates between the prior ํ 0 (as ํผโโ) and a degenerate point mass on the MAP structure (as ํผโ0). Proof. The objective ํฝ(ํ) is: ํฝ(ํ)=โํ ํ ํฎ (ํฎ)ํ (ํฎ)โํผโํ ํ ํฎ (ํฎ)log ํ ํ (ํฎ) ํ 0 (ํฎ) . Introducing Lagrange multiplier ํ for the constraint โ ํ ํํฎ (ํฎ)=1 and differentiating with respect to ํ ํ (ํฎ): ํ (ํฎ)โํผ(log ํ ํ (ํฎ) ํ 0 (ํฎ) +1)+ํ=0โนlogํ ํ โ (ํฎ)= ํ (ํฎ) ํผ +logํ 0 (ํฎ)+ ํโํผ ํผ . Normalizing over ํฎ gives the stated form. The second variation is โํผ/ํ ํ (ํฎ)<0, confirming a global maximum. Uniqueness follows from strict concavity of โํท KL (ํ ํ โฅํ 0 ) over the probability simplex. Substituting ํ (ํฎ)= 1 ํ logํ(ํ|ํฎ) gives the tempered posterior form; setting ํผ=1/ํ reduces the exponent to 1, recovering the exact Bayesian posterior by Bayesโ theorem. โซ Remark 1 (Amortization gap and temperature). In practice, ํ ํ is a parameterized model (SymFormer), not a free distribution over all of ํข. The trained policy therefore approximates ํ โ within the modelโs capacity; the gap ํท KL (ํ โ โฅํ ํ ) is the amortization gap, analogous to that in amortized variational inference. The gradient โ ํ ํฝ(ํ) pushes ํ ํ toward ํ โ locally, but convergence to the global maximizer is not guaranteed. Additionally, the experimental ํผ=0.01 with ํ=16,181 gives 1/(ํํผ)โ0.006, placing the trained policy in a regime considerably warmer than the true posterior (1/(ํํผ)=1). The policy is thus a heavily smoothed approximation to the posterior. It spreads probability more broadly across 7 structures than Bayesโ rule prescribes, which is appropriate for the exploration- exploitation tradeoff in RL training but means the structural variance estimator ํ struct underestimates the true posteriorโs concentration. Remark 2 (Prior and pretraining). We take ํ 0 to be the imitation-pretrained policy, obtained by supervised learning on circuits generated by LearnSPN. The imitation loss (cross- entropy on LearnSPN token sequences) stabilizes early RL training and encodes a data- informed structural prior, interpreting the pretraining phase as prior construction. We estimate structural uncertainty via model averaging. Given a test observation ํฑ โ and ํพ independently sampled structures ํฎ 1 ,...,ํฎ ํพ โผํ ํ with fitted parameters ํ ฬ ํ : ํฬ(ํฑ โ )= 1 ํพ โํ ํฎ ํ ,ํ ฬ ํ ํพ ํ=1 (ํฑ โ ), ํ struct (ํฑ โ )= 1 ํพโ1 โ(ํ ํฎ ํ ,ํ ฬ ํ (ํฑ โ )โํฬ(ํฑ โ )) 2 ํพ ํ=1 . The factor 1/(ํพโ1) gives the unbiased sample variance estimator (Besselโs correction). This estimator is consistent for the true inter-structural variance as ํพโโ. 3.4 Option-Level REINFORCE REINFORCE assigns a scalar reward ํ (ํฎ) to an entire token sequence of length ํ (typically 50โ200 tokens for our circuits). The gradient estimator is: ํฬ tok = 1 ํ โ( ํ ํก=1 ํ (ํฎ)โํ)โ ํ logํ ํ (ํ ํก โฃํ ํก ) The signal-to-noise ratio (SNR) of this estimator scales as ํ(1/ โ ํ) in the number of tokens (by a standard argument: each term contributes independent noise proportional to the variance of (ํ โํ)โlogํ, while the signal averages over only ํท meaningful structural choices embedded among ํ tokens). The root cause is that most tokens are deterministic given the grammar state: leaf tokens are fully determined by scope-coverage constraints, and product-node tokens are forced once sum-node children are decided. Only sum-node arity decisions (tokens of type Sum ํ ) constitute genuine policy choices. Let ํทโคํ denote the number of sum-node selections in a generated circuit. Option-level estimator: Let โ(ํฎ)=ํก:ํ ํก โSum 2 ,Sum 3 be the index set of structural decisions in the generated sequence ํฎ, with |โ(ํฎ)|=ํท(ํฎ). We define the option-level REINFORCE gradient estimator as: ํฬ opt = 1 ํท(ํฎ) โ( ํกโโ(ํฎ) ํ (ํฎ)โํ)โ ํ logํ ํ (ํ ํก โฃํ ํก ) 8 Proposition 2 (SNR improvement). Assume tokens are generated i.i.d. (a simplification), that Var[(ํ โํ)โ ํ logํ ํ (ํ ํก โฃํ ํก )]=ํ 2 is constant across all positions ํก, and that ํผ[(ํ โ ํ)โ ํ logํ ํ (ํ ํก โฃํ ํก )]=0 at non-structural positions (since ํ ํ is near-deterministic there). Then: SNR(ํฬ opt ) SNR(ํฬ tok ) = โ ํ ํท . The two estimators are proportional in expectation: ํผ[ํฬ opt ]= ํ ํท ํผ[ํฬ tok ]. Both estimate the same gradient direction; their scale difference by ํ/ํท is absorbed into the effective learning rate. Proof. Let ํ ํก =ํผ[(ํ โํ)โ ํ logํ ํ (ํ ํก โฃํ ํก )]. By assumption ํ ํก =ํโ 0 for ํกโโ and ํ ํก =0 otherwise. Under i.i.d. variance ํ 2 : ํผ[ํฬ tok ]= 1 ํ โํ ํก ํ ํก=1 = ํทํ ํ , Var[ํฬ tok ]= ํํ 2 ํ 2 = ํ 2 ํ . ํผ[ํฬ opt ]= 1 ํท โํ ํก ํกโโ =ํ, Var[ํฬ opt ]= ํทํ 2 ํท 2 = ํ 2 ํท . Therefore ํผ[ํฬ opt ]=(ํ/ํท) ํผ[ํฬ tok ], and: SNR(ํฬ opt ) SNR(ํฬ tok ) = ํ/(ํ/ โ ํท) (ํทํ/ํ)/(ํ/ โ ํ) = ํ โ ํท/ํ ํทํ/(ํ โ ํ) = โ ํ ํท . โซ Empirically, NLTCS circuits have ํโ50โ100 and ํทโ3โ6, giving โ ํ/ํทโ3โ5 in gradient SNR. The 33ร gain in sample efficiency (circuits to reach a target performance) compounds this with reduced mode-collapse behavior observed in practice. 3.5 Hybrid Adam/Anemone Parameter Optimization Given a fixed structure ํฎ, we optimize parameters ํ=(ํ sum ,ํ leaf ) using a hybrid scheme: Sum weights via Anemone EM: Anemone [Liu & Van den Broeck 2025] is a mini-batch EM algorithm for PC parameters. Each step computes top-down flow probabilities ํ ํ (ํฑ) (the probability that node ํ is activated on input ํฑ under the current model), then updates sum weights via flow-weighted sufficient statistics: ํ ํ,ํ new โโํ ํ ํฑโโฌ (ํฑ)โ ํ ํ,ํ โ ํ ํ (ํฑ) ํ ํ (ํฑ) 9 This is an implicit adaptive learning rate that scales each componentโs update by its contribution to current batch likelihood. Anemone converges 8ร faster than Adam on PC parameters across benchmarks, exploiting the multilinear polynomial structure of ํ ํ (ํฑ) that gradient-based methods cannot leverage. Leaf parameters via Adam: Leaf parameters (Bernoulli logits for binary data) do not benefit from the flow-weighted EM update โ the EM update for leaves degenerates to batch empirical means under uniform sum weights, destroying MLE initialization. We observed empirically that pure Anemone EM for leaves causes log-likelihood degradation from โ5.37 to โ25.30 nats in early training. Adam with its momentum and adaptive learning rate handles the curved leaf landscape correctly. Let โ(ํ)= 1 |โฌ| โ log ํฑโโฌ ํ ํ (ํฑ). For exponential family mixture models, full-batch EM is equivalent to a natural gradient step in the Fisher information metric [Amari 1998]. For tree-structured PCs, the block-diagonal Fisher (Proposition 3) means this natural gradient decomposes independently per sum node โ exactly the structure Anemone exploits. In the mini-batch setting Anemone approximates this natural gradient, with the KL regularization in its objective controlling the distribution shift between updates. For leaf parameters, the Fisher block structure mixes sum-weight and leaf contributions in a way that is ill-conditioned under random sum-weight initialization, making natural gradient steps unreliable; Adamโs diagonal preconditioning is a more robust choice, as confirmed by the empirical degradation observed with pure EM on leaves. 4. Uncertainty Quantification Framework We decompose predictive uncertainty into three additive layers, each with distinct formal guarantees. 4.1 Structural Uncertainty As derived in Section 3.3, structural uncertainty is estimated by Monte Carlo model averaging with the unbiased sample variance: ํ struct (ํฑ โ )= 1 ํพโ1 โ(ํ ํฎ ํ (ํฑ โ )โํฬ(ํฑ โ )) 2 ํพ ํ=1 This term is nonzero if and only if different structural hypotheses assign different probabilities to ํฑ โ , detecting genuine epistemic uncertainty about the data-generating decomposition. It is a consistent estimator of the inter-structural variance under the trained policy ํ ํ ; how closely this reflects the true Bayesian posterior variance depends on the amortization gap and the temperature ํผ (see Remark 1). 10 4.2 Parameter Uncertainty Block-diagonal Fisher information: By decomposability, different sum nodesโ weights govern independent (in the probabilistic sense) aspects of the circuitโs computation. Formally: Proposition 3 (Block-diagonal Fisher; known result, included for completeness). For a smooth and decomposable tree-structured PC ํ (every internal node has exactly one parent) with sum nodes ํ 1 ,...,ํ ํ , the Fisher information matrix โ(ํ sum ) is block- diagonal: โ(ํ sum )=โจ ํ=1 ํ โ ํ (ํ ํ ํ ) where each block โ ํ is a (ํ ํ โ1)ร(ํ ํ โ1) positive-definite matrix for a sum node with ํ ํ children (the simplex constraint removes one degree of freedom). This follows from the multilinear polynomial form of PCs [Darwiche 2003; Broadrick et al. 2024], which implies that each sum weight appears in a disjoint subset of monomials. We include the proof for completeness. Proof. For distinct sum nodes ํ ํ โ ํ ํ , the cross-Fisher entry is โ ํํ =ํผ ํฑ [โ ํ ํ ํ logํ ํ (ํฑ)โ โ ํ ํ ํ logํ ํ (ํฑ)]. By the chain rule, โ ํ ํ ํ logํ ํ =ํ ํ โ1 โ โ ํ ํ ํ ํ ํ . The multilinear polynomial form (Darwiche 2003) gives โ ํ ํ ํ ํ ํ (ํฑ)=TD(ํ ํ ;ํฑ)โ ํ ํ ํ (ํฑ), where ํ ํ is the child indexed by ํ ํ ํ . In a tree-structured PC, ํ ํ and ํ ํ lie on disjoint root-to-leaf paths (since there are no shared subgraphs). Therefore TD(ํ ํ ;ํฑ)โ TD(ํ ํ ;ํฑ) factors into a product of probabilities along non-overlapping paths, and the expectation ํผ ํฑ [TD(ํ ํ )โ ํ ํ ํ โ TD(ํ ํ )โ ํ ํ ํ ]/ํผ ํฑ [ํ ํ 2 ] factors as a product of independent marginals over the disjoint scopes, giving โ ํํ =0. โซ Delta-method variance: Given the block-diagonal Fisher โ(ํ sum ) estimated from training data and the multilinear polynomial gradient โ ํ sum ํ ํ (ํฑ โ ), the delta-method approximation to parameter uncertainty is: ํ param (ํฑ โ )โ 1 ํ (โ ํ sum ํ ํ (ํฑ โ )) โค โ(ํ sum ) โ1 (โ ํ sum ํ ํ (ํฑ โ )). The 1/ํ factor arises from the asymptotic MLE covariance: Var[ํ ฬ ]โ 1 ํ โ(ํ) โ1 under standard regularity conditions, so that ํ param โ0 as ํโโ at rate 1/ํ. Using the identity โํ ํ (ํฑ)/โํ ํ,ํ =TD(ํ;ํฑ)โ ํ ํ (ํฑ) [Darwiche 2003, Theorem 1] (where TD(ํ;ํฑ) is the top-down probability of node ํ on input ํฑ), both the gradient and the Fisher blocks are computable from Anemoneโs flow statistics at ํ(|ํ|) additional cost. With ํ= 16,181 training samples and |ํ sum |โ40 free parameters, the 1/ํ prefactor renders ํ param negligible โ a consistency check on the framework. The block Fisher matrices can be ill-conditioned (empirically, condition numbers up to 1000 in sparse circuits). We apply an eigenvalue-clamped pseudo-inverse, regularizing 11 only directions with eigenvalues below a threshold ํ min while preserving well-conditioned directions exactly. 4.3 Leaf Uncertainty and Variance Propagation DirichletโCategorical leaves: For binary data (ํฑโ0,1 ํ ), we model each leaf as Dirichletโ Categorical with concentration parameters ํ โ =(ํผ โ,0 ,ํผ โ,1 ). The predictive mean is ํ โ = ํผ โ,1 /(ํผ โ,0 +ํผ โ,1 ) and the predictive variance is: ํ โ = ํผ โ,0 ํผ โ,1 (ํผ โ,0 +ํผ โ,1 ) 2 (ํผ โ,0 +ํผ โ,1 +1) . Anemone compatibility: The conjugate update for Dirichlet concentration from a batch โฌ with flow weights ํ โ (ํฑ) is: ํผ โ,ํฃ new =ํผ โ,ํฃ prior +ํโ ํ ฬ โ,ํฃ , ํ ฬ โ,ํฃ =โํ โ ํฑโโฌ (ํฑ)โ ํ[ํฅ ํ (โ) =ํฃ] where ํ ฬ โ,ํฃ is the flow-weighted count of label ํฃ at leaf โ. This is exactly the sufficient statistic Anemone already computes, making the extension parameter-free. Importantly, ํ ฬ โ,ํฃ is bounded by batch size (since ํ โ (ํฑ)โค1), preventing the evidence-inflation pathology that afflicts gradient-based evidential learning. Variance propagation through the circuit. Product nodes (exact). Decomposability ensures that child circuits ํ ํ ํ (ํฑ ํ ํ ํ ) are evaluated on pairwise disjoint variable sets. In a tree-structured PC, the leaf parameters under each child sub-tree are disjoint objects with independent Dirichlet concentrations. Therefore ํ ํ ํ (ํฑ ํ ํ ํ ) and ํ ํ ํ โฒ (ํฑ ํ ํ ํ โฒ ) are independent random variables (for ํโ ํ โฒ ). Taking logarithms and applying variance additivity for independent variables: Var [ logํ ํ (ํฑ) ] =โVar ํ ํ=1 [logํ ํ ํ (ํฑ ํ ํ ํ )] This is exact, not an approximation โ it follows from the variance additivity for sums of independent random variables. No linearization or delta method is applied at product nodes. Sum nodes. A sum node computes ํ ํ (ํฑ)= โ ํ ํ,ํ ํ ํ=1 ํ ํ ํ (ํฑ) with fixed deterministic weights ํฝ ํ . In a tree-structured PC (which LearnSPN produces and which our grammar generates), the children of each sum node have their own disjoint leaf nodes, so the Dirichlet leaf uncertainties of different children are independent. Applying the variance formula for a weighted sum of independent random variables: 12 Var [ ํ ํ (ํฑ) ] =โํ ํ,ํ 2 ํ ํ=1 ํ ํ ํ (ํฑ) where ํ ํ ํ (ํฑ)=Var[ํ ํ ํ (ํฑ)]. This is exact under the independence assumption. This formula is computed in the same bottom-up pass as the forward evaluation. Total uncertainty decomposition: For a fixed structure ํฎ ํ , leaf uncertainty ํ leaf,ํ (ํฑ โ ) is obtained via upward variance propagation from leaves. Aggregating over ํพ structural samples: ํ total (ํฑ โ )=ํ struct (ํฑ โ )+ 1 ํพ โํ param,ํ ํพ ํ=1 (ํฑ โ )+ 1 ํพ โํ leaf,ํ ํพ ํ=1 (ํฑ โ ) where ํ param,ํ is the delta-method parameter variance for structure ํฎ ํ . The additive form follows from the law of total variance applied hierarchically: the between-structure term (ํ struct ) and the average within-structure term are orthogonal by construction, and within each structure, parameter and leaf uncertainty are treated as additive under the approximation that their cross-covariance is small relative to the dominant structural term. 5. Experiments 5.1 Setup Datasets: We evaluate on two DEBD binary density estimation benchmarks: - NLTCS (16 variables, 16,181 train / 2,157 test): a retirement survey dataset used as the primary development testbed. - Plants (69 variables, 17,412 train / 3,482 test): a plant co-occurrence dataset used for preliminary scalability evaluation. Baselines: The primary structural baseline is LearnSPN [Gens & Domingos 2013] with G- test independence scoring and default hyperparameters, evaluated using SPFlow 1.0. We report test set average log-likelihood (nats, higher is better). LearnSPN achieves โ6.093 on NLTCS and approximately โ12.98 on Plants. Training protocol: Phase 1 (supervised pretraining): SymFormer is trained by maximum likelihood on token sequences generated by running LearnSPN on 60 training circuits, for 50 epochs. Phase 2 (RL fine-tuning): option-level REINFORCE with the pretrained policy as ํ 0 , hybrid Adam/Anemone parameter optimization (30 Anemone steps per circuit for RL rewards), epsilon-greedy exploration (ํ=0.15 annealed to 0.05), and entropy regularization with coefficient ํผ=0.01. A replay buffer of 200 circuits maintains diversity. 13 5.2 NLTCS Results Table 1 summarizes performance across training phases. The supervised pretraining baseline establishes the starting point for RL fine-tuning; option-level RL (Phase 2e) dramatically outperforms token-level RL (Phase 2c/d) in sample efficiency. Phase Method Test L (nats) Circuits Used Gap to LearnSPN Pretraining Supervised (imitation) โ6.229 โ 0.136 Phase 2b Token-level REINFORCE (baseline) โ6.232 4,000+ 0.139 Phase 2c Token-level REINFORCE + vocab expansion โ6.159 4,000 0.066 Phase 2e Option-level REINFORCE โ6.105 120 (30ep) โ converged 0.011 LearnSPN Greedy heuristic โ6.093 โ 0 Convergence and sample efficiency: Option-level REINFORCE reaches โ6.139 nats in 30 epochs (120 circuit evaluations), matching Phase 2cโs best performance (โ6.159 nats after 500 epochs, 4,000 evaluations). The full Run D converges to โ6.105 nats. This 33ร reduction in circuits-to-performance is consistent with Proposition 2โs SNR analysis, given empirically measured ํ/ํทโ15โ30 for NLTCS circuits. Value head ablation: Phase 2e added an actor-critic value head operating at the option level to reduce gradient variance further. On NLTCS, the value headโs explained variance remained near zero throughout training (EV โ 0), providing no benefit. We attribute this to the small number of structural decisions per circuit (ํทโ3โ6) โ insufficient for meaningful credit assignment to a learned value function. The value head is a no-op on NLTCS but may provide benefit on larger datasets with richer structure (ํทโซ10). 14 5.3 Uncertainty Quantification Analysis (NLTCS) We evaluated the three-layer UQ decomposition on the NLTCS test set using ํพ=10 structural samples from the trained policy. Table 2 shows the mean decomposition across test points. Layer Mechanism Mean Variance Fraction of Total Structural MC model averaging (ํพ=10) 0.324 85.1% Parameter Block-diagonal Fisher + delta method 0.004 1.1% Leaf Dirichlet variance propagation 0.052 13.8% Total 0.380 100% This decomposition is physically sensible: with ํ=16,181 training samples and |ํฝ sum |โ 40 free parameters, the asymptotic CramรฉrโRao bound implies negligible parameter uncertainty, as confirmed by ํ param accounting for just 1.1% of total variance. Structural uncertainty dominates at 85.1%, indicating that the policyโs structural diversity (different decomposition choices across samples) drives most of the predictive uncertainty on this dataset. Monte Carlo validation of leaf UQ: We validated the analytic variance propagation against Monte Carlo estimation (5,000 samples per leaf parameter). The mean relative error across test points was 3.8% with correlation 0.997, confirming that the analytic propagation formulas are accurate. Fisher matrix conditioning: Sum node Fisher blocks exhibited condition numbers ranging from 2 to 1,200. Eigenvalue-clamped pseudo-inverse with ํ min =10 โ4 was necessary to prevent numerical blow-up; 18% of blocks required regularization. 5.4 Preliminary Scalability: Plants Dataset We ran option-level REINFORCE on the Plants dataset (69 variables) for 25 epochs to assess scalability. Key differences from NLTCS: โข Circuit size scales: ํโ200โ400 tokens vs. 50โ100 on NLTCS. โข Anemone steps were reduced from 100 to 30 per circuit for RL reward computation (sufficient since only relative circuit ranking matters for REINFORCE, not absolute convergence). โข Training time was approximately 6โ12 minutes per epoch due to larger circuit evaluation. After 25 epochs, the best circuit achieved โ15.77 nats, closing 19% of the 3.45-nat gap between the pretraining baseline (โ16.43 nats) and LearnSPN (โโ12.98 nats). Training was still improving; full convergence results are pending. 15 These preliminary results demonstrate that the framework scales beyond the 16-variable NLTCS setting, though the larger search space and longer circuits make convergence slower. The value head, which provides no benefit on NLTCS, may be beneficial here given the larger number of structural decisions per circuit. 6. Discussion 6.1 Connection to Program-Level Marginalization Proposition 1 establishes that sampling from the trained policy ํ ํ and averaging circuit outputs implements (approximate) Bayesian model averaging over probabilistic circuit structures. This can be viewed as program-level marginalization, averaging over complete probabilistic programs (circuits) rather than over derivation paths within a fixed program (as in ProbLog/DeepProbLog). Every circuit in our hypothesis space guarantees polynomial-time inference by construction, ensuring that the marginalization is tractable regardless of the number of structures sampled. In contrast, proof-level marginalization in general logic programming involves summing over derivation trees in a #P-hard computation. Our framework avoids this by restricting the hypothesis space to tractable theories from the outset. 6.2 Limitations and Failure Modes Amortization gap and temperature: The trained ํ ํ approximates ํ โ within the modelโs capacity. Two separate gaps separate it from the true Bayesian posterior: (1) the amortization gap ํท KL (ํ โ โฅํ ํ ) from finite model capacity, and (2) the temperature mismatch โ the experimental ํผ=0.01 with ํ=16,181 gives 1/(ํํผ)โ0.006, meaning the trained policy is considerably warmer (flatter) than the true posterior (1/(ํํผ)=1). Neither gap is quantifiable without access to the intractable partition function ํ(ํผ). For the purposes of uncertainty quantification, ํ struct measures the diversity of the trained policy, which reflects Bayesian structural uncertainty only approximately. Grammar constraints as inductive bias: The grammar vocabulary Sum 2 ,Sum 3 ,Factorize ํ limits expressible structures. LearnSPN can generate arbitrary-arity sum nodes and product decompositions; our grammar cannot. The 0.011-nat residual gap on NLTCS after convergence may be a grammar limitation rather than an optimization failure. Expanding the vocabulary (e.g., Sum 4 , Sum 5 ) is a straightforward extension but increases the action space and may require more exploration. Single dataset validation: Our full experimental results (UQ decomposition, ablation, sample efficiency analysis) are validated on a single dataset (NLTCS). The Plants results are preliminary. Rigorous claims about the frameworkโs generality require evaluation across the full DEBD benchmark suite (20 datasets), which we leave as immediate future work. 16 Value head on small circuits: The actor-critic value head (Phase E) provides no benefit on NLTCS because ํทโ3โ6 structural decisions is too few for meaningful temporal credit assignment. This is an important practical limitation: option-level REINFORCE alone is sufficient when circuits are small, but larger datasets with richer structures may require the value head for further efficiency gains. Leaf uncertainty and log-likelihood: Dirichlet leaf refinement showed marginal log- likelihood improvement (gap of 0.033 nats relative to Bernoulli leaves), suggesting that leaf evidential uncertainty is primarily a calibration feature rather than a likelihood-maximizing one. This is expected: the Dirichlet prior reduces point estimates toward 0.5 for low- evidence leaves, slightly sacrificing MLE performance for better uncertainty representation. 6.3 Future Work Immediate priorities include: (1) full DEBD benchmark evaluation across 20 datasets to establish statistical significance; (2) vocabulary expansion to assess whether grammar limitations explain the residual 0.011-nat gap on NLTCS; (3) convergence of Plants training and evaluation; (4) theoretical characterization of the amortization gap for autoregressive policies on context-free grammars. Longer-term directions include extending to continuous variable circuits (Normal-Inverse-Gamma leaves), first-order circuits, and integration of the SVGP-KAN perception module for the full neuro-symbolic pipeline. 7. Conclusion We have presented SymCircuit, a framework for learning probabilistic circuit structures via entropy-regularized reinforcement learning. The central theoretical result โ that the optimal MaxEnt RL policy is a tempered posterior ํ โ (ํฎ)โํ 0 (ํฎ)โ ํ(ํ|ํฎ) 1/(ํํผ) , recovering the exact Bayesian posterior at ํผ=1/ํ โ provides a principled foundation for interpreting the trained policy as an amortized variational approximation to Bayesian structure inference. The practical implementation combines SymFormerโs grammar- constrained generation with option-level REINFORCE (yielding 33ร sample efficiency over token-level alternatives on NLTCS, consistent with the derived โ ํ/ํท SNR improvement), hybrid Adam/Anemone optimization, and a three-layer uncertainty decomposition grounded in the multilinear polynomial structure of PC output functions. On NLTCS, SymCircuit closes 93% of the gap to the LearnSPN greedy baseline with dramatically fewer circuit evaluations. We hope this work encourages further investigation of learned generative policies as a principled alternative to greedy search in structured probabilistic model families. 17 References Amari, S. (1998). Natural gradient works efficiently in learning. Neural Computation, 10(2), 251โ276. Broadrick, O., Zhang, H., & Van den Broeck, G. (2024). Polynomial semantics of tractable probabilistic circuits. Proceedings of the 40th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 244:418โ429. Choi, Y., Vergari, A., & Van den Broeck, G. (2020). Probabilistic circuits: A unifying framework for tractable probabilistic models. UCLA Technical Report. http://starai.cs.ucla.edu/papers/ProbCirc20.pdf Dang, M., Vergari, A., & Van den Broeck, G. (2020). Strudel: Learning structured- decomposable probabilistic circuits. Proceedings of the 10th International Conference on Probabilistic Graphical Models (PGM), PMLR 138:137โ148. Darwiche, A. (2003). A differential approach to inference in Bayesian networks. Journal of the ACM, 50(3), 280โ305. Gens, R., & Domingos, P. (2013). Learning the structure of sum-product networks. Proceedings of the 30th International Conference on Machine Learning (ICML), PMLR 28(3):873โ880. Levine, S. (2018). Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv:1805.00909. Liu, A., & Van den Broeck, G. (2025). Rethinking probabilistic circuit parameter learning. arXiv:2505.19982 [Anemone]. Liu, A., Liu, X., Zhao, D., Niepert, M., Liang, Y., & Van den Broeck, G. (2025). Tractable transformers for flexible conditional generation. Proceedings of the 42nd International Conference on Machine Learning (ICML). arXiv:2502.07616 [Tracformer]. Park, Y., Lu, A. C., Huang, S.-C., Hu, Q., Ju, Y. S., & Osher, S. (2026). SymPlex: A structure- aware Transformer for symbolic PDE solving. arXiv:2602.03816 [SymPlex]. Rawlik, K., Toussaint, M., & Vijayakumar, S. (2012). On stochastic optimal control and reinforcement learning by approximate inference. Proceedings of Robotics: Science and Systems VIII (RSS), Sydney, Australia. DOI: 10.15607/RSS.2012.VIII.045. Ziebart, B. D., Maas, A. L., Bagnell, J. A., & Dey, A. K. (2008). Maximum entropy inverse reinforcement learning. Proceedings of the 23rd AAAI Conference on Artificial Intelligence, 1433โ1438.