DAEDALUS: Bootstrapping Agent Memory from Self-Generated Tasks

AI summary

Overview

Research area: LLM agents, agent memory, automated task generation, agentic benchmarks (AppWorld, τ²-bench, AutomationBench).

Technical level: Advanced.

Scope: The paper introduces Daedalus, a training-free method that builds reusable, environment-specific memory for an LLM agent purely from tasks the agent generates and attempts itself, without curated training tasks or an oracle verifier.

What This Paper Is About

LLM agents deployed in a new environment lack the practical knowledge needed to act reliably, so without memory they repeat the same mistakes across tasks, fail more often, and take longer trajectories. Existing ways of giving agents procedural memory require either human-written guidelines or a curated set of training tasks plus a verifier that scores each attempt, both of which assume prior knowledge of the environment and are unavailable in most settings. Daedalus removes both requirements: it bootstraps a bank of textual heuristics from self-generated practice tasks, keeping a lesson only after that lesson has demonstrably turned a solver's failure into repeated success, and injects the resulting bank into the agent's context at test time.

Key Contributions

1. A training-free memory bootstrapping pipeline. Daedalus pairs an Explorer agent that interacts with the environment to propose realistic, solvable tasks with a Solver agent that attempts them, plus a Surveyor, a Judge, an Extractor and a Consolidator, all without curated tasks or an oracle verifier.

2. Failure-to-success heuristic validation. Rather than retaining an insight based on the outcome of the trajectory it came from, Daedalus accepts a heuristic only when the Solver, with that heuristic in context, reaches N_s = 3 consecutive successes after having failed at least once on the same task. This tests the heuristic itself rather than the task's feasibility.

3. Difficulty calibration and generation-efficiency components. Task outcomes (too easy, too hard, accepted) feed back to the Explorer, which revises tasks up to N_r = 5 times; guidelines distilled from refinement histories and a one-time environment survey from the Surveyor reduce generation cost and increase the share of sessions producing an accepted heuristic.

4. Empirical and evaluative results. Comparisons against a no-memory baseline and six memory methods on three benchmarks, an analysis of cross-model-family transfer, ablations of each pipeline component, an LLM-judge validation against official verifiers, a comparison of whole-bank injection versus per-turn retrieval, and a demonstration that Daedalus-generated tasks can rank models consistently with the official AppWorld test set. Code and artifacts are released at www.github.com/illuin-tech/daedalus.

Main Findings

• Memory improves success and consistency. Daedalus raises the mean success rate (MSR) over the no-memory baseline by 15.9, 10.0 and 4.3 points on AppWorld, τ²-bench and AutomationBench respectively, and pass^5 increases by 1.7× to 2.2×. On AppWorld and τ²-bench this comes at no extra inference cost over the no-memory baseline (USD 3.2 vs 3.2, and USD 0.5 vs 0.5 per run), mainly because the agent needs fewer turns.

• It is the strongest method without training tasks, and competitive with methods that have them. Daedalus (AppWorld MSR 60.2 ±0.9, pass^5 32.1 ±3.6; τ²-bench 67.5 ±2.5, 37.5 ±7.8; AutomationBench 36.0 ±1.5, 21.4 ±4.9) beats PREPING on both metrics on all three benchmarks, and is within error margins of the best training-task method in four of six MSR/pass^5 columns, falling behind only ACE on AppWorld pass^5 (41.1 ±3.8) and ExpeL on AutomationBench MSR (42.6 ±0.5). Unlike ACE, ReasoningBank and AutoGuide, it never falls below the no-memory baseline on any benchmark.

• Self-generated tasks recover most of the benefit of curated ones. The Daedalus-curated variant, which runs the same Solver loop on benchmark training tasks, ranks first within error margins on every benchmark and metric; Daedalus underperforms it by only 0.6, 2.5 and 4.0 MSR points, with pass^5 gaps within error margins on all three.

• Heuristics transfer across model families. All nine combinations in Table 2 are positive. GPT-5.4-mini gains as much from a Qwen-generated bank as from its own (+16.8 vs +15.9). DeepSeek-V4-Flash gains less (3.0 to 8.3 points) because its no-memory baseline of 80.6% leaves less room for improvement.

• Solver traces and empirical validation drive the result. In the cumulative ablation, exploration alone hurts: a single Explorer trajectory scores 35.7 MSR versus the 44.3 no-memory baseline. Including Solver traces produces a +15.8 MSR jump (to 54.5), and adding the Solver loop's failure-triggered revisions and repeated-success validation adds +4.5 MSR (to 59.0).

