🤖 AI

ATLAS: Scaffold-Free Algorithm Synthesis by LLMs via Embedding-Guided Quality-Diversity Search

ATLAS는 구성 요소와 제어 흐름을 동적으로 재구조화하는 동시에, 광대한 설계 공간을 탐색하고 다양하며 성능이 뛰어난 솔루션을 발견하기 위해 오류 조건부 복구와 유사도 기반 아카이브를 채택함으로써, LLM이 조합 최적화를 위한 전체 알고리즘을 자율적으로 합성할 수 있도록 하는 스캐폴드-프리(scaffold-free) 방식의 임베딩 가이드형 다양성-질(quality-diversity) 프레임워크이다.

원저자: Danial Yazdani, Mohammad Nabi Omidvar, Yuan Sun, Maksud Ibrahimov, Xiaodong Li

게시일 2026-08-18

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Danial Yazdani, Mohammad Nabi Omidvar, Yuan Sun, Maksud Ibrahimov, Xiaodong Li

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

최적화는 현대 생활의 많은 부분을 움직이는 조용한 엔진입니다. 최적화는 연료를 아끼기 위해 배송 트럭의 경로를 설정하거나, 공장 기계의 작업을 제시간에 끝내도록 일정을 짜거나, 갈등 없이 작업자에게 교대 근무를 배정하는 것과 같이 복잡한 과업을 위한 가장 좋은 가능한 배치를 찾는 수학적 예술입니다. 수십 년 동안 이러한 문제를 해결하기 위해서는 인간 전문가가 탐색을 안내할 규칙과 논리를 직접 설계해야 했습니다. 이 전문가들은 고정된 뼈대와 같은 엄격한 프레임워크를 설계한 다음, 그 뼈대의 특정 부분들을 영리한 휴리스틱(heuristics), 즉 경험적인 규칙들로 채워 넣었습니다. 이 방식은 효과적이긴 했지만, 컴퓨터가 항상 인간이 그려놓은 상자 안에서만 작동하게 하여, 업무를 조직하는 근본적으로 다른 방식을 상상할 수 없게 만들었습니다.

최근 인공지능이 이러한 역학 관계를 바꾸기 시작했습니다. 에세이를 쓰거나 질문에 답할 수 있는 것과 동일한 기술인 대규모 언어 모델은 이러한 최적화 퍼즐을 풀기 위한 코드를 작성할 수도 있다는 것을 보여주었습니다. 초기 시도들은 이 모델들에게 퍼즐의 특정 부분, 예를 들어 다음 항목을 선택하는 구체적인 규칙만을 작성하도록 요청하고, 나머지 구조는 인간 설계자에게 남겨두었습니다. 하지만 새로운 사고방식은 만약 인공지능이 처음부터 전체 기계를 설계하도록 허용한다면, 인간 전문가가 결코 구상하지 못했을 솔루션을 발견할 수도 있다는 점을 시사합니다. 그러나 문제는 컴퓨터에게 완전한 자유를 주는 것이 위험하다는 것입니다. 가드레일이 없다면 컴퓨터는 쉽게 오류를 일으키거나, 규칙을 무시하거나, 무한 루프에 빠지는 코드를 생성할 수 있습니다. 이제 한 연구팀이 이 위험을 헤쳐 나갈 방법을 개발하여, 인공지능이 기초부터 완전하고 작동 가능한 알고리즘을 발명할 수 있게 했으며, 이를 통해 인간이 설계한 최고의 시스템에 필적하는 솔루션을 찾아냈습니다.

Danial Yazdani와 RMIT 대학교 및 기타 기관의 동료들이 이끄는 연구진은 ATLAS라고 불리는 시스템을 만들었습니다. 이름은 '아카이브 기반 3계층 알고리즘 합성(Archive-based Three-Layer Algorithm Synthesis)'의 약자이지만, 그 기능은 더 간단합니다. 그것은 인공지능이 미리 작성된 구조 없이 완전한 최적화 알고리즘을 자유롭게 구축할 수 있는 스캐폴드 프리(scaffold-free, 구조물 없는) 환경입니다. 전통적인 방식에서는 인간이 "여기서 시작하여, 이것을 확인하고, 그다음 저것을 한다"와 같은 고정된 단계인 뼈대를 제공하고 AI는 빈칸만을 채웁니다. ATLAS는 이 뼈대를 완전히 제거합니다. 인간은 "차량 용량을 준수하면서 이동 거리를 최소화하라"와 같은 문제 정의와, 컴퓨터가 데이터를 받고 답을 반환하는 방법에 대한 간단한 규칙만을 제공합니다. 내부 로직부터 제어 흐름에 이르기까지 모든 것은 AI의 책임입니다.

