논문리뷰

LLM : 논문리뷰 : Evolving Deeper LLM Thinking

AI바라기 2025. 1. 21. 13:28

논문 정리 노트: Evolving Deeper LLM Thinking

Purpose of the Paper

기존의 Large Language Models (LLMs)는 추론(reasoning) 성능을 향상시키기 위해 self-refinement나 tree search와 같은 방법을 사용해왔습니다. 하지만 이러한 방법들은 개별 추론 단계에 대한 평가가 필요하거나, underlying inference problem을 formalize해야 하는 한계가 있었습니다. 본 논문은 solution evaluator가 존재할 때, underlying inference problem을 formalize하지 않고도 LLM의 inference time compute를 확장하여 복잡한 문제 해결 능력을 향상시키는 새로운 evolutionary search 전략, Mind Evolution을 제안하고자 합니다. 특히, natural language planning task에서 solution evaluator를 활용하여 LLM이 "더 깊이 생각"하도록 유도하고, Best-of-N 및 Sequential Revision과 같은 기존 inference 전략을 능가하는 성능을 달성하는 것이 목표입니다.

Key Contributions

  • Mind Evolution: LLM을 사용하여 candidate solution을 생성, 재조합 및 개선하는, 자연어 공간에서 작동하는 novel evolutionary search strategy를 제안합니다.
  • Formalization 불필요: solution evaluator만 있으면 underlying inference problem을 formalize할 필요 없이 복잡한 문제에 적용 가능합니다.
  • 자연어 플래닝 성능 향상: TravelPlanner 및 Natural Plan 벤치마크에서 Best-of-N 및 Sequential Revision과 같은 기존 inference 전략 대비 significantly better performance를 달성했습니다.
  • 새로운 벤치마크 StegPoet 제안: formulate하기 어렵지만 programmatic verification이 가능한 새로운 벤치마크를 제안하여 Mind Evolution의 적용 가능성을 확장했습니다.
  • 심층 분석: Mind Evolution의 성능에 영향을 미치는 다양한 요소(e.g., critic, textual feedback, island model)를 분석하고, 각 요소의 중요성을 ablation study를 통해 검증했습니다.

Novelty

  • LLM을 활용한 evolutionary search: LLM의 language understanding 및 generation 능력을 활용하여 자연어 공간에서 evolutionary search를 수행하는 최초의 연구입니다.
  • Global refinement: 개별 추론 단계를 평가하는 대신, 완전한 solution에 대한 global refinement를 수행하여 search efficiency를 향상시켰습니다.
  • 광범위한 적용 가능성: solution evaluator만 있으면 formalization 없이 다양한 문제에 적용할 수 있는 general framework를 제공합니다.
  • 자연어 플래닝에 대한 새로운 접근 방식: 기존의 formal solver 기반 접근 방식과 달리, 자연어 공간에서 직접 solution을 최적화하여 LLM의 능력을 최대한 활용합니다.

Experimental Highlights

  • TravelPlanner 및 Natural Plan 벤치마크:
    • Mind Evolution은 Gemini 1.5 Flash를 사용하여 TravelPlanner에서 95.6%, Natural Plan의 Meeting Planning에서 85.0%의 success rate를 달성했습니다.
    • 두 단계 접근 방식(Gemini 1.5 Pro 활용)을 통해 TravelPlanner에서 100%, Natural Plan의 Trip Planning에서 99.6%, Meeting Planning에서 98.4%의 success rate를 달성했습니다.
    • Best-of-N, Sequential-Revision+ 등 baseline 대비 significantly better performance를 보였습니다.
  • StegPoet 벤치마크:
    • Mind Evolution은 Gemini 1.5 Pro를 사용하여 87%의 success rate를 달성했습니다.
  • Ablation Study:
    • Critic, textual feedback, island model, LLM-based island reset 등 Mind Evolution의 핵심 구성 요소의 중요성을 검증했습니다.
    • Critic과 textual feedback이 성능에 가장 큰 영향을 미치는 것으로 나타났습니다.
  • Scaling Analysis:
    • Generation 수 증가에 따른 Mind Evolution의 성능 향상을 확인했습니다.
    • Mind Evolution이 baseline 대비 candidate solution 수 측면에서 더 효과적임을 입증했습니다.

Limitations

  • Programmatic evaluator 의존: 현재는 proposed solution을 programmatically evaluate하고 critique할 수 있는 natural language planning problem에 중점을 두고 있습니다.
  • LLM-based evaluator 개발 필요: 더 광범위한 application에 적용하기 위해 LLM-based evaluator 개발이 필요합니다.

