Self-Generated In-Context Examples Improve LLM Agents for Sequential Decision-Making Tasks
Authors: Vishnu Sarukkai
Zhiqiang Xie
Kayvon Fatahalian
Venue: NeurIPS 2025 poster ()
Keywords: language models
agents
self-improvement
in-context learning
sequential decision-making
Primary area: deep_learning

Abstract: Improving Large Language Model (LLM) agents for sequential decision-making tasks typically requires extensive task-specific knowledge engineering—custom prompts, curated examples, and specialized observation/action spaces. We investigate a different approach where agents automatically improve by learning from their own successful experiences without human intervention. Our method constructs and refines a database of self-generated trajectories that serve as in-context examples for future tasks. Even naive accumulation of successful trajectories yields substantial performance gains across three diverse benchmarks: ALFWorld (73\% to 89\%), Wordcraft (55\% to 64\%), and InterCode-SQL (75\% to 79\%). These improvements exceed those achieved by upgrading from gpt-4o-mini to gpt-4o and match the performance of allowing multiple attempts per task. We further enhance this approach with two innovations: database-level curation using population-based training to propagate high-performing example collections, and exemplar-level curation that selectively retains trajectories based on their empirical utility as in-context examples. With these enhancements, our method achieves 93\% success on ALFWorld—surpassing approaches that use more powerful LLMs and hand-crafted components. Our trajectory bootstrapping technique demonstrates that agents can autonomously improve through experience, offering a scalable alternative to labor-intensive knowledge engineering.

