구조적 검색(Structural retrieval)은 궤적 스냅샷 기반의 에이전트 실패 예측에서 기본 RAG보다 유망한 성능을 보여줍니다

KNN 투표를 사용하는 구조적 검색 엔진(Structural retrieval engine)은 기본 RAG(Retrieval-Augmented Generation)보다 유망한 신호를 보여줍니다. 홀드아웃 궤적(held-out trajectories)의 60단계 이후 스냅샷에 대해 평균 AUC = 0.705를 기록한 반면, 기본 RAG는 9%에서 100% 커버리지 사이의 어떤 코사인 임계값(cosine threshold)에서도 약 0.60 AUC에서 정체되었습니다.
결과는 예비적인 단계입니다. 단일 리포지토리(single-repo) 및 별도의 PR(distinct-PR) 조건(벤치마크 설계에서 다룸)으로 인해 평가 세트가 220개의 궤적으로 제한되어 있어, 95% 부트스트랩 신뢰 구간(bootstrap confidence intervals)이 겹치므로 더 큰 데이터셋에서 격차가 확인되어야 합니다. 다만, 충분한 공개 데이터셋을 찾는 것 자체가 여전히 해결되지 않은 문제입니다.

에이전트의 수와 궤적 데이터베이스가 증가함에 따라 새로운 검색 요구 사항이 나타나고 있습니다. 바로 텍스트 내용에 의한 의미적 유사성(semantically similar)이 아닌, 구조적으로 유사한(structurally similar) 궤적을 찾는 것입니다. 궤적의 구조, 즉 의미론과는 독립적인 결정과 결과의 시퀀스는 모니터링, 경험/성찰(experience / reflection) 파이프라인을 위한 필터링, 평가 및 기타 에이전트 인프라 계층에 유용한 신호를 전달합니다.
우리의 실험은 기본 RAG가 문서가 아닌 행동 시퀀스(action sequences)를 위해 설계되었기 때문에 이러한 구조적 신호를 놓친다는 것을 보여줍니다. 우리는 궤적을 타입이 지정된 요소(typed elements)의 시퀀스로 표현하는 접근 방식을 제안하며, 이를 오픈 소스 Python 패키지인 episodiq으로 구현하여 이 글의 마지막 부분에서 설명합니다.
이 글의 나머지 부분에서는 방법론과 지표(metric) 선택에 대해 다룹니다.

왜 궤적의 결과를 예측해야 하는가?

궤적에 대해 던질 수 있는 질문 중, 성공할 것인가 실패할 것인가 하는 질문은 현실과 대조하여 확인할 수 있다는 점에서 두드러집니다. 궤적 분석이 드러내는 대부분의 내용—어느 단계가 생산적이었는지, 에이전트가 어디서 흐름을 놓쳤는지, 어떤 행동 패턴이 형성되고 있는지—은 해석(interpretation)의 영역입니다. 유용하긴 하지만 외부의 정답(ground truth)이 없습니다. 실행이 성공할지 실패할지는 다릅니다. 결과는 궤적의 객관적인 속성입니다.
이로 인해 우리는 검색 품질을 평가하기 위한 두 가지 옵션을 갖게 되었습니다:

• LLM judge를 통해 주관적이고 국소적인 특징(local features)에 대해 궤적(trajectories)을 주석 처리(Annotate)합니다.

• 이진 성공/실패 레이블(binary success/failure label)을 객관적인 전역 속성(global property)으로 사용합니다.

궤적 스냅샷(trajectory snapshot)은 특정 턴(turn)에서의 상태를 의미합니다. 우리의 가설은 다음과 같습니다: 만약 검색 엔진(retrieval engine)이 스냅샷 구조를 포착한다면, 적절한 턴 T에 도달했을 때 성공적인 궤적의 스냅샷은 다른 성공적인 궤적의 스냅샷과 더 유사할 것이며, 그 반대도 마찬가지일 것입니다. 이는 성공 또는 실패가 복잡한 이벤트이기에 국소적인 규칙(local rules)으로 환원될 수 없다는 점에서 더 어려운 프레이밍(framing)입니다.

벤치마크 (The benchmark)

