X-Tree가 에이전트 궤적을 재사용 가능한 스킬 트리로 토큰화한다

무엇인가

이 논문이 푸는 문제는 멀티스텝 에이전트 학습이 액션을 평평한 스트림으로 취급한다는 점이다. SFT와 RLVR은 모든 토큰에 같은 가중치를 주기 때문에, browse-and-select나 pick-up-and-move처럼 과제를 넘나들며 반복되는 하위 절차의 계층 구조를 목적함수가 쓰지 않는다. 저자들은 이 구조가 데이터 안에 이미 존재하는데도 학습이 이를 활용하지 않아, 같은 궤적에서 얻을 수 있는 것보다 적게 뽑아낸다고 본다. 문제는 경험이 희소하다는 것이다. 궤적은 사람이 수집하거나 모델이 합성·검증해야 하고, 환경과 과제, 검증기를 따로 만들어야 해서 웹 텍스트처럼 확장되지 않는다. 최근 에이전트들이 LLM이 쓴 스킬을 컨텍스트에 넣어 이 구조를 쓰긴 하지만, 가중치에는 아무것도 압축되지 않아 검색 이상으로 일반화하지 못한다.

어떻게 동작하나

제안 방법 X-Tree는 텍스트 BPE 토크나이저에서 출발한다. 문자 스트림을 빈도 기반으로 병합해 어휘를 만드는 방식을 경험에 적용하되 두 가지를 바꾼다. 먼저 각 raw action(thought 제외)을 verb<role> 형태의 타입 토큰으로 정규화한다. 예를 들어 fill(bid,'2/2/26')은 type<date>가 되고, element id나 객체 이름 같은 값은 제거된다. 구조적으로 동일한 액션이 같은 심볼을 공유하게 만들어 반복을 보이게 하는 것이다. 다음으로 병합 기준을 재사용성으로 정의한다. 후보 쌍 uv에 대해 X-Score = f_uv(인접 등장 횟수) × (ℓ_u+ℓ_v)^p_ℓ(확장 길이) × (succ(uv)+ε)^p_s(성공 에피소드 비율)로 점수를 매기고, p_ℓ과 p_s는 1로 둔다. 즉 길고 신뢰할 만하며 반복되는 구조가, 자주 나오지만 짧거나 실패가 잦은 쌍보다 우선한다. 병합은 f_uv - 1 > η(ℓ_u+ℓ_v)라는 압축 조건을 통과할 때만 수행하고, 최고 점수 쌍을 재귀적으로 합쳐 트리를 만든다. 결과 트리의 잎은 정규화된 액션이고 내부 노드는 하위 스킬의 조합인 스킬이며, 깊이 d_v는 자식 중 깊은 쪽보다 하나 크다. 전체 절차는 결정적이고 감사 가능하며 LLM 호출이 0회다. 궤적에 적용하면 반복되는 스킬 구간과 그렇지 않은 원시 액션으로 나뉜 top-level tiling을 얻는다.

무엇과 다른가

이 트리를 저자들은 세 가지 학습 설정에 넣는다. 첫째, 환경 없이 궤적만 있는 오프라인 RL에서는 각 X-Tree 노드가 하나의 학습 인스턴스가 된다. 골드 궤적에서 노드 앞부분을 프리픽스로 주고 정책이 최대 ℓ_v 스텝을 생성하며, 보상은 r = (1-α)·(1/ℓ_v)Σmatch_j + α·(1+γ·d_v)·c_v로 α=0.3, γ=0.5다. 앞항은 골드 경로를 얼마나 따라갔는지, 뒷항은 노드를 끝까지 완수했을 때 깊이에 비례해 주는 보너스다. 둘째, 환경과 검증기가 있는 온라인 RLVR에서는 적응적 스킬 보너스를 더한다. r_i = R_out(τ_i) + λ_g·Σ b_v이고 λ_g = λ_0·clip(1 - w_g/w_ref, 0, 1)로, 그룹 내 성공 비율 w_g가 0일 때 최대, w_ref에 도달하면 0이 된다. 검증기가 롤아웃을 구분하지 못할 때만 신호를 공급하고 구분이 가능해지면 스스로 사라지는 장치다. 셋째, on-policy self-distillation에서는 LLM이 쓴 스킬 뱅크 대신 X-Tree 렌더링을 self-teacher의 특권 컨텍스트로 넣는다. 토큰별 격차 δ_t에 로지스틱 게이트 g_t=σ(β·δ_t)를 걸어 교사가 더 확신하는 토큰에서만 증류하고, 계수 c=0.01로 RL 손실에 더한다.

어떻게 쓰나

WebArena 실험은 7.9k 궤적에서 256개 X-Tree 스킬을 마이닝하고, Qwen2.5-7B-Instruct로 절반 풀을 SFT한 뒤 나머지 절반의 X-Tree 노드로 GRPO를 한 스테이지 돌린다. 694개 결정적 태스크를 30스텝 상한으로 평가한 결과, SFT-Full(Go-Browse 레시피) 18.4 대비 22.9 성공률로 +4.5%p, 상대 24% 향상이다. 같은 RL 연산량을 SFT 2에폭 추가에 쓰면 +0.4에 그쳐 연산량 때문이 아님을 보인다. 사이트별로는 admin +6.4, 절차 비중이 큰 gitlab +5.2, shopping +4.9로 격차가 크고, 쿼리 작성 중심인 reddit·map·wiki에서는 줄어든다. 어블레이션에서 전체 궤적으로 같은 RL을 하면 -3.0, X-Tree의 개수·길이 분포만 맞춘 random span은 -3.4, X-Score를 무작위로 바꾼 random tree는 -5.0으로 SFT-only(18.4) 아래로 떨어진다. 완료 보너스를 뺀 plain mixing은 -2.2, 깊이별 커리큘럼은 -1.7, 궤적 단위 이진 보상은 -4.7이다.

전제와 한계

ScienceWorld에서는 1,673개 궤적에서 80개 스킬을 뽑아 1.5B·3B·7B 세 스케일에서 200개 궤적 SFT 워밍스타트 후 GRPO를 돌린다. 본 과제(G0·G1)에서 최대 +4.9%p, 학습에 쓰지 않은 과제(G2)에서도 모든 스케일에서 앞서며 최대 +3.9%p다. 롤아웃 수 n을 바꾼 실험에서는 12개 칸 중 11개에서 우세했고, n=4에서 격차가 3.6에서 4.4로 커지다 n이 커지면 좁혀진다. λ_g 노출은 n=2에서 0.50, n=16에서 0.18~0.26으로 떨어져 보너스가 정책이 약할 때 작동하고 강해지면 사라짐을 확인한다. WebShop에서는 1,824개 궤적에서 48개 스킬을 뽑아 512개 held-out 에피소드로 평가해 성공률 최대 +3.6%p, graded score 최대 +4.6%p를 얻는다. 자원을 동일하게 맞춘 실험에서도 SFT 데이터만으로 마이닝한 X-Tree가 앞서고, 100개 궤적만으로 만든 X-Tree가 500개 SFT 워밍스타트의 결과 보상 73.8을 75.2로 넘는다. OPSD에서는 LLM이 쓴 스킬 뱅크(gpt-oss-120b, GPT-o3)와 대등하거나 앞서며 ScienceWorld 최대 +3.7, WebShop 최대 +1.7을 기록했고, 7B에서 OPSD가 ScienceWorld +5.8%p, WebShop graded score +4.4를 낸다.

실무 관점에서 이 논문이 쓸모 있는 지점은 세 가지다. 환경과 검증기가 없어 궤적만 쌓여 있는 상황이면 오프라인 RL 통합이 곧바로 적용 대상이고, RLVR 초반이나 롤아웃 수가 작아 보상이 희소한 구간에서는 적응적 스킬 보너스가 그 구간만 메워준다. self-distillation에서 LLM으로 스킬 뱅크를 만드는 비용을 없애고 싶을 때도 대안이 된다. 도입 전에 확인할 것은 정규화 템플릿이 자기 도메인 액션 공간을 얼마나 덮는지, X-Score의 p_ℓ·p_s·η와 압축 임계, λ_0와 w_ref 같은 환경별 하이퍼파라미터, 그리고 마이닝 코퍼스가 평가 과제를 누출하지 않는지다. 저자들도 마이닝 코퍼스에서 held-out 과제를 제외해도 결과가 견고하다는 분석을 별도로 제시한다.

저자들이 밝힌 한계는 분명하다. X-Tree를 고정된 풀에서 한 번만 마이닝하고 학습 중에는 개선하지 않는다. 정책 자신의 궤적에서 마이닝하면 구조와 정책이 루프를 돌며 함께 좋아질 수 있다는 것이 저자들의 전망이다. 또 세 가지 통합을 각각 한 설정에서만 평가했고 결코 결합하지 않았다. 하나의 모델을 X-Tree 노드로 학습시키면서 동시에 X-Tree 보너스를 받고 X-Tree로부터 증류하는 구성은 미래 과제로 남겨둔다. 근본적으로 X-Tree는 이미 존재하는 경험을 재조직할 뿐 새 경험을 만들지 않는다. 다만 어떤 쌍이 반복되고 어떤 쌍이 성공하는지 기록하기 때문에, 코퍼스가 얇은 지점을 표시해 어떤 궤적을 합성해 채워야 하는지 알려줄 수 있다고 저자들은 덧붙인다.