Mara Chain: Rethinking Failure as a Stepping Stone for AI System Auto-Evolution

AI summary

Overview

Research area: Machine learning / automated optimization of compound AI systems — specifically, evolution of mutable artifacts (prompts, skills, agent harnesses, retrieval pipelines, code) rather than model weights.

Technical level: Intermediate. The paper assumes familiarity with LLM-based prompt/agent optimization loops, agent evaluation harnesses, and multi-objective (Pareto) selection, but its central idea is described in plain terms.

Scope: The paper introduces Mara Chain, a refinement procedure that keeps rejected optimization candidates and refines them along a bounded lineage instead of discarding them, and evaluates it on AppWorld (skills), TerminalBench 2.1 (agent harnesses), and MuSiQue (retrieval pipelines) across three LLMs.

What This Paper Is About

Deployed AI systems are increasingly improved by editing prompts, skills, harnesses, and code, using a propose–evaluate–select loop in which an LLM proposes a candidate configuration and an evaluator either accepts or rejects it. The authors observe that rejected candidates usually carry useful information — a partial fix, a sound direction with a buggy implementation, or a wrong attempt whose measured effect rules out a route — and that throwing them away causes later proposals to re-diagnose the same failures. The goal is a procedure that retains and refines those rejected candidates so that optimization escapes these repeated "persistent failure barriers" while keeping rollout cost bounded.

Key Contributions

1. Diagnosis of persistent failure barriers. The paper formalizes the residual of an execution — the unsolved task conditions — and describes settings where that residual stays invariant across iterations regardless of rollout budget, arguing this is caused by the standard practice of discarding any candidate that fails the acceptance bar.

2. The Mara Chain refinement procedure. A history-conditioned procedure that, when a direct candidate fails the acceptance bar, retains the candidate's rollout traces, residual failures, structured analysis, and change history, then generates a sequence of descendants along one lineage. The chain is bounded by a fixed depth, and a chain that produces no descendant beating the initial candidate is discarded, so a failed chain adds no lasting cost.

3. Pareto-filtered Top-N selection. A two-stage candidate-pool update: weakly Pareto-dominated candidates are removed using per-task validation score vectors (with the more recent candidate retained when validation vectors are identical), then, if the non-dominated set exceeds N, only the N candidates with the highest mean validation scores are kept. The second stage exists because high-dimensional per-task score vectors leave many candidates mutually non-dominated.

4. A modular framework and cross-artifact evidence. Mara Chain is implemented in a modular optimization framework with seven pluggable components across target-side, optimizer-side, and candidate-store roles, plus a concurrent scheduler running multiple slots over a shared pool and a filesystem-backed memory. The same procedure is demonstrated on three different artifact classes: skill configuration, agent-harness configuration, and retrieval-pipeline configuration.

Main Findings

• AppWorld skill optimization. On 585 recorded tasks (168 test_normal, 417 test_challenge), Mara Chain attains the best value in every metric: 89.9 / 83.9 Normal TGC / SGC, and 76.7 / 59.0 Challenge TGC / SGC. This compares with ACE (83.9 / 69.6 / 74.1 / 55.4), GEPA (83.3 / 67.9 / 69.3 / 44.6), and SkillOpt-Lite (70.8 / 51.8 / 68.3 / 46.0) against an empty-skill baseline of 48.2 / 35.7 / 33.3 / 19.4.

• Relative gains and rollout efficiency on AppWorld. Mara Chain outperforms GEPA, ACE, and SkillOpt-Lite by up to 20.5% in relative performance. It reaches a validation score of 0.8 after 3,280 rollouts versus 9,514 for GEPA — 65.5% fewer rollouts; ACE and SkillOpt-Lite never reach that score. In wall-clock terms it reaches 0.8 in 11.9 h versus 35.8 h for GEPA, and ultimately reaches 0.87 while GEPA plateaus at 0.805.

• TerminalBench 2.1 harness optimization. On 89 agentic-OS tasks, the Mara-Chain-optimized harness attains a 71.9% pass rate, exceeding the 51.7% of AHE, Codex, and the Kira base by 20.2 percentage points, and surpassing Meta-Harness and OpenCode (49.4%) by 22.5 points. The introduction reports this as a 39.1% improvement over the harness optimizers AHE and Meta-Harness.

