PaperlayerView exact revision on arXiv

Source-linked AI summary

SAP: State-Guided Data Synthesis with Argument Provenance for Multi-Turn Tool Use

Zichen Tian, Jinpeng Chen, Cheng Gong, Suiyun Zhang, Rui Liu

arXiv:2609.06124v1cs.AI

TL;DR

Multi-turn tool-use synthesis often underrepresents argument-level dependencies, which can leave correctly selected tools with fabricated, stale, or weakly grounded arguments. SAP addresses this with state-guided FSM generation, provenance constraints, and turn-level executor validation, producing SAP-4B data that achieves competitive results across BFCL v4 multi-turn and τ 2-bench.

  • Problem

    Existing multi-turn synthesis methods largely overlook cross-turn argument dependencies, despite their importance when tool arguments must be grounded in prior state, returns, or user messages.

  • Method

    SAP dynamically builds a provenance-annotated FSM, fills and executes tool calls turn by turn, and validates argument sources against execution history.

  • Results

    SAP-4B achieves competitive results on BFCL v4 multi-turn and τ 2-bench using data synthesized by SAP.

  • Takeaways & Limitations

    Argument provenance, state guidance, and turn-level validation provide a synthesis framework for constructing multi-turn tool-use data with long-range dependencies and high correctness.

  • Takeaways & Limitations

    The method is evaluated with English documentation in single-agent settings, and its Provenance Tag system does not cover entity anaphora in free text.

Abstract

from arXiv · show

High-quality multi-turn tool-use data is essential for training agentic models, yet existing data synthesis methods often underrepresent the argument-level dependencies that are critical to long-horizon tool use. As a result, even when a model selects the correct tool, task execution may still fail because the model fills tool arguments with fabricated, stale, or weakly grounded values. To address this problem, we propose \textbf{State-Guided Data Synthesis with Argument Provenance (SAP)}. SAP combines state guidance, tool-argument provenance constraints, and turn-level validation to efficiently construct tool-use trajectories with long-range dependencies and high accuracy. Using data generated by SAP, we build SAP-4B, which is highly competitive even when compared with much larger models across multiple benchmarks. Source code, synthesized data, and trained weights are available at https://github.com/Zichen1024/SAP.

1 Introduction

SAP addresses gaps in multi-turn tool-use synthesis by explicitly modeling argument provenance, guiding trajectories with state structure, and validating calls during generation. The resulting SAP-4B data supports competitive performance across BFCL v4 multi-turn and τ 2-bench.

  • Motivation: Existing synthesis methods often overlook cross-turn argument dependencies, although incorrect arguments frequently cause multi-turn failures even when the tool is selected correctly.Arguments may come from initial state, prior tool returns, or earlier user messages, creating risks of fabricated, stale, or hallucinated values.
  • Approach: SAP dynamically builds an FSM from tool documentation, assigns provenance constraints to arguments, and validates tool calls turn by turn.Failed calls are retried locally rather than causing the entire trajectory to be discarded.
  • Contributions: SAP introduces argument-provenance diagnostics showing that existing open-source data contain shallow dependency chains and few arguments depending on previous turns.These diagnostics target the long-range argument tracking needed in multi-turn tool use.
  • Results: SAP-4B achieves competitive results on BFCL v4 multi-turn and τ 2-bench, with ablations confirming the importance of each component.The reported result uses data synthesized by SAP.

2 Related Work

Prior multi-turn synthesis methods mainly follow intent-first or trace-first paradigms, while SAP makes argument provenance an active synthesis-time constraint. It also differs by using an automatically rebuilt FSM and a single synthesis-pass executor loop rather than relying on post-hoc filtering or outer-loop training.

  • Existing paradigms: Intent-first methods expand tool calls after drafting user intent, whereas trace-first methods sample executable trajectories and derive user queries from them.These paradigms use varied planning, validation, dependency-graph, and refinement strategies.
  • SAP distinction: SAP assigns every tool-call argument a provenance type and resolves declared sources against executor state before binding.This enforces argument-level causal consistency during synthesis rather than after generation.
  • SAP distinction: SAP lifts cross-turn checking from post-hoc filtering into a synthesis-time constraint, unlike approaches that detect propagated errors after generation.Its FSM is rebuilt from updated tool documentation without manually specified pairwise tool dependencies.
  • SAP distinction: SAP keeps executor validation within one synthesis pass and produces fixed SFT data, whereas InfTool co-evolves data and models through outer-loop GRPO.The comparison concerns pipeline organization rather than benchmark performance.

