TRIP-Bench: A Benchmark for Long-Horizon Interactive Agents in Real-World Scenarios

AI summary

Overview

Research area: Evaluation and training of LLM-based interactive agents, specifically long-horizon multi-turn task completion with tool use (travel planning as the testbed).

Technical level: Advanced. The paper assumes familiarity with reinforcement learning for LLMs (PPO-style objectives, advantage estimation, KL regularization), tool-calling agent architectures, and user simulation.

Scope: The paper introduces a benchmark (TRIP-Bench) and an online multi-turn RL training method (GTPO), and reports results for a set of recent large language models on travel-planning tasks requiring long-horizon planning, global constraint adherence, and adaptation to evolving user behavior.

What This Paper Is About

Existing agent benchmarks underrepresent real deployment challenges: enforcing global constraints, coordinating multi-tool reasoning, and adapting to evolving user behavior over long, multi-turn interactions. The authors build TRIP-Bench, a long-horizon travel-planning benchmark using real-world data, 18 curated tools, and 40+ travel requirements, with difficulty-controlled splits that push dialogues to 15 user turns, 150+ tool calls, and 200k+ tokens of context. They also propose GTPO, an online multi-turn reinforcement learning method, to improve long-horizon constraint satisfaction and interaction robustness.

Key Contributions

1. A large-scale tool-augmented simulation environment. The authors extend and clean the TripTailor dataset (enriching POI attributes such as hotel room types and restaurant set menus, and fixing formatting, logic, and consistency issues), then build a unified interface of 18 tools across transportation, attractions, restaurants, hotels, and general utilities. The final dataset covers 40 cities with 6k+ attractions, 80k+ hotels, 400k+ restaurants, and 1M+ distinct products.

2. A task synthesis and validation pipeline for difficulty-controlled, behaviorally rich tasks. Rubric-to-constraint generation, progressive modification-chain synthesis (up to three steps), complexity-conditioned curation into easy/mid/hard tiers, and four hard interaction subsets (LIT, FIT, AIS, PMR), plus a two-stage prompt-based and manual quality-control process.

3. Extensive evaluation and analysis of current models. The paper reports loose and strict metrics across difficulty levels and analyzes resource cost, single-turn versus multi-turn behavior, error breakdowns, and user-simulator reliability.

4. GTPO, an online multi-turn RL method. GTPO (referred to in the paper both as Group Relative Turn-level Policy Optimization and, in the method section heading, as Group Turn-level Preference Optimization) combines turn-level reward normalization, global-instruction normalization, and turn-level reward differencing, with an ablation over these components.

Main Findings

• TRIP-Bench is highly challenging. The abstract reports that even advanced models achieve at most 50% success on the easy split, with performance dropping below 10% on hard subsets. The introduction states that most models score below 10% in strict mode, and that in loose mode the best-performing model, GPT-5.2, reaches only 45%.

• Strict scores are very low, including on Easy. In Table 2, GPT-5.2 (w/ thinking) reaches 66 loose / 49 strict on Easy, 55 loose / 13 strict on Mid, and 45 loose / 18.5 strict overall — the highest overall strict score reported. Several models score 0.0 on both metrics overall (for example, Qwen3-235B-A22B-Thinking-2507 reports 0.0 loose and 0.0 strict).

• Thinking substantially helps on easier splits but not enough for hard strict cases. On Easy-strict, DeepSeek-V3.2 rises from 5.0 (w/o thinking) to 31.0 (w/ thinking), and the Overall-strict score increases from 2.3 to 10.5. Hard-strict performance remains uniformly low across models. FIT remains unsolved under strict evaluation, and PMR lags behind LIT.

• GTPO outperforms SFT and GRPO. In Table 3, GTPO full on Qwen2.5-14B-Instruct reaches 35 Easy-loose / 13 Easy-strict / 18 Mid-loose / 0 Mid-strict, versus 16/4/8/0 for SFT and 29/0/12/0 for single-turn GRPO. On Qwen2.5-32B-Instruct, GTPO full reaches 49/21/40/5 versus 32/3/5/0 for SFT (the base model scores 0 on all reported cells).

• GTPO-trained Qwen2.5-32B-Instruct surpasses Gemini-3-Pro under the same evaluation. The paper reports 40 on Mid-loose and 21 on Easy-strict for the trained 32B model, and states the trained model outperforms Gemini-3-Pro. GTPO also exceeds the base model by over 20 percentage points under the loose setting and the SFT model by over 10 percentage points under loose and over 5 percentage points under strict.

• Component ablation. Turn-level Reward Normalization (TRN) stabilizes training; adding Global Instruction Normalization (GIN) improves average rewards; Turn Reward Differencing (TRD) yields the best results by prioritizing incremental gains and boosting the complete pass rate.

• Performance scales with output tokens, but cost scales logarithmically. Performance scales approximately linearly with the number of output tokens, while the performance-to-inference-cost relationship is closer to logarithmic due to input-token overhead from multi-step reasoning. DeepSeek-V3.2 Thinking under the Loose regime achieves performance comparable to GPT-5.2 at about 10% of the cost (approximately $0.25).

