Reinforced Generation of Combinatorial Structures: Ramsey Numbers

이 논문은 LLM 기반 코드 변이 에이전트인 'AlphaEvolve'를 활용하여 5 가지 고전적 램지 수의 하한을 개선하고, 기존에 알려진 모든 정확한 램지 수 하한을 재발견하며 다양한 경우에 최선의 하한을 달성했다는 점을 제시합니다.

핵심

램지 수 (Ramsey Numbers) 를 찾아낸 AI 의 여정: "완벽한 혼돈 속의 질서" 찾기

이 논문은 수학의 난제 중 하나인 **'램지 수 (Ramsey Numbers)'**를 해결하기 위해 인공지능 (AI) 이 어떻게 활약했는지를 설명합니다. 마치 거대한 퍼즐 조각을 맞춰 완벽한 그림을 완성하려는 시도와 비슷합니다.

1. 램지 수란 무엇일까요? (비유: "완벽한 파티")

상상해 보세요. 여러분이 초대받은 파티가 있습니다.

• 규칙 1: 파티에 모인 사람 중 **3 명이 서로 모두 아는 사이 (친구)**라면, 그 파티는 '3-친구'가 있는 파티입니다.
• 규칙 2: 반대로 **3 명이 서로 모두 모르는 사이 (낯선 사람)**라면, 그 파티는 '3-낯선 사람'이 있는 파티입니다.

램지 수는 "이 두 가지 규칙 중 하나라도 반드시 발생하게 하려면, 최소한 몇 명을 초대해야 할까?"를 묻는 숫자입니다.

• 예를 들어, 6 명만 초대하면 3 명이 서로 친구이거나, 3 명이 서로 낯선 사람인 경우 중 하나는 반드시 발생합니다. (이 경우 램지 수는 6 입니다.)

하지만 숫자가 커질수록 (예: 13 명이 서로 친구이거나 18 명이 서로 낯선 사람) 이 숫자를 정확히 맞추는 것은 우주만큼이나 어렵습니다. 수학자들은 "적어도 이 정도는 가능하다"는 **하한선 (Lower Bound)**을 찾기 위해 수천 년 동안 노력해 왔습니다.

2. 이 연구의 핵심: "코드를 진화시킨 AI"

기존의 수학자들은 이 문제를 풀기 위해 **매번 새로운 방법 (알고리즘)**을 직접 설계해야 했습니다. 마치 새로운 열쇠를 하나하나 직접 깎아보는 것과 같죠.

하지만 이 연구에서는 AlphaEvolve라는 AI 에이전트를 사용했습니다.

• 비유: 이 AI 는 "열쇠를 직접 깎는 사람"이 아니라, **"열쇠를 깎는 '기계'를 스스로 진화시키는 공장의 관리자"**입니다.
• AI 는 수많은 코드를 생성하고, 그중에서 더 좋은 결과를 내는 코드를 선택해 변형 (돌연변이) 시킵니다. 마치 자연선택처럼, 가장 잘 작동하는 '검색 프로그램'만 살아남게 하는 것입니다.

3. AI 가 무엇을 발견했나요? (새로운 기록 경신)

이 AI 는 기존에 알려진 5 가지 램지 수의 하한선을 모두 높였습니다. 즉, "이 정도 크기의 파티에서는 친구나 낯선 사람이 반드시 생긴다"는 기존 믿음을 깨고, **"아니, 그보다 더 많은 사람이어야만 그런 상황이 생긴다"**는 것을 증명했습니다.

• R(3, 13): 60 → 61 (1 명 더 필요해짐)
• R(3, 18): 99 → 100
• R(4, 13): 138 → 139
• R(4, 14): 147 → 148
• R(4, 15): 158 → 159

이것은 마치 "이 크기의 퍼즐은 100 조각으로 완성된다"고 믿었는데, AI 가 "아니요, 101 조각이어야만 완성됩니다!"라고 말하며 새로운 조각을 찾아낸 것과 같습니다.

4. AI 는 어떻게 그걸 찾았나요? (전략의 다양성)

흥미로운 점은 AI 가 모든 문제를 같은 방법으로 푼 것이 아니라는 것입니다. 마치 다양한 요리사가 각자 다른 재료를 이용해 최고의 요리를 만드는 것처럼, 각 문제마다 최적의 전략을 스스로 찾아냈습니다.

• 무작위 탐색: 어떤 문제는 그냥 무작위로 그래프를 만들어가며 시도하는 것이 좋았습니다.
• 수학적 구조 활용: 어떤 문제는 고대부터 알려진 '페일리 그래프 (Paley Graph)' 같은 수학적 구조를 시작점으로 삼아 진화시켰습니다.
• 순환 구조: 또 다른 문제는 원형으로 연결된 구조 (Circulant Graph) 를 기반으로 탐색했습니다.

