🤖 AI

FitText: Evolving Agent Tool Ecologies via Memetic Retrieval

FitText is a training-free framework that bridges the semantic gap between user tasks and API documentation by embedding dynamic, evolutionary "Memetic Retrieval" into an agent's reasoning loop, significantly improving tool selection accuracy across diverse benchmarks compared to static retrieval methods.

Original authors: Kyle Zheng, Han Zhang, Renliang Sun, Chenchen Ye, Wei Wang

Published 2026-05-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Kyle Zheng, Han Zhang, Renliang Sun, Chenchen Ye, Wei Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Lost in Translation" Moment

Imagine you are a highly intelligent robot (an AI agent) trying to fix a complex problem, like getting a refund for a cancelled flight. You have a massive library of tools (APIs) available to you—thousands of them, like "Check Flight Status," "Issue Refund," or "Call Customer Service."

The problem is a language gap.

You (the User) say: "My flight was cancelled, help me get my money back." (This is high-level and emotional).
The Tools are described like: "Process a refund for eligible booking ID." (This is technical and rigid).

If you just ask the library for tools based on your exact words, you might get the wrong ones. The old way of doing this was to pick a few tools at the very start and stick with them. But as the robot thinks through the problem, it realizes, "Wait, I need to check the ticket rules before I can ask for a refund." The old tools don't fit anymore, but the robot is stuck with them.

The Solution: FitText (The "Hypothetical Tool" Generator)

The authors introduce FitText, a new way for the robot to find the right tools while it is thinking. Instead of just searching for the tools, the robot first writes a fake description of the tool it thinks it needs.

Think of this like a translator or a sketch artist.

The Sketch: The robot looks at your request ("I need a refund") and draws a rough sketch of the tool it needs: "A tool that checks if a flight is cancelled and finds the booking ID."
The Search: It uses this sketch to search the library. Because the sketch sounds more like the tool descriptions than your original sentence did, it finds better matches.
The Feedback Loop: Once it finds some tools, it looks at them. "Oh, I see the real tools are called 'CheckFlightStatus' and 'FindBookingInfo'." It then updates its sketch to match the real tools better and searches again.

The Four Strategies (From Simple to Super-Organic)

The paper tests four different ways to use this "sketching" method, ranging from simple to complex:

Single-Pass (The One-Shot): The robot draws one sketch, searches once, and hopes for the best. It's fast but might miss the mark.
Multi-Turn Refinement (The Polishing): The robot draws a sketch, finds some tools, sees what they look like, and then redraws the sketch to be more accurate. It does this a few times, slowly polishing the description until it fits perfectly.
Scattershot (The Crowd-Sourcing): Instead of drawing one sketch, the robot draws many different sketches at once (e.g., "Maybe I need a tool for checking status?" and "Maybe I need a tool for finding the ticket number?"). It searches for all of them and combines the best results. This is great for when the robot isn't sure what it needs.
Memetic Retrieval (The Evolutionary Garden): This is the paper's star feature. It treats the sketches like plants in a garden.
- Generation: The robot creates a population of different sketches.
- Selection: It checks which sketches find the best tools. The "fittest" sketches survive; the bad ones are thrown out.
- Crossover & Mutation: It takes two good sketches and "breeds" them together (mixing their ideas) or slightly mutates them (changing a word) to see if a new, better sketch emerges.
- Memory: It keeps a list of what it has already tried so it doesn't waste time searching the same dead ends again.

This "Memetic" approach is like natural selection. Over a few rounds of "generations," the population of sketches evolves to become perfectly tuned to find the exact tools needed, even for very confusing tasks.

The Results: What Worked?

The team tested this on two huge datasets containing tens of thousands of tools.

The Win: FitText, especially the Memetic strategy, was a huge success. It found the right tools much more often than the old methods.
- On one test, it improved the ranking of the correct tool from being 8th place down to 2nd place.
- On another test, it increased the success rate of completing tasks by 24 percentage points.
The Catch (The "Brain" Requirement): The paper found a crucial limit. This evolutionary "breeding" of sketches only works if the robot's brain (the base AI model) is smart enough to understand the nuances of the sketches.
- With a smart model, the evolutionary process refines the signal and finds the right tools.
- With a weaker model, the evolutionary process amplifies noise. It's like trying to breed a better race car, but the mechanic is bad at fixing engines; the "offspring" just get worse and worse. The paper notes that for this method to work, you need a capable "semantic operator" (a smart AI) to do the breeding.

Summary Analogy

Imagine you are looking for a specific, rare book in a library with 50,000 books, but you only know the feeling of the story, not the title.

Old Way: You ask the librarian, "Do you have a book about a sad flight?" The librarian gives you a list of books with "flight" in the title, but none are about refunds. You give up.
FitText (Memetic): You write a fake book blurb: "A story about a cancelled trip and getting money back." You ask the librarian. They show you a few books. You realize the library uses specific terms like "Travel Voucher." You rewrite your blurb to match those terms. You do this again, mixing and matching ideas from the books you found, until you write a blurb that is so perfect the librarian hands you the exact book you need immediately.

The paper proves that by letting the AI "evolve" its own search queries in real-time, it can navigate massive tool ecosystems much better than before.

Technical Summary: FitText – Evolving Agent Tool Ecologies via Memetic Retrieval

1. Problem Statement

Large Language Model (LLM) agents face a fundamental "semantic gap" between how users describe tasks (high-level, goal-oriented queries) and how tools are documented (functional, parameter-heavy descriptions). As API ecosystems scale to tens of thousands of endpoints, static retrieval methods fail to bridge this gap. Existing paradigms suffer from two critical limitations:

Schema Injection: Providing a fixed, manually curated set of tools leads to context rot and is infeasible for large-scale ecosystems.
Static Root-Query Retrieval: Selecting tools once based on the initial query is brittle because user intent is often amorphous and evolves during execution. Agents frequently discover the need for new tools only after reasoning through intermediate steps, but static retrieval cannot adapt to this evolving context.

Furthermore, standard embedding models trained for general semantic matching often fail to align task intent with specific tool metadata, particularly in stochastic environments where available functionality cannot be anticipated at query time.

2. Methodology: FitText Framework

The authors propose FitText, a training-free framework that embeds dynamic tool retrieval directly into the agent's reasoning loop. Instead of retrieving tools based on the raw user query, the LLM generates pseudo-tool descriptions—natural language hypotheses of the needed functionality. These descriptions serve as retrieval probes that bridge the semantic gap between user intent and tool documentation.

The framework is instantiated as a spectrum of strategies, ranging from fast to thorough:

Single-Pass Retrieval: The LLM generates one initial pseudo-tool description ( $d_0$ ) which is used for a single retrieval step. This establishes the baseline benefit of operating in a semantic space closer to tool documentation than the raw query.
Multi-Turn Refinement: Drawing on iterative self-refinement, this strategy uses retrieval feedback to progressively improve the description. After retrieving a set of tools, the agent uses exemplar tool descriptions (blurbs) to refine its hypothesis ( $d_t$ ) in subsequent turns, grounding the generation in the actual vocabulary and structure of the tool corpus.
Scattershot Retrieval: To overcome the single-trajectory limitation of refinement, this approach generates a diverse population of pseudo-tool descriptions in parallel (using high temperature sampling). It aggregates retrieval results via hierarchical voting (based on vote count, mean rank, and similarity), ensuring tools consistently retrieved across diverse hypotheses are prioritized.
Memetic Retrieval: This is the core evolutionary strategy. It treats pseudo-tool descriptions as "memes" in a cultural evolution loop.
- Population & Selection: It maintains a population of competing hypotheses. Fitness is determined by retrieval quality (semantic similarity) minus a penalty for redundancy with previously explored tool sets (stored in a Tool Memory).
- Evolutionary Operators: The LLM acts as a semantic evolutionary operator, performing crossover (combining constraints/intent from two parents) and mutation (adjusting wording while preserving intent) at the meaning level rather than token level.
- Local Search: Offspring undergo refinement using retrieval feedback before the next generation.
- Tool Memory: A persistent memory stores previously retrieved tool sets to suppress redundant search, acting as a soft taboo against revisiting explored regions of the tool ecology.

3. Key Contributions

FitText Framework: A training-free, model-agnostic approach that reframes tool retrieval as an exploration over a heterogeneous tool ecology. It dynamically generates and refines pseudo-tool descriptions as the agent's understanding of the task evolves.
Memetic Retrieval: An evolutionary loop incorporating crossover, mutation, fitness-driven selection, and a tool memory. It achieves state-of-the-art performance on ambiguous, multi-tool tasks where deterministic retrieval fails.
Empirical Insight on Bottlenecks: The authors demonstrate that retrieval quality, not planning capability, is the binding constraint on end-to-end agent performance. Scaling the analysis model (retriever) yields significant gains, whereas scaling the planner does not.
Base Model Contingency: The paper identifies that memetic search is contingent on the base model's capacity. Under weaker models, evolutionary search amplifies noise rather than refining signal, effectively inverting the benefits seen with frontier models.

4. Experimental Results

The framework was evaluated on ToolRet (43k tools, 4 domains) and StableToolBench (16,464 APIs).

Retrieval Performance (ToolRet):
- FitText significantly improves average retrieval rank compared to static query retrieval (8.81).
- Memetic Retrieval achieved the best average rank of 2.78 using GPT-4.1-mini.
- All LLM-guided strategies outperformed static retrieval across all metrics (NDCG@5, Precision@5, Recall@5).
End-to-End Performance (StableToolBench):
- Memetic Retrieval achieved an average pass rate of 0.73, a 24-point absolute gain over static query retrieval (0.49).
- Gains were most pronounced on complex, multi-tool tasks (G2 and G3 subsets), where Memetic improved pass rates by 22–34 points over static baselines.
Ablation Findings:
- Refinement Depth: Single-trajectory refinement (Multi-Turn) shows diminishing returns beyond the first turn, motivating population-based strategies.
- Model Dependency: When using a weaker base model (Qwen3-30B), Memetic Retrieval collapsed (pass rate dropped to ~32%, below static retrieval). This confirms that evolutionary search requires a base model capable of acting as a competent semantic operator; otherwise, diversity generation amplifies noise.

5. Significance and Claims

The paper claims that adaptive, in-loop retrieval is a general-purpose interface for evolving tool ecosystems. By treating tool discovery as an exploration process rather than a static lookup, FitText allows agents to adaptively narrow large tool spaces without task-specific training.

The authors emphasize that the "semantic gap" is the primary barrier to effective tool use, and bridging it via pseudo-tool generation is more effective than improving planning alone. Furthermore, the work highlights a critical prerequisite for evolutionary tool exploration: the base LLM must possess sufficient semantic reasoning capacity to act as a valid evolutionary operator. Without this capacity, the complexity of memetic search becomes a liability rather than an asset.

The framework is presented as modular and orthogonal to advances in agentic planning, serving as a plug-and-play capability that enhances the robustness of tool-augmented agents in open-domain, large-scale API environments.