ASTRA: Automated Synthesis of agentic Trajectories and Reinforcement Arenas

🍞 Hook: Imagine you’re learning to use a toolbox to fix a bike. If the teacher only tells stories about tools but never lets you touch real wrenches and screws, you won’t become a confident fixer.

🥬 The Concept: Tool-augmented AI agents are language models that can call external tools (like search, calculators, APIs) step by step to solve tasks.

• How it works: 1) Read a user question, 2) Decide which tool to call and with what inputs, 3) Read the tool’s response, 4) Plan the next step, 5) Repeat until done.
• Why it matters: Without tools, many real-world jobs (booking, data lookups, multi-app flows) are too hard or too slow. 🍞 Anchor: Asking “Find the cheapest flight then summarize hotel options” makes the agent call a flight API, then a hotel API, then write a neat answer.

🍞 Hook: You know how chess isn’t just one move; you think ahead across many turns.

🥬 The Concept: Multi-turn decision making means the agent must plan and adapt over several steps, not just one.

• How it works: 1) Make a plan, 2) Take an action, 3) See what happened, 4) Update the plan, 5) Continue until the goal.
• Why it matters: Without multi-turn thinking, the agent can’t fix mistakes or combine info from multiple tools. 🍞 Anchor: To answer “Compare two apartments by price, size, and commute,” the agent needs several calls and adjustments.

🍞 Hook: If your science fair judge changes rules mid-competition and you can’t check them, it’s hard to improve fairly.

🥬 The Concept: Verifiable environments are training worlds where tool behavior, rules, and rewards are code-executable and checkable.

• How it works: 1) Define tools with code, 2) Run tool calls in a sandbox, 3) Compare outputs against ground truth, 4) Give reliable rewards.
• Why it matters: Without verification, rewards can be noisy or wrong, breaking long-horizon reinforcement learning. 🍞 Anchor: A calculator tool returns exact numbers you can re-run; a fuzzy “LLM-simulated” calculator might change answers.

🍞 Hook: Learning from examples is like following a cookbook before you start inventing your own recipes.

🥬 The Concept: Supervised Fine-Tuning (SFT) teaches models from curated examples of good tool use.

• How it works: 1) Build example trajectories, 2) Train the model to mimic them, 3) Get a solid starting policy.
• Why it matters: RL from scratch can flail; SFT gives the model basic coordination so RL can go farther. 🍞 Anchor: Show the model several correct “plan → tool calls → final answer” scripts so it can copy the pattern.

🍞 Hook: Practicing without a coach’s score is like shooting hoops in the dark—you won’t know if you’re improving.

🥬 The Concept: Reinforcement Learning (RL) improves a model by rewarding better sequences of choices.

• How it works: 1) Try a path, 2) Get a score, 3) Adjust policy to favor higher-scoring paths.
• Why it matters: Without real feedback from environments, the model can’t learn robust, long-run strategies. 🍞 Anchor: If an agent makes fewer, smarter tool calls and still solves the task, it earns a higher reward.

The World Before: Many tool-agent training methods relied on LLM-simulated environments. That means an LLM pretended to be every tool and every rule. It was scalable but not guaranteed correct. Rewards became unreliable; the same action might get different scores. Other works split multi-turn stories into single steps, losing the “whole-journey” learning signal.

The Problem: Training agents to use tools across long conversations needs two things: (1) lots of realistic, multi-turn tool-use examples (for SFT) and (2) stable, code-verifiable environments (for RL). Most prior pipelines needed manual cleaning or used unverifiable simulators, causing unstable RL and limited long-horizon learning.

Failed Attempts: SFT-only approaches learned style but not adaptation; RL-only approaches started too weak to explore. LLM-only simulators led to reward flicker (inconsistent feedback), so multi-turn policies didn’t stabilize.

The Gap: We needed fully automated data and environment synthesis with verifiable rules, plus a training method that first teaches basics (SFT) and then polishes real skills (RL) with reliable trajectory-level rewards.