측정 대상 (What we measure)
주요 지표는 60단계 이후부터의 단계별 층화 ROC AUC(per-step stratified ROC AUC)입니다. 이는 생존 분석(survival analysis) 및 동적 예측(dynamic prediction)(예: 시간 의존적 ROC)에서 사용되는 잘 확립된 시간 층화 평가(time-stratified evaluation)의 궤적 단계(trajectory-step) 대응물로, 각 피험자를 일치하는 시간에 점수화하여 기간 길이(horizon length)로 인한 혼란 변수(confounding)를 제거합니다. 이는 실시간 실패 예측 모니터링을 시뮬레이션합니다. 다음 섹션에서는 이것이 정확히 어떻게 계산되는지, 그리고 왜 이것을 선택했는지 설명합니다.
이 방식이 단일 전역 AUC(single global AUC)보다 선택된 데에는 세 가지 이유가 있습니다:

• 실패한 궤적(Failed trajectories)은 성공한 궤적보다 체계적으로 더 깁니다. 이는 특정 데이터셋에 국한된 것이 아니라 에이전트 궤적(agentic trajectories)의 일반적인 특성입니다. 따라서 전역 AUC(global AUC)는 점수에 길이를 유출(leak)시킵니다. 즉, "궤적이 얼마나 진행되었는가"를 조금이라도 이용하는 검색기(retriever)는 정당하지 않은 공로를 얻게 되며, 순수한 구조적 기여(structural contribution)는 보이지 않게 됩니다. 길이 인식 검색기(Length-aware retrievers)가 잘못된 것은 아닙니다. 대략적으로 동일한 단계(step)에 있는 스냅샷을 유사하게 취급하는 것은 정상적입니다. 하지만 우리는 구조적 신호(structural signal)를 분리해내고자 합니다.

• 궤적-스냅샷 검색 시스템(trajectory-snapshot retrieval system)의 자연스러운 과업은 현재 시점의 스냅샷과 유사한 스냅샷을 찾는 것이지, 그들의 상태를 미래로 투영(project)하는 것이 아닙니다.

• 매 단계 수행되는 평가(running per-step evaluation)는 미래에 대한 지식 없이 실시간 모니터링을 시뮬레이션합니다. 이미 완료된 궤적을 분류하는 것은 실질적인 가치가 없습니다.

매 단계 계층화된 AUC(per-step stratified AUC)가 계산되는 방식 (정확히)
평가 세트의 모든 궤적에 대해, 우리는 스냅샷 시퀀스를 기록합니다: 단계 인덱스 s = 0, 1, …, S에 따라 정렬된 에이전트 단계당 하나의 스냅샷입니다. 각 스냅샷에서 검색 엔진(retrieval engine)은 풀(pool)에서 가장 유사한 상위-k(top-k) 경로를 반환하며, 우리는 fail_frac(s) = 해당 상위-k 중 소유 궤적이 실패로 끝난 비율을 계산합니다.
단계 s에서 우리가 평가하는 점수는 해당 스냅샷의 실패 비율(fail fraction)이며, 만약 이 단계에서 커버리지(coverage)가 없다면 가장 최근에 알려진 값을 사용합니다.
각 절대적 단계 s에서, 우리는 해당 단계까지 도달한 궤적들의 집합, 즉 자체 길이가 최소한 s인 궤적들을 취합니다. 이것이 단계 s에서의 활성 인구(active population)입니다. 이 집합의 각 궤적은 두 가지 값, 즉 점수(score)와 실제 라벨(true label, 실패 또는 성공)을 가집니다.
그런 다음 우리는 이 그룹에 대해 표준 ROC AUC를 계산합니다. ROC AUC는 활성 집합에서 무작위로 하나의 실패 사례와 하나의 성공 사례를 뽑았을 때, 실패 사례가 더 높은 점수를 가질 확률입니다. 0.5는 점수가 클래스를 구분하지 못함을 의미하며, 1.0은 완벽한 분리를 의미합니다.

최대 스텝(max step) ≥ s인 궤적(trajectories)들만 참여합니다. 모든 활성 궤적들이 동일한 클래스에 속하는 스텝(실패가 없거나 성공이 없는 경우)은 ROC AUC를 정의할 수 없으므로 제외됩니다.
최종 헤드라인 수치는 s = 60부터 최대 스텝까지의 모든 유효한 스텝에 대한 평균값입니다:
AUC@step_60 = mean( AUC(s) for s in [60, S_max] where defined )

