PaperlayerView exact revision on arXiv

Source-linked AI summary

DAEDALUS: Bootstrapping Agent Memory from Self-Generated Tasks

Antoine Edy, Max Conti, Victor Xing, Marc-Antoine Allard, Nawfal Benhamdane, Gautier Viaud

arXiv:2610.08048v1cs.AIcs.CLcs.LG

TL;DR

LLM agents need practical knowledge to act reliably in new environments, but existing procedural-memory approaches rely on curated tasks and verifiers. DAEDALUS bootstraps and tests heuristics through self-generated practice; across three benchmarks, it improves success rates and pass^5 over a no-memory baseline.

  • Problem

    Agents need practical knowledge that carries across tasks, but procedural memory typically requires curated training tasks and an oracle verifier, which demand prior environment knowledge and human effort.

    Source: §1 · pp. 1–2

  • Method

    DAEDALUS generates and calibrates practice tasks, derives heuristics from solver failures, and retains them only after repeated success before building a test-time memory bank.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Across AppWorld, τ 2-bench, and AutomationBench, success rates improve by up to 15.9 points and pass^5 by 1.7 to 2.2× over a no-memory baseline, at little to no extra inference cost.

    Source: §1 · p. 2

  • Takeaways & Limitations

    DAEDALUS-generated tasks rank models consistently with official benchmark test sets, suggesting an evaluation proxy when curated tasks do not exist.

    Source: §1 · p. 2

    DAEDALUS builds its bank before deployment and relies on an imperfect LLM judge; on AppWorld, performance declined beyond 90 sessions as memory grew.

    Source: §6 · p. 9

Abstract

from arXiv · show

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, $\tau^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.

1 INTRODUCTION

Agents need practical knowledge that transfers across tasks, but conventional procedural memory depends on curated tasks and verifiers that new environments may lack. DAEDALUS builds and tests heuristics through self-generated practice, improving benchmark success and pass^5 over a no-memory baseline.

1 INTRODUCTION

  • Reliable action in complex environments requires practical knowledge that carries across tasks; without procedural memory, agents rediscover environments, making avoidable errors and longer, costlier executions.The passage notes the adoption of agent skills as a reflection of this need.Source: §1 · p. 1
  • Up to 15.9 points higher success rates and 1.7 to 2.2× higher pass^5 over a no-memory baseline across three benchmarks, at little to no extra inference cost.The benchmarks are AppWorld, τ 2-bench, and AutomationBench.Source: Figure 1 · p. 1, §1 · p. 2
  • Conventional procedural memory draws lessons from prior attempts, but needs curated tasks and often a verifier, requiring prior environment knowledge and substantial human effort.Memory built from incoming task queries instead leaves early tasks without memory, and in both cases learning comes from the tasks the memory is meant to support.Source: §1 · pp. 1–2
  • DAEDALUS generates solvable tasks, derives in-context heuristics from solver failures, and keeps heuristics only after they enable repeated success.Task outcomes also guide difficulty refinement, and the resulting memory items are empirically tested.Source: §1 · p. 2

2 RELATED WORK

Prior work builds agent memory from task attempts, skills, and generated tasks, but often depends on predefined tasks, verifiers, or weight updates. DAEDALUS instead generates tasks to expose recoverable solver failures and retains heuristics after repeated success.

2 RELATED WORK

  • Memory methods often store insights from successful or failed trajectories without confirming that an insight helps overcome the failure; DAEDALUS retains one only after repeated success.Examples include ExpeL, AutoGuide, and reflection-based systems.Source: §2 · p. 2
  • Skill libraries can use executable code or refined natural-language skills, while many memory methods organize workflows or long-term stores; most collect experience from predefined task sets.The passage associates reward-based skill refinement with oracle verifiers or weight updates.Source: §2 · p. 2
  • Task-generation work often creates training data for weight updates; memory-focused methods favor feasible tasks or environment coverage, whereas DAEDALUS targets failures the solver can learn to overcome.The cited memory-focused approaches include Voyager, SkillWeaver [Zheng et al., 2025], and PREPING [Choi et al., 2026].Source: §2 · pp. 2–3

3 BUILDING MEMORY FROM SELF-GENERATED TASKS

DAEDALUS uses a one-time practice budget to build a bank of textual heuristics without training tasks or an oracle verifier. Explorer, Solver, and Extractor loops calibrate tasks and validate heuristics before consolidation for test-time use.