Future Work

  • LLM-based evaluator 개발: Mind Evolution의 적용 범위를 확장하기 위해 programmatically evaluate하기 어려운 task에도 적용 가능한 LLM-based evaluator를 개발할 계획입니다.
  • 다양한 task 및 domain으로 확장: Mind Evolution을 다른 natural language processing task 및 domain으로 확장하여 general applicability를 검증할 계획입니다.
  • Hybrid approach 연구: Mind Evolution과 다른 search strategy(e.g., tree search)를 결합한 hybrid approach를 연구하여 성능을 더욱 향상시킬 계획입니다.
  • Efficiency 개선: Mind Evolution의 computational cost를 줄이고 efficiency를 개선하기 위한 방법을 연구할 계획입니다.

 

 

 

abstract

우리는 Large Language Models에서 inference time compute를 scaling하기 위한 진화적 탐색 전략을 탐구합니다. 제안된 접근 방식인 Mind Evolution은 language model을 사용하여 후보 응답을 생성, 재조합 및 개선합니다. 제안된 접근 방식은 solution evaluator를 사용할 수 있을 때마다 기본 inference 문제를 공식화할 필요가 없도록 합니다. inference cost를 제어하면서, Mind Evolution이 자연어 계획 작업에서 Best-of-N 및 Sequential Revision과 같은 다른 inference 전략보다 훨씬 우수한 성능을 보인다는 것을 발견했습니다. TravelPlanner 및 Natural Plan 벤치마크에서, Mind Evolution은 공식 solver를 사용하지 않고 Gemini 1.5 Pro를 사용하여 문제 인스턴스의 98% 이상을 해결합니다.

 

 

 

 

 

 

 

 

 

 

1. Introduction

어떻게 Large Language Model (LLM)이 복잡한 문제에 대해 더 깊이 생각하고, inference time compute를 활용하여 문제 해결 능력을 향상시키도록 유도할 수 있을까요? 이전 연구에서는 inference time compute를 활용하기 위한 다양한 전략을 조사했습니다. 예를 들어, chain-of-thought, self-consistency, 피드백 기반의 sequential revision, 보조 verifier 또는 evaluator에 의해 유도되는 search 등이 있습니다. solution evaluator를 사용할 수 있는 경우, search 전략은 증가된 compute로 문제 해결 능력을 안정적으로 향상시킬 수 있다는 장점이 있습니다. 예를 들어, Best-of-N 및 tree search와 같은 방법은 자연스럽게 추가 compute를 활용하여 더 큰 solution 후보 집합을 탐색함으로써 성공적인 solution을 찾을 확률을 높입니다.

 

그림 1 | Mind Evolution은 자연어 공간에서 작동하는 유전자 기반 진화적 search 전략입니다. 이 그림은 Mind Evolution이 여행 계획 작업을 위해 어떻게 solution 후보의 모집단을 더 높은 품질의 후보로 진화시키는지를 보여줍니다. 후보 모집단은 반복적인 프로세스를 통해 개선되며, 각 반복에서 LLM이 후보를 재조합하고 개선하는 데 사용됩니다.

 

 

 

inference time compute를 더 잘 활용하기 위해, 우리는 free-flowing stochastic exploration과 large-scale iterative refinement를 결합한 LLM을 위한 진화적 search 전략을 제안합니다. 우리는 이 접근 방식을 Mind Evolution이라고 부릅니다. 그림 1에 설명된 것처럼, Mind Evolution은 다양한 후보 solution의 모집단을 진화시키는 유전적 search 전략으로, LLM을 활용하여 evaluator의 피드백을 기반으로 solution 후보를 생성, 재조합 및 개선합니다. 전체 프로세스는 지능적인 문제 해결 행동의 특징으로 간주되는 확산적 사고(자유롭게 흐르는 병렬 아이디어 탐색)와 수렴적 사고(아이디어 평가 및 선택)를 결합하는 것과 유사합니다.

평가를 위해 독립적인 후보를 생성하여 광범위하게 search하는 Best-of-N과 달리, Mind Evolution은 다양한 후보 집합을 탐색하고 가장 유망한 대안을 개선하면서 광범위하고 심층적으로 search합니다. self-refinement 또는 tree search와 같이 개별 reasoning 단계를 평가해야 하는 sequential reasoning 접근 방식과 달리, Mind Evolution은 전체 solution에 대한 전역적 개선을 수행하므로 단계별 프로세스 보상이 아닌 전역적 solution evaluator만 있으면 됩니다. 또한, 진화적 방법의 전형적인 특징으로, Mind Evolution은 쉽게 병렬화될 수 있습니다.

