Anomaly Detection on Agent Traces: Sequence Models, Embeddings, and the Cold-Start Problem

Abstract

A behavioral baseline is inert until something scores new behavior against it and decides what to flag. This article treats that detection layer as a data-science problem. It defines the anomaly score and the threshold that turn a model into alarms, situates agent detection on the supervision spectrum from supervised to fully unsupervised, and compares three detector families — sequence models scored by likelihood or reconstruction error, and embedding-based density and distance methods. It then confronts the cold-start problem, where no benign baseline exists yet, with a bootstrap strategy, and closes on threshold selection, drift, and honest evaluation. The throughline: detection is a set of engineering choices governed by what data you actually have, and every choice must be stated with its error budget.

A behavioral baseline answers a question about probability; a detector answers a question about action. Between them sits a chain of decisions that determines whether the whole apparatus helps or merely generates noise: how to convert a model's verdict into a single score, where to set the line that separates flag from allow, which detector family to trust given the data you have, and what to do in the first hours of an agent's life when there is no normal to compare against at all. None of these decisions is settled by the baseline; each is an empirical trade-off with a measurable error budget. This piece works through them.

Detection as Scoring and Thresholding

Detection reduces to two operations: assign each observed behavior a scalar anomaly score that grows as the behavior becomes less consistent with normal, then compare that score to a threshold. The canonical score is the negative log-likelihood under the baseline — an observation the model finds improbable earns a high score — but any monotone measure of dissimilarity from normal serves the same role. The threshold converts a continuous surprise into a binary decision, and where you place it is a policy choice, not a mathematical fact.

That placement is the classic precision-recall trade-off. Lower the threshold and you catch more true anomalies but drown reviewers in false positives; raise it and alerts stay clean but misses grow. Because labeled attacks against a specific agent are scarce, the practical method is to set the threshold from the distribution of benign scores — for example at a high quantile of held-out normal — so that the expected false-positive rate is controlled by construction, then adjust against whatever true-positive evidence you can gather.

The consequence is that a detector is never characterized by a single accuracy number. It is characterized by an operating curve — the trade-off between detection rate and false-alarm rate as the threshold sweeps — and by the specific point on that curve you have chosen to run at. Any claim about a behavioral detector that omits its operating point is incomplete.

\[s(x) = -\log \hat{p}(x), \qquad \text{flag } x \iff s(x) > \tau, \qquad \tau = Q_{1-\alpha}\big(\{ s(x) : x \in \text{held-out benign} \}\big)\]

The Supervision Spectrum

Chandola, Banerjee, and Kumar organize anomaly detection by how much labeled data is available, and agent trace detection lives at the label-poor end of that spectrum. Supervised detection, which trains a classifier on labeled normal and labeled attacks, is rarely applicable because attacks against a specific agent are few, novel, and non-recurring — there is no representative sample of the positive class to learn. Assuming it is available is the most common way a behavioral program fools itself.

The workable regime is semi-supervised: learn a model of normal from benign operation only, and treat improbable behavior as suspect. It matches the data you can actually obtain — an observation window you have reason to believe is benign — and it degrades gracefully, flagging novelty rather than only known attacks. Its risk is that anything absent from the benign window looks anomalous, so it must be paired with a review process that distinguishes benign novelty from malicious novelty.

The hardest regime is unsupervised, where even the assumption of a clean benign window fails and you must find anomalies inside unlabeled, possibly contaminated data. Here detection leans on the structural assumption that anomalies are rare and different — a small minority that sits in low-density regions — and methods must be robust to a contaminated majority. Knowing which regime you are in is the first design decision, because it eliminates whole families of method.

Labeled attacks are scarce, pushing agent detection toward the semi-supervised and unsupervised end.

Sequence Models: Likelihood and Reconstruction

The first detector family scores the order and structure of a trace. A sequence model estimates the probability of each action given its predecessors; a trace whose transitions are collectively improbable earns a high score even when every individual action is common. The transparent baseline is an order-k Markov model scored by per-action perplexity, which points at exactly which transition broke expectation — a property that matters when a human must adjudicate the alert.

A more expressive variant scores by reconstruction error. Train a sequence autoencoder to compress and regenerate benign traces; at detection time, feed a new trace through and measure how badly it reconstructs. Behavior that resembles training normal reconstructs cleanly and scores low; genuinely novel structure reconstructs poorly and scores high. Reconstruction error captures patterns a fixed-order Markov model misses, at the cost of the interpretability the Markov model preserves — a trade the design must make deliberately.

Both variants share the mimicry vulnerability that Wagner and Soto established for system-call detection: an adversary who knows the sequence model can interleave normal-looking transitions until the malicious sequence lies inside the high-probability region. Order-based detection raises attacker cost but cannot stand alone; it must be combined with content signals — which arguments, which egress — so that conforming in order does not also grant conformance in effect.

