Self-Generated In-Context Examples Improve LLM Agents for Sequential Decision-Making Tasks

Thank you for your thoughtful review and positive assessment. We are excited that you liked our approach's strong performance, the connection to episodic memory in cognitive science, and appreciated how the design of our components work together to maintain general applicability with minimal task-specific modifications.

Computational costs (including the training as well as retrieval costs at every step), are not analyzed thoroughly, so we cannot be certain that the costs are justified.

Cost Analysis: We provide detailed token usage to address your cost-benefit question. Average tokens per request: 5,047/68 input/output tokens (Wordcraft), 5,385/37 (InterCode), 3,706/30 (ALFWorld), with a maximum episode of 8, 20, and 61 requests respectively. More generally, for any task, we require 2 requests per step (reasoning + acting), plus 1 additional request when using planning (see Appendix D6, L550-556). At GPT-4o-mini pricing (0.15/0.6 USD per 1M tokens), cost per episode ranges from 0.004 USD for InterCode to 0.035 USD for ALFWorld. To collect 1000 episodes, maximum API costs range from 4-35 USD.

Contextualizing the costs of scaling performance along various axes: In Section 6.3, we demonstrate that our approach can yield substantial cost savings to two common alternatives for scaling model performance: (i) switching to a larger LLM, and (ii) test-time scaling via multiple attempts per task (assuming access to a perfect verifier). On ALFWorld, our full configuration of Traj-Bootstrap + DB-Curation + Exemplar-Curation with 5 parallel databases requires 3,500 × 5 training trajectories. Using GPT-4o-mini, the worst-case cost of constructing the databases is 600 USD, after which per-task `test-time' cost of using GPT-4o-mini is only ~0.034 USD. By comparison, using GPT-4o at test time (without collecting training trajectories) costs ~0.57 USD per task, reaching the same cumulative spend as our approach after ~1,100 test-time tasks. The alternative baseline of test-time scaling with 3 attempts per task costs a total of ~0.10 USD per task, which exceeds our method's total cost after ~8,900 test-time tasks. In other words, after a modest up-front investment (of a few hundred dollars of compute) our approach remains consistently more cost-effective than either alternative, while also improving test-time agent performance. Consider a hypothetical production agentic service processing a million ALFWorld tasks a day (a very modest industry-scale production throughput). The cost savings in a single day of using our method, including all offline dataset construction, would be 530,000 USD vs. GPT-4o, or 60,000 USD vs GPT-4o-mini with 3 trials of test time compute.

Is any tradeoff for efficiency (e.g. not retrieving at every step, retrieving only once every k steps) possible?

Retrieving every 5 steps instead of every step on ALFWorld leads to a drop in task success rate when comparing Fixed-DB baseline (0.69 vs 0.73 with every-step retrieval) and our best method Traj-Bootstrap+DB-Curation+Exemplar-Curation (0.91 vs 0.93 with every-step retrieval). This represents only 4-point and 2-point decreases respectively—a performance trade-off for substantial efficiency gains. This 5× reduction in retrieval frequency only reduces retrieval operations (from 32 to 7 per episode for ALFWorld's worst-case scenario). While performing retrieval less frequently doesn't reduce LLM token usage per call, it may significantly reduce LLM inference cost in systems with prefix caching (due to the shared prompt structure for 5 consecutive LLM invocations)

The results are limited to GPT4o-mini, limiting generalizability.

We conducted additional experiments using Mixtral 8x7B Instruct v0.1. Using databases collected with GPT-4o-mini, we compared Fixed-DB baseline versus our best method when evaluated with Mixtral. Results averaged across 5 trials show strong cross-model generalization: ALFWorld (0.55 vs 0.27, +28 points), IC-SQL (0.70 vs 0.52, +18 points), Wordcraft (0.52 vs 0.40, +12 points). These improvements match or exceed our GPT-4o-mini results, demonstrating that curated databases transfer effectively across model families and addressing generalizability concerns.

From the performance results, it appears that significant gains come from accruing a potentially critical mass of training exemplars, enough to cover the test distribution. For example, while ALFWorld is complex, its test set consists of 134 examples across 6 task types. I would not be surprised if the retrieved exemplars are extremely similar to the actual test task. That said, I think it would still be an interesting finding if this were the case.

You are correct that significant gains come from accruing a progressively larger, diverse set of training exemplars, and the algorithmic mechanism by which the Traj-Bootstrap algorithm improves performance with scale is that it becomes more likely for a training exemplar to have similarities to a later test-time task. However, note that on the benchmarks tested, there is a train-test split between the tasks. For instance, ALFWorld is evaluated on the eval-out-of-distribution split, an entirely different set of room/object layouts than the layouts present in the training set (L659). Therefore, the LLM cannot simply copy the actions from the train tasks to the test tasks.

Does the agent see few-shot exemplars aside from the ones it retrieves?

The agent is only provided retrieved trajectories—no additional few-shot examples beyond what's retrieved from our curated database. Full prompt templates are in Appendix D.2.

Can you provide examples of retrieved exemplars? It would be useful to show how the retrieved exemplars collective shape the agent's policy.

We will include concrete examples of retrieved trajectories in our Appendix to demonstrate how they collectively shape agent behavior across different scenarios. Unfortunately, we cannot include screenshots or other media in the rebuttal response this year, and showing a significant sample of trajectories in this response is not feasible due to character limits, our trajectories are similar to the ones seen as in-context examples in the ExpeL paper [1].

Is the high level plan fixed once generated? How important is it for the initial plan to be correct?

In our ReAct-style implementation, the high-level plan is generated once per task—but the agent reasons step-by-step with retrieved trajectories providing guidance for both immediate actions and longer-term reasoning patterns. The plan is important to guiding the trajectory on the longer-horizon ALFWorld task, but is omitted altogether for the shorter horizon InterCode-SQL and Wordcraft tasks. Please see Appendix D6, L550-556 for details.

We will incorporate these clarifications and additional results in our revision.

[1] Zhao, Andrew, et al. "Expel: Llm agents are experiential learners." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 17. 2024.

Thank you for your detailed review and feedback. We appreciate that you thought our experiments include a "full ablation study of each single component" and that the "paper writing is clear and the result presentation is good."

The main idea of this paper is similar to a COLM paper [Xiao 2024], which also improves LLM agents by distilling knowledge from past trajectories, and also does automatic task decomposition + learning from failed trajectories

We appreciate you highlighting the relationship with O3D, as it helps clarify our distinct contributions. While both works focus on improving LLM agents through past trajectories, our approaches are fundamentally different in philosophy and mechanism.

Key Algorithmic Differences: O3D employs data distillation, summarization, task decomposition, and explicit learning from failed trajectories. In contrast, our method intentionally avoids these complex mechanisms, instead focusing on collecting, filtering, and retrieving raw low-level trajectories. Our core hypothesis is that scaling the number of trajectories available to retrieve in-context and applying thoughtful data curation achieves performance superior to state-of-the-art methods requiring complex hierarchical learning and extensive manual prompt engineering—and our results support this claim.

Performance and Model Efficiency: Our approach achieves superior performance (93% with GPT-4o-mini for ours vs 91% with GPT-4 for O3D on ALFWorld). This demonstrates a key advantage: we can lift weaker models to strong performance purely through database scaling, without human engineering, manual prompting, or fine-tuning. Of course, improved performance with a weaker base model requires a tradeoff somewhere–and in this case that tradeoff is using more LLM calls at training time–not test time–to create a larger database of (self-collected) trajectories.

In our analysis of computational costs (included later in this rebuttal), a hypothetical production agentic service processing a million ALFWorld tasks a day (a very modest industry-scale production throughput) could save in a single day of using our method, including all offline dataset construction, 530,000 USD vs. GPT-4o, or 60,000 USD vs GPT-4o-mini with 3 trials of test time compute.

Methodological Contributions: Our work makes two distinct methodological contributions: (1) demonstrating how scaling the number of trajectories available to retrieve in-context and applying thoughtful data curation can exceed state-of-the-art methods that utilize complex hierarchical learning and extensive manual prompt engineering, and (2) presenting a novel retrieval scheme--with multi-key retrieval, re-retrieval at each step of a trajectory, leveraging similarity across “reasoning” rather than “observation”, see Appendix C for details-- extracts significant value from simple data. This challenges the assumption that complex data processing is necessary for trajectory-based improvement.

Can the authors include some results from other models (e.g. open-sourced models) to justify the generalizibility of the method?

Addressing your request for results from other models, we conducted additional experiments using Mixtral 8x7B Instruct v0.1, a popular open-source model. Using databases previously collected with GPT-4o-mini, we compared performance when Mixtral 8x7B uses our Fixed-DB baseline versus our best method (Traj-Bootstrap + DB-Curation + Exemplar-Curation). Results averaged across 5 trials demonstrate strong improvements: ALFWorld shows a 28-point boost (0.55 vs 0.27), IC-SQL achieves an 18-point gain (0.70 vs 0.52), and Wordcraft exhibits a 12-point improvement (0.52 vs 0.40). These improvements match or exceed our GPT-4o-mini results, demonstrating cross-model generalization and broader applicability.

Regarding test-time costs, it would be nice if the authors can also provide details of total number of input tokens and additional computations required for retrieval, in comparison to baseline methods.

Cost Analysis: We provide detailed token usage to address your cost-benefit question. Average tokens per request: 5,047/68 input/output tokens (Wordcraft), 5,385/37 (InterCode), 3,706/30 (ALFWorld), with a maximum episode of 8, 20, and 61 requests respectively. More generally, for any task, we require 2 requests per step (reasoning + acting), plus 1 additional request when using planning (see Appendix D6, L550-556). At GPT-4o-mini pricing (0.15/0.6 USD per 1M tokens), cost per episode ranges from 0.004 USD for InterCode to 0.035 USD for ALFWorld. To collect 1000 episodes, maximum API costs range from 4-35 USD.

Contextualizing the costs of scaling performance along various axes: In Section 6.3, we demonstrate that our approach can yield substantial cost savings to two common alternatives for scaling model performance: (i) switching to a larger LLM, and (ii) test-time scaling via multiple attempts per task (assuming access to a perfect verifier). On ALFWorld, our full configuration of Traj-Bootstrap + DB-Curation + Exemplar-Curation with 5 parallel databases requires 3,500 × 5 training trajectories. Using GPT-4o-mini, the worst-case cost of constructing the databases is 600 USD, after which per-task `test-time' cost of using GPT-4o-mini is only ~0.034 USD. By comparison, using GPT-4o at test time (without collecting training trajectories) costs ~0.57 USD per task, reaching the same cumulative spend as our approach after ~1,100 test-time tasks. The alternative baseline of test-time scaling with 3 attempts per task costs a total of ~0.10 USD per task, which exceeds our method's total cost after ~8,900 test-time tasks. In other words, after a modest up-front investment (of a few hundred dollars of compute) our approach remains consistently more cost-effective than either alternative, while also improving test-time agent performance. Consider a hypothetical production agentic service processing a million ALFWorld tasks a day (a very modest industry-scale production throughput). The cost savings in a single day of using our method, including all offline dataset construction, would be 530,000 USD vs. GPT-4o, or 60,000 USD vs GPT-4o-mini with 3 trials of test time compute.