• MuSiQue retrieval-pipeline optimization (4-hop). Optimized pipeline versus the hand-written default over top-10 retrieved documents: test nDCG@10 0.405 versus 0.301 (+0.104) and test Recall@10 0.460 versus 0.329 (+0.131); validation nDCG@10 0.553 versus 0.419 (+0.134) and validation Recall@10 0.605 versus 0.395 (+0.210). A 2-slot ablation without Mara Chain (depth 0) reached 0.371 / 0.421 test and 0.505 / 0.560 validation.

• Ablation: gains grow with task difficulty. On the easier AppWorld Normal split the effect is barely visible (Normal TGC 86.9 with Mara Chain versus 86.9 without; Normal SGC 75.0 versus 76.8). On the harder Challenge split it turns clearly positive: Challenge TGC 76.7 versus 71.9 (+4.8 pp) and Challenge SGC 59.0 versus 51.8 (+7.2 pp). The largest gain is on TerminalBench 2.1, where the pass rate rises from 57.3% without Mara Chain to 71.9% (+14.6 pp). Disabling Top-N selection degrades every AppWorld metric (Normal TGC/SGC 83.3 / 67.9; Challenge TGC/SGC 73.6 / 53.2). The paper notes there is no w/o Top-N result for TerminalBench 2.1, where Top-N uses N = 1.

• Sample efficiency of the combined mechanisms. The full setting reaches a validation score of 0.79 after 2,356 rollouts and finishes at 0.87. The w/o Mara Chain ablation (Top-N only) reaches 0.79 after 3,480 rollouts and finishes at 0.81, while the w/o Top-N ablation (Mara Chain only) needs 5,388 rollouts to reach 0.79. The paper describes the two mechanisms as synergistic.

• Cross-model generalization. Paired AppWorld comparisons across three system models show Mara Chain improving over the corresponding empty-skill baseline on every metric: +40.3 pp on GLM-5, +32.7 pp on DeepSeek-V4-Pro, and +23.4 pp on Qwen3.5-397B-A17B (mean across the four metrics). For example, on DeepSeek-V4-Pro the optimized skill reaches 93.5 / 83.9 / 81.5 / 69.8 versus an empty-skill 66.7 / 39.3 / 60.9 / 30.9.

• Case study on sanitize-git-repo. Recorded traces show that without Mara Chain, partial fixes are discarded and later proposals do not continue from them, leaving the task failed. With Mara Chain, successive descendants build on partial fixes, escalate from prose guidance to a script, correct the script's observed behavior, and eventually pass — with refinement tending to move toward higher-reliability representations.

Methodology in Plain English

The framework treats a system's editable parts — prompts, scripts, config files, code — as a real directory of files that the optimizer adds to, deletes from, and edits in place, rather than as a constrained parameter vector or domain-specific language. Each user specifies an artifact schema that defines the directory structure and the semantic role of each file.

Optimization runs an outer propose–evaluate–select loop. A parent candidate is sampled from a shared pool using leadership counts, which favor candidates that lead on different score dimensions (a candidate counts toward leadership on dimension j if it is within a small epsilon of the pool maximum on that dimension). The parent is run on a training minibatch to establish a baseline, and a candidate P_n is proposed. If P_n clears the acceptance bar against the parent, it goes to validation on the full validation set. If not, the Mara Chain is triggered.

Inside the chain, all rollout logs, traces, scores, and metadata are persisted to a filesystem-backed memory. At each chain step, the proposer reads the accumulated context — per-instance score history across chain nodes, structured analyses of prior nodes, an attributed artifact-change history, and raw run records — produces a new child that inherits the last node's artifacts, edits it, rolls it out on the same fixed minibatch, and persists the result. The chain stops as soon as a node clears the bar, or after depth d; it returns its highest-scoring node only if that node clears the same bar as the direct candidate, otherwise it returns nothing. Validated candidates then update the pool through Pareto filtering followed by Top-N truncation. Multiple slots run this procedure in parallel over the shared pool until the rollout budget is exhausted. Defaults are N = 3 and d = 5.

Why This Matters

