arXiv:2606.25394v1 cs.LG

FactorLibrary: From Polynomials to Circuits via Recursive Subgoals

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

제출 2026-06-24

원문 초록

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

요약

유한체 위 다항식의 최소 산술 회로(arithmetic circuit) 탐색을 상향식·하향식 강화학습(RL) 문제로 정식화하고, 분해 가능한 부분식을 에피소드 간 재사용 하위목표로 저장하는 FactorLibrary를 제안해 급격히 커지는 조합 탐색 공간을 완화한다. PPO+MCTS 하향식 에이전트가 가장 안정적인 성능을 보였으며, 복잡도 8까지 인증된 최적 회로를 91.8% 성공률로 찾았다.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.25394v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.21609v2cs.AI공통 태그 Math, Combinatorial Optimization

HierFlow: Hierarchical Coupled Dual-Space Search for Automatic Agentic Workflow Generation

구조화된 워크플로우는 대규모 언어 모델(LLM)이 복잡한 문제를 해결할 수 있게 해주지만, 이를 자동으로 생성하는 것은 방대한 조합적 탐색 공간으로 인해 심각하게 저해되며, 이는 종종 유연하지 않고 자원을 많이 소모하는 오프라인 학습 의존성을 초래한다. 이를 해결하기 위해, 우리는 워크플로우 생성을 상위 토폴로지 층이 하위 작업 경계를 규정하고 하위 수준의 실행 결과가 토폴로지 자체를 능동적으로 재형성하는, 토폴로지와 실행이 맞물린 탐색 패러다임으로 개념화한다. 이 기반 위에서, 우리는 피드백 기반 토폴로지 조정과 하위 워크플로우 최적화를 위한 빠른 MCTS(Monte Carlo Tree Search) 기반 트리 탐색을 결합하여 에이전트형 워크플로우 설계를 자동화하는, 학습 불필요·테스트 시점 계층적 탐색 아키텍처인 HierFlow를 제안한다. HierFlow는 맥락적 필요에 따라 실행 수준 탐색을 선택적으로 트리거하는 지능형 게이팅 모듈을 통해 효율성을 극대화하며, 우리는 작업 간 결합 정도가 계층적 분할의 효과에 미치는 영향을 상세히 분석함으로써 이 메커니즘을 추가로 뒷받침한다. 질의응답, 수학적 추론, 코드 생성 벤치마크에 걸친 종합적인 테스트는 HierFlow가 강력한 베이스라인을 지속적으로 능가하며, 추가 학습 부담 없이 고품질 결과와 계산 효율성의 최적 균형을 제공함을 확인한다.

arXiv:2610.13461v1cs.AI공통 태그 Math, Combinatorial Optimization

SqueezeBench: 포화에 강건한 수학적 능력 평가

SqueezeBench: Saturation-Resilient Evaluation of Mathematical Capability

AI 시스템은 수학 분야에서 빠르게 발전하고 있지만, 이러한 발전을 측정하기는 어렵다. 이미 풀린 문제들로 구성된 벤치마크(benchmark)는 포화(saturate)되며, 미해결 문제들로 구성된 벤치마크에서는 각 문제가 최초로 단 한 번만 해결될 수 있다. 우리는 포화에 강건한 벤치마크인 SqueezeBench를 제시한다: 성공은 문제를 제거하는 대신 기준을 높인다. 각 문제는 작은 $n$에 대해서만 값이 알려진 정수 함수 $f(n)$을 고정하며, 벤치마크는 이에 대한 하한(lower) 기록과 상한(upper) 기록을 유지한다. 기록(record)은 $f$를 한정(bound)함을 기계 검증된 증명(machine-checked proof)으로 보인 계산 가능한 Lean 함수이다. 제출(submission)은 새로운 함수를 제안하고, 그 함수가 $f$를 한정하며, 모든 $n$에서 현재 기록보다 나쁘지 않고, 일부 $n$에서는 엄밀히 더 우수함을 증명한다. 채택되면 해당 제출은 다음 제출이 넘어서야 할 새로운 기록이 된다. 따라서 이 시스템은 한계값(bound)뿐 아니라 그 증명까지 선택하며, 단일 $n$에서의 기록을 개선할 수도 있고 성장률(growth rate)을 개선할 수도 있다. 모든 $n$에서 두 기록 사이의 간극은 인증된 한계값들이 $f(n)$을 결정하는 데에서 얼마나 떨어져 있는지를 보여준다. 모든 증명은 두 개의 독립적인 Lean 커널에 의해 검증되므로, 심판이 수학적 내용을 검토할 필요가 없다. 검증 과정은 또한 작은 $n$에서 전수 탐색(exhaustive search)으로 $f$를 계산하는 함수를 거부하며, 유지관리자(maintainer)는 제출자의 보고서만 읽고 더 큰 $n$에서 그러한 탐색이 있는지를 확인한다. 우리는 극단적 조합론(extremal combinatorics) 분야의 열 가지 문제를 스무 개의 증명된 초기 기록 및 승인 도구(admission tools)와 함께 공개한다. 기준선(baseline)으로서, 최신(frontier) 언어 모델(language model) 기반 에이전트(agent)는 기록당 최대 한 시간을 사용하여 82건의 제출을 승인받았고 모든 기록을 개선했으며, 이는 기존 발표된 문헌의 범위를 넘어서지는 않았다. 이후 두 개의 더 새로운 모델(model) 기반 에이전트들이 이 기록들로부터 시작하여 60건의 추가 제출을 승인받았고, 20개의 기록 중 19개를 다시 개선했다. 열 가지 문제 중 여덟 가지 문제에서는, 적어도 하나의 기록이 여전히 발표된 최선의 한계값(bound)에 비해 점근적으로(asymptotically) 뒤처져 있다.