이러한 자유는 광대하고 혼란스러운 풍경을 만들어냅니다. 고정된 구조가 없으면 AI는 문제를 해결하기 위한 수백만 가지의 서로 다른 방법을 생성할 수 있지만, 이러한 시도 중 상당수는 실패할 것입니다. 코드가 충돌하거나, 출력이 잘못된 형식이거나, 문제의 규칙을 위반할 수도 있습니다. 이를 관리하기 위해 연구진은 엄격한 품질 관리 검사관 역할을 하는 시스템을 구축했습니다. AI가 새로운 알고리즘을 생성하면, 시스템은 이를 일련의 테스트 문제들에 실행해 봅니다. 만약 알고리즘이 충돌하거나 잘못된 결과를 생성하면, 시스템은 단순히 그것을 버리는 데 그치지 않습니다. 대신, 왜 실패했는지(메모리가 부족했는지, 시간이 초과되었는지, 혹은 불가능한 솔루션을 생성했는지 등)를 정확히 분석하여 그 구체적인 오류 메시지를 AI에게 다시 전달합니다. 그러면 AI는 이 피드백을 사용하여 코드를 재작성하고, 특정 결함을 수정하려고 시도합니다. 이러한 오류 조건부 복구(error-conditioned repair) 과정은 실패를 학습의 기회로 바꾸어, 다른 방식에서는 탐색을 종료시켰을 법한 실수로부터 시스템이 회복할 수 있게 합니다.

탐색이 하나의 평범한 솔루션에 갇히는 것을 방지하기 위해, ATLAS는 자연이 다양성을 보존하는 방식에서 영감을 얻은 전략을 사용합니다. 많은 최적화 탐색에서 시스템은 빠르게 하나의 "좋은" 답에 수렴하여 더 이상 다른 것을 찾지 않으며, 이로 인해 다른 영역에 숨겨진 훨씬 더 나은 솔루션을 놓칠 수 있습니다. ATLAS는 성공적인 알고리즘들을 의미론적 지도(semantic map)로 구성함으로써 이를 피합니다. 이는 코드의 의미를 수학적으로 표현하여 유사한 알고리즘들을 그룹화하고 서로 다른 그룹들을 분리하는 방식입니다. 시스템은 지금까지 찾아낸 최고의 알고리즘들을 다양한 컬렉션으로 유지하며, 이를 통해 솔루션 공간의 다른 영역을 계속 탐색하고 단일한 설계로 붕괴되지 않도록 보장합니다. 이를 통해 시스템은 서로 매우 다르게 보일지라도 성능이 동일한 여러 경쟁력 있는 접근 방식들을 동시에 보유할 수 있습니다.

연구진은 이 접근 방식을 배송 차량 경로 지정, 공장 작업 일정 관리, 시설 위치 할당이라는 네 가지 악명 높은 유형의 문제들에 대해 테스트했습니다. 그들은 ATLAS를 인간이 만든 프레임워크의 단일 구성 요소만을 설계하도록 허용한 방식 및 다양성 시스템 없이 전체 알고리즘을 설계하도록 한 버전과 비교했습니다. 결과는 명확했습니다. ATLAS는 인간이 설계한 뼈대에 의존하는 방식보다 일관되게 우수한 성과를 보였습니다. 또한 다양성 시스템 없이 전체 알고리즘 합성을 수행한 버전보다도 뛰어난 성과를 거두었으며, 이는 다양한 솔루션을 살아있는 상태로 유지하는 것이 최상의 결과를 찾는 데 결정적임을 입증했습니다. 더욱 놀랍게도, ATLAS가 발명한 알고리즘들은 전문가들에 의해 수년간 정교하게 다듬어진 강력한 인간 설계 알고리즘들과 경쟁할 만한 수준이었습니다. 어떤 경우에는 AI가 생성한 솔루션이 최고의 인간 노력과 통계적으로 구분이 불가능할 정도였고, 다른 경우에는 오히려 약간 더 나은 성능을 보이기도 했습니다.

