LLM을 위한 Swarm Optimization (PSO, ACO)

생물 기반 최적화(Bio-inspired optimization)가 LLM 시대에 다시 돌아오고 있습니다. LMPSO(arXiv:2504.09247)는 입자 군집 최적화(Particle Swarm Optimization; PSO)를 사용하며, 각 입자(particle)의 속도(velocity)가 프롬프트(prompt)가 되고 LLM이 다음 후보(candidate)를 생성합니다. 수식이나 프로그램처럼 구조화된 시퀀스 출력(structured-sequence output)에 잘 작동합니다. Model Swarms(arXiv:2410.11163)는 각 LLM 전문가(expert)를 모델 가중치 다양체(model-weight manifold) 위의 PSO 입자로 다루며, 9개 데이터셋의 12개 베이스라인(baseline) 대비 평균 13.3% 성능 향상을 보고했고, 사용한 인스턴스는 이터레이션(iteration)당 200개뿐이었습니다. SwarmPrompt(ICAART 2025)는 프롬프트 최적화를 위해 PSO와 회색늑대 알고리즘(Grey Wolf)을 결합(hybridize)합니다. AMRO-S(arXiv:2603.12933)는 다중 에이전트(multi-agent) LLM 라우팅을 위한 개미 군집 최적화(Ant Colony Optimization; ACO) 기반의 페로몬 전문가(pheromone specialist)입니다. 4.7배 속도 향상, 해석 가능한 라우팅 근거(interpretable routing evidence), 그리고 추론(inference)과 학습(learning)을 분리하는 품질 게이트형 비동기 업데이트(quality-gated asynchronous update)를 제공합니다. 이 강의에서는 프롬프트 파라미터 공간 위의 PSO와 에이전트 라우팅 위의 ACO를 직접 구현하고, 이 고전 알고리즘들이 왜 LLM 시대에 잘 맞는지, 그리고 언제 맞지 않는지를 측정합니다.

유형: Learn + Build 언어: Python (stdlib) 선수 지식: Phase 16 · 09 (병렬 Swarm과 네트워크형 아키텍처), Phase 16 · 14 (에이전트를 위한 합의와 Byzantine Fault Tolerance) 예상 시간: 약 75분

문제

여러분이 어떤 과제 평가(task eval)에서 62%를 기록하는 프롬프트를 가지고 있다고 합시다. 이 프롬프트를 개선하고 싶습니다. 가장 단순한 접근은 그래디언트 없이 수동으로 조금씩 손보는 방법(gradient-free manual tweaking)이지만, 규모를 키우기 어렵습니다. 강화 학습(reinforcement learning)은 보상 신호(reward signal)와 충분한 롤아웃(rollout)이 필요합니다. 프롬프트에 역전파(backprop)를 적용하는 것도 사실상 불가능합니다. 프롬프트는 미분 가능한 파라미터(differentiable parameter)가 아니라 이산적인 문자열(discrete string)이기 때문입니다.

고전적인 생물 기반 최적화 알고리즘, 즉 연속 탐색 공간(continuous search space)을 위한 PSO와 경로 선택(path selection)을 위한 ACO는 바로 이런 상황을 위해 설계되었습니다. 이들은 그래디언트가 필요 없고(gradient-free), 집단 기반(population-based)이며, 평가 한 번당 비용이 저렴합니다. LLM과 결합해 그래디언트 없는 탐색 단계로 사용하면 의외로 실용적인 옵티마이저(optimizer)가 됩니다.

같은 패턴은 다중 에이전트 시스템의 에이전트 라우팅에도 적용됩니다. ACO 방식의 페로몬 자취(pheromone trail)는 어떤 과제 유형(task-type)에서 어떤 에이전트가 가장 잘 작동했는지를 기록하고, 라우터가 그 자취를 활용(exploit)하게 하며, 페로몬을 시간에 따라 감쇠(decay)시켜 경로가 다시 발견될 여지를 남깁니다.

개념

PSO 복습 (Kennedy & Eberhart 1995)

