DEV Community: Slava

Predicting agent failures from trajectory shape: trajectory-pattern retrieval outperforms basic RAG

Slava — Tue, 30 Jun 2026 14:05:29 +0000

A trajectory-pattern retrieval engine reaches AUC 0.71 (95% CI [0.61, 0.78]) for per-step failure prediction on held-out coding-agent trajectories - and, notably, eval > tune. A tuned text-embedding (cosine-KNN) baseline over the same data lands at chance: every configuration and aggregation we tried has a confidence interval that includes 0.5.

Growing databases of agent traces that companies collect (or should collect, if they haven't started yet) present an opportunity to analyse or monitor agents, since their efficiency, safety and security shape net economic impact. For practical purposes, different layers occupy different points on the cost (operational or inference), latency and accuracy spectrum. The LLM-as-a-judge approach clearly occupies the expensive, slow, high-accuracy slot. Tools that rely on statistical instruments or deterministic signals, on the other hand, are expected to provide a fast and cheap gateway to LLM-based evaluation.

This leads us to a question: what tools are currently available to extract signals about an agent's trajectory, given a database of related runs? We tested basic RAG and an alternative retrieval method on agent failure prediction: take a snapshot of a trajectory at some turn, find its N closest neighbouring snapshots (excluding the same trajectory), and use the neighbours' failure rate to make a prediction.

Failure prediction was chosen with a few points in mind:

it is an objective, not opinion-based, characteristic of an agent trajectory, and doesn't require an LLM judge
it is a global feature, which makes for a hard baseline (local properties are expected to be easier)
it has practical value for analytics, token efficiency or runtime monitoring

The benchmark

Dataset
275 trajectories from SWE-rebench-OpenHands-Trajectories, filtered to the tobymao/sqlglot repository (178 failures, 97 successes). At the preprocessing stage, trajectories were filtered so that each one comes from a unique pull request. Any same-PR pair carries near-identical semantic content and introduces data leakage; leaving same-PR samples in the dataset bumps eval AUC up by ~20–30 points.
The split is built by randomly ordering instance-id-sorted trajectories, then proportionally interleaving by status - a 100-trajectory tune slice and a 175-trajectory held-out eval slice, both landing at ~65% failure rate (the population mean). The split is used in hyperparameter selection, not in retrieval: eval queries see the full corpus. Reported confidence intervals are per-trajectory bootstrap, 2000 draws.

Metric: per-step stratified AUC from step 50
The primary metric is per-step stratified weighted ROC AUC from step 50 onwards - the trajectory-step analogue of the well-established time-stratified evaluation used in survival analysis and dynamic prediction (e.g. time-dependent ROC), where each subject is scored at matched times to remove confounding from horizon length.

The final score is a weighted mean of per-step AUCs. For every stepS ≥ 50:

Take the trajectories still alive at S (those whose last snapshot is at step ≥ S); call this count n_S.
Compute a score for each of them on its [0…S] snapshot slice.
Compute ROC AUC across that active set - call it AUC_S.

The per-step AUCs are then combined into a single weighted average.

Step 50 was chosen because in the studied dataset ~95% of trajectories are still alive at step 50. Weighting is done so that the early steps - where most runs are still alive - carry the most weight.

This was chosen over a single global AUC for a reason: failed trajectories are systematically longer than successful ones. This property seems highly regular in the agentic domain, rather than an anomaly of this particular dataset. A global AUC therefore leaks length into the score: any retriever that relies solely on final trajectory length gets around 0.68 AUC (global), while at step stratified setup should converge to 0.5. Global AUC also has little practical value: the usefulness of post-run classification is unclear, whereas the per-step stratified version emulates real-time monitoring.

Participants

Trajectory-pattern retrieval KNN
Basic RAG (cosine-KNN)

What trajectory-pattern retrieval is: use an embedder model to embed each message into 1024 dimensions, cluster all messages as actions and observations, build a compressed vocabulary of typed action-observation tokens (~50–60 tokens), then represent each run as a sequence of these tokens. More specifics are described below.

What basic RAG is precisely: each prefix is reduced to one vector (swept over 1024 or 2048 dimensions) by averaging its last N messages (N swept across the interval {1…20}, plus an all-messages special case); retrieval is top-k (k over {1…50}) nearest neighbours from distinct trajectories by cosine similarity; the score is the failure rate of the retrieved set. It scores exactly the way a RAG-style failure monitor would.
For both participants, the Qwen3 8B embedder mode is used. Trajectory-pattern retrieval skips the initial task message, while for basic RAG both options were tested: including or excluding the initial message.

Aggregations
At each step we summarise a trajectory's accumulated fail-similarity into a single score, and we report the cumulative mean (cummean) over the 175 eval trajectories, since cummean proved the most noise-robust and therefore the most useful given the dataset limitations.
A valid objection is that basic RAG might fare better under an aggregation other than our headline cummean, so we additionally tune and evaluate it under running-max (cummax) and peak-running-mean (cummeanmax). For each aggregation we run the full query/retrieval hyperparameter search independently and keep the configuration that maximises that aggregation's tune-set AUC, then score it on the held-out eval set - so each aggregation is reported under its own best-tuned configuration. Best aggregation for basic RAG turned out to be a cummax, while other two show inverted AUC, so we will report cummax for basic RAG further.

Results

Every basic RAG interval includes 0.5. On this corpus, text-embedding cosine retrieval has no usable signal for predicting the outcome - even when allowed to pick its best aggregation. The trajectory-pattern retrieval cummean interval has a lower bound of 0.621, clearly above chance, and the fact that eval and tune are close (with eval slightly higher) shows no sign of an overfit.

How trajectory-pattern retrieval works

The representation is built bottom-up:
Embed and cluster every observation and action message in the corpus. Each message ends up labelled by its cluster (observations get classes o1, o2, …; actions get a1, a2, …). The initial task prompt is dropped - it can't be cleanly typed, and keeping it degrades downstream metrics.
At each agent step, form the pair (action class, observation class).
Cluster those pairs - concatenating each pair's centroid embeddings - into a compact act_obs token vocabulary (~50–60 tokens in our setup).
A trajectory becomes the resulting sequence of act_obs tokens, one per step.

Retrieval
Three-stage retrieval is used:

anchors placed at evenly spaced centre steps along the path → a per-window MinHash LSH band prefilter (a cheap candidate shortlist)
a dense Jaccard rerank over each candidate's neighbourhood → a cross-anchor aggregate
an aggregative shift-aware Levenshtein rerank: it slides across a trajectory with a window W, finds the best-matching alignment position in the candidate trajectory within W/2, applies a shift penalty and produces a score for each element (point); these scores are then averaged.

Here we note that this rerank technique was not an obvious choice, and more basic sequence-similarity algorithms were tested, such as whole-sequence Levenshtein, whole-sequence Levenshtein with a substitution matrix, Smith-Waterman, Needleman-Wunsch, DTW (Dynamic Time Warping) and some others. All of them performed near the basic-RAG level, which suggests a valuable interpretation of agent-trace structure that we may cover later.

Related code and benchmark are open-sourced
The codebase to run this benchmark was open-sourced as a Python package named Episodiq. Numbers should reproduce; if they don't, that's a bug we want to know about.
The same representation supports several practical features, which were also implemented:

Human-readable logs at ~98% lower annotation cost, LLM-free at runtime. Annotate one representative per cluster and reuse it for every trajectory; new messages are tagged at write time by KNN against their slice - instant labels, zero LLM calls in the hot path. The gap widens with corpus size: at 1,000 trajectories it reaches 99% (~165×), because annotation cost scales with the vocabulary, not the corpus.
A per-snapshot fail-similarity score, as benchmarked above.
Loop detection - surfaces an agent stuck repeating a type of step, useful for token-waste monitoring even when the run isn't broken.
An action-predictability signal - flags steps where the next action is highly constrained versus steps where the agent could plausibly branch many ways.

Results are preliminary - a single repository, 175 held-out trajectories, wide bootstrap intervals. The gap should be confirmed on larger corpora, though assembling a large enough public trajectory dataset is itself an open problem.

Structural retrieval shows promise over basic RAG for agent failure prediction on trajectory snapshots

Slava — Tue, 02 Jun 2026 14:43:21 +0000

A structural retrieval engine with KNN voting shows a promising signal over basic RAG: AUC = 0.705 averaged over snapshots from step 60 onward on held-out trajectories, while basic RAG plateaus around 0.60 AUC at any cosine threshold from 9% to 100% coverage.
Results are preliminary - single-repo and the distinct-PR condition (covered in benchmark design) limit the eval set to 220 trajectories, so 95% bootstrap confidence intervals overlap and the gap should be confirmed on larger datasets - though finding a sufficient public dataset is itself an open problem.

As the number of agents and trajectory databases grow, a new retrieval need emerges: finding trajectories that are structurally similar, rather than semantically similar by text content. The structure of a trajectory - the sequence of decisions and outcomes, independent of semantics - carries signals useful for monitoring, filtering for experience / reflection pipelines, evaluation, and other layers of agent infrastructure.
Our experiment shows that basic RAG loses this structural signal because it is designed for documents, not action sequences. We propose an approach where a trajectory is represented as a sequence of typed elements, and have implemented it in an open-source Python package, episodiq, described at the end of this article.
The rest of this piece covers the methodology and the metric choice.

Why predict a trajectory's outcome?

Among the questions one can ask about a trajectory, will it succeed or fail stands out because it can be checked against reality. Most of what trajectory analysis surfaces - which step was productive, where the agent lost the thread, which behavioural pattern is forming - is interpretation: useful, but with no external ground truth. Whether a run will succeed or fail is different: outcome is an objective property of the trajectory.
This gave us two options for grading retrieval quality:

Annotate trajectories on subjective, local features via an LLM judge.
Use the binary success/failure label as an objective global property.

A trajectory snapshot is its state at some turn. Our hypothesis: if a retrieval engine captures snapshot structure, then snapshots of successful trajectories should be more similar to snapshots of other successful ones, and vice versa, once some reasonable turn T is reached. This is the harder framing, because success or failure is a complex event - it cannot be reduced to local rules.

The benchmark

What we measure
The primary metric is per-step stratified ROC AUC from step 60 onward - the trajectory-step analogue of the well-established time-stratified evaluation used in survival analysis and dynamic prediction (e.g. time-dependent ROC), where each subject is scored at matched times to remove confounding from horizon length. It simulates real-time failure-prediction monitoring. The next section explains exactly how it is computed and why we chose it.
This was chosen over a single global AUC for three reasons:

Failed trajectories are systematically longer than successful ones. This is not specific to this particular dataset but a general property of agentic trajectories. A global AUC therefore leaks length into the score: any retriever that even partially exploits "how far the trajectory has gone" gets credit it doesn't deserve, and the purely structural contribution becomes invisible. Length-aware retrievers are not broken - it is normal to treat snapshots at approximately the same step as similar - but we want to isolate the structural signal.
For a trajectory-snapshot retrieval system, the natural task is to find snapshots similar to the current one at this moment - not to project their state into the future.
A running per-step evaluation simulates monitoring in real time without knowledge of the future. Classifying already-completed trajectories has no practical value.

How per-step stratified AUC is computed (precisely)
For every trajectory in the eval set, we record a sequence of snapshots: one snapshot per agent step, ordered by step index s = 0, 1, …, S. At each snapshot, the retrieval engine returns the top-k most similar paths from the pool, and we compute fail_frac(s) = the fraction of those top-k whose owning trajectory ended in failure.
The score we evaluate at step s is the fail fraction for that snapshot, or the latest known value if there is no coverage at this step.
At each absolute step s, we take the set of trajectories that have made it that far - those whose own length is at least s. This is the active population at step s. Each trajectory in this set has two values: its score and its true label (failure or success).
We then compute the standard ROC AUC for this group. ROC AUC is the probability that, if we draw one random failure and one random success from the active set, the failure has the higher score. 0.5 means the score doesn't distinguish the classes; 1.0 is perfect separation.
Only trajectories whose max step ≥ s participate. Steps where all active trajectories belong to the same class (no failures or no successes among them) are skipped, because ROC AUC is undefined there.
The final headline number is the mean over all valid steps from s = 60 to the maximum step:
AUC@step_60 = mean( AUC(s) for s in [60, S_max] where defined )

Why start at step 60. On this dataset, 76% of trajectories are still active at step 60 (209/275) - enough accumulated context for the structural signal to surface, while the active population is still large enough to keep per-step AUC statistically meaningful. Earlier steps carry too little behaviour to discriminate outcome; much later, only the longest tails remain and the active set shrinks.

Why per-step AUC is stratified by construction
At step s, all trajectories alive at step s are compared only to peers at the same step, so a retriever that exploits snapshot length alone gets an expected AUC of 0.5 - the length signal is removed by the stratification, leaving only the structural contribution.

Participants
Episodiq - our structural retrieval engine (described below).
Basic RAG (cosine KNN) - embedding baseline: each prefix is reduced to a single vector by averaging the last N messages (N swept across {1, 5, 10, 15, all}); retrieval is top-k nearest neighbours from distinct trajectories by cosine similarity; the score is the failure rate of the retrieved set.

The task
At every step from 60 onward, assign each active snapshot a probability that it belongs to a failed trajectory.

The data
275 trajectories from SWE-rebench-OpenHands-Trajectories, filtered to the tobymao/sqlglot repository (178 failures, 97 successes). No two trajectories share the same PR, because any same-PR pair carries near-identical semantic content, which would leak directly into a RAG-style retriever's neighbour-by-cosine matching. The instance cap (one trajectory per PR) removes that confound.

Inputs
All participants receive the same trajectory prefix at every step, but consume it differently:
Episodiq. Each observation and action message is classified into a cluster; the prefix becomes a sequence of typed cluster tokens (initial user prompt dropped - it cannot be cleanly typed), which is then used to retrieve similar paths from completed trajectories. Stratified split: 55-trajectory tune slice, 220-trajectory disjoint eval slice.

Basic RAG was tested across:

embedding dimensions: 1024 and 2048
include / exclude task message
top_k: {5, 10, 25, 50}
last-N messages averaged: {1, 5, 10, 15, all}
cosine similarity: {0.5, 0.6, 0.7, 0.8, 0.9, 0.95} Reported number is the best configuration over the sweep.

Results

Main finding: Episodiq leaps in AUC and coverage drop, while across the entire basic-RAG sweep, AUC stays pinned in the 0.58–0.60 range at every coverage from 9% to 100%. Cosine similarity saturates - tightening the threshold buys selectivity but no extra signal - and no embedding configuration we tried recovers what structural retrieval picks up.

The 0.10 headline gap has overlapping 95% CIs on a 220-trajectory eval, but the saturation is a property of the whole sweep, not of one estimate.
The flip side is coverage: at the picked similarity threshold (0.20), only 22% of step-60 snapshots have a structural match above threshold; and coverage drop is extremely steep, with 22% coverage being next acquired point after near full coverage. Although, coverage drop here is expected - the space of possible trajectory shapes is combinatorially large, so a genuinely similar neighbour won't always exist, we note that such steep curve is not very convenient. We see concrete ways to widen this window without diluting signal - the focus of the next version.

How Episodiq works

The representation is built in four steps:
Embed and cluster every observation and action message in the corpus - each message ends up labelled by its cluster (observations get classes o1, o2, …, oN; actions get a1, a2, …, aN).
At each agent step, form the pair (action class, observation class) for that step.
Cluster those (action, observation) pairs - concatenating each pair's centroid embeddings as the input vector - into a compact act_obs token vocabulary (a few dozen tokens in our setup).
A trajectory is the resulting sequence of act_obs tokens - one token per agent step.
The initial observation (the task prompt) is dropped from step 1: it cannot be cleanly typed, and including it degrades downstream metrics.

Retrieval
Each path is reduced to its sequence of act_obs tokens accumulated up to that step (noise tokens - cluster outliers - are kept as ordinary symbols, since dropping them empirically hurt retrieval quality). A sliding window of n = 3 produces the trigram set of the path.
Each trigram set becomes a MinHash signature of K = 512 permutations - a fixed-size fingerprint that approximates Jaccard similarity in O(K) per comparison instead of O(|set|). At retrieval time we score the query snapshot's signature against every completed trajectory's path, take the top-k matches above a similarity threshold, and report fail_frac - the fraction of those top-k whose owning trajectory ended in failure.
Two parameters are tuned per dataset: top_k (how many neighbours to vote with - picked 10) and similarity_threshold (the floor below which a match is discarded - picked 0.20). Tuning runs on the 55-trajectory stratified slice; the 220-trajectory hold-out is touched only for the final eval.

What Episodiq does beyond similarity search

The same representation supports several practical features:

Human-readable logs at dramatically lower token cost & LLM-free annotation at runtime. Annotate one representative per cluster, then reuse those annotations for every trajectory. New messages joining online are tagged at write time by KNN against messages of the same slice - instant labels, zero LLM calls in the hot path. On the 275-trajectory sqlglot eval we measure 98% reduction in token use vs naive per-message annotation; this gap widens with corpus size - at 1000 trajectories it reaches 99% (≈ 165×) and grows further, because cluster-annotation cost scales with the vocabulary, not the corpus.
Per-snapshot fail-similarity score, as described in this article.
Loop detection. If an agent gets stuck repeating the same type of messages in a loop, it is surfaced. This does not always mean the agent is broken - it can be useful simply for monitoring token waste.
Action-predictability signal. Marks each step as one where the next action is predictable, or one where the agent could plausibly branch many ways.

What this means

Structural similarity is signal that text-embedding retrieval misses.
Across the entire basic-RAG sweep - every combination of embedding dimension, top-k, prefix window, and cosine threshold we tried - no setting recovered what structural retrieval picks up. This isn't a verdict against embeddings; they remain the right tool for content similarity. It's a constructive finding: agent trajectories carry a second axis of similarity, orthogonal to text content, and the most useful systems will combine both rather than choose.

For operators running agents at scale, this is signal currently left on the table.
If you already store trajectories, the same representation gives you a fail-prediction analytics, a filter for experience and reflection pipelines, loop and action-variance signals, and human-readable logs at ~98% token savings - all LLM-free at runtime. The only paid input is a one-time message embedding pass: ~$0.10 for this dataset. Everything else - clustering, MinHash, retrieval - is cheap CPU work, and inference cost is approaching zero.

For anyone evaluating trajectory retrieval, per-step stratified AUC is the load-bearing metric.
A single global AUC mixes structural signal with length leakage - a trivial length-only classifier reaches AUC 0.66 on this dataset. The stratification removes that confound by construction (the length-only baseline collapses to 0.5), so any number reported under this metric is a direct read on the structural contribution. We recommend it for cross-system comparisons.

Limitations and where this goes

The benchmark is SWE-rebench-OpenHands-Trajectories specific. The pipeline and underlying representation are general - nothing is hand-tailored to coding agents - but we have not yet verified that the approach transfers to other domains (browser agents, support agents, data-analysis agents) without re-tuning. We expect it to, but expectation isn't evidence.

Episodiq needs a meaningful pool of trajectories. Clustering and signal thresholds become informative only once the corpus has seen enough behaviour to surface recurring patterns. Practically, several hundred trajectories is the minimum we have worked with. Few trajectories analysis is not what this tool is for.

Narrow coverage window. The Jaccard similarity distribution is concentrated in a narrow band, so coverage is sensitive to the threshold: a small move in similarity_threshold shifts coverage substantially. We have preliminary results indicating that an alternative path-similarity method can substantially relax this tradeoff - comparable AUC at near-100% coverage, and strictly higher AUC where coverage is traded for selectivity. This is the headline focus of the next version.

Try it

Reproduction kits
Episodiq benchmark (Basic RAG baseline at benchmarks/basic.py)
Episodiq is open source: github. Numbers should reproduce; if they don't, that's a bug we want to know about.
If you run agents at scale, the most useful thing you can do is point Episodiq at your trajectories and tell us what breaks. From our experiments, system tuning can be tricky and tuning decisions are sensitive to data. Working installations, failure modes, and "this doesn't fit my use case because X" are all useful to hear.
Contact: Telegram / skaiscan@gmail.com