주로 진화적 프로그램 generation에 관한 문헌에서 진화적 search와 LLM을 결합하는 것에 대한 이전 연구가 있었습니다. 그러나 이 이전 연구는 실행 피드백 또는 코드 설명의 지침을 사용하여 공식 프로그램 공간을 search하는 데 중점을 둡니다. 반대로, Mind Evolution은 공식 공간에서의 search에 국한되지 않습니다. 이를 통해 Mind Evolution은 프로그램 방식의 solution evaluator를 사용할 수 있는 한, 공식화되지 않았거나 공식화하기 어려운 문제에 적용될 수 있습니다. 특히, 우리는 후보 solution이 여전히 구현 가능한 oracle evaluator를 사용하여 자동으로 구문 분석, 평가 및 비평될 수 있는 자연어 계획 작업에 중점을 둡니다. 이 접근 방식은 주어진 문제에 대한 좋은 solution을 생성하는 것보다 후보 solution의 품질을 평가하는 것이 더 쉬운 경우가 많다는 관찰을 이용합니다.

자연어 계획 영역에서, 우리는 TravelPlanner 및 Natural Plan 벤치마크를 고려합니다. 여기서 제약 조건 만족 문제는 기본 목표, 제약 조건 또는 변수를 명시적으로 공식화하지 않고 자연어로 표현됩니다. 이러한 문제는 일련의 전역 및 지역 제약 조건을 충족하는 상호 연결된 결정 집합을 필요로 합니다. 예를 들어, TravelPlanner에서는 예산 제한 및 기타 선호 사항을 모두 고려하면서 다양한 숙박 및 식사 제약 조건을 존중하는 여행 계획을 생성해야 하며, 이 모든 것이 오직 자연어로만 표현됩니다. 지금까지 LLM은 공식 solver의 도움 없이는 이러한 작업에서 좋은 성능을 달성하지 못했습니다. 예를 들어, Gemini 1.5 Flash와 o1-preview는 TravelPlanner에서 각각 5.6%와 11.7%의 성공률을 달성하는 반면, Natural Plan의 Meeting Planning 영역에서는 각각 20.8%와 44.2%만 달성합니다. 800개의 독립적으로 생성된 응답에 대해 Best-of-N을 활용하더라도 Gemini 1.5 Flash는 여전히 TravelPlanner에서 55.6%, Meeting Planning에서 69.4%의 성공률만 달성합니다. 본 논문에서 우리는 진화적 search를 통한 탐색과 개선이 문제 해결 능력을 눈에 띄게 향상시킬 수 있음을 보여줍니다. 특히, inference time compute를 제어할 때, Mind Evolution은 Gemini 1.5 Flash가 TravelPlanner에서 95.6%, Meeting Planning에서 85.0%의 성공률을 달성할 수 있도록 합니다. 우리는 2단계 접근 방식을 추가로 실험합니다. 여기서 해결되지 않은 문제 인스턴스는 이후에 Gemini 1.5 Pro를 사용한 Mind Evolution으로 처리되어 TravelPlanner에서 100%, Meeting Planning에서 98.4%의 성공률을 달성합니다. 본 논문의 모든 실험은 finetuning 없이 기성 LLM만 사용합니다.

우리가 아는 한, TravelPlanner 벤치마크에서 비슷한 성능을 달성한 유일한 이전 연구는 보조 공식 solver를 활용하고 LLM이 주어진 문제 인스턴스를 동등한 공식화로 먼저 번역하도록 요구하는 것입니다. 일반적으로 자연어로 표현된 문제를 올바르게 공식화하는 데는 상당한 노력과 전문 지식이 필요합니다. LLM이 이러한 번역을 올바르게 수행하도록 유도하려면 적어도 그만큼의 도메인 전문 지식이 필요합니다. Mind Evolution은 자연어 공간에서 solution을 직접 최적화하여 이러한 제약을 제거합니다.

마지막으로, 우리는 생성된 에세이, 이야기 또는 시에 숨겨진 메시지를 인코딩하는 새로운 벤치마크 문제인 StegPoet을 소개합니다. 이러한 형태의 stenography는 공식화하고 해결하기 어렵지만, 숨겨진 메시지 탐지기는 여전히 프로그램 방식으로 search를 유도하기 위해 구현될 수 있습니다. 우리의 동기는 쉽게 공식화될 수 있는 자연어 영역을 넘어서는 search의 적용 가능성을 입증하는 것입니다. 우리는 Mind Evolution이 Gemini 1.5 Pro가 이 작업에서 87%의 성공률을 달성할 수 있음을 발견했습니다.

 

 

