Agentic Neurosymbolic Collaboration for Mathematical Discovery: A Case Study in Combinatorial Design

이 논문은 대규모 언어 모델, 심볼릭 계산 도구, 인간의 전략적 지시가 결합된 신경심볼릭 협업 시스템을 통해 조합론 설계 이론에서 $n \equiv 1 \pmod{3}$인 라틴 사각형의 불균형에 대한 새로운 하한을 발견하고 Lean 4 로 공식적으로 검증한 사례를 제시합니다.

핵심

🕵️‍♂️ 이야기의 배경: "완벽한 균형"을 찾는 여정

연구자들은 **'라틴 방진 (Latin Square)'**이라는 특수한 숫자 배열을 연구하고 있었습니다.

• 비유: 마치 3x3, 4x4 크기의 스도쿠처럼, 각 행과 열에 숫자가 한 번씩만 나오게 배열하는 것입니다.
• 목표: 이 숫자들이 공간적으로 얼마나 '균형' 잡혀 있는지를 측정하는 **'불균형도 (Imbalance)'**를 가능한 한 0 에 가깝게 만드는 것입니다.
• 난제: 특히 $n$을 3 으로 나눴을 때 1 이 남는 경우 (예: 4, 7, 10 등) 에는 완벽한 균형 (불균형도 0) 을 만드는 것이 수학적으로 불가능하다는 것이 알려져 있었습니다. 그래서 연구자들은 "그렇다면 가장 작은 불균형은 도대체 얼마일까?"를 찾아야 했습니다.

---

🤝 세 명의 팀원: 어떻게 협력했나?

이 발견은 한 명의 천재가 혼자 한 것이 아니라, 세 가지 다른 '성격'을 가진 팀원들이 협력한 결과였습니다.

1. AI 에이전트 (대담한 탐험가)

• 역할: 방대한 숫자 데이터를 빠르게 훑어보고, 인간이 눈치채기 어려운 숨겨진 패턴을 찾아냅니다.
• 비유: 마치 수천 개의 퍼즐 조각을 순식간에 뒤적이며 "어? 이 조각들은 모두 짝수 모양이네?"라고 외치는 탐험가입니다.
• 성공: AI 는 수많은 숫자 데이터를 분석하다가 "아! 모든 거리가 짝수로만 나온다!"는 놀라운 사실을 발견했습니다. 이는 기존에没人이 눈치채지 못했던 핵심 단서였습니다.

2. 심볼릭 도구 (엄격한 검사관)

• 역할: AI 가 발견한 패턴을 엄격하게 증명하고, 모든 경우의 수를 계산하여 검증합니다.
• 비유: 수학의 법정을 운영하는 검사관입니다. AI 가 "이게 맞아요!"라고 말하면, 검사관은 "정말 모든 경우에 맞는지, 실수는 없는지"를 컴퓨터로 100% 정확하게 계산해 봅니다.
• 성공: AI 가 발견한 '짝수 패턴'이 수학적으로 옳은지 증명하고, 실제로 그 최소 불균형 값을 가진 숫자 배열을 컴퓨터로 찾아냈습니다.

3. 인간 연구자 (나침반을 든 지도자)

• 역할: 연구의 방향을 결정하고, 막다른 골목에서 방향을 틀어주는 역할을 합니다.
• 비유: 미로 속에서 길을 잃었을 때, "저기 벽이 보이니 이쪽은 안 돼. 다른 길로 가자"라고 말해주는 지도자입니다.
• 성공: 초기에는 "완벽한 균형 (불균형 0) 을 찾는 것"에 집착하다가, AI 와 컴퓨터가 아무리 해도 안 된다는 것을 보자, 인간 연구자가 **"그냥 0 을 찾으려 하지 말고, '가장 작은 양수'를 찾아보자"**라고 질문을 바꿨습니다. 이 한 마디의 방향 전환이 전체 발견의 열쇠였습니다.

---

🚀 발견의 과정: 5 단계의 여정

이 팀은 5 일 동안 15 번의 세션을 거치며 다음과 같은 과정을 겪었습니다.

1. 막다른 골목 (Dead End): 처음에는 "완벽한 균형"을 찾기 위해 수학적 공식을 뒤적였지만, AI 와 컴퓨터는 "이건 안 돼, 구조가 너무 복잡해"라고 결론 내렸습니다.
2. 방향 전환 (The Pivot): 인간 연구자가 "그럼 0 이 아닌 최소값을 찾아보자"라고 질문을 바꿨습니다. 이것이 승부수였습니다.
3. 패턴 발견 (The Insight): AI 가 새로운 질문으로 데이터를 다시 분석하자, "모든 거리가 짝수다!"라는 놀라운 사실을 찾아냈습니다.
4. 오류 수정 (The Review): AI 가 증명서를 작성하자, 다른 AI 들이 "여기서 실수했어! 이 공식은 모든 경우에 적용 안 돼"라고 지적했습니다. (여기서 AI 는 비평가로서는 훌륭했지만, 새로운 것을 창조하는 데는 약점이 있었습니다.)
5. 최종 증명 (The Result): 인간과 컴퓨터가 협력하여 "최소 불균형은 $4n(n-1)/9$다"라는 정리를 증명했고, 이를 컴퓨터로 검증했습니다.