3 Preliminaries

SAP formulates synthesis in a POMDP and abstracts dialogue phases with a dynamically generated FSM. Its provenance system requires every argument value to have an executor-verifiable source, enabling measurement of cross-turn dependency chains.

  • 3.1 Task Definition: The task is modeled as a POMDP whose latent environment state evolves through tool invocations and responses observed via returns and user messages.The synthesis goal is a dataset whose argument values have explicitly declared, executor-verifiable causal sources.
  • 3.2 FSM Definition: The FSM abstracts environment dynamics into dialogue-phase states, with generated states and directed edges defining tool sequences and provenance-tagged arguments.The taxonomy is fixed across domains, while concrete states and transitions are generated per toolset.
  • 3.2 FSM Definition: AFSM constructs the FSM from tool documentation at synthesis time, so new toolsets can be supported by rebuilding it from updated documentation.This avoids manually specifying pairwise tool dependencies.
  • 3.3 Provenance Tags: Each argument source is categorized as Pi, Po, Pc, Pu, or runtime-only Pf, with Pf created when a declared source becomes unusable.The planner records the original source and validates the recovered call through the executor.
  • 3.4 Argument Dependency Graph: Argument dependency graphs represent reused value instances across turns, and chain length counts the turn boundaries crossed before consumption.Arguments with Po or Pu sources create cross-turn dependencies, while Pi, Pc, and Pf have zero chain length.

4 Method

SAP uses a closed synthesis loop in which AFSM creates a provenance-annotated skeleton, Aplan binds and executes arguments, and Amsg writes messages after validation. Deterministic and agent-side checks filter the resulting trajectories, while rewrite operators create targeted failure variants.

  • Pipeline: AFSM generates a provenance-annotated FSM skeleton, and Aplan converts sampled paths into executable calls using history and declared provenance tags.Same-turn calls are grouped into parallel step groups before execution.
  • Pipeline: Aplan binds runtime-dependent values against actual executor returns and recovers unusable arguments from permitted initial-state or newly introduced values.Recovered calls are validated after binding, while the original declared source is preserved.
  • Message synthesis: Amsg synthesizes user and assistant messages only after tool-call ground truth is fixed, grounding messages against actual returns.Newly introduced values appear as explicit literals, while referenced values use validated vague referents.
  • Hard variants: Two rewrite operators create hard variants for missing parameters and missing functions, including clarification and reveal turns for omitted parameter values.The operators target common deployment failure modes while preserving a validated base trajectory.
  • Validation: Every trajectory passes deterministic code-side checks and an LLM judge for intent alignment and rewrite compliance before persistence.Rejection by either check immediately discards the trajectory.

5 Experiments

SAP-4B is evaluated on BFCL v4 multi-turn and τ 2-bench, where it improves over its Qwen3-4B backbone and remains competitive with larger baselines. Ablations indicate that provenance tags and the FSM structure are central to the synthesis pipeline’s data quality and downstream performance.

  • Main results: +8.3 BFCL v4 multi-turn Avg improvement, from 22.1 to 30.4, over the Qwen3-4B-Instruct backbone without RL.The largest BFCL gains occur on Base (+11.5), LongCtx (+10.5), and MissParam (+9.0).
  • Main results: +2.9 τ 2-bench Avg improvement, from 32.2 to 35.1, over the Qwen3-4B-Instruct backbone without RL.Retail improves by +1.7 and Airline by +4.0.
  • Main results: SAP-4B’s multi-turn-only training does not regress BFCL v4 single-turn performance and produces small consistent lifts on Non-live and Live splits.The single-turn evaluation is presented as an out-of-distribution probe.
  • Main results: SAP-4B reaches 30.4 BFCL v4 MT Avg versus 30.3 for AWM-4B and 35.1 τ 2-bench Avg versus 24.7 for AWM-4B.On τ 2-bench, SAP-4B matches or exceeds several 8B baselines, while it still trails 8B baselines on BFCL v4.
  • Main results: The closed-source frontier reaches BFCL v4 MT averages in the 60s and τ 2 averages in the 70s, leaving substantial headroom for open-source 4B models on BFCL v4.GPT-5.2-High is reported at 48.5 versus approximately 60 on BFCL v4 MT and 72.1 versus approximately 78 on τ 2.
  • Ablations: Removing the FSM skeleton cuts the pipeline data pass-rate from 89% to 50%, while disabling per-call retry lowers it to 54%.The surviving no-FSM trajectories are too few and biased for a fair SFT comparison.
  • Ablations: Keeping the FSM but removing Provenance Tags yields a 92% pass-rate and zero Po arguments.This result identifies tag declarations as the mechanism generating cross-turn dependency arguments.
  • Ablations: Removing Provenance Tag declarations lowers BFCL v4 MT Avg from 30.4 to 24.0, while removing both rewrite operators lowers it to 28.8.The tag-removal effect is largest on LongCtx (-10.5) and Base (-8.5); rewrite removal produces smaller but consistent declines.