arXiv:2609.27833v1cs.LG공통 태그 Deep Reinforcement Learning, Math

추론 문자열에서 부분 순서로: 몫 정책 최적화를 통한 검증기 인증 규칙 전이

From Reasoning Strings to Partial Orders: Verifier-Certified Rule Transport through Quotient Policy Optimization

많은 계산은 독립적인 하위 목표나 서로 겹치지 않는 상태 갱신이 교환 가능(commute)하기 때문에 여러 개의 유효한 실행 순서를 허용한다. 검증 가능한 보상을 사용하는 강화학습(reinforcement learning with verifiable rewards)은 보통 성공한 각 궤적(trace)을 서로 별개의 토큰 시퀀스로 취급하므로, 직렬화(serialization) 선택이 논리적 의존성으로 오인될 수 있다. 우리는 인접한 연산 쌍을 네이티브 검증기(native verifier)로 재실행하는 Verifier-Certified Rule Transport(VCRT)를 제안한다. 두 순서가 모두 수용되고 동일한 정규 상태(canonical state)에 도달하는 쌍은 교환 인증서(commutation certificate)를 제공하며, 거부되거나 상태가 바뀌는 역순은 반다이아몬드(anti-diamond)를 제공한다. VCRT는 반다이아몬드를 사용하여 진정한 선행 조건을 보존하고, 인증된 각 궤도(orbit)의 전체 확률 질량에 정책 크레딧을 할당한다. 또한 교환 후 일관성, 원본 유지(source retention), 정책 드리프트(policy drift)를 제약한다. 우리는 공유된 익명화 관계 그래프 인터페이스를 통해 ProofWriter, CLRS, Lean 전반에서 하나의 환경을 제외하는(leave-one-environment-out) 전이를 평가한다. 모든 학습과 체크포인트 결정은 홀드아웃 평가 이전에 고정되며, 홀드아웃 평가는 탐색이나 검증기 피드백 없이 항목당 하나의 그리디 궤적을 사용한다. VCRT는 가장 강력한 대응 기준선의 64.53%에 비해 77.60%의 매크로 통과율을 달성하였으며, 이는 13.06%p의 짝지은(paired) 향상이다(95% 부트스트랩 신뢰구간 [12.58, 13.54]). 이 향상의 대부분은 33.49%p를 기록한 Lean에서 나오며, ProofWriter와 CLRS는 평균 2.85%p 향상된다. 메커니즘 테스트는 일관되게 반다이아몬드 지도(supervision)를 지지하는 반면, No-Orbit은 전체 VCRT와 통계적으로 구별되지 않는다. 이 증거는 정확한 궤도 집계(exact orbit aggregation)가 전반적인 이점을 준다는 점을 입증하지 못한다.

arXiv:2609.28085v1cs.LG공통 태그 Deep Reinforcement Learning, Combinatorial Optimization

잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝

Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling

잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.

arXiv:2609.28385v1cs.LG공통 태그 Deep Reinforcement Learning, Math

교사를 언제 어디서 신뢰할 것인가: 엔트로피 보정 크레딧 할당을 통한 온-정책 증류와 GRPO의 통합

When and Where to Trust the Teacher: Unifying On-Policy Distillation and GRPO through Entropy-Calibrated Credit Assignment

