🤖 AI

Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery

이 논문은 대조적 재가중치 부여(contrastive reweighting)를 통해 부모 선택을 안내하는 계층적 개념 모델을 학습함으로써, 비생산적인 개념 조합을 식별하고 회피하여 탐색 효율성과 해석 가능성을 향상시키는 방식인 대조적 개념 트리 탐색(Contrastive Concept-Tree Search, CCTS)을 소개하며, 이를 통해 LLM 지원 알고리즘 발견을 강화한다.

원저자: Timothee Leleu, Sudeera Gunathilaka, Federico Ghimenti, Surya Ganguli

게시일 2026-02-04

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Timothee Leleu, Sudeera Gunathilaka, Federico Ghimenti, Surya Ganguli

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 아주 재능 있지만 약간 혼란스러워하는 도제에게 원 안에 원을 채우거나 점들을 배치하여 아주 작은 삼각형이 생기지 않도록 하는 것과 같은 복잡한 퍼즐을 푸는 법을 가르치려 한다고 상상해 보십시오. 당신에게는 강력한 도구가 있습니다. 바로 대규모 언어 모델(LLM)인데, 이는 코드를 작성할 수 있는 매우 똑똑하고 박식한 로봇과 같습니다.

하지만 문제가 하나 있습니다. 당신이 로봇에게 새로운 해결책을 시도해 보라고 요청하면, 로봇은 왜 특정 해결책이 다른 것보다 더 나은지 이해하지 못한 채 그저 무작위로 추측하거나 이전의 시도를 약간 수정할 뿐입니다. 이는 마치 어떤 향신료가 요리의 맛을 더 좋게 만드는지 알지 못한 채, 단순히 재료를 무작위로 바꿔가며 레시피를 개선하라고 요구하는 것과 같습니다.

이 논문은 이를 해결하기 위해 **대조적 개념 트리 탐색(Contrastive Concept-Tree Search, CCTS)**이라는 새로운 방법을 소개합니다. 이 방법이 어떻게 작동하는지 쉬운 아이디어로 나누어 설명하겠습니다.

1. 문제점: 어둠 속에서의 탐색

현재 대부분의 시스템은 "피트니스 콘테스트(체력 검정 대회)"처럼 작동합니다. 코드를 여러 개 생성한 다음, 어떤 것이 가장 높은 점수를 받는지 확인하고, 그 승리한 코드만을 가지고 어떻게 하면 더 개선할 수 있을지 로봇에게 묻습니다.

결함: 이것은 현재 내가 서 있는 봉우리만을 바라보며 산을 오르는 것과 같습니다. 당신은 작은 언덕에 올라서 그것이 정상이라고 생각하며 갇혀버릴 수도 있고, 하나의 결과에 너무 집중한 나머지 더 나은 경로를 놓칠 수도 있습니다. 로봇은 코드 뒤에 숨겨가 있는 '개념'을 이해하는 것이 아니라, 단지 최종 점수만을 볼 뿐입니다.

2. 해결책: "개념 트리(Concept Tree)"

저자들은 단순히 최종 점수만을 보는 대신, 코드 안에 들어있는 **재료(개념)**를 보아야 한다는 것을 깨달았습니다.

비유: 코드가 단순한 텍스트 덩어리가 아니라, 아이디어의 '가계도'라고 상상해 보십시오.
- 최상단에는 "최적화(Optimization)"와 같은 광범위한 아이디어가 있습니다.
- 그 아래로 "경사 하강법(Gradient Descent)"과 같은 구체적인 아이디어들이 가지를 칩니다.
- 더 아래로 내려가면 "적응형 학습률(Adaptive Learning Rate)"과 같은 아주 세밀한 디테일들이 있습니다.
CCTS 방식은 로봇이 작성하는 모든 코드에 이러한 "개념 태그"를 붙이도록 강제합니다.

3. 마법의 기술: "좋은 것" vs "나쁜 것" 목록

이것이 이 새로운 방법의 핵심입니다. 시스템은 모든 시도 결과물을 두 개의 더미로 나눕니다.

"좋은" 더미: 점수가 잘 나온 시도들.
"나쁜" 더미: 점수가 낮게 나온 시도들.

그런 다음, "차이점 찾기" 게임을 합니다.