왜 60 스텝부터 시작하는가. 이 데이터셋에서는 76%의 궤적(209/275)이 60 스텝에서도 여전히 활성 상태입니다. 이는 구조적 신호(structural signal)가 드러나기에 충분한 문맥(context)이 축적된 상태이면서, 동시에 활성 인구(active population)가 스텝별 AUC를 통계적으로 유의미하게 유지할 수 있을 만큼 충분히 큰 상태임을 의미합니다. 더 이른 스텝은 결과를 판별하기 위한 행동 정보가 너무 적고, 훨씬 더 나중에는 긴 꼬리(long tails) 부분만 남게 되어 활성 집단이 축소됩니다.

왜 스텝별 AUC는 구조적으로 층화(stratified)되어 있는가
스텝 s에서, 스텝 s에 살아있는 모든 궤적은 동일한 스텝의 동료들과만 비교됩니다. 따라서 스냅샷 길이(snapshot length)만을 이용하는 검색기(retriever)는 기대 AUC 0.5를 얻게 됩니다. 즉, 층화(stratification)를 통해 길이 신호가 제거되고 구조적 기여(structural contribution)만 남게 됩니다.

참가 모델
Episodiq — 당사의 구조적 검색(structural retrieval) 엔진(아래에서 설명).
Basic RAG (cosine KNN) — 임베딩 베이스라인: 각 접두사(prefix)는 마지막 N개의 메시지를 평균하여 하나의 벡터로 축소됩니다 (N은 {1, 5, 10, 15, all} 범위를 탐색). 검색은 코사인 유사도(cosine similarity)를 기반으로 서로 다른 궤적들 중 상위 k개의 최근접 이웃(top-k nearest neighbours)을 찾는 방식이며, 점수는 검색된 집합의 실패율(failure rate)입니다.

태스크(The task)
60 스텝 이후의 모든 스텝에서, 각 활성 스냅샷(active snapshot)이 실패한 궤적에 속할 확률을 할당합니다.

데이터
SWE-rebench-OpenHands-Trajectories에서 추출하여 tobymao/sqlglot 리포지토리로 필터링된 275개의 궤적(실패 178개, 성공 97개)을 사용합니다. 동일한 PR(Pull Request)을 공유하는 궤적은 두 개도 존재하지 않습니다. 동일한 PR 쌍은 거의 동일한 의미론적 내용(semantic content)을 담고 있어, RAG 방식의 검색기가 코사인 유사도 기반 매칭을 수행할 때 정보가 직접적으로 유출(leak)될 수 있기 때문입니다. 인스턴스 캡(instance cap, PR당 하나의 궤적)을 통해 이러한 혼란 변수(confound)를 제거했습니다.

입력값 (Inputs)
모든 참가자는 매 단계마다 동일한 궤적 접두사 (trajectory prefix)를 받지만, 이를 소비하는 방식은 다릅니다:
Episodiq. 각 관측 (observation) 및 행동 (action) 메시지는 하나의 클러스터 (cluster)로 분류됩니다. 접두사는 유형화된 클러스터 토큰 (typed cluster tokens)의 시퀀스가 되며 (초기 사용자 프롬프트는 깔끔하게 유형화될 수 없으므로 제외됨), 이는 완료된 궤적들로부터 유사한 경로를 검색하는 데 사용됩니다. 층화 분할 (Stratified split): 55개 궤적의 튜닝 슬라이스 (tune slice), 220개 궤적의 비중복 평가 슬라이스 (disjoint eval slice).

기본 RAG (Basic RAG)는 다음 항목들에 대해 테스트되었습니다:

• 임베딩 차원 (embedding dimensions): 1024 및 2048
• 작업 메시지 (task message) 포함 / 제외
• top_k: {5, 10, 25, 50}
• 평균화된 마지막 N개 메시지 (last-N messages averaged): {1, 5, 10, 15, all}
• 코사인 유사도 (cosine similarity): {0.5, 0.6, 0.7, 0.8, 0.9, 0.95} 보고된 수치는 탐색 (sweep) 과정 중 가장 성능이 좋았던 설정입니다.

결과 (Results)

주요 발견 사항: Episodiq는 AUC와 커버리지 하락 (coverage drop) 측면에서 비약적인 발전을 보인 반면, 전체 기본 RAG (basic-RAG) 탐색 과정에서는 9%에서 100%까지 모든 커버리지 구간에서 AUC가 0.58–0.60 범위에 머물러 있었습니다. 코사인 유사도는 포화 상태에 도달하며, 임계값 (threshold)을 높이면 선택성 (selectivity)은 얻을 수 있으나 추가적인 신호 (signal)는 얻지 못했습니다. 또한 우리가 시도한 어떤 임베딩 설정도 구조적 검색 (structural retrieval)이 포착하는 정보를 복구하지 못했습니다.