기존 연구와의 차별점 (이 논문만의 핵심)

  • Best-of-N, Tree Search 등 기존 Inference Time Compute 활용 전략의 한계 지적:
    • Best-of-N은 독립적 후보 생성으로 "넓은" 탐색에만 치중, "깊은" 탐색 부족
    • Sequential Reasoning (Self-Refinement, Tree Search)은 개별 Reasoning 단계 평가 필요 → Global Solution Evaluator만 필요한 Mind Evolution과의 차별점 강조
  • "Mind Evolution":
    • 진화 알고리즘 (Genetic Algorithm) 기반: LLM을 활용하여 Solution Candidate들을 생성, 재조합, 개선
    • "Divergent Thinking (확산적 사고)" + "Convergent Thinking (수렴적 사고)" 결합: 자유로운 병렬 아이디어 탐색 + 아이디어 평가 및 선택 → 지능적 문제 해결 모방
    • "Global Refinement" 수행: 개별 단계 평가 없이, 완성된 Solution에 대한 전역적 개선 → Global Solution Evaluator만 있으면 적용 가능
    • 쉬운 병렬화
  • 기존 Evolutionary Search + LLM 연구와의 차별성:
    • 기존 연구: Formal Program Space 탐색에 집중 (실행 피드백, 코드 설명 활용)
    • Mind Evolution: Formal Space 제약 없음 → Formalization이 어렵거나 불가능한 문제에도 적용 가능 (Programmatic Solution Evaluator만 있으면 OK)
    • 자연어 기반 Planning Task에 초점: Solution을 자동으로 파싱, 평가, 비평 가능 (Oracle Evaluator 활용) → Solution 생성보다 평가가 쉽다는 점 이용
  • 실험 및 결과:
    • TravelPlanner, Natural Plan 벤치마크: 기존 LLM (Gemini 1.5 Flash, o1-preview)은 Formal Solver 없이는 낮은 성능
    • Mind Evolution: Inference Time Compute 제어 하, Gemini 1.5 Flash 성능 크게 향상 (TravelPlanner 95.6%, Meeting Planning 85.0% 성공률)
    • 2단계 접근법 (Mind Evolution + Gemini 1.5 Pro): TravelPlanner 100%, Meeting Planning 98.4% 성공률
    • StegPoet (새로운 벤치마크): Formalization이 어려운 Stenography Task에도 적용 → Gemini 1.5 Pro 87% 성공률

요약:

  • Mind Evolution: LLM의 Inference Time Compute 활용을 극대화하는 새로운 진화적 탐색 전략.
  • 핵심: Formal Space 제약 없이, Global Solution Evaluator만으로, "넓고 깊은" 탐색을 통해, 자연어 기반 Planning Task에서 SOTA 성능 달성.
  • 시사점: Formalization이 어려운 문제에도 LLM의 문제 해결 능력 향상 가능성 제시.
  • 한마디로: LLM, 이제 진화로 똑똑해진다! (Formalization 없이도!)

AI 연구자들이 주목할 만한 부분:

  • Inference Time Compute 활용의 새로운 패러다임: 기존 방법론과의 비교를 통해 Mind Evolution의 장점 및 차별성 부각
  • Formalization 제약 극복: 다양한 문제 영역으로의 확장 가능성
  • Global Solution Evaluator 기반 접근: Reasoning 과정에 대한 명시적 피드백 불필요
  • 실험적 검증: TravelPlanner, Natural Plan, StegPoet 벤치마크를 통한 성능 입증
  • 간단하고 직관적인 알고리즘: 쉬운 구현 및 병렬화 가능

추가로 읽어보면 좋은 부분:

  • Figure 1 (Mind Evolution 도식화)
  • 2단계 접근법 (Mind Evolution + Gemini 1.5 Pro) 상세 내용
  • StegPoet 벤치마크 상세 내용

 

2. Related Work

LLM과 Evolutionary Search의 결합

섹션 1에서 논의된 프로그램 generation 연구 외에도, 최근 여러 연구에서 LLM과 evolution을 결합하여 수치 최적화 및 조합 최적화를 탐구했습니다. 본 연구에서 다루는 자연어 계획과 같은 문제 공간은 자연어로 지정된 제약 조건에 따라 계획을 최적화하는 조합 최적화 문제로도 볼 수 있습니다. 이러한 이전 연구와는 대조적으로, 우리는 공식적인 공간 대신 자연어 공간에서 solution을 진화시키는 데 중점을 둡니다. 이를 통해 각 작업 인스턴스에 대해 상당한 노력과 전문가 지식이 필요한 작업 공식화 요구 사항이 제거됩니다.

