기술 요약: BONSAI – 스킬에 대한 진화 가능성 유도 트리 탐색

1. 문제 정의

본 논문은 **동결된 에이전트(frozen agents)**를 위한 스킬(skills) 최적화 문제를 다룹니다. 여기서 "스킬"이란 단순한 프롬프트 템플릿이 아니라, 가중치를 업데이트할 수 없는 동결된 대규모 언어 모델(LLM)을 안내하는 자연어 문서(현장 매뉴얼 역할)로 정의됩니다. 에이전트는 경험으로부터 학습할 수 없으므로, 결여된 모든 능력은 반드시 스킬 텍스트 내에 인코딩되어야 합니다.

표준적인 스킬 최적화 방식은 다음과 같은 반복 루프를 따릅니다: 에이전트의 실패를 바탕으로 스킬을 편집하고, 홀드아웃(held-out) 태스크에서 테스트하며, 점수를 개선하는 편집 사항을 유지합니다. 저자들은 이 방법의 결정적인 사각지대를 지적합니다. 단일 검증 점수만으로는 광범위한 고원(broad plateau) 위에 놓인 문서(추가 편집에도 견고함)와 좁은 첨단(narrow spike) 위에 놓인 문서(과적합되어 취약함)를 구분할 수 없다는 점입니다. 좁은 첨단 위의 문서는 높은 점수를 기록할 수 있지만, 이는 데드 엔드(dead end)가 될 수 있습니다. 왜냐하면 추가적인 편집이 기존의 능력을 파괴하는 경향이 있기 때문입니다. 기존 방식들은 추가적인 계산 비용을 들이지 않고도 스킬 영역의 "진화 가능성(evolvability)"—즉, 변이를 통해 실행 가능한 변형을 생성할 수 있는 능력—을 측정하는 방법이 부족합니다.

2. 방법론: BONSAI

BONSAI(Bonsai Optimisation via Natural-language Search and Adaptive Iteration)는 스킬 최적화를 즉각적인 적합도(fitness)가 아닌 **진화 가능성(evolvability)**에 의해 유도되는 **몬테카를로 트리 탐색(MCTS)**으로 재구성합니다.

핵심 구성 요소

• 모델: 두 개의 동결된 모델이 사용됩니다.
  • Performer (수행자): 스킬에 따라 태스크를 수행하는 동결된 에이전트 (예: granite-4.1-30b).
  • Optimizer (최적화 도구): Performer의 실패를 바탕으로 스킬을 재작성하는 두 번째 동결된 모델 (예: DeepSeek-V3.2).
• 트리 구조: 스킬은 루트 노드가 시드(seed) 문서인 트리 형태로 조직됩니다. 모든 엣지는 부모 노드의 변이(reflective rewrite)를 나타냅니다. 이 구조는 문서 공간에 이웃 토폴로지(neighborhood topology)를 부여합니다.

주요 지표

• 적합도 ($v(n)$): 노드 $n$에 있는 문서의 검증 점수입니다.
• 진화 가능성 ($Q(n)$): 스킬의 변이 이웃(mutational neighborhood)에 대한 기대 적합도로 정의됩니다. 이는 노드의 혈통(lineage, 해당 노드와 그 모든 자식 노드)의 평균 적합도로 추정됩니다.
  $$Q(n) = \frac{1}{m(n)} \sum_{s \in L(n)} v(s)$$
  여기서 $L(n)$은 혈통이며, $m(n)$은 점수가 매겨진 구성원의 수입니다.
• 취약성 ($\sigma(n)$): 현재 적합도와 진화 가능성 사이의 차이입니다: $\sigma(n) = v(n) - Q(n)$.
  • $\sigma > 0$: 취약한 상태(brittle, overfit peak)를 나타냅니다 (현재 점수가 이웃 평균보다 높음).
  • $\sigma \le 0$: 진화 가능한 영역을 나타냅니다 (이웃이 현재 점수를 유지하거나 개선함).

탐색 알고리즘

탐색은 상한 신뢰 구간(Upper Confidence Bound, UCB) 선택 규칙을 사용하여 반복적으로 진행됩니다:
$$U(s) = v(s) + \lambda(Q(s) - v(s)) + c\sqrt{\frac{\ln N(p)}{N(s)}}$$

• 착취 (Exploitation): $\lambda(Q(s) - v(s))$ 항은 탐색을 높은 진화 가능성을 가진 영역으로 유도합니다. $\lambda=1$일 때, 탐색은 순수 적합도 $v(s)$보다 $Q(s)$(진화 가능성)를 우선시합니다.
• 탐험 (Exploration): 표준 UCB 항은 약한 브랜치들이 다시 방문되도록 보장합니다.
• 수용 (Acceptance): 제안된 자식 노드는 작은 훈련 미니배치에서 엄격하게 개선될 경우에만 수용됩니다 (식 4).
• 백업 (Backup): 수용된 자식은 혈통 통계($N, m, W$)를 업데이트합니다. 거부된 변이는 방문 횟수 $N$만 업데이트하여, 실패한 재작성이 특정 영역의 진화 가능성 추정치를 인위적으로 떨어뜨리는 것을 방지합니다.
• 확장 (Widening): 노드는 점수가 매겨진 샘플 수에 기반하여 하위 선형적인 자식 노드 수용 능력을 가지며, 이를 통해 탐색이 넓게 퍼지기보다 깊게 진행되도록 보장합니다.

