[기술 요약] HiFo-Prompt: LLM 기반 자동 휴리스틱 설계를 위한 후견(Hindsight) 및 선견(Foresight) 프롬프팅

1. 문제 정의 (Problem Statement)

조합 최적화(Combinatorial Optimization, CO) 문제를 해결하기 위한 효과적인 휴리스틱(Heuristic) 설계는 전통적으로 인간의 직관과 경험에 의존해 왔습니다. 최근 대규모 언어 모델(LLM)을 진화 연산(Evolutionary Computation, EC)과 결합하여 코드를 자동으로 생성하는 자동 휴리스틱 설계(AHD) 연구가 활발하지만, 기존 방식들은 다음과 같은 두 가지 핵심적인 한계를 가집니다.

• 전역적 제어 능력의 부재 (Lack of Global Control): 기존 모델들은 개별 후보군에 대한 국소적 반성(Reflection)에 그치며, 전체 인구 집단의 동역학(예: 정체, 다양성 붕괴)을 파악하여 탐색(Exploration)과 이용(Exploitation) 사이의 균형을 능동적으로 조절하지 못합니다.
• 지식 지속성 및 축적의 실패 (Knowledge Decay): 성공적인 설계 원칙이 특정 코드 구현체에 얽매여 있어, 우수한 부모 개체가 버려지면 그 밑에 깔린 핵심 알고리즘 논리(Design Principles)도 함께 소실됩니다. 즉, 과거의 성공으로부터 배우는 '누적 학습'이 이루어지지 않습니다.

2. 제안 방법론 (Methodology: HiFo-Prompt)

본 논문은 LLM을 단순한 코드 생성기에서 **심볼릭 메타 최적화 도구(Symbolic Meta-optimizer)**로 격상시키기 위해 HiFo-Prompt 프레임워크를 제안합니다. 이 프레임워크는 두 가지 시너지 전략을 사용합니다.

① Foresight (선견) 모듈: Evolutionary Navigator

인구 집단의 상태를 실시간으로 모니터링하여 탐색 전략을 결정하는 메타 컨트롤러 역할을 합니다.

• 상태 모니터링: 성능 정체(Stagnation)와 표현형 다양성(Phenotypic Diversity, 알고리즘 텍스트의 유사도 측정)을 지속적으로 관찰합니다.
• 전략 전환 (Regime Switching): 분석 결과에 따라 세 가지 모드 중 하나를 선택하여 프롬프트에 '설계 지침(Design Directive)'을 주입합니다.
  • Explore (탐색): 다양성이 낮거나 정체될 때, 완전히 새로운 접근 방식을 시도하도록 유도.
  • Exploit (이용): 성능이 꾸준히 향상될 때, 기존 패턴을 정교화하도록 유도.
  • Balance (균형): 두 전략을 조화롭게 적용.

② Hindsight (후견) 모듈: Insight Pool

과거의 성공적인 경험을 추상화된 지식으로 변환하여 저장하는 지식 저장소입니다.

• 지식 추출 (Insight Distillation): 우수한 성능을 보인 엘리트 개체들로부터 일반화 가능한 설계 원칙(Insights)을 LLM을 통해 추출합니다.
• 지식 관리 (Insight Pool): 추출된 인사이트는 고유한 신뢰도 점수(Credibility Score)를 부여받으며, 중복된 지식은 자카드 유사도(Jaccard Similarity)를 통해 필터링됩니다.
• 신용 할당 (Credit Assignment): 새로운 인사이트가 생성된 후, 그 인사이트를 사용해 만들어진 결과물의 성능에 따라 점수를 업데이트(EMA 방식)하여 유용한 지식만 남깁니다.

③ 가이드형 프롬프트 합성 (Guided Prompt Synthesis)

위의 두 모듈에서 얻은 정보는 **기초 프롬프트(Foundational Prompt) + Hindsight(인사이트) + Foresight(설계 지침)**의 형태로 결합되어 LLM에게 전달됩니다. 이를 통해 LLM은 현재 진화 단계에 최적화된 맥락을 갖게 됩니다.

3. 주요 기여 (Key Contributions)

1. 계층적 제어 구조 도입: LLM을 단순 연산자가 아닌, 전역적 계획(Foresight)과 누적 경험(Hindsight)을 갖춘 능동적 추론자로 변모시켰습니다.
2. 지식의 탈동기화 (Decoupling): 알고리즘의 실행 코드와 핵심 설계 원칙(Thought)을 분리하여, 코드가 사라져도 지식은 남을 수 있는 구조를 구축했습니다.
3. 효율적인 심볼릭 그래디언트: 수치적 미분(Numerical Gradient) 대신 자연어 기반의 설계 지침을 사용하여, 비용이 많이 드는 미세 조정(Fine-tuning) 없이도 효과적인 전략 전환을 달성했습니다.

4. 실험 결과 (Results)

다양한 복잡한 최적화 문제(TSP, Online BPP, FSSP, Bayesian Optimization)에서 실험을 진행한 결과:

• SOTA 달성: 기존의 최첨단 AHD 방법론(EoH, ReEvo, MCTS-AHD 등)을 능가하는 성능을 보였습니다.
• 우수한 수렴 속도 및 효율성: 더 적은 수의 LLM 호출(Query)과 짧은 시간 내에 더 높은 품질의 휴리스틱을 발견했습니다.
• 강력한 일반화 성능: TSP(외판원 문제)의 단계별 구축 방식 및 GLS(가이드 국소 탐색) 방식 모두에서 기존 수작업 휴리스틱에 근접하거나 뛰어난 성능을 보였습니다.

5. 의의 (Significance)

본 연구는 LLM 기반 자동 알고리즘 설계 분야에서 **"어떻게 하면 모델이 과거를 기억하고 미래를 계획하며 스스로 진화할 수 있는가?"**라는 근본적인 질문에 대한 해답을 제시합니다. 이는 단순히 코드를 잘 짜는 AI를 넘어, **자신의 문제 해결 방법론을 스스로 발명하고 학습하는 에이전트(Agent)**로 나아가는 중요한 이정표를 마련했다는 점에서 큰 의의가 있습니다.