[논문 리뷰] 강화된 조합 구조 생성: LLM이 램지 수를 풀다

TL;DR

램지 수(Ramsey Number)는 '완전한 무질서'가 불가능함을 보여주는 조합론의 핵심 문제로, 특정 구조가 반드시 나타나는 최소 크기를 찾는 것입니다. 구글 딥마인드의 본 연구는 AlphaEvolve라는 LLM(거대 언어 모델) 기반의 진화적 알고리즘을 제안하여, 5개의 램지 수에 대한 새로운 하한(lower bound)을 발견했습니다. 이 방법은 특정 문제에 맞춰진 단일 알고리즘을 설계하는 대신, 문제 해결을 위한 탐색 알고리즘 자체를 생성하고 진화시키는 메타-접근법을 사용합니다. 그 결과, R(3, 13)부터 R(4, 15)까지 총 5개의 새로운 기록을 세웠으며, 이는 조합론과 같은 난제 해결에 AI가 인간의 직관을 넘어 새로운 발견을 할 수 있음을 보여주는 중요한 사례입니다.

연구 배경 및 동기

램지 수란 무엇인가?

램지 수 $R(s, t)$ 는 조합론과 그래프 이론에서 매우 중요한 미해결 문제입니다. 간단한 예로 $R(3, 3)$ 을 생각해 봅시다.

파티 문제: 파티에 모인 사람들 중에는 서로 아는 3명 그룹 또는 서로 모르는 3명 그룹이 반드시 존재하려면 최소 몇 명이 있어야 할까요?

정답은 6명, 즉 $R(3, 3) = 6$ 입니다. 5명까지는 두 그룹이 모두 존재하지 않는 경우가 가능하지만, 6명이 모이면 둘 중 하나는 반드시 존재하게 됩니다.

이를 그래프 이론으로 표현하면, $N$ 개의 정점을 가진 완전 그래프( $K_N$ )의 모든 간선을 빨간색 또는 파란색으로 칠할 때, 빨간색 삼각형( $K_3$ ) 또는 파란색 삼각형( $K_3$ )이 반드시 존재하게 되는 최소 $N$ 을 찾는 것과 같습니다.

램지 수를 찾는 것은 $s$ 와 $t$ 가 조금만 커져도 극도로 어려워지는 NP-난해 문제입니다. 저명한 수학자 폴 에어디시는 "외계인이 $R(5, 5)$ 의 값을 알아내겠다고 위협한다면 모든 수학자를 동원해 계산하겠지만, $R(6, 6)$ 을 묻는다면 우리가 먼저 공격해야 할 것"이라고 말할 정도로 그 계산 복잡성은 상상을 초월합니다.

이러한 어려움 때문에, 정확한 값을 찾는 대신 하한(lower bound), 즉 "최소한 이 크기 이상의 그래프는 존재한다"를 증명하는 연구가 활발히 진행되어 왔습니다. 기존 연구는 주로 수작업이나 특정 휴리스틱에 기반한 알고리즘에 의존하여 탐색 공간이 제한적이었습니다. 본 연구는 이러한 한계를 극복하고자 LLM을 이용해 탐색 알고리즘 자체를 발견하는 새로운 접근법을 제안합니다.

연구	접근 방식	차별점
Paley 그래프 연구	대수적 구조 활용	특정 유형의 그래프에 국한됨
순환 그래프 연구	순환 구조 활용	제한된 탐색 공간
휴리스틱 탐색	사전 정의된 휴리스틱에 의존	인간의 직관을 넘어서기 어려움
본 논문 (AlphaEvolve)	LLM 기반 메타-알고리즘	다양한 탐색 알고리즘을 자동으로 생성 및 진화

핵심 기여

AlphaEvolve 메타-알고리즘 개발: LLM(PaLM 2)을 활용하여 탐색 알고리즘을 생성하고 진화시키는 시스템을 구축했습니다. 이는 문제 해결사를 만드는 해결사(solver for solver)입니다.
5개의 새로운 램지 수 하한 발견: $R(3, 13)$ , $R(3, 18)$ , $R(4, 13)$ , $R(4, 14)$ , $R(4, 15)$ 에 대한 기존 세계 기록을 경신했습니다.
탐색 알고리즘의 독립적 발견: 기존 연구에서 알고리즘이 공개되지 않은 경우에도, AlphaEvolve는 해당 기록을 달성하거나 뛰어넘는 새로운 알고리즘을 독립적으로 발견했습니다.
조합론 문제 해결의 새로운 패러다임 제시: 인간이 설계한 알고리즘의 한계를 넘어, AI가 복잡한 수학 문제에 대한 새로운 해결 전략을 창발할 수 있음을 입증했습니다.

제안 방법론: AlphaEvolve

