프롬프트 선택 최적화: 최적 암 식별(Best-Arm Identification)로 LLM 평가 예산 아끼기

핵심 메시지

• 여러 프롬프트를 모두 같은 횟수로 평가하는 균등 배분은, 이미 나쁘다는 게 드러난 후보에까지 예산을 계속 쓰기 때문에 낭비가 크다.
• 이 문제는 멀티암드 밴딧의 '최적 암 식별(best-arm identification)'로 최적 해법이 잘 연구돼 있으며, 핵심은 성능이 낮은 후보를 초기에 빨리 제거하는 것이다.
• 대표 알고리즘인 연속 제거(Successive Rejects)와 순차 반감(Sequential Halving)은 구현이 간단하면서도 균등 배분보다 이론적으로 우월하다.
• 탐험과 활용을 절충하는 epsilon-greedy나 UCB 같은 고전 밴딧 알고리즘은 최적 암 식별에는 적합하지 않다.
• 이 방식은 프롬프트뿐 아니라 모델·하이퍼파라미터처럼 평가 비용이 비싼 모든 선택 문제에 그대로 적용된다.

쉽게 이해하기

20개의 시스템 프롬프트 버전을 만들어 두고 그중 배포할 최적안을 고른다고 하자. 평가 예산이 500회로 제한돼 있을 때 가장 흔한 방식은 각 프롬프트를 25회씩 균등하게 돌려 평균 점수가 가장 높은 것을 고르는 것이다. 영상은 거의 모두가 이렇게 하지만, 이것이 사실은 돈 낭비라고 지적한다.

몇 번만 평가해도 어떤 후보가 형편없는지는 금방 드러난다. 그런데 균등 배분은 이미 나쁘다고 판명된 후보에도 남은 예산을 계속 쏟는다. 반대로 상위 2~3개 유력 후보는 서로 비슷해 보여 정작 무엇이 최고인지 가리려면 더 많은 시도가 필요한데, 예산이 엉뚱한 곳에서 소진되는 것이다.

이 문제는 수학적으로 잘 연구된 멀티암드 밴딧 문제, 그중에서도 '최적 암 식별'에 해당한다. 여러 슬롯머신(암) 각각이 고정돼 있지만 알 수 없는 분포에서 값을 내놓고, 정해진 횟수만큼 당긴 뒤 평균이 가장 높은 암을 찾아내는 것이 목표다. 총 N회 안에서 최적 암을 찾을 확률을 최대화하는 '고정 예산' 변형이 가장 실용적이며, 원하는 신뢰도를 최소 횟수로 달성하는 '고정 신뢰도' 변형은 이론 분석이 깔끔해 문헌에서 자주 쓰인다.

연속 제거(Successive Rejects)는 예산을 K-1개 단계로 나눠, 각 단계에서 남은 암을 균등하게 당긴 뒤 가장 낮은 하나를 탈락시켜 마지막에 하나만 남긴다. 순차 반감(Sequential Halving)은 단계를 log2(K)개로 나누고 매 단계마다 하위 절반을 한꺼번에 제거해 더 공격적으로 후보를 줄인다. 두 알고리즘 모두 '못한 후보를 먼저 빨리 걸러내고, 남은 예산을 상위 후보 구별에 집중한다'는 통찰을 공유한다.

오차 분석은 이 이점을 정량적으로 보여준다. 각 암과 최적 암의 점수 차이를 갭(delta), 갭들의 역수 합을 난이도(H)로 정의하면, 균등 배분과 순차 반감 모두 시도 횟수가 늘수록 오차가 지수적으로 감소한다. 결정적 차이는 암 개수 K의 영향이다. 균등 배분은 오차식 분모에 K가 들어가 명백히 나쁜 암을 100개 추가해도 수렴 속도가 일률적으로 느려지지만, 순차 반감은 분모에 K 대신 난이도 H가 들어가 빨리 제거되는 나쁜 암은 성능에 거의 영향을 주지 않는다.

NeurIPS 2024에서 발표된 'Triple' 논문은 프롬프트 선택을 멀티암드 밴딧과 연결한다. 프롬프트 최적화 시스템은 보통 LLM으로 여러 프롬프트를 생성한 뒤(APE) 실패 원인을 분석해 새 프롬프트를 만들며 개선하는데(APO), 어느 경우든 마지막에는 후보 풀에서 최적 프롬프트를 골라야 한다. 실험에서 최적 암 식별 알고리즘은 균등 선택과 표준 밴딧을 일관되게 앞섰고, APE 파이프라인에서는 연속 제거가 균등 선택보다, APO에서는 UCB보다 더 나은 평균 성능 순위를 기록했다.

주요 인사이트

• 핵심 원리는 단순하다. '나쁜 후보를 초기에 빨리 탈락시켜 남은 예산을 유력 후보 구별에 몰아준다'는 것이며, 연속 제거와 순차 반감은 이 원리를 각각 다른 강도로 구현한 것이다.
• 탐험·활용 균형을 추구하는 UCB나 epsilon-greedy는 좋다고 알려진 암을 자주 당겨 보상을 얻으려 하지만, 최적 암 식별에서는 보상을 챙길 필요가 없으므로 오히려 부적합하다는 점을 구분해야 한다.
• 순차 반감의 오차식에 K가 아니라 난이도 H가 들어간다는 사실은, '명백히 나쁜 후보를 많이 늘려도 손해가 거의 없다'는 실용적 함의를 준다. 실제로 최적 암과 근접한 후보만 문제를 어렵게 만든다.
• 이 기법은 프롬프트 선택을 넘어, 여러 모델이나 하이퍼파라미터 조합처럼 한 번의 평가가 비싼 모든 선택 문제에 드롭인 방식으로 적용해 균등 평가보다 나은 결과를 얻을 수 있다.

자주 묻는 질문

관련 AI 소식