---

💡 이 논문이 우리에게 주는 교훈

이 연구는 AI 가 수학자를 대체하는 것이 아니라, 인간과 AI 가 어떻게 협력해야 진정한 발견을 할 수 있는지를 보여줍니다.

• AI 는 '창의적 패턴 발견'과 '비판'에 강하지만, '새로운 가설을 세우는 것'이나 '전략적 판단'에는 약합니다.
• 인간은 막다른 길에서 방향을 틀어주는 '나침반' 역할이 가장 중요합니다.
• 컴퓨터 (심볼릭 도구) 는 AI 의 상상력을 '검증'하는 엄격한 기준이 되어줍니다.

결론적으로, 이 논문은 "AI 가 수학 문제를 푼다"는 것을 넘어, **"AI 가 인간의 직관과 컴퓨터의 계산력을 연결하여, 인간이 혼자서는 도달하지 못했던 새로운 수학의 문을 열었다"**는 것을 증명합니다. 마치 **탐험가 (AI), 검사관 (컴퓨터), 지도자 (인간)**가 함께 미로를 헤쳐나가 보물 (새로운 수학 정리) 을 찾아낸 이야기입니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem Setting)

• 연구 주제: 라틴 방진 (Latin Square) 의 불균형 (Imbalance) 에 대한 하한 (Lower Bound) 을 찾는 문제.
• 라틴 방진: $n \times n$ 크기의 배열로, 각 행과 열에 $n$ 개의 서로 다른 심볼이 정확히 한 번씩 나타나도록 구성됨. 실험 설계 등 다양한 분야에서 중요하게 사용됨.
• 불균형 (Imbalance, $I(L)$): 행 간의 거리 합을 기반으로 정의된 값.
  • $n \equiv 0, 2 \pmod 3$인 경우, 불균형이 0 인 '공간적으로 균형 잡힌 라틴 방진 (SBLS)'이 존재할 수 있음.
  • 핵심 문제: $n \equiv 1 \pmod 3$인 경우, 이상적인 거리가 정수가 아니므로 불균형이 0 이 될 수 없음. 이 경우 최소 달성 가능한 불균형 값이 무엇인지가 오랫동안 미해결 문제였음.
• 목표: $n \equiv 1 \pmod 3$인 경우에 대한 새로운 하한을 발견하고, 이를 달성하는 구조를 제시하는 것.

2. 방법론: 에이전트 신경 - 심볼릭 협업 프레임워크 (Methodology)

이 연구는 인간의 전략적 방향 설정, 대규모 언어 모델 (LLM) 기반 에이전트, 그리고 심볼릭 계산 도구를 통합한 신경 - 심볼릭 (Neurosymbolic) 협업 방식을 사용했습니다.

• 아키텍처 구성:

  1. 인간 연구자 (Human Researcher): 전략적 목표 설정, 연구 방향 전환 (Pivot), 결과의 품질 판단.
  2. AI 에이전트 (LLM Agent): Anthropic 의 Claude Opus 4.5를 기반으로 하며, 터미널, 파일 시스템, 외부 도구 접근 권한을 가짐.
     • 역할: 가설 생성, 숨겨진 패턴 발견, 증명 초안 작성, 코드 생성 및 실행.
  3. 심볼릭 도구 (Symbolic Tools):
     • SageMath: 대수적 분석 및 정밀 계산.
     • Rust Solver: 조합적 객체의 포괄적 열거 (Exhaustive Enumeration).
     • Simulated Annealing (Python): 확률적 최적화 및 근사 해 탐색.
  4. 지속적 메모리 시스템 (Persistent Memory): 세션 간 연속성을 보장하기 위한 2 단계 구조 (프로젝트 상태 파일, 주제별 지식 베이스). 모델 가중치 업데이트 없이 외부 파일로 지식을 축적.
  5. 다중 모델 검토 (Multi-model Deliberation): 여러 최첨단 LLM 을 병렬로 활용하여 증명의 오류를 비판하고 검증.