입자 군집 최적화는 연속 탐색 공간 위의 입자 집단을 다룹니다. 각 입자는 위치 x_i와 속도 v_i를 가지고, 매 이터레이션마다 다음과 같이 갱신됩니다.

v_i <- w * v_i + c1 * r1 * (p_best_i - x_i) + c2 * r2 * (g_best - x_i)
x_i <- x_i + v_i
evaluate fitness(x_i)
update p_best_i if improved
update g_best if global best

여기서 p_best는 입자 자신이 지금까지 찾은 최적해, g_best는 군집(swarm) 전체의 최적해입니다. w, c1, c2는 각각 관성(inertia), 인지(cognitive), 사회(social) 가중치이고, r1, r2는 무작위 계수입니다.

LLM 출력 위의 PSO — LMPSO

arXiv:2504.09247은 LLM이 생성하는 구조화된 출력(수식, 프로그램)에 PSO를 적용합니다. 각 입자는 하나의 후보 출력(candidate output)입니다. 속도는 현재 출력을 개인 최적해(personal best) 또는 전역 최적해(global best) 쪽으로 어떻게 수정할지 설명하는 프롬프트이고, LLM은 이 속도 프롬프트로부터 새로운 출력을 생성합니다. 속도의 "관성"은 "작고 점진적인 변경만 가하라" 같은 프롬프트로 표현됩니다.

이 방식은 다음과 같은 조건에서 잘 작동합니다.

• 출력이 구조화되어 있어 파싱과 평가가 가능한 경우.
• 적합도(fitness)가 자동으로 계산되는 경우(테스트 실행, 산술적 평가 등).
• 집단 크기가 작은 경우(약 10~30개 입자). 그래야 전체 LLM 호출(call) 비용을 관리할 수 있습니다.

반면 적합도 평가에 사람의 검토가 필요하면 잘 작동하지 않습니다. 이터레이션마다 드는 비용이 지나치게 커지기 때문입니다.

Model Swarms

arXiv:2410.11163은 PSO를 출력 계층(output layer)이 아니라 모델 계층으로 옮깁니다. 각 "입자"는 전문가 LLM의 파라미터이며, 군집은 그래디언트 없는 업데이트를 통해 파라미터를 집단 최적해 쪽으로 이동시킵니다. 보고된 결과는 9개 데이터셋, 12개 베이스라인 대비 평균 13.3% 성능 향상이며, 이터레이션당 인스턴스는 200개에 불과합니다.

핵심 통찰은 LLM 전문가 모델들이 이미 공유 파라미터 다양체(adapter weights, LoRA deltas) 위에서 서로 가까이에 위치한다는 점입니다. 이런 저차원 부분공간(low-dimensional subspace) 위에서 PSO는 저렴하면서도 효과적입니다.

ACO 복습 (Dorigo 1992)

개미 군집 최적화에서는 개미들이 그래프(graph)를 횡단(traverse)하고, 각 경로에는 페로몬 자취가 남아 있습니다. 개미의 이동 확률은 페로몬 강도에 비례해 가중됩니다. 과제를 완수한 개미는 해의 품질(solution quality)에 비례해 페로몬을 남기고(deposit), 페로몬은 시간이 지나면서 감쇠합니다.

AMRO-S — 에이전트 라우팅을 위한 ACO

arXiv:2603.12933은 다중 에이전트 라우팅에 ACO를 적용합니다. 각 과제 유형이 "목적지(destination)"이고, 각 에이전트는 가능한 경로(route)입니다. 좋은 출력을 만들어낸 경로의 페로몬은 더 강해집니다. 주요 기여는 다음과 같습니다.

• 해석 가능한 라우팅 근거. 페로몬 강도는 사람이 직접 읽을 수 있는 신호입니다.
• 품질 게이트형 비동기 업데이트. 페로몬은 품질 검사가 통과한 뒤에만 갱신되며, 이를 통해 추론과 학습이 분리됩니다.
• 다중 에이전트 라우팅 벤치마크에서 4.7배 속도 향상을 달성했습니다.

