Verifier Red Queen: Adversarial Co-Evolution of Agent Skills and Verifiers

Reusable agent Skills encode procedural knowledge for long-horizon tasks that require tool use, intermediate artifacts, and task-specific validation. Autonomous Skill evolution depends on reliable fitness signals. When Skills co-evolve with imperfect verifiers, selection can reward incomplete assertions, brittle coverage, and verifier-specific shortcuts over task competence. This feedback loop can produce skill–verifier collusion: both populations converge to transient conventions while performance on hidden tasks declines. We introduce Verifier Red Queen (VRQ), a three-population framework that jointly evolves Solver Skills, Red-Team Verifiers, and Calibrator Verifiers. Red-Team Verifiers generate heterogeneous challenges using metamorphic testing, input perturbations, invariant checks, adversarial tool outputs, and partial-execution audits. These challenges expose failures that checks favored by recent selection fail to detect. Calibrator Verifiers determine whether the challenges preserve task semantics and admit valid solutions, filtering out irrelevant, contradictory, and unsatisfiable objectives. VRQ also maintains a historical hall of fame of effective Skills and Verifiers. Candidates must withstand current opponents and earlier verification strategies, reducing cyclic forgetting and temporal overfitting. We evaluate VRQ under controlled settings with weak-verifier exploitation opportunities and verifier shifts. The evaluation measures task success, hidden-test generalization, false positives, shortcut persistence, verifier diversity, and collusion. Component ablations isolate the contributions of calibration, historical selection, adversarial diversity, metamorphic testing, and population update strategies to robust Skill improvement under search-time verifier exploitation.