Turnslide: Scalable Multi-Turn Data Synthesis by Walking a Finite-State Machine

AI summary

Overview

Research area: Synthetic training-data generation for multi-turn tool calling in small language models (SLMs); practical LLM agent training and evaluation.

Technical level: Intermediate. Readers need some familiarity with LLM fine-tuning, function/tool calling, and benchmarks such as BFCL v4, but the Finite-State Machine (FSM) abstraction itself is explained from first principles.

Scope: The paper presents Turnslide, a fully automated pipeline that models each API as a finite-state machine, samples state-valid tool sequences from it, and converts each sequence into a full multi-turn conversation with a single LLM call — evaluated by fine-tuning SLMs per BFCL v4 API domain and by comparing data quality and generation cost against ToolFlow and APIGen-MT.

What This Paper Is About

Base SLMs are cheap, low-latency, and deployable on private infrastructure, but they perform poorly at multi-turn tool calling, and fine-tuning them requires per-API trajectory data that rarely exists. Existing synthesis methods are expensive because they need hand-built mock sandboxes and many separate LLM calls per generated conversation turn (roleplaying user, assistant, and tool responses), and their tool sequencing is stateless, so generated trajectories can violate system preconditions and get discarded. The paper's goal is a lightweight synthesis framework that produces state-valid, controllable, diverse multi-turn tool-calling data at a fraction of the generation cost.

Key Contributions

1. FSM-based synthesis method. A synthetic data generation method for multi-turn tool calling that models API dynamics as an automatically constructed finite-state machine, generates each trajectory in a single LLM call, and controls diversity by specifying the distribution over selected blueprint attributes (number of turns, tool sequence, task complexity).

2. Downstream evaluation of data quality. The method is evaluated by fine-tuning a student SLM on synthetically created traces and reporting benchmark accuracy before and after training for each API domain derived from BFCL v4. Training on data created with FSM-based sampling has the highest positive impact of all the methods tested.

3. Quality comparison against related work. Benchmarking against ToolFlow and APIGen-MT on data quality, showing the FSM data trains better students: 70.7% full accuracy against 63.4% and 53.7%, with higher judged data quality (3.34 against 3.03 and 3.04).

4. Cost comparison against related work. Benchmarking the same two methods on generation cost, showing 1.0 LLM call per trajectory versus 34.3 and 107.2, producing 3.6–6.6× more trajectories under a fixed 20M-token budget.

Main Findings

• Base SLMs collapse on multi-turn tool calling. On the multi-turn category of BFCL v4, Gemini-3-Pro scores only 61% and GPT-5.2 44%. Untuned students fare far worse: Llama-3.2-3B-Instruct scores 4.0%, Qwen3-1.7B 11.0%, and Llama-3.2-1B-Instruct 0.0%. Fine-tuning closes the gap: at 3B scale xLAM-2-3b-fc-r reaches 58.4% and xLAM-2-8b-fc-r reaches 70.0%.

• FSM sampling gives the largest downstream gain. Fitting a multiple linear regression with generation condition, API domain, and student model as controls, the FSM condition yields β = 10.1% (SE 2.62, p < 0.01), the Markovian tool graph β = 7.88% (SE 3.19, p = 0.03), and the Turns mutator β = 2.89% (SE 2.87, p = 0.321).

• Gains concentrate in precondition-heavy domains. FSM improvements are most evident in VehicleControlAPI, TravelAPI, and TradingBot, where state requirements are pronounced (e.g., locking doors and pressing the brake before starting the engine, or authenticating a user before booking a flight). In state-agnostic domains like GorillaFileSystem, FSM and Markovian results are comparable.

• Full-conversation accuracy by condition (per-domain, "Full" column). Base Student: Trading 26.3, Travel 21.5, VehicleControl 5.6, FileSystem 18.9, Tick.&Trav. 12.5. Unmutated Baseline: 43.9, 47.8, 18.8, 67.3, 38.5. Turns Mutator: 44.9, 42.3, 19.1, 74.2, 40.4. Markovian: 41.5, 60.6, 19.7, 84.5, 36.6. FSM: 54.2, 61.5, 22.5, 80.2, 47.2.

• Cheaper generation at higher quality (Table 2, TradingBot domain, fixed 20M-token budget):

• Low rejection rate. After generation, tool calls and parameters are checked against function signatures and a ROUGE-based diversity filter discards duplicates; the rejection rate is approximately 2.3%.

• FSM construction is cheap. The FSM is built automatically with two LLM calls: one to identify underlying system states, and one to determine guard and transition relations for each tool.

• FSM fidelity is not verified. The recovered FSM is not checked against a downstream specification of the API; the authors rely on downstream performance as the metric for fidelity.

Methodology in Plain English

