SBCO: Self-Supervised, Verifier-Grounded Harness Optimization For Planning Agents

SBCO: Self-supervised Block Coordinate Optimizer is a method for improving planning agents with explicit constraints. It is a verifier-grounded harness optimizer in the same closed-loop, improve-from-experience family as the Gödel-machine methods, but self-supervised rather than self-referential. Given an agentic harness, "SBCO learns a decomposed bank of per-constraint verifiers and a policy that checks the agent’s output and repairs it when a reliable verifier fires. The optimizer is a fixed meta agent: it improves the harness by approximate block coordinate ascent with textual gradients, from its own graded feedback and with no human labels."

The harness is formalized as a tuple (P, T, W) consisting of a prompt P, frozen tools T, and an agentic workflow W, which is further partitioned into a set of verifiers V and a policy Π. SBCO iteratively alternates between two phases: (a) optimizing the verifier set V while fixing P and Π, and (b) optimizing the prompt P and policy Π while fixing V. Both optimizations are done in textual space using textual gradients obtained through a critic/strategist.

For each constraint c, SBCO learns a verifier with a signature block (describing input/output signatures and semantics) and an implementation block (the actual function body). Verifier quality is judged using a small set of baseline evaluations to construct a ground-truth set, scored by precision/recall (F1). A verifier is accepted into the bank only if it clears a reliability floor (precision τP = 0.80, recall τR = 0.55). The outer loop iterates through blocks in sequenced order, using tactical refinement with textual gradients interleaved with strategic pivots to break out of local optima. A keep-best ratchet prevents regression, and downstream phases can escalate to upstream phases to re-open artifacts.

Experiments use the DeepPlanning benchmark with two long-horizon planning tasks: Travel Planning and Shopping. The task agent uses GPT-5.4-mini as backbone, with GPT-5.4-medium as critic/strategist. Baselines include the Huxley-Gödel Machine (HGM), a domain-customized variant (HGM-C), and a no-op baseline. Results show SBCO matches HGM-C on Travel (84 vs. 83 composite) and exceeds it on Shopping (94 vs. 91 match, 79 vs. 70 case accuracy), while using 4–5.5× less compute budget (733 vs. 4000 plans on Travel, 989 vs. 4000 on Shopping). The naive HGM barely improves at 8000 plans. The train-validation gap is negligible (Travel 84.3 vs. 83.9; Shopping 93.7 vs. 94.8), indicating no overfitting.

SBCO also demonstrates generalization: learned verifiers and policies transfer across backbone LLMs. Transferring a GPT-5.4-mini-learned policy to a Mistral task agent lifts Mistral from 32.2 to 42.1 composite on Travel (+9.9), comparable to optimizing from scratch (+9.6 to 41.8). On Shopping, transfer lifts Mistral from 62.3 to 94.4 (+32.1).

Qualitative analysis shows learned verifiers are highly reliable (mean precision > 0.97). For Travel, the best verifiers (F1=1.00) handle local, decidable predicates like hotel rating, cheapest direct train, budget constraints, and diverse attraction options. The worst verifiers (F1≈0) involve geo-spatial proximity (e.g., restaurant closest to attraction) and derived-quantity reasoning (e.g., reasonable transfer time), where the feedback signal is not rich enough. For Shopping, the best verifiers (F1 up to 1.00) check missing required attributes (color, brand, size, delivery time, rating, review count, sales volume) and coupon presence. The worst verifiers involve over-inclusion (extra products) with low precision (0.14–0.53).

The learned policies are task-specific. Travel learns a gated, LLM-replan-centric pipeline with tiered reliability gating (acting on hard verifiers at precision ≥ 0.98, commonsense at ≥ 0.999), a three-stage repair (deterministic code patch, batched LLM replan with verbatim literal copying, narrow commonsense replan), and conservative verify-and-accept (reverting if no improvement). Shopping learns a code-application-dominant policy that appends missing products/coupons without removing existing ones, exploiting the reward function's recall-only nature, with at most two grouped LLM replans for remaining failures.

Error analysis shows SBCO fixes precisely the constraints it can verify reliably. For Travel, the largest gains come from seamless intercity transfers (+5 net), hotel star service and train departure time range (+4 each), and diverse attraction options (+2). For Shopping, gains are uneven: L1 (+0.096), L2 (+0.154, largest), and L3 (+0.045, limited because coupon-stacking lacks a reliable verifier).