Self-Generated In-Context Examples Improve LLM A gents for Sequential Decision-Making Tasks
Vishnu Sarukkai Stanford University
Zhiqiang Xie
Kayvon Fatahalian Stanford University
Stanford University
Abstract
Improving Large Language Model (LLM) agents for sequential decision-making tasks typically requires extensive task-specifi knowledge engineering custom prompts, curated examples, and specialized observation/action spaces. We inves- tigate a different approach where agents automatically improve by learning from their own successful experiences without human intervention. Our method con- structs and refines database of self-generated trajectories that serve as in-context examples for future tasks. Even naive accumulation of successful trajectories yields substantial performance gains across three diverse benchmarks: ALFWorld (73% to 89%), Wordcraft (55% to 64%), and InterCode-SQU (75% to 79%). These improvements exceed those achieved by upgrading from gpt-4o-mini to gpt-4o and match the performance allowing multiple attempts per task. We further enhance this approach with two innovations: database-level curation using population-basee training to propagate high perfooref example collections, and exemplar- curation that selectively retains trajectories based their empirical utility in-context examples. With these enhancements, our method achieves 93% suc- ALFWorld-surpasiin
approaches that more powerful I.LMs and hand-crafted components. Our trajectory bootstrapping technique demonstrates that agents can autonomously improve through experience, offering scalable alternative to labor-intensive knowledge engineering.
Introduction
When creating LLM agents for sequential decision-making tasks, practitioners often improve agent performance by investing in task-specific knowledge engineering (through tedious prompt tuning ([], human-crafted in-context examples 2 3 or custom observation and action spaces 4 5). Using
these techniques, scaling agent performance comes from scaling human effort.
In this paper, we investigate an alternative path: enabling LLM agents to autonomously bootstrap their own performance by leveraging their successful experiences via in-context learning. The efficacy in-context learning depends critically on both the quality of the examples 2 and their relevance the current decision point [6-8) This insight provides natural direction for automated agent seff-improvement accumulating successful self-generated trajectories and estimating the most relevant and effective prior experiences to
in-context examples for each action.
Our work assumes a ReAct-style agent 9 that retrieves different examples for each decision point based their relevance to the current situation [1. [T. We build on this foundation by focusing specifically on how to construct and refine the underlying database self self-generated examples. How identify which trajectories enhance performance performance? This database construction problem requires addressing both the collection of high- quality trajectories and the strategic curation of the most valuable ones for future retrieval at each decision point in the agent's 's reasoning and acting loop.
new tasks versus those that hinder
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Algorithm ReAct-style Agent Loop
1: function AGENT(Y, D2
2: Cp < Retrieve (D, keys [g])
> Retrieve for plan
3:
<- LLMplan (g. Cp)
Generate initial plan
4: Initialize r (g.P, 0- -): E.obs() ()
5:
Ci + Retrieve DD keys = 1g,p, 01))
>> Retrieve for current observation
6:
for f = 1 Io do
7:
T f LLM (T, 02, Ct)
D Generate reasoning
8:
C.+1 t Retrieve (D, keys = (t.),
> Retrieve for current reasoning
9:
0, f (TM oz, r,, C(+1)
> Decide action
10:
0t+1, done, (.step(a))
Execute action in environment
11:
<- T (or, 0t)
12:
if done then
13:
return (0.P. {(0;, rú; return (g.p, TT, 9,),,,
14:
Failed due timeout
We demonstrate that even naive database accumulation improves test-set performance from 73% to 89% on ALFWorld, 55% to 64% on Worderaft, and 75% to 79% on InterCode-SQLI (Equivalent to what baseline agent would achieve if it were allowed two to three attempts per task.) We further propose two database construction enhancements: (1) database-level curation that identifies and propagates high-perfore performiffoo example databases, and (2) exemplar-level curation that identifies helpful trajectories based on their empirical utility as in-context examples. These approaches do not require task-specife prompt engineering [22 or custom observation/actioon space design []] but improve success rates on ALFWorld to 93%- Sor--supsssinn approaches like AutoManual 4 that more powerful LLMs and hand-crafted observation and action spaces, well hierarchical approaches like Autoguide [12]. The success rate improvement on AL.FWorld exceeds the boost obtained from upgrading the agent's underlying LLM from gpt-4o-mini gpt-4o. Our results highlight the practical value of trajectory bootstrapping as dimension for scaling test-time compute.
2 Preliminaries
Sequential Decision-Making Tasks We focus on multi-step sequential decision-making tasks where agents must produce series of actions based observations of the environment. The sequential nature of these tasks introduces unique challenges for LLM agents, as they must interpret intermediate environmental feedback, maintain coherent reasoning across steps, and adapt their strategy based on the evolving task state.
We assume standard POMDP setup (App. B where agent, given task goal interacts with the environment & for up T timesteps. At each timestep f, the agent receives an observation or- takes an action at, and & transitions to the next state. We consider sparse-reward environments where success only determined at the end of an episode. This is standard setting in prior agentic Please see App. for details.
work 99 13 12
ReAct-style Agent Loop Our work assumes a ReAct-style + agent architecture that employs recent best practices for in-context retrieval [TO] [1]. The agent operates through three-phase
approach (planning, reasoning, and acting) as formalized in Alg. I Two key components differentiate our implementation from basic ReAct: (1) initial planning step where the agent generates high-level plan before execution begins [ line 3), which has been shown to boost performance in
prior work [00
44 13 4. and (2) dynamic retrieval of different trajectory segments for each decision
point
11, rather than using the same examples throughout an episode 9 13, 12).
The agent operates through three key LLM--ased functions: LLMplan generates a high-level plan p for the goal, LLMeeason processes observations o, to produce reasoning rt. and LLM,er determines actions or- The Retrieve() function selects the & most relevant examples from database 'D based on similarity between lookup keys and examples. Our contribution focuses specifically on constructing and refining the trajectory database that powers this retrieval mechanism, without relying task-specific

---

prompting, observation spaces [ or action spaces [S] 4. Note that in Alg. [ all task-specific knowledge is encapsulated in D. For simplicity, we eschew other techniques, like hierarchical that are also task-agnostic, but add additional agent complexity.
learning 13 12
3 Problem Statement
Given the ReAct-style agent described in Sec. 2 our goal is to construct trajectory database that maximizes agent performance on sequential decision-making tasks. We focus on building and refining the example database accessed by the agent's retrieval mechanism. Formally, we aim to construct a trajectory database D where each trajectory т E DD captures a complete task attempt: т (g. P: {(o,, Fr, at) at)),,, We aim maximize agent performance across tasks T: DD' arg maxp (Success Agent (g. D, E, E))]. where Success() returns the binary outcome We assume that we are given: (1) D initialized with a small number of human- uuman-generated trajectories, (2) a descriptor of the action space, and (3) access to set of training tasks drawn from T that the agent can attempt. All three assumptions are typical for ReAct-based agents 10
12
4 Related Work
In-context learning for agent improvement Despite the current popularity of reinforcement learning-based approaches for improving agent capabilities 11 in-context learning offers distinct scientific and practical advantages. These benefits include model-agnostic portability across different LLMs, efficiency in law-sa regimes B 19 and accessibility when implementation
barriers exist for weight modification methods. Both empirical and theoretical work has established that in-context performance can scale effectively with additional examples 6
7 19 g suggesting that strategic example accumulation should lead to significant performance improvements. We focus on maximizing the value of limited examples through in-context methods, while hypothesizing that database quality, not just quantity, critically influences performance scaling. For completeness, we offer a preliminary investigation in App. of how our collected trajectories could potentially serve as training data for fine-tuning approaches.
Automatic in-context examples Recent work has demonstrated the effectiveness of optimizing both instructional content and example curation in prompts. DSPy (20) introduced framework for optimizing multi-step pipelines through instruction tuning and strategic example curation. Self- generated examples containing reasoning traces can eliminate the need for numan-written examples, and these self- eef-rgenerated examples often contribute more to performance than optimized instructions alone [21] These approaches typically select fixed exemplars for all task instances, whereas our method enables the dynamic selection of different in-context examples for each decision.
In-context self-improvement of LLM Agents Self-improvement methods for LLM agents either aim solve one task (performing scarch/optimizzaioon) or transfer knowledge from prior tasks to novel ones (generalization) (see App. J.2 for further discussion). Approaches to solve single task scale the number of sampled solutions at inference time 24 incorporate feedback from failed attempts 225 Knowledge transfer approaches include abstraction- -based methods like Expel. [13 and AutoGuide 12), while others employ task-specific information in their design- -RAP [0] uses task-specific prompts and AutoManual
[ constructs task-specific state and action spaces (see
App.J.I) Other dimensions of self-improvement include hierarchical execution (26) and optimization techniques for multi-stage systems 27|29 -echniques complementary to our approach. Rather than developing complex architectures or leveraging task-specific information, we focus on identifying which trajectories most contribute to successful outcomes in-context examples.
In-context reinforcement learning Our work connects the emerging area of in-context rein- forcement learning, where language models perform sequential decision makiing through contextual examples rather than parameter updates. Recent work has explored how transformers can implement RL algorithms in-context, both via algorithm distillation for in-context RL [30], and via transformers' ability to learn from reward trajectory contexts via supervised pretraining
LLMs can balance
exploration-explotaaioo tradeoff' through intelligent prompt design [32 and other work suggests I. being able to perform in-context policy iteration (33) While these approaches focus on learning RL algorithms or policies in in-context, work addresses complementary problem: how to
3

---

Algorithm 2 Database Curation Logic for +DB-Curation
1: procedure OPTIMIZEDATABASES((()) D.,..., Dr). interval)
2: Initialize performance metrics {mi1 m22 my for each database
3: for / 1,2,... ..., Ttroin do for i = 1,2, ..., .N in parallel do Execute task t using database D) successful, add trajectory to D;
4:
5:
6:
7:
Update rolling performance metric m, recent tasks
8:
if 10 x 2 for any E N then Sort databases by rolling performance on recent tasks Replace worst database with copies of best
9:
effectively curate and retrieve trajectory examples to maximize in-context learning performance for sequential decision-making tasks.
Methods
We now discuss three algorithms for constructing database D using continual collection approach.
5.1 Traj-Bootstrap: Constructing a Database of Previously-Solved Tasks
Our mejjectory-bootstrapppee algorithm Traj-Bootstrap constructs trajectory database D by collecting successful agent experiences. As outlined in Sec. 3] we start with a minimal set of human human-provided exemplars (which could be empty), then grow the database as the agent successfully completes training tasks. This process creates positive feedback loop where successful examples help the agent solve new tasks, generating more successful examples.
Traj-Bon Bojjs-Bottt operates on principles similar to weighted regression in reinforcement learn- ing (34, where only successful trajectories (s mechanism ensures the agent learns from positive examples while avoiding potentially misleading be leveraged by asking the agent to imitate the successful patterns in these trajectories. Failed trajectories are more challenging to operationalize due to the credit attribution problem: it necessary to identify the 'good' vs 'bad' parts of the trajectory so the the agent can imitate the good parts and avoid the mistakes made in the bad parts, Failed trajectories do offer the opportunity to guide exploration 25
are stored in the database. This filtering
failed attempts. Successful trajectories
we leave this direction to future work.
5.2 + -DB-Curation: Database-Leved Data Curation
Traj-Bootstrap exhibits unpredictable performance variation across training (database construction) trials, even when fol- lowing identical collection procedures. Fig. iillustrates this variation across five trials on the InterCode-SOU benchmark (a benchmark we use for evaluation in Sec. 6 The variance
InterCode-SQL
Success Rate
arises from two factors: (I) the stochasticity of LLM outputs
0.76
creating different initial trajectories, and (2) an amplification effect where early differences in collected examples lead to wide performance variation.
0.74
0.72
0
200
400 600 800
This observation motivates data curation strategy inspired by population-basse training reinforcement learning [35] Fig. [ shows that some databases lead to better task per- formance than others-ss so we identify the underperforming databases periodically during training and remove them, con- tinuing growth from top-performing ones. We introduce +DB- Curation, a population-basee based training algorithm (Alg- 2 to identify and propagate the most effective databases during the bootstrapping process.
Num. Training Tasks
Figure 1: Traj-Bootstrap exhibits variance test-time success rate. Dashed lines plot success rates achieved five independent trials.

---

Algorithm 3 Database Construction from Top Exemplars for +Exemplaa-CCraatoon
1: procedure SELECCTEXEMLLAASS(D) D2...., DN Trrain)
2: Deamposite f-
3: Compute quality metric (()) for each trajectory T E U D; for each task t Train do
4:
5:
Tr 4- (successful trajectories for task across all databases) if T, is not empty then
6:
7:
Select top-1 trajectory from T, by quality metric Q
8:
Add selected trajectory to composite
9:
return D composite.
+DB-Curatee CBB-Curation maintains N database instances initialized with identical Numan-providee exemplars. Each instance is used by a separate agent that accumulates successful trajectories independently. Curation events occur when the number of tasks attempted reaches size thresholds (starting size 10 and doubling thereafter). At each threshold, the agent's 's success rate all training tasks since the last threshold, and replaces the worst-performing database with copy of the top-pet hop-peffrmmig database.
evaluates database performance based on
The key insight of this approach is that database quality emerges from collective properties-like coverage, diversity, and complementarity across examples-not just individual trajectory quality. Moreover, single trajectory collected early in training can influence many future trajectories by guiding the agent toward particular solution strategics, creating cascading database-level effects. By selecting and propagating entire databases, we preserve these beneficial emergent properties while using a simple, computationally efficient evaluation metric based on recent performance.
5.3 + +Exemplar-Curationn Exemplar-Level Data Curation
While database- curation via -DB-Curation identifies entire sets of complementary trajectories, discarding whole databases can eliminate valuable trajectories. We find that even poor-pertiee poo-rrerfonnng databases contain individual high-quality trajectories that yield better outcomes when used exam- ples. Conversely, some successful trajectories may contain bad individual decisions that would be unhelpful to repeat. This observation motivates +Exemplar- Cuuiaaaionn identifying and selecting indi- vidual high-quality exemplars across multiple database instances based on their empirical utility as in-context examples. This approach parallels value-function learning reinforcement learning (36). where we estimate the 'value' of each trajectory based on its contribution to successful outcomes.
We introduce eetrieval-weigheee quality metric analogous to value function to quantify each trajectory's 's contribution to successful outcomes:
Q(T) = ΣIERG 9- Si(T)
EiER(Y Si(T)
where R(T) is the set of tasks for which trajectory 7 was retrieved, o; the binary outcome of task i, and f((T) is the retrieval frequency during task
This value metric measures how often a trajectory is associated with successful outcomes when retrieved as an in-context example. It weights outcomes by retrieval frequency, prioritizing trajectories frequently retrieved during successful completions while penalizing those associated with failures.
Curaaionr-Curationn For each task in the training set, identifies all successful Alg. 3 outlines +Exemplar Curation. trajectories across all N database instances and selects the exemplar with the highest value according to the metric. This approach constructs composite database containing only the most effective exemplars as measured by their empirical contribution to successful outcomes on subsequent tasks.
5.4 Train-Time vs Test-Tiime Time LLM Costs
The curation methods (+DB-Curation and +Fxemplar- (uuutaao- maintain N parallel database in- stances during training, and therefore require N more LLM inference during training compared
5

---

to Traj-Bootstin However, all methods use the same quantity and distribution of training tasks. At test time, all three methods have identical computational costs-Alg. is simply provided with different database 'D for each method. This contrasts with approaches that scale the number of LLM calls per test-time task improve performance [5]. Our methods shift computational burden to training while maintaining efficient inference, property our in-context methods share with fine-tuning methods.
Experiments
We evaluate our database construction methods through experiments addressing three key questions:
Database scaling: How does task success rate scale with increasing database size?
Improving database construction: How much population- training and exemplar- level curation improve task success rate?
Overall effectiveness: How do our approaches compare to alternative approaches leveraging taec-spec domain knowledge or hierarchical algorithms?
6.1
Experimental Setup
6.1.1 Benchmark Tasks
We evaluate our methods on three benchmarks: ALFWorld 37 a text-hased environment for navigation and object manipulation; InterCode-SOL [38] interactive coding environment for SQL query generation; and Wordcraft [39] a simplified adaptation of Little Alchemy requiring compositional reasoning combine elements. These benchmarks were selected because they: (1) provide large enough task pools to support meaningful train/test splits, (2) represent diverse reasoning challenges relevant sequential decision-making and (3) have been used in prior work, enabling direct comparisons with existing methods.
6.1.2 Methods Compared
Our methods include:
The baseline agent as described in Sec. with a fixed database human- provided initial examples and no database growth.
Fixed-DB:
Traj- :ootsroots The simple progressive accumulation approach from Sec. 5.1
-aag--Boottra---DBuuratto Our database-level trajectory curation from Alg.
Bootstraa-+EEeeppla--ee Curattin:: Our exemplar-level trajectory curation from Alg.
Bagl-Booottrap--BBEemmee Careemmmpaa--rrttionnn curation and propagation and our exemplar-level trajectory curation.
Curation: Applying both our database-level trajectory
We compare these methods to two hierarchical designs. Autoguide [12] converts successful tra- jectories into explicit rules and retrieves the most contextually relevant rules, alongside low-level trajectories, at inference time. AutoManual [4] leverages hand-crafted task-specific observation and action spaces-see App. for details. Unless otherwise specified, we use GPT-4o-min as our base LLM. We report success rates averaged over five random seeds. See App. E for additional details.
6.2 Traj-Bootstrap Results
Traj-Bon Fraj-Bootstrap performance improves with more training tasks Tab. presents the final success rate metrics for our database construction methods. The performance of Traj-Bootstrap generally improves with increases in the number of training tasks attempted (Fig 2 Performance continues to improve with more training tasks across all benchmarks, but exhibits diminishing returns most gains occur within the first 25% of added training tasks. This efficiency decline occurs because each new example is retrieved less frequently as the database grows, influencing fewer generations, a pattern consistent with findings from Bertsch et al. [19] and Agarwal et al. [ As mentioned in Sec. 5) we observe performance variability across trials and within individual trials. Cross-trial variance indicates that some trials produce higher-performing databases when solving identical tasks. Within-trial fluctuations show that certain added trajectories degrade performance.

---

Method
ALFWorld
InterCode-SQL
Worderaft
Fixed-DB
0.73+-0.02
0.75++0.01
0.55++0.03
Traj-Bootstrap
0.89=00001
0.79+0.01
0.64+0.03
+DB-Curation
0.91=00011
0.78+10.01
0.64+0.001
+ Exemplar-Curation
0.90=10.02
0.81
0.72+10.02
-+-Exeemllar-Curatton
0.93:10.03
0.82:10.01
0.69:10.01
Table 1: Average success rate of our methods: self-collected trajectories provide the largest
boosts in task success rate. rraj-Bootstrap outperforms Fixed-DB across all three benchmarks. The combination of 3DB-Curation and +Exemplar- Curlttion provides the best performance on both ALFWorld and InterCode-SQL. +Exemplar- Curation provides the best performance on Wordcraft.
Ceemmpaa-Cuuationn
Method
LIM((s)
Num Training Tasks
ALFWorld
gpt-3.5-turbo
Autoguide
12
100
0.79*
+ +gpt-4-turbo
gpt-4o-mini
36
0.72=0.01
Automanual
gpt-4-turbo
0.91=0.01
+gpt-4o-mini
gpt-4o-mini
0
0.73=0.05
Fixed-DB
gpt-4o
0.88=0.02
gpt-4o-mini
100
0.84=0.04
Traj-Boun Proj-Bootstrap
gpt-40-mini
3500
0.89=0.01
gpt-4o-mini
100
1.06-0002
+DB-Curation
gpt-4o-mini
3500
0.01
gpt-4o-mini
100
0.86=0.03
Hxemplaa-Curaatee
gpt-4o-mini
3500
0.90=0.02
+DB-Curatiee
gpt-4o-mini
100
0.81=0.02
+Exemplar Curation Cucaalaa-CCuation
gpt-4o-mini
3500
0.93=0.03
Table 2: Comparison of agent success rates on World: contextualizing the performance
of Troj--oostrap. The 15-point boost in average success rate from database construction via Traj-Bootstre is similar to that achieved from upgrading Fixed-DB from gpt-4o-mini to gpt-4o. The performance of Hiti-Booostta--DB-Eemme EExxemplar-Curation exceeds Automanual [4], even though Automanual utilizes hand-designed observation and action spaces and a better LLM (gpt-4-turo++gpt 4o-mini). indicates results reported from original papers.
+DB-Curation boosts performance on ALFWorld Fig. illustrates how +DB-Curation can improve upon Sraj-Bootstrrpp ss performance, despite exhibiting occasional performance dips at smaller database sizes. These dips result from inaccurate estimates (due to low sample count) of database quality early in the process- inteess-ittoouccigg noise into the curation process.
+Exemplar-Curatiee boosts performance on InterCode-SQL, and Worderaft As seen in Tab. +Exemplar- Currtaion yields improvements in final task success rates InterCode-SQLI and Wordcraft. and also boosts success rate at intermediate database sizes for both InterCode-SQL and Wordcraft ()ig To further highlight the impact of our exemplar- databases built from the 'best' trajectories that are the most empirically effective in-context examples versus the least effective trajectories, as determined by Equation i Sec. 5.3 The 'best' curve is identical to + #Exempla-CCurationn while the 'worst' curve selects the bottom-1 trajectory instead of top-1 1 in Alg. [] line 7. Using the database of high-quality examples yields higher success rate across all database sizes for ALFWorld and Wordcraft, and for smaller database sizes for InterCode-SQL.
curation metric, Fig. 4 compares
+DB+ Eeee--ex-pll--raateee achieves best performance on Forl and InterCode-SQI. Fig. and Tab. highlight that combined +DB+Exemplar-Curatt achieves the best final task success rates on both ALFForld and InterCode-SQL (0.93 and 0.82 respectively). Note that Wordcraft. DDB-Curation fails to
and +Exemplar- Currtion can be complementary, as the

---

ALFWorld
InterCode-SQL
Wordcraft
0.70
Success Rate
0.90
Success Rate
0.78
0.65
0.80
0.76
0.60
0.74
0.55
0.70
0.50
0.72
0 1000 2000 3000
0
200 400 600 800
0 1000 2000 3000
Num. Training Tasks
Num. Training Tasks
Num. Training Tasks
Avg of 5 trials
results: success rate improves with increasing training tasks on all three benchmarks. Individual trials (5) shown dashed lines. All benchmarks exhibit diminishing returns as the database size increases. Trials show substantial performance variability, both within individual trials and across different trials.
Figure 2:
ALFWorld
InterCode SQL
Wordcraft
0.82
Success Rate
0.70
0.90
0.80
Success
0.85
0.65
0.78
0.80
0.76
0.60
0.75
0.74
0.55
0
1000 2000 3000
0
200
400
600 800
1000 2000 3000 4000 Num. Training Tasks
Num. Training Tasks
Num. Training Tasks
Traj-Bootstrap
+DB-Curation
+Exemplar-Curation
+DB+ExemplarCuraaton
Figure 3: Success rate comparison for Traj-Bootstrap and its variants (+DB-Curation, TExemplar-Curationn JDB-Exemplar-Crrttin
+DB-Curation enhances final success rate only ALFWorld, but improves success rate for smaller DB sizes all benchmarks. +Exemplar- Curation delivers success rate gains on both Intercode-SQL. and Worderaft. The combination of both enhancements delivers the largest gains both ALFWorld and InterCode-SQI.
provide boosts whether not +Exemplar- Cuxeatplr-Cuuaation Curation is used-Trai Tai---r-tt-BtBarappp and JDB-Curation perform identically (0.64), and +Exemplar- Curation(O.71) outperforms +DB+Exemplar Curation (0.67).
Currattii
6.3 Contextualizing performance boosts from Traj-Bootstrap
To contextualize the improvements achieved by Traj- Traj-Bootsttrp, we compare with several alternative strategies: test-time sampling, using better LLM, task-specific strategies, and hierarchical strategies.
Comparison with test-time scaling Our trajectory bootstrapping approaches achieve success rate improvements equivalent scaling test-time compute by making multiple task attempts advantage in scenarios where multiple attempts are impractical or when success verification is unavailable test time. Furthermore, our approaches provide these benefits without requiring any modifications to the test-time inference process. To demonstrate the magnitude of this benefit, we compare our methods to the alternative strategy of making multiple attempts each test task with the Fixed-DB DBB baseline and selecting the best outcome [22 24). Tab, 3 reports the pass k metrics for Fixed-DB across all three benchmarks, representing the probability of at least one successful attempt when making l independent attempts at each task. Using only a single attempt per task, Traj- Bootstrap approach achieves success rate comparable to Fixed-DB pass 2 or pass@3 on all three benchmarks.
and/or +Exemplar- Cuuratinn perform nearly on the level of Fixed-DB pass @4 on ALFWorld, pass on MherCode-SQL. and pass@: @5 for Wordcraft.
Comparsion with model upgrades On ALFWorld, after 3500 training tasks Traj- Traj-Boot yields a 20-point success rate boost over Fixed-DB, significantly outperforming the 15-point improvement gained by upgrading Fixed-DB more powerful L.M.
Comparison with task-specific strategies Tab. shows that Dea-Booottrap--B-EEenee Curation using GPT-4o-mini achieves success rate exceeds (0.93) that exceeds that of Automan- ual 4 configured to use combination of GPT-4-turbo and GPT-4o-mini (0.91). Thus, methods

---

ALFWorld
InterCode-S00
Wordcraft
Success Rate
0.90
Success Rate
0.80
Success Rate
0.70
0.85
0.78
0.65
0.80
0.76
0.60
0.75
0.74
0
1000 2000 3000
200
400
600 800
1000 2000 3000 4000 Num. Training Tasks
Num. Training Tasks
Num. Training Tasks
Best
Worst
Figure 4: The 'best' bootstrapped trajectories compared to the "worst'. Databases constructed from the highest-quality successful trajectory per task, as measured by Eq. [ outperform databases built from the lowest-quality successful trajectories on both ALFWorld and Worderaft. The "best' curve is identical to +Exemplar- Curation,,, while the 'worst' curve selects the bottom-1 trajectory
instead of top- in Alg. 3 line 7.
Method
ALFWorld
Intercode-SQL.
Wordcraft
Traj-Bootstrap
0.89-10.01
0.79:10.01
0.64-00.3
+DB+Exemplar-Cunaae
0.93:10.03
0.82:10.01
0.69:10.01
Fixed-DBGl
0.73+00.33
0.75+10.01
0.55+0.03
Fixed-DB @
0.87+00.02
0.78++0.03
0.62++0.02
Fixed-DB @
0.92+-0.02
0.80+-0.03
0.64+00.22
Fixed-DBB @4
0.94+-0.0
0.81+0002
0.66+00.2
Fixed-DB@5
0.9610002
0.82+0.03
0.72
Table 3: Pass @ of Fixed-DB on all benchmarks. On all benchmarks, using only single test-time attempt per task, Traj Botts-Bpttt achieves success rates between that Fixed-DB at pass@2 and at pass mass@3. +DB+Exemplar Curration achieves success rates between p and @5
outperform approach that uses more powerful LLM and customized observation and action spaces. See App. K for comparison to hand-crafted approaches on InterCode-SQL.
Comparison with hierarchical algorithms Given 100 training tasks, Autoguide, hierarchical rule-learning approach, achieves 0.79 success rate (using a combination of gpt-3.5-turbo + gpt-4- turbo). Given the same number of training tasks our best approach achieves significantly greater success rate (0.86) with gpt-4o-mini (Tab. While this comparison employs different algorithms and L.LMs, the performance of Traj- Traj-Boot suggests that self-constructed databases low-level trajectories can be competitive with hierarchical approaches.
6.4 Extending Traj-Bootstrap
Can we predict agent success? Beyond improving agent performance, we can also utilize our self-collected examples implement useful agent diagnostics, such as predicting agent's success on novel tasks. On InterCode-SQU and Wordcraft, we train a calibrated Random Forest classifier of agent success based on task goal and initial observation embeddings. Classifier quality (measured via AUROC) improves with database size, reaching 0.77 for InterCode-SQL and 0.71 for Wordcraft with our largest databases. The predicted probabilities also closely match empirical success rates, indicating well-calibrated predictions. See App. H for details.
self-collected databases for fine-tuning? We fine-tune GPT-4o-mini using trajectories from our best cessf-perfoming Traj- Bow.Bootttt----eeeppppe Euraeemea---rraatiion database for each benchmark. The resulting fine-tuned agents (ReAcctFiiettne) outperform our in-context approach on ALFWorld (23-point vs. 20-point boost) and Wordcraft (19-point vs. 14-point), but perform worse on InterCode- (4-point vs. 7-point). This suggests our self-collected examples are effective not only for in-context learning but also for creating fine-tuned agents. See App. F for details.
Can
Does our approach generalize across models? To test whether our method captures fundamental task structure rather than model-specific artifacts, evaluate Mixtral 8x7B Instruct v0.1 using

---

databases collected with GPT-4o-mini. Despite this challenging cross moss- transfer scenario. our full method achieves substantial improvements: +28 points on ALFWorld (0.55 vs. 0.27), +18 points on IC-SQL (0.70 vs. 0.52), and +12 points on Wordcraft (0.52 vs. 0.40). These gains match or exceed those observed with -Pii--ommini itself, demonstrating that curated databases can effectively transfer across different model architectures and families. See App. G details.
7 Discussion
Contextualizing the costs of scaling performance along various axes Our self iep-iimprveeenttt algorithm offers substantial cost savings compared two common approaches for scaling model performance: (i) switching to a larger LLM, and (ii) test-time scaling via multiple attempts per task (assuming access perfect verifier).
Our full configuration with 5 parallel databases requires 3,500 x training trajectories on GPT-4o- mini, with worst-case database construction cost of $600. After this one-time investment, the per- task inference cost is only S0.034 (sce Appendix Diror for detailed token usage and cost calculations). As shown in Section 6.3 this approach achieves a 0.93 task success rate ALFWorld outperforming GPT-4o with Fixed-DB (0.88) and matching GPT--4-mini with Fixed-DB and attempts per task (0.92).
In comparison, using GPT-4o inference time costs $0.57 per task, breaking even with our approach after only 1,100 tasks. Test-time scaling with 3 attempts costs $0.10 per task, breaking even after 8,750 tasks. Beyond these thresholds, our method remains consistently more cost-effective while delivering superior performance.
At production scale, these savings become substantial. Consider service processing one million ALFWorld tasks daily-a modest industry-scall throughput. Our method would save $530,000 daily versus GPT-4o, or $60,000 daily versus GPT-4o-mini with test-time compute, even accounting for all offline construction costs.
Failed trajectories used to improve the system During the initial database construction step, our method achieves train-set success rates of 81.3% (ALFWorld), 76.9% (InterCode). and 58.6% (Worderaft) on average across 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 (.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, is challenging for the LLM to identify the actions within that trajectory to emulate and the ones avoid repeating.
Future directions The success of our approach reveals performance gains that stem primarily from accumulating successful examples, establishing foundation for agent self-improvement where the quantity and quality of accessible data rivals the importance of architectural complexity. This parallels trends in traditional deep learning, where data curation often yields substantial improvements. Our findings point to promising research directions that approach LLM agent enhancement from a data-centric perspective- -avree--ddniingggg both strategic data collection methods (balancing exploration versus exploitation across diverse tasks) and refined filtering techniques to maximize performance.
Acknowledgments Thank you to Brennan Shacklett, Purvi Goel, Zander Majercik. William Wang, Bradley Brown, Jon Falcon, and William Mark for valuable discussions and feedback. This work was supported by the Stanford HAI SEAMS program, Roblox, and Meta, and API credits were provided by OpenAl and together.ai.
10

---

References
[1] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Shain-of-though prompting elicits reasoning in large language models. Advances neural information processing systems, 35:24824 24837, 2022.
[2] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[3] Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, et al. Larger language models do in-context learning differently. arXiv preprint arXiv:2303.03844 2023.
[4] Minghao Chen, Yihang Li, Yanting Yang. Shiyu Yu, Binbin Lin, and Xiaofei He. Automanual: Generating instruction manuals by IIm agents via interactive environmental learning. arXiv preprint arXiv:2405./62477 2024.
[5] Ke Yang, Yao Liu, Sapana Chaudhary, Rasool Fakoor, Pratik Chaudhari, George Karypis, and Huzefa Rangwala. Agentoccam: A simple yet strong baseline for Ilm-based web agents. arXiv preprint arXiv:2410. 13825, 2024.
[6] Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211. 15661, 2022.
[7] Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. International Conference on Machine Learning, pages 35151-35174. PMLR, 2023.
[8] Rishabh Agarwal, Avi Singh, Lei Zhang, Bernd Bohnet, Luis Rosias, Stephanie Chan, Biao Zhang, Ankesh Anand, Zaheer Abbas, Azade Nova, et al. Many-shot in-context learning. Advances in Neural Information Processing Systems, 37:76930-76966, 2024.
[9] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023.
[10] Tomoyuki Kagaya, Thong Jing Yuan, Yuxuan Lou, Jayashree Karlekar, Sugiri Pranata, Akira Kinose, Koki Oguri, Felix Wick, and Yang You. Rap: Retrieval- planning with contextual memory for multimodal Ilm agents. arXiv preprint arXiv:2402.03610, 2024.
[11] Ruiwen Zhou, Yingxuan Yang, Muning Wen, Ying Wen, Wenhao Wang, Chunling Xi, Guoqiang Xu, Yong Yu, and Weinan Zhang. Trad: Enhancing IIm agents with step-wise thought retrieval and aligned decision. In Proceedings of the 47th International ACM SIGIR Conference Research and Development in Information Retrieval, pages 3-13, 2024.
[12] Yao Fu, Dong-Ki Ki Kim, Jaekyeom Kim, Sungryull Sohn, Lajanugen Logeswaran, Kyunghoon Bae, and Honglak Lee. Autoguide: Automated generation and selection of context-aware guidelines for large language model agents. arXiv preprint arXiv:2403. 08978, 2024.
[13] Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang. Expel: Llm agents are experiential learners. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 19632-19642, 2024.
[14] Chan Hee Song, Jiaman Wu, Clayton Washington, Brian M Sadler, Wei-Lun Chao, and Yu Su. Llm--eanner: Few-shot grounded planning for embodied agents with large language models. In Proceedings of the IEEE/CVF international conference computer vision, pages 2998-3009, 2023.
[15] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback, arXiv preprint arXiv:2204.0558 2022.

---

[16] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, (1533788-57441 2023.
[17] Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El- Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai ol system card. arXiv preprini wrXiv:2412.167200 2024.
[18) Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning, arXiv preprint arXiv:2501.12945 2025.
[19] Amanda Bertsch, Maor Ivgi, Uri Alon, Jonathan Berant, Matthew R Gormley, and Graham Neubig. In-context learning with long-context models: An in-depth exploration. arXiv preprint arXiv:2405.00200, 2024.
[20] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas Joshi. Hanna Moazam, et al. Dspy: Compiling declarative language model calls into self-improving pipelines. arXiv preprint arXiv:2310.03714. 2023.
[21] Krista Opsahl-Ong Michael Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. Optimizing instructions and demonstrations for multi-stage language model programs. arXiv preprint arXiv:2406. 1695, 2024.
[22] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint 2rXiv:2407.21787, 2024.
[23] Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx. Summer Yue, and Hugh Zhang. Planning in natural language improves Ilm search for code generation. arXiv preprint arXiv:2409.03733 2024.
[24] Xiyao Wang, Zhengyuan Yang. Linjie Li, Hongjin Lu, Yuancheng Xu, Chung-Ching Lin, Kevin Lin, Furong Huang, and Lijuan Wang. Scaling inference-time search with vision value model for improved visual comprehension. arXiv preprint arXiv:2412.03704 2024.
[25] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36:8634-8652, 2023,
[26] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint 26,
[27] Jon Saad-Falcon Adrian Gamarra Lafuente, Shlok Natarajan, Nahum Maru, Hristo Todorov, Etash Guha, E Kelly Buchanan, Mayee Chen, Neel Guha, Christopher Ré, al. Archon: An architecture search framework for inference-time techniques. arXiv preprint 0xXiv:2409.15244 2024.
[28] Shengran Hu, Cong Lu, and Jeff Clune. Automated design of agentic systems. arXiv preprint arXiv:2408.084/ 2024.
[29] Jiayi Zhang, Jinyu Xiang, Zhaoyang Yu, Fengwei Teng, Xionghui Chen, Jiaqi Chen, Mingchen Zhuge, Xin Cheng, Sirui Hong. Jinlin Wang. et al. Aflow: Automating agentic workflow generation. arXiv preprint 20. 2024.
[30] Michael Laskin, Luyu Wang. Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steiger- wald, DJ Strouse, Steven Hansen, Angelos Filos, Ethan Brooks, al. In-context reinforcement learning with algorithm distillation. arXiv preprint arXiv:2210. 152 2022.
[31] Jonathan Lee, Annie Xie, Aldo Pacchiano, Yash Chandak, Chelsea Finn, Ofir Nachum, and Emma Brunskill. Supervised pretraining can learn in-context reinforcement learning. Advances in Neural Information Processing Systems, 36:43057-43083, 2023.
12

---

[32] Zhenwen Dai, Federico Tomasi, and Sina Ghiassian. In-context exploration-exploitation for reinforcement learning. arXiv preprint arXiv:2403..6826, 2024.
[33] Ethan Brooks, Logan Walls, Richard L Lewis, and Satinder Singh. Large language models can implement policy iteration. arXiv preprint arXiv:2210.038211 2022.
[34] Jan Peters and Stefan Schaal. Reinforcement learning by reward-weightes regression for operational space control. In Proceedings of the 24th international conference on Machine learning, pages 745-750, 2007.
[35] Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint arXiv:1711.09846, 2017.
[36] Andrew G Barto. Reinforcement learning: An introduction. by richard's sutton. SIAM Rev, (2):423, 2021.
[37] Mohit Shridhar, Xingdi Yuan, Marc-Alexande Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. arXiv preprint arXiv:2010.037/6 2020.
[38] John Yang, Akshara Prabhakar, Karthik Narasimhan, and Shunyu Yao. Intercode: Standardizing and benchmarking interactive coding with execution feedback. Advances in Neurul Information Processing Systems, 36:23826-23854 2023.
[39] Minqi Jiang, Jelena Luketina, Nantas Nardelli, Pasquale Minervini, Philip HS Torr, Shimon Whiteson, and Tim Rocktäschel. Worderaft: An environment for benchmarking commonsense agents, arXiv preprint (xXx:20007.09/85, 2020.
[40] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03887 2021.
[41] Carlos E Jimenez, John Yang. Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310.06770. 2023.
[42] Hongliang He, Wenlin Yao, Kaixin Ma. Wenhao Yu, Yong Dai, Hongming Zhang, Zhenzhong Lan, and Dong Yu. Webvoyager: Building an end-to-end web agent with large multimodal models. arXiv preprint arXiv:2401.139) 2024.
[43] Nils Reimers and Iryna Gurevych. Sentence-hert: Sentence embeddings using siamese bert- networks. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL htt. http::/tt///xii org/
abs/1908. 10084
[44] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. arXiv preprint 2401::2400.0828// 2024.
[45] Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. Advances in Neural Information Processing Systems, 35:20744-20757, 2022.
[46] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhut- dinov, and Christopher Manning. Hotpotqa: dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv: 1809 1809. 201 8.
13

---

A Limitations and Broader Impacts
We make the assumption that we are given a few human-pree pronan-rrovied examples at the start of the database construction process-an an assumption standard in the Agentic literature [3 12 10] In App. we explore the alternate setting of starting from an empty database, and look forward to further research on bootstrapping from zero human examples in the future. Our algorithm is dependent on the in-context capabilities of LLMs-so our algorithms may be less effective using an LLM with weaker in-context capabilities than gpt-4o-mini, but may be more effective if paired with more advanced LLMs. In addition, our algorithm generally produces improvements in task success rates, monotonically increasing, and we hope future work will help improve
but task success rates both the monotonicity and sample efficiency of our algorithm.
This work has the potential to allow LLM Agents applied to variety of task domains to self- ieprove. This provides a variety of benefits in terms of task performance, but could lead to applications in the future where the agents perform reward hacking-type behavior-performing performing undesirable behaviors that are not captured in task success/failure. Since the behavior of our agents is controlled via in-context examples, a potential mitigation technique could be to manually inspect the databases of self- ieff-generated examples, or even use an LLM Judge to inspect the examples.
B Note on Sequential Decision-Making Tasks
We focus on multi-step sequential macisiion-maknggeeeo tasks where agents must produce series of actions over time based on observations of the environment. The sequential nature of these tasks introduces unique challenges for LLM agents, as they must interpret intermediate environmental feedback. maintain coherent reasoning across multiple steps, and adapt their strategy based on the evolving task state. This contrasts with one-shot generation tasks (e.g., solving math problems 400), one-shot code generation 411) where feedback is only available after the complete solution is provided. Our example-driven learning strategy is potentially also suitable to single-step decision-make makonn tasks, but we focus on the multi-step setting due to its applicability to number of agentic tasks in real-world settings (embodied agents [14), prowser-based tasks (42), etc.).
Formally, these tasks can be modeled as Partially Observable Markov Decision Processes (POMDPs), represented by the tuple OS, ,, R, 7), where S denotes the underlying state space, O the observation space. A the action space, T S x AA + S defines the deterministic transition function, R: x A
the reward function, and y [0, 1] is the discount factor. The partial observability reflects that agents don't 't have direct access to the full environment state but rather receive observations that provide limited information.
Given a task goal g. an episode consists of the agent interacting with the environment for a maximum of T timesteps. At each timestep t, the agent receives an observation o, O of the current state, takes an action a, E A. and the environment transitions to the next state according to the transition function T. In our setting, we specifically consider sparse-reward environments where success is only determined at the end of an episode-thy agent receives R = for successful task completion
and R 0 otherwise. This is a standard setting prior agentic work [ 13 12
C Key Agent Details
In Sec. 2 we establish agent design that enables it to learn in-context from its self-collected experiences. Here, we elaborate on a few key design decisions in our agent design:
Standardized prompts: we use the same simple, task-agnostic prompt templates for all tasks, rather than writing new prompts per task. These prompts are in App. D Alternate appraoches incorporate domain-specific information into their prompts-we discuss these approaches in Appendices J.I and K
Two-level retrieval: We retrieve trajectories at both trajectory level (for planning) and state level (for reasoning and action selection), enabling the agent to leverage both strategic patterns and situation-specifee techniques. Database D contains self-collected trajectories, and retrieval is performed at the trajectory level for the initial plan p. and in the leatl observation-rrasonii action loop for both r; and aq.
14

---

Algorithm 4 Multi-key Retrieval
1: procedure MULTIKEYRETRIEVALOO keys, state_key, query, k. window_sh _iize)
2: similarities + 0
3: for each trajectory T in D do
4: sim 0
5: for each key in traj keys do
6:
sim t- sim CosineSimllartyyquueerkkky. r[key])
7:
sim <- huan//traj_kyss
D- Average similarity across trajectory keys
8:
immilarities.appen///s
9:
similar caailarrraaectoriess + TopK (pppiiiillaisissss k)
10:
if state key is not None then
State-level retrieval with window
11:
windowed results +-
12:
for each trajectory in similar trajectories do
13:
state sint__iillarities +-
14:
for each state in 7-states do
15:
state_sim f-
(aarSS/ii/rrrttuuuusssstteeeeeee sfstate_est sim, s, in)ex(s))
state_similariies.apped(dddi
17:
amost_similn state, idx <- Max(state similarities)
18:
window_stare f- max(0, idx wwindow_sizer size/2]]
19:
window t_l_eeedddd_eed <- min( r.sttatss] idx - [window siieesizeeee size/2])
20:
windowed lall_rrruuttsaasse aappisspppppddr...... wwwndwwwwsweteeee sstatttttttt//t window window_end)) __nd)_endd
21:
return windowed_resulss
22:
else
23:
return similar trajectories
Multi-key retrieval: All retrieval is performed by KNN, with similarity metric defined the average of cosine similarities across the specified 'key' variables. For instance, Line 3 of Alg. retrieve from 'D using two keys: goal and plan p. We return similar trajectories based off the average of the cosine similarities of goals and plans when comparing each trajectory the current trajectory. When doing state-level retrieval (Lines and 10), additionally find the most similar states within the selected trajectories via state-level key Oz or Tr. then return window of states around the most similar state. This similar the retrieval scheme in [10.. See detailed pseudocode for retrieval in Alg.
Thought- retrieval: For the first step of a trajectory, we retrieve using the trajectory- level keys (g-p) well as the current observation (Alg. line 6) but for all subsequent steps we use reasoning 7t as a key instead of observation or (Alg. line 9). This approach, inspired by Zhou et al. [TT], enables generalization across trajectories with similar reasoning, and similarity across natural-language ra can be handled by generic embedding functions easily than potentially bespoke observations ot. By retrieving every step, aim retrieve the most relevant trajectories for each decision.
Generic embedding mechanism: Since g. P. and r, are all natural-language strings, we employ standard embeddings (all-MiniLM-L6-x22 [43] that generalize across domains without task specifcc engineering.
D Token Usage and Cost Analysis
We provide a detailed breakdown of token usage and costs for our self-improvement approach across all three benchmarks. This analysis demonstrates the economic viability of our method compared to alternative approaches for scaling model performance.
D.I Per-Episode Token Usage
Table 4 summarizes the average token consumption per episode across our three evaluation domains. Token counts reflect the full agent execution trace, including both reasoning and action generation steps.
15

---

Benchmark
Avg Input Tokens
Avg Output Tokens
Max Episode Length
Worderaft
5,047
68
8 requests
InterCode 5,385
37
20 requests
ALFWorld 3,706
30
61 requests
Table 4: Average token usage per episode across benchmarks. Episode length refers to the maximum
number API requests needed to complete task.
The token usage pattern reflects our agent architecture design. For any task, we require requests per step (one for reasoning, one for acting), plus additional request when using planning at the episode start. The variance in input token counts primarily reflects differences in accumulated trajectory history within an episode.
D.2 Per-Episode Cost Breakdown
Using GPT-4o-mini pricing (as of writing: $0. 15 per 1M input tokens, $0.60 per 1M output tokens), calculate the cost per episode for each benchmark:
Wordcraft:
Cost (5,047 x 0.15 68 x 0.60)/1,0000,00 x 8 = $0.006 per episode
InterCode: Cost (5,385 0.15 37 (.600/1,,00.0 x $0.016 per episode
ALFWorld:
Cost (3,706 0.15 + 30
x 61 $0.034 per episode
D.3 Training Database Construction Costs
Our full self-improvement configuration uses 5 parallel databases with trajectory bootstrapping and exemplar curation. For ALFWorld, we collect 3,500 training trajectories per database; for Wordcraft, we collect 4,000 trajectories per database; and for InterCode, we collect 800 trajectories per database. The worst-case cost for database construction is:
Benchmark
Episodes per DB
Total Episodes
Total Training Cost
Per-Task Inference Cost
Wordcraft
InterCode 4,000
20,000
$120
$0.006
800
4,000
S64
$0.016
ALFWorld 3,500
17,500
$595
$0.034
Table Training and inference costs across benchmarks. Total episodes calculated as episodes per database parallel databases.
Note that these costs represent one-time upfront investments. Once the databases are constructed, the per-task inference cost remains constant regardless of how many test-time tasks are processed.
D.4 Cost Comparison with Baseline Approaches
We compare our approach against two common alternatives:
Alternative 1: Using a larger model (GPT-4o). At current pricing ($5.00/S15.00 per 1M input/out- put tokens), GPT-40 costs approximately:
Worderaft: $0.20 per task
InterCode: $0.54 per task
ALFWorld: $0.57 per task
Alternative Test-time scaling with multiple attempts. task (assuming perfect verifier):
Using GPT-4o-mini with attempts per
16

---

Wordcraft: $0.018 task
InterCode: $0.048 per task
ALFWorld: $0.102 per task
D.5
Breakeven Analysis
For ALFWorld (our most expensive benchmark), our method breaks even with:
GPT-4o after $595/($0.57 - $0.034) ~ 1,110 test tasks
GPT-4o-mini with attempts after
S0.034) v 8,750 test tasks
D.6 Production-Scale Cost Savings
To contextualize these savings at production scale, consider hypothetical agentic service processing 1 million ALFWorld tasks daily (a modest industry-scale throughput):
Daily cost comparison:
Our approach: 1M x $0.034 + $595 (amortized) R $34,595
GPT-4o baseline: 1M $0.57 $570,000
GPT-4o-mini with 3 attempts: 1M x $0.102 = $102,000
Daily savings:
vs. GPT-4o: $535,405 ($195M annually)
3-attempt baseline: $67,405 ($24.6M annually)
These calculations demonstrate that even modest upfront investments in self-improvement can yield substantial returns at production scale, while simultaneously improving task performance.
E
Additional Implementation Details
E.1
Hyperparameters
Unless otherwise specified, we use GPT-4o-mini as base LLM (temperature 0.1). For Fixed-DB and all Traj-Bootstrap agents, we retrieve the top-k most similar trajectories at each decision step (k = 6 for ALFWorld and InterCode-SQLL 10 for Wordcraft). We initialize each database with small buoanddrovided example set (18 for ALFWorld, 10 for InterCode-SQL.. for Wordcraft). With +DB-Curan BOB-Curation. maintain N 5 database instances with curation every time the database size is doubled, starting with a minimum size of ten trajectories. We report success rates averaged over five random seeds. The standard deviation of the success rates is also reported. By default, report success rate given the database at the end of the training process.
E.2 Prompt Templates
Across all benchmarks, we use standardized prompt templates for the core components of our retrieval-based ReAct agent. The same templates were used across all benchmarks with no task- specific modifications. These templates are intentionally minimalist, focusing providing the necessary context and retrieved examples while avoiding task-specific prompt engineering.
The templates are included below. Across all templates, the in-context examples follow the format specified in the prompt itself (for plan, the in-context examples are form "goal.plan", etc):
Plan:
17

---

prstem_prompts 'You are an expert at generating high-level plans of actions to achieve goal. An Here is your action space: paction_spaced An Here are some examples of plan from episodes that succesafully achieved similar goals: {examplea)' user_prompt, 'goal; (g plan:
Reason:
prstemmprompt: 'You are an expert at reasoning about the most appropriate action to take towards achieving goal. An Here is your action space: daction_spaced An Here are some examplea of
goal, plan, inteevvatioo,resoninngg action from episodes that successfully achieved similar goals: {examples)'
user_prompt- 'goal: {noal)An plan: (plan)\n trajectory: (trajectory)\n reasoning:
Act:
prompt: 'You
agent in environment. Given the current
towards achieving goal: (self. (self.goal). An Here is your action space: daction_space); Here are some
observation, you must select an action
examples of paal,,paa,obberraaee observation, cbservatioon.eaaonngg..eee
from episodes that successfully achieved similar goals: {examples)'
user ppoopt:: 'goal: (goal)(n plan: {plan)nn trajectory: (trajectory) action:
E.3
Retrieval Implementation
For all retrieval steps, we implement hybrid search across all the desired retrieval keys-ex, goal, plan, observation, reasoning. We return the top-k examples by averaged distance across each of the keys. We implement a sliding window approach for state-level retrieval to enhance contextual relevance-we include the surrounding context (preceding and following states) up window of 5 steps to provide coherent episode fragments.
The retrieval mechanism is implemented using FAISS 44 for efficient similarity search the
database grows. We use exact nearest neighbor search.
E.4 Population-Based Training Details
Our database-level curation approach maintains a population of database instances. Each instance is initialized with the same set of duman-providee exemplars. The population undergoes curation every time the database size doubles, and performance evaluated on the tasks attempted since previous doubling.
The replacement strategy follows standard population- based training practices: the bottom 20% of databases (based on validation performance) are replaced with copies of the top 20%.
E.5
Quality Metric Computation
For exemplar-level curation, we track the retrieval patterns of each trajectory throughout the training process. For each task, we record: 1. Which trajectories were retrieved How many times each trajectory was retrieved during the solution process 3. Whether the task was successfully completed
After completing all training tasks, compute the quality metric Q(T) for each trajectory r
Q(T) ΣIERG) 9 f((T) ΣiER(T) f((T)
where R(T) the set of tasks for which trajectory was retrieved, o, E (0, 1} is the outcome of task and f((T) is the retrieval frequency of trajectory during task i.
18

---

Method
ALFWorld
InterCode-SQL
Wordcraft
Traj- Bar.Boosaaa------eenn----CC-rrre
0.93+-0.03
0.82+-0.01
0.69
ReAct-Finetune
0.96+00.0
0.79+00.01
0.74+0.01
Table 6: Trained the same data, fine-tuned agent ReAct-Finetune competitive with our best in-context approach. This suggests that our self-collected data is effective not only for in-context prompting but also for creating fine-tuned agents. All values are averages over 5 trials.
To ensure statistical significance, we only compute the quality metric for trajectories that were retrieved for at least different tasks. For trajectories with insufficient retrieval data, we assign neutral quality score equal to the average success rate across all tasks.
E.6 Note on planning step
Following the convention from RAP [0]. we omit the planning step on benchmarks with short trajectory length (Intercode-SQL. Worderaft). This planning step is valuable for maintaining long- horizon coherence on the ALFWorld benchmarks (30 steps), and is standard in prior ReAct-based agentic work [10 13 12), whether the planning step is explicitly separate from reasoning, or incorporated into the first reasoning step.
Can Self-Collected Examples Improve a Fine-Tuned LLM Agent?
We have shown that self-collected databases improve the performance in-context LLM agents. Here, we test whether the same data also benefit fine-tuning.
Using the OpenAl fine-tuning API, we fine-tune GPT-4o-mini on each benchmark using data from our best-performing database construction method: wraj-Bootstrap+-DB Feee-l---e------- Carplarrnrrrrion,, collected over the full training set. We fine-tune using simple ReAct-format prompt:
'syatem': You are ReAct agent that helps users accomplish tasks. Given a
goal, you will receive observations about the environment and respond with your reasoning and actions. For each observation, first think through the problem step by step (Thought), then decide on action (Action),
+ actions should be clear, concise, directly executable the environment.'s
"user'"'Goaa" :Goal: {goal} \n Initial observation: (iseervations00))
'assistant's 'Thought: (inemming(i]AAAAttioin [action[i]}},
'user': 'Observation: (observations [i+1]}', (i+1])
We refer to the resulting fine-tuned model as ReAct-Finetuur To run the agent, we prompt it with goal and initial observation, then alternate assistant messages (for reasoning and action) with user messages (for new observations).
Tab. 6 shows that ReAct-Finetune slightly outperforms the in-context agent ALFWorld (0.96 vs. 0,93) and Worderaft (0.74 vs. 0.69), while performing slightly worse on InterCode-SQL (0.79 vs. 0.82). These results suggest that self-collected examples are effective only for in-context prompting but also for creating competitive fine-tuned agents.
G Can Databases Transfer Across LLMs?
To evaluate whether our self-improvement approach captures fundamental task structure or merely exploits model-specific artifacts, we conducted additional experiments using Mixtral 8x7B Instruct, popular open-source model with different architecture and capabilities than GPT-4o-mini. This experiment tests a challenging transfer scenario: databases collected with GPT-4o-mini are used to improve different model at test time, without any additional data collection fine-tuning
19

---

G.1 Experimental Setup
We evaluate Mixtral 8x7B on all three benchmarks, comparing the Fixed-DB baseline to Traj- Boosstap-DDB-xxemplar Curation. Critically, all databases were previously collected using GPT-4o- mini trajectories. Each configuration evaluated over random seeds, with results averaged across trials. As seen in Table 7 despite the distribution gap between the collection model (GPTT-4o-mini) and deployment model (Mixtral 8x7B), our self-improvement methods yield substantial performance gains across all benchmarks.
Benchmark
Fixed-DB
TrajBS+DB+-EemplarGGG
Improvement
ALFWorld
0.27
0.55
+28 points
IC-SQL
0.52
0.70
+18 points
Wordcraft
0.40
0.52
+12 points
Table 7: Cross-model generalization results with Mixtral 8x7B Instruct v0.1 using databases collected
with GPT-44-mini. All results averaged over 5 trials. Full Method refers to Traj-Bootstrap DB-
Curation Exemplar-Curation.
G.2 Comparison with In-Distribution Performance
Benchmark GPT-4o-mini Improvement
Mixtral 8x7B Improvement
ALFWorld
+20 points
+28 points
IC-SQL.
+7 points
+ 188 points
Worderaft
+14 points
+ +12 points
Table 8: Comparison of performance improvements (Fixed-DB vs. Traj-BS-DB-EEemplar--C
between the collection model (GPT-4o-mini) and different deployment model (Mixtral 8x7B).
Table 8 compares the improvements observed with Mixtral 8x7B against those achieved with GPT- 4o-mini (the collection model) using the same methods. The improvements with Mixtral 8x7B match or exceed those observed with GPT--4omiii on all three benchmarks. This suggests that our approach captures fundamental task structure such as effective exploration strategies, common failure modes, and successful action cenuences-rather than exploiting model-specific quirks or artifacts.
H Can We Predict Agent Success Rates?
We have shown that increasing the number of self-collected examples improves agent performance. Here, we test whether the same examples also predict performance on new tasks.
On InterCode-SCe and Wordcraft, task difficulty is partly observable from the goal g and initial observation 01. For InterCode- SQLL, is a natural-language query. For Worderaft, is the desired element and 01 specifies available crafting elements. In contrast, ALFWorld task difficulty depends heavily scene layout, which and o do not reveal. We therefore exclude ALFWorld from this analysis.
We use the same embedding model as in retrieval (all-Minil string [g: 01). We train a calibrated Random Forest classifier predict task success/failure, calibrating its outputs via 5-fold cross-validation with a learned sigmoid function. For each of 5 independent Traj-Bootstrap trials, we evaluate (1) the classifier's AUROC held-out tasks, and (2) its calibration.
3 to encode the concatenated
As shown in Fig. prediction performance improves as the database grows. For InterCode-SQLL AUROC rises from 0.60 (100 tasks) to 0.77 (800 tasks). Wordcraft shows similar trend, improving from 0.50 (100 tasks) to 0.71 (4000 tasks). In both cases, predictive accuracy increases alongside task performance.
Fig. G shows the calibration of the final classifiers (trained on available training tasks). Predicted success probabilities closely match observed success rates, indicating well-calibrated models.
20

---

1.00
1.00
ROC AUC
0.75
AUC
0.75
0.50
0.50
0.25
0.25
0.00
0.00
200
400
600
800
1000 2000 3000
Num training tasks
Num training tasks
(a) InterCode-SQL
(b) Worderaft
Figure 5: AUROC of success prediction improves with more self-collected examples. Performance
continues rise with increasing database size.
Observed Task Success Rate
Oeserved Task Success Rate
1.0
1.0
0.5
0.5
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
Predicted Prob of lask Success
Predicted Prob of lask Success
(a) InterCode-SQL
(b) Worderaft
Figure 6: Predicted probabilities are well-calibrated. For both benchmarks, predicted and empirical success rates generally align.
I Is it Possible to Bootstrap an Agent Without Initial Hand-Crafted Examples?
Providing small number of hand-crafted in-context examples is standard practice in the LLM agent literature 13 12 12] IO] However, what if we initialized Traj-Bootstras with an empty database? In order understand the value the initial human- -umanndrovided examples, we test Traj-Boostrap with and without the initial human-provided examples on Wordcraft. We refer to the variant initialized with an empty database as -Human-Eaa -xamnanss Traj-Bootstrap, initialized by default with a database of 5 human-provided provided trajectories for Wordcraft, achieves better performance with these starting examples than when initialized from an empty database (-Human Exammles. Performance still scales with database size for Human-EXxmpless examples, even after self-collecting trajectories on 4000 training tasks. On at least this one task, the initial human-prov human-provided trajectories shaped the reasoning and action patterns of the agent in a way that boosted the continual database construction process. We leave exploration of hand-crafting these in-context examples to future work.
in this case fails to reach the performance achieved
via 5 numan-providee
J Key Details of Prior Agentic Approaches
J.1 How does Automanual Leverage Hand-Crafted Information
Rather than learning from self-collected examples, an alternate approach agent construction is to leverage practitioner domain knowledge. Beyond implementing both hierarchical learning system and code-based action spaces, Automanual 4 incorporates domain knowledge about the ALFWorld task into multiple components of the algorithm. In this section we include some code from the official Automanual GitHub illustrate.
Observation spaces Automanual uses a modified observation space that enhances the FL.Worll string by adding two critical pieces of information: 1) The current location of the agent, 2) What the
21

---

Wordcraft
Success Rate
0.60
0.55
0.50
0.45
1000 2000 4000
Num. Training Tasks
Traj-Bootstrap
-Human Exammples
Figure 7: Ablating the value of initial human-provided examples, Worderaft. Traj-Bootstrap. initialized by default with a database of 5 human-provided trajectories for Wordcraft, achieves better performance with these starting examples than when initialized from an empty database (-Human- Examples). Performance still scales with database size for -Human --uma-uu-aapaaaa Examples-buu in this case fails to reach the performance achieved via human mronann-rovieed examples, even after self-collecting trajectories on 4000 training tasks.
agent is currently holding. Both of these pieces of information typically have to be deduced from the trajectory of previous observations and actions. but Automanual tracks them explicitly:
if "Kothing happens" in observation: self last__bbs observation
if "go to" in script:
self. cur_uur_looo re search go to ((S+)', script) group curffcur_loc, info observation
if "open" script "close" script:
observation
if "take" in script: self holding [Pssear (.+?) (?=\sfrom)", script) group(1)
wew.ch (x"
10
self. cur cuw_loo_iiffoor
11
if
"put" in script:
12
self holding "nothing"
elif "go _ur_loc_info-
self. cur script:
14
15
loc re.schhc go to (As+)', script) group(1)
16
if loc == curf.cur_loc.
observation f" You welf.cur_loee
observation self cur cur_loc_info
{self cur_ and holding (self holding)
Action spaces In ALFWorld. any task typically involves three main components: Searching for an object, 2) Performing action with the object (heating, cooling, cleaning, etc.), 3) Placing the object somewhere. Automanual significantly simplifies both the search and placement operations by providing multi-action helper functions within its code-based action space:
Defóne helper method to fänd object that is needed def find_object (agent, recep_to, check, object_name): for receptacle in recep_to_ce (receptacle) observation agent. go_ttoottoooooooo # Check if we need to open the receptacle. If we do, open it.
to_p_tt__heck,,
if 'closed' in observation:
observation agent.open (peceeetta))))
Check if the object és in/on the receptacle. if object_name in observation:
10
object_ids get_ vet_objeet__te return bdjs receptacle return None, None
(itec_nname)
12
13
22

---

14
Deféne a helper method to put object in/on the target receptacle def go_to__ut__o_jee paj____bjecaaaeett, rarget__eceptaale, object_id): observation agent. Beanttgo_otttrrreee check if target, receptacle closed. If so, open it.
15
16
17
18
if 'closed' observation:
19
observation agent. www. (pertarett_recepttccll receptacle)
observation agent. peent.put_in__eee pnt__in_or_onobjjecee target_receptacle) return observation
J.2 A note on training and test sets
The distinction between how different techniques leverage data is crucial in understanding the generalization capabilities of LLM agents. We can categorize existing approaches based on how they treat training and test data:
Single-Task Optimization Some approaches focus exclusively on improving performance on single task instance without concern for generalization. For example, Shinn et (25) leverages feedback from failed attempts to incrementally improve performance on the same task. Similarly, search methods [22 24 expand the solution space for specific problem instance. While these approaches can solve individual tasks, they don't 't transfer knowledge across different problems, essentially 'overfitting' a single instance.
Mixed Train-Test Evaluation Some recent work blurs training and test boundaries. For instance, RAP [10] makes multiple passes over the same dataset, allowing the system to 'learn' from some test examples before evaluating others within the same This approach does assess true generalization capability, as the model has indirect exposure to the test distribution during its learning phase.
Full Train-Test Separation Several papers maintain a clear separation between training and test data: 1) ExpeL [13] extracts general rules from a training set of trajectories and applies them to entirely separate test tasks, 2) AutoGuide [2] generates contextual guidelines from training experiences that are evaluated on distinct test scenarios. 3) AutoManual [4] constructs hierarchical 'manuals' from training interactions that are then applied novel test tasks.
Our approach similarly ensures that trajectories used for database construction come exclusively from designated training tasks, with evaluation conducted on separate set of test tasks never seen during the database construction phase. This separation is essential for validating that the knowledge captured by the agent generalizes to new problems rather than memorizing specific solutions.
K Comparison to Hand-Crafted InterCode-SQL. Agent
We further contextualize the performance of Traj Traj-Boots Booittroottappp by comparing to two hand-crafted agents on InterCode-SQL. The Intercode-SQL paper (38) provides hand-crafted agent, GameSQL to solve the task, and optionally provides the agent with a "handicap'ggiving -giving the agent information on all relevant parts of the database schema. We denote the assisted version GameSQL+Cheat, Neither agent provides in-context examples, and both share a bespoke, hand-crafted prompt (see App. N.
As seen in Tab. 9 Fixed-DB performs similarly to GameSQL (0.74 vs 0.73), and the performance of our best method, +DB+Exemplar- Curation, approaches the performance of GameSQL+Cheal (0.82 vs 0.84). Therefore, our Curtammmpa---raatioonn ReAct-style agent nearly as much as the lift provided to the hand-crafted agent via 'handicap' access to the database schema.
techniques lift the performance of a generic
23

---

Method
Intercode-SQL. Success Rate
GameSQL
0.73
GameSQL+Cheat
0.84
Fixed-DB
0.74
Traj-Bootstran
0.79
+DB-Curation
0.78
TExemplar-Curatio
0.81
#DB+xxemmlar-Curall
0.82
Table 9: Comparison of agent success rates InterCode-SQL: contextualizing the performance
of Traj-Boostrap. Without cheats, the hand-crafted GameSQL. agent (0.73) performs comparably to
Fixed-DB (0.74). With handicap access to the database schema, GameSQL+Cheat (0.84) slightly outperforms +DBB+Exempla-Curaaa
(0.82). The boost from our database-construction techniques nearly matches the boost from providing the GameSQL agent with access to privileged database schema information.
L Benchmark Details
L.1 ALFWorld
ALFWorld is text-based environment that aligns with embodied tasks, allowing agents navi- gate and manipulate objects through textual commands. We use the standard ALFWorld benchmark consisting of 3500 training tasks and 134 -utto-ddistribution test tasks across task categories:
Pick & Place: Find and move objects to specified locations
Clean & Place: Find, clean, and place objects
Heat & Place: Find, heat, and place objects
Cool & Place: Find, cool, and place objects
Pick Two & Place: Find and move two objects to specified location
Look at Object: Find object and examine under light
Following [10]. for the ALFWorld benchmark we perform similarity search over task categories in addition to the other retrieval keys (goal, plan, observation, action). We do this follow the convention in this prior work.
For our initial human- -rooandd exemplars, used the 18 successful trajectories (3 per task category) provided by Zhao et al. 113. These trajectories were used to initialize all database instances.
The success criteria for ALFWorld tasks are defined by the environment and require the agent to satisfy all conditions specified in the goal. For example, a 'Heat & Place* task, the agent must find the target object, place it in the microwave. turn the microwave, and finally place the heated object at the specified destination. Both Autoguide and Automanual allow 50 actions for task completion- but choosing to employ "reasoning" counts action. Since force agent reason every step, we allow our agents (Fixed-DB, (on Autoguide and Automanual, the agent does not reason in practice at most steps in search procedure).
and variants) only 30 steps for task completion
For this benchmark, we do not provide an action space string to the LLM, relying purely on the in-context examples to communicate the action space.
L.2 InterCode-SQL
InterCode-SQI. 38 is an interactive coding environment for evaluating language agents' SQL programming abilities. We use subset of the InterCode benchmark focusing SQL query generation, built upon the Spider SQI. dataset. Of the 1034 tasks the dataset, we randomly assign 800 tasks train and the remaining 234 tasks test.

---

Each task provides a natural language query request. The agent must generate a syntactically correct SQL query that retrieves the requested information. The agent must first execute queries understand the database schema. The environment provides feedback on syntax errors and execution results, but the agent is only allowed submit a solution once.
The success criteria for InterCode-SQL tasks require the agent to submit a solution query within 10 steps. The environment executes the query and compares the results against a ground-truth reference.
For our initial human-provided exemplars, we collected 10 human-created trajectories for 10 randomly-selectee training tasks. These trajectories all solved trajectories, we append the solution query to the goal string since the goal of the task is to 'discover' this query through interacting with the SQL database.
used to initialize all database instances. For
We used the following action space string for InterCode-SQL:
Your action space is outputting valid mysql commands to solve the sql task. You will be evaluated the Latest Standard Output. If you believe the latest observation is the final answer, you complete the task by running 'submit' by itself.
You have 10 iterations to solve the task.
Follow the syntax and logical flow from the provided examples exactly.
L.3 Worderaft
Wordcraft [39] a simplified adaptation of the game Little Alchemy, where agents must combine elements to create elements through multi-step processes. We randomly select 4000 training tasks and 500 test tasks from the subset of tasks requiring up to steps to solve, with the train-test split separating the tasks into disjoint sets of goal elements.
The agent starts with set elements and must discover combinations that creates a particular target element specified in the goal. The environment provides feedback successful combinations and updates the available elements accordingly.
The success criteria for Wordcraft tasks require the agent to create the target element within 4 steps, while the minimum solution length up steps.
For our initial numan-provided exemplars, we collected human-annotatee trajectories from randomly-selectimg training tasks. These trajectories were used to initialize all database instances. We collected fewer initial trajectories for Worderaft than for InterCode-SQL. (4 vs 10) since Wordcraft is slightly simpler task, requiring up to 4 steps for task completion while InterCode-SCi requires up to 10.
We used the following action space string for Wordcraft:
Output strings with the names the two entities we would like to combine in this step.
L.4
Note on Benchmark Selection
We selected three sequential preision-making benchmarks that cover different reasoning chal- Loges--AFFWorkee [37] tests text-based navigation and object manipulation, InterCode-SQL tests interactive code generation, and Worderaft (39 tests compositional reasoning.
38
we encountered bugs generating achievable goals the full benchmark (confirmed by http:///ihhhlooooommmcooooo//oss and identified tasks with incorrect rewards.
While prior works 13 test on WebShop 45),
We excluded QA benchmarks (HotPotQA 46 etc.) because performance depends information retriever quality and LILM self-evaluation efficacy, two factors that would confound our study of LLM Self--mprovemeett We plan to test algorithms QA benchmarks in future work.
25

---

M
Computational Resources
All experiments were conducted using the following computational resources:
NVIDIA A5000 GPU (24GB memory) for embedding computation
64GB RAM
The majority of computation was spent on OpenAl API calls for the LLM-based decision-making. Database operations including embedding computation, storage, and retrieval accounted for less than 5% of the total computation time.
For embedding computations, used all-MiniLM-LL-v22 [43
For LLM inference, we used the OpenAl API for GPT-4o-mini, which required approximately:
2,000,000 API calls for ALFWorld
200,000 API calls for InterCode-SQLI
500,000 API calls for Wordcraft
The total cost of API usage was approximately $3,000 USD.
N
GameSQL Prompt
Yang et al.
38 write this hand-crafted prompt for the GameSQL agent:
(self. Language)Env is multé- turn game that tests your ability to write
(self. language) command that produces an output corresponding to natural language query.
#8 GAKE DESCRIPTION
At the start of this game, you are given natural language query describing
-
both and Asúde from the natural language query, you have no information about the tables you have access to.
destred output (i.e. "Find the first name of student
+ dog pets").
10 The game will played in series of turns. Each turn, you can submit + {self. language} command.
11
You will then get response detailing the output of your {self. language) query along with reward 12 that tells you how close your (self. language) command is to the correct + answer.
13
The goal of this game is to write fself. language) command that gets reward of The game will automatically
15
terminate once you get reward of 1.
16
17
#$ INPUT DESCRIPTION
Each turn, you submit (self. language) command. Your (self. language)
+ command should be formatted as follows:
19
20
(self. language)
Your {self. language} code here
23
24
Your (self. language} command can help you do one of two things:
25
1. Learn more about the tables you have access to
2. Ezecute fself. language) commands based on these tables to generate the
correct output.
27
26

---

28
# OUTPUT DESCRIPTION
29
Given your (self- language) command imput, "fself. Language)Env will then give back output formatted follows:
10
31
Output: <string?
32
Reward: <decimal value between and 1>
The output is string displaying the result from executing your + {self. language) query.
35
The reward is a decimal value between and 1.
36
## REWARD DESCRIPTION
The reward should interpreted ratio. tells you how many your
+ {self. language)
29
command outputted correctly compared to the correct answer.
40
## RULES
1. NOT ask questions. Your commands fed directly into SQL compiler.
43
44
# STRATEGY
You are free to play as many turns of the game you' d like to inspect tables and develop your (self language} command.
47
48 The best strategy for this game is to first write (self. language) commands that help you learn about the tables that you have access to. For instance, in SQL environment, you might 50 and "DESC <table name> to learn more about the tables you have access to.
'SHOY TABLES
51
52 Once you have good understanding of the tables, you should then write {self. language) commands
59 that would answer the natural language query using tables you have access to.
54
27

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Abstract and intro clearly state the contributions, which match the experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See App.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
28

---

Justification:
Paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Information provided both in Sec and in several sections of the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer: [Yes]
Justification: Code is attached in Supplemental, and will be made publicly available. Bench- marks are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/pp wwcppblic/guticcccccccceee.oo.pe wetgguddddeeoeeubbinnnnn ssiiisolccyyyyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details across Sec. 6 and Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All tables have standard deviation of success rate across 5 trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information in Appendix M
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See App.
A
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Paper offers an algorithmic framework for self-improving LLM Agent, existing safeguards for L.LMs themselves apply when an L.M used within the agentic system.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All used models and benchmarks are cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cow/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets. The paper does include code to replicate experiments in the supplemental, but this code is not core asset introduced by the paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
33

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
Justification: Paper describes usage of LLMs as a core component of an LLM Agent.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
34


Reviews:
[{"review_id": "BgjZ6wdia8", "reviewer": "Reviewer_eKr8", "summary": "This paper provides extensive experiments consistently showing that using only successful self-generated trajectories as in-context examples can cause an increase in performance. Furthermore, they provide a dataset curation method (DB+) to store the most relevant successful trajectories that can be used with multiple reasoning algorithms.", "questions": "See Weakness 1", "limitations": "See Weakness 1", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThe authors use a trajectory bootstrapping method, DB+, that samples successful self-generated trajectories to be used for self-improvement for sequential decision making\n\nLots of ablations to show consistent increased performance with successful self-generated examples across different algorithms, tasks, and models.\n\nThe idea of predicting agent success in Section 6.4 is novel\n\nLine 155 about collective properties is I think a significant benefit of this approach as it relates to the coverage of situations that the agent has examples to rely on\n \n**Weakness**\n\nMy 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. 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. I understand Figure 2 shows that in some cases only 1000 training tasks are needed to reach the performance of 3500 training tasks. Furthermore, in Figures 2 and 3, of these training tasks, how many of them have failed trajectories that are discarded?\n\nConsider also citing some In-Context RL papers such as [1], which also looks at multi-step decision making.\n\n[1] Dai, Zhenwen, Federico Tomasi, and Sina Ghiassian. \"In-context Exploration-Exploitation for Reinforcement Learning.\" arXiv preprint arXiv:2403.06826 (2024).", "was_revised": true, "final_justification": "I think the authors did a relatively good job of addressing concerns of cost analysis and failed trajectory use. They also responded well to novelty issues brought up by another reviewer. I think this paper can contribute to the field.", "rebuttal": "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.\n\n> 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.\n\nWe appreciate your concern about discarding failed trajectories and provide detailed analysis below.\n\n**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.\n\n**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.\n\n**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.\n\n> 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.\n\nYou 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.\n\n> Consider also citing some In-Context RL papers such as [1], which also looks at multi-step decision making.\n\nThank you for the suggestion. Here is an updated related work section we propose to include in our final manuscript:\n\nOur 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.\n\n**References:**\n- Laskin, Michael, et al. \"In-context Reinforcement Learning with Algorithm Distillation.\" ICLR 2023\n- Lee, Jonathan, et al. \"Supervised pretraining can learn in-context reinforcement learning.\" NeurIPS 2023  \n- Dai, Zhenwen, et al. \"In-context Exploration-Exploitation for Reinforcement Learning.\" ICLR 2024\n- Brooks, Ethan, et al. \"Large language models can implement policy iteration.\" NeurIPS 2023"}, {"review_id": "RJTq6VUkFk", "reviewer": "Reviewer_4WEi", "summary": "This paper proposes a method for improving large language model (LLM) agents on sequential decision-making tasks by leveraging self-generated, successful trajectories as in-context examples. Instead of relying on human-engineered prompts or domain-specific action/observation design, the authors introduce a trajectory bootstrapping approach that enables agents to iteratively build and refine a database of successful trajectories through autonomous experience. Key innovations include:\n\t•\tTraj-Bootstrap: a simple accumulation of successful task completions.\n\t•\t+DB-Curation: database-level curation using population-based training.\n\t•\t+Exemplar-Curation: exemplar-level selection of trajectories using a value metric based on empirical utility.\nExtensive experiments on ALFWorld, Wordcraft, and InterCode-SQL demonstrate notable performance gains, even surpassing methods that use more powerful LLMs or handcrafted components.", "questions": "1\tPaper 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.\n2\tGeneralization 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.\n3\tTraining/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?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: The paper offers a practical and scalable alternative to manual prompt engineering, validated through solid empirical results. The bootstrapping and curation strategies are clearly described and effectively evaluated across diverse tasks. The proposed method offers a general, task-agnostic mechanism that could be widely useful in agentic settings. It shows that high performance can be achieved even with lightweight models through data-centric optimization.\n\n\nWeaknesses: The methodology is well-implemented but somewhat straightforward, relying heavily on repeated LLM calls during training. While empirical gains are strong, theoretical insights are limited. The structure of the paper is confusing. Notably, placing the Problem Statement before Related Work breaks conventional scientific writing flow. This likely reflects an incomplete or unpolished draft and disrupts the narrative logic for readers. The novelty lies in the reuse and filtering of examples, which is more incremental than transformative compared to prior ReAct-style agents and retrieval-based pipelines. 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.", "was_revised": true, "final_justification": "My concerns have been addressed and I am recommending acceptance.", "rebuttal": "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.\"\n\n> 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.\n\nWe 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.\n\n> 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.\n\nYour 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). \n\nResults 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.\n\nAlthough 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.**\n\n> 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?\n\nYou 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.\n\nAdditionally, 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. \n\n**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.**\n\n> 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. \n\nWe 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."}, {"review_id": "zhr0oZ5Uzj", "reviewer": "Reviewer_HntP", "summary": "The paper proposes an approach to improve LLM Agent by retrieving and curating existing trajectories. The proposed method is based on first collecting successful agent trajectories, then improve the data quality by database-level curation or exemplar-level curation. Experiment shows that each proposed component is effective on ALFWorld, InterCode-SQL and Wordcraft in terms of improving the success rate of LLM after seeing more training trajectories.", "questions": "- 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?\n- Table 2 uses different LLM models for baselines and proposed method, it would be nice to make them consistent. \n- Table 2 show the bootstrap method's performance with gpt-4o-mini. Can the authors include some results from other models (e.g. open-sourced models) to justify the generalizibility of the method?\n- Is the retrieval on trajectory-level or sub-trajectory-level?", "limitations": "Limitations are discussed in Appendix A, about the method may be less effective with weaker models.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The experiments include full ablation study of each single component in algorithm, making it easy to interpret the method and results. \n- The paper writing is clear and the result presentation is good.\n\n## Weaknesses\n- The novelty of the proposed method seems to be limited. 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. From the results on ALFWorld, these two methods are on par, but [Xiao 2024] uses fewer training trajectories in total. It would be nice if the authors can justify the novelty, uniqueness and advantages of the proposed method, and do some experiments to compare with them.\n- 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. \n\n\n\nXiao et al. O3D: Offline Data-driven Discovery and Distillation for Sequential Decision-Making with Large Language Models. COLM 2024.", "was_revised": true, "final_justification": "The authors included more experiment results show the generalizability of the method. In the case where the agent is supposed to interact with a large amount of test tasks, the proposed method can be cost-efficient. \n\nI still think that the presentation of the paper can be improved. For example, show some concrete examples of database and exemplar. Also, it's better to incorporate the discussion in rebuttal into the final paper.", "rebuttal": "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.\"\n\n> 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\n\nWe 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.\n\n**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.\n\n**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. \n\nIn 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.   \n\n**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.\n\n> Can the authors include some results from other models (e.g. open-sourced models) to justify the generalizibility of the method? \n\nAddressing 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.\n\n> 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.\n\n**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.\n\n**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.\n\n> 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?\n\n**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. \n\n> Is the retrieval on trajectory-level or sub-trajectory-level? \n\nWhen 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. \n\n> Table 2 uses different LLM models for baselines and proposed method, it would be nice to make them consistent. \n\nWe 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."}, {"review_id": "IQT1vTTBht", "reviewer": "Reviewer_YEwY", "summary": "This paper proposes an exemplar curation approach for LLM agents in sequential decision making tasks. The proposed approach views the training of LLM agents as exemplar curation, where a growing list of exemplars are curated using two complementary methods, DB-curation,  and exemplar-curation, to maintain a database of retrievable successful examples that the agent has attempted. The proposed approach is evaluated on three sequential decisionmaking tasks, showing improvements competitive with the state of the arts. Ablation studies validate the effectiveness of proposed curation approaches.", "questions": "- Does the agent see few-shot exemplars aside from the ones it retrieves?\n- Can you provide examples of retrieved exemplars? It would be useful to show how the retrieved exemplars collective shape the agent's policy.\n- Is the high level plan fixed once generated? How important is it for the initial plan to be correct?\n- Is any tradeoff for efficiency (e.g. not retrieving at every step, retrieving only once every k steps) possible?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The proposed approach shows strong performance across all evaluated tasks.\n- The idea of training as growing a database of retrievable knowledge is interesting, and salient for LLM agents, which are particularly effective in retrieval-augmented usage, and cannot easily be finetuned. This is also related to the idea of episodic memory in cognitive science, which is an interesting connection.  \n- The components of the proposed approach, including the curation approaches and multi key retrieval method, are well designed.\n- The method appears to make only minor task-specific modifications to ReAct, making it not overly complicated, and generally applicable.\n\nWeaknesses\n- The method appears computationally expensive, especially when maintaining N(x2, when using both curation approaches together) databases, and training over hundreds or thousands of examples. 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.  \n- 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. \n- The results are limited to GPT4o-mini, limiting generalizability.", "was_revised": true, "final_justification": "The paper proposes a simple but effective method for learning as trajectory accumulation, which takes a different approach to many other agents in this domain, which focus on complex agent scaffolds with hand-crafted exemplars. It is likely that approaches such as the proposed method will likely scale better with increasingly more capable models, which makes the paper's contribution meaningful.\n\nMy main concern was that the method requires excessive computational costs or unrealistic assumptions about train-test distribution overlap, which the authors have addressed successfully. Assuming that the discussions from rebuttal are fully reflected in the updated draft, I am happy to give it an accept rating.", "rebuttal": "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.\n\n> 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. \n\n**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.\n\n**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.\n\n> Is any tradeoff for efficiency (e.g. not retrieving at every step, retrieving only once every k steps) possible?\n\nRetrieving 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) \n\n> The results are limited to GPT4o-mini, limiting generalizability.\n\nWe 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.\n\n> 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. \n\nYou 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. \n\n> Does the agent see few-shot exemplars aside from the ones it retrieves?\n\nThe 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.\n\n> Can you provide examples of retrieved exemplars? It would be useful to show how the retrieved exemplars collective shape the agent's policy.\n\nWe 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]. \n\n> Is the high level plan fixed once generated? How important is it for the initial plan to be correct?\n\nIn 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.  \n\nWe will incorporate these clarifications and additional results in our revision.\n\n[1] Zhao, Andrew, et al. \"Expel: Llm agents are experiential learners.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 17. 2024."}]

Author rebuttal:

Meta-review: This paper introduces a trajectory bootstrapping and exemplar curation framework for improving large language model (LLM) agents on sequential decision-making tasks. The central idea is to iteratively collect and curate successful self-generated trajectories, forming a database that can be retrieved and reused as in-context exemplars. Two complementary curation strategies are proposed: DB-level curation, which optimizes the quality of the stored database, and exemplar-level curation, which selects exemplars based on empirical utility. This paper provides a simple and general mechanism for improving LLM agents without requiring domain-specific knowledge. It also provides thorough and systematic experimental evaluation, including extensive ablations and results across multiple benchmarks. Overall, I believe this paper makes a valuable empirical and practical contribution to the field. It proposes a simple yet effective framework for leveraging successful trajectories in sequential decision-making, with strong results supported by rigorous ablation studies. The framing around trajectory bootstrapping and curation is intuitive and potentially impactful for future LLM agent research. I recommend acceptance.
Decision: Accept (poster)