3 BUILDING MEMORY FROM SELF-GENERATED TASKS

  • A one-time budget of practice sessions builds a test-time bank of textual heuristics through nested Explorer task-calibration and Solver failure-learning loops.The Solver attempts tasks while an Extractor derives heuristics from failures.Source: §3 · p. 3
  • The Solver starts each task from a fresh environment state; after failure, the Extractor writes or revises a heuristic for the Solver to retry in context.A task is accepted after at least one failure followed by Ns consecutive successes; too-easy and too-hard tasks yield no accepted heuristic.Source: §3 · p. 3, Figure 3 · p. 4
  • The Explorer proposes and completes realistic tasks to establish feasibility, then revises tasks judged too easy or too hard, using loop outcomes to target recoverable failures.Refinement can continue up to Nr times; sessions that exhaust refinements contribute no heuristic.Source: §3 · p. 3
  • A Surveyor first maps task areas, while refinement histories become guidelines for later Explorer sessions, supporting task diversity and more efficient difficulty calibration.The Surveyor defines a target distribution across environment areas.Source: §3 · p. 4
  • After practice, a Consolidator merges accepted heuristics into a bank, removing redundant advice while preserving actionable guidance; the frozen bank is injected at each test task’s start.The paper compares this one-time injection choice with per-turn retrieval.Source: §3 · p. 4

4 EXPERIMENTS

DAEDALUS is evaluated on three agentic benchmarks against no-memory, self-generated-memory, and training-task memory baselines. It improves over no-memory, is competitive with training-task methods, and transfers across model families.

4.1 EVALUATION FRAMEWORK

  • Evaluation covers AppWorld, τ 2-bench retail, and AutomationBench Operations, using held-out test tasks and five inference runs per method.AutomationBench Operations is split 30/70; τ 2-bench excludes airline and telecom, while AppWorld uses its normal test split.Source: §4.1 · pp. 4–5
  • Comparisons include no-memory, PREPING, five training-task memory methods, and a DAEDALUS-curated variant using the same training tasks.PREPING is the only other compared method that builds memory from self-generated tasks.Source: §4.1 · p. 4
  • Figure 4 illustrates calibration: an initially easy task is hardened, and h2 enters memory only after three consecutive Solver successes.The experimental loop allows up to five refinements and stops after eight failures.Source: Figure 4 · p. 5, §4.1 · p. 5

4.2 MAIN RESULTS

  • DAEDALUS is within error margins of the best training-task method in four of six MSR and pass^5 columns, trailing ACE on AppWorld pass^5 and ExpeL on AutomationBench MSR.It underperforms DAEDALUS-curated by 0.6, 2.5, and 4.0 MSR points; pass^5 gaps are within error margins on all three benchmarks.Source: §4.2 · pp. 5–6
  • MSR rises by 15.9, 10.0, and 4.3 points over no-memory on AppWorld, τ 2-bench, and AutomationBench, while pass^5 increases 1.7× to 2.2×.DAEDALUS consistently outperforms PREPING on both metrics.Source: §4.2 · p. 5, Table 1 · p. 6
  • All nine AppWorld cross-family MSR gains are positive; GPT-5.4-mini gains +16.8 from a Qwen bank versus +15.9 from its own.Table 2 reports base-agent MSR by column and improvements from banks generated by auxiliary/solver pairs by row.Source: Table 2 · p. 6, §4.2 · p. 6

5 ANALYSIS AND ABLATIONS

The analysis tests DAEDALUS’s generation pipeline, memory use, and generated tasks as evaluation proxies. It finds that solver-grounded heuristics matter for performance, while consolidation and task calibration shape inference and generation efficiency.

5.1 MEMORY GENERATION

  • +15.8 MSR comes from adding Solver traces, and a further +4.5 MSR from repeated-success validation, relative to the preceding ablation variants.Exploration-only variants underperform the no-memory baseline; validation empirically removes noisy lessons.Source: §5.1 · p. 7
  • The environment survey and task-design guidelines cut generation cost by 48% relative to (D), while guidelines alone reduce refinements from 183 to 161 and cost by 12%.Guidelines change MSR by −1.1 points, within standard error; Solver and Judge costs fall by 60% with fewer refinements.Source: §5.1 · p. 7, Figure 5 · p. 7
  • The LLM judge achieves κbench > 0.7 agreement with benchmark verifiers and κinter > 0.8 across repeated calls, with precision exceeding recall on every benchmark.The precision-recall pattern means the judge leans toward rejecting successes rather than accepting failures.Source: §5.1 · p. 8, Table 4 · p. 8
  • Five sessions yield more than half the improvement reached at the 90-session peak, but AppWorld MSR declines beyond 90 sessions as the bank grows.Hierarchical consolidation does not recover the decline.Source: §5.1 · p. 8, Figure 6 · p. 8
  • Using GPT-5.4-mini for every auxiliary agent still beats the no-memory baseline by 6.9 MSR and 5.3 pass^5 points, about half the gain with GPT-5.4.DAEDALUS remains useful without a larger auxiliary model.Source: §5.1 · p. 8, Table 5 · p. 8