The pipeline treats the hidden system state behind an API as the thing that makes tool calls valid or invalid — for example, you may have to authenticate a user before updating an account balance. Each API domain is modeled as a finite-state machine consisting of states (which determine which tool invocations are valid), tool functions, guards (state conditions that allow a tool to be called), and transition relations (how calling a tool changes the state). This machine is built offline by an LLM in two stages; the paper's appendix shows the prompts for dimension induction (Stage 1) and transition induction (Stage 2), which is called in batches of ten tools.

Sampling a tool sequence then becomes a walk along the FSM: in each state, a tool is drawn from those its guard permits, and the tool's transition relation leads to the next state. Because the blueprint already carries the system state, one LLM call suffices to generate the entire conversation, rather than separate calls per role and per turn. Diversity is not optimized directly; instead the authors set a target distribution. The number of turns is uniform over a fixed range (2–10 in their runs). For tool sequences, drawing permitted tools with equal probability does not make tools uniform overall, because guards and transitions visit some states far more often than others, so the authors solve a convex subproblem with CVXPY to find per-state sampling probabilities that bring the marginal tool distribution as close to uniform as possible. Task complexity is raised by inserting "phantom tool calls" — information_retrieval and arithmetic_computation — at random positions before tools with numerical or string-valued parameters; these are not real API tools but instructions to the generator to retrieve or transform information first.

Downstream, the authors adapt BFCL v4 into a domain-partitioned dataset, grouping examples across distinct APIs and splitting each domain into seed and test sets 50:50, so seed corpora often contain fewer than 10 examples per API. Parallel tool calls were expanded into multiple turns with a single tool call. GLM-5.1 is used as the teacher model to synthesize 5000 synthetic examples, and Qwen3.5-2B and Llama-3.2-3B-Instruct are fine-tuned as students, with results averaged across students and two-fold cross-validation over the train/test partitions. Because fewer than 10 examples remained in each test set after splitting, the test set was augmented with additional trajectories generated using the Fable 5 model, produced independently of the pipeline under test, verified by executing against the BFCL implementation, and author-verified; these are strictly held out from training.

Why This Matters

Impact on research. The paper argues that the dominant blueprint for tool-calling data synthesis — a static, stateless graph over tools — cannot express dependencies that span an entire conversation, since whether a tool may be called depends on the full history and the initial environment state. The FSM formulation makes state transitions Markovian while the tool sequence itself is not, because the tool distribution is conditioned on the current state. It also reframes diversity as a distribution-matching problem rather than an optimization objective, which is a distinct methodological move.

Real-world applications:

• Rapid fine-tuning of small, privately hosted tool-calling models for each new API, since the seed corpus per API is often fewer than 10 examples and the pipeline is fully automated.
• Deployments where data cannot leave the environment, which is the paper's stated motivation for wanting SLMs that run on a user's own infrastructure.
• Domains with hard operational preconditions, such as vehicle control (locking doors and pressing the brake before starting an engine), travel booking (authenticating a user before booking a flight), and trading or banking operations.
• Dataset regeneration when a tool schema changes, which the paper identifies as a recurring cost of hand-annotated alternatives.

Industry relevance. The scalability claim is quantitative: 1.0 LLM call per trajectory versus 34.3 (ToolFlow) and 107.2 (APIGen-MT), roughly 3.6–6.6× more trajectories (or 4.0–6.5× the number of turns) under a fixed 20M-token budget, while also reaching higher fine-tuned accuracy. That combination matters for teams that must rebuild training data frequently rather than once.

Future Directions

• Verify the FSM before synthesis. The pipeline deliberately runs in a fully autonomous regime without checking the recovered FSM against the API specification, so errors in the FSM can propagate into generated data. The authors suggest using ensembles of frontier models to generate and judge the FSM.

• Broaden comparisons with related work. Computational costs of data synthesis and fine-tuning restricted the comparison against ToolFlow and APIGen-MT to a single domain under a fixed token budget; a full multi-domain comparison is left open.

• Strengthen evaluation sets. Part of the test set was LLM-generated because the per-domain splits left very few examples; larger and more stable held-out evaluation would be needed to move beyond the two-fold cross-validation setup used here.

• Re-examine baseline implementations. Publicly released code for the baseline comparisons could not be found at the time of publication, so the authors re

Authors’ abstract

Small language models are inexpensive to serve and can run on private infrastructure, but base models are often not good enough at multi-turn tool calling, and fine-tuning them needs per-API data that rarely exists. Existing synthesis methods are too expensive for high-scale fine-tuning, as they often require mock operational environments for different domains and multiple LLM calls per generated conversation turn. We introduce a fully automated, lightweight synthesis framework that models each API as a finite-state machine, representing the system as abstract states that determine when each tool may be called, producing state-valid sequences of tools; sequences are translated into complete examples with a single LLM call. Rather than optimize diversity, we set a target distribution over the number of turns, the tool sequence and task complexity. We measure data quality by fine-tuning SLMs on generated trajectories, showing that our FSM-based generation significantly improves downstream accuracy over an unmutated baseline and, against existing works, reaches 70.7% full accuracy over 63.4% and 53.7% with 3.6-6.6$\times$ fewer tokens.