다른 연구에서는 목표 작업의 성능을 향상시키기 위해 prompt 최적화에 evolutionary search를 적용하기도 했습니다. 이 중 EvoAgent는 TravelPlanner 벤치마크에서도 그들의 접근 방식을 평가했습니다. 계획에 직접 evolutionary search를 수행하는 우리 연구와는 대조적으로, EvoAgent는 문제 해결을 위한 multi-agent system을 구성하기 위해 새로운 LLM agent를 진화시킵니다. TravelPlanner validation set에서 그들의 최고 성공률은 GPT-4로 7.2%였던 반면, 우리의 접근 방식은 Gemini 1.5 Flash로 95% 이상을 달성했습니다.

LLM과 Evaluator의 결합

본 연구에서는 evolutionary search 중에 프로그램 기반 evaluator를 사용하여 solution을 평가합니다. 실행 기반 evaluator를 inference 루프에 통합하는 idea는 code generation에 관한 문헌에서 널리 채택되었으며, 여기서 실행 환경은 LLM이 생성된 코드의 버그를 수정하기 위한 피드백을 제공합니다.

다른 이전 연구에서는 response refinement, search, 그리고 model 학습 개선을 위해 학습된 verifier, reward model 또는 self-evaluation을 사용하는 것을 고려했습니다. 이러한 접근 방식은 더 넓은 도메인과 자유 형식 solution에 적용될 수 있지만, 학습된 피드백 model 또는 self-evaluator는 노이즈가 있을 수 있고 완벽하게 신뢰할 수 없습니다. 우리는 이러한 근사적인 피드백 메커니즘에 대한 고려를 향후 연구 과제로 남겨둡니다.

 

 

 

핵심: 기존 연구와의 비교를 통해, "자연어 공간에서의 Solution 진화"라는 차별점 및 "Program-based Evaluator 활용"의 근거 제시

1. LLM + Evolutionary Search 관련 연구:

  • 기존 연구들:
    • 수치 최적화, 조합 최적화에 LLM + Evolution 적용
    • Prompt 최적화에 Evolutionary Search 적용 (EvoAgent 등)
    • EvoAgent: TravelPlanner 벤치마크에서 Multi-Agent System 구성을 위해 LLM Agent를 진화시킴 (GPT-4로 7.2% 성공률)
  • 본 연구 (Mind Evolution) 차별점:
    • 자연어 공간에서 Solution (e.g., 계획)을 직접 진화시킴 (Formal Space X) → Task Formalization 불필요 (노력, 전문 지식 절감)
    • TravelPlanner 벤치마크: Gemini 1.5 Flash로 95% 이상 성공률 (EvoAgent 대비 훨씬 우수)

2. LLM + Evaluator 관련 연구:

  • 기존 연구들:
    • Code Generation: 실행 기반 Evaluator (Execution Environment)를 Inference 루프에 통합 → 코드 버그 수정 (피드백)
    • 학습된 Verifier, Reward Model, Self-Evaluation: Response Refinement, Search, Model 학습 개선 등에 활용
  • 본 연구 (Mind Evolution) 차별점:
    • Program-based Evaluator 활용: Evolutionary Search 과정에서 Solution 평가
    • 학습된 피드백 모델, Self-Evaluator는 부정확 (Noisy) → 정확하고 신뢰할 수 있는 (Reliable) Program-based Evaluator 사용 (근거)
    • 근사적 피드백 (Approximate Feedback) 메커니즘은 향후 연구 과제

요약:

  • Mind Evolution:
    • 자연어 공간에서 Solution 진화: Task Formalization 불필요
    • Program-based Evaluator: 정확하고 신뢰할 수 있는 Solution 평가
  • 기존 연구 대비: 자연어 공간, Program-based Evaluator라는 차별점, TravelPlanner에서 압도적 성능

AI 연구자들이 주목할 만한 부분:

  • 자연어 공간에서의 Solution 진화: Formalization 없이 LLM 활용 범위 확장
  • Program-based Evaluator의 중요성: 정확한 Solution 평가를 통한 성능 향상
  • EvoAgent와의 비교: TravelPlanner 벤치마크에서의 성능 우위 (95% vs 7.2%)

추가로 읽어보면 좋은 부분:

  • Program-based Evaluator의 구체적인 구현 방식
  • EvoAgent와의 상세한 비교 분석

한마디로: "자연어 + Program-based Evaluator"로 차별화된 Mind Evolution! (Formalization, Noisy Feedback은 이제 그만!)

 

 

 

 

3. Method

Mind Evolution은 자연어 계획 작업에 대한 효율적인 solution search를 조정하기 위해, LLM 및 맞춤형 prompt 집합과 결합된 유전적 search 전략을 사용합니다. Mind Evolution을 자세히 설명하기 전에, 먼저 language-based genetic algorithm에 대한 간략한 개요를 제공합니다.