Is it necessary to distinguish database-level and exemplar-level curation? Is it okay to simplify the organization and just do atomic-level data curation with a unified framework?

Regarding database vs. exemplar-level curation: These serve complementary purposes—database-level curation propagates the best populations of training examples while exemplar-level curation identifies high-utility individual examples. Our ablations show both contribute meaningfully to performance.

Is the retrieval on trajectory-level or sub-trajectory-level?

When planning, retrieval occurs at the trajectory level (L486-488). At each step, we retrieve a sub-trajectory window around the most relevant stat3 (L488-490). For a detailed overview of retrieval, see Algorithm 4 in Appendix C.

Table 2 uses different LLM models for baselines and proposed method, it would be nice to make them consistent.

We understand your concern about model consistency in Table 2. We use the same LLM models for baselines and proposed methods when possible. For Automanual, since source code is available, we evaluated two configurations for thoroughness: (1) GPT-4o-mini for both manual generation and inference (apples-to-apples comparison with our method), and (2) GPT-4-turbo for manual generation with GPT-4o-mini for test-set inference (representing their best-case scenario from their original paper while maintaining fair inference comparison). For AutoGuide, we report results from their paper (GPT-3.5-turbo + GPT-4-turbo) since code was not available.

Thank you for your thorough review and positive assessment of our work. In particular, we were excited that you agree with our perspective on database quality—that "database quality emerges from collective properties—like coverage, diversity, and complementarity across examples—not just individual trajectory quality." (Line 155). We also agree that this is one of the core contributions of our submission.

