POLCA: LLM을 활용한 확률적 생성 최적화

LLM 에이전트나 프롬프트 최적화 시 발생하는 무작위적인 결과와 노이즈 섞인 피드백 문제를 해결하는 프레임워크이다. 의미적으로 중복된 제안을 걸러내는 ε-Net 기법을 통해 탐색 공간을 효율적으로 관리하며, 복잡한 시스템의 자동 튜닝 비용을 크게 절감한다.

LLM 프롬프트나 에이전트 코드를 최적화할 때, 실행할 때마다 결과가 달라지거나 피드백에 노이즈가 섞여 있으면 최적의 방향을 찾기 어렵다. 이는 Gradient Descent에서 노이즈가 심한 그래디언트를 따라가는 것과 유사하며, 결국 최적화가 정체되거나 비슷한 실수만 반복하게 된다. POLCA는 이 문제를 해결하기 위해 Embedding 개념을 도입한다. 생성된 모든 후보를 벡터 공간에 매핑하고, 특정 거리(ε) 안에 이미 존재하는 후보가 있다면 이를 중복으로 간주해 제외하는 ε-Net 원리를 적용한다. 이를 통해 LLM이 의미적으로 새로운 영역을 탐색하도록 강제한다. 또한 모든 평가 결과를 우선순위 큐에 저장하고, LLM Summarizer가 전체 이력을 분석해 성공 패턴과 실패 패턴을 추출한다. 이 요약된 정보는 다음 최적화 단계에서 가이드라인 역할을 하며, 마치 사람이 과거 경험을 통해 학습하듯 시스템이 스스로 개선 방향을 잡게 한다.

POLCA는 SampleMinibatch, SelectPrograms, Evaluate, UpdateStats의 반복 루프로 작동한다. 전체 데이터셋 대신 무작위로 추출된 미니배치를 사용하여 평가 비용을 줄이면서도, 유망한 후보는 여러 번 평가하여 점수의 신뢰도를 높인다. 핵심인 SemanticFilter는 가장 먼 지점을 먼저 선택하는 Farthest-first traversal 전략을 사용한다. 새로운 후보 theta'와 기존 메모리 Q 내 후보들 사이의 최소 거리 d(theta') = min ||phi(theta) - phi(theta')||_2를 계산한다. 이 거리가 사용자 정의 임계값 ε보다 클 때만 새로운 후보로 승인하며, 이를 통해 탐색 공간의 다양성을 보장한다. Summarizer는 메모리에 저장된 이력을 보상 임계값 tau를 기준으로 성공(H+)과 실패(H-)로 분류한다. 각 그룹에서 대표적인 궤적을 대조 샘플링하여 LLM에 입력으로 제공한다. LLM은 이 대조적인 사례들을 통해 어떤 요소가 성능 향상에 기여했는지 파악하고 다음 후보 생성에 반영한다.

tau-bench 리테일 도메인 실험에서 POLCA는 기본 프롬프트 대비 13% 향상된 성능(Pass@1 0.439)을 기록했다. 이는 GEPA(0.429)나 OpenEvolve(0.418) 등 기존 최적화 알고리즘보다 높은 수치이며, 특히 미니배치 샘플링으로 인한 확률적 노이즈 환경에서 더 견고한 성능을 보였다. VeriBench의 Python-to-Lean 4 번역 작업에서 95.2%의 컴파일 통과율을 달성했다. 이는 DSPy(88.8%)나 GEPA(69.5%)를 크게 앞지르는 결과로, LLM 판정관의 주관적이고 노이즈 섞인 피드백을 효과적으로 처리했음을 입증한다. KernelBench를 이용한 CUDA 커널 최적화 실험에서도 POLCA는 PyTorch 기본 구현 성능을 1.0배 이상 초과하는 커널을 가장 빠르게 찾아냈다. 특히 초기 단계에서는 순차적 방식보다 느릴 수 있으나, 병렬 배치 업데이트 설계를 통해 전체 시간 대비 성능 효율이 우수하게 나타났다.

POLCA는 생성형 최적화 문제를 확률적 환경으로 확장하여 {P, theta_0, D, Theta, G, O}로 정의한다. 여기서 P는 프로그램, D는 데이터 분포, G는 수치적 점수와 텍스트 피드백을 제공하는 가이드, O는 LLM 최적화 도구이다. 이론적 분석을 위해 UCB 점수를 우선순위 함수로 사용했다. [평균 보상 + 불확실성 보너스]를 통해 유망한 후보를 체계적으로 탐색하며, 최적화 오라클이 일정 확률로 개선된 후보를 제안할 수 있다면 확률적 환경에서도 근사 최적해로 수렴함을 수학적으로 증명했다. ε-Net 메커니즘은 탐색 공간 Theta를 이산화하는 역할을 한다. 임베딩 함수 phi를 통해 파라미터를 벡터화하고, 거리가 ε 이내인 후보들을 동일하게 취급함으로써 무한한 탐색 공간을 유한한 크기로 제한하여 계산 복잡도를 관리한다.

경험적 평균 점수를 기반으로 한 우선순위 결정은 효율적이지만, 보상의 확률 분포가 복잡할 경우 더 고도화된 선택 전략이 필요할 수 있다. 또한 최적화 도구인 LLM이 항상 개선된 후보를 제안할 수 있다는 가정이 실제 복잡한 문제에서는 성립하지 않을 가능성이 있다.