AlphaEvolve는 LLM을 핵심 엔진으로 사용하는 진화적 탐색 알고리즘입니다. 특정 문제에 대한 해결책(그래프)을 직접 찾는 것이 아니라, 해결책을 찾는 프로그램(알고리즘)을 탐색합니다.

진화적 탐색 루프 (Evolutionary Search Loop)

AlphaEvolve는 다음과 같은 진화 과정을 반복하여 더 나은 탐색 프로그램을 찾아냅니다.

초기 집단 생성 (Initialization): C++로 작성된 몇 가지 기본적인 탐색 알고리즘으로 프로그램 집단(population)을 시작합니다.
평가 (Evaluation): 집단에 있는 각 프로그램을 실행하여 $(s, t)$ -free 그래프를 생성하고, 그 성능(그래프 크기 등)을 평가하여 점수를 매깁니다.
선택 (Selection): 높은 점수를 받은 프로그램을 '부모'로 선택합니다.
진화 (Evolution): LLM에게 부모 프로그램을 제시하고, 변형(mutation) 또는 교차(crossover)를 지시하는 프롬프트를 전달합니다.
- 변형 프롬프트 예시: "이 코드의 성능을 개선하기 위해 무작위성을 추가하여 새로운 자식 코드를 생성해 주세요."
- 교차 프롬프트 예시: "두 부모 코드의 장점을 결합하여 새로운 자식 코드를 생성해 주세요."
자식 프로그램 추가: LLM이 생성한 새로운 '자식' 프로그램을 컴파일하고 평가한 후, 집단에 추가합니다. 이 과정을 반복하며 집단 전체의 성능을 점진적으로 향상시킵니다.

프로그램 평가 및 목적 함수

생성된 프로그램의 성능은 그것이 찾아낸 그래프의 품질로 평가됩니다. 예를 들어, $R(3, s)$ 의 하한을 찾기 위한 목표는 삼각형( $K_3$ )이 없으면서 크기가 $s$ 인 독립 집합(independent set)도 없는 가장 큰 그래프를 찾는 것입니다.

목적 함수 (Objective Function) $E(G)$

생성된 프로그램 내부의 탐색 알고리즘(예: local search)은 그래프의 "결함"을 최소화하는 방향으로 작동합니다. 이 결함은 목적 함수 $E(G)$ 로 측정됩니다.

E(G) = w \cdot (\text{number of } K_3) + (1-w) \cdot f(\alpha(G), s)

$\text{number of } K_3$ : 그래프 $G$ 에 있는 삼각형의 개수입니다. 목표는 이를 0으로 만드는 것입니다.
$\alpha(G)$ : 그래프 $G$ 의 독립 집합(independent set)의 최대 크기입니다.
$f(\alpha(G), s)$ : 독립 집합의 크기가 목표치 $s$ 를 초과할 경우 페널티를 부과하는 함수입니다.
$w$ : 두 목표 사이의 균형을 맞추는 가중치입니다.

삼각형 개수 변화량( $\Delta K_3$ )

탐색 알고리즘이 효율적으로 작동하려면 그래프를 약간 수정했을 때 목적 함수가 어떻게 변하는지 빠르게 계산할 수 있어야 합니다. 두 정점 $u, v$ 사이에 간선을 추가(또는 제거)할 때, 새로 생기는 삼각형의 개수는 $u$ 와 $v$ 의 공통 이웃(common neighbors)의 수와 같습니다.

\Delta K_3 = |N(u) \cap N(v)|

이 간단한 계산을 통해 지역 탐색(local search)의 각 단계를 매우 빠르게 평가할 수 있습니다. AlphaEvolve가 생성한 많은 성공적인 프로그램들은 이 $\Delta K_3$ 휴리스틱을 효과적으로 활용했습니다.

실험 설정

목표: $R(3, s)$ 와 $R(4, s)$ 형태의 램지 수에 대한 기존 하한 기록 경신
LLM: 구글의 PaLM 2 모델 사용
초기 집단: 시뮬레이티드 어닐링, 유전 알고리즘 등 기본적인 휴리스틱 탐색 알고리즘 포함
평가 지표: 생성된 그래프가 제약 조건(e.g., (3, s)-free)을 만족하는지 여부와 그래프의 크기(정점의 수)

실험 결과 분석

AlphaEvolve는 총 5개의 램지 수에 대해 새로운 하한을 발견하여 기존 기록을 성공적으로 경신했습니다. 이는 수십 년간 정체되어 있던 문제에서 이룬 중요한 진전입니다.

램지 수	기존 하한	새로운 하한	향상률(%)
R(3, 13)	60	61	1.67%
R(3, 18)	99	100	1.01%
R(4, 13)	138	139	0.72%
R(4, 14)	147	148	0.68%
R(4, 15)	158	159	0.63%

