FactorLibrary: From Polynomials to Circuits via Recursive Subgoals

📄 arXiv: 2606.25394v1 📥 PDF

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

分类: cs.LG, cs.AI

发布日期: 2026-06-24

备注: 14 pages, 8 figures, in 3rd AI for Math Workshop (ICML 2026)

💡 一句话要点

提出FactorLibrary以解决有限域多项式的最小算术电路问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 算术电路 有限域 强化学习 组合优化 因式分解 代数复杂性 机器学习

📋 核心要点

  1. 核心问题：寻找有限域上多项式的最小算术电路是一个组合难题，现有方法在搜索空间快速增长时面临挑战。
  2. 方法要点：提出FactorLibrary，通过存储可重用的因式分解子表达式，优化强化学习过程中的目标设定。
  3. 实验或效果：PPO+MCTS自顶向下代理在复杂度为8的电路中成功率达到91.8%，表现出最稳定的性能。

📝 摘要（中文）

寻找有限域上多项式的最小算术电路是代数复杂性理论中的一个组合难题。本文将其形式化为一个强化学习问题，采用自底向上和自顶向下的两种方法。为应对快速增长的组合搜索空间，提出了FactorLibrary，它存储可因式分解的子表达式，作为训练过程中可重用的子目标。通过Gumbel-PPO-MCTS训练自底向上的代理，并使用PPO+MCTS和SAC训练两个自顶向下的代理，其中PPO+MCTS代理表现最为稳定，成功率达到91.8%，能够找到复杂度为8的认证最优电路。

🔬 方法详解

问题定义：本文旨在解决有限域上多项式的最小算术电路问题。现有方法在面对快速增长的组合搜索空间时，效率较低，难以找到最优解。

核心思路：论文提出FactorLibrary，通过存储可因式分解的子表达式，作为训练过程中的可重用子目标，从而减少搜索空间并提高学习效率。

技术框架：整体架构包括自底向上的Gumbel-PPO-MCTS代理和两个自顶向下的代理（PPO+MCTS和SAC）。FactorLibrary作为核心模块，支持代理在训练中快速访问和利用因式分解的子表达式。

关键创新：最重要的创新在于FactorLibrary的引入，它通过存储和重用子目标，显著提高了搜索效率和学习稳定性，与传统方法相比，能够更有效地处理复杂的组合问题。

关键设计：在训练过程中，采用Gumbel-PPO-MCTS和PPO+MCTS等强化学习算法，设置了适当的超参数以优化学习过程，确保代理能够在复杂度为8的电路中找到认证最优解。具体的损失函数和网络结构设计未在摘要中详细说明，需参考原文。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，PPO+MCTS自顶向下代理在复杂度为8的电路中成功率达到91.8%，表现出最稳定的性能，相较于其他方法，显著提升了找到认证最优电路的能力。

🎯 应用场景

该研究的潜在应用领域包括密码学、编码理论和计算机代数等领域，能够为优化电路设计和提高计算效率提供新的思路。FactorLibrary的设计理念也可能在其他组合优化问题中得到应用，推动相关领域的研究进展。

📄 摘要（原文）

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