5.2 MEMORY USE AT INFERENCE

  • Consolidating the bank and injecting it at task start improves MSR by 10.7 points over unconsolidated heuristics and outperforms the retrieval options tested.BM25 retrieval reaches 58.2% at k=30 but remains below whole-bank injection.Source: §5.2 · p. 8, Table 6 · p. 9

5.3 SELF-GENERATED TASKS AS EVALUATION PROXIES

  • On 81 accepted tasks from the 90-session AppWorld run, model rankings align with the normal test split for MSR and pass^3 (Kendall’s τ = 0.89, p < .001 for both).Thirty-four of 36 model pairs are ordered consistently for each metric, although absolute success rates differ.Source: §5.3 · p. 9

6 CONCLUSION

The conclusion presents DAEDALUS as a way to build environment-specific memory from self-generated tasks, retaining heuristics only after they turn solver failures into repeated successes. The accompanying algorithms formalize memory generation and its curated-task counterpart.

6 CONCLUSION

  • Across three benchmarks, DAEDALUS is strongest among methods without training tasks, competitive with methods that require them, and transfers memory across model families.The paper also reports that its generated tasks rank models consistently with curated benchmarks.Source: §6 · p. 9

A PSEUDO-CODE ALGORITHMS

  • The pseudocode formalizes memory generation, the supervised DAEDALUS-curated counterpart, and memory-augmented inference.Sans-serif names denote prompted LLM calls, small-cap names denote algorithms, and monospace names denote environment operations.Source: A PSEUDO-CODE ALGORITHMS · p. 14

A.1 DAEDALUS GENERATION

  • DAEDALUS generation initializes a survey, task, heuristic, and guideline bank, then consolidates accepted heuristics into a frozen bank.The generation inputs include n sessions and thresholds for consecutive successes, cumulative failures, and task refinements.Source: §A.1 · p. 14, A PSEUDO-CODE ALGORITHMS · p. 14
  • For each proposed task, the solver loop mines and validates a heuristic; tasks judged too easy or too hard can be refined up to Nr times.The solver loop resets the environment, retries with an edited heuristic after failure, and accepts it after Ns consecutive successes.Source: §A.1 · pp. 14–15, A PSEUDO-CODE ALGORITHMS · p. 14

A.2 DAEDALUS-CURATED

B LIMITATIONS

DAEDALUS builds a frozen memory bank for one environment, but its lifecycle, supported environments, and success signal constrain its scope. Consolidation can also lose heuristic scope, especially in smaller task categories.

Memory lifecycle

  • Memory is built once before deployment and frozen at test time; iterative updates from deployment experience remain future work after preliminary attempts yielded inconsistent gains.Source: B LIMITATIONS · p. 15

Environment and verification coverage

  • DAEDALUS assumes the Explorer can complete tasks in a resettable environment; dual-control settings such as τ 2-bench telecom are not yet supported.Success is judged by an LLM against self-written conditions, with κbench agreement of 0.73–0.81 against official verifiers.Source: B LIMITATIONS · pp. 15–16

Consolidation at scale

  • Both 140-session consolidations fall below the 90-session bank overall, though they nearly match it on 131 Other tasks; most of the gap lies in three small categories.The examples show scope loss: one merge narrows a rule to enumerating a matching container, while another broadens a public-playlist rule to any public playlist.Source: B LIMITATIONS · p. 16, Table 7 · p. 16

C MEMORY GENERATION SETTINGS

The generation settings balance retaining difficult-task heuristics against spending compute on tasks that cannot be solved or calibrated. Replay supports the value of accepted heuristics, while extractor choice affects the gain on curated tasks.