6 Discussion

SAP’s compact SFT-only setting achieves competitive results while using approximately 9k trajectories, but the method does not fully prevent hallucinations for newly created or fallback values. Execution checks localize unresolved quality issues to individual calls and make recoveries auditable.

  • Limitations: SAP does not fully prevent hallucinations for newly created Pc values or fallback recoveries that introduce a new value.Pf records the recovery event and original source, after which the executor checks the resulting call.
  • Efficiency and scope: Approximately 9k SFT-only trajectories let SAP-4B match or exceed several 8B RL-trained methods on τ 2-bench in a compact setting.The setup is constrained by live-executor cost and compute budget.
  • Efficiency and scope: SAP-4B uses a non-think backbone with SFT only, yielding substantially lower per-turn inference cost at comparable or better τ 2-bench accuracy.The comparison is made with open-source 4B baselines that use long deliberation chains before tool calls.
  • Error localization: Turn-level execution validation prevents an incorrect file binding from cascading into a later call, while fallback recovers and validates a usable recipient.The case study contrasts successful validation and recovery with failures caused by disabling those mechanisms.

7 Conclusion

SAP makes argument provenance an active synthesis-time constraint in a state-guided, execution-validated pipeline for multi-turn tool-use trajectories. The authors report benchmark validation and identify scope, cost, and evaluation boundaries.

  • 7 Conclusion: SAP promotes argument provenance from post-hoc annotation to a synthesis-time constraint through a provenance type system and FSM-driven, execution-in-the-loop generation.The pipeline dynamically rebuilds FSMs from tool documentation and validates executability per turn.
  • 7 Conclusion: SAP is domain-agnostic because updated tool documentation and a swapped executor backend suffice to support new toolsets without manual rule engineering.
  • 7 Conclusion: The authors propose provenance signals as a possible process-reward interface for future agentic reinforcement learning.Successful prior-output retrievals and binding mismatches are written into θprov during synthesis.
  • 7 Conclusion: The reported limitations include one-pass skeleton drafting, argument-only provenance coverage, English documentation, single-agent settings, expensive live validation, and no human-agreement statistics.The paper also notes that larger comparison numbers are quoted from original papers because concurrent systems do not release full pipelines.

A.1 Detailed FSM Specification

The FSM specification provides a shared state taxonomy and transition schema for generating provenance-aware tool-use trajectories. Verification, weighted coverage, executor feedback, and closure checks constrain both tool calls and synthesized messages.

  • Cross-domain reuse: The FSMs are regenerated from domain tool documentation using the shared taxonomy, so new domains require documentation rather than downstream protocol changes.Concrete implementations cover Retail, Airline, and BFCL v4 multi-turn domains.
  • State-type taxonomy (Σ): The shared taxonomy uses 13 abstract state types, including authentication, information gathering, search, outcomes, actions, errors, rejection, and completion.
  • Transition record (δ ∈∆): Each transition records an action, condition, probability, weight, critical-path flag, and provenance tag mapping tools and arguments to declared sources.The design-time sources are initial state, previous output, self-created value, and previous user message.
  • Vspec: Structural Constraints and Long-Tail Coverage: The verifier rejects illegal FSMs, paths lacking the required length, incomplete argument tags, and first-edge references to prior outputs or user messages.This removes a frequent nonexistent-context error before planning begins.
  • Long-tail coverage: Inverse-frequency sampling forces each new FSM to include at least one turn using a rare tool, while tracking tool frequencies without encoding inter-tool dependencies.
  • Argument planning and execution: Aplan fills and validates calls in a refill-on-failure loop, feeds executor errors back into prompts, and truncates trajectories that exceed the retry cap.Same-turn calls are partitioned into ordered groups with no prior-output edge within a group.
  • User-message dependencies: For previous-user-message dependencies, Aplan temporarily remaps arguments to self-created values, restores their tags, records virtual-history introductions, and checks that Amsg emits matching literals.Closure failures roll back the trajectory.
  • Amsg synthesis: Amsg slices must-mention markers per call and synthesizes intent fragments whose expressions cover required values and match each call’s operation.Dedicated prompts constrain clarification turns, prohibit new capabilities, and limit disclosure to the executed history.