Real Stakes: In real apps—customer support, shopping, travel, healthcare info—agents must pick the right tool, handle errors, and combine results across many steps. If they overcall tools, it’s slow and expensive; if they undercall, they fail. Users want trust that the agent’s training was fair, stable, and reproducible. That’s where ASTRA steps in: it automates the making of both the practice stories and the practice worlds, and it proves results by code, not vibes.

🍞 Hook: Imagine teaching a robot chef two things: first, follow solid recipes; second, practice in a real kitchen where timers and ovens work exactly as the manual says.

🥬 The Concept: ASTRA is a two-part, fully automated training system that (1) synthesizes multi-turn tool-use trajectories from real tool-call graphs for SFT, and (2) builds code-executable, rule-verifiable environments from decomposed Q&A for multi-turn RL.

• How it works: 1) Create diverse tool chains from real MCP servers and score their trajectories, 2) Decompose questions into sub-questions with dependencies and implement each as sandboxed tools, 3) Train first with SFT to form a strong base, 4) Then run online RL with a trajectory-level F1 reward, plus irrelevant-tool mixing to learn to choose wisely.
• Why it matters: Without both parts—broad, grounded SFT data and verifiable RL worlds—agents either can’t generalize well or can’t learn stable long-horizon strategies. 🍞 Anchor: First, ASTRA shows the model many “how to use maps + booking APIs together” stories; then it lets the model practice inside a guaranteed-correct mini-world where each tool is real code.

Multiple Analogies:

1. Sports camp: SFT = drills with a playbook; RL = scrimmages on an official field with referees you can trust.
2. Driver’s ed: SFT = classroom lessons with route diagrams; RL = closed-course driving tests with working traffic lights and precise scoring.
3. Orchestra: SFT = sheet music rehearsals; RL = full concert in a tuned hall where acoustics (rules) are known and measurable.

Before vs After:

• Before: Data was often simulated by LLMs; rewards weren’t verifiable; multi-turn learning wobbled; models overfit to clean tool lists; SFT or RL alone wasn’t enough.
• After: ASTRA auto-builds trajectories and verifiable environments; rewards are deterministic; RL can run stably over long horizons; models learn to both act and discriminate tools.

Why It Works (intuition, no equations):

• Trajectory synthesis on real tool-call graphs gives the model a map of what tool sequences exist and how to read tool docs. This forms basic competence.
• Verifiable environments turn learning into a fair game with fixed rules and checkable answers, so RL signals are stable and meaningful.
• F1-style rewards teach the agent to finish the job (recall) while staying efficient (precision), preventing runaway tool spam or fear of calling tools.
• Irrelevant-tool mixing supplies negative examples that look tempting but are wrong, sharpening the model’s judgment.

Building Blocks (each with a sandwich):

• 🍞 Hook: You know how a subway map shows connections between stations. 🥬 The Concept: Tool-call graphs are maps of which tools can follow which, based on docs and schemas.

  • How it works: 1) Normalize tool schemas, 2) Propose chains, 3) Build a graph of transitions, 4) Sample valid walks.
  • Why it matters: Without a map, you might propose nonsense sequences. 🍞 Anchor: Weather → geocoder → events makes sense; weather → payment → DNA doesn’t.

• 🍞 Hook: Breaking a big homework problem into mini-questions makes it easier. 🥬 The Concept: Q&A decomposition turns one main question into sub-questions with dependencies.

  • How it works: 1) Generate sub-QAs, 2) Check atomicity and dependency consistency, 3) Ensure completeness, 4) Merge similar sub-environments.
  • Why it matters: Without precise steps, you can’t build checkable tools or reward partial progress. 🍞 Anchor: “Find best clinic” might split into “nearby clinics,” “insurance coverage,” “ratings,” then combine.

• 🍞 Hook: Getting a ribbon for a whole race, not just one sprint, feels fairer. 🥬 The Concept: Trajectory-level F1 reward scores the whole multi-turn attempt, balancing success and efficiency.

  • How it works: Compute recall (tasks solved) and precision (success per tool call), combine via harmonic mean.
  • Why it matters: Without both, models become too spammy (recall-only) or too timid (precision-only). 🍞 Anchor: Solving 4/5 sub-tasks with 6 calls beats solving 4/5 with 20 wasteful calls.