AI 는 인간이 직접 설계한 알고리즘보다 훨씬 더 복잡하고, 때로는 인간이 상상하지 못한 새로운 조합을 찾아냈습니다. 심지어 기존에 "어떻게 이 숫자를 찾았는지"에 대한 설명이 없던 문제들까지, AI 가 그 과정을 다시 찾아내어 증명했습니다.

5. 결론: 왜 이것이 중요한가요?

이 연구는 인공지능이 단순히 문제를 푸는 것을 넘어, '문제를 푸는 방법 (알고리즘) 자체'를 발견할 수 있다는 것을 보여줍니다.

• 과거: 인간이 "이 문제를 풀기 위해 이 방법을 써라"라고 지시.
• 현재: 인간이 "이 문제를 풀어봐"라고 지시하고, AI 가 "아, 이 문제를 풀려면 이런 새로운 방법이 필요하구나!"라고 스스로 방법을 찾아냄.

이것은 수학, 물리학, 그리고 복잡한 과학 문제를 해결하는 방식에 혁명을 일으킬 수 있는 첫걸음입니다. AI 가 이제부터는 우리가 상상하지 못한 새로운 수학적 진보를 이끌어낼지도 모릅니다.

한 줄 요약:

"AI 가 스스로 코드를 진화시켜, 수백 년간 풀리지 않았던 '완벽한 혼돈 속의 질서' 찾기 게임 (램지 수) 의 기록을 깨뜨렸다."

기술 요약

강화된 조합 구조 생성: 램지 수 (Ramsey Numbers) 연구 논문 기술 요약

이 논문은 AlphaEvolve라는 대규모 언어 모델 (LLM) 기반 코드 변이 에이전트를 사용하여 고전적인 그래프 이론 문제인 **램지 수 (Ramsey Numbers)**의 하한 (lower bound) 을 개선한 연구 결과를 제시합니다. 저자들은 AlphaEvolve 를 단일 메타 알고리즘으로 활용하여, 기존에 수동으로 설계된 맞춤형 탐색 알고리즘들을 대체하거나 능가하는 새로운 탐색 알고리즘을 자동 생성하고, 이를 통해 5 개의 주요 램지 수 하한을 기록 갱신했습니다.

---

1. 문제 정의 (Problem)

• 램지 수 $R(r, s)$: $n$개의 정점을 가진 임의의 무방향 그래프가 항상 $r$개의 정점으로 이루어진 클릭 (clique) 이나 $s$개의 정점으로 이루어진 독립 집합 (independent set) 중 하나를 포함하도록 보장하는 최소 정점 수 $n$입니다.
• 목표: $R(r, s) \ge n+1$임을 증명하기 위해, $r$크기의 클릭도 $s$크기의 독립 집합도 포함하지 않는 $n$개의 정점을 가진 그래프 (위itness graph) 를 구성하는 것입니다.
• 현황: $r, s$가 작을 때 ($3 \le s \le 9$등) 는 정확한 값이 알려져 있지만, 그 외의 많은 경우에 하한과 상한 사이의 격차가 매우 큽니다. 기존 연구들은 특정 문제 쌍$(r, s)$마다 수동으로 설계된 전용 탐색 알고리즘을 사용하여 하한을 개선해 왔습니다.

2. 방법론 (Methodology)

이 연구의 핵심은 AlphaEvolve를 활용한 자동화된 알고리즘 발견 과정입니다.

• AlphaEvolve 메커니즘:

  • 진화 (Evolution): 탐색 알고리즘 (코드 스니펫) 의 집합 (Population) 을 유지합니다. 성능 기반 선택 함수로 부모 알고리즘을 고른 후, LLM 을 프롬프트하여 변이된 새로운 알고리즘 ($p_{new}$) 을 생성합니다.
  • 실행 및 평가: 생성된 알고리즘은 두 가지 그래프를 출력합니다.
    1. 주요 그래프 ($G_1$): 유효성 검증 (클릭/독립 집합 없음) 을 거친 그래프. 크기에 비례하여 점수를 받으며, 기존 최선 기록 (SoTA) 을 넘으면 가중치가 크게 부여됩니다.
    2. 잠재적 그래프 ($G_2$): 더 크지만 위반 사항 (violations) 이 있는 그래프. 위반 횟수가 기대값 대비 적을수록 보너스 점수를 받아 탐색이 한계까지 확장되도록 유도합니다.
  • 초기화 전략: 알고리즘은 빈 그래프에서 시작하여 점진적으로 확장하거나, 팔레이 (Paley) 그래프, 순환 (Circulant) 그래프, 대수적 구조 등 특정 초기화 전략을 통해 시작합니다.