• Guidelines and the survey improve cost-efficiency, not memory quality. Guidelines reduce refinements from 183 to 161 and generation cost by 12% while changing MSR by −1.1 points, within standard error. Together with the environment survey they raise the share of sessions ending in an accepted heuristic (86.7% to 97.8%) and cut generation cost by 48% relative to the Solver-loop variant (USD 210.4 to 109.7); Solver and Judge costs fall by 60% because fewer refinements are needed.

• The LLM judge agrees substantially with official verifiers. κ_bench is 0.807 on AppWorld (N = 168), 0.749 on τ²-bench (N = 40) and 0.729 on AutomationBench (N = 70), with κ_inter above 0.8 on every benchmark. Precision exceeds recall everywhere (e.g. .943 vs .846 on AppWorld), so the judge leans toward rejecting successes rather than accepting failures.

• Gains emerge with a tiny exploration budget and then plateau and decline. Five sessions already deliver more than half of the improvement reached at the 90-session peak; beyond 90 sessions MSR decreases as the bank grows, and a hierarchical consolidation designed for large banks does not recover the loss (54.6 vs 53.7 MSR).

• A weaker auxiliary model still helps. Running all auxiliary agents on GPT-5.4-mini yields a bank that beats the no-memory baseline by 6.9 MSR and 5.3 pass^5 points, about half the gain obtained with GPT-5.4 as the auxiliary model (51.2 ±1.6 vs 60.2 ±0.9 MSR).

• Whole-bank injection at task start beats per-turn retrieval at this scale. The consolidated bank improves MSR by 10.7 points over the unconsolidated heuristics, while deduplication alone gives no significant gain. Random, BM25 and Qwen3-Embedding-4B top-5 retrieval all improve over the no-memory baseline by up to 10 MSR points but do not differ significantly; BM25 with k = 30 reaches 58.2%, still below whole-bank injection. The authors suggest useful heuristics are relevant in a latent, "oblique" way rather than semantically similar to the current step.

• Generated tasks can serve as an evaluation proxy. On the 81 accepted tasks of the 90-session AppWorld run, nine models without memory are ranked consistently with the AppWorld normal test split (Kendall's τ = 0.89, p < .001 for both MSR and pass^3; 34 of 36 model pairs ordered consistently). Absolute success rates differ because the generated tasks were calibrated to GPT-5.4-mini.

Methodology in Plain English

The method spends a one-time budget of n practice sessions in the target environment. Each session has an outer and an inner loop. In the outer loop, an Explorer agent explores the environment, proposes a realistic instruction with explicit success conditions, and completes the task itself to confirm it is solvable. In the inner loop, a Solver agent attempts the task from a freshly reset environment while an LLM Judge checks the trajectory against the success conditions. When the Solver fails, an Extractor writes a heuristic from the instruction and the failed trajectory (or revises the previous one), and the Solver retries with that heuristic in context. Crucially, the Extractor is not told which success conditions were missed, which pushes it toward general rather than task-specific fixes. The loop stops when the Solver succeeds three times in a row or reaches eight cumulative failures. A heuristic is accepted only if the Solver failed at least once before that streak of three successes; if the Solver never failed, the task is too easy, and if it hit the failure cap, too hard. The Explorer uses that outcome to revise the task harder or easier, up to five times.

Two extra components reduce cost. Before the first session, a Surveyor explores the environment once and defines a target distribution of tasks across its areas, which the Explorer follows to diversify coverage. After any session that required refinement, the refinement history becomes guidelines that help the Explorer calibrate difficulty in later sessions. Finally, a Consolidator merges the accepted heuristics in a single LLM call, removing redundancy while preserving actionable guidance, and the resulting frozen bank is injected once at the start of each test task.

Evaluation uses AppWorld's normal test split, the retail domain of τ²-bench (airline is excluded because it contains ground-truth errors and telecom's dual-control setting would require simulating user-side tools), and the Operations split of AutomationBench. Splits are 90/168 training/test tasks for AppWorld, 74/40 for τ²-bench retail, and 30/70 for AutomationBench Operations, stratified by the number of services each task involves. One Daedalus session is run per training task so that the generation budget matches the number of tasks available to baselines. All auxiliary agents run on a larger model (GPT-5.4, or GPT-5.6 Terra on AutomationBench) while the Solver and base agent run on a smaller one (GPT-5.4-mini, or GPT-5.6 Luna). Each method builds one memory bank and is averaged over five independent inference runs, reporting mean success rate and pass^5 with standard errors, plus inference cost in USD per run at OpenAI standard-tier prices assuming perfect prompt caching.