• 🍞 Hook: Learning to ignore clickbait makes you a smarter reader. 🥬 The Concept: Irrelevant-tool mixing adds distractor tools across similarity levels.

  • How it works: 1) Embed tool docs, 2) Group by similarity bands, 3) Add sampled distractors, 4) Train to choose right.
  • Why it matters: Without distractors, the model won’t learn to reject tempting wrong tools. 🍞 Anchor: Offered “temperature_in_fahrenheit” vs “temperature_of_classroom_paint” when you need weather—pick the right one.

• 🍞 Hook: A fair tryout needs consistent scoring and enough active plays. 🥬 The Concept: Adaptive Batch Filling ensures each RL update uses samples with real learning signal.

  • How it works: Buffer rollouts; keep batches where reward variance is non-zero; skip dead batches.
  • Why it matters: Without it, some updates do nothing, causing instability. 🍞 Anchor: If every scrimmage ends 0–0, no one learns; you pick games with real action.

At a high level: Input (tool docs, domains, Q&A traces) → SFT Trajectory Synthesis → SFT Training → QA-based Environment Synthesis → Online RL with F1 rewards and distractor tools → Trained Agent.

Step A: Multi-turn Trajectory Synthesis (for SFT) 🍞 Hook: Think of organizing a messy toolbox so you can actually build something cool.

🥬 The Concept: Schema normalization and MCP server grouping make tools consistent and composable.

• How it works: 1) Collect tool docs from registries and datasets, 2) Convert all to one OpenAI-style format, 3) Group by server (MCP), 4) Filter for quality (enough tools, clear docs, convertible schemas).
• Why it matters: Without consistency, you can’t reliably plan cross-tool chains or train at scale. 🍞 Anchor: 1,585 MCP servers and 19,036 tools remain after filtering, across 41 domains.

🍞 Hook: Building a LEGO city follows roads, not random jumps.

🥬 The Concept: Tool-chain construction samples valid sequences using a transition graph.

• How it works: 1) LLM proposes tasks and plausible chains within each server, 2) Build a directed graph of observed transitions, 3) Random-walk sample length-bounded chains, 4) Verify dependencies and task coherence.
• Why it matters: Without dependency checks, you’d call tools missing required inputs. 🍞 Anchor: “search_products → get_product_details → add_to_cart” forms a valid chain; missing IDs fails verification.

🍞 Hook: Teachers tweak questions to keep practice varied but fair.

🥬 The Concept: Task construction and augmentation create realistic, diverse prompts linked to tool chains.

• How it works: 1) Chain-conditioned tasks (guarantee executability), 2) Server-only tasks (broader coverage), 3) Augment by paraphrasing, complexity, persona—while keeping language and intent consistent, 4) Score by question quality, realism, and tool necessity; keep only above thresholds.
• Why it matters: Without careful filtering, you get off-topic or trivial tasks that don’t train tool use. 🍞 Anchor: “Find two laptops under $900, prefer 16GB RAM, summarize pros/cons” in English stays English after augmentation.

🍞 Hook: Sometimes you must pretend a component exists to test the rest.

🥬 The Concept: Hybrid execution uses real MCP tools when available and emulated tools otherwise.

• How it works: 1) Use Qwen-Agent to manage tool-calling loops, 2) Call deployed tools directly, 3) Use a stateful emulator for doc-only tools with a 20% failure chance to mimic reality.
• Why it matters: Without emulation and failures, models overfit to perfect worlds and break in the wild. 🍞 Anchor: A payment API might timeout; the agent should retry or adjust.

🍞 Hook: Getting graded helps you learn faster.

🥬 The Concept: Automated reward modeling scores each trajectory along seven axes (understanding, planning, context use, conciseness, success, final answer quality) and averages them.

• How it works: 1) Separate query understanding from plan quality, 2) Score tool-response understanding and planning per round then average, 3) Track tool-call success and conciseness, 4) Check final answer faithfulness and relevance, 5) Average all for a single SFT-quality score.
• Why it matters: Without fine-grained scoring, SFT data quality drifts and weakens training. 🍞 Anchor: A trajectory that misunderstands the query but plans fine gets partial credit, not a pass.

