Bilevel Optimization of Synthetic Trajectories for Multi-Turn LLM Fine-Tuning

Shresth Verma, Mauricio Tec, Cheol Woo Kim, Kai Wang, Milind Tambe · 2026

Read Bilevel Optimization of Synthetic Trajectories for Multi-Turn LLM Fine-Tuning by Shresth Verma, Mauricio Tec, Cheol Woo Kim, Kai Wang, Milind Tambe (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24743.txt.

Introduction

Shresth Verma and others improve multi-turn training by reweighting synthetic trajectories. Single-turn generation shines, but multi-turn interaction lags. Their BOOST framework nests two levels. The inner level trains the model on reweighted data. The outer level trains a light reweighting head on held-out real tasks, assigning continuous weights. A PAC-Bayesian bound exposes a three-way trade among diversity, task shift, and effective sample size. Tests consistently beat baselines, upweighting trajectories that match real data and show higher merit.

Catalog record

CREATORShresth Verma, Mauricio Tec, Cheol Woo Kim, Kai Wang, Milind Tambe
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70511
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24743

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bilevel Optimization of Synthetic Trajectories for Multi-Turn LLM Fine-Tuning Shresth Verma, Mauricio Tec, Cheol Woo Kim, Kai Wang, Milind Tambe Abstract While LLMs excel at single-turn generation, they struggle with long-horizon, multi-turn interactions. Offline reinforcement learning (RL) offers a scalable approach, yet its performance hinges on the availability and quality of multi-turn trajectory data. A common remedy is to augment training with synthetic trajectories generated by LLMs or simulators, but synthetic data is highly heterogeneous in quality, and naively treating all trajectories as equally informative can degrade performance. We propose BOOST, a bilevel optimization framework where the inner level trains the LLM on reweighted data and the outer level trains a lightweight reweighting head on held-out real validation tasks, assigning continuous trajectory-level weights without requiring an external judge. To ground this approach, we derive a PAC-Bayesian bound revealing a three-way trade-off: synthetic data increases diversity but risks task-shift, while concentrating weight on high-quality trajectories improves empirical performance at the cost of effective sample size. Empirically, our method consistently outperforms multiple baselines. Analysis reveals it upweights synthetic trajectories that align with the real data distribution and exhibit higher qualitative merit. 1 Introduction Large Language Models (LLMs) excel at generating fluent, human-like text, yet they often struggle with long-horizon reasoning and interaction ( 20 ; 19 ; 14 ; 18 ) . In multi-turn settings such as negotiation, persuasion, or technical troubleshooting, effective behavior requires planning across multiple steps, where intermediate actions may not yield immediate rewards but are essential for long-term success. For instance, a capable agent might ask a clarifying question rather than providing a premature answer, prioritizing future outcomes over short-term quality ( 3 ; 16 ; 1 ) . To address this limitation, multi-turn interaction can be framed as a reinforcement learning (RL) problem. While online RL optimizes for long-term objectives, model scale and interaction costs make it prohibitively expensive for LLMs. Consequently, offline RL has emerged as a scalable alternative, learning policies from pre-collected trajectories ( 28 ; 5 ; 15 ) . Despite its scalability advantages, offline RL introduces a new bottleneck: the availability and quality of multi-turn trajectory data. High-performing offline RL methods require datasets with sufficient coverage of the state–action space, which is especially challenging in multi-turn domains. To mitigate this issue, recent work has explored augmenting training data with synthetic trajectories generated by LLMs or simulators ( 27 ; 11 ) . While this improves coverage, it raises a critical challenge: synthetic data is highly heterogeneous in quality. A naive approach is to treat all trajectories as equally informative, but this can lead to suboptimal or even degraded performance, as low-quality or misleading trajectories may dominate the learning signal ( 2 ; 26 ; 10 ) . Prior work has attempted to address this via binary filtering using a stronger LLM judge, retaining only trajectories that pass a quality threshold, or using expert knowledge base for generating synthetic data ( 33 ; 12 ; 11 ) . While effective, such approaches discard potentially useful signal and rely on access to a higher-capacity scorer. We propose a principled bilevel optimization framework for incorporating synthetic data into multi-turn RL for LLM fine-tuning. Alongside fine-tuning the LLM, we learn a lightweight reweighting head that assigns a scalar weight to each trajectory in a mixed dataset. These normalized weights modulate each trajectory’s contribution in standard offline RL objectives, ensuring compatibility with various algorithms. Unlike heuristic filtering, our method performs continuous reweighting based on validation performance. We formulate the learning of reweighting model as a bilevel optimization problem: the inner level trains the policy on reweighted data, while the outer level optimizes the weights to improve performance on held-out real validation tasks. Unlike prior work that focuses on coarse-grained data source reweighting ( 23 ; 31 ) , our method operates at the trajectory level, enabling fine-grained control over data quality. This is particularly important in settings with synthetic data, where variability in quality can be substantial even within a single data source. Empirically, we demonstrate that our approach improves multi-turn RL performance by effectively leveraging synthetic data while mitigating the impact of low-quality trajectories. Analysis shows our model upweights trajectories that align more closely with the real data distribution. We summarize our contribution as follows: 1. We propose a bi-level optimization framework for trajectory-level reweighting of synthetic data in multi-turn RL fine-tuning of LLMs. We instantiate this framework with a reweighting head trained jointly with the base LLM and the Q functions via a fully first-order optimization scheme. The trajectory-level reweighting head scales to large datasets without prohibitive computational overhead. We further introduce some engineering innovations in bilevel updates which improve training stability. 2. To ground our approach, we derive a PAC-Bayesian bound on performance under trajectory reweighting. This reveals a three-way tradeoff: synthetic data increases diversity but risks task-shift, while focusing on high-quality trajectories improves empirical performance but reduces effective sample size, hiking the complexity penalty. 3. We empirically validate our approach on multi-turn RL benchmarks, showing consistent gains over baselines such as uniform data usage and reweighting applied only to real data. While we anticipated reweighting to always bias toward offline data, analysis reveals a surprise: BOOST selectively upweights synthetic trajectories mirroring the true distribution while suppressing low-quality offline samples. This manages the tradeoff between diversity and task-shift without sacrificing effective sample size. Furthermore, this process sometimes also recovers latent signals from offline points that were undervalued prior to synthetic augmentation, suggesting a synergistic rather than competitive relationship between data sources. Related Work Related work spans three areas: synthetic data augmentation and its degradation risks ( 29 ; 2 ; 26 ) ; bi-level optimization for SFT data reweighting ( 23 ; 17 ; 6 ) ; and offline/multi-turn RL for long-horizon LLM planning ( 28 ; 5 ; 15 ) . BOOST uniquely intersects these by extending bi-level reweighting to multi-turn RL with synthetic augmentation. See the Appendix for details. 2 Preliminaries: Multi-Turn LLMs Fine-Tuning and Data Selection 2.1 Task-conditioned Markov Decision Processes We model multi-turn LLM dialogue as a task-conditioned Markov Decision Process \mathcal{M}_{z}=(\mathcal{S},\mathcal{A},P_{z},R_{z},\rho_{z},\gamma) , where each task z\sim\mathcal{P}_{\mathrm{task}} is drawn from a task distribution and indexes a task-specific transition kernel P_{z} , reward R_{z} , and initial-state distribution \rho_{z} ( 13 ; 8 ) . The state s_{t} is the full interaction history up to time t ; an action a_{t} is a complete utterance sampled from the policy \pi(\cdot\mid s_{t}) ; and the next state concatenates the current state, action, and environment response: s_{t+1}=[s_{t};a_{t};o_{t}] . In the infinite-horizon formulation, the goal is to find a policy \pi_{\theta} maximizing the expected task-conditioned discounted return J_{\infty}(\pi)=\mathbb{E}_{z\sim\mathcal{P}_{\mathrm{task}},\,\tau\sim p_{\pi}}\!\left[\sum_{t=0}^{\infty}\gamma^{t}R_{z}(s_{t},a_{t})\right] with discount factor \gamma\in(0,1) . In the finite-horizon formulation, episodes terminate after at most H_{\max} steps. Many RL algorithms are traditionally framed for the infinite horizon case, while being often applied in practice to both frameworks. The common setup we consider for the theory and experiments in this paper is the task-conditioned finite-horizon setup with horizon H_{\max} , reward R_{z}(s_{t},a_{t})=-1 at every step prior to task completion, R_{z}(s_{t},a_{t})=0 once the task is completed (an absorbing terminal state), and \gamma=1 ; defining the expected hitting time of policy \pi on task z as T_{z}^{\pi}=\mathbb{E}\!\left[\inf\{t\in\mathbb{N}:\text{task $z$ completed at

Read the complete text