Learning Randomized Reductions

Motivation

• Known: Random self-reducibility는 Goldwasser & Micali (1984)가 처음 정의했고, Blum et al. (1993)의 self-correcting program 연구를 통해 cryptography, average-case complexity, instance hiding, interactive proof system 등에 응용되어 왔다. 그러나 기존 RSR 발견은 x+r, x-r, x·r, x, r과 같은 고정된 query function 집합에 의존한 전문가의 수작업 유도에 의해서만 이루어졌다.
• Gap: 40년 넘게 RSR 발견이 전문가의 수동 유도에 의존해 실용적 활용이 제한되어 왔으며, 기존 방법은 소수의 고정된 query function으로만 제한되어 미분, 적분, 도메인 특화 변환이 필요한 복잡한 함수들의 RSR을 발견할 수 없었다.
• Why: RSR을 자동으로 발견할 수 있다면 self-correcting program, instance-hiding protocol, 암호학 및 복잡도 이론 응용을 실용적 규모로 확장할 수 있으며, sigmoid와 같이 신경망에서 널리 쓰이는 함수에 대한 새로운 RSR 발견은 이론적·실용적 가치가 크다.
• Approach: 무작위 상관 샘플링과 회귀(regression) 기반 가설 탐색을 결합하여 프로그램의 RSR 후보를 학습하고 이를 형식적으로 검증하는 Bitween 프레임워크를 제안하며, LLM 에이전트를 통해 고정된 query function 집합을 넘어서는 새로운 후보를 동적으로 제안하는 Agentic Bitween을 추가로 도입한다.

Achievement

1. RSR 학습의 이론적 정식화: correlated sampling 하에서의 sample complexity 분석을 포함한 RSR learning의 형식적 정의를 최초로 제시했다.
2. V-BITWEEN 구축: linear regression, genetic programming (GPLearn), symbolic regression (PySR), mixed-integer programming (Gurobi) 등 다중 backend를 통합한 회귀 기반 파이프라인을 구축했고, linear regression backend가 RSR-BENCH의 80개 함수 중 43개(54%)에 대해 가장 우수한 성능을 보였다.
3. sigmoid 함수의 최초 RSR 발견: 신경망에서 널리 쓰이는 sigmoid 함수에 대해 알려진 바 없던 새로운 randomized self-reduction 식(Equation 1)을 도출했다.
4. A-BITWEEN을 통한 발견 범위 확장: LLM 에이전트가 고정된 query function 집합을 넘어서는 새로운 query function을 제안하는 neuro-symbolic 접근을 통해 80개 함수 중 64개(80%)에서 RSR을 발견하여, 순수 신경망 기반 baseline 대비 발견율과 검증 정확도 모두에서 우수한 성능을 보였다.
5. RSR-BENCH 벤치마크 구축: 8개 카테고리(basic arithmetic, exponential, logarithmic, trigonometric, hyperbolic, inverse trigonometric, ML activation, special mathematical function)에 걸친 80개 과학·머신러닝 함수로 구성된 벤치마크를 self-testing 문헌과 functional-equation 이론에서 수집하여 구축했다.
6. 비스칼라 구조로의 일반화: 아키텍처 변경 없이 행렬(matrix), quaternion, octonion, Clifford algebra, Lie algebra 등 비스칼라 대수 구조로 프레임워크가 확장 가능함을 입증했다.

How

• 문제 정식화: RSR을 f(x)를 랜덤하게 상관된 점들에서의 f 평가값으로 표현하는 관계식으로 정의하고, correlated sampling 하에서의 sample complexity를 분석하는 이론적 틀을 제시.
• V-BITWEEN 파이프라인: 프로그램 Π(x)를 오라클로 삼아 x+r, x-r, x·r, x, r 등 고정된 query function에서 무작위 상관 샘플을 추출하고, linear regression을 포함한 여러 backend로 이 샘플들 간의 다항식적 관계(RSR 후보)를 추론한 뒤 형식적으로 검증.
• backend 비교: linear regression, GPLearn (genetic programming), PySR (symbolic regression), Gurobi (MILP)뿐 아니라 RAG-SR, ParFam, MetaSymNet 등 최신 symbolic regression 기법도 backend로 통합하여 비교, linear regression이 timeout 없이 가장 신뢰성 있게 동작함을 확인.
• A-BITWEEN 신경-기호 접근: LLM agent가 V-BITWEEN의 도구(query 생성, 회귀, 검증)를 활용하며 고정된 집합을 넘어선 새로운 query function을 제안하고, 이를 symbolic regression으로 검증하여 hallucination을 줄이는 방식으로 동작.
• 평가: RSR-BENCH의 80개 함수에 대해 각 backend/방법의 RSR 발견율, 검증 정확도, 실행 시간(runtime)을 비교 분석(Figure 2, 3, 4).

Originality

• RSR 발견 문제를 최초로 자동화 학습 문제로 형식화하고 sample complexity 이론을 결합한 점.
• 기존 40년간 고정되어 있던 x+r, x-r, x·r, x, r query function 집합을 LLM agent를 통해 동적으로 확장한 neuro-symbolic 접근(A-BITWEEN)을 새롭게 제시한 점.
• sigmoid 함수에 대한 세계 최초의 RSR을 발견하여 이론적 공백을 실제로 메운 점.
• 스칼라 함수를 넘어 matrix, quaternion, octonion, Clifford/Lie algebra와 같은 비스칼라 대수 구조로 아키텍처 변경 없이 일반화 가능함을 보인 점.

Limitation & Further Study

• RSR-BENCH가 80개 함수로 제한적이며, 20%(16개) 함수에 대해서는 A-BITWEEN조차 RSR을 발견하지 못해 여전히 완전한 자동화에는 한계가 있음.
• LLM agent가 제안하는 새로운 query function의 탐색 공간이 이론적으로 얼마나 완전한지, 혹은 특정 함수 클래스에 대한 발견 가능성의 보장이 부족함.
• symbolic regression 계열 backend(RAG-SR, ParFam, MetaSymNet)들이 안정적으로 동작하지 않았다고 언급되나, 이는 하이퍼파라미터 튜닝 부족일 가능성이 있어 backend 비교의 공정성에 대한 추가 검증이 필요함.
• 후속 연구로는 비스칼라 대수 구조에 대한 체계적 벤치마크 확장과, LLM 기반 query function 제안의 이론적 보장 강화, 그리고 검증 단계의 형식적 증명 자동화 확대가 필요해 보임.

Evaluation

총평: 40여 년간 전문가의 수작업에 의존해온 RSR 발견 문제를 이론적 정식화와 실용적 자동화 시스템(Vanilla/Agentic Bitween)으로 풀어낸 독창적이고 의미 있는 연구로, sigmoid의 새로운 RSR 발견과 비스칼라 구조로의 일반화 등 구체적 성과가 인상적이나 벤치마크 규모와 이론적 완전성 보장 측면에서 추가 연구 여지가 있다.