Step B: Verifiable Environment Synthesis (for RL) 🍞 Hook: Solving a big puzzle is easier with verified little pieces you can snap together.

🥬 The Concept: Q&A decomposition extracts the semantic topology—sub-questions and dependencies.

• How it works: 1) Given a domain corpus and hop budget, generate (main Q, answer) plus sub-QAs, 2) Validate dependency consistency, atomicity, sequential rationality, and completeness, 3) Keep only high-quality instances.
• Why it matters: Without a correct dependency map, partial progress and rewards become unreliable. 🍞 Anchor: “Plan a weekend trip” decomposes into flights, hotels, and attractions, with clear dependencies.

🍞 Hook: Practice labs must be real enough to test what you’ve learned.

🥬 The Concept: Environment synthesis creates code tools for each non-leaf sub-question and validates them in a sandbox.

• How it works: 1) Synthesize tool specs and scale complexity (parameters, values), 2) Generate invocation statements, 3) Implement Python tools, 4) Run in a sandbox to verify outputs match ground truth; retry if needed.
• Why it matters: Without executable tools and deterministic checks, RL signals wobble. 🍞 Anchor: A clinic-finder tool takes city + insurance, returns validated clinics you can re-run consistently.

🍞 Hook: If two questions differ only by city name, one bigger tool can serve both.

🥬 The Concept: Sub-environment merging consolidates functionally equivalent sub-questions to avoid action-space bloat.

• How it works: 1) Group homogeneous sub-questions by intent, 2) Expand the tool’s internal data structures, 3) Verify all invocations still pass in the sandbox.
• Why it matters: Without merging, training gets slower and noisier. 🍞 Anchor: A weather tool handles many cities by adding a city-indexed dataset and tests all lookups.

Step C: RL Training with Stable, Meaningful Signals 🍞 Hook: Being graded on both winning and sportsmanship changes how you play.

🥬 The Concept: F1-style trajectory reward balances completion and efficiency.

• How it works: r = solved/required, p = solved/calls, reward = harmonic mean of r and p; encourages solving more with fewer unnecessary calls.
• Why it matters: Precision-only makes models too shy; recall-only makes them spam tools; F1 balances both. 🍞 Anchor: Solving all sub-tasks with sensible calls outranks solving the same tasks with wasteful retries.

🍞 Hook: Tryouts are better when you face both obvious fakes and lookalike decoys.

🥬 The Concept: Irrelevant-tool mixing samples distractors across similarity bands.

• How it works: 1) Embed tools, 2) Partition into high/medium/low similarity to in-scope tools (excluding same-domain near duplicates), 3) Sample K from each band, 4) Present the mixed set to the agent.
• Why it matters: Without realistic distractors, the model won’t learn to say “no” to tempting wrong tools. 🍞 Anchor: Given “get_weather(city)”, also show “get_temperature_of_oven” and “get_weather_of_color” to test discrimination.

🍞 Hook: If a practice match has no goals or shots, it teaches nothing.

🥬 The Concept: Adaptive Batch Filling selects only rollout groups with non-zero reward variance for updates.

• How it works: 1) Buffer samples, 2) Keep filling until you have n valid ones (Std(reward) > δ), 3) Update policy, 4) Repeat.
• Why it matters: Without it, many updates are wasted and training destabilizes. 🍞 Anchor: Skip 0–0 games; train on games with real plays so gradients mean something.

Secret Sauce:

• Dual topologies: static tool-call graphs (teach breadth) + semantic dependency graphs (teach deep planning).
• Fully verifiable code worlds: deterministic rewards enable stable long-horizon RL.
• F1 reward + distractor mixing: sculpts both doing and discerning.
• Infrastructure tweaks (context parallelism, vLLM inference, adaptive batching) keep training efficient and steady.

Example Walkthrough:

• Input: “Compare 3 apartments under $2,000 within 30 minutes of work, then summarize pros/cons.”
• SFT phase: Use verified chain like search_listings → get_details → estimate_commute → summarize; score plan quality, conciseness, and final answer.
• RL phase: Decompose into sub-Qs (listings under budget, commute times, pros/cons), synthesize code tools (search, commute estimator), merge similar queries, add distractor tools, give F1 reward; the agent learns to pick the right tools, in the right order, with minimal waste.