3.1. Language-based Genetic Algorithm 개요

Genetic algorithms은 자연 선택에서 영감을 받은 메타 휴리스틱입니다. Genetic algorithm에서는 목표 최적화 목적에 대해 더 높은 품질의 개체를 더 많이 포함하는 모집단으로 후보 solution의 모집단을 진화시킵니다. 이러한 목적은 종종 "적합도(fitness)" 함수라고도 합니다. 각 개별 후보는 변형되고 다른 후보와 재조합될 수 있는 유전적 표현을 갖습니다.

진화적 search는 일반적으로 독립적으로 생성된 후보 solution의 모집단으로 시작됩니다. 각 세대에서 모든 개체의 적합도는 목표 목적에 따라 평가됩니다. 그런 다음 후보는 적합도에 따라 번식을 위해 확률적으로 선택됩니다("선택"). 번식에서 선택된 부모의 유전적 표현은 결합("교차")되고 잠재적으로 변경("돌연변이")되어 새로운 자식 solution을 생성합니다. 이러한 프로세스는 다음 세대의 자식을 생성하고, 그 다음 모집단에 들어갑니다. 더 높은 적합도를 가진 부모가 재조합을 위해 선택될 가능성이 더 높기 때문에, 모집단 적합도는 일반적으로 연속적인 세대에 걸쳐 증가합니다.

Island Model

진화하는 모집단의 다양성을 유지하기 위해, "이주"와 지정된 빈도로 발생하는 "섬 재설정" 이벤트 사이에서 독립적으로 생성되고 진화되는 별개의 하위 모집단("섬")이 생성되는 island model을 도입하는 것이 도움이 됩니다. 이주 작업의 경우, 한 섬의 solution은 적합도에 따라 확률적으로 선택되어 인접한 섬으로 이동합니다. 섬 재설정 작업의 경우, 전체 적합도가 낮은 섬의 모집단은 전역 모집단에서 강력한 solution으로 대체되며, 이는 또한 선택 효과를 갖습니다. island model은 FunSearch와 같은 최근의 성공적인 노력에 채택되었습니다.

Language-based Genetic Representation

Language-based genetic algorithm의 개별 후보는 자연어로 표현됩니다. 이를 통해 LLM의 강력한 언어 이해 및 generation 능력을 활용하여 prompting을 통해 강력한 재조합(교차 및 돌연변이) 및 섬 재설정 작업을 구현할 수 있습니다.

3.2. Mind Evolution

그림 1은 Mind Evolution의 설계를 보여주며, 하이퍼파라미터는 표 1에 나열되어 있습니다. Mind Evolution의 핵심 구성 요소는 다음과 같습니다.

  1. 선택 및 이주 작업을 위한 구체적인 선택
  2. LLM을 사용한 초기화, 재조합(교차 및 돌연변이) 및 섬 재설정 작업을 구현하는 prompt 집합
  3. 주어진 solution의 품질을 평가하고 선택적으로 감지된 문제에 대한 피드백을 제공하는 적합도 함수

전체 진화 프로세스는 유효한 solution이 발견되거나 𝑁gens 세대가 완료될 때까지 반복되며, 그 후 최고 점수 후보가 반환됩니다.

Fitness Evaluation

섹션 1에서 논의한 바와 같이, 우리는 각 문제 영역에 대한 적합도 함수를 구현하며, 여기서 후보 solution은 프로그램 방식으로 구문 분석되고 평가됩니다. 원칙적으로, LLM 평가를 포함하여 solution 품질을 평가할 수 있는 모든 함수를 사용할 수 있습니다. 평가 함수는 Mind Evolution에서 세 가지 주요 역할을 수행합니다. (1) 최적화 목적을 측정하여 solution에 점수를 매기는 것(있는 경우); (2) solution이 주어진 제약 조건을 충족하는지 확인하는 것; (3) 해당 텍스트 피드백을 제공하는 것. 예를 들어, Meeting Planning 작업에 대한 평가 함수는 제안된 계획에 점수를 매기고, 얼마나 많은 제약 조건이 위반되는지(예: 기존 일정과 충돌하는 회의), 일정에 포함된 유효한 회의 이벤트 수, 계획이 요구되는 형식을 따르는지 여부에 따라 텍스트 피드백을 제공합니다(자세한 내용은 부록 A.2 참조). 섹션 4.4의 ablation study에서 볼 수 있듯이 텍스트 피드백을 사용하는 것이 경험적으로 중요하다는 것을 발견했습니다.