시스템은 다음과 같이 질문합니다: "좋은 더미에는 자주 등장하지만, 나쁜 더미에는 없는 개념은 무엇인가?" (이것이 유용한 개념입니다).
또한 다음과 같이 질문합니다: "나쁜 더미에는 자주 등장하지만, 좋은 더미에는 없는 개념은 무엇인가?" (이것이 함정 개념입니다).

4. 결과: 무엇을 피해야 하는지 배우기

연구 결과 놀라운 사실이 밝혀졌습니다. 시스템은 단순히 무엇을 해야 하는지를 배울 때뿐만 아니라, 무엇을 하지 말아야 하는지를 배울 때 성능이 가장 크게 향상되었습니다.

비유: 당신이 완벽한 케이크를 굽고자 한다고 상상해 보십시오. 기존 방식은 그냥 '괜찮은' 맛이 나는 케이크를 계속 구우면서 운 좋게 더 좋아지기를 바라는 것이었습니다. 새로운 방식(CCTS)은 "소금을 너무 많이 넣으면 케이크를 망친다. 베이킹 파우더를 넣는 것을 잊으면 실패한다"라는 것을 깨닫는 요리사와 같습니다.
이러한 "함정 개념"(소금과 같은 것)을 적극적으로 피함으로써, 탐색은 훨씬 더 효율적이 됩니다. 즉, 막다른 길에서 시간을 낭비하는 것을 멈추게 됩니다.

5. 테스트 방법

연구진은 몇 가지 어려운 수학 퍼즐(예: 상자 안에 최대한 많은 원을 채우는 "원 채우기(Circle Packing)" 문제)을 통해 이 방법을 테스트했습니다.

그들은 이 새로운 방법을 기존의 "피트니스 전용" 방식들과 비교했습니다.
결과: 새로운 방식이 더 나은 해결책을 더 빠르게 찾아냈습니다.
"합성(Synthetic)" 테스트: 이 결과가 사용된 특정 로봇의 우연한 효과가 아님을 증명하기 위해, 연구진은 정답을 이미 알고 있는 단순화된 버전의 "장난감 세계(toy world)"를 구축했습니다. 이 가상의 세계에서도 새로운 방식은 완벽하게 작동했으며, 이는 복잡한 로봇 없이도 이 논리가 성립함을 입증했습니다.

요약

요컨대, 이 논문은 AI에게 단순히 추측하는 것을 멈추고 게임의 규칙을 배우는 법을 가르칩니다. 아이디어를 트리 구조로 정리하고, 무엇이 작동하고 무엇이 실패하는지를 비교함으로써, 시스템은 나쁜 아이디어는 피하고 좋은 아이디어는 결합하는 법을 배웁니다. 이는 무작위적인 탐색을 가이드가 있는 투어로 바꾸어 놓으며, 새로운 알고리즘의 발견을 훨씬 더 빠르고 똑똑하게 만듭니다.

핵가치: 가장 큰 승리는 올바른 개념을 찾는 것뿐만 아니라, 잘못된 개념을 피하는 법을 배울 때 옵니다.

기술 요약: LLM 지원 알고리즘 발견을 위한 대조적 개념 트리 탐색 (Contrastive Concept-Tree Search)

문제 정의

대규모 언어 모델(LLM) 지원 알고리즘 발견은 LLM이 후보 프로그램을 제안하고 외부 평가자가 작업 피드백을 제공하는 반복적인 블랙박스 최적화 프로세스로 작동한다. 최근의 패러다임들(예: Funsearch, AlphaEvolve)은 조합론적 문제(Erdős 스타일의 문제 등)에 대한 솔루션을 재발견하거나 개선하는 데 성공했지만, 이들은 주로 적합도(fitness) 중심의 진화적 업데이트에 의존한다. 이러한 기존 시스템에서 부모 선택은 프로그램의 가공되지 않은 성능(적합도)에 의해 결정되며, 탐색은 성능 순으로 정렬된 프로그램의 계보 위에서 진행된다.

