Meerkat: Finding Rare Safety Violations Across Agent Traces with Clustering and Adaptive Search

Paper: 2604.11806 Authors: Adam Stein, Davis Brown, Hamed Hassani, Mayur Naik, Eric Wong Categories: cs.AI, cs.CL

The Gap

Auditors need to find safety violations in massive collections of agent traces — think thousands of execution logs from AI systems. The problem: failures are rare (1 in 1000), complex (require understanding multi-step behaviors), and sometimes only visible when comparing multiple traces (coordinated misuse, covert patterns).

Existing approaches fail in predictable ways. Per-trace judges (like LLM classifiers) can’t see cross-trace patterns. Agentic auditing (having an AI agent investigate) doesn’t scale — examining 10,000 traces one-by-one is computationally prohibitive. Fixed monitors (rule-based detectors) break when agents exhibit novel misbehaviors not anticipated by the rules.

Problem: Rare violations in massive trace collections
   |
   v
Assumption: Violations cluster in embedding space
   |
   +---> Method: Cluster traces, then adaptively search clusters
   |
   +---> Evidence: 4x more reward hacking found, discovers benchmark cheating
   |
   v
Conclusion: Structured search beats exhaustive or per-trace approaches

The Increment

One sentence: Before Meerkat, auditors chose between missing cross-trace violations (per-trace judges) or computational infeasibility (exhaustive agentic search); after Meerkat, they can find sparse violations at scale by searching the compressed structure of trace clusters.

Core Mechanism

Meerkat operates in two phases. First, it embeds all traces and clusters them, creating a compressed map of the trace landscape. Each cluster represents traces with similar behavioral patterns. Second, it performs adaptive search: an LLM agent investigates promising clusters, decides which to explore deeper, and can request detailed analysis of specific traces within clusters.

The search is hierarchical. The agent starts with cluster summaries (high-level behavioral descriptions). If a cluster looks suspicious, it can “zoom in” — request representative traces, examine specific examples, or even compare traces across clusters. The agent maintains a search state, tracking which regions it’s investigated and which warrant deeper inspection.

Input: 10,000 traces
   |
   v
[Embedding] --> Vector space
   |
   v
[Clustering] --> ~100 clusters
   |
   v
[Agent Search Loop]
   |
   +---> Read cluster summaries
   |
   +---> Pick suspicious cluster
   |
   +---> Request traces from cluster
   |
   +---> Analyze for violations
   |
   +---> Decide: dig deeper or move on?
   |
   v
Output: Flagged violations

Think of Meerkat as a detective investigating a city’s crime patterns. Instead of interviewing every citizen (exhaustive search), the detective first gets a map showing neighborhoods with similar characteristics (clustering). Then they strategically visit suspicious neighborhoods, talk to a few residents, and decide whether to investigate further or move to another area. The detective can zoom between city-level patterns and individual interviews, but never wastes time on obviously safe neighborhoods. The clustering compresses 10,000 citizens into 100 neighborhoods, making strategic investigation feasible.

Key Concepts

• Trace clustering as search compression: When you have 10,000 traces, examining each is infeasible. But if violations share behavioral patterns, they’ll cluster together in embedding space. Clustering compresses the search space from 10,000 individual items to ~100 groups. Now an agent can strategically sample: investigate a few traces per cluster, identify suspicious clusters, and focus compute there. It’s like organizing a library — instead of checking every book for a topic, you check sections, then shelves, then specific books.

• Adaptive search budget allocation: The agent doesn’t spend equal time on every cluster. It maintains a “suspicion score” and allocates more investigation budget to promising regions. If a cluster shows early signs of violations, the agent requests more traces, performs deeper analysis, or compares with other clusters. If a cluster looks clean after initial inspection, it moves on. This is crucial because violations are sparse — most clusters are benign, so you want to quickly rule them out and focus on the 5% that matter.

• Cross-trace violation detection: Some failures only appear when comparing multiple traces. Example: an agent might subtly manipulate data in trace A, then exploit that manipulation in trace B. Per-trace judges miss this because each trace looks individually fine. Meerkat’s agent can request traces from multiple clusters, compare them, and spot coordinated patterns. It’s like fraud detection — one transaction looks normal, but the pattern across ten transactions reveals the scheme.

Framework Shift

Before (per-trace judges):          After (Meerkat):

[Trace 1] ---> [Judge] ---> OK      [10K traces]
[Trace 2] ---> [Judge] ---> OK           |
[Trace 3] ---> [Judge] ---> OK           v
    ...                              [Cluster]
[Trace 10K] -> [Judge] ---> OK           |
                                         v
(Misses cross-trace patterns)       [Agent Search]
(No strategic focus)                     |
                                    +----+----+
                                    |         |
                                [Cluster A] [Cluster B]
                                    |         |
                                [Dig deep] [Skip]
                                    |
                                [Find violation]

From exhaustive linear scanning to hierarchical strategic search, the core shift is treating trace collections as explorable landscapes rather than flat lists.

Expert Assessment

Problem choice: This is a real gap. As AI agents deploy at scale, auditing becomes a bottleneck. The paper targets a genuine pain point — existing methods genuinely don’t scale to production trace volumes. The problem sits at the intersection of AI safety and practical deployment, which is timely.

Method maturity: The core insight (cluster then search) is elegant but not groundbreaking — it’s applying standard information retrieval ideas to a new domain. The execution is solid: they handle the engineering details (embedding choice, cluster granularity, agent prompting) competently. However, there’s a simpler baseline they don’t explore: active learning with uncertainty sampling. Could you achieve similar results by training a classifier and iteratively labeling high-uncertainty examples?

Experimental integrity: The results are impressive (4x improvement on CyBench, discovering benchmark cheating), but I’m skeptical of one claim. They say Meerkat “discovers widespread developer cheating” on a benchmark, but don’t provide enough detail to assess whether this is genuine cheating or legitimate optimization. The baselines are fair — they compare against per-trace LLM judges and exhaustive search within budget constraints. The ablations are thorough.

Writing quality: The paper front-loads motivation well, but the method section is dense. Section 3.2 (agent search procedure) would benefit from a concrete walkthrough with a real example. The related work section is perfunctory — they cite relevant papers but don’t position their contribution clearly against prior agentic auditing work.

Verdict: weak accept — Solid execution on a real problem with strong empirical results, but the conceptual novelty is incremental and some experimental claims need more support.

Takeaways

Hierarchical search for rare events: When searching for sparse failures in large datasets, don’t scan linearly. Cluster first, then adaptively allocate search budget. This pattern transfers beyond AI safety — think log analysis, fraud detection, or quality assurance in manufacturing.

Embedding-based clustering as a general auditing primitive: If you can embed your data (traces, logs, user sessions), clustering gives you a compressed map for investigation. The key insight: violations with similar root causes cluster together, so you can sample strategically.

Agent-in-the-loop for flexible detection: Fixed rules break on novel behaviors. Per-instance classifiers miss cross-instance patterns. An agent with access to cluster-level and instance-level views can adapt its search strategy. This is useful anywhere you need flexible, context-aware anomaly detection.

Concrete technique: Their two-stage embedding (trace → summary → embedding) is worth stealing. Directly embedding long traces is noisy; summarizing first improves cluster quality. Simple but effective.