🍞 Hook: When you play a tournament, you want referees, fair rules, and a scoreboard everyone trusts.

🥬 The Concept: ASTRA is tested on three agentic tool-use tournaments (BFCL-MT, τ-Bench, ACEBench) and two math reasoning checks (AIME 2024/2025).

• How it works: 1) Use vLLM for consistent decoding, 2) Evaluate with function-calling, 3) Repeat trials for stability (esp. small test sets), 4) Compare original vs SFT vs RL phases.
• Why it matters: Without fair settings and baselines, you can’t tell real improvement. 🍞 Anchor: Think of running the same drill on the same field with the same ball, then posting the scores.

The Test and Why:

• BFCL-v3 Multi-Turn (BFCL-MT): Measures multi-step, multi-turn tool use including missing-function/param and long-context stress—like an obstacle course.
• τ-Bench: Has a user simulator; tests conversation robustness under tool-and-user loops.
• ACEBench: Focuses on multi-step, multi-turn tool learning; small set repeated for stable means.
• AIME 2024/2025: Checks non-agentic reasoning (math) so we ensure tool skill doesn’t harm core thinking.

The Competition:

• Closed-source: Claude Opus/Sonnet/Haiku 4.5, Gemini 3 Pro/2.5 Pro, GPT-4.1.
• Open-source: Kimi-K2, GLM-4.6, LoopTool-32B, Qwen3-14B/32B.
• Ours: ASTRA-14B-thinking-v1, ASTRA-32B-thinking-v1.

The Scoreboard (contextualized):

• BFCL-MT Overall: ASTRA-32B hits 64.25%, which is like moving from consistent Bs to solid A-/B+ relative to same-scale peers. ASTRA-14B gets 58.13%, lifting a mid-level C/B- to a firm B.
• τ-Bench Overall: ASTRA-32B reaches 75.20% and 63.70% (Retail/Telecom), and ASTRA-14B reaches 68.00% and 57.70%. That’s like beating many open-source classmates and catching up to advanced students.
• ACEBench Overall: ASTRA-32B scores 71.88% and ASTRA-14B 68.96%, approaching closed models’ territory.
• Stage Gains: From original → SFT → RL, each step lifts scores; RL adds the biggest boost, showing verifiable RL with F1 reward is key.
• Non-agentic Math: AIME averages remain essentially steady or slightly improved (e.g., ASTRA-32B around 75.15%), so tool-skills didn’t cost reasoning.

Surprising Findings:

• Reward design is destiny: Recall-only RL ballooned turn counts and destabilized training; precision-only made the model overly cautious; F1 balanced both and stayed stable.
• Irrelevant-tool mixing matters: Without distractors, discrimination weakens; random distractors help; similarity-banded distractors help the most.
• Output length adjusts: SFT compresses outputs (concise plans), RL settles to an in-between length—shorter than the original, longer than SFT—suggesting practical reasoning plus adequate explanation.

Concrete Numbers (highlights):

• ASTRA-32B BFCL-MT Overall: 64.25% (vs. Qwen3-32B 47.88). ACEBench Overall: 71.88% (vs. 59.79). τ-Bench Overall: 75.20% (Retail), 63.70% (Telecom).
• ASTRA-14B BFCL-MT Overall: 58.13% (vs. Qwen3-14B 44.50). ACEBench Overall: 68.96% (vs. 51.67). τ-Bench Overall: 68.00% (Retail), 57.70% (Telecom).
• AIME: ASTRA keeps roughly the same band as bases—no collapse of math reasoning.

Takeaway: Across tough, interactive, tool-heavy tests, ASTRA’s two-stage training with verifiable RL and trajectory-level rewards delivers consistent, strong gains while preserving core reasoning.

🍞 Hook: Even the best bikes need tune-ups; knowing limits helps you ride smarter.

🥬 The Concept: Honest assessment means naming what ASTRA can’t yet do, what it needs, when not to use it, and what’s still unknown.