Impact on research. The paper reframes rejected candidates from waste to evidence, and argues this is a general, model-agnostic mechanism for AI-system auto-optimization rather than a benchmark-specific trick. It connects to reflection-based methods (Reflexion, Self-Refine), quality-diversity search (MAP-Elites), and compound-system optimizers (DSPy, TextGrad, Trace, AFlow), while supplying a bounded, cost-aware variant of retaining failure evidence.

Real-world applications:

• Agent product engineering: continuously improving a deployed agent's harness or skill files to raise task pass rates on long-horizon, multi-step work without retraining the underlying model.
• Retrieval and RAG operations: tuning a retrieval pipeline's node configurations, node scripts, and prompts — the MuSiQue setting — to raise ranking quality (nDCG@10) and recall over a hand-written baseline.
• Evaluation-harness maintenance: automatically evolving the harness that runs OS or computer-use tasks, as in the 89-task TerminalBench 2.1 setup, so that measured model capability is not capped by a poorly configured harness.
• Budget-constrained optimization of production systems: the reported rollout and wall-clock savings (reaching the same validation score with 65.5% fewer rollouts and in 11.9 h versus 35.8 h) matter where each evaluation run costs real compute and time.

Industry relevance. The work comes from Ant Group with collaborators at Beijing Intelligent Game and Decision Lab and Beijing Defense Innovation Institute, and targets a practical pain point: improving deployed AI systems through artifact edits under a fixed rollout budget. It is presented across three frozen target LLMs (GLM-5, DeepSeek-V4-Pro-0813, Qwen3.5-397B-A17B) with a Pi coding agent as proposer, suggesting the approach is meant to slot into existing toolchains rather than require a specific model.

Future Directions

1. Adaptive chain depth. Make chain depth track problem difficulty — deeper on hard barriers, earlier termination on easy ones — and use cheaper proposer models or budgeted depth to reduce wall-clock and token cost.
2. Wider exploration. Move diversity-aware selection beyond a single test score, and branch the serial lineage into a parallel "Mara tree."
3. Trustworthiness and fallback. Add per-node confidence estimates with fallback to the baseline candidate.
4. Transferable experience. Distill effective strategies into a shared experience bank that is meta-learned across artifact configurations and domains.

Two limitations the authors state are open questions in themselves: Mara Chain diagnoses one batch at a time and can overfit that batch's failure modes, which per-instance Pareto selection across batches only mitigates; and its context construction and diagnosis logic are a hand-designed first version that remains fixed throughout the search.

Target Audience

Researchers and engineers working on automated prompt, agent, skill, harness, or pipeline optimization who are already familiar with propose–evaluate–select loops and Pareto-based candidate selection. It is most useful to practitioners who optimize deployed AI systems under hard rollout budgets, and to researchers interested in failure-driven search, reflection, and quality-diversity methods for compound AI systems.

Authors’ abstract

Optimizing deployed AI systems increasingly amounts to editing prompts, skills, harnesses, and code rather than model weights. Existing approaches commonly optimize these artifacts through propose-evaluate-select procedures, where candidate configurations are evaluated and only those meeting an acceptance criterion are selected. Yet our analysis shows that discarded candidates often contain information critical for subsequent optimization. Discarding them causes later proposals to revisit the same failure modes. We introduce Mara Chain, a refinement procedure that turns rejected candidates into stepping stones. Rather than discarding a rejected candidate, Mara Chain retains and iteratively refines it using evidence accumulated across preceding attempts. The procedure limits each refinement chain to a fixed depth and applies Pareto-filtered Top-N selection to bound the candidate pool. Across AppWorld skill optimization, TerminalBench 2.1 harness optimization, and MuSiQue retrieval-pipeline optimization, Mara Chain delivers greater task-performance gains with fewer rollouts. It outperforms GEPA, ACE, and SkillOpt-Lite by up to 20.5% in relative performance on AppWorld, reaching the target score with 65.5% fewer rollouts than GEPA. It improves the pass rate by 20.2 and 22.5 percentage points over AHE and Meta-Harness on TerminalBench 2.1, respectively, and improves MuSiQue test nDCG@10 and Recall@10 by 0.104 and 0.131 over a hand-written retrieval pipeline.