Technical Summary: BOOST – Bilevel Optimization of Synthetic Trajectories for Multi-Turn LLM Fine-Tuning

Problem Statement

Large Language Models (LLMs) excel at single-turn generation but struggle with long-horizon, multi-turn interactions (e.g., negotiation, troubleshooting) that require planning across multiple steps where intermediate actions may not yield immediate rewards. While offline Reinforcement Learning (RL) offers a scalable alternative to online RL for fine-tuning LLMs on pre-collected trajectories, it faces a critical bottleneck: the scarcity and quality of multi-turn trajectory data.

To address data scarcity, recent approaches augment training sets with synthetic trajectories generated by LLMs or simulators. However, synthetic data is highly heterogeneous in quality. Naively treating all trajectories (real and synthetic) as equally informative can degrade performance, as low-quality or misleading synthetic trajectories may dominate the learning signal. Prior attempts to mitigate this involve binary filtering using stronger "judge" LLMs or expert knowledge bases, which discard potentially useful signals and require access to higher-capacity models. There is a need for a method that can continuously reweight synthetic data at the trajectory level without relying on external judges, effectively balancing the diversity offered by synthetic data against the risk of task-shift.

Methodology: BOOST

The authors propose BOOST (Bilevel Optimization of Synthetic Trajectories), a framework that integrates synthetic data into multi-turn RL fine-tuning via a bilevel optimization process.

Core Framework

BOOST formulates the learning process as a bilevel optimization problem:

1. Inner Level: Trains the LLM policy ($\pi_\theta$) and Q-value functions on a mixed dataset ($D_{mixed} = D_{real} \cup D_{synthetic}$) using a reweighted loss.
2. Outer Level: Optimizes a lightweight reweighting head ($w_\phi$) to assign continuous scalar weights to individual trajectories. The goal of the outer level is to minimize the loss of the resulting policy on a held-out real validation set ($D_{val}$).

Unlike prior work that reweights coarse-grained data sources, BOOST operates at the trajectory level, enabling fine-grained control over data quality. The reweighting head takes a trajectory as input and outputs a weight $w_\phi(\tau)$, which is normalized via softmax over a minibatch to modulate the trajectory's contribution to the training loss.

Training Procedure and Stability

The training algorithm (Algorithm 1) employs three key engineering innovations to ensure stability and convergence:

1. Alternating Frozen Updates: At each iteration, only one parameter group (auxiliary policy $\psi$, primary policy $\theta$, or reweighting head $\phi$) is updated while others are frozen. This prevents conflicting gradient signals.
2. Warm-Start Initialization: The primary policy $\theta$ is re-initialized from the auxiliary policy $\psi$ at the start of each outer iteration. Since $\psi$ tracks the inner-level optimum, this provides a warm start that accelerates convergence.
3. Asymmetric Learning Rates: The policy parameters ($\theta, \psi$) use a significantly higher learning rate than the reweighting head ($\phi$). This reflects the hierarchical nature of the problem, ensuring the policy reaches a stable solution before the weights are adjusted.

Theoretical Foundation

The authors derive a PAC-Bayesian hitting-time bound to ground the approach. The bound reveals a three-way trade-off:

• Synthetic Data: Increases diversity and effective sample size but risks task-shift (divergence from the target task distribution).
• High-Quality Focus: Concentrating weight on high-quality trajectories improves empirical performance but reduces the effective sample size ($n_{eff}$), increasing the complexity penalty.
• BOOST's Role: The framework aims for a "useful middle regime," assigning high weights to synthetic trajectories that align with the real data distribution and validation objectives, while discounting those that introduce noise or task-shift, all while preserving sufficient effective sample size for generalization.

Key Contributions

1. Bilevel Framework for Trajectory Reweighting: The authors introduce a principled bilevel optimization framework for reweighting synthetic data in multi-turn RL fine-tuning. They instantiate this with a parameter-efficient reweighting head trained jointly with the base LLM and Q-functions via a fully first-order optimization scheme.
2. Theoretical Analysis: They derive a PAC-Bayesian bound on performance under trajectory reweighting, explicitly characterizing the trade-off between data diversity, task-shift, and effective sample size.
3. Empirical Validation: The method is validated on three multi-turn RL benchmarks (20 Questions, Car Dealer Negotiation, and WebShop) using two RL algorithms (Monte Carlo Return and ILQL).

Results

Experiments demonstrate that BOOST consistently outperforms multiple baselines, including uniform data usage, naive synthetic augmentation, and bilevel reweighting applied only to real data.

• Performance Gains: BOOST shows the largest gains in low-data regimes. For example, in the 20 Questions task under the Monte Carlo Return setting, BOOST improved performance by 242.6% over the best vanilla baseline (3.46 vs. 1.01). In Car Dealer Negotiation, it improved by 31.7% (40.92 vs. 31.08).
• Synthetic Data Utility: Naively adding synthetic data often hurt performance (e.g., in ILQL settings, unweighted synthetic augmentation underperformed vanilla training in 4 out of 6 settings). BOOST successfully leveraged synthetic data by upweighting only those trajectories that aligned with the real data distribution.
• Weight Analysis:
  • The learned weights are non-uniform and vary per point.
  • High-weight synthetic points are those closest to the offline data distribution in embedding space (negative correlation between weight and distance to nearest offline neighbors).
  • Crucially, BOOST recovers latent signals from offline points that were previously undervalued. In the Car Dealer environment, 36.2% of offline points that received low weight under an offline-only objective were promoted to high weight when synthetic data was introduced, suggesting a synergistic relationship between data sources.

Significance and Claims

The paper claims that BOOST establishes a practical path toward data-efficient multi-turn LLM adaptation. By learning trajectory-level weights without external judges, the method manages the trade-off between the diversity provided by synthetic data and the risk of task-shift.

The authors emphasize that their approach:

• Does not require access to a higher-capacity "judge" model.
• Operates at a fine-grained trajectory level rather than coarse data sources.
• Effectively recovers useful signals from both high-quality synthetic data and previously undervalued offline data.

The paper concludes with a modest limitation: current reweighting operates at the trajectory level. Future work could explore finer-grained per-timestep reweighting to recover useful signals from partially good trajectories.