가장 인상적인 발견 중 하나는 AI가 좋은 솔루션을 찾을 수 있다는 것뿐만 아니라, 매우 다양한 종류의 좋은 솔루션을 찾아냈다는 점입니다. 연구진이 최종 알고리즘 컬렉션을 조사했을 때, 그들은 풍부하고 다양한 구조들을 목격했습니다. 어떤 것들은 매 단계마다 최선의 국소적 선택을 하는 그리디(greedy) 접근 방식을 사용했습니다. 다른 것들은 국소적 함정에서 벗어나기 위해 냉각 과정을 시뮬레이션하거나 실수를 반복하지 않기 위해 메모리를 사용하는 것과 같은 다양한 전략을 결합한 복잡한 하이브리드 방식을 사용했습니다. 시스템은 단순히 문제를 해결하는 하나의 "최선의" 방법만을 찾은 것이 아니라, 구별되는 고성능 전략들의 포트폴리오를 발견한 것입니다. 이는 가능한 알고리즘의 공간이 이전에 생각했던 것보다 훨씬 더 풍부하며, 인간의 제약을 제거함으로써 인공지능이 이 공간을 효과적으로 탐색할 수 있음을 시사합니다.

이 연구는 자동화된 설계의 미래가 이러한 스캐폴드 프리 합성(scaffold-free synthesis)에 있을 수 있음을 시사합니다. AI가 솔루션의 로직에 대한 전적인 책임을 지도록 하고, 오류를 처리하고 다양성을 유지할 수 있는 견고한 시스템을 제공함으로써, 연구자들은 복잡한 문제를 해결하는 새로운 방법을 열 수 있습니다. 이 연구는 인간 전문가가 쓸모없어졌다고 주장하는 것이 아닙니다. 오히려 인간이 문제를 제공하고 AI에게 방법을 발명할 자유를 주었을 때, 그 결과가 얼마나 강력할 수 있는지를 보여줍니다. 연구진은 현재 시스템이 매우 효과적이지만, 특히 생성된 알고리즘의 수치적 설정을 미세 조정하는 데 있어 여전히 개선의 여지가 있다고 언급했습니다. 그러나 핵심적인 성과는 확고합니다. 즉, 전체적이고 작동 가능한 최적화 알고리즘을 자율적으로 합성하며, 완전한 자유라는 혼돈 속에서 질서와 탁월함을 찾아내는 시스템을 구축했다는 것입니다.

기술 요약: ATLAS – 임베딩 가이드 품질-다양성 탐색을 통한 LLM 기반 스캐폴드 프리(Scaffold-Free) 알고리즘 합성

문제 정의
현재의 대규모 언어 모델(LLM) 기반 자동 알고리즘 설계 방법들은 일반적으로 "스캐폴드(scaffolded)" 프레임워크 내에서 작동합니다. 이러한 접근 방식(예: FUNSEARCH, EOH, REEVO)에서는 LLM이 사용자 정의된 고정된 제어 흐름 내에서 작동하는 특정 휴리스틱 구성 요소(예: 우선순위 선택기 또는 점수 함수)를 합성합니다. 이러한 방식은 합성과 평가를 단순화하지만, 알고리즘 아키텍처, 구성 요소 인벤토리 및 상호작용 로직을 미리 지정함으로써 탐색 공간을 제한합니다. 결과적으로, 이러한 방법들은 새로운 구성의 구축 휴리스틱, 지역 탐색(local search), 메타휴리스틱을 결합한 하이브리드 파이프라인과 같은 대안적인 알고리즘 조직을 탐색할 수 없습니다.

전체 알고리즘 합성(Full-algorithm synthesis)은 이러한 제한을 제거하여 LLM이 완전한 엔드 투 엔드(end-to-end) 알고리즘을 설계할 수 있도록 합니다. 그러나 이러한 자유는 탐색 공간을 크게 확장시켜, 유효하지 않은 후보 생성, 실행 실패, 단일 설계 영역으로의 조기 수렴 등의 위험을 초래합니다. 또한, 결과로 나오는 알고리즘 지형은 다봉성(multimodality)을 띠는 경우가 많으며, 서로 다른 내부 조직을 가진 경쟁적인 알고리즘들이 표현 공간의 서로 다른 영역을 점유하게 됩니다. 기존의 전체 합성 방식은 이러한 이질적인 지형을 효과적으로 탐색하면서 다양성을 유지하는 데 어려움을 겪습니다.