이러한 접근 방식의 결정적인 한계는 프로그램 공간이 약하게 구조화되어 있다는 점이다. LLM에 의해 제약되더라도, 생성된 알고리즘은 검색 알고리즘이 활용할 수 있는 명확한 국소성(locality), 매끄러운 변이 또는 구성적 구조를 결여하는 경우가 많다. 결과적으로, 가이드는 알고리즘의 어떤 의미론적 구성 요소가 실제로 유용한지에 대한 명시적이고 학습된 이해보다는, 가공되지 않은 적합도 신호와 LLM의 암묵적 사전 지식(prior)에 주로 의존하게 된다. 본 논문은 검색 효율성과 해석 가능성을 향상시키기 위해 LLM의 프로그램 공간에 대한 내부 표현을 어떻게 최대한 활용할 것인가라는 열린 질문을 다룬다.

방법론: 대조적 개념 트리 탐색 (CCTS)

저자들은 검색 가이드를 가공되지 않은 적합도에서 학습된 계층적 의미론적 개념 공간으로 전환하는 프레임워크인 **대조적 개념 트리 탐색(Contrastive Concept-Tree Search, CCTS)**을 소개한다. 핵심 가설은 알고리즘이 노드가 개념을 나타내고 엣지가 정제 또는 특수화를 인코딩하는 계층 구조로 조직된 기저의 의미론적 개념 공간에 의해 설명될 수 있다는 것이다.

1. 개념 표현 및 트리 구축

특징 추출 (Feature Extraction): 각 후보 프로그램 $x$ 는 LLM에게 관련 개념 목록을 생성하도록 유도함으로써 추출된 의미론적 특징 표현 $b = \Phi(x)$ 로 매핑된다.
계층 구조 (Hierarchical Structure): 이러한 개념들은 루트가 있는 개념 트리(rooted concept tree)로 조직된다. 개념 벡터 $b$ 는 활성화가 조상 폐쇄적(ancestor-closed)인 지표 벡터이다(즉, 자식 개념을 활성화하면 모든 조상 개념도 활성화됨). 이 트리는 탐색 과정에서 새로운 개념이 발견됨에 따라 동적으로 성장한다.

2. 개념 효용의 대조적 학습

CCTS는 단순히 프로그램의 적합도 점치에 기반하여 부모를 선택하는 대신, 어떤 개념이 성능과 경험적으로 연관되어 있는지 대조적 접근 방식을 통해 학습한다.

분할 (Partitioning): 평가된 프로그램의 아카이브를 성능 임계값 $\tau_t$ 를 기준으로 "좋은" ( $y_i \ge \tau_t$ ) 집합과 "나쁜" ( $y_i < \tau_t$ ) 집합으로 분할한다.
모델 피팅 (Model Fitting): 각각의 좋은 집합과 나쁜 집합의 특징 분포에 대해 두 가지 확률 모델 $\hat{p}_{\eta^+}(b)$ 와 $\hat{p}_{\eta^-}(b)$ 를 피팅한다. 저자들은 계층적 베르누이 모델을 사용하는 트리 구조 파젠 추정기(Tree-structured Parzen Estimator, TPE) 방식의 접근법을 활용한다. 이 모델은 계층 구조 내의 부모를 조건으로 하는 특징들의 조건부 독립성을 가정한다.
우도비 점수 (Likelihood Ratio Scoring): 각 프로그램에 대해 다음과 같은 우도비 점수(로그-개념 효용)가 계산된다:
$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$
이 점수는 특정 개념 집합이 고성능 솔루션과 저성능 솔루션을 얼마나 강력하게 구별하는지를 정량화한다.

3. 부모 선택 및 탐색 역학

편향된 샘플링 (Biased Sampling): 부모는 아카이브에서 우도비 점수에 비례하는 확률로 선택된다. 이는 검색을 성능 개선과 경험적으로 연관된 개념 조합을 포함하는 프로그램 쪽으로 편향시킨다.
탐색 메커니즘 (Exploration Mechanism): 조기 수렴을 방방지하고 새로운 개념의 발견을 장려하기 위해, CCTS는 경량화된 탐색 메커니즘을 포함한다. 여기에는 다음이 포함된다:
- 베타 사전 확률 (Beta Priors): 새로운 개념이 절대 0의 확률을 갖지 않도록 카운트를 스무딩(smoothing)한다.
- 참신성 편향 (Novelty Bias): 자주 시도된 개념의 가중치를 낮추어 아직 충분히 탐색되지 않은 영역을 선호하도록 한다.
- 혼합 전략 (Mixture Strategy): 착취(learned contrastive model 기반)와 탐색(novelty 기반)의 혼합 전략이 자식 생성을 위한 LLM 프롬프트에 주입할 개념을 선택하도록 가이드한다.

