Motivated by auto-proof generation and Valiant's VP vs. VNP conjecture, we study the problem of discovering efficient arithmetic circuits to compute polynomials, using addition and multiplication gates. We formulate this problem as a single-player game, where an RL agent attempts to build the circuit within a fixed number of operations. We implement an AlphaZero-style training loop and compare two approaches: Proximal Policy Optimization with Monte Carlo Tree Search (PPO+MCTS) and Soft Actor-Critic (SAC). SAC achieves the highest success rates on two-variable targets, while PPO+MCTS scales to three variables and demonstrates steady improvement on harder instances. These results suggest that polynomial circuit synthesis is a compact, verifiable setting for studying self-improving search policies.
Figures & tables
Figure 1: Two arithmetic circuits for the polynomial x2+2xy+y2 .
Depth
C4-main
C4-pretrain
0
3
1
1
12
2
2
174
9
3
10,862
96
4
8,949
6,548
Table 1: Circuit-depth distribution for C4 boards.
Metric
C4-main (multivar)
C4-pretrain (single-var)
Nodes
20,000
6,656
Edges
31,746
20,966
Roots
3
1
Nodes with multiple optimal circuits
18,966 (94.83%)
6,592 (99.04%)
Max optimal circuits for one node
164
92
Max total circuits for one node
1,596
15,296
Table 2: C4 game-board structure and path-efficiency statistics. Optimal circuits are shortest root-to-node paths.
Variables
Task
Iter 50
Iter 100
Iter 150
Iter 200
Entropy
n=2
C=5 success (%)
29.40
26.50
27.40
34.90
3.28
C=6 success (%)
26.00
27.30
27.60
35.80
3.21
C=5 avg reward
2.47
2.22
2.34
3.08
—
C=6 avg reward
2.19
2.30
2.31
3.20
—
n=3
C=5 success (%)
17.70
20.90
26.50
27.30
3.65
C=6 success (%)
16.40
23.50
20.90
19.90
3.72
Table 3: PPO+MCTS evaluation on F5 (1000 episodes per checkpoint, near-greedy MCTS with τ=0.1 ). Success rates are percentages; entropy is the policy entropy at iter 200.
Variables
Task
Iter 50
Iter 100
Iter 150
Iter 200
Entropy
n=2
C=5 success (%)
48.30
55.60
53.20
57.80
1.85
C=6 success (%)
45.10
49.70
48.30
46.30
1.88
C=5 avg reward
3.41
4.14
3.90
4.37
—
C=6 avg reward
3.09
3.52
3.39
3.19
—
n=3
C=5 success (%)
5.40
5.00
6.20
10.70
2.23
C=6 success (%)
4.30
4.30
5.60
9.40
2.22
Table 4: SAC evaluation on F5 (1000 episodes per checkpoint, greedy policy). Success rates are percentages; entropy is the policy entropy at iter 200.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 2: PPO+MCTS training plots for complexity 5.
Figure 3: PPO+MCTS training plots for complexity 6.
Figure 4: Soft Actor-Critic Training Metrics Over Time (MA50) at Complexity level 1-4
Figure 5: Soft Actor-Critic Training Metrics Over Time (MA50) at Complexity 5
Finding minimal arithmetic circuits for polynomials over finite fields is a combinatorially hard problem central to algebraic complexity theory. We formulate it as a reinforcement learning problem in two directions, bottom-up and top-down. To address the challenge of a fast-growing combinatorial search space, we introduce FactorLibrary, which stores factorizable subexpressions that serve as reusable subgoals across training episodes. We trained a bottom-up agent with Gumbel-PPO-MCTS and two top-down agents with PPO+MCTS and SAC. The PPO+MCTS top-down agent exhibited the most stable performance, finding certified optimal circuits up to complexity 8 with a success rate of 91.8%.
Rohan Pandey, Michael Ruofan Zeng, Weikun K. Zhang +5
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.
Y. Sungtaek Ju
Department of Mechanical and Aerospace Engineering, University of California, Los Angeles
This paper presents ARCS (Autoregressive Circuit Synthesis), a system for amortized analog circuit generation. ARCS produces complete, SPICE-simulatable designs (topology and component values) in milliseconds rather than the minutes required by search-based methods. A hybrid pipeline combines two learned generators, a graph VAE and a flow-matching model, with SPICE-based ranking. It achieves 99.9% simulation validity (reward 6.43/8.0) across 32 topologies using only 8 SPICE evaluations, 40x fewer than genetic algorithms. For single-model inference, a topology-aware Graph Transformer with Best-of-3 candidate selection reaches 85% simulation validity in 97ms, over 600x faster than random search. The key technical contribution adapts Group Relative Policy Optimization (GRPO) to multi-topology circuit reinforcement learning. GRPO resolves a critical failure mode of REINFORCE, cross-topology reward distribution mismatch, through per-topology advantage normalization. This improves simulation validity by +9.6 percentage points over REINFORCE in only 500 RL steps (10x fewer). Grammar-constrained decoding additionally guarantees 100% structural validity by construction via topology-aware token masking.