• 발견 과정 (5 단계):

  1. 대수적 역공학적 접근 (Dead End): 완벽한 순열 (Perfect Permutations) 을 대수적으로 찾으려 했으나 실패 (구조가 없는 '먼지'로 판명).
  2. 연구 방향 전환 (Research Pivot): 인간 연구자가 "불균형이 0 인 객체 찾기"에서 "최소 양의 불균형 특성 규명"으로 문제를 재정의함.
  3. 데이터를 통한 패리티 발견: 에이전트가 수치 데이터를 분석하여 모든 이동 상관관계 (shift correlation) 가 짝수라는 숨겨진 제약 조건 (Parity Constraint) 을 발견.
  4. 형식화 및 다중 모델 검토: 증명을 작성하는 과정에서 '순환 라틴 방진 (Circulant)'에만 국한된 오류와 $\sigma/\sigma^{-1}$ 불일치 오류를 다중 모델 검토를 통해 발견 및 수정.
  5. 계산적 확장: '거의 완벽한 순열 (Near-perfect Permutations)' 개념을 도입하고 시뮬레이션 어닐링을 통해 $n=52$까지 최적 해를 찾음.

3. 주요 기여 (Key Contributions)

1. 에이전트 신경 - 심볼릭 협업 프레임워크 제안:
   • 모델 가중치 업데이트 없이 세션 간 연속성을 유지하는 지속적 메모리 시스템과 다중 모델 검토를 포함한 새로운 수학적 발견 워크플로우 제시.
2. 조합 설계 이론에서의 수학적 발견:
   • 새로운 개념: 라틴 방진을 위한 '거의 완벽한 순열 (Near-perfect Permutations)' 개념 도입.
   • 정리 (Theorem): $n \equiv 1 \pmod 3$인 경우, 라틴 방진의 불균형 하한이 **$4n(n-1)/9$**임을 증명.
   • 실현 가능성: $n=4$부터 $n=52$까지 이 하한을 달성하는 순열의 존재를 계산적으로 확인.
3. 다중 모델 검토의 비대칭성 발견:
   • 최첨단 LLM 들 간의 토론은 **비판 (오류 발견)**에는 매우 신뢰할 수 있지만, **구축적 주장 (새로운 가설 제안)**에는 신뢰할 수 없음을 규명.
4. 프로세스 수준의 분석:
   • 신경 패턴 인식 (에이전트), 심볼릭 계산 (도구), 인간 전략적 판단의 각 구성 요소가 발견 과정에서 수행한 구체적인 인지적 기여를 세분화하여 분석.

4. 연구 결과 (Results)

• 주요 정리 (Theorem 3): $n \equiv 1 \pmod 3$인 모든 $n \times n$ 라틴 방진 $L$에 대해 불균형 $I(L)$은 다음을 만족함:
  $$I(L) \ge \frac{4n(n-1)}{9}$$
• 구성 (Construction): '거의 완벽한 순열 (Near-PP)'을 사용하여 위 하한을 정확히 달성하는 라틴 방진을 구성함.
  • 정의: 모든 이동 $\delta$에 대해 $f_\sigma(\delta) \in \{a, a+2\}$를 만족하는 순열 ($a = (n(n+1)-2)/3$).
• 실험 결과:
  • $n=4$부터 $n=52$까지의 모든 $n \equiv 1 \pmod 3$ 경우에 대해 최적 불균형 값을 달성하는 순열을 발견.
  • 이전 연구 (Ramaswamy and Szeider, 2023) 는 $n=10$에서도 최적에 도달하지 못했으나, 본 연구의 에이전트 접근법은 $n=52$까지 성공.
• 형식적 검증: Lean 4 증명 보조기를 사용하여 하한 정리를 형식적으로 검증함 (약 340 줄의 Lean 코드).

5. 의의 및 결론 (Significance)

• 진정한 수학적 발견의 가능성: AI 와 인간의 협업이 순수 수학 분야에서 새로운 정리와 개념을 창출할 수 있음을 실증함.
• 인간 - AI 협업의 본질:
  • AI 에이전트: 방대한 데이터에서 인간이 놓치기 쉬운 숨겨진 패턴 (패리티 제약) 을 발견하고 가설을 생성하는 데 탁월함.
  • 심볼릭 도구: 엄밀한 검증과 포괄적 탐색을 제공하여 AI 의 추측을 사실로 만듦.
  • 인간 연구자: 막다른 길 (Dead End) 에서 연구 질문을 근본적으로 재정의하는 **메타인지적 판단 (Strategic Pivot)**을 제공. 이는 현재 AI 에이전트 단독으로는 수행하기 어려운 영역임.
• 시스템 설계에 대한 시사점:
  • LLM 기반 에이전트는 '비평가 (Critic)'로서는 강력하지만 '건설자 (Constructor)'로서는 약점이 있음.
  • 신경 - 심볼릭 시스템은 인간의 전략적 지휘와 AI 의 패턴 인식 능력을 결합할 때 가장 효과적임.

이 논문은 단순한 자동화를 넘어, AI 가 인간의 직관과 결합하여 복잡한 수학적 문제를 해결하고 새로운 지식을 창출할 수 있는 구체적인 사례를 제시했다는 점에서 의의가 큽니다.