My main problem is that the paper discards the failed trajectories and leaves how to use them as future work. I understand their message is that performance can improve with just successful trajectories. However, I am worried about the inefficiency of LLM calls when discarding the failed ones.

We appreciate your concern about discarding failed trajectories and provide detailed analysis below.

Failed trajectories are used to improve the system: During database construction, our method achieves success rates of 81.3% (ALFWorld), 76.9% (InterCode), and 58.6% (Wordcraft) on average across 5 training runs. This means 18.7%, 23.1%, and 41.4% of trajectories are discarded respectively. While failed trajectories are not retained for in-context use at test time, failed trajectories are used to improve agent performance via our Exemplar-Curation algorithm (Section 5.3). We do not provide the failed trajectories directly in-context due to the challenges of credit attribution—given a long trajectory with a single incorrect action, it is challenging for the LLM to identify the actions within that trajectory to emulate and the ones to avoid repeating.

Cost Analysis: We provide detailed token usage to address your cost-benefit question. Average tokens per request: 5,047/68 input/output tokens (Wordcraft), 5,385/37 (InterCode), 3,706/30 (ALFWorld), with a maximum episode of 8, 20, and 61 requests respectively. More generally, for any task, we require 2 requests per step (reasoning + acting), plus 1 additional request when using planning (see Appendix D6, L550-556). At GPT-4o-mini pricing (0.15/0.6 USD per 1M tokens), cost per episode ranges from 0.004 USD for InterCode to 0.035 USD for ALFWorld. To collect 1000 episodes, maximum API costs range from 4-35 USD.