Setting the hyperparameters

  • The generation loop uses Nf = 8 failed attempts and Nr = 5 refinements: smaller limits risk losing hard-task heuristics, while larger ones spend compute on uncalibratable tasks.Most heuristics are accepted after one or two failures, but a tail needs up to seven; most sessions need at most two refinements, with only a handful needing four or five.Source: C MEMORY GENERATION SETTINGS · p. 16, Figure 9 · p. 16

Impact of the extractor model choice

  • On curated AppWorld tasks, the gain over no memory falls from 16.5 to 12.8 MSR points with GPT-5.4-mini at high reasoning effort, and to 9.5 points with reasoning disabled.Pass^5 does not change; every extractor still improves the solver by a clear margin.Source: C MEMORY GENERATION SETTINGS · p. 17, Table 8 · p. 17

Counterfactual replay of accepted heuristics

  • With accepted heuristics, AppWorld MSR rises from 66.7% to 77.0% and pass^3 from 40.7% to 55.6% across 81 tasks.Paired-bootstrap 95% confidence intervals exclude zero for both gains.Source: C MEMORY GENERATION SETTINGS · p. 17

D MEMORY RETRIEVAL AND INJECTION

Retrieval gains depend more on how many heuristics are surfaced and kept in context than on the retriever or a dedicated query. Persistent guidance performs better than transient injection, while whole-bank injection remains strongest in the reported comparisons.

Retrieval method and number

  • At k=5, dense, sparse, and random retrieval do not differ significantly; increasing BM25 retrieval improves MSR and pass^5, with gains plateauing at k=10–20 before rising again at k=30.Retrieval approaches whole-bank injection only when it surfaces about half the bank; for a 3.1k-token bank, a subset offers no practical benefit.Source: D MEMORY RETRIEVAL AND INJECTION · p. 17

Retrieval query source

  • R2R costs 14.8 versus 3.8 per run and reaches no-memory MSR (44.2 vs. 44.3) while falling below baseline pass^5 (11.9 vs. 14.9).A dedicated query adds a second LLM call per turn and does not make retrieval more precise.Source: D MEMORY RETRIEVAL AND INJECTION · p. 18, Table 9 · p. 18

Injection policy

  • TRANSIENT retrieval yields 48.5 MSR and pass^5 of 13.1, below the no-memory pass^5 baseline; deduplication beats repetition on MSR (54.3 vs. 50.0).NO REPLACEMENT reaches 56.0 MSR but remains below whole-bank injection at task start (60.2); whole-bank injection at every turn also underperforms injecting it once at the start, at higher cost.Source: Figure 10 · p. 17, D MEMORY RETRIEVAL AND INJECTION · p. 18, Table 10 · p. 18

E EXPERIMENTAL SETUP DETAILS

The experimental setup standardizes model roles and baseline implementations, while documenting task filtering, environment constraints, and generation cost. DAEDALUS uses substantially more Solver rollouts than the baselines, chiefly because generated tasks need calibration.

Models and shared settings

DAEDALUS

  • The 90-session AppWorld run retained 88 accepted heuristics after an experimental filter removed seven near-duplicate accepted tasks and replaced them with seven successful sessions.The filter was not part of the general method or used on other benchmarks; analyses of that run use only the 81 originally accepted tasks.Source: E EXPERIMENTAL SETUP DETAILS · p. 19, Table 12 · p. 19

τ 2-bench retail environment

  • For τ 2-bench retail, the Explorer rejects generated tasks whose reference solution exchanges more than one item in a call, avoiding grades that depend on argument order.The environment and benchmark tasks remain unmodified.Source: E EXPERIMENTAL SETUP DETAILS · p. 19

Baselines

  • The reimplemented baselines use specified adaptations, including frozen test-time ReasoningBank memory and ACE's offline, no-ground-truth playbook variant.PREPING uses released code and, on τ 2-bench, its proposer sees sampled database records to write feasible tasks.Source: E EXPERIMENTAL SETUP DETAILS · p. 19, Table 13 · p. 20

Memory construction budget

  • DAEDALUS uses 1,225 Solver rollouts, about 6 times ExpeL and 14 times single-attempt methods; 705 rollouts refine tasks that were too easy or hard.The Solver loop itself costs about as much on generated tasks as on curated ones, while task calibration roughly doubles it.Source: E EXPERIMENTAL SETUP DETAILS · p. 19, Table 14 · p. 20

Environment access during generation

  • Generation does not access test-task states; it uses training-task worlds on AppWorld and AutomationBench, while τ 2-bench methods share one database.On AppWorld, generation excludes Amazon and Gmail, which appear only in the challenge split.Source: E EXPERIMENTAL SETUP DETAILS · p. 20