• Multi-turn interaction degrades relative to single-turn under strong global constraints. Single-turn accuracy exceeds multi-turn by roughly 10 percentage points on average for global constraints (for example validating POI opening hours or optimizing attraction sequences), and on the two most challenging hard evaluation sets multi-turn performance under the Loose metric falls more than 20 percentage points behind single-turn. Multi-turn remains competitive on local constraints that change infrequently (for example hotel cancellation policies or specific cuisine requirements).

• User simulator reliability. A manual evaluation of 20 randomly sampled trajectories (104 turns in total) found 98% reliability that the issued instruction ID was consistently reflected in subsequent queries; 10 trajectories in AIS (62 turns) scored an average of 4.7/5 for capturing intended ambiguity and faithful style simulation.

• Exploration versus single-try reliability. pass@k increases with more samples, indicating non-trivial exploratory ability, but pass@1 remains low and strict evaluation is substantially worse; avg^k stays stable across k, which the authors present as evidence of benchmark stability.

Methodology in Plain English

Data. The authors start from the TripTailor travel dataset and clean/expand it. They synthesize tasks in three layers. First, meta-information: they sample two- and three-city combinations from 40 cities, assign distance-based stays of 2–7 days, sample departure dates and group sizes, and use transportation tools to filter infeasible seeds — retaining roughly 6k two-city and 4k three-city itineraries. For three-city itineraries they keep only cases where two cities are within 500 km or the three are roughly collinear. Second, rubric and constraint construction: about 40 requirement categories from real travel planning, expressed in over 80 natural-language formulations, each paired with a generator function that produces a feasible ID set and a validator that checks whether a single ID satisfies the expression. Third, modification chains: up to three progressively more restrictive steps, trimmed or shortened to avoid redundancy where earlier constraints already imply later ones.

Task generation. Tasks are partitioned into easy, mid, and hard tiers using trip length, number of cities, number of constraints, and difficulty of simulated user behaviors. For a set of constraint expressions, the candidate set is the intersection of individual feasible sets, then further filtered by the validators; the authors require the resulting candidate set to be at least (4–10) times the trip length in days to guarantee enough flexibility. The hard split is extended into four subsets: LIT (more turns via fewer initial constraints and smaller per-turn updates), FIT (chains infeasible at the current step but feasible after rolling back one step, composing 2–4 infeasible requirements requiring 2–4 rollbacks), AIS (ambiguous constraints revealed only when the model errs or asks clarifying questions, across five interaction styles), and PMR (two similar itineraries sharing 6–9 modification chains, with trigger nodes to switch, roll back, or merge plans).

User simulation. Rather than a full instruction block (as in VitaBench and UserBench) or a fully predefined script (as in COMPASS), the authors use a user dialogue graph with a per-turn list of active preferences, updating the simulator prompt dynamically and varying behavioral diversity by difficulty. Later changes are not visible to earlier steps, and preferences switch only at a small set of key nodes. Nine categories of user behaviors are modeled.

Evaluation. Twelve general constraints are defined: 4 for basic feasibility and 8 for planning soundness. Two aggregate metrics are reported: Overall Strict (zero feasibility, soundness, and user-constraint violations) and Overall Loose (zero feasibility violations, at most two soundness violations, at most one user-constraint violation).

Training. For SFT, roughly 120k samples are synthesized with DeepSeek-v3.2 (no-think); only about 500 fully correct trajectories result, so the authors fix the tools and outputs and supply error feedback for three rounds of repair, yielding about 9k trajectories that pass evaluation. Keeping only trajectories with full reasoning and planning scores leaves about 3k trajectories, combined with Toucan data for SFT cold-start. For RL, they sample once over the same 120k inputs with the SFT-trained model and retain trajectories satisfying a relaxed criterion (zero feasibility violations and soundness plus constraint violations at most 5), yielding 7,040 samples. Training is done on Qwen2.5-14B-Instruct and Qwen2.5-32B-Instruct.

GTPO mechanics, in plain terms. For each prompt, a group of multi-turn rollouts is sampled. Each turn's raw reward is the fraction of satisfied constraints, gated to zero if feasibility is violated. GTPO then (1) normalizes each constraint's binary scores within a rollout across the turns where it applies (global instruction normalization), (2) computes the difference between a turn's reward and the previous turn's reward — using the group maximum of the previous turn when that turn was infeasible — to emphasize incremental improvement rather than inherited quality (turn-wise reward differencing), and (3) normalizes these differenced values across the group per turn, only for turns with at least half the group's samples, masking turns that exceed the context budget (turn-level reward normalization). The resulting turn-local advantages feed a PPO-style clipped objective with a per-token KL penalty to a reference policy. Advantages are turn-local and do not propagate across turns.

