LLM agents often lack operational knowledge when entering new environments, forcing them to discover tool behaviors or environment conventions on their own. Without memory of past attempts, they repeat mistakes across tasks, leading to higher failure rates and longer trajectories. Existing solutions rely on human‑written guidelines or procedural memory built from training tasks and an oracle verifier, both of which presuppose prior environment knowledge.
DAEDALUS introduces a self‑bootstrapping memory construction method that requires neither pre‑existing tasks nor an oracle. The system pairs two agents:
- explorer: interacts with the environment to generate tasks that are challenging yet solvable;
- solver: attempts to solve those tasks.
When the solver fails, a heuristic is extracted from the failure trace and is only accepted after the solver repeatedly succeeds using that heuristic in context. Accepted heuristics feed back to the explorer to adjust the difficulty of future tasks. All accepted heuristics are consolidated into a memory bank for use at test time.
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.2× over a no‑memory baseline, while remaining competitive with methods that rely on training tasks, but at a lower inference cost. Performance gains appear even with a modest exploration budget, and the generated tasks can serve as proxy benchmarks for model ranking.
Ablation studies reveal that solver traces provide the essential information for deriving effective heuristics, and factorizing early discoveries makes exploration more cost‑efficient.
The code and artifacts are publicly available at www.github.com/illuin-tech/daedalus.
Review