Firefly: Explore Real APIs First, Then Generate Verifiable Tool-Call Tasks for RL

Background: The Trilemma of Tool-Calling Training Data

Training tool-calling agents via reinforcement learning (RL) requires thousands of tasks with correct intermediate tool calls and verifiable final answers. Existing benchmarks provide only dozens to hundreds of tasks. Three mainstream data-construction approaches each miss one critical property:

Human annotation (e.g., Tau-Bench, API-Bank) yields natural, correct tasks but is expensive ($200–$2,000 per RL task) and limited in scale (50–500 tasks per domain).

Pure simulation lets an LLM play both user and tool, enabling scale but deviating from real API behavior (field formats, edge cases, errors).

Forward generation uses real tools: an LLM writes a task, then a solver rolls out a trajectory whose answer becomes ground truth. This fails because the task may be unsolvable with the real API, or the solver may make mistakes that are baked in as ground truth.

Even with verifiable tasks, environment drift (changing API outputs, server downtime, rate limits) makes live RL training unreproducible.

Core Idea: Back-Chaining – Explore First, Ask Later

Firefly reverses the order: a strong LLM first explores real MCP servers , observes actual tool outputs, and only then writes a task around those observed results. This guarantees ground-truth correctness by construction.

Which domain was registered first, amazon.com or netflix.com, and how many years apart were they registered?

In forward generation the question is invented before knowing tool outputs. In Firefly, the LLM first calls whois for both domains, sees registration years 1994 and 1997, then writes the question and extracts ground truth from the observed responses.

Firefly Pipeline

3.1 Server Collection

From ~3,000 servers in the Smithery registry, 900 exposing at least one tool were filtered by four criteria: statelessness, no user authentication, schema clarity, non-triviality. Result: 240 servers, 993 tools .

3.2 Tool Graph: Weak Semantic Prior

To guide exploration in a 993-tool space, a directed Tool Graph was built. An LLM judged pairwise compatibility (output of tool A → input of tool B) from descriptions and schemas, labeling edges high/medium/low confidence. The graph contains ~83K edges (avg 88 successors per tool), 64K at medium+ confidence, including cross-server edges. It does not dictate tasks but steers exploration toward semantically plausible neighborhoods.

3.3 DAG Exploration on Live Servers

Starting from a tool with ≥2 high-confidence successors, an LLM interactively builds a tool-call DAG on live servers. At each step it receives a random subset of successors in the graph and can fan-out (parallel calls), sequence (single successor), or fan-in (merge multiple outputs). Every node records tool name, input parameters, and actual output. Exploration stops when tool-call budget is exhausted or no successors remain. These DAGs become raw material for task synthesis and simulator indexing.

3.4 Back-Chaining Task Synthesis & Validation

For each DAG, the LLM selects a subset of nodes, writes a natural-language task that includes information needed to fill tool-call parameters, and extracts ground truth directly from the chosen nodes' outputs. Remaining nodes serve as distractors. Each task gets a structured Answer Schema (JSON template with named placeholders) and a natural-language Answer Template for automatic field-level evaluation.

An LLM Judge validates each task-trajectory pair on five dimensions: Verifiability, Well-Specifiedness, Interpretability, Realism (≥5/10), Difficulty Calibration. ~50% of candidates are filtered out.

3.5 Retrieval-Augmented Tool-Call Simulator

To eliminate environment drift, every tool call observed during exploration (tool name, input, output) is cached. During RL, the simulator replaces live servers with a three-layer strategy:

Exact Match : hash input parameters → return cached real output.