그래프팅 (Grafting, 선택적 연산자)

서로 다른 브랜치 간의 능력 파편화 문제를 해결하기 위해, BONSAI는 그래프트(graft) 연산자를 포함합니다. 만약 노드 $A$가 노드 $B$가 가진 능력이 결여되어 있다면(훈련 데이터에 대한 태스크별 점수 비교를 통해 결정됨), 최적화 도구는 $A$를 $B$의 기법을 포함하도록 재작성하라는 요청을 받습니다. 이때 기증자 $B$는 증거로서 작용할 뿐 조상(ancestry)이 아니며, 방문 업데이트를 받지 않습니다.

배포 (Shipping)

예산을 모두 소진하면, BONSAI는 가장 높은 진화 가능성을 가진 문서가 아니라, 가장 높은 검증 점수를 가진 단일 문서($\arg\max v(n)$)를 배포합니다. 이는 최종 출력이 발견된 최고의 성능을 가진 문서임을 보장하며, 진화 가능성은 오직 탐색 예산을 유도하는 메커니즘으로서만 기능합니다.

3. 주요 기여

1. 유도 지표로서의 진화 가능성: 저자들은 스킬 최적화에서 (현재의 적합도와 구별되는) 변이 하에서의 강건성(진화 가능성)이 결정적인 속성임을 식별했습니다.
2. 비용 없는 추정: 추가적인 모델 호출 없이도 진화 가능성($Q$)을 측정할 수 있는 방법을 제안합니다. 이는 탐색 과정에서 이미 지불된 적합도 점수를 재사용하여 변이 이웃의 품질을 추정합니다.
3. 트리 기반 탐색 프레임워크: BONSAI는 순서 없는 후보 집합을 이웃 속성을 측정하고 최적화할 수 있는 구조화된 탐색 공간으로 변환합니다.
4. 비대칭적 능력 전이: 그래프트 연산자의 도입은 문서를 병합하지 않고도 특정 능력을 계보 간에 전이할 수 있게 하여, 스킬이 서로 다른 방향으로 분화되는 문제를 해결합니다.

4. 실험 결과

프레임워크는 30B 규모의 동결된 performer와 DeepSeek-V3.2 optimizer를 사용하여 세 가지 벤치마크에서 평가되었습니다.

• SpreadsheetBench: BONSAI는 시드 문서를 5.71 포인트 개선했으며, 예산이 동일한 베이스라인인 GEPA보다 2.14 포인트 앞섰습니다. 그래프팅을 활성화했을 때 **25.00%**의 정확도에 도달했습니다.
• SearchQA: BONSAI는 시드 대비 6.57 포인트를 개선했으며, GEPA(78.29%)를 0.71 포인트 앞질렀습니다 (79.00%).
• LiveMathematicianBench: BONSAI는 **64.91%**의 정확도를 달성하여, 시드(28.23%)를 크게 앞질렀으며 GEPA를 8.77 포인트 차이로 이겼습니다.
• SkillOpt와의 비교: 모든 벤치마크에서 BONSAI는 두 번째 베이스라인인 SkillOpt보다 평균 3.97 포인트 높은 성능을 보였습니다. 저자들은 SkillOpt의 성과 저조 원인을 근본적인 궤적을 보지 못한 채 편집 사항을 압축해버리는 집계 단계 탓으로 돌렸습니다.
• 절제 실험 (진화 가능성 vs 탐욕적 방식): 선택 신호를 순수 탐욕적 적합도($\lambda=0$)로 변경했을 때, 모든 벤치마크에서 성능이 크게 하락했습니다 (예: LiveMathematicianBench에서 -7.02 포인트). 이는 진화 가능성에 의한 유도가 성공의 주요 동력임을 확인시켜 줍니다.

5. 의의 및 주장

본 논문은 BONSAI가 스킬 공간에서 개선이 지속되는 영역으로 탐색 예산을 성공적으로 유도하며, 좁고 과적합된 첨단에 갇히지 않는다는 점을 입증합니다. 진화 가능성을 적합도와 별개의 속성으로 취급함으로써, 이 방법은 표준적인 점수 기반 최적화의 "사각지대"를 피합니다.

저자들은 이러한 개선이 표준적인 '더 나으면 수용(accept-if-better)' 루프 이상의 추가 비용 없이 달성되었다는 점을 강조합니다. 진화 가능성 지표는 기존 탐색 데이터를 통해 도출되기 때문입니다. 이 프레임워크는 동결된 에이전트에게 있어 스킬 공간의 "지형"(진화할 수 있는 능력)이 현재의 "고도"(점수)만큼이나 중요하다는 것을 보여줍니다. 결과적으로, 스킬 최적화를 변이 강건성에 의해 유도되는 트리 탐색으로 구성하는 것이 기존의 성찰적 프롬프트 진화나 학습 가능한 상태(trainable-state) 접근 방식보다 우수한 일반화 성능을 제공함을 시사합니다.