방법론: ATLAS 프레임워크
ATLAS(Archive-based Three-Layer Algorithm Synthesis)는 임베딩 가이드 품질-다양성(quality-diversity) 탐색을 사용하여 전체 알고리즘 설계 공간을 탐색하도록 설계된 스캐폴드 프리 프레임워크입니다.

스캐폴드 프리 합성 (Scaffold-Free Synthesis):
- 입력: 시스템은 문제 명세(목적 함수, 제약 조건)와 최소한의 고정된 I/O 인터페이스(인스턴스 및 솔루션 형식)만을 받습니다.
- 출력: LLM은 솔루션 구축, 제약 조건 처리 및 내부 상태 관리를 담당하는 완전하고 실행 가능한 Python 알고리즘을 생성합니다. 사용자 지정 내부 구조나 구성 요소 인벤토리는 제공되지 않습니다.
- 평가: 외부 평가기는 후보를 실행하고, 솔루션의 타당성을 검증하며, 목적 함수 값을 독립적으로 재계산합니다. 평가기는 솔루션을 수정하거나 타당하게 만들지 않으며, 실패는 복구를 위한 별도의 증거로 취급됩니다.
임베딩 가이드 아카이브 관리 (Embedding-Guided Archive Management):
- 표현: 알고리즘은 (이름, 설명, 소스 코드)의 튜플로 표현되며, 사전 학습된 모델(mGTE-large-en-v1.5)을 사용하여 임베딩됩니다.
- 의미론적 레퍼토리 (Semantic Repertoire): ATLAS는 임베딩 공간에 조직된 유효한 알고리즘들의 유한한 아카이브를 유지합니다. 유사도 기반 중복 제거 및 용량 제한 프루닝(pruning)을 통해, 아카이브가 단일 최적점으로 붕괴되지 않고 임베딩 공간의 구별된 영역들에 걸쳐 커버리지를 보존하도록 보장합니다.
- 실패 복구 (Failure Recovery): 특화된 REPAIR 연산자는 분류된 실패 증거(예: 타임아웃, 제약 조건 위반, 인터페이스 오류)를 기반으로 후보를 재생성하며, 이를 에러 조건부 복구(error-conditioned recovery)라는 탐색 연산자로 활용합니다.
3계층 탐색 전략 (Three-Layer Search Strategy):
탐색과 활용의 균형을 맞추기 위해 ATLAS는 세 계층에 걸쳐 탐색 자원을 할당합니다.
- 계층 1 (엘리트 정교화 - Elite Refinement): 현재 최적의 알고리즘( $a^*$ )과 그와 임베딩상 가장 가까운 이웃들에 집중하며, 단일 참조 정교화 연산자(IMPROVE, TUNE, SIMPLIFY) 및 로컬 COMBINE을 사용합니다.
- 계층 2 (분산 정교화 - Distributed Refinement): 엘리트가 아닌 클러스터의 대표들에게도 전용 정교화 기회를 할당하여, 유망하지만 현재는 약한 영역들이 버려지는 것을 방지합니다.
- 계층 3 (교차 영역 합성 - Cross-Region Synthesis): 서로 다른 영역의 대표들(최적의 $a^*$ 포함)로부터 구성 요소와 상호작용을 결합하여 새로운 하이브리드 조직을 발견하는 교차 클러스터 합성을 수행합니다.
의미론적 연산자 (Semantic Operators):
프레임워크는 다음과 같은 LLM 기반 연산자 세트를 활용합니다.
- CREATE: 초기화를 위한 제로 레퍼런스 생성.
- IMPROVE, TUNE, SIMPLIFY: 단일 참조 정교화.
- COMBINE, DIVERGE: 하이브리드화를 위한 다중 참조 합성 및 발산.
- REPAIR: 에러 조건부 재생성.

주요 기여