B Additional Ablation Studies

The additional studies quantify synthesis cost for the SAP pipeline and clarify what the estimate includes. They do not provide a direct cost comparison with existing methods.

  • B Additional Ablation Studies: The pipeline-side studies include synthesis cost, cross-backbone fallback-rate analysis, and component ablations on data-generation success rate.
  • Synthesis cost: $0.49 per trajectory was the measured average API cost across 500 validated multi-turn trajectories.
  • Synthesis cost: Approximately $4,410 is estimated for the released set of about 9k trajectories under the same pipeline configuration and trajectory mix.The estimate covers synthesis-time API usage and excludes SFT training and downstream evaluation.
  • Synthesis cost: The paper makes no direct cost comparison because comparable trajectory-level billing logs are unavailable for existing methods.

B.2 Plan-Agent Fallback Rate Across Backbones

The Pf study compares how four backbones honor provenance sources while filling arguments for identical FSM skeletons. Gemini-3.1 Pro shows the strongest adherence, while other backbones exhibit higher fallback or more literal fabrication.

  • The study measures Pf on 500 identical FSM skeletons and reports the distribution of declared sources consumed by Aplan.Pf is the fraction of filled arguments requiring recovery because the declared source cannot be used directly.
  • 2.02% fallback is the lowest rate, achieved by Gemini-3.1 Pro, which also has the highest Pi utilization at 42.7%.These results indicate the strongest adherence to declared sources among the evaluated backbones.
  • 4.82% fallback is the highest rate, observed for Qwen3.5-Plus, with heterogeneous fallback_from labels including default, user_request, and user_intent.The observed labels suggest weaker compliance with the FSM-imposed source constraint.
  • DeepSeek-V4-Flash uses 9.2% Po and 59.4% Pc, while its 3,253 arguments are fewer than Gemini-3 Pro’s 4,348 on the same skeletons.The backbone tends to fabricate literals rather than reference prior tool returns, producing shorter trajectories.
  • 2.76% fallback places Gemini-3 Pro in the middle, with all fallbacks routed through Pc and a predictable failure mode.The main pipeline uses Gemini-3.1 Pro for AFSM and Gemini-3 Pro for Aplan.

B.3 Pipeline-Level Ablation

The ablation shows that FSM structure and executor-in-the-loop retries are central to successful synthesis, while provenance tags preserve cross-turn dependency structure even when they slightly reduce pass rate.

  • The ablation generates 500 trajectories per variant and measures executor pass-rate, fallback, and source-type distributions.All variants use Gemini-3 Pro with the same toolset and initial-config pool; comparisons are meaningful within this independent run.
  • 89% → 50% success follows removal of the FSM skeleton, while argument-level fallback rises to 15.75%.Without macro-level path planning, generated calls misalign with Tag-declared causal dependencies and fall back to Pc.
  • 92% pass-rate and zero fallback result from removing Provenance Tags, but the pipeline produces zero Po arguments.The resulting pipeline uses only local Pi and Pc sources and loses cross-turn dependency structure.
  • 54% success results when per-call retry is disabled, highlighting the importance of executor-in-the-loop refill.The full, FSM+noTag, and noRetry variants allow up to three sampled paths and three refills per call.

B.4 Out-of-Distribution Generalization on BFCL Single-Turn

SAP-4B is evaluated on BFCL v4 single-turn tasks to test transfer beyond its multi-turn training setting. Accuracy improves on both controlled Non-live and noisier Live queries without regression.

  • BFCL v4 single-turn evaluation: +0.52 Non-live accuracy shows that multi-turn-only training does not regress on controlled single-turn tasks.Non-live tasks primarily test tool selection, argument filling, and intra-turn parallelism.
  • BFCL v4 single-turn evaluation: +0.54 Live accuracy shows a comparable gain on real-world user-contributed queries with noisier phrasing and broader intent coverage.The Live split is more sensitive to generalization and robustness than the controlled Non-live split.
  • Provenance case studies: SAP’s case studies contrast local-only arguments with cross-turn dependencies spanning up to L = 2 turns.Trajectory B consumes tweet_id from a post_tweet return and mentioned_usernames from a list_all_following return.
  • Provenance case studies: The FSM declares Po edges at plan time, and Aplan resolves them against executor state before binding arguments.This design makes the cross-turn dependency trajectory a representative SAP construction rather than an incidental pattern.
Loading 2609.06124v1…