mlsanityData to 14 Oct 2026

Scaling Textual Gradients via Sampling-Based Momentum

arXiv 2506.00400 ↗First posted 31 May 2025cs.CL cs.AIcited by 6

Not on the map. Why?

Abstract (arXiv)

LLM-based prompt optimization, which uses LLM-provided ``textual gradients'' (feedback) to refine prompts, has emerged as an effective method for automatic prompt engineering. However, its scalability and stability are unclear when using more data in training. We systematically investigate the potential and challenges of scaling training data in textual gradient descent. We show that naively scaling training examples is infeasible due to both explicit context-length limits and an implicit context wall, where long-context degradation yields diminishing returns. Inspired by prior wisdom in stochastic gradient descent, we propose Textual Stochastic Gradient Descent with Momentum (TSGD-M), which reweights updates through momentum sampling, using bootstrapped minibatch validation accuracy as importance weights over historical prompts. To stabilize TSGD and enable effective scaling within a limited context window, TSGD-M carries prior prompts information by textitdynamically exploring the past top performing prompts without expanding input context length. TSGD-M integrates seamlessly into existing prompt optimization frameworks, including TextGrad, DSPy-COPRO, and AdalFlow, and achieves consistent gains across 6 benchmarks.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 57 of its 90 references that are in the map. First posted on arXiv 31 May 2025.

Builds on

57 of 90 references.

References · 57

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2022Training language models to follow instructions with human feedbackcited by 15,971
  4. 2024The Llama 3 Herd of Modelscited by 14,715
  5. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  6. 2020Scaling Laws for Neural Language Modelscited by 6,586
  7. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  8. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,886
  9. 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
  10. 2018HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answeringcited by 3,754
  11. 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,455
  12. 2022Training Compute-Optimal Large Language Modelscited by 3,019
38 more
  1. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  2. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,986
  3. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Themcited by 1,807
  4. 2025s1: Simple test-time scalingcited by 1,341
  5. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,141
  6. 2021Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivitycited by 1,135
  7. 2022Large Language Models Are Human-Level Prompt Engineerscited by 1,045
  8. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
  9. 2023Large Language Models as Optimizerscited by 864
  10. 2023Quantifying Language Models' Sensitivity to Spurious Features in Prompt Design or: How I learned to start worrying about prompt formattingcited by 817
  11. 2023Automatic Prompt Optimization with "Gradient Descent" and Beam Searchcited by 653
  12. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 501
  13. 2024Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programscited by 291
  14. 2024TextGrad: Automatic "Differentiation" via Textcited by 273
  15. 2023PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimizationcited by 233
  16. 2023Large Language Model as Attributed Training Data Generator: A Tale of Diversity and Biascited by 232
  17. 2018A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decaycited by 226
  18. 2024BABILong: Testing the Limits of LLMs with Long Context Reasoning-in-a-Haystackcited by 215
  19. 2019Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacementcited by 211
  20. 2024Many-Shot In-Context Learningcited by 206
  21. 2024The Effect of Sampling Temperature on Problem Solving in Large Language Modelscited by 170
  22. 2024Same Task, More Tokens: the Impact of Input Length on the Reasoning Performance of Large Language Modelscited by 152
  23. 2014A* Samplingcited by 151
  24. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 119
  25. 2024InternLM-Math: Open Math Large Language Models Toward Verifiable Reasoningcited by 119
  26. 2025Multi-Agent Design: Optimizing Agents with Better Prompts and Topologiescited by 113
  27. 2025S*: Test Time Scaling for Code Generationcited by 98
  28. 2023Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generationcited by 96
  29. 2022Structured Prompting: Scaling In-Context Learning to 1,000 Examplescited by 81
  30. 2024Differentially Private Synthetic Data via Foundation Model APIs 2: Textcited by 76
  31. 2024Uncertainty Estimation and Quantification for LLMs: A Simple Supervised Approachcited by 76
  32. 2019Learning to Few-Shot Learn Across Diverse Natural Language Classification Taskscited by 57
  33. 2024Squeezed Attention: Accelerating Long Context Length LLM Inferencecited by 57
  34. 2024Can Long-Context Language Models Subsume Retrieval, RAG, SQL, and More?cited by 56
  35. 2023Cost-Effective Hyperparameter Optimization for Large Language Model Generation Inferencecited by 40
  36. 2023When does In-context Learning Fall Short and Why? A Study on Specification-Heavy Taskscited by 37
  37. 2021Stochastic Batch Acquisition: A Simple Baseline for Deep Active Learningcited by 36
  38. 2024How Susceptible are LLMs to Influence in Prompts?cited by 33

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 5.

6 papers.

  1. 2025Test-Time Policy Adaptation for Enhanced Multi-Turn Interactions with LLMscited by 3
  2. 2026AgentGrad: Intervention-guided Prompt Optimization for Multi Agent Systemscited by 3
  3. 2026HPFA: Hypergraph-Based Paired Failure Attribution for LLM Reasoningcited by 1
  4. 2026The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflowscited by 1
  5. 2026Reflective Context Learning: Studying the Optimization Primitives of Context Spacecited by 0
  6. 2026Trading Strategy Optimization via Textual Gradientcited by 0