FitText: Evolving Agent Tool Ecologies via Memetic Retrieval

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.