• 탐색 알고리즘의 특징:

  • AlphaEvolve 는 각 $(r, s)$ 쌍에 대해 최적화된 고유한 탐색 알고리즘을 생성합니다.
  • 생성된 알고리즘들은 확률적 탐색 (Stochastic Search), 시뮬레이티드 어닐링 (Simulated Annealing), 타부 탐색 (Tabu Search), 유전 알고리즘 (Genetic Algorithm) 등을 조합하거나 변형하여 사용합니다.
  • 초기화 다양성:
    • 무작위/확률적 초기화 (Erdős-Rényi 그래프 등)
    • 대수적 시딩 (Paley 그래프, 3 차/2 차 잉여 그래프 등)
    • 순환/사이클릭 부트스트랩 (Sum-free 집합 기반)
    • 하이브리드/프랙탈/스펙트럴 시딩

3. 주요 기여 (Key Contributions)

1. 램지 수 하한 기록 갱신: 5 개의 중요한 램지 수 하한을 기존 기록에서 개선했습니다.
   • $R(3, 13)$: 60 $\to$ 61
   • $R(3, 18)$: 99 $\to$ 100
   • $R(4, 13)$: 138 $\to$ 139
   • $R(4, 14)$: 147 $\to$ 148
   • $R(4, 15)$: 158 $\to$ 159
2. 포괄적인 성과 달성: 알려진 정확한 값을 가진 모든 램지 수에 대해 하한을 재현 (recovered) 했으며, 다른 많은 경우에 기존 최선 기록 (SoTA) 을 달성했습니다.
3. 단일 메타 알고리즘의 효율성: 이전 연구들이 각 문제마다 별도의 알고리즘을 설계했던 것과 달리, AlphaEvolve 라는 하나의 메타 알고리즘으로 다양한 문제 쌍에 대한 최적의 탐색 알고리즘을 자동 생성했습니다.
4. 알고리즘의 다양성 발견: 생성된 알고리즘들은 단순히 기존 방법의 모방이 아니라, 특정 문제 구조에 맞는 대수적 초기화, 다중 휴리스틱 체이닝, 맞춤형 위반 계수 등 인간이 설계하지 않은 새로운 전략들을 포함하고 있음을 확인했습니다.

4. 결과 (Results)

• 성능 비교: Table 1 과 Table 2 에서 보듯, AlphaEvolve 는 $r, s \le 22$ 범위의 많은 셀에서 기존 최선 기록을 달성하거나 능가했습니다.
• 알고리즘 특성 분석:
  • 일부 문제 (예: $R(4, 13)$) 에서는 기존 연구 [ET15] 와 유사한 대수적 구조 (3 차 잉여, Paley 그래프) 로 초기화되었으나, 최적화 전략 (시뮬레이티드 어닐링 대신 진화한 휴리스틱 사용) 은 완전히 달랐습니다.
  • 다른 문제 (예: $R(4, 14)$) 에서는 기존 연구가 3 차 그래프로 시작했던 반면, AlphaEvolve 는 다양한 주기를 가진 순환 그래프 (Circulant graphs) 클래스로 시작하여 더 나은 결과를 얻었습니다.
  • $R(4, 10)$과 같은 경우, AlphaEvolve 는 순환 그래프 분포에서 샘플링하고 Tabu Search 를 통합한 완전히 새로운 탐색 전략을 발견했습니다.
• 코드 공개: 개선된 5 개의 램지 수에 대한 그래프 구성과 탐색 알고리즘 코드는 GitHub 에서 공개되었습니다.

5. 의의 및 중요성 (Significance)

• AI 를 통한 수학적 발견: 이 연구는 LLM 기반 에이전트가 단순히 지식을 요약하는 것을 넘어, 새로운 알고리즘을 설계하고 복잡한 조합 최적화 문제를 해결하는 능력을 입증했습니다.
• 휴리스틱 자동 발견: 기존에는 인간 연구자가 문제의 구조를 분석하여 맞춤형 휴리스틱을 설계해야 했지만, AlphaEvolve 는 이 과정을 자동화하여 인간이 생각하지 못했던 효율적인 탐색 전략을 찾아냈습니다.
• 확장 가능성: 이 접근법은 극한 조합론 (Extremal Combinatorics) 뿐만 아니라, 다른 수학적 구조 발견이나 NP-hard 문제 해결에도 적용 가능한 패러다임을 제시합니다.
• 상한 (Upper Bound) 문제와의 대비: 램지 수 하한 개선은 '반례 (위itness) 그래프'를 찾는 문제이므로 AlphaEvolve 와 같은 생성적 접근이 효과적이지만, 상한 개선 (해당 크기의 그래프가 존재하지 않음을 증명) 은 완전히 다른 접근법 (형식적 증명 등) 이 필요함을 지적하며 연구의 한계와 방향성을 명확히 했습니다.

결론적으로, 이 논문은 AI 가 수학의 최전선 문제 해결에 있어 단순한 보조 도구가 아닌, 창의적인 알고리즘 설계자로서 역할을 할 수 있음을 보여주는 획기적인 사례입니다.