CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning

Weikun K. Zhang; Rohan Pandey; Bhaumik Mehta; Kaijie Jin; Naomi Morato; Archit Ganapule; Michael Ruofan Zeng; Jarod Alper

cs.LGMar 17, 2026

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning

Authors: Weikun K. Zhang, Rohan Pandey, Bhaumik Mehta, Kaijie Jin, Naomi Morato, Archit Ganapule, Michael Ruofan Zeng, Jarod Alper

Organizations: University of Washington

Abstract

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

Panel of Figure 1 — Figure 1: Two arithmetic circuits for the polynomial $x^{2}+2xy+y^{2}$ .

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

\mathbb{F}_{5}

(1000 episodes per checkpoint, near-greedy MCTS with

\tau=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

\mathbb{F}_{5}

(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

Panel of Figure 2 — Figure 2: PPO+MCTS training plots for complexity 5.

Panel of Figure 3 — 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

Program Synthesis

Program synthesis automatically constructs executable programs from examples, specifications, demonstrations, or natural-language descriptions.

See all 177 papers

FactorLibrary: From Polynomials to Circuits via Recursive Subgoals
Jun 24, 2026Rohan Pandey, Michael Ruofan Zeng, Weikun K. Zhang +5Circuit Discovery Reinforcement Learning
University of Washington, Seattle, WA, USA.
SymCircuit: Bayesian Structure Inference for Tractable Probabilistic Circuits via Entropy-Regularized Reinforcement Learning
Mar 20, 2026Y. Sungtaek JuProbabilistic Circuits Uncertainty Quantification
Department of Mechanical and Aerospace Engineering, University of California, Los Angeles
ARCS: Autoregressive Circuit Synthesis with Topology-Aware Graph Attention and Spec Conditioning
Mar 30, 2026Tushar Dhananjay PathakElectronic Design Automation Autoregressive Generation
New York University

Jun 24, 2026J/K move · Enter open · S save

FactorLibrary: From Polynomials to Circuits via Recursive Subgoals

Rohan Pandey, Michael Ruofan Zeng, Weikun K. Zhang, Kaijie Jin+4

University of Washington, Seattle, WA, USA.

Circuit Discovery Reinforcement Learning RL for Combinatorial Optimization Circuit Complexity

Open paper AskPDF arXiv

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\%

Abstract

Program Synthesis

Explore similar work

FactorLibrary: From Polynomials to Circuits via Recursive Subgoals

SymCircuit: Bayesian Structure Inference for Tractable Probabilistic Circuits via Entropy-Regularized Reinforcement Learning

ARCS: Autoregressive Circuit Synthesis with Topology-Aware Graph Attention and Spec Conditioning