\[s_{\text{seq}}(x) = \tfrac{1}{T}\sum_{t} -\log P(a_t \mid a_{

Embeddings: Detection in Representation Space

The second family maps behavior into a vector space and detects anomalies geometrically. An embedding is a learned numeric representation — here, of an action, a tool call, or a whole trace — placed so that behaviors used in similar ways sit close together. Once traces are points in such a space, anomaly detection becomes a question about geometry: an anomaly is a point far from its neighbors or in a low-density region.

Two workhorses operate on embeddings. Distance-based detection scores a trace by its distance to its k nearest benign neighbors, flagging points that are isolated. Density-based detection, including one-class methods that fit a boundary around the benign region, flags points that fall outside the learned support. Both generalize better than exact sequence matching because a novel-but-similar trace lands near known-normal points and is correctly treated as normal, while a genuinely foreign trace lands in empty space.

The embedding approach has its own failure surfaces the data scientist must watch. The geometry is only as good as the representation: an embedding that discards the feature an attacker exploits — say, the egress destination — cannot separate on it. And embeddings can place a cleverly constructed malicious trace near benign ones, which is mimicry in representation space. As always, the mitigation is to detect on multiple, independent representations rather than a single learned space.

\[s_{\text{knn}}(x) = \tfrac{1}{k}\sum_{i=1}^{k} \lVert \phi(x) - \phi(x_{(i)}) \rVert, \quad x_{(i)} = i\text{-th nearest benign neighbor in embedding } \phi\]

The Cold-Start Problem

Every method above assumes a benign baseline exists. At the moment an agent is deployed, or after any change that invalidates the old baseline, it does not. This is the cold-start problem: you must detect abnormal behavior before you have observed enough normal behavior to define it. Ignoring it means either running blind during the riskiest window — the debut — or flagging everything as anomalous because nothing is yet familiar.

The resolution is a bootstrap loop that tightens over time. Begin with a conservative prior that is not learned from this agent at all: a hand-specified allow-list of expected tools and a strict egress policy, accepting high false positives in exchange for coverage. Where a similar agent already has a baseline, transfer it as a starting point. As benign traffic accumulates under human review, fit the semi-supervised baseline, progressively relax the conservative prior, and raise the threshold from the widening benign score distribution. The system moves from policy-heavy to model-heavy as evidence arrives.

Two disciplines keep the bootstrap honest. First, the early window must be adjudicated, not assumed benign, or contamination is baked into the very first baseline. Second, the transition criteria — how much benign data, what fit quality — must be explicit, so the shift from conservative prior to learned model is a decision with a record, not a silent drift. Cold-start is not a phase to survive but a controlled hand-off from static policy to behavioral model.

Detection begins on a conservative prior and tightens as reviewed benign traffic trains the learned baseline.

Choosing a Detector

No single detector dominates; the right choice follows from two axes. The first is what the anomaly is: a lone bad action needs only a point method, a wrong-in-context action needs a conditional method, and a bad sequence of good actions needs order- or embedding-aware detection. The second is what data you have: a clean benign window enables semi-supervised likelihood or one-class methods, while a contaminated or absent baseline forces robust unsupervised or bootstrap approaches.

In practice you run several detectors and combine them, because their blind spots differ. A Markov sequence model and an embedding density model fail on different traces, and an argument-content check fails on different traces still; requiring an alert to clear the ensemble, or scoring by their agreement, raises the bar for an adversary who would otherwise only need to fool one. The cost is calibration complexity, which is why the ensemble must share a common evaluation harness and a single reported operating point.

The overarching rule is to match the detector to the data regime honestly. A method that assumes labeled attacks, or a clean baseline, or a stationary distribution, will fail quietly when that assumption does not hold. Naming the assumption each detector makes is as important as measuring its accuracy.

The detector family follows from whether order matters and whether a clean benign baseline exists.

Thresholds, Drift, and Honest Evaluation

A deployed detector needs a defensible operating point and a plan for change. Set the threshold from the benign score quantile to control false positives, then move it against real true-positive evidence — red-team exercises, injected canaries, adjudicated incidents — and record the operating point you chose. Report the detector as an operating curve, not a scalar: detection rate against false-alarm rate across the threshold sweep, with the running point marked.

Drift erodes any fixed threshold. As the agent's normal behavior shifts with model, tool, and prompt changes, the benign score distribution moves, and a static threshold silently changes its false-positive rate. Monitor the score distribution on recent benign traffic and re-derive the threshold when it moves, the same discipline the baseline itself requires. The NIST AI Risk Management Framework's MEASURE function frames exactly this: a metric is only useful if it is validated, documented, and kept current.

Finally, hold the mimicry limit in view when reporting results. A detector's measured detection rate is against the adversaries you tested, not against an informed adversary optimizing to evade the specific model you deployed. State the threat model your numbers assume, keep the strongest signals from being fully public where feasible, and layer independent detectors so that evading the ensemble is strictly harder than evading any one member.

Detector families and the regime each fits.
Family	Anomaly it catches	Needs	Main weakness
Marginal / point	Rare action in isolation	Benign frequencies	Blind to context and order
Sequence (Markov / autoencoder)	Bad order of good actions	Benign sequences	Mimicry by padding
Embedding distance / density	Foreign trace geometry	Benign embedding + representation	Misses features not embedded
Robust unsupervised	Rare points in unlabeled data	Rarity assumption	Contamination sensitivity

📌

Report the operating point. A behavioral detector is defined by its detection-versus-false-alarm curve and the point you run at, never by a single accuracy figure.

Key takeaways

Detection is scoring plus thresholding: convert the baseline's verdict into a scalar surprise, then compare to a threshold set from the benign score distribution to control false positives by construction.
Agent-trace detection lives at the label-poor end of the supervision spectrum; semi-supervised (learn normal only) is the workable default, and assuming labeled attacks exist is a common self-deception.
Sequence models catch bad order of good actions via likelihood or reconstruction error; embedding methods catch foreign traces geometrically — and both must be paired with content signals to resist mimicry.
The cold-start problem is solved by a bootstrap loop: start on a conservative static prior, accumulate adjudicated benign traffic, fit the model, and tighten — a controlled hand-off, not a blind window.
No detector dominates; choose by anomaly type and data regime, run an ensemble whose blind spots differ, and name the assumption each detector makes.
Thresholds drift with the agent's normal; monitor the benign score distribution, re-derive the threshold on change, and report an operating curve with a stated threat model rather than a scalar.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

🚀Cold-start bootstrap — do these in orderquickstart

How to run detection from an agent's first minute without flying blind or flagging everything.

Start on a conservative prior: an explicit expected-tool allow-list and a strict egress policy.
Route all early traffic through human review; adjudicate the window rather than assuming it is benign.
Once enough reviewed-benign traces accumulate, fit the semi-supervised baseline.
Set the threshold at a high quantile of held-out benign scores and progressively relax the prior.
Record the transition criteria and the chosen operating point as a decision, not a silent change.

🧪Threshold-from-benign + ensemble score (sanitized)harness

A no-op skeleton that calibrates a threshold on benign scores and combines detectors.

function calibrate(threshold_quantile, benign_scores):
    return quantile(benign_scores, threshold_quantile)   # e.g. 0.99

function ensemble_score(trace, detectors):
    # detectors differ in blind spots: markov, embedding-density, argument-check
    zs = [ z_normalize(d.score(trace), d.benign_mu, d.benign_sd) for d in detectors ]
    return max(zs)                                        # require clearing the toughest

function decide(trace, detectors, taus):
    votes = [ d.score(trace) > taus[d.name] for d in detectors ]
    return "flag" if any(votes) else "allow"              # union raises recall; adjust per budget

Calibrated ensemble detection

✅Detector evaluation gatechecklist

Do not ship a detector until each item holds.

The data regime (supervised / semi-supervised / unsupervised) is named and matched by the method.
The operating point is chosen and reported, with the detection-versus-false-alarm curve.
The benign score distribution is monitored and the threshold re-derived on drift.
At least two independent detectors with differing blind spots are combined.
The threat model behind the reported numbers is stated, including the mimicry caveat.

Glossary

Anomaly score: A scalar that increases as an observation becomes less consistent with the model of normal, typically the negative log-likelihood.
Threshold: The score value above which behavior is flagged; setting it is a policy choice trading detection against false alarms.
Semi-supervised detection: Fitting a model of normal from benign data only and flagging improbable behavior, without labeled attacks.
Reconstruction error: How poorly a model trained to regenerate normal reproduces an input; high error signals unfamiliar structure.
Embedding: A learned numeric vector representation placing similar behaviors close together so anomalies can be found geometrically.
Cold-start problem: The need to detect abnormal behavior before enough normal behavior has been observed to define it.
Operating point: The chosen position on a detector's detection-rate-versus-false-alarm-rate curve at a given threshold.

Abstract

Detection as Scoring and Thresholding

The Supervision Spectrum

Sequence Models: Likelihood and Reconstruction

Embeddings: Detection in Representation Space

The Cold-Start Problem

Choosing a Detector

Thresholds, Drift, and Honest Evaluation

Key takeaways

Practitioner Toolkit

Glossary

References