220개의 궤적(trajectory) 평가에서 0.10의 헤드라인 격차는 95% 신뢰 구간(CI)이 겹치지만, 이러한 포화(saturation) 현상은 하나의 추정치가 아닌 전체 스윕(sweep)의 특성입니다.

반대 급부는 커버리지(coverage)입니다. 선택된 유사도 임계값(0.20)에서, 60단계 스냅샷 중 임계값 이상의 구조적 일치(structural match)를 보이는 것은 22%에 불과합니다. 또한 커버리지 하락이 매우 가파른데, 거의 전체 커버리지 상태 이후 다음으로 획득되는 지점이 22% 커버리지일 정도입니다. 물론 여기서의 커버리지 하락은 예상된 결과입니다. 가능한 궤적 형태의 공간은 조합론적으로 매우 크기 때문에, 진정으로 유사한 이웃이 항상 존재하지는 않습니다. 다만 이러한 가파른 곡선은 그리 편리하지 않다는 점을 언급해 둡니다. 저희는 신호(signal)를 희석하지 않으면서 이 범위를 넓힐 수 있는 구체적인 방법들을 확인했으며, 이것이 다음 버전의 초점이 될 것입니다.

Episodiq의 작동 방식

표현(representation)은 네 단계로 구축됩니다:

1. 코퍼스(corpus) 내의 모든 관찰(observation) 및 행동(action) 메시지를 임베딩(embed)하고 클러스터링(cluster)합니다. 각 메시지는 최종적으로 해당 클러스터에 의해 레이블이 지정됩니다(관찰은 o1, o2, …, oN 클래스를, 행동은 a1, a2, …, aN 클래스를 할당받습니다).
2. 각 에이전트 단계(agent step)에서, 해당 단계의 (행동 클래스, 관찰 클래스) 쌍을 형성합니다.
3. 이러한 (행동, 관찰) 쌍들을 — 각 쌍의 중심점(centroid) 임베딩을 입력 벡터로 연결하여 — 압축된 act_obs 토큰 어휘집(vocabulary, 저희 설정에서는 수십 개의 토큰)으로 클러스터링합니다.
4. 궤적(trajectory)은 결과적으로 생성된 act_obs 토큰의 시퀀스이며, 에이전트 단계당 하나의 토큰이 할당됩니다.

초기 관찰(태스크 프롬프트)은 1단계에서 제외됩니다. 이는 깔끔하게 유형화(type)할 수 없으며, 이를 포함할 경우 다운스트림 지표(downstream metrics)를 저하시키기 때문입니다.

검색 (Retrieval)
각 경로는 해당 단계까지 축적된 act_obs 토큰의 시퀀스로 축소됩니다 (노이즈 토큰(noise tokens) - 클러스터 이상치(cluster outliers) - 은 일반 심볼로 유지됩니다. 경험적으로 이를 제거할 경우 검색 품질이 저하되었기 때문입니다). n = 3의 슬라이딩 윈도우(sliding window)를 사용하여 경로의 트리그램(trigram) 집합을 생성합니다.
각 트리그램 집합은 K = 512개의 순열(permutations)을 가진 MinHash 시그니처(signature)가 됩니다. 이는 비교당 O(|set|) 대신 O(K)의 복잡도로 자카드 유사도(Jaccard similarity)를 근사하는 고정 크기의 지문(fingerprint)입니다. 검색 시점에는 쿼리 스냅샷(query snapshot)의 시그니처를 모든 완료된 궤적(trajectory)의 경로와 대조하여 점수를 매기고, 유사도 임계값(similarity threshold)을 초과하는 상위 k개(top-k)의 일치 항목을 가져온 뒤, 해당 상위 k개 중 소유 궤적이 실패로 끝난 비율인 fail_frac을 보고합니다.
데이터셋당 두 개의 파라미터가 조정됩니다: top_k (투표에 참여할 이웃의 수 - 10으로 선택) 및 similarity_threshold (일치 항목을 버리는 하한선 - 0.20으로 선택). 튜닝은 55개의 궤적으로 구성된 층화 추출(stratified slice) 데이터에서 실행되며, 220개의 궤적으로 구성된 홀드아웃(hold-out) 데이터는 최종 평가를 위해서만 사용됩니다.

Episodiq가 유사도 검색을 넘어 수행하는 것

동일한 표현(representation)을 통해 다음과 같은 여러 실용적인 기능을 지원합니다: