[논문리뷰] X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization (경험을 토큰화하는 에이전트 스킬 트리)

About this offer

(출처: arXiv:2609.32993, Figure 2) X-Tree: Tokenizing Reusable Experience for Efficient Agent Generalization 저자 : Sitao Cheng, Xunjian Yin, Zhiyuan Sun, Yuxuan Li, Ruiwen Zhou, Xiangru Jian, Victor Zhong 소속 : University of Waterloo, Duke University, National University of Singapore 공개일 : 2026년 9월 26일 (arXiv v1, cs.AI) arXiv : https://arxiv.org/abs/2609.32993 코드 : https://github.com/sitaocheng/X-Tree · 프로젝트 페이지 : https://sitaocheng.github.io/xtree 분류 : LLM Agent / Reinforcement Learning / Skill Discovery / Experience Reuse 🔖 TL;DR (한눈에) 멀티스텝 에이전트 학습은 궤적(trajectory)을 평평한 액션 스트림 으로 소비한다. SFT와 RLVR은 모든 토큰에 같은 가중치를 주기 때문에, 과제마다 반복되는 하위 절차(sub-procedure)의 계층 구조를 전혀 활용하지 못한다 . 기존 에이전트 하네스는 이 구조를 쓰긴 하지만 LLM이 글로 써낸 스킬을 프롬프트에 넣는 방식 이라, 효과가 "검색해서 끼워넣기" 범위를 넘지 못하고 가중치에는 남지 않는다 . X-Tree는 LLM 호출 0회 로, 텍스트 토크나이저가 빈도만 세어 어휘를 만드는 것과 같은 방식으로 궤적에서 계층을 캐낸다. 액션을 verb⟨role⟩ 형태로 정규화한 뒤 재사용성 점수(X-Score) 로 인접 쌍을 BPE처럼 병합해 트리를 만든다. 각 노드는 "자주 등장하고 성공과 결부된 스킬이 하위 스킬로 어떻게 조립되는가"를 담고, 이를 데이터(오프라인 RL) · 보상(온라인 RLVR) · 컨텍스트(OPSD) 세 경로로 학습에 투입한다. WebArena·ScienceWorld·WebShop 3개 환경, 1.5B/3B/7B 3개 스케일에서 동일 데이터·동일 예산 조건으로 기존 레시피를 앞섰다(WebArena +4.5 SR, ScienceWorld +5.8 SR, WebShop +4.1 success). 특히 무작위 트리(17.9 SR)가 트리를 아예 안 쓴 경우(19.9 SR)보다 나빴다 — 성능이 "쪼개기" 자체가 아니라 구조의 질 에서 나온다는 증거. 한 줄 요약 : 에이전트 궤적 속에 암묵적으로 깔려 있던 "재사용 가능한 절차"를, LLM 없이 통계적 병합만으로 명시적 스킬 트리로 뽑아내고, 그 트리를 데이터·보상·컨텍스트 세 방향에서 모델 가중치에 심는 방법. 📄 초록(Abstract) 완역 멀티스텝 에이전트는 평평한 액션 스트림 위에서 학습된다. SFT와 RLVR은 모든 토큰에 균일한 가중치를 부여하며, 과제들에 걸쳐 반복적으로 나타나는 하위 절차들 — 즉 사람이 재사용 가능한 루틴으로부터 하향식(top-down)으로 계획을 세울 수 있게 해주는 그 계층 구조 — 을 무시한다. 이 구조는 쓰이지 않은 채 방치되고, 평평한 학습은 각각의 희소한 궤적을 그 내용이 허용하는 수준보다 덜 활용한다. 최근의 에이전트들은 그 구조를 실제로 사용하기는 하지만, 오직 LLM이 작성한 스킬을 컨텍스트에 넣는 형태로만 사용하며 가중치에는 결코 반영하지 않기 때문에, 그 이득이 검색(retrieval)의 범위를 넘어 일반화되지 않는다. 우리는 대신 이 계층 구조를 데이터 자체로부터 복원하여 그 위에서 학습하며, 이때 LLM 호출은 전혀 사용하지 않는다. 오직 세는 것만으로 어휘를 구축하는 텍스트 토크나이저를 따라, 우리는 액션 구간(span)들을 재사용성 기준으로 점수화하고 정규화된 액션들을 병합하여 재사용 가능한 경험 트리(reusable eXperience tree, X-Tree)를 만든다. 각 X-Tree 노드는 자주 등장하며 성공을 담지하는(success-bearing) 스킬이 하위 스킬들로부터 어떻게 구성되는지를 포착하여, 효율적인 일반화를 유도한다. 우리는 X-Tree를 세 가지 학습 설정에 통합한다: 각 노드를 하나의 학습 인스턴스로 쓰는 오프라인 RL, 적응적 스킬 보너스를 쓰는 온라인 RLVR, 그리고 X-Tree를 자기-교사(self-teacher)의 특권적 컨텍스트로 쓰는 온-폴리시 자기증류(on-policy self-distillation). WebArena, ScienceWorld, WebShop에서 세 가지 모델 스케일에 걸쳐, X-Tree는 동일한 데이터와 예산 조건에서 표준 레시피를 최대 WebArena 4.5% SR, ScienceWorld 5.8% SR, WebShop 4.1% success만큼 개선한다. 대조 분석들은 그 이득이 X-Tree의 구조와 세 가지 통합 방식에서 비롯됨을 보여준다. 요약 정리 : 저자들의 진단은 "데이터가 부족한 게 아니라, 있는 데이터를 평평하게 소비해서 덜 뽑아먹고 있다"는 것이다. 해법은 궤적에서 반복·성공 패턴을 통계적으로 병합해 스킬 계층(X-Tree)을 만드는 것. 핵심 차별점은 두 가지로, (1) 스킬 추출에 LLM을 쓰지 않아 결정론적이고 감사(audit) 가능하며, (2) 스킬을 프롬프트에 끼워넣는 데 그치지 않고 데이터·보상·컨텍스트 세 경로로 가중치에 학습시킨다 는 점이다. 🧩 왜 이 문제가 중요한가 (배경) 에이전트를 학습시킬 때 가장 비싼 자원은 GPU가 아니라 궤적 이다. 웹 환경에서 성공한 멀티스텝 궤적 하나를 얻으려면 긴 롤아웃과 검증이 필요하고, 사람이 라벨링하면 더 비싸다. 그런데 이 귀한 궤적을 학습에 넣는 방식은 지금까지 거의 한 가지였다. 액션을 토큰 시퀀스로 늘어놓고 SFT로 따라 하게 하거나, 에피소드 끝의 성공/실패 하나로 RLVR을 돌리는 것이다. 문제는 이 두 방식 모두 궤적을 구조 없는 긴 끈 으로 취급한다는 데 있다. 웹 에이전트가 쇼핑 사이트에서 "검색창에 질의를 입력하고 → 결과에서 상품을 고르고 → 옵션을 선택하고 → 구매"를 수행했다면, 이 네 단계는 과제가 바뀌어도 거의 그대로 재등장하는 덩어리 다. 사람은 이런 덩어리를 "루틴"으로 묶어 기억하고, 새 과제를 만나면 루틴 단위로 하향식 계획을 세운다. 반면 평평한 학습은 click 이라는 토큰 하나하나에 같은 무게를 둘 뿐, "이 네 개가 하나의 단위다"라는 사실을 모델에 알려주지 않는다. 이 지점이 바로 암묵지(tacit knowledge)의 데이터화 문제와 맞닿는다. 성공한 궤적 안에는 "이 환경에서 무엇이 통하는 절차인가"라는 지식이 이미 들어 있지만, 그것은 액션 나열 속에 암묵적으로 흩어져 있다. 명시적으로 꺼내 쓰려면 누군가 구조화해야 한다. 최근 연구들(AWM, Voyager, SkillWeaver 등)의 답은 "LLM에게 궤적을 읽히고 스킬을 글로 쓰게 하라"였다. 이 방식은 작동하지만 세 가지 비용을 치른다. 첫째, 스킬 추출 단계마다 LLM 호출 비용 이 든다. 둘째, LLM이 써낸 스킬 설명은 비결정론적이고 검증하기 어렵다 . 셋째, 그리고 가장 중요하게, 그 스킬은 추론 시점에 프롬프트로 검색해 넣어야만 효과가 있다. 모델 가중치는 스킬을 배우지 못했으므로, 검색이 실패하거나 컨텍스트에서 빠지면 이득도 사라진다. X-Tree는 이 세 비용을 동시에 공격한다. "LLM에게 요약을 시키지 말고, 토크나이저처럼 세기만 하라"는 것이 출발점이다. BPE가 코퍼스에서 자주 붙어 나오는 문자 쌍을 병합해 서브워드 어휘를 만드는 것처럼, 자주 붙어 나오고 성공과 결부된 액션 쌍을 병합해 스킬 어휘를 만든다. 그리고 그 어휘를 프롬프트가 아니라 학습 신호 로 쓴다. 🔬 방법론 X-Tree는 크게 두 부분이다. 궤적 풀에서 트리를 캐내는 마이닝 단계 , 그리고 그 트리를 학습에 투입하는 세 가지 통합 방식 이다. (출처: arXiv:2609.32993, Figure 1) 1단계: 액션 정규화 (Canonicalization) 원시 액션을 그대로 세면 아무것도 반복되지 않는다. click(element_id=4821) 과 click(element_id=7733) 은 문자열로는 다른 액션이지만, 추상 수준에서는 둘 다 "링크를 클릭했다"다. 그래서 각 액션을 verb⟨role⟩ 형태의 타입 토큰으로 바꾼다. verb : 액션의 함수 이름에서 가져온다. role : 그 verb가 작용하는 대상의 클래스. WebArena에서는 접근성 트리(accessibility tree)의 role을, ScienceWorld에서는 9개 객체 클래스 어휘(door, instrument, paint, container, device, plant, animal, substance, location)를 쓴다. slot : element ID, 입력한 텍스트, 옵션 값 같은 구체적 값은 심볼에서 제거하되 따로 저장한다 . 그래서 마이닝이 끝난 뒤에도 원래 값을 복원할 수 있다. 에이전트의 thought는 아예 제외한다. 예를 들어 WebArena에서 fill 과 type 은 모두 type 으로, goto / go_back / go_forward 는 모두 navigate 로 접힌다. 중요한 점은 이 매핑이 환경별로 액션 스페이스를 보고 한 번 작성하는 고정 템플릿 이라는 것이다. 학습도, LLM 호출도 없다. 2단계: X-Score로 병합 (Eq. 1) 인접한 두 심볼 u, v (각각 원시 액션이거나 이전 병합으로 만들어진 노드)에 대해 병합 후보 uv 의 점수를 이렇게 매긴다. X(u, v) = f_uv · (l_u + l_v)^{p_l} · (succ(uv) + ε)^{p_s} 세 항의 직관은 각각 반복성 · 길이 · 성공 이다. f_uv : 코퍼스 전체에서 (u,v) 가 인접해 등장한 횟수 → 자주 쓰이는 쌍일수록 높다. l_u + l_v : 후보가 펼쳐지는 원시 액션 개수(원시 액션은 l=1) → 긴 덩어리를 선호한다. succ(uv) : 그 f_uv 번의 등장 중 성공한 에피소드에 속한 비율 → 성공과 결부된 패턴을 선호한다. p_l , p_s : 길이와 성공의 가중 지수. 주요 3개 환경에서 p_l = 1, p_s = 1 , MiniWoB++에서는 p_s = 1.5 . ε = 0.001 . 이 공식의 효과는 명확하다. 길고 믿을 만하며 반복되는 쌍이, 자주 나오지만 짧거나 실패와 얽힌 쌍을 이긴다. 단순 빈도 기반 BPE와 결정적으로 다른 지점이 바로 succ 항이다. 여기에 압축 제약 이 붙는다. f_uv − 1 > η · (l_u + l_v) 병합은 코퍼스에서 f_uv − 1 개의 심볼 등장을 없애는 대신 길이 l_u + l_v 의 어휘 항목 하나를 추가한다. η 는 그 항목의 비용을 정한다. 이 제약이 없으면 코퍼스가 소수의 거대한 심볼로 붕괴한다. 3단계: 트리 구축 초기화 — 각 궤적을 정규화된 원시 액션 시퀀스로 두고, 원시 액션을 리프로 삼는다. 카운트 — 현재 코퍼스에서 모든 인접 쌍의 f_uv , 길이, succ 를 센다. 필터 — 압축 제약과 함께 빈도( f_min ), 길이( L_max ), 성공률( s_min ), 과제 유형 수( T_min ) 필터를 통과한 후보만 남긴다. 선택 — X-Score가 가장 높은 후보를 고른다. 병합 — 노드 v = uv 를 만들고 자식을 (u, v) 로 기록한 뒤, 코퍼스의 해당 인접 등장들을 v 로 치환한다. 노드는 길이 l_v , 깊이 d_v , 등장 횟수, 성공률을 함께 들고 있다. 후보가 없거나 스킬 상한 K 에 도달하면 멈춘다. 그렇지 않으면 2번으로. 깊이는 조립 트리의 높이 다. 리프는 d=0 이고, 내부 노드는 d_v = 1 + max(자식들의 깊이) . 트리를 궤적에 적용할 때는 가장 큰 노드로 궤적을 타일링(tiling) 하고, 어떤 스킬에도 덮이지 않은 위치는 원시 토큰으로 남긴다. 이 타일링이 세 가지 통합 방식 모두가 쓰는 단위다. 환경별 마이닝 하이퍼파라미터는 다음과 같다. 기호 의미 WebArena ScienceWorld WebShop η 압축 비용 0.3 0.5 0.5 K 스킬 상한 256 80 60 L_max 최대 스킬 길이(액션) 12 8 8 f_min 최소 쌍 빈도 4 5 5 s_min 최소 스킬 성공률 0 0.9 0 T_min 스킬당 최소 과제 유형 수 1 2 1 실제로 캐낸 트리의 규모는 이렇다. 벤치마크 마이닝 궤적 수 원시 액션 타입 수 캐낸 스킬 수 WebArena 7,974 139 256 (상한 도달) ScienceWorld 1,673 84 80 (상한 도달) WebShop 1,824 17 48 (압축 제약에 걸림) WebArena 학습에 쓰인 노드 집합은 총 5,148개 로, 깊이 1이 약 3.5k, 깊이 2가 1.2k, 깊이 3이 0.4k다. ScienceWorld에서는 깊이 6까지 나타난다. (출처: arXiv:2609.32993, Figure 5) 위 그림이 이 방법의 정체를 가장 잘 보여준다. ScienceWorld의 "침실에서 미지의 물질 B의 온도를 측정해 50도 이상이면 초록 상자, 미만이면 파란 상자에 넣어라"라는 과제에서, 18개 액션이 4개의 X-Tree 노드와 2개의 원시 액션, 즉 6개 토큰으로 압축된다. 그중 S2(보라색)는 서로 다른 두 토큰 안에 중첩되어 재등장한다. 통합 1: 오프라인 RL (데이터로서의 X-Tree) 궤적의 위치 t 에 있는 각 X-Tree 노드 v 가 하나의 RL 인스턴스 가 된다. 정책은 정답 접두사 s_<t 를 조건으로 받아 최대 l_v 스텝을 생성한다. 각 스텝 j 에서 정답 액션과 대상 요소를 모두 맞추면 match_j = 1 이고, 첫 불일치에서 롤아웃을 중단 한다. 맞춘 스텝에 대해서는 기록된 정답 관측(observation)을 붙여준다 — 그래서 롤아웃이 존재하지 않는 관측을 상상하지 않는다(오프라인 안전성). 보상은 c_v = ∏_j match_j (모든 스텝을 맞췄을 때만 1)로 두고, r = (1 − α) · (1/l_v) Σ_j match_j + α · (1 + γ·d_v) · c_v α = 0.3 , γ = 0.5 . 첫 항은 정답 경로를 따라가는 데 주는 조밀한 크레딧 , 둘째 항은 깊이 d_v 에 비례하는 완주 보너스 다. 깊은 노드를 끝까지 맞추는 것이 더 큰 보상을 받는다는 점이 "계층적 보상"의 실체다. 통합 2: 온라인 RLVR (보상으로서의 X-Tree) 그룹 g 안의 롤아웃 τ_i 에 대해, r_i = R_out(τ_i) + λ_g · Σ_{v ∈ matched(τ_i)} b_v λ_g = λ0 · clip(1 − w_g / w_ref, 0, 1) w_g 는 그룹에서 성공한 롤아웃의 비율이다. 이 설계의 핵심은 스스로 사라지는(self-fading) 보너스 라는 점이다. 아무 롤아웃도 성공하지 못했을 때 보너스는 최대 강도 λ0 이고, 그룹 성공률이 w_ref 에 도달하면 0으로 떨어진다. 즉 검증자의 결과 신호가 쓸모 있어지는 순간 정확히 그 시점에 shaping 항이 사라진다 . 시간 기반 스케줄이 아니라 성공률 기반이라는 점이 중요하다. 실제로 측정된 후반 학습 노출도는 n=2에서 0.50, n=16에서 0.18~0.26으로 떨어진다. 노드 보너스 b_v 는 ScienceWorld에서 1 + 0.5·d_v (에피소드당 1회), WebShop에서 10 · s_v · k_v / T 다. 중첩 매치에서는 외부 노드가 자신의 b_v 에서 내부에 이미 지급된 최대 보너스를 뺀 값 을 받아, 스킬과 하위 스킬의 이중 계산을 막는다. 통합 3: 온-폴리시 자기증류 OPSD (컨텍스트로서의 X-Tree) 학생과 교사가 같은 가중치 다. 차이는 프롬프트뿐으로, 교사는 검색된 X-Tree 스킬이 앞에 붙은 특권적 컨텍스트 를 본다. 둘이 같은 샘플 응답 y 를 채점하므로 로그확률이 위치별로 정렬된다. δ_t = log π_θ̄(y_t | s^tea) − log π_θ(y_t | s^stu) g_t = σ(β · δ_t) L = L_GRPO(R_out) + c · (1/|y|) Σ_t g_t (log π_θ̄(y_t | s^tea) − log π_θ(y_t | s^stu)) 게이트 g_t 는 교사가 더 확신하는 토큰에서 1에 가깝고, 학생이 이미 잘 아는 토큰에서 0에 가깝다. c = 0.01 , ScienceWorld는 β = 5 , WebShop은 β = 0 (게이트가 상수 0.5, 즉 균일 증류). 이 설정이 영리한 이유는 완전히 공정한 비교 를 가능하게 하기 때문이다. 자기-교사가 읽는 스킬 뱅크만 바꾼다. LLM이 쓴 뱅크(ScienceWorld는 gpt-oss-120b, WebShop은 GPT-o3)냐, 렌더링된 X-Tree냐. 다른 모든 것은 동일하다. 📊 실험 결과 WebArena: 오프라인 RL (Qwen2.5-7B, 694개 결정론적 과제, 30스텝 상한, 3패스 평균) Method gitlab (187) shopping (158) admin (156) reddit (112) map (67) wiki (14) All (694) Qwen2.5-7B-Instruct (base) 6.4 7.8 7.7 2.4 9.0 2.4 6.5 Go-Browse (SFT-Full, 2 epochs) 16.8 21.7 22.9 16.4 10.4 7.1 18.4 SFT-Full, 4 epochs (compute 매칭) 17.5 19.4 24.4 16.1 13.4 11.9 18.8 Offline RL w/ Outcome reward 15.5 23.4 23.1 15.2 7.5 14.3 18.2 Offline RL w/ Random span 18.4 20.9 26.6 14.7 11.9 14.3 19.5 X-Tree, Plain mixing (all depths) 16.1 24.5 25.4 19.9 14.4 23.8 20.7 X-Tree, Curriculum (d=1→2) 17.8 21.5 28.6 20.8 12.4 23.8 21.2 X-Tree Full 22.0 26.6 29.3 18.8 10.4 14.3 22.9 전체 SR 22.9는 SFT-Full(2 epochs) 18.4 대비 +4.5 다. 사이트별로 보면 gitlab(16.8→22.0)과 admin(22.9→29.3)처럼 양식 입력과 메뉴 탐색이 반복되는 곳에서 이득이 크고, map(10.4→10.4)과 wiki(7.1→14.3, 다만 과제가 14개뿐)처럼 반복 구조가 약한 곳에서는 이득이 없거나 노이즈 수준이다. 재사용 가능한 절차가 실제로 존재하는 사이트에서만 작동한다 는 해석이 자연스럽다. 어블레이션: 이득은 어디서 오는가 Method SR Δ X-Tree Full 22.9 – 트리 구조 검증 Whole trajectory (트리 없음) 19.9 −3.0 Random span 19.5 −3.4 Random tree 17.9 −5.0 오프라인 RL 설계 검증 X-Tree Plain mixing 20.7 −2.2 X-Tree Curriculum (d=1→2) 21.2 −1.7 Binary outcome reward 18.2 −4.7 SFT-Full, 2 epochs 18.4 −4.5 SFT-Full, 4 epochs 18.8 −4.1 이 표에서 가장 의미 있는 숫자는 Random tree 17.9 다. 무작위로 만든 트리는 트리를 아예 쓰지 않은 경우(19.9)보다도 2.0 포인트 나쁘다 . 궤적을 잘게 쪼개 학습 인스턴스 수를 늘리는 것 자체는 효과가 없고, 오히려 해로울 수 있다는 뜻이다. 성능은 X-Score가 고른 구조의 질 에서 나온다. 참고로 무작위 트리는 노드의 88%가 길이 2인 반면, 캐낸 트리는 43%만 길이 2다. 온라인 RLVR: 롤아웃 수에 따른 스케일링 (ScienceWorld, 1.5B) n Setting G0 (seen) G1 (unseen variation) G2 (unseen task) 2 outcome-only 12.9 13.7 11.8 2 + X-Tree bonus 14.6 15.5 13.0 4 outcome-only 24.2 23.9 12.1 4 + X-Tree bonus 28.0 27.5 16.5 8 outcome-only 38.6 36.2 22.8 8 + X-Tree bonus 39.8 39.5 25.6 16 outcome-only 47.5 49.0 26.6 16 + X-Tr