검증 가능한 보상을 통한 강화학습(RLVR)은 최종 정답의 정합성을 통해 수학적 추론을 감독하지만 개별 토큰에 대한 안내는 거의 제공하지 못합니다. 온-정책(on-policy) 증류(OPD)는 학생이 생성한 응답에 대해 조밀한 피드백을 제공하지만, 교사의 선호도가 반드시 정합성을 반영하는 것은 아닙니다. 최근의 하이브리드 방식들은 OPD와 검증기 기반 이점(advantage)을 결합하거나 교사 비율을 활용해 작업 크레딧에 다시 가중치를 부여합니다. 그러나 교사의 안내는 검증기 기반 그룹 정규화 이후에 반영되며, 토큰 재가중치 부여가 각 응답에 할당된 전체 작업 크레딧을 반드시 보존하는 것은 아닙니다. 본 논문에서는 응답 및 토큰 수준 모두에서 단일 GRPO 스타일 업데이트 내에 검증기와 교사 신호를 통합하는 UECR-GRPO(Unified Entropy-Calibrated Credit Redistribution for GRPO)를 제안합니다. 경로-효용 통합(Path-Utility Unification, PUU)은 단일 KL 정규화 목적 함수에서 검증기 보상과 교사 대 앵커 경로 로그 비율을 결합합니다. 온-정책 구현에서는 길이 정규화된 교사 점수를 사용하며 그룹 정규화 및 PPO 클리핑 이전에 두 보상을 결합하여, 교사의 증거가 응답 순위 결정에 영향을 미칠 수 있도록 합니다. 그런 다음 엔트로피 보정 재분배(Entropy-Calibrated Redistribution, ECR)는 부호가 있는 교사-이전 정책 간 토큰 격차를 사용하여 검증기 기반 컴포넌트를 재분배합니다. 전체 어휘 교사 엔트로피는 불확실한 안내를 감쇠시키는 한편, 응답별 제로섬 투영은 클리핑 이전에 전체 작업 크레딧과 토큰별 부호를 보존합니다. 5개의 수학적 추론 벤치마크 전반에서 UECR-GRPO는 Qwen3-1.7B 및 Qwen3-4B 학생 모델을 통해 각각 17.21%와 65.09%의 평균 \(\mathrm{Avg@12}\) 정확도를 달성하여, 각 규모의 가장 강력한 기준선 모델보다 0.89%p 및 0.56%p 더 높은 성능을 보였습니다.

arXiv:2609.26704v1cs.CL공통 태그 Deep Reinforcement Learning, Math

반복 샘플링을 넘어서: LLM 추론을 위한 탐색 정책 학습

Beyond Repeated Sampling: Learning Search Policies for LLM Reasoning

대규모 언어 모델(LLM)은 테스트 시간 연산(test-time compute)을 더 많이 투입하여 고난도 추론 문제를 점진적으로 해결하고 있지만, 여전히 지배적인 전략은 단순 반복 샘플링(naive repeated sampling)에 머물러 있습니다. 즉, 다수의 독립적인 해결책을 생성하고 그중 하나가 정답이기를 기대하는 방식입니다. 이러한 샘플링은 국소적 디코딩 노이즈(local decoding noise)만을 통해 탐험(exploration)을 수행하므로, 진정으로 차별화된 아이디어보다는 거의 중복에 가까운 시도를 다수 생성하는 경향이 있습니다. 본 연구에서는 문제별 개념, 힌트 또는 전략을 먼저 샘플링한 다음 이에 기반하여 답변 생성을 조건화함으로써 시맨틱 수준에서 탐험을 유도할 수 있는지 질문을 던집니다. 이를 단일 궤적(single trajectory) 내에서 다양하고 많은 개념을 도출하는 단순하면서도 더욱 탐험적인 절차로 구체화하고, 반복 샘플링이 어려움을 겪는 고난도 문제에서 이를 평가합니다. 나아가 개념 생성을 학습 가능하도록 발전시킵니다. 즉, 강화학습(reinforcement learning)을 통해 소형 개념 생성 모델을 최적화하여, 이 모델이 생성한 개념이 동결된(frozen) 더 큰 답변 생성 모델의 다운스트림 성공을 극대화하도록 합니다. 고난도 수학 추론 문제에서, 학습된 개념 생성 모델은 동일한 답변 생성 연산량 할당 하에서 단순 반복 샘플링 대비 답변 생성 모델의 pass@k를 실질적으로 향상시키고, 튜닝되지 않은 훨씬 더 큰 모델에서 추출한 개념의 성능을 능가하며, 학습 과정에서 접하지 않은 다른 계열의 모델을 포함한 답변 생성 모델로도 전이됩니다. 따라서 소형 모델을 훨씬 더 큰 모델을 위한 효과적이고 재사용 가능한 탐색 정책(search policy)으로 학습시킬 수 있습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.