많은 고전적인 search 문제(예: NP-완전 문제)의 경우, solution을 확인하는 것이 문제를 해결하는 것보다 훨씬 쉬울 수 있습니다. 마찬가지로, 우리는 고려하는 자연어 계획 작업에 대한 평가 함수를 작성할 수 있음을 관찰합니다. 후보 solution의 정확성을 확인할 수 있는 능력이 우리가 고려하는 작업에서 유효한 solution을 생성하는 능력으로 분명히 이어지지는 않습니다. 즉, 평가 함수를 구현하는 것은 작업을 해결하는 것과 동일하지 않습니다.

Population Initialization

대상 문제가 주어지면, 문제 설명, 문제 해결에 필요한 정보 및 관련 지침으로 LLM을 prompting하여 𝑁convs개의 초기 solution을 독립적으로 샘플링합니다. 𝑁seq > 1인 경우, 이러한 초기 solution은 각각 아래에 설명된 "비판적 대화를 통한 개선(Refinement through Critical Conversation)" 프로세스의 𝑁seq - 1 추가 턴을 통해 순차적으로 평가되고 개선됩니다. 전체적으로 이 초기화 절차는 𝑁convs × 𝑁seq 후보 solution을 생성하며, 이는 첫 번째 세대의 첫 번째 섬에 대한 초기 모집단을 구성합니다.

Refinement through Critical Conversation (RCC)

그림 2와 같이 "비평가" 캐릭터와 "저자" 캐릭터 간의 비판적 대화를 구성하여 개선된 solution을 생성하기 위해 후보 solution(또는 재조합 프로세스를 위한 후보 solution 집합)이 주어지면 LLM을 활용합니다. 이 두 역할을 분리하는 것은 LLM의 비판적 사고 능력을 향상시키기 위한 것입니다. 각 대화 턴은 Reflexion과 유사하게 비판적 피드백을 기반으로 solution이 개선되는 prompt 기반 프로세스로 구성됩니다. 특히, 비평가는 먼저 입력으로 제공된 후보 solution을 분석하고, 텍스트 평가 피드백을 해석하고, 피드백에 제시된 문제를 수정하는 방법을 제안합니다. 그런 다음 저자는 입력 후보, 후속 평가 및 비평가의 분석을 기반으로 단일 개선된 solution을 제안합니다. 이러한 대화를 유도하는 데 사용되는 특정 prompt는 부록 A.1에 나와 있습니다. 섹션 4.4의 ablation study는 비평가의 분석 단계가 상당한 성능 향상을 제공한다는 것을 보여줍니다.

Selection

섬의 다음 세대를 생성하기 위해, 우리는 Boltzmann tournament selection을 따릅니다. 여기서 0에서 𝑁parent 부모가 적합도 점수의 softmax 변환에서 파생된 확률 분포에 따라 모집단에서 확률적으로 샘플링됩니다. 이런 식으로, 더 높은 성능의 solution이 번식을 위해 선택될 가능성이 더 높지만, 다양성을 위해 다른 후보가 가끔 선택될 수도 있습니다.

Crossover and Mutation

우리는 교차 및 돌연변이 작업을 단일 재조합 단계로 구현합니다. 여기서 LLM은 위에서 설명한 RCC 프로세스(그림 2)를 사용하여 주어진 부모 집합을 개선하도록 지시됩니다. 특히, 재조합을 위해 1에서 𝑁parent 부모를 샘플링하고, 그림 2의 단계 (b)를 수정하여 먼저 부모의 평가 결과를 통합한 다음, 모든 부모에게 비평가를 적용하고 다음 세대를 위한 "초기 solution"으로 수정된 solution을 제안합니다. 그런 다음, 𝑁seq > 1인 경우, 단계 (c)(d)(e)를 계속 따라가면서 이전 자식을 RCC 프로세스를 사용하여 개선하여 순차적으로 𝑁seq - 1 자식 solution을 생성합니다. 각 섬의 각 세대에 대해 𝑁convs × 𝑁seq 자식 solution이 섬 모집단에 추가되며, 중복된 solution은 제거됩니다. 선택을 위해, 아래의 섬 재설정을 수행할 때를 제외하고는 후보 solution을 명시적으로 폐기하는 대신 Boltzmann tournament를 따릅니다.

Migration between Islands

