Technical Summary: Improving Language Agents through BREW

Problem Statement

Large Language Model (LLM)-based agents have demonstrated increasing capability in complex, multi-step tasks such as GUI automation, tool use, and data manipulation. However, a fundamental limitation persists: these agents cannot learn from experience. In every new session, an agent must rediscover solutions from scratch, repeating the same errors, redundant API calls, and failed manipulations it has previously resolved.

Existing approaches to agent memory suffer from specific deficiencies. Weight optimization (e.g., fine-tuning) bakes knowledge into opaque model parameters, resisting inspection or modular updates. Conversely, memory-augmented agents often store information at the wrong granularity: either retaining transient, raw trajectory fragments that lack generalizability, or storing high-level reflections that lack the specificity required to guide execution. Furthermore, prior methods often fail to generalize across environments or degrade performance when retrieved context is misaligned.

Methodology: The BREW Framework

The authors introduce BREW (Bootstrapping expeRientially-learned Environmental knoWledge), a framework designed to distill an agent's past interaction trajectories into a structured, retrievable Knowledge Base (KB) of natural-language recipes. Unlike code primitives used in program synthesis, BREW targets natural-language abstractions suitable for environments described and interacted with via language (e.g., GUIs, conversational interfaces).

The framework operates through the following core components:

1. Trajectory Generation and Hindsight Relabeling

The process begins by generating full-length trajectories (rollouts) for a set of queries using an LLM-powered agent. To enrich the training signal, BREW employs Hindsight Relabeling. Failing trajectories are sampled, and an LLM generates an alternative task description under which the agent's observed behavior constitutes a valid solution. Re-executing the agent on these reframed tasks converts roughly half of the originally failing trajectories into successful demonstrations, shifting the effective data distribution and surfacing latent competencies.

2. Reflector and Integrator Agents

• Reflector Agent: Takes a rollout and its evaluation labels to output sentence-level insights mapped to specific concepts (e.g., "Compress and Extract Files").
• Concept Deduplication: Generated concepts are clustered semantically to create a compact set of "meta-concepts," ensuring the KB remains modular and non-redundant.
• Integrator Agent: Incrementally builds and refines KB documents. Instead of a flat memory, the KB is partitioned into local documents, each tied to a meta-concept. This structure supports efficient, context-specific retrieval and modular updates.

3. Expand-and-Gather Monte Carlo Tree Search (EG-MCTS)

To optimize the content of the KB, BREW formalizes the construction process as a state-space search problem. Since natural-language recipes lack the clean verification signals of compiled code, the authors introduce EG-MCTS, a reward-guided algorithm that navigates the space of possible KB configurations.

• Parallel Search: The algorithm maintains parallel search trees for each meta-concept.
• Expand Phase: For each concept, the best current document state is expanded by generating new variants based on insights from rollouts.
• Gather Phase: The best states from all concept trees are gathered to form a "running-optimum" KB state. This state is used to evaluate the reward of expanded nodes, ensuring that the optimization of one concept considers its interaction with the rest of the KB.
• Reward Objective: The search optimizes a composite reward function balancing Correctness (accuracy of downstream reasoning) and Retrievability (how effectively the document is retrieved given the growing KB).

Key Contributions

1. Recipe Learning from Trajectories: A technique for distilling concept-level procedural recipes from agent interactions, guided by human-validated rubrics and task-specific graders. This partitions raw experience into modular, human-interpretable knowledge.
2. State-Space Search for Optimization: The formalization of KB refinement as a search problem solved via EG-MCTS, addressing the noise and ambiguity inherent in optimizing natural-language abstractions through parallel, reward-guided exploration.
3. Hindsight Relabeling for Coverage: An adaptation of hindsight relabeling to expand the diversity of learned recipes, converting near-miss trajectories into positive demonstrations to reveal latent agent competencies.
4. Empirical Performance: Demonstrated state-of-the-art results on domain-grounded benchmarks, showing significant gains in task success and efficiency.

Experimental Results

BREW was evaluated on three benchmarks: OSWORLD (computer-use automation), τ2-Bench (tool use), and SpreadsheetBench (data manipulation).

• Task Success: BREW achieved 10–20% gains in task success rates compared to base agents and existing memory-augmented baselines (Cognee, Agent-Mem). For instance, on OSWORLD (GTA1-7B + o3), BREW improved success from 53.30% to 61.70%.
• Efficiency: The framework reduced execution steps by 10–15%, indicating that the KB helps agents bypass redundant exploration.
• Baseline Comparison: Notably, existing baselines sometimes degraded performance below memoryless agents (e.g., Agent-Mem on OSWORLD dropped to 43.83% vs. 53.30% baseline), suggesting that naive memory injection can be harmful. BREW avoided this failure mode through its reward-driven state search, which optimizes KB content before deployment.
• Ablation Studies:
  • Search Strategy: EG-MCTS outperformed Iterative Refinement and Greedy Search, particularly in complex domains like OSWORLD where broader exploration is beneficial.
  • Hindsight Relabeling: Enabled consistent improvements across all benchmarks and search strategies, shifting the training distribution to include more diverse successful demonstrations.
  • Fidelity vs. Generalization: While other methods showed high fidelity on training data, they often failed to generalize to test sets (negative transfer). BREW's distillation of condition-action rules indexed by environment state allowed it to generalize across tasks with shared procedural sub-structures.

Significance and Claims

The paper claims that BREW provides a transparent, controllable, and modular substrate for agent optimization, offering an alternative to direct model fine-tuning. By decomposing agent memory into concept-level documents and optimizing their content via state-space search, BREW allows agents to internalize "recipes"—general patterns of what to do, when it applies, and what to watch out for—rather than memorizing raw click sequences.

The authors emphasize that the resulting Knowledge Base is inspectable and extensible. Unlike opaque policy updates, the KB captures reusable behavioral patterns that can be directly reviewed and updated. The work suggests that for real-world environments where long-term consistency and adaptability are essential, structured memory driven by experience and optimized via search is a critical step forward in language agent development. The framework achieves these improvements while maintaining memory and compute costs comparable to base LLMs, with the KB construction cost being a negligible fraction of the total compute budget when amortized over test episodes.