F.1 GENERATED TASK AND ACCEPTED HEURISTIC

Table 15 presents an AppWorld example of an Explorer-generated task, its Judge-checked success conditions, and the heuristic accepted after the Solver loop.

F.1 GENERATED TASK AND ACCEPTED HEURISTIC

  • Table 15 presents one AppWorld task generated by the Explorer, along with its success conditions and accepted heuristic.The Judge checks the success conditions; the heuristic is accepted after the Solver loop.Source: §F.1 · p. 21, Table 15 · p. 21
  • The example identifies the success conditions checked by the Judge.Source: §F.1 · p. 21
  • The table also shows the heuristic accepted after the Solver loop.Source: §F.1 · p. 21

F.2 A COMPLETE GENERATION SESSION

Figure 11 shows part of DAEDALUS generation session 78 on AppWorld; after 12 exploration turns, the Explorer proposes a task about assigning unfinished, unassigned tasks in shared Todoist projects.

F.2 A COMPLETE GENERATION SESSION

  • After 12 exploration turns, the Explorer proposes a task about assigning unfinished, unassigned tasks in shared Todoist projects, excluding subtasks.Source: §F.2 · p. 22
  • The proposed task asks for assignments across any of the user's shared Todoist projects.Source: §F.2 · p. 22
  • Figure 11 depicts a partial view of DAEDALUS generation session 78 on AppWorld.Source: Figure 11 · p. 22

F.3 SURVEYOR OUTPUT

This section presents the surveyor outputs and benchmark-specific prompts for generating and assessing challenging, natural tasks, guiding solver operation, and turning failures into reusable lessons. It also describes prompt choices including simplified AppWorld guidance and business-operations decision rules intended to transfer across tasks and applications.

F.3 SURVEYOR OUTPUT

  • The surveyor favors rich end-user domains and cross-app work, warning against shallow CRUD over-coverage and under-coverage of Todoist and Splitwise.It assigns Spotify 22%, Todoist 18%, and Splitwise 17%; Phone is used regularly and File System often as a helper in cross-app tasks.Source: §F.3 · p. 23

G PROMPTS

  • The appendix presents shared and benchmark-specific prompts, with role colors distinguishing task generation, judging, memory work, and solving.It notes that prompts may be partial, use runtime placeholders, and share text with other prompts.Source: G PROMPTS · p. 23

G.1 DAEDALUS PROMPTS

  • The Surveyor prompt requires an empirically grounded coverage plan and a closed tag manifest whose tags identify meaningful, measurable coverage gaps.Tags must be falsifiable; anything with a target much above half belongs in guidance rather than the coverage manifest.Source: §G.1 · p. 24
  • Explorer prompts call for grounded, natural, under-specified tasks whose difficulty comes from substantial scope and real constraints, not contrived rules or extra steps.Tasks should be brief but substantial, calibrated to a capable solver, and revised with small targeted changes when too easy or too hard.Source: §G.1 · pp. 24–26
  • Judge and memory prompts evaluate intended outcomes and turn solver attempts into concise, generalizable heuristics that are updated and consolidated without redundancy.The judge requires evidence for group-wide outcomes; extraction and consolidation prioritize actionable lessons, coverage, and minimality.Source: §G.1 · pp. 27–28

G.2 BENCHMARK-SPECIFIC PROMPTS

  • For AppWorld, the authors replace the original solver prompt’s extensive human-written heuristics with a simplified version to evaluate methods with less hand-engineered guidance.Source: §G.2 · p. 29
  • The environment block specifies authentication, API discovery, explicit access-token use, field inspection, and verification before completing a task.It instructs agents to retrieve matching account credentials, log in through the app, pass the returned token to protected calls, and re-read changed records or re-derive answers before calling complete_task.Source: §G.2 · p. 29
  • The customer-service memory prompt asks for discrete, generalizable lessons covering policy, information gathering, tool arguments, communication, and task completion.Each output bullet follows a “When <situation>, <do this>” format and excludes task-specific identifiers or values.Source: §G.2 · p. 30
  • The business-operations prompt prioritizes reusable decision rules over task-specific endpoint recipes, with a narrow exception for mechanical traps that recur across services.It targets failures in evidence gathering, qualification, source authority, and verification that a write took effect, and requires bullets to describe task shape rather than the application.Source: §G.2 · pp. 30–31
Loading 2610.08048v1…