이주 이벤트 사이에서 각 섬 모집단은 독립적으로 진화됩니다. 이주하는 동안, 현재 섬에서 세대를 완료한 후 현재 섬 𝑖에서 다음 섬 𝑖 + 1로 상위 𝑁emigrate solution이 복제됩니다(우리는 섬의 모집단을 1에서 𝑁island까지 순차적으로 업데이트합니다). 이주는 섬 사이에서 주기적으로 수행되므로, 섬 𝑁island의 이주자는 섬 1에 도착합니다. 우리는 이러한 형태의 주기적 이주가 전체 진화 과정을 가속화한다는 것을 발견했습니다.

Island Reset

섬 재설정은 𝑁reset 간격 세대마다 발생합니다. 섬 재설정 이벤트 동안, 상위 수행자가 먼저 전역 모집단에서 선택되고, 평균 점수가 가장 낮은 𝑁reset 섬의 모집단이 폐기되고, 선택된 상위 수행자가 재설정된 섬에 복제됩니다. 상위 수행자를 선택하기 위해, 우리는 두 가지 접근 방식을 탐구합니다. (1) 적합도에 따라 상위 𝑁top 후보를 직접 선택합니다. (2) 먼저 적합도에 따라 상위 𝑁candidate 후보를 선택한 다음, LLM에게 이 풀에서 서로 실질적으로 다른 𝑁top 좋은 후보를 선택하도록 prompt합니다. 섹션 4.4의 ablation study는 후자의 전략, 즉 섬 재설정에 LLM을 사용하는 것이 더 나은 성능을 달성한다는 것을 보여줍니다.

 

 

핵심: "Mind Evolution" - LLM + Genetic Algorithm으로 자연어 Planning 문제 풀기

3.1 Language-based Genetic Algorithm (기본 개념)

  • Genetic Algorithm: 자연 선택 기반 메타 휴리스틱, 우수 Solution Candidate (개체) 모집단 진화
  • 핵심 요소:
    • Fitness Function (적합도 함수): Solution 품질 평가
    • Selection (선택): Fitness 기반 우수 개체 선택
    • Crossover (교차) / Recombination (재조합): 선택된 개체 결합 → 새 개체 생성
    • Mutation (돌연변이) / Refinement (개선): 개체 변형
  • Island Model: 다양성 유지를 위한 독립적 하위 모집단 (Island) + Migration (이주), Island Reset
  • Language-based: 개체가 자연어로 표현 → LLM 활용 (Recombination, Island Reset에 강점)

3.2 Mind Evolution (핵심 알고리즘)

  • 구성 요소:
    • Selection & Migration: Boltzmann Tournament Selection, Cyclic Migration
    • Prompt Set: Initialization, Recombination, Island Reset을 위한 LLM Prompt
    • Fitness Function: Solution 품질 평가, 제약 조건 검증, 텍스트 피드백 제공
  • 진화 과정:
    1. Fitness Evaluation: Program-based Evaluator로 Solution 평가 (정확성, 신뢰성 중시)
    2. Population Initialization: LLM Prompting으로 초기 Solution 생성 (Nconvs 개) + Refinement (Nseq - 1회)
    3. Refinement through Critical Conversation (RCC): "Critic" + "Author" 역할 부여 (LLM) → 비판적 사고, 개선 유도 (Reflexion과 유사)
    4. Selection: Boltzmann Tournament Selection으로 부모 개체 선택 (다양성 고려)
    5. Crossover & Mutation: RCC 활용, 부모 개체 개선 → 자식 개체 생성 (Nconvs * Nseq 개, 중복 제거)
    6. Migration: 주기적, Cyclic Migration (Island 간 개체 이동) → 진화 가속화
    7. Island Reset: 주기적, Global Population에서 우수 개체 선택 → Island 모집단 교체 (LLM 활용, 다양성 확보)

이 논문만의 핵심:

  • LLM + Genetic Algorithm: LLM의 추론 능력 (Recombination, Refinement)과 Genetic Algorithm의 탐색 능력 결합
  • 자연어 기반: Solution, Prompt 모두 자연어 → Formalization 불필요
  • Program-based Fitness Evaluation: 정확하고 신뢰할 수 있는 Solution 평가 (학습된 모델, Self-Evaluation X)
  • Refinement through Critical Conversation (RCC): Critic, Author 역할 분리 → 비판적 사고, 개선 유도
  • LLM 활용 Island Reset: 다양성 확보, 성능 향상

AI 연구자들이 주목할 만한 부분:

  • Genetic Algorithm의 새로운 적용: LLM과의 결합을 통한 자연어 문제 해결
  • Program-based Evaluation의 중요성: 정확한 Solution 평가의 핵심
  • RCC: LLM의 비판적 사고 능력 향상 기법
  • 실험적 검증: TravelPlanner, Natural Plan, StegPoet 벤치마크를 통한 성능 입증 (4. Results에서 다룰 예정)
  •