Why This Matters

Memory is usually the part of an agentic system that requires the most human preparation: someone has to collect representative tasks, write a verifier, and check that the lessons are correct. Daedalus shows that an agent can supply that supervision itself, in an environment nobody has prepared, and still come close to methods that were given curated training tasks — at little or no extra inference cost. The finding that exploration-only memory actively hurts (35.7 MSR versus a 44.3 no-memory baseline) while empirically validated, failure-grounded memory helps is a concrete design lesson for anyone building agent memory: what is stored matters less than whether it was tested against the solver's own failures. The cross-family transfer results and the proxy-evaluation result also matter for practice, because they mean a bank and a test set produced once can be reused for other models.

Real-world applications:

• Enterprise and SaaS workflow automation: the AutomationBench setting (business workflows across services) is exactly where agents are deployed without curated training data.
• Customer-service agents: the τ²-bench retail setting covers conversational tasks where environment conventions must be discovered rather than documented.
• Code and app automation: the AppWorld setting covers Python-driven app interaction, a common pattern for internal tooling agents.
• Model and agent evaluation: Daedalus-generated tasks ranked nine models consistently with the official test split, offering a proxy evaluation set for environments that have no curated benchmark.

Industry relevance: the method is training-free and leaves model weights untouched, so it applies to closed as well as open models, and the ablation on auxiliary model choice shows it still delivers roughly half its benefit when only a smaller model is available. The released artifacts — configurations, generated tasks, heuristic banks, and all agent trajectories — lower the barrier to reproducing and auditing the pipeline.

Future Directions

• Scaling the bank. On AppWorld, performance declined beyond 90 sessions as memory grew, and hierarchical consolidation did not recover the loss; the authors flag how the composition and coverage of the bank vary across environments as an open question.
• Better consolidation for large memories. Consolidation can misstate the scope of some heuristics, and minor changes had a large impact on parts of the test distribution, so more reliable merging is needed.
• Retrieval suited to large memories. Whole-bank injection worked best at this scale, but large banks call for retrievers designed for "oblique" queries, where the relevant heuristic is not semantically similar to the current step. BM25 at k = 30 still trailed whole-bank injection.
• Updating memory at test time and improving judging. Daedalus builds the whole bank before deployment and relies on an imperfect LLM judge; the authors name test-time memory updates and more reliable multi-judge validation as natural next steps.

Target Audience

Researchers and engineers working on LLM agents, agent memory, self-improving or self-play agent systems, and agentic benchmark construction. It is also relevant to practitioners who need to deploy agents in environments where no curated task set or verifier exists, and to those interested in using agent-generated tasks for model evaluation. Readers should be comfortable with terms such as in-context memory, pass^k, and agentic benchmark evaluation.

Authors’ abstract

LLM agents often lack the operational knowledge to act reliably in new environments, as they must discover specific tool behaviors or environment conventions on their own. Without memory of past attempts, they repeat the same mistakes across tasks, leading to more task failures and longer trajectories. To address this, agentic systems typically rely on human-written guidelines or on procedural memory built from training tasks and an oracle verifier, both of which require prior knowledge of the environment. We present DAEDALUS, a method for bootstrapping reusable agent memory from self-generated practice without existing tasks or oracle verifiers. DAEDALUS pairs two agents: an explorer that interacts with the environment to generate challenging yet solvable tasks, and a solver that attempts them. A heuristic is derived from each solver failure and accepted only after the solver repeatedly succeeds with that heuristic in context. These outcomes also provide feedback for the explorer to refine the difficulty of future tasks. Accepted heuristics are then consolidated into a memory bank for test-time use. Across AppWorld, $τ^2$-bench, and AutomationBench, DAEDALUS improves mean success rates by up to 15.9 points and pass^5 by up to 2.2x over a no-memory baseline, and is competitive with methods using training tasks, at a lower inference cost than most. We show that performance gains already emerge with a small exploration budget, and that its heuristics also benefit agents from other model families. Our ablations further reveal that solver traces provide the key information needed to derive effective heuristics, while factorizing early discoveries makes exploration more cost-efficient. Beyond memory construction, we find that the tasks generated by DAEDALUS can serve as a proxy for benchmark tasks when ranking models by performance. Code and artifacts: www.github.com/illuin-tech/daedalus.