RHO: Label-Free Agent Harness Optimization from Historical Trajectories Lifts SWE-Bench Pro from 59% to 78%

Forum topic · 小凯 · 2026-06-14

Summary

RHO (Retrospective Harness Optimization), from Microsoft Research Asia and City University of Hong Kong, is a label-free method for improving deployed AI agents using only their own past execution trajectories. Without any ground-truth annotations, validation sets, or external scorers, RHO runs a three-step pipeline: (1) DPP-Greedy selection of 10 representative core tasks balancing difficulty and diversity via abstract LLM-generated fingerprints; (2) grouped rollouts with self-validation and self-consistency diagnostics scored by severity; and (3) Best-of-N candidate harness generation with strict positive self-preference acceptance. A single optimization round raises Codex's pass rate on SWE-Bench Pro from 59% to 78% (+19 points), outperforming memory- and skill-library baselines like Dynamic Cheatsheet, ReasoningBank, and Sleep-time Compute, and beating validation-set-driven Meta-Harness with 3x less compute and no annotations. Analysis shows domain-specific behavioral changes—more verification in code tasks, more navigation in terminal tasks—concentrated gains on long-horizon tasks, and a deliberately conservative design that minimizes regression risk.

RHO: Evolving Agents in the Dark with Self-Preference

How do you know whether a deployed agent is getting better or worse? The conventional answer—build an annotated validation set—is impractical in production: future task distributions are unknown, expert annotation is prohibitively expensive, and human feedback arrives too late.

Researchers from Microsoft Research Asia and City University of Hong Kong propose RHO (Retrospective Harness Optimization): let the agent learn from its own unlabeled historical trajectories. No annotations, no validation set, no external scorer. A single optimization round lifts pass rate on SWE-Bench Pro from 59% to 78%—a 19-point absolute gain with zero ground-truth labels.

Key points

1. Why label-free matters

Existing agent-improvement methods all depend on labeled data:

Prompt optimization needs labeled good/bad examples
Memory augmentation needs validation sets to filter experiences
Skill library evolution needs scorers to judge skill quality
Meta-Harness needs full validation sets for multi-round iteration

RHO's premise: the agent's own trajectories—successes and failures alike—are themselves the signal source.

2. Three-step pipeline

Step 1: Core set selection (DPP-Greedy). From tens of thousands of past tasks, RHO picks 10 representative ones using a Determinantal Point Process that balances:

*Difficulty*: rich failure signal worth learning from
*Diversity*: coverage of different failure modes

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

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

where $e^{r_i}$ are difficulty weights and $$S$$ is the cosine-similarity matrix. θ=0.7 (difficulty-dominant, diversity-constrained) is optimal: 78% vs. 62% (pure difficulty) and 58% (pure diversity) on SWE-Bench Pro.

Step 2: Grouped rollouts with self-diagnosis. Each of the 10 core tasks runs 3 times, yielding 30 parallel trajectories analyzed by two signals:

Self-validation: the agent checks each trajectory for wrong tool calls, wrong assumptions, premature stops, exploiting its knowledge-aware refusal ability; output is JSON diagnostics.
Self-consistency: divergence across the 3 trajectories per task—divergent plans, different tool sequences, contradictory answers—indicates high uncertainty.

Signals are merged into diagnostic instructions $$I_t$$ with severity scores (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 with self-preference. Diagnostics generate N=3 candidate harnesses; each is pitted against the original on the core tasks, scored by the agent on a $$[-10, +10]$$ scale. The acceptance threshold is strictly positive (> 0), not non-negative: "Breaking ties in favor of change would inflate regression risk for no expected gain." RHO's conservative philosophy: prefer no change over making things worse.

3. Results

vs. feedback-free baselines:

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

Memory/skill methods change only part of the agent; RHO optimizes the entire harness (tools + prompts + skills + workflow).

vs. validation-set methods: RHO (no labels, 1.0× compute) scores 78%; Meta-Harness (labels, 10 rounds, 3.1× compute) needs 320 units of compute to reach 80%. RHO wins on both efficiency and practicality.

4. Behavior actually changed

SWE-Bench Pro: Verify +61%, Navigate −13%
Terminal-Bench 2: Navigate +27%, Edit −44%
GAIA-2: Execute +25%, Edit −17%

Gains concentrate on long-horizon tasks, where systematic workflow flaws (forgetting to verify, premature stopping) dominate—precisely what RHO fixes.

5. Why it matters

1. Solves a real deployment pain point—no annotated validation set needed. 2. Single round, no iteration—can run while the agent is idle. 3. Full-harness optimization, not just memory or skills. 4. Conservative deployment philosophy—strictly positive acceptance, no task-specific hardcoded fixes, priority on high-severity recurring failures. 5. Self-supervised generality—no reward design, no domain-specific scorers; any agent with trajectory logs can use it.

6. Limitations

Compute cost: requires re-running core tasks (k×G) and candidate evaluation (N×k)—cheaper than 10-round Meta-Harness, but not free.
Depends on trajectory quality: garbage history yields nothing; the agent must succeed at least sometimes.
Blind spots: self-validation misses hallucinations the model can't detect.
Fingerprint quality: DPP selection is only as good as the LLM's abstract descriptions.

Even so, the ROI is hard to refuse: a 19-point gain on core agentic capability from one retrospective optimization at zero annotation cost.

---

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.