품질 게이트는 매우 중요합니다. 이것이 없으면 빠르지만 잘못된 답을 내는 에이전트가 페로몬을 쌓아 올리게 되고, 시스템이 잘못된 경로에 고착(lock-in)됩니다.

LLM에 PSO / ACO를 쓸 때

PSO를 쓰는 경우:

• 탐색 공간이 연속적이거나, 연속 파라미터로 매핑되는 경우(프롬프트 임베딩, LoRA 가중치, 생성용 수치 파라미터 등).
• 적합도 계산이 저렴하고 자동인 경우.
• 집단 크기를 작게 유지할 수 있는 경우(10~30).

ACO를 쓰는 경우:

• 라우팅 또는 경로 선택 문제가 있는 경우.
• 의사결정이 시간이 지나면서 강화되는 경우(같은 과제 유형이 반복적으로 들어옴).
• 라우팅 결정에 대해 해석 가능한 근거가 필요한 경우.

둘 다 쓰지 않는 경우:

• 적합도 평가에 사람의 검토가 필요한 경우. 이터레이션마다 너무 비쌉니다.
• 탐색 공간이 PSO가 다루기 어려운 형태로 이산적이고 조합적(discrete and combinatorial)인 경우. 이때는 유전 알고리즘(genetic algorithm)을 사용합니다.
• 실시간 의사결정에 엄격한 지연 시간(latency) 제한이 있는 경우. PSO와 ACO는 단일 패스 휴리스틱(single-pass heuristic)보다 수렴(converge)이 느립니다.

왜 생물 기반 알고리즘이 여전히 통하는가

그래디언트 기반 방법은 미분 가능한 신호가 있어야 합니다. 그런데 LLM 출력과 라우팅 결정은 본질적으로 미분 가능하지 않습니다. 의사 그래디언트(pseudo-gradient) 방법인 강화학습 라우터나 DPO 방식의 프롬프트 튜너도 동작은 하지만, 비싼 학습 과정을 필요로 합니다.

PSO와 ACO에 필요한 것은 오직 평가자(evaluator) 함수뿐입니다. 후보 출력이나 라우팅 결정을 점수화할 수만 있다면 그 공간을 최적화할 수 있습니다. 그래서 적용 가능성의 진입 장벽이 훨씬 낮아집니다.

실무적 한계

• 집단 예산(Population budget). 입자 수 N × 이터레이션 수 T × 평가 한 번당 비용입니다. LLM 평가 호출이 약 $0.02라면, 입자 20개로 50번 이터레이션을 도는 PSO는 약 $20이 듭니다. 이에 맞춰 계획해야 합니다.
• 탐색과 활용의 균형(Exploration vs exploitation). 페로몬 감쇠 속도와 PSO 관성은 상충 관계(trade-off)에 있습니다. 감쇠가 너무 빠르면 좋은 해를 잊어버리고, 너무 느리면 초기 지역 최적해(local optimum)에 갇힙니다.
• 재앙적 표류(Catastrophic drift). 적합도 지형(fitness landscape)이 바뀌면 두 알고리즘 모두 한 번 수렴한 뒤에도 다시 발산할 수 있습니다(새로운 데이터 분포 등). 최고 적합도의 안정성을 모니터링해야 합니다.

직접 만들기

code/main.py는 다음을 구현합니다.

• LMPSO — 수치형 프롬프트 파라미터(temperature, top_k weights) 위의 PSO입니다. 각 입자의 "LLM 생성"은 스크립트로 작성된 적합도 함수로 시뮬레이션되며, 30번의 이터레이션 동안 알고리즘을 실행하고 g_best의 수렴 과정을 보여 줍니다.
• AMRO_S — ACO 방식 라우팅입니다. 에이전트 3명, 과제 유형 4개, 페로몬 행렬(pheromone matrix), 200개의 라우팅 과제로 구성됩니다. 자취가 형성되는 모습을 보여 주기 위해 시간에 따른 (task_type → agent choices) 분포를 출력합니다.
• 비교(Comparison) — 같은 과제 스트림에 대해 무작위 라우팅과 ACO 라우팅을 비교하고 품질과 지연 시간을 측정합니다.