• How it works: 1) List limitations, 2) Note resource requirements, 3) Warn about misuse cases, 4) Pose open questions.
• Why it matters: Without clarity, it’s easy to overpromise and underdeliver. 🍞 Anchor: A map that marks detours and foggy areas keeps travelers safe.

Limitations:

• Environment synthesis cost: Generating and verifying many code tools can be compute- and time-heavy, especially for large, complex domains.
• Coverage gaps: Although broad, tool and domain coverage is not infinite; rare or highly specialized APIs may be underrepresented.
• Leaf-node language steps: Non-tool linguistic steps are allowed only at leaves; tasks needing nested language-only reasoning may be under-modeled.
• Cross-server composition: Current chains are restricted within the same MCP server for SFT; cross-server orchestration is not yet modeled.
• Reward proxy: F1 over sub-tasks and calls is powerful but still a proxy; some tasks value intermediate exploration or safety checks not directly captured.

Required Resources:

• Compute for long-context training (20k–49k token windows), high batch RL (e.g., 256), and sandboxed execution.
• Storage/I/O management for frequent SFT checkpoints and RL rollouts.
• Tool doc harvesting and embedding services for similarity-banded distractors.

When NOT to Use:

• Domains with non-deterministic or privacy-locked tools that cannot be executed or verified in sandbox conditions.
• Tasks whose success cannot be encoded as verifiable outputs (e.g., subjective style judgments without measurable criteria).
• Ultra-low-latency or low-budget setups where environment synthesis and RL cycles are impractical.

Open Questions:

• How to incorporate human-in-the-loop cheaply for corner cases while keeping most of the pipeline automated?
• Can we extend verifiable environments to handle user-in-the-loop dynamics (changing goals mid-dialogue) while keeping determinism where it counts?
• How to scale cross-server tool compositions and reason about inter-API contracts safely?
• Can reward shaping capture broader utility, like robustness to flaky tools, partial credit for safe fallbacks, or cost-awareness under strict budgets?
• What curriculum policies best pace environment difficulty as the agent grows stronger?

Bottom line: ASTRA makes a big stride toward automated, verifiable agent training, but future work must push into richer, interactive, cost-aware, and cross-ecosystem scenarios.

🍞 Hook: Teaching a pilot starts with flight manuals, then hours in a certified simulator.

🥬 The Concept: ASTRA unifies two automated pieces—trajectory synthesis on real tool-call graphs for SFT, and verifiable, code-executable environments from Q&A decompositions for multi-turn RL—plus an F1-style reward and distractor tools.

• How it works: 1) Build and score diverse multi-turn trajectories; 2) Construct deterministic sandboxed tools tied to sub-questions; 3) Train first by imitation, then by verified interaction with trajectory-level rewards; 4) Use adaptive batching for stable updates.
• Why it matters: This pipeline brings reliable, scalable, end-to-end training to tool-using agents, delivering state-of-the-art performance at matched sizes without harming core reasoning. 🍞 Anchor: The agent first learns the playbook, then excels in a certified scrimmage arena with fair scoring.

3-Sentence Summary:

• ASTRA automatically creates both the practice stories (multi-turn trajectories) and the practice worlds (verifiable code environments) that tool-using agents need.
• It trains models in two stages: supervised fine-tuning for a strong base and online reinforcement learning with F1 trajectory rewards in deterministic sandboxes.
• The result is state-of-the-art multi-turn tool performance at comparable scales, approaching closed systems while preserving reasoning.

Main Achievement:

• Making verifiable, scalable, end-to-end agent training practical by coupling static tool-topology SFT with semantic-topology RL and trajectory-level rewards.

Future Directions:

• Add user-in-the-loop training while preserving verifiability; support cross-server tool chains; refine cost-aware and safety-aware rewards; richer curricula from environment generators.

Why Remember This:

• ASTRA shows that the path to robust tool agents is not just more data—it’s the right kind of data (graph-grounded trajectories) and the right kind of practice (verifiable worlds) with the right kind of score (trajectory-level F1). This combination turns long-horizon tool use from a shaky demo into a teachable, testable, and reproducible skill.