스캐폴드 프리 전체 알고리즘 합성: ATLAS는 LLM이 사용자 지정 구조로부터 자유롭게 완전한 알고리즘 아티팩트를 제어하게 함으로써, 다양한 구성 요소 인벤토리와 제어 흐름을 발견할 수 있는 프레임워크를 도입합니다.
임베딩 가이드 품질-다양성 탐색: 알고리즘을 사전 학습된 임베딩 공간에 조직함으로써, ATLAS는 다봉성 탐색을 구현합니다. 이는 경쟁적인 알고리즘들을 서로 다른 영역에 보존하여 조기 수렴을 완화하고, 교차 영역 합성을 위한 의미론적으로 다양한 참조를 제공합니다.
계층적 3계층 탐색: 제안된 자원 할당 전략은 최적의 설계를 체계적으로 정교화하는 동시에, 다른 영역의 대표들을 성숙시키고 영역 간의 구성 요소를 결합합니다.
독립적 평가 및 실패 조건부 복구: 시스템은 실행, 인터페이스, 타당성 실패를 별도의 신호로 취급하여, 이를 패널티를 주는 대신 REPAIR 연산자로 라우팅함으로써, 초기에는 실패할 수 있는 복잡한 다단계 알고리즘을 포함하도록 탐색 공간을 확장합니다.
경험적 통찰: 통제된 연구를 통해 ATLAS를 통한 구성 요소 합성에서 전체 알고리즘 합성으로의 전환이 대부분의 설정에서 성능을 향상시킨다는 것을 입증하였으며, 향후 시스템을 위한 설계 지침을 제공합니다.

실험 결과
ATLAS는 네 가지 NP-난해 조합 최적화 벤치마크인 용량 제한 차량 경로 문제(CVRP), 시간 창이 있는 CVRP(CVRPTW), 플로우 숍 스케줄링(FSS), 이차 할당 문제(QAP)에 대해 평가되었습니다.

베이스라인과의 비교:
- ATLAS는 네 가지 기본 벤치마크 설정 모두에서 최신 구성 요소 합성 방법(EOH, REEVO, MCTS-AHD)보다 통계적으로 우수한 성능을 보였습니다.
- 또한, 동일한 전체 알고리즘 연산자를 사용하지만 임베딩 가이드 품질-다양성 아카이브 없이 표준 적합도 기반 선택에 의존하는 매칭된 전체 합성 베이스라인(EOH-FULL)보다도 우수한 성능을 보였습니다. 이는 ATLAS의 아카이브 조직의 기여도를 분리해 줍니다.
- ATLAS는 강력한 인간 설계 도메인 특화 알고리즘(예: PyVRP, IG-TB, BMA)과 대등한 수준을 유지했습니다. CVRPTW에서 ATLAS는 최고의 인간 설계 평균값과 일치했으며, CVRP에서는 PyVRP와 통계적으로 유의미한 차이를 보이지 않았습니다.
다봉성 유지 (Multimodal Retention):
- 단일 합성 실행 내에서, ATLAS는 서로 다른 임베딩 공간 영역으로부터 여러 경쟁적인 알고리즘을 유지했습니다. 코드 검사 결과, 이러한 알고리즘들은 주요 구축 방식이나 글로벌 탐색 백본(예: 리그렛 삽입, 세이빙스 기반 구축, 파괴 및 재구축 전략 간의 변화)에서 차이를 보였으며, 이는 프레즘의 구조적 다양성 유지 능력을 확인시켜 줍니다.
일반화 (Generalization):
- ATLAS는 확장된 문제 인스턴스(기본 크기의 절반 및 두 배)에 대해 견고한 성능을 입증하였으며, 모든 추가 설정에서 다른 LLM 기반 방법들보다 뛰어난 성능을 보였습니다.

의의 및 주장
본 논문은 임베딩 가이드 품질-다양성 탐색이 확장된 전체 알고리즘 설계 공간을 실질적으로 탐색 가능하게 만든다고 주장합니다. 사용자 지정 스캐폴드의 제약을 제거함으로써, ATLAS는 고정된 스캐폴드가 배제할 수 있는 대안적인 알고리즘 조직을 LLM이 탐색할 수 있게 합니다. 결과는 여러 경쟁적인 영역을 보존하고 영역 간 재조합을 가능하게 하는 것이 인간의 전문성에 필적하는 고성능의 구조적으로 다양한 하이브리드 알고리즘을 발견할 수 있게 한다는 점을 시사합니다. 저자들은 ATLAS가 경쟁적인 결과를 달와내지만, 전용 하이퍼파라미터 최적화를 통해 더 큰 이득을 얻을 수 있을 수 있다고 언급하며 이를 향후 연구 과제로 제시했습니다.

유사한 논문