다음과 같이 실행합니다.

python3 code/main.py

예상 출력:

• LMPSO: g_best 적합도가 무작위 수준에서 30번의 이터레이션을 거치며 거의 최적 수준까지 개선됩니다.
• AMRO-S: 페로몬 표가 과제 유형별로 적합한 에이전트로 안정화됩니다. ACO 라우팅은 품질에서 무작위 라우팅보다 약 30~40% 더 좋고, 재시도(retry)가 줄어 지연 시간도 낮아집니다.

사용해보기

outputs/skill-swarm-optimizer.md는 LLM과 에이전트 최적화 문제에서 PSO, ACO, 유전 알고리즘, 그래디언트 기반 옵티마이저 중 무엇을 고를지 결정하는 데 도움을 줍니다.

배포 전 확인

• 작게 시작합니다(Start small). 입자 1020개, 이터레이션 2050회로 시작합니다. 수렴 곡선이 분명한 개선을 보일 때만 규모를 키웁니다.
• 이터레이션마다 페로몬과 g_best를 로그로 남깁니다. 자취 없이 군집 옵티마이저를 디버깅하는 것은 매우 고통스럽습니다.
• 품질 게이트로 업데이트를 통제합니다(Quality-gate updates). 특히 ACO 라우팅에서는 빠르지만 틀린 답을 내는 에이전트가 페로몬을 얻으면 안 됩니다.
• 분포가 바뀌면 감쇠를 재설정합니다(Reset decay on distribution shift). 평가 분포가 달라지면 오래된 페로몬은 더 이상 유효하지 않습니다. 페로몬을 초기화하거나 감쇠 속도를 일시적으로 두 배로 올립니다.
• 이터레이션당 비용에 상한을 둡니다. 이터레이션당 비용 지표를 별도로 출력합니다. 한 이터레이션에 $500이 들면서 0.5% 성능 개선만 얻는 PSO는 배포할 만한 가치가 없습니다.

연습문제

1. code/main.py를 실행하고 LMPSO의 수렴 과정을 관찰합니다. 집단 크기를 5, 10, 20, 50으로 바꿔봅니다. 어느 크기에서 수렴까지 걸리는 시간이 포화(saturate)됩니까? (쉬움)
2. "재앙적 표류" 실험을 구현합니다. 30번째 이터레이션 이후 적합도 함수를 바꿉니다. PSO는 얼마나 빨리 적응합니까? p_best를 초기화하면 도움이 됩니까? (중간)
3. AMRO-S에 품질 게이트를 추가합니다. 평가 점수가 0.7 이상인 실행에만 페로몬을 남기도록 합니다. 게이트가 없는 버전과 비교하면 수렴이 어떻게 달라집니까? (중간)
4. LMPSO 논문(arXiv:2504.09247)을 읽습니다. 논문의 "프롬프트로서의 속도(velocity as a prompt)" 개념을 우리 코드의 수치 속도(numeric velocity)에 다시 매핑해 봅니다. 시뮬레이션에서 무엇이 사라졌고, 무엇이 보존되었습니까? (어려움)
5. AMRO-S 논문(arXiv:2603.12933)을 읽습니다. 분리된 "추론 빠른 경로(inference fast-path)"와 비동기 페로몬 업데이트를 구현합니다. 지속적인 부하 상황에서 시스템 지연 시간이 어떻게 달라집니까? (어려움)

핵심 용어

더 읽을거리

• Kennedy & Eberhart — Particle Swarm Optimization — 1995년 PSO 원전 논문입니다.
• Dorigo — Ant Colony Optimization — 1992년 ACO의 기초입니다.
• LMPSO — Language Model Particle Swarm Optimization — 구조화된 LLM 출력을 위한 PSO입니다.
• Model Swarms — gradient-free LLM expert optimization — 모델 가중치 부분공간 위의 PSO입니다.
• AMRO-S — ant-colony multi-agent routing — 품질 게이트가 적용된 페로몬 기반 라우팅입니다.