Limitations include evaluation on only two constraint-based planning domains, gains bounded by base LLM power, and no meta-cognitive abilities. The conclusion states that "for constraint-based planning, the bottleneck is the structure of the improvement signal: decomposed, correctness-grounded verification is a far cheaper route to comparable or better quality than expensive self-modification or metacognitive search."

Improvements to AI Systems:

1. Add a self-supervised verifier bank with reliability gating. The system learns a set of per-constraint verifiers (each with a signature and implementation block) and only acts on those that exceed precision ≥0.80 and recall ≥0.55 on a small ground-truth set. This allows the AI to autonomously decide which checks it can trust, avoiding blind self-correction.

2. Implement block-coordinate ascent in textual space for iterative self-improvement. The AI alternates between optimizing its verifiers (while fixing its prompt and policy) and optimizing its prompt/policy (while fixing verifiers), using textual gradients from a critic. This prevents the system from overfitting to a single improvement path and enables targeted, stepwise refinement without human labels.

3. Add a keep-best ratchet and strategic pivots to prevent regression and escape local optima. The system retains the best-performing version of its harness at each step, and when tactical refinements stall, it triggers a strategic pivot (e.g., re-opening upstream artifacts) to explore new solution regions. This ensures monotonic improvement and robustness against premature convergence.

4. Enable cross-backbone transfer of learned verifiers and policies. The system stores its learned verifier bank and policy as modular artifacts that can be applied to a different base LLM (e.g., from GPT-5.4-mini to Mistral). This yields large performance gains (+9.9 on Travel, +32.1 on Shopping) without retraining from scratch, effectively making the improvement reusable across models.

5. Implement tiered reliability gating for action selection. The policy acts on hard verifiers only when precision ≥0.98, and on commonsense verifiers only when precision ≥0.999. This prevents the AI from making risky changes based on uncertain checks, while still allowing high-confidence repairs.

6. Add a three-stage repair pipeline with deterministic code patches first, then batched LLM replans with verbatim literal copying, then narrow commonsense replans. This prioritizes cheap, exact fixes (e.g., appending missing products or correcting hotel ratings) before resorting to expensive generative replanning, reducing compute by 4–5.5× while matching or exceeding baseline quality.

7. Exploit reward structure explicitly via code-application-dominant policies. For tasks with recall-only rewards (e.g., Shopping), the system learns to append missing items without removing existing ones, maximizing score without risking false positives. This demonstrates the ability to infer and exploit task-specific reward dynamics from graded feedback.

8. Use decomposed verification to localize improvement signal. Instead of a single global critic, the system learns per-constraint verifiers (e.g., hotel rating ≥4, cheapest direct train, coupon present). This decomposes the improvement problem into decidable subproblems, enabling precise fixes for constraints with rich feedback (F1=1.00) and avoiding wasted effort on unverifiable ones (e.g., geo-spatial proximity).

9. Add a train-validation gap check to detect overfitting. The system reports negligible gaps (e.g., 84.3 vs. 83.9 on Travel), confirming that improvements generalize to unseen cases. This allows the AI to trust its learned policies beyond the training distribution.

10. Enable escalation from downstream phases to upstream phases. If a later optimization phase (e.g., policy refinement) fails to improve, the system can re-open earlier artifacts (e.g., verifier bank) for re-optimization, creating a feedback loop that adapts to discovered weaknesses.

---

What the Improved AI System Can Do:

• Self-improve on constraint-based planning tasks (e.g., travel itineraries, shopping lists) without human labels, using only its own graded feedback and a small baseline evaluation set.

• Achieve higher or equal task quality than expensive self-modification methods (e.g., Gödel machines) while using 4–5.5× less compute (e.g., 733 vs. 4000 plans on Travel).

• Transfer its learned improvement strategies to new, weaker base models, lifting their performance significantly (e.g., Mistral from 32.2 to 42.1 on Travel) without retraining from scratch.

• Reliably verify and repair constraints it can check with high precision/recall (e.g., missing product attributes, budget limits, hotel ratings), while gracefully ignoring constraints it cannot verify (e.g., subjective reasonable transfer time).

• Avoid overfitting and regression through ratcheting and train-validation monitoring, ensuring robust, monotonic improvement.

• Operate in a closed-loop, improve-from-experience paradigm where it iteratively refines its own verifiers and policies, adapting to task-specific reward structures (e.g., recall-only scoring) for maximal gains.