RHO: Evolving Agents in the Dark — Label-Free Harness Optimization from Historical Trajectories

After an agent is deployed, how do you know whether it's getting better or worse? The conventional answer — build a labeled validation set, run it, check the score — is impractical in real deployments: future task distributions differ from the past, and labeling costs are prohibitive.

Researchers at Microsoft Research Asia and City University of Hong Kong propose a dirtier but effective approach: let the agent study its own past failures and teach itself to improve. No labels, no validation set, no external scorer — just the agent's own historical trajectories.

This is RHO (Retrospective Harness Optimization). On SWE-Bench Pro, a single optimization round lifts the pass rate from 59% to 78% — a 19-point absolute gain with zero ground-truth labels.

Why Label-Free Is the Core Pain Point

Existing agent optimization methods almost all depend on labeled data:

• Prompt optimization: needs human-labeled good/bad examples
• Memory augmentation: needs a validation set to decide which experiences to keep
• Skill library evolution: needs a scorer to judge skill improvements
• Meta-learning (Meta-Harness): needs a full validation set for multi-round iteration

Deployment reality: 1. Future task distributions are unknown — today's validation set may be irrelevant tomorrow 2. Labeling is expensive — SWE-Bench-level tasks require professional engineer review 3. Feedback latency — by the time humans finish scoring, the agent has run hundreds of new tasks

RHO's premise: the trajectories the agent generates are themselves the signal source. Both success and failure patterns hide in unlabeled logs; the challenge is distilling them.

The Three-Step Pipeline

Step 1: Core Set Selection (DPP-Greedy)

From ~100,000 historical trajectories, RHO selects just 10 representative tasks using a DPP (Determinantal Point Process), balancing two seemingly conflicting criteria:

• High difficulty: rich failure signal
• Diversity: coverage of different failure modes

Each trajectory gets an abstract fingerprint from an LLM — forced to use only abstract structural vocabulary (invariant, precedence, boundary, propagation, ordering) with concrete names (repos, functions, frameworks) banned. Fingerprints are embedded as vectors, and the DPP kernel is:

\[K = diag(e^r) \cdot S \cdot diag(e^r)\]

where \(e^{r_i}\) is the difficulty weight and \(S\) the cosine similarity matrix. Ablations: DPP (θ=0.7, difficulty-dominant with diversity constraint) reaches 78%; pure difficulty 62%; pure diversity 58%.

Step 2: Grouped Rollouts — Self-Diagnosis

Each of the 10 core tasks is rerun 3 times (30 parallel trajectories), then analyzed with two self-diagnostic signals:

Self-Validation (within-trajectory): the agent checks each trajectory for correct and efficient completion, flagging wrong tool calls, wrong assumptions, and premature stops as JSON diagnostics.

Self-Consistency (across-trajectories): divergence among the 3 rollouts of the same task indicates high uncertainty — divergent plans, different tool sequences, contradictory answers.

Signals merge into diagnostic instruction sets \(I_t\), each with a severity score (0.0–1.0) as soft attention weights. Ablations:

• Remove self-consistency: 78% → 56% (−22%)
• Remove self-validation: 78% → 70% (−8%)
• Remove both (raw trajectories only): 78% → 60% (−18%)

Step 3: Best-of-N Candidate Selection

Diagnostics generate N=3 candidate harnesses. Candidates are evaluated on core tasks and ranked via pairwise self-preference (integer scores in \([-10, +10]\)).

Key design: the acceptance threshold is strictly positive (> 0), not non-negative. The paper's rationale: "Breaking ties in favor of change would inflate regression risk for no expected gain." RHO's conservative philosophy: better unchanged than worse.

Core Results: 59% → 78%, One Round Is Enough

vs. Feedback-Free Baselines

| Method | Type | SWE-Bench Pro | Terminal-Bench 2 | GAIA-2 | |:---|:---|---:|---:|---:| | Vanilla Codex | — | 59% | 71% | 29% | | Dynamic Cheatsheet | Skill library | 62% (+3%) | 73% (+2%) | 30% (+1%) | | ReasoningBank | Memory | 61% (+2%) | 73% (+2%) | 28% (−1%) | | Sleep-time Compute | Memory | 64% (+5%) | 73% (+2%) | 32% (+3%) | | RHO | Full harness | 78% (+19%) | 76% (+5%) | 37% (+8%) |

Other methods only optimize memory or skills (max +5%); RHO optimizes the entire harness (tools + prompts + skills + workflow), changing overall behavior.

vs. Validation-Set-Driven Methods

| Method | Needs labels | Compute | SWE-Bench Pro | |:---|:---|---:|---:| | RHO | ❌ No | 103 (1.0×) | 78% | | Meta-Harness (1 round) | ✅ Yes | 41 (0.4×) | 62% | | Meta-Harness (10 rounds) | ✅ Yes | 320 (3.1×) | 80% |

At equal compute (one round), RHO beats Meta-Harness 78% vs. 62%. Meta-Harness needs 3× compute plus labeled data to reach comparable performance (80%).

Behavior Actually Changes — Not Just Tuning

• SWE-Bench Pro: Verify actions +61% (self-checking), Navigate −13% (less aimless file browsing)
• Terminal-Bench 2: Navigate +27% (more exploration is right for CLI tasks), Edit −44%
• GAIA-2: Execute +25% (hands-on verification for knowledge tasks), Edit −17%

These changes are domain-specific — not a universal template, but targeted strategy adjustments per domain's failure modes. That is the essential difference between "harness optimization" and "prompt tuning."

Gains Concentrate on Long-Horizon Tasks

Short tasks were already correct; the optimization headroom was small. RHO's advantage is pronounced on long-step tasks (e.g., 20+ step software engineering), indicating it fixes systematic errors in long-horizon reasoning — structural workflow flaws like always forgetting to verify, always stopping early, or repeating the same mistakes on similar tasks.

Why This Matters

1. Solves a real deployment pain point: labeled validation sets are rarely feasible; RHO proves they're unnecessary. 2. Single round, no iteration: Meta-Harness needs 10 rounds; RHO needs one — you can optimize during agent idle time. 3. Optimizes the full harness, not a part: tools, prompts, and workflows — the agent's overall behavior patterns. 4. Conservative deployment philosophy: strictly positive acceptance threshold (> 0), no task-specific hardcoded fixes, prioritization of high-severity recurring failures — minimizing regression risk matters more than maximizing scores. 5. Self-supervised generality: no hand-designed reward functions, no domain-specific scorers — any agent with historical trajectories qualifies.

Limitations

• Compute cost: rerunning core tasks (k×G) and candidate evaluation (N×k) isn't free, though cheaper than 10-round Meta-Harness.
• Depends on trajectory quality: garbage trajectories in, garbage out — the agent must succeed at least sometimes.
• Blind spots: self-validation can miss certain hallucinations, biasing diagnostics.
• Fingerprint quality: DPP selection depends on the LLM's abstract descriptions being accurate.

Even so, the practical value is clear: a 19-point capability gain from one retrospective optimization at zero labeling cost — hard-to-refuse ROI in production.

---

Paper: Evolving Agents in the Dark: Retrospective Harness Optimization via Self-Preference. Wenbo Pan et al., Microsoft Research Asia & City University of Hong Kong. arXiv:2606.05922.