FitText: Evolving Agent Tool Ecologies via Memetic Retrieval

2026/05/31 by Kyle Zheng, Han Zhang, Renliang Sun +2
Computer Science · #cs.AI #cs.IR #cs.LG #cs.MA

paper · pdf · doi:10.48550/arxiv.2605.02411

Accepted to the COLM 2026 main conference. 30 pages, including appendices

arxiv created 2026/07/31 · arxiv updated 2026/08/04

Abstract

Efficient reasoning is not only a matter of shortening an answer trace; for tool-using agents, it also depends on whether the agent is reasoning over the right action space. As API ecosystems scale to tens of thousands of endpoints, the semantic gap between user requests and tool documentation makes this problem concrete: static retrieval from the initial query can fail before planning begins, and stronger planning alone cannot recover a missing tool. We study this problem as budgeted test-time retrieval and introduce FitText, a training-free framework that makes the tool interface revisable during execution by generating, refining, and evolving natural-language pseudo-tool descriptions as retrieval probes. FitText supports serial refinement, parallel exploration, and Memetic Retrieval, which adds evolutionary selection, local refinement, and tool memory to avoid redundant search. On StableToolBench (16,464 APIs), Memetic FitText reaches an 84.3% pooled pass rate, improving +26.7 points over static retrieval, +22.2 over Single-Pass, +23.2 over Re-Invoke, and +27.5 over Xu-style root refinement. It leads on every evaluated current model, with gains growing alongside model capability, and produces the largest improvements on ambiguous multi-tool tasks where dynamic re-retrieval restores correct candidates after early mistakes. At 40-way concurrency, parallel population execution keeps batched wall-clock at 1.01x Single-Pass despite the added search work.

Citations

• Large Language Model Reasoning Failures
• DeepAgent: A General Reasoning Agent with Scalable Toolsets
• ToolDreamer: Instilling LLM Reasoning Into Tool Retrievers
• Exploring Solution Divergence and Its Effect on Large Language Model Problem Solving
• The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs
• Self-Guided Function Calling in Large Language Models via Stepwise Experience Recall
• Tool Graph Retriever: Exploring Dependency Graph-based Tool Retrieval for Large Language Models
• GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning
• AlphaEvolve: A coding agent for scientific and algorithmic discovery
• Dynamic Cheatsheet: Test-Time Learning with Adaptive Memory
• Retrieval Models Aren't Tool-Savvy: Benchmarking Tool Retrieval for Large Language Models
• A Survey of Automatic Prompt Engineering: An Optimization Perspective
• The Danger of Overthinking: Examining the Reasoning-Action Dilemma in Agentic Tasks
• DMQR-RAG: Diverse Multi-Query Rewriting for RAG
• ToolGen: Unified Tool Retrieval and Calling via Generation
• Efficient and Scalable Estimation of Tool Representations in Vector Space
• Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
• Re-Invoke: Tool Invocation Rewriting for Zero-Shot Tool Retrieval
• Enhancing Tool Retrieval with Iterative Feedback from Large Language Models
• Advancing Tool-Augmented Large Language Models: Integrating Insights from Errors in Inference Trees
• Tool-Planner: Task Planning with Clusters across Multiple Tools
• StableToolBench: Towards Stable Large-Scale Benchmarking on Tool Learning of Large Language Models
• Corpus-Steered Query Expansion with Large Language Models
• SEE: Strategic Exploration and Exploitation for Cohesive In-Context Prompt Optimization
• Large Language Models: A Survey
• AnyTool: Self-Reflective, Hierarchical Agents for Large-Scale API Calls
• Understanding the planning of LLM agents: A survey
• Executable Code Actions Elicit Better LLM Agents
• ControlLLM: Augment Language Models with Tools by Searching on Graphs
• ToolChain*: Efficient Action Space Navigation in Large Language Models with A* Search
• MetaTool Benchmark for Large Language Models: Deciding Whether to Use Tools and Which to Use
• EvoPrompt: Connecting LLMs with Evolutionary Algorithms Yields Powerful Prompt Optimizers
• Large Language Models as Optimizers
• Counterfactually Auditable Lifecycle Certification for Autonomous Agents
• RestGPT: Connecting Large Language Models with Real-World RESTful APIs
• Gorilla: Large Language Model Connected with Massive APIs
• Tree of Thoughts: Deliberate Problem Solving with Large Language Models
• Tool Learning with Foundation Models
• Self-Refine: Iterative Refinement with Self-Feedback
• Reflexion: Language Agents with Verbal Reinforcement Learning
• ART: Automatic multi-step reasoning and tool-use for large language models
• Query2doc: Query Expansion with Large Language Models
• Toolformer: Language Models Can Teach Themselves to Use Tools
• Precise Zero-Shot Dense Retrieval without Relevance Labels
• Task-aware Retrieval with Instructions
• Distributing Accountability, Not Capability: Phase Separation and the LLM Workflow Quadrant in Autonomous AI Agent Architectures
• Self-Consistency Improves Chain of Thought Reasoning in Language Models
• WebGPT: Browser-assisted question-answering with human feedback
• SimCSE: Simple Contrastive Learning of Sentence Embeddings
• SimCSE: Simple Contrastive Learning of Sentence Embeddings
• A STATISTICAL INTERPRETATION OF TERM SPECIFICITY AND ITS APPLICATION IN RETRIEVAL
• Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
• HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face