Textual Stochastic Gradient Descent: Discrete Optimization of External Memory for Reasoning Language Agents

While Large Language Models (LLMs) possess strong reasoning capabilities, enabling them to learn continuously from experience without parametric retraining remains an open challenge. Existing Retrieval-Augmented Generation (RAG) approaches typically treat memory as a static or append-only corpus, leading to "memory saturation," where accumulating noise and redundant information degrade performance over time. To address this, we propose an Experience Library Optimization framework that treats the agent's external memory, which we call the experience library, as a learnable parameter under an explicit capacity budget. We introduce Textual Stochastic Gradient Descent (TSGD), a discrete optimization algorithm that refines this library via failure-driven Add, Edit, and Delete operations. TSGD estimates "textual gradients" through self-reflection and uses a dual-verification mechanism to ensure generalization, which prevents overfitting to local errors. Empirical results on MATH and AIME benchmarks show that TSGD achieves state-of-the-art performance, improving accuracy by up to $18.7\%$ over zero-shot baselines and substantially outperforming static RAG, while keeping a compact memory footprint (compressing hundreds of experiences into $\approx 30$ high-utility rules).

Modern AI systems can reason well, but they do not easily learn from their own mistakes. Teaching them something new usually means expensive retraining. A popular alternative is to let the system keep a growing notebook of past examples to consult, but this tends to backfire: the notebook fills up with redundant or misleading entries, and performance gets worse as it grows. We take a different view. Instead of letting this notebook pile up, we treat it as something the system should actively improve, much like studying for an exam by refining your notes rather than just adding more pages. Our method lets the AI add a new note when it fails a problem, correct a note that led it astray, and remove ones that are redundant, all while keeping the notebook small. Every change is double-checked so that it helps on similar future problems, not just the single case at hand. On challenging math competition problems, this approach raises accuracy substantially while shrinking the notebook from hundreds of entries to about thirty well-chosen rules.