Evaluation setup. All models use default temperature settings, or 0.7 when unspecified. DeepSeek-V3.2 serves as the user simulator at temperature 0.7. Models evaluated include Kimi-K2 (Kimi-K2-0905-Preview, Kimi-K2-Thinking), Qwen3-235B-A22B (Instruct-2507, Thinking-2507), GLM-4.7, DeepSeek-V3.2, Gemini-3 (Flash and Pro), GPT-5.2, and Claude-Sonnet-4.5, each in non-thinking and thinking configurations where supported. Trained models are evaluated only on easy and mid subsets, because the hard subset often requires context lengths exceeding 128k tokens, beyond the maximum context length the trained models support.

Why This Matters

Impact on research. The paper argues that prior benchmarks either focus on single-turn tasks, add multi-turn interaction without systematically modeling complex rule constraints, or present instructions in segmented fragments that under-model revisions, rollbacks, and version control. The comparison table positions TRIP-Bench as the only listed benchmark marking all of instruction following, planning and reasoning, task complexity, tool complexity, and interaction complexity as fully addressed, with a reported max tool calls/average turns range of [50,150] versus [15,15] for TravelPlanner, [5,5] for TripTailor, [0,5] for LLMs Get Lost, [1,20] for UserBench, [1,40] for tau-Bench, [1,60] for tau²-Bench, [15,50] for COMPASS, and [5,75] for VitaBench. GTPO is offered as an online RL recipe for robust long-horizon training.

Real-world applications.

• Travel planning assistants that must satisfy hard global constraints (opening hours, budgets, routing) while users iteratively revise requirements.
• Customer-service agents operating under verbose policy constraints, the setting targeted by tau²-Bench, where rollbacks and feasibility judgments matter.
• General tool-orchestrating assistants that must coordinate many calls across heterogeneous APIs while tracking evolving user preferences.
• Training pipelines for long-horizon agents, where GTPO's reward shaping could be applied to domains beyond travel.

Industry relevance. The reported finding that GTPO-trained Qwen2.5-32B-Instruct outperforms Gemini-3-Pro on TRIP-Bench suggests that targeted multi-turn RL can close part of the gap between open and closed models for this task class, which matters for teams choosing between self-hosted models and API-based systems. The cost analysis — DeepSeek-V3.2 Thinking matching GPT-5.2 under the Loose regime at about 10% of cost, approximately $0.25 — speaks directly to deployment economics, and the paper notes a persistent generational gap between open-source and leading closed-source systems on the strict metric.

Future Directions

• Scaling trained models to the hard subsets. Trained models were evaluated only on easy and mid because the hard subset often requires context beyond the 128k-token limit the models support; extending context handling and training to LIT, FIT, AIS, and PMR remains open.

• Closing the multi-turn global-constraint gap. Since single-turn outperforms multi-turn by roughly 10 percentage points on global constraints and by more than 20 percentage points on the two most challenging hard sets under the Loose metric, improving cross-turn consistency under strong global constraints is an explicit open problem.

• Improving strict-mode reliability. Fitz remains unsolved under strict evaluation and hard-strict scores remain uniformly low; the paper frames pass@k versus pass@1 behavior as evidence of limited single-try reliability, leaving reliability rather than capability as a target.

• Release and reproduction. The impact statement says the authors plan to release the benchmark, evaluation scripts, supporting resources, and trained models, enabling follow-up work in both training and evaluation.

(The paper does not report additional planned directions beyond these.)

Target Audience

Researchers and engineers working on LLM agents, multi-turn reinforcement learning, and agent evaluation — particularly those building tool-using assistants that must maintain global constraints across long interactions. It is also relevant to practitioners selecting between open and closed models for long-horizon task completion, and to benchmark designers interested in task synthesis, user simulation, and difficulty-controlled evaluation splits.

Authors’ abstract

As LLM-based agents are deployed in increasingly complex real-world settings, existing benchmarks underrepresent key challenges such as enforcing global constraints, coordinating multi-tool reasoning, and adapting to evolving user behavior over long, multi-turn interactions. To bridge this gap, we introduce \textbf{TRIP-Bench}, a long-horizon benchmark grounded in realistic travel-planning scenarios. TRIP-Bench leverages real-world data, offers 18 curated tools and 40+ travel requirements, and supports automated evaluation. It includes splits of varying difficulty; the hard split emphasizes long and ambiguous interactions, style shifts, feasibility changes, and iterative version revision. Dialogues span up to 15 user turns, can involve 150+ tool calls, and may exceed 200k tokens of context. Experiments show that even advanced models achieve at most 50\% success on the easy split, with performance dropping below 10\% on hard subsets. We further propose \textbf{GTPO}, an online multi-turn reinforcement learning method with specialized reward normalization and reward differencing. Applied to Qwen2.5-32B-Instruct, GTPO improves constraint satisfaction and interaction robustness, outperforming Gemini-3-Pro in our evaluation. We expect TRIP-Bench to advance practical long-horizon interactive agents, and GTPO to provide an effective online RL recipe for robust long-horizon training.