Contextualizing the costs of scaling performance along various axes: In Section 6.3, we demonstrate that our approach can yield substantial cost savings to two common alternatives for scaling model performance: (i) switching to a larger LLM, and (ii) test-time scaling via multiple attempts per task (assuming access to a perfect verifier). On ALFWorld, our full configuration of Traj-Bootstrap + DB-Curation + Exemplar-Curation with 5 parallel databases requires 3,500 × 5 training trajectories. Using GPT-4o-mini, the worst-case cost of constructing the databases is 600 USD, after which per-task `test-time' cost of using GPT-4o-mini is only ~0.034 USD. By comparison, using GPT-4o at test time (without collecting training trajectories) costs ~0.57 USD per task, reaching the same cumulative spend as our approach after ~1,100 test-time tasks. The alternative baseline of test-time scaling with 3 attempts per task costs a total of ~0.10 USD per task, which exceeds our method's total cost after ~8,900 test-time tasks. In other words, after a modest up-front investment (of a few hundred dollars of compute) our approach remains consistently more cost-effective than either alternative, while also improving test-time agent performance. Consider a hypothetical production agentic service processing a million ALFWorld tasks a day (a very modest industry-scale production throughput). The cost savings in a single day of using our method, including all offline dataset construction, would be 530,000 USD vs. GPT-4o, or 60,000 USD vs GPT-4o-mini with 3 trials of test time compute.

Basically my question is if the improvement is worth the amount of LLM calls? Table 2 shows a 5% increase from 100->3500 training tasks.

You correctly note that a 12-point increase for the ALFWorld task with Traj-Bootstrap comes from the first 100 training tasks, with a 5-point increase in task performance for Traj-Bootstrap when increasing from 100 to 3500 training tasks. We believe this boost is compelling for two reasons: (1) A 5-point improvement from 0.84 to 0.89 success rate represents a 31% reduction in the agent's error rate (from 16% errors to 11% errors)—a substantial improvement. (2) In an appropriately architected production system, this performance boost could come "for free". When running an agent in production, the system could store new experiences in the database, and our results suggest the agent would continue to improve with database size. This represents a key advantage of our approach: performance scaling that naturally accompanies deployment without additional engineering effort.

Consider also citing some In-Context RL papers such as [1], which also looks at multi-step decision making.

Thank you for the suggestion. Here is an updated related work section we propose to include in our final manuscript:

Our work connects to the emerging area of in-context reinforcement learning, where language models perform sequential decision-making through contextual examples rather than parameter updates. Recent work has explored how transformers can implement RL algorithms in-context: Laskin et al. (2023) demonstrate algorithm distillation for in-context RL, while Lee et al. (2023) investigate transformers' ability to learn from reward trajectory contexts via supervised pretraining. Dai et al. (2024) examine in-context exploration-exploitation strategies, showing that LLMs can balance these competing objectives through prompt design, and Brooks et al. (2023) study in-context policy iteration. While these approaches focus on learning RL algorithms or policies in-context, our work addresses a complementary problem: how to effectively curate and retrieve trajectory examples to maximize in-context learning performance for sequential decision-making tasks.

References:

• Laskin, Michael, et al. "In-context Reinforcement Learning with Algorithm Distillation." ICLR 2023
• Lee, Jonathan, et al. "Supervised pretraining can learn in-context reinforcement learning." NeurIPS 2023
• Dai, Zhenwen, et al. "In-context Exploration-Exploitation for Reinforcement Learning." ICLR 2024
• Brooks, Ethan, et al. "Large language models can implement policy iteration." NeurIPS 2023

Thank you for your detailed review and constructive feedback. We are encouraged you think our method offers "a practical and scalable alternative to manual prompt engineering" with "solid empirical results" and represents "a general, task-agnostic mechanism that could be widely useful in agentic settings."

1 Paper Structure Revision: The placement of Related Work after Problem Statement is unconventional and makes the reading flow less logical. Consider reorganizing the sections to follow the standard order: Introduction → Related Work → Method → Experiments.

We respectfully note that Problem Statement sections before Related Work are commonly used in machine learning papers, particularly when the technical problem formulation helps contextualize subsequent related work discussions. In this paper we made the deliberate choice to help readers understand the specific setup before contextualizing our proposed solution with respect to prior work. However, we appreciate your feedback on narrative flow and will ensure the presentation is as clear as possible in our revision.

2 Generalization to New Tasks: How does the system handle domain shifts or novel goals that were not part of the training task distribution? The reliance on accumulated in-context trajectories might hurt generalization.

Your question about handling domain shifts and novel goals is insightful. To address generalizability concerns, we conducted additional experiments using Mixtral 8x7B Instruct v0.1, a popular open-source model with different architecture and capabilities than GPT-4o-mini. Using databases previously collected with GPT-4o-mini, we compared performance when Mixtral 8x7B uses our Fixed-DB baseline versus our best method (Traj-Bootstrap + DB-Curation + Exemplar-Curation).

Results averaged across 5 trials demonstrate strong cross-model generalization: ALFWorld shows a 28-point improvement (0.55 vs 0.27), IC-SQL achieves an 18-point gain (0.70 vs 0.52), and Wordcraft exhibits a 12-point boost (0.52 vs 0.40). These improvements match or exceed the gains we observed with GPT-4o-mini (20, 7, and 14 points respectively), suggesting our approach captures fundamental task structure rather than model-specific artifacts. This cross-model transfer demonstrates robustness to significant distribution gaps between collection and deployment models.

Although our experimental testbeds do not feature domain shift, handling situations involving domain shift is a strength of our approach by design. Unlike approaches that use a fixed set of in-context examples or approaches that require model fine-tuning (typically a high-cost, high-latency operation), our system allows for continual learning via accumulating examples in the database during deployment, naturally expanding coverage to new domains or task variations encountered in practice. This "learning while doing" capability means initial domain gaps can be progressively closed, potentially in seconds, by accessing recently collected experience.

3 Training/Test Gap Concerns: While the paper aims to reduce hand-crafted engineering, the method still depends on hand-curated starting examples and extensive self-training—how is the potential gap between training and deployment (e.g., in online settings) mitigated?

You raise an important point about the training-deployment gap. The cross-model experiments above address this concern, as GPT-4o-mini (collection) and Mixtral 8x7B (evaluation) represent a substantial train-test distribution gap in terms of model architecture and capabilities. The strong performance transfer provides evidence that our curated databases generalize effectively across different deployment contexts.

Additionally, while a human-provided starting database is helpful for jump starting performance, it is not strictly necessary—as shown in Appendix G, Figure 7, our method can actually bootstrap from an empty starting database, albeit with less data efficiency. This reduces dependence on hand-crafted engineering compared to traditional approaches.

The key insight is that our system becomes more robust over time. As it encounters new scenarios during deployment, it automatically expands its database with successful solutions, making it increasingly suitable for diverse real-world applications.

The overall conceptual framework builds heavily on existing ideas (ReAct, retrieval-based LLMs, in-context learning), and the innovation is mainly in implementation rather than theory or modeling.

We agree completely that our approach builds on existing agentic designs (ReAct, retrieval, in-context learning). We emphasize that our contribution lies in demonstrating that simple, well-designed exemplar curation and retrieval can outperform approaches requiring hand-crafted task-specific observation/action spaces and hierarchical learning components, while being significantly easier to implement and scale. Our core finding—that scaling the number of trajectories available to retrieve in-context and applying thoughtful data curation achieves performance superior to state-of-the-art methods that utilize complex hierarchical learning and extensive manual prompt engineering—represents a valuable insight for the field, offering a practical data-driven path to scaling in-context LLM agent performance without architectural complexity.