램지 수 문제에서 하한을 단 1만큼 올리는 것도 매우 중요한 성과로 여겨집니다. 이는 이전까지 알려지지 않았던 더 복잡하고 큰 반례(counterexample) 그래프를 실제로 구성했음을 의미하기 때문입니다.

Ablation Study

연구진은 AlphaEvolve의 핵심 요소들이 성능에 미치는 영향을 분석하기 위해 Ablation Study를 수행했습니다. 그 결과, LLM을 이용한 진화적 탐색(변형, 교차)이 단순히 초기 프로그램 집단을 사용하거나 무작위로 코드를 수정하는 것보다 훨씬 우수한 성능을 보임을 확인했습니다. 이는 LLM이 코드의 의미를 이해하고 지능적으로 개선하는 능력이 결과에 결정적인 역할을 했음을 시사합니다.

비판적 평가

강점

혁신적인 접근법: 문제 자체를 푸는 대신 '문제 해결사'를 만드는 AlphaEvolve의 메타-러닝 접근 방식은 다양한 과학 및 공학 분야의 난제에 적용될 수 있는 새로운 패러다임을 제시합니다.
인간의 직관을 넘는 발견: LLM이 생성한 알고리즘들은 인간이 설계한 기존 방식과 다른 독창적인 전략을 포함하고 있었으며, 이는 AI가 인간의 지식 체계를 확장할 수 있는 잠재력을 보여줍니다.
실질적인 성과: 수십 년간 풀리지 않았던 램지 수 문제에서 5개의 새로운 기록을 세우며 방법론의 실효성을 명확히 입증했습니다.

한계점과 개선 방향

높은 계산 비용: LLM 호출과 수많은 자식 프로그램의 컴파일 및 평가는 막대한 계산 자원을 필요로 합니다. 알고리즘 생성 및 평가 과정을 최적화하여 비용 효율성을 높이는 연구가 필요합니다.
재현성 문제: LLM의 결과는 확률적(stochastic)이므로 동일한 입력에 대해서도 다른 코드를 생성할 수 있습니다. 특정 성공 사례를 재현하기는 어려울 수 있으나, 방법론 자체의 효과는 통계적으로 입증 가능합니다.

향후 연구 방향

다른 조합론 문제로의 확장: AlphaEvolve를 다른 NP-난해 문제(예: 부울 충족 가능성 문제(SAT), 외판원 문제(TSP))에 적용하여 새로운 알고리즘을 발견하는 연구를 진행할 수 있습니다.
과학적 발견으로의 응용: 조합론을 넘어 재료 과학, 신약 개발, 단백질 접힘 등 거대한 탐색 공간을 가진 다른 과학 분야의 문제 해결에 이 방법론을 적용할 수 있습니다.
LLM과의 상호작용 개선: 인간 전문가가 LLM과 상호작용하며 알고리즘을 함께 개발하는 협력적 프레임워크를 구축하여 탐색 효율을 높일 수 있습니다.

실무 적용 가이드

AlphaEvolve와 같은 접근법은 다음과 같은 특징을 가진 문제에 효과적일 수 있습니다.

거대한 탐색 공간: 해를 찾기 위한 공간이 매우 넓어 무작위 탐색이나 단순한 휴리스틱이 비효율적인 경우
알려진 최고 알고리즘이 없는 경우: 문제에 대한 효과적인 해결 알고리즘이 아직 발견되지 않았거나, 기존 알고리즘의 성능 개선이 정체된 경우
빠른 평가 함수: 생성된 해결책(또는 해결 알고리즘)의 품질을 신속하게 평가할 수 있는 환경이 필수적입니다.

이 방법론을 적용하기 위해서는 상당한 컴퓨팅 자원(LLM API, 분산 컴퓨팅 클러스터)과 프롬프트 엔지니어링에 대한 전문성이 필요합니다.

결론

본 연구는 LLM을 단순한 코드 생성 도구가 아닌, 복잡한 과학적 문제에 대한 새로운 해결 전략을 창발하는 '창의적 파트너'로 활용할 수 있음을 보여주었습니다. AlphaEvolve는 인간의 직관이 닿기 어려운 거대한 알고리즘 공간을 탐색하여, 수십 년간 난제로 여겨졌던 램지 수 문제의 새로운 지평을 열었습니다. 이는 AI가 수학, 과학, 공학 분야에서 인간의 지능을 보강하고 새로운 발견을 가속화할 수 있는 강력한 도구가 될 것임을 시사하는 중요한 이정표입니다.

참고 자료

논문 원본: Large language models can find new Ramsey number lower bounds (arXiv:2402.16458)
관련 자료: Google DeepMind Blog Post (유사한 방법론인 AlphaDev에 대한 블로그)

[논문 리뷰] Reinforced Generation of Combinatorial Structures: Ramsey Numbers