Fuzzy Match with LLM Generation : retrieve top-k most similar historical calls (prioritizing the task's ground-truth trajectory), then condition an LLM on those real outputs to select or generate a response.

No Data : if the tool has no cached calls, return an error.

The conservative third layer ensures that only calls near the known solution path receive realistic responses. The simulator provides reproducibility (identical outputs on every run) and verifiability (ground-truth derivation always resolvable via Exact Match). RL reward is binary: exact field-level match against Answer Schema, falling back to LLM Judge for semantic equivalence.

Firefly Dataset Statistics

Source: ~3,000 Smithery servers → 240 servers, 993 tools.

Exploration produced 9,749 DAG trajectories .

Back-chaining synthesized 9,275 candidate tasks ; 5,144 passed all quality checks .

Split: 200 held-out test, 4,944 train.

Task difficulty: easy 19.5%, medium 77.0%, hard 3.5%.

Ground-truth trajectories average 3.0 tool calls (range 1–10); Answer Schema averages 4.6 fields .

38.5% of tasks require cross-server tool composition (test set covers 98 servers, 221 tools).

LLM Judge realism score: 7.8/10 .

Simulator coverage during training: 42.2% Exact Match, 57.8% Fuzzy Match, 0% No Data .

Generation cost: Claude Sonnet 4.5 via AWS Bedrock batch inference, ~23.5B tokens (21.4B in, 2.0B out), ~$47K (one-time; dataset and simulator enable unlimited offline RL).

Experiments

5.1 Firefly Test Set: 4B Model Matches Claude Sonnet 4.6

Base model: Qwen3-4B-Thinking-2507 . RL with GRPO + Dynamic Filtering (8 rollouts per prompt; prompts with 8/8 correct removed, all-wrong retained). 300 steps on 16 GPUs (actor) + 16 GPUs (async rollout) using Slime framework.

Pass@1: 28.1% → 41.5% (+13.4 pts), comparable to Claude Sonnet 4.6 (42.2%) .

Pass@8: 52.8% > Claude Sonnet 4.6 (50.3%), near Claude Opus 4.7 (54.4%) .

Pass@16: 57.0% ≈ Claude Opus 4.7 (57.0%).

Training curves show steady improvement across all k. The modest gap between pass@16 (57.0%) and pass@1 (41.5%) suggests some hard tasks exceed the 4B model's capacity.

5.2 Transfer to Public Benchmarks

Firefly RL improves performance on all evaluated public benchmarks (API-Bank, Tau2-Bench, MCPMark, MCP-Atlas, etc.), despite distribution shifts (multi-turn in Tau2-Bench vs. single-turn multi-step in Firefly). Gains vary; Tau2-Bench Telecom shows limited improvement. Consistent positive transfer indicates the model learns generalizable tool-use skills: tool selection, parameter filling from observations, chaining intermediate outputs, deriving answers from structured responses. Notably, single-turn multi-step training benefits multi-turn scenarios because core difficulties (tool selection, state tracking, API grounding, multi-step reasoning) overlap.

Future Directions

6.1 Multi-Turn Back-Chaining

Extend back-chaining to multi-turn dialogues: split a DAG into stages, each corresponding to a user turn, while keeping every turn verifiable. Incorporate clarification and correction patterns.

6.2 Scaling to Larger Models

Current 4B model may be near its ceiling on hard tasks (pass@1 vs pass@16 gap). Larger models (30B+) could benefit more from verifiable supervision, raising both pass@1 ceiling and pass@16 coverage. Open question: how should data scale and difficulty distribution co-evolve with model size? (Hard tasks only 3.5% now.)

6.3 Verified-by-Construction as a General Paradigm

Firefly's core is a general recipe: (1) generate observable results in a real environment, (2) construct tasks around those results, (3) cache the environment for reproducible replay. Open challenges: handling stateful/authenticated tools, fidelity of LLM-generated fuzzy responses, applicability to Web Agents, Code Agents, etc.

Conclusion

Firefly demonstrates that reversing the synthesis order—explore real APIs first, then synthesize tasks from observed outcomes—resolves the trilemma of scale, realism, and verifiability. The accompanying Retrieval-Augmented Simulator enables fully offline, reproducible RL. The resulting 5,144-task dataset lifts a 4B model to frontier-model performance on tool-use benchmarks and transfers to diverse public evaluations. The authors release data, simulator, and training code (arXiv:2605.17558, GitHub: https://github.com/leoleoasd/firefly-neurips-2026) to seed further research on verifiable agent learning.