LLM agents that improve by remembering past successful runs pile up thousands of stored trajectories. A trajectory is a recorded episode of observations, thoughts and actions, and the agent later pastes one into its prompt as a worked example. Which few hundred to keep, and which one to show for a new task, are usually decided by text similarity or by a per-trajectory quality score. Case-based reasoning learned decades ago that this is the wrong question. A stored case is useful because of the set of new problems it can be adapted to solve within a cost budget, which the old literature calls its functional neighborhood. Looking similar on the surface is not the same thing. Once neighborhoods are known, choosing a small library becomes a maximum-coverage problem. That problem is NP-hard, but the greedy algorithm provably recovers at least 63% of the optimal coverage.
We propose to bring this idea to LLM agents and to fix the step that made it impractical: actually measuring neighborhoods. The plan has three parts. We run the agent on a small random sample of (stored trajectory, task) pairs and record whether it succeeds within a step budget. From those probes we learn a predictor of "will this trajectory get this task solved." We then use that single predictor twice, first as the objective for greedy library selection and then as the retrieval score at test time. The claim is that a library chosen and indexed by predicted adaptation success beats libraries curated by per-item quality or by semantic diversity. We expect the gap to be largest at small library sizes, and the method only needs to observe a few percent of the pairwise matrix.
Core Claim and What Is New
Classical case-addition policies, introduced in Remembering to Add and extended in A Case‐Addition Policy for Case‐Base Maintenance, already do greedy coverage over adaptation-bounded neighborhoods. They proved NP-completeness and the $(1-1/e)$ guarantee, and they reached full competence on Towers of Hanoi with 58 cases where 200 random cases did not. These papers supply our method. They differ from this proposal in two ways. First, they assume neighborhoods are given or computed exhaustively at $O(n^2)$ cost. Second, their adaptation is a symbolic planner, not a stochastic language model. For an LLM agent each matrix entry costs a full environment rollout, so the exhaustive matrix is the bottleneck, not the greedy step.
The closest modern work, Self-Generated In-Context Examples Improve LLM Agents, curates trajectories with a per-trajectory value $Q(\tau)$ built from downstream success. It raised ALFWorld success from 73% to 93%. $Q(\tau)$ scores each item alone, so two excellent trajectories that help the same tasks both survive while tasks nobody helps stay uncovered. Our objective is set-level. It also asks which tasks each trajectory helps, not how often it helps on average.
Concretely, let $T$ be a pool of training tasks with weights $p(t)$ and $V$ the stored trajectories. Let $\hat P(t,v)$ be the predicted probability that the agent solves task $t$ within $B$ steps when shown trajectory $v$. We select a library $S \subseteq V$ with $|S|\le k$ by maximizing
$$f(S) = \sum_{t \in T} p(t)\, \max\Big(\hat P_0(t),\ \max_{v \in S} \hat P(t,v)\Big),$$
where $\hat P_0(t)$ is the predicted success with no exemplar. This is a facility-location function: monotone and submodular, so greedy keeps the $(1-1/e)$ guarantee. The inner max is also exactly the retrieval rule used at deployment, so selection and retrieval share one notion of similarity.
This deliberately inherits the lesson of Case-Based Similarity Assessment. There, estimating adaptability from stored adaptation experience cut DIAL's adaptation effort from 65 to 36 memory operations compared with semantic similarity. That paper did no subset selection, and our proposal adds it.
Research Program
The first component is a probing and prediction stage. We collect a trajectory pool $V$ by running a base ReAct agent on training tasks in ALFWorld (ALFWorld), InterCode-SQL (InterCode) and Wordcraft, the three environments of the self-generated-examples work. We then spend a fixed rollout budget on random (task, trajectory) pairs and record success and steps used.
The predictor combines two signals. One is a low-rank factorization of the sparse success matrix, which captures "this trajectory helps this family of tasks." The other is a small model over embeddings of the task goal and the trajectory's high-level plan, which handles tasks and trajectories with few observed entries. Rollout outcomes are noisy, so we repeat a small subset of pairs to calibrate $\hat P$.
The second component is active refinement. Greedy facility location only cares about entries that could change the argmax, so a second probing round targets pairs where the current top choice for a task is uncertain. We will measure how much of the full-matrix selection quality is recovered as a function of the fraction of pairs probed. This is the practical question that the batch-only maintenance literature left open.
The third component is analysis that tests the case-based reasoning thesis directly in LLM agents. On a subset of ALFWorld we compute the full success matrix. We report how well embedding cosine similarity rank-correlates with observed adaptation success. We also report how often the most semantically similar trajectory makes the agent worse than having no exemplar. SkillAligner observed a related regression of 17.91% under semantic skill retrieval.
Baselines
The naive reference is no exemplar at all, together with uncurated top-$m$ dense retrieval over the full pool. This measures whether curation matters at all.
The strongest existing method is the $Q(\tau)$ curation with multi-key retrieval from Self-Generated In-Context Examples Improve LLM Agents. It reports success rising from 73% to 93% on ALFWorld, from 75% to 82% on InterCode-SQL, and from 55% to 72% on Wordcraft. It is the strongest competitor because it already uses downstream success and is tuned for these exact environments. We will reimplement it on the same agent model and the same trajectory pool. The fairness rule is that it receives the same total number of environment rollouts our method spends on probing, used to accumulate more retrieval history for its $Q$ estimates. Beating it means higher held-out test success at equal library size $k$ and equal rollout budget, across three seeds. We expect clear gains at small $k$, roughly 10–50 trajectories, and at least parity at the largest $k$. The published 93% is a reference point only: our reimplementation number is the one we compare against.
The semantic coreset baseline is greedy facility location over sentence embeddings, and separately the diversity-plus-representativeness selector of PaCS-ICL. PaCS-ICL reports a +3.2% to +3.6% gain over baselines on classification-style in-context learning with 18 examples. No reported result was found on Lacuna for PaCS-ICL on ALFWorld or any agent benchmark. Both semantic selectors will use the same $k$ and the same retriever as the other arms.
The maintenance baseline is the adaptation-guided ranking from Adaptation-Guided Case Base Maintenance, adapted from regression. Cases are ranked by leave-one-out benefit and then filtered by condensed nearest neighbor. It reports over 38% improvement over random deletion on Computer Hardware at 10 cases.
The key ablations form a two-by-two design. Selection is either predicted coverage or $Q(\tau)$, and retrieval is either the learned predictor or embedding similarity. This separates the value of choosing the library well from the value of indexing it well. A further ablation replaces $\hat P$ with the exhaustively measured matrix on the ALFWorld subset, which gives an upper bound on what estimation error costs.
Why not just…?
Why not just keep the highest-$Q(\tau)$ trajectories? This is the real threat. If trajectory usefulness is roughly one-dimensional, with some trajectories simply better for everything, then ranking by $Q$ and covering tasks coincide. The full-matrix analysis settles it. If the success matrix is nearly rank-one, our method should tie $Q(\tau)$, and we would report that the redundancy argument fails for these agents. If the matrix has task-family structure, covering task families should beat the per-item ranking at small $k$. The selection ablation measures this directly.
Why not just cluster trajectories by embeddings and keep medoids? The selection literature argues that surface proxies can be arbitrarily far from downstream usefulness without structural priors (Tackling Provably Hard Representative Selection). The case-based reasoning evidence above shows the same misalignment in practice. That argument is worst-case and comes from other domains, though. Our correlation study and the semantic-coreset baseline test whether it holds for LLM agents, where embeddings of task goals may in fact track adaptability well.
Why not just store everything and retrieve at test time? The self-generated-examples work reports that naive accumulation hits diminishing returns. Storing everything also does not fix retrieval by surface similarity, which is where SkillAligner's regressions arise. The uncurated arm with learned retrieval isolates this. If storing everything plus our predictor as retriever matches the curated library, then the selection half of the proposal is unnecessary. We would then present the result as learned adaptation-aware retrieval and drop the coverage claim.
Why not just repair the retrieved trajectory at execution time, as SkillAligner does? Execution-time repair and library selection are complementary rather than competing. We will run SkillAligner-style alignment on top of each library to check whether the gains add up or whether repair erases differences between libraries.
Decisive Checks
The proposal stands if three things hold. On held-out tasks in all three environments, predicted-coverage selection with learned retrieval beats the reimplemented $Q(\tau)$ curation at equal $k$ and equal rollout budget. Probing about 5% of pairs recovers most of the full-matrix gain on the ALFWorld subset. The two-by-two ablation shows that selection contributes beyond retrieval.
It fails, informatively, under either of two outcomes. A near-rank-one success matrix would mean usefulness is not task-specific. A near-perfect correlation between embedding similarity and adaptation success would mean the classical similarity-adaptability gap does not carry over to language-model agents. Either outcome is worth reporting.
References
- Remembering to Add: Competence-preserving Case-Addition Policies for Case- Base Maintenance
- A Case‐Addition Policy for Case‐Base Maintenance
- Self-Generated In-Context Examples Improve LLM Agents for Sequential Decision-Making Tasks
- Case-Based Similarity Assessment: Estimating Adaptability from Experience
- ALFWorld: Aligning Text and Embodied Environments for Interactive Learning
- InterCode: Standardizing and Benchmarking Interactive Coding with Execution Feedback
- SkillAligner: Treating Retrieved Skills as Adaptable Drafts at Execution Time
- Unsupervised Process-Aware Coreset Selection for In-Context Learning
- Adaptation-Guided Case Base Maintenance
- Tackling Provably Hard Representative Selection via Graph Neural Networks