Diverse Construction of Sidon Sets with Generative Flow Networks

Motivation

• Known: GFlowNet은 terminal object를 reward에 비례하여 샘플링하도록 설계되어 다양한 고reward 후보를 생성하는 데 적합하며, AlphaTensor나 FunSearch 같은 최근 AI 시스템들이 조합적 구성 문제에서 강력한 발견을 보여준 바 있다. Sidon set은 additive combinatorics의 고전적 대상으로 M(n) = (1+o(1))√n이라는 극값 크기가 알려져 있다.
• Gap: 기존 조합 최적화 연구는 대체로 단일 최적해를 찾는 데 집중했으나, 많은 조합 문제는 구조적으로 상이한 다수의 최대 크기 해를 가지며, 이를 다양하게 발견하는 능력을 엄밀한 global constraint 하에서 평가할 벤치마크가 부재했다. 또한 Mn이 열거 불가능한 큰 n에서도 적용 가능한 방법론적 요소들이 충분히 연구되지 않았다.
• Why: Sidon set 구성은 sharp global constraint(모든 pairwise sum이 서로 달라야 함) 하에서 다수의 구조적으로 다른 최대해가 존재하는 깨끗한 벤치마크를 제공하며, 이는 GFlowNet 기반 diverse combinatorial construction 방법론의 유효성을 검증하고 향후 non-enumerable 영역으로 확장 가능한 AI-assisted mathematical construction 연구에 기반을 제공한다.
• Approach: Sidon set 구성을 ordered trajectory와 exact feasibility masking을 갖춘 sequential GFlowNet으로 정식화하고, number-theoretic transformer backbone, catalogue 기반 adherence loss, 그리고 작은 n에서 큰 n⋆로의 behavioural cloning transfer라는 세 가지 요소를 결합하여 연구한다.

Achievement

1. Inductive bias의 지배적 효과 입증: n∈{30,50}에서 number-theoretic transformer backbone이 MLP 및 vanilla-transformer baseline을 일관되게 능가함을 보여, 성능 향상의 주요 원인이 모델의 inductive bias임을 규명했다.
2. 대규모(n=80) scratch training의 실패 및 해법 제시: n=80에서 scratch GFlowNet 훈련이 붕괴함을 관찰했으나, BC로 초기화한 후 target-size adherence supervision을 적용한 fine-tuning이 M80의 약 0.82–0.83 total coverage를 달성함을 보였다.
3. Catalogue-free curriculum 전이 성능 확인: n=80의 catalogue를 전혀 사용하지 않은 30→...→80 curriculum learning만으로도 0.77의 coverage를 달성하여, 작은 n에서의 지식이 큰 n으로 전이 가능함을 입증했다.
4. 엄밀한 평가 프로토콜 설계: coverage fraction, normalized entropy, held-out discovery rate 등 diverse construction을 정량적으로 측정할 수 있는 metric들과 known-solution split(An/Hn) 프로토콜을 제시하여 memorization과 generalization을 구분할 수 있게 했다.

How

• 상태를 ordered partial Sidon set (x1,...,xk)로 표현하고, forward action은 STOP 또는 Sidon 성질을 보존하는 새로운 원소 삽입으로 정의
• exact feasibility masking을 적용하여 유효하지 않은 삽입에 대해 logit을 -∞로 설정, 모든 sampled prefix가 항상 유효한 partial Sidon set이 되도록 보장
• ordered trajectory와 결정론적 backward process(PB(s|s')=1)를 사용하여 permutation symmetry를 제거하고 별도의 backward policy 학습 불필요
• trajectory-balance(TB) objective를 사용하되 deterministic backward process 덕분에 log Zθ + Σlog PF,θ(at|st) - log R(S) 형태로 단순화
• 상태 표현으로 binary set membership 벡터(bset), binary pairwise sum 벡터(bsum), 그리고 구성 진행 상황을 나타내는 scalar/sequence feature를 결합
• number-theoretic transformer가 modular, Fourier, sum-conflict 구조를 인코딩
• 부분 catalogue(An/Hn split)에 대한 adherence loss를 추가하여 target n에서의 supervision 제공
• n < n⋆의 여러 크기에서 behavioural cloning으로 사전학습 후 bridged GFlowNet fine-tuning 수행

Originality

• Sidon set 구성을 diverse combinatorial construction의 벤치마크로 처음 정식화하고, 단일 최적해가 아닌 구조적으로 상이한 다수 최대해 발견을 GFlowNet으로 접근한 독창적 시도
• modular/Fourier/sum-conflict 구조를 인코딩하는 number-theoretic transformer backbone을 설계하여 도메인 특화 inductive bias를 도입
• 작은 n에서 큰 미지의 n⋆로의 behavioural cloning transfer와 target-size adherence loss를 결합한 하이브리드 학습 전략 제안
• Mn이 known일 때와 partial reference family Rn만 있을 때를 모두 다루는 An/Hn held-out split 평가 프로토콜을 제시하여 memorization과 generalization 구분 가능

Limitation & Further Study

• n=80에서의 headline coverage(~0.82-0.83)는 상당 부분 adherence pool(supervised catalogue)에 대한 memorization을 반영하며, held-out discovery rate는 0.12-0.21로 상당히 낮아 실제 일반화 능력은 제한적임
• 모든 정량적 실험이 Mn이 정확히 enumerable한 규모(n=30,50,80)에 국한되어 있으며, 논문에서 목표로 삼은 n∈{200,500} 같은 non-enumerable 규모로의 실제 확장은 미래 연구로 남겨짐
• 저자들 스스로도 이 연구를 "controlled preliminary step"이라 명시하며 autonomous mathematical discovery의 실증이 아님을 인정함
• 후속 연구로는 실제 non-enumerable n에서의 방법 검증, held-out discovery rate 개선을 위한 학습 전략 고도화, 그리고 다른 조합 구조(예: 다른 additive combinatorics 문제)로의 일반화 가능성 탐구가 필요함

Evaluation

총평: Sidon set을 diverse combinatorial construction의 정제된 벤치마크로 제시하고 number-theoretic inductive bias와 BC transfer의 효과를 체계적으로 검증한 견실한 연구이나, 핵심 성과가 supervised catalogue에 대한 강한 의존성을 가지고 있어 non-enumerable 영역으로의 실질적 확장은 아직 입증되지 않은 예비 단계의 작업이다.