주요 기여

명시적 의미론적 구조: 본 논문은 표준 진화 알고리즘에서 사용되는 구조화되지 않은 프로그램 공간을 넘어, 계층적 개념 트리를 학습함으로써 알고리즘 공간의 잠재적 구조를 명시적으로 만드는 것을 제안한다.
대조적 가이드: 단순히 어떤 프로그램이 가장 높은 성능을 보이는지 추적하는 것이 아니라, 어떤 개념을 우선시하고 결정적으로 어떤 개념을 피해야 하는지를 학습하는 대조적 통계 프레임워크를 도입한다.
해석 가능성: 이 방법은 탐색 과정 중에 탐구된 의미론적 구조에 대한 통찰을 제공하는, 작업 특화된 해석 가능한 개념 트리를 생성한다.
합성 검증: 저자들은 "교사(teacher)" 개념 트리와 정답 효용(ground-truth utilities)이 존재하는 통제된 합성 환경을 구축하였다. 이를 통해 CCTS가 기저의 의미론적 구조를 복구할 수 있으며, 관찰된 탐색 역학이 특정 LLM의 아티팩트가 아닌 개념 효용의 학습에 의해 구동됨을 검증할 수 있었다.

실험 결과

저자들은 원형 패킹(circle packing), 산술적 카케야 추측(Arithmetic Kakeya conjecture), 하일브론 삼각형 문제(Heilbronn's triangle problem), 정사각형-내-정사각형(squares-in-square) 문제 등 다양한 오픈 Erdős 유형의 조합론적 문제 벤치마크에서 CCTS를 평가하였다.

성능 향상: CCTS는 여러 작업에 걸쳐 Baseline 전략(Uniform, Greedy, $k$ -elite selection)보다 일관되게 높은 점수와 빠른 개선 속도를 달연했다.
개선 메커니즘: 분석 결과, 성능 향상은 주로 어떤 개념을 피해야 하는지를 학습하는 데서 기인한다는 것이 밝혀졌다. 성공적인 실행은 실패한 실행과 유사한 고효용 개념 세트를 식별했지만, 저효용(해로운) 개념을 억제하는 능력이 현저히 뛰어났다. 이는 CCTS가 LLM의 초기 사전 지식에 의한 오도된 상관관계로 인한 생산적이지 않은 탐색을 줄임으로써 검색을 안정화한다는 것을 시사한다.
합성 검증: 합성 환경에서 학습된 개념 효용은 정답 교사 효용과 강한 상관관계( $r=0.94$ )를 보였으며, 이는 이 방법이 의미 있는 의미론적 표현을 효과적으로 복구함을 확인시켜 준다.
구조 의존성: 탐색 전략은 (예: 분기 비율) 기저의 개념 트리 구조에 따라 최적의 탐색과 착취 사이의 균형이 달라진다는 것이 발견되었으며, 이는 탐색 전략이 문제 공간의 토폴로지에 맞게 조정되어야 함을 시사한다.

의의 및 주장

본 논문은 현재의 LLM 지원 알고리즘 발견이 근본적인 불일치를 겪고 있다고 주장한다: 즉, 높은 점수를 받는 알고리즘이 반드시 강력한 자손을 생성하는 것은 아닌데, 이는 약하게 구조화된 공간에서 적합도가 진화 가능성(evolvability)의 좋은 대리자가 아니기 때문이다. CCTS는 선택의 기준을 가공되지 않은 적합도에서 개선에 대한 의미론적 증거로 전환함으로써, 거리, 재조합 및 검색 방향이 유의미한 개념 공간에서 검색이 작동할 수 있게 한다.

저자들은 이 연구를 더 신뢰할 수 있고 확장 가능한 알고리즘 발견을 향한 방법론적 진보로 위치시킨다. 그들은 현재의 결과가 특정 벤치마크에 대한 상대적 개선을 보여주지만, 주요 기여는 명시적이고 인간 친화적인 의미론적 개념 구조가 어떻게 자동화된 발견을 더 투명하고, 제어 가능하며, 효율적으로 만들 수 있는지를 입증한 데 있음을 강조한다. 이 연구는 향후 시스템이 블랙박스 적합도 신호에만 의존하기보다 잠재적인 의미론적 계층 구조를 학습하고 활용하는 데 집중해야 함을 시사한다.