Agents2026~122 minarXiv:2602.01675

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

score 3Yuanzhe Shen, Zisu Huang, Zhengyuan Wang +14meituan↑ 9Feb 2, 2026cs.AI

🎯 Pitch

Even the most advanced models fail catastrophically when faced with truly long, evolving multi-turn tasks—success rates plunge below 10% on hard subsets where agents must handle infeasible constraints or ambiguous user intent shifts. TRIP-Bench reveals this gap by stress-testing agents across 150+ tool calls and 200k-token dialogues, and shows that structured turn-level reinforcement learning can close some, but not all, of the distance to real-world reliability.

1. Executive Summary

This paper introduces TRIP-Bench, a long-horizon benchmark grounded in realistic travel-planning scenarios that tests LLM agents on constraint adherence, multi-tool orchestration, and adaptation to evolving user behavior across dialogs spanning up to 15 turns, 150+ tool calls, and over 200k tokens of context. Even the strongest models struggle: GPT-5.2 with thinking achieves only 45% success under the loose metric and 18.5% under the strict metric, with performance dropping below 10% on hard subsets like Feasible–Infeasible Transition (requiring agents to recognize infeasible constraint combinations and execute rollbacks) and Ambiguous Intent Shifts (where user preferences are deliberately underspecified). The paper further proposes GTPO (Group Relative Turn-level Policy Optimization), an online multi-turn reinforcement learning method combining global instruction normalization (calibrating reward signals across constraint groups throughout the dialogue), turn-wise reward differencing (emphasizing incremental improvement by using the previous turn's reward as a baseline), and turn-level reward normalization (stabilizing per-turn advantage estimates across rollouts). Training Qwen2.5-32B-Instruct with GTPO improves performance by over 10 percentage points under the loose setting and 5 points under the strict setting over the supervised fine-tuning baseline, surpassing Gemini-3-Pro, establishing that structured turn-level credit assignment yields robust multi-turn gains — while performance on the hardest subsets remains at zero under the strict metric for all models, underscoring that existing approaches still cannot fully satisfy complex constraint interactions and dynamic user behavior simultaneously.

2. Context and Motivation

The Core Problem: We Cannot Evaluate Whether LLM Agents Can Handle Real-World Deployment Complexity

The fundamental challenge this paper addresses is that existing benchmarks fail to capture the demands that actual deployment of LLM agents imposes. When an LLM-based travel planner or customer service agent goes into production, it must simultaneously handle multiple interacting difficulties: following dozens of explicit rules and constraints, orchestrating sequences of tool calls where each depends on the outputs of previous calls, maintaining consistency across many turns of user interaction, and adapting when the user changes their mind, provides ambiguous preferences, or requests rollbacks to earlier versions of a plan. Existing benchmarks test at most a subset of these capabilities in isolation, but no benchmark forces an agent to demonstrate all of them at once over genuinely long interaction horizons.

The practical stakes are significant. The paper's authors come from Meituan, a major Chinese platform for local services including travel booking, food delivery, and hotel reservations. In such settings, agent failures are not abstract benchmark scores — they are incorrect bookings, violated user constraints, and frustrated customers. A travel agent that books a hotel outside the user's specified radius, schedules an attraction during its closed hours, or fails to recognize that two user constraints are mutually unsatisfiable (and thus requires a rollback) produces real operational costs. Without benchmarks that surface these failure modes systematically, developers cannot diagnose whether their agents are improving on the dimensions that matter for deployment.

This gap is not merely practical — it represents a theoretical blind spot in how the field evaluates agent capabilities. Current evaluation paradigms largely fall into two categories. Single-turn benchmarks (TravelPlanner, MCP Universe, Tool Decathlon) test whether an agent can produce a correct plan given a complete, unambiguous specification of requirements in one shot. Multi-turn benchmarks with simple interactions (τ-Bench, τ²-Bench, UserBench) add conversation but keep per-turn requirements shallow — queries are solvable with a few tool calls, rarely involve complex global constraints, and do not model the iterative refinement, ambiguity resolution, and version control that characterize real user-agent interactions. Neither category tests the simultaneous exercise of long-horizon planning, multi-constraint reasoning, tool orchestration, and behavioral adaptation that genuine deployment demands.

This paper's core insight is that these capabilities are not additive — they interact. A system that can follow constraints in a single turn may fail when those constraints are introduced progressively across turns. A system that can handle clear instructions may collapse when instructions are deliberately ambiguous. A system that can plan when all requirements are satisfiable may not know when to declare infeasibility and request a rollback. Existing benchmarks cannot reveal these interaction effects because they never create the conditions where they arise.

The Gap in Existing Benchmarks: Three Dimensions of Under-Representation

The paper systematically documents what existing benchmarks miss along three axes, summarized in Table 1. Understanding these gaps requires examining each axis in detail, because the paper's construction of TRIP-Bench is a direct response to specific shortcomings it identifies in prior work.

Dimension 1: Task Complexity — Long-Horizon, Multi-Step Objectives Under Multiple Constraints

Most existing benchmarks operate at modest scale along several dimensions that compound to determine real task difficulty. TravelPlanner (Xie et al., 2024) and TripTailor (Wang et al., 2025) — the most directly comparable travel-planning benchmarks — present users with complete constraint specifications upfront in a single turn. TripTailor averages only 5 tool calls and 5 turns, meaning the planning horizon is short and there is little opportunity for error accumulation or iterative refinement. The paper's earlier work, TripTailor, provides the data foundation for TRIP-Bench but treats the task as essentially single-shot: the agent receives all requirements and produces a plan.

What makes task complexity genuinely demanding in deployment is not merely the number of constraints but how those constraints interact across time, space, and cost dimensions. A user might require attractions of specific categories (Ecology, Flora & Fauna Zones), restaurants of specific cuisines with minimum star ratings, hotels within a distance radius, and transportation under a per-person budget — all while ensuring temporal feasibility (activities cannot overlap, transit times must be respected), spatial logic (restaurants should be near adjacent activities), and product consistency (ticket quantities must match party size). Individual constraints may be satisfiable in isolation but jointly infeasible. The agent must recognize this and either find creative trade-offs or communicate the infeasibility to the user. No existing benchmark systematically constructs these interaction effects.

The paper quantifies this gap in Table 1: where prior benchmarks handle at most 15–75 tool calls, TRIP-Bench tasks require 50–150+ tool calls. Where prior benchmarks average 5–50 turns, TRIP-Bench spans up to 15 turns with complex per-turn interactions. But the raw numbers understate the qualitative difference: the tool calls in TRIP-Bench are not independent lookups but form interdependent chains where flight searches constrain hotel selection, hotel location constrains restaurant proximity, and attraction timings must fit within intercity travel schedules.

Dimension 2: Tool Complexity — Realistic Interfaces and Coordinated Multi-Tool Orchestration

A second shortcoming of existing benchmarks is that their tool interfaces are oversimplified. The paper argues for two specific properties that real tool environments exhibit: appropriateness (tools have clear functional boundaries, consistent semantics, and require appropriate parameterization to produce useful results) and interdependency (tools exhibit sequential dependencies, result passing, and cascading invocation relationships that increase orchestration complexity).

Prior benchmarks are inconsistent on these properties. TravelPlanner and TripTailor use simplified search interfaces without the filtering, sorting, and pagination controls that real APIs expose. τ-Bench and τ²-Bench provide more realistic tools but for customer service domains where the tool chains are typically shallow (checking account status, processing returns) rather than deeply interdependent. COMPASS and VitaBench improve tool diversity but their inter-tool dependencies are limited.

The paper's tool suite (detailed in Appendix B.1) exemplifies the complexity it advocates. The 18 tools span five categories (attractions, hotels, flights, trains, restaurants) plus general utilities. Critically, they are not independent: a hotel search requires knowing the city and dates (derived from the itinerary meta-information), and its results feed into distance calculations via get_route_estimate, which in turn influence restaurant proximity constraints and daily schedule feasibility. Flight and train searches require airport/station coordinate lookups to compute intercity transit buffers. Restaurant selection must account for proximity to both the day's attractions and the hotel. This web of dependencies means that an agent cannot treat tool calls as isolated queries — it must maintain state, reason about how intermediate results constrain downstream choices, and recognize when an early commitment (e.g., choosing a hotel) has made a later constraint (e.g., a specific restaurant type within 10 km) unsatisfiable.

The paper's emphasis on appropriateness is also important. Real APIs return structured results with many fields; an agent must know which fields to use for filtering (e.g., using sort_key and sort_order to prioritize by price or rating rather than retrieving all results and filtering in context) and which to ignore. Poorly parameterized calls produce noise that accumulates in context, degrading performance on long-horizon tasks. TRIP-Bench's tools provide field-based filtering, sorting, and pagination controls precisely so that evaluation can distinguish agents that use tools efficiently from those that brute-force retrievals.

Dimension 3: Interaction Complexity — Diverse, Dynamic User Behaviors Over Extended Dialogues

The most distinctive gap the paper identifies is in interaction complexity. Even benchmarks that support multi-turn dialogue (τ²-Bench, VitaBench, COMPASS) model relatively simple user behaviors: linear instruction addition, occasional error pointing, straightforward preference statements. Real users are messier. They change their minds mid-conversation, provide preferences that are initially ambiguous and only clarified when the agent makes a wrong assumption, request that the agent merge elements from two previously discussed plans, and demand to revert to an earlier version after a series of unsatisfactory modifications.

The paper catalogs nine categories of user behaviors (Appendix B.3) that TRIP-Bench models, ranging from simple (instruction appending, error reporting) to complex (intent redirection, plan comparison/integration, version rollback). Four particularly challenging composite behaviors define the hard subsets:

Long Interaction Task (LIT): The user provides fewer initial constraints and smaller per-turn updates, forcing the dialogue to extend over many turns to fully specify requirements. This tests whether the agent maintains consistency when constraint information is distributed across a long context window.
Feasible–Infeasible Transition (FIT): The user introduces constraint combinations that are temporarily unsatisfiable. The agent must recognize infeasibility (rather than hallucinating a plan that violates constraints), communicate it, and then incorporate the user's rollback instructions to return to a feasible state. This tests metacognitive awareness — knowing when the problem as stated has no solution.
Ambiguous Intent Shifts (AIS): The user deliberately provides underspecified preferences (e.g., "I want good food" without specifying cuisine, budget, or rating threshold) and only reveals the explicit criteria when the agent makes an incorrect assumption or proactively asks clarifying questions. This tests whether the agent can recognize ambiguity, ask targeted questions, and avoid over-committing to interpretations of vague preferences.
Plan Merge Redirect (PMR): The user constructs two similar itineraries, introduces dialogue nodes that trigger switching between them, optionally rolls back after several turns, or requests merging the two plans. This tests version control — maintaining multiple plan states, tracking what constraints apply to which version, and correctly executing merges and rollbacks.

These behaviors are not merely difficult for difficulty's sake. They reflect real interaction patterns the authors have observed in deployment at Meituan. The paper argues that a benchmark without these behaviors cannot predict how an agent will perform when faced with actual users, who frequently change requirements, express preferences ambiguously, and request revisions to earlier decisions.

Why Prior Approaches Fall Short: Systematic Analysis

The paper's Table 1 provides a systematic comparison along ten traits grouped into four capability dimensions: Instruction Following (Constraint Adherence, Preference Alignment), Planning & Reasoning (Information Integration, Goal Management), Task Complexity (execution depth measured by tool calls and turns), Tool Complexity (Appropriateness, Interdependency), and Interaction Complexity (Behavior Attributes, Behavioral Diversity). The table also tracks whether each benchmark is Scalable (supporting automated evaluation at scale) and Trainable (providing data suitable for training as well as evaluation).

The pattern across existing benchmarks is that each addresses some dimensions while leaving others unaddressed, and no prior benchmark addresses all simultaneously:

TravelPlanner and TripTailor handle preference alignment and basic planning but lack constraint adherence (they don't enforce system-level rules), have simplified tools without interdependency, and model no behavioral diversity. They are single-turn or near-single-turn benchmarks.
τ-Bench and τ²-Bench excel at constraint adherence (verbose policy constraints) and tool appropriateness/interdependency, but they do not test preference alignment across turns, goal management under ambiguity, or diverse user behaviors. Their interactions, while multi-turn, are structurally simple — each turn is largely independent rather than building toward a complex, globally constrained objective.
COMPASS and VitaBench improve on behavioral diversity and tool complexity but still fall short: COMPASS relies on fully predefined scripts where the model only renders dialogue style (limiting genuine behavioral diversity and autonomy), and VitaBench, while enhancing dynamic interactions, does not cover the full range of behavioral attributes or the systematic difficulty control that TRIP-Bench provides.
UserBench introduces intention ambiguity but focuses on relatively simple tasks with shallow tool use and no complex global constraints. Its interactions are richer than earlier benchmarks but lack the long-horizon planning demands of travel planning.

The paper's diagnosis is that these gaps are not accidental — they reflect a fundamental tension in benchmark design between controllability (ensuring fair, reproducible evaluation) and realism (capturing the messiness of real user interactions). Prior benchmarks have leaned toward controllability, using simpler interactions, shorter horizons, and complete upfront constraint specifications to enable clean evaluation. TRIP-Bench represents a deliberate shift toward realism while attempting to maintain controllability through structured task synthesis, quality control, and rule-based evaluation metrics.

A Deeper Issue: The Distributional Shift Problem in Multi-Turn Training

Beyond benchmark evaluation, the paper identifies a second gap in how agents are trained for multi-turn interaction. This context from Section 2 (Related Work, "Multi-turn Reinforcement Learning") and Section 4 (Method) motivates the GTPO algorithm.

Most work on tool-using RL agents targets single-turn multi-step tasks where the user query is a fixed context and the agent produces a single response (SimpleTIR, Search-R1, AgentGym-RL). For multi-turn dialogue, a common simplification concatenates prior turns into a long context and treats the training problem as essentially single-turn with extended history. Gao et al. (2024, REFUEL) showed this induces covariate shift: training uses static offline histories generated by some (possibly different) policy, but deployment observes histories generated by the agent's own evolving policy, and the mismatch compounds over turns. The agent learns to respond appropriately to a particular distribution of conversation histories, but as its own behavior changes during training, the histories it encounters shift, invalidating the training signal.

Methods like MUA-RL (Zhao et al., 2025) and UserRL (Qian et al., 2025b) partially address this by integrating dynamic user simulation into the RL loop, so the agent trains on histories it actually generates. However, as the paper notes, these approaches "largely focus on direct user–LLM dialogue rather than long-chain tool invocation." The multi-turn tool-use setting adds an additional layer: not only does conversation history shift with policy changes, but the tool-call trajectories within each turn also shift, creating compound distributional drift. An agent that becomes better at hotel search will retrieve different hotels, which changes the feasible restaurant and attraction options, which changes the plan structure, which changes what the simulated user says next. Existing RL methods for multi-turn tool use do not account for this compound drift, leaving an open challenge that GTPO aims to address.

How This Paper Positions Itself

The paper's contribution is two-fold and integrated: a benchmark that creates the conditions under which the identified gaps become measurable, and a training method designed to address some of those gaps.

For evaluation, TRIP-Bench positions itself as the first benchmark to simultaneously test long-horizon constraint adherence, multi-tool orchestration with interdependent tools, and diverse multi-turn user behaviors with systematic difficulty control. The paper does not claim to introduce entirely new individual challenges — individual prior benchmarks have tested subsets of these capabilities. The novelty is in the combination and the difficulty ceiling it creates: by requiring all capabilities simultaneously over long horizons with complex interactions, TRIP-Bench surfaces failure modes that simpler benchmarks mask. The fact that even GPT-5.2 with extended thinking achieves only 18.5% under strict evaluation and models score zero on FIT under the strict metric validates that this combination creates genuinely new difficulty.

For training, GTPO positions itself as an online multi-turn RL method that addresses the credit assignment problem inherent in long-horizon tool-use dialogues. Rather than treating the final plan's correctness as the only signal (as in standard outcome-based RL) or ignoring the sequential structure (as in concatenated single-turn approaches), GTPO performs structured reward normalization across three levels: per-constraint normalization across the whole dialogue (Global Instruction Normalization), per-turn reward differencing to isolate incremental contributions (Turn-wise Reward Differencing), and per-turn normalization across rollouts to stabilize advantage estimates (Turn-level Reward Normalization). The paper demonstrates that this structured credit assignment yields consistent improvements over both SFT and GRPO baselines, with gains that scale from 14B to 32B models.

The paper's framing is explicitly practical: it is written from the perspective of practitioners deploying agents in production (several authors are at Meituan) who need benchmarks that predict real-world performance and training methods that produce robust agents. The emphasis on constraint verifiability (all evaluation metrics are rule-based and automatically computable), scalability (the benchmark supports automated evaluation and training data generation), and trainability (the benchmark can generate training trajectories, not just evaluation instances) reflects this deployment-oriented perspective. TRIP-Bench is designed not just to measure capability but to enable iterative improvement — a contrast with purely evaluation-focused benchmarks that provide no pathway from measurement to better performance.

3. Technical Approach

3.1 Reader Orientation

TRIP-Bench is a benchmark and training framework for long-horizon interactive agents that plan travel itineraries by calling 18 different tools (searching flights, hotels, restaurants, attractions, computing routes, etc.) across dozens of conversation turns with a simulated user who can add, modify, delete, or ambiguously specify constraints. The core problem it solves is that existing benchmarks test at most a subset of long-horizon reasoning, multi-constraint adherence, tool orchestration, and behavioral adaptation in isolation — TRIP-Bench forces agents to exercise all these capabilities simultaneously under systematically controlled difficulty, revealing failure modes (like the inability to recognize infeasible constraint combinations or maintain consistency across 150+ tool calls) that simpler benchmarks never surface. The "shape" of the solution is a three-part system: (1) a data generation pipeline that synthesizes travel-planning tasks with controllable complexity by sampling real-world constraints, constructing modification chains that simulate iterative user refinement, and composing complex interaction patterns (feasibility transitions, ambiguity, plan merging); (2) a simulation environment with 18 tools and a dynamic user simulator that maintains a per-turn preference graph and injects behaviors according to difficulty-controlled dialogue patterns; and (3) an online multi-turn RL method (GTPO) that performs hierarchical reward normalization — across constraints globally, across turns sequentially, and across rollouts simultaneously — to provide stable credit assignment for long-horizon tool-use training.

3.2 Big-Picture Architecture (Diagram in Words)

The TRIP-Bench system has five major components that operate in two phases — benchmark construction and agent evaluation/training:

Data Construction Pipeline (Section 3.2): Takes a real-world database of 40 cities with 6k+ attractions, 80k+ hotels, 400k+ restaurants, and 1M+ products. First, synthesizes itinerary meta-information (city combinations, trip lengths, dates) via combinatorial sampling and feasibility filtering. Second, generates constraints from 40+ rubric types (budget, cuisine, star ratings, proximity, timing) with 80+ natural-language expressions using paired generator/validator functions. Third, constructs modification chains — sequences of 1–3 progressively more restrictive constraint modifications — that simulate iterative user refinement, with redundancy pruning to ensure each step meaningfully narrows the candidate set. Fourth, composes tasks at three difficulty tiers (easy/mid/hard) by sampling rubrics across four dimensions (transportation, attractions, restaurants, hotels) and applying difficulty-conditioned user behavior patterns.
Tool Environment (Section 3.1, Appendix B.1): A unified interface exposing 18 functions across five domains — attractions (3 functions: search, detail, coordinates), hotels (3 functions: search, detail, coordinates), flights (3 functions: search, detail, coordinates), trains (3 functions: search, detail, coordinates), restaurants (3 functions: search, detail, coordinates), and general utilities (3 functions: route estimation, city center lookup, date arithmetic). Each tool accepts filtering parameters (price ranges, star ratings, cuisines, distance thresholds, time windows), sorting keys, and pagination controls, returning structured results that agents must parse and chain into planning decisions.
User Simulator (Section 3.4): Maintains a per-turn list of active user preferences derived from a dialogue graph. At each turn, dynamically updates a simulator prompt that selects up to 4 instruction IDs from history/new/modify/issue instruction pools, generates a natural-language user query reflecting the selected instructions and behavioral style (impatience, ambiguity, exploratory tone), and ensures later changes are invisible to earlier turns while switching preferences only at designated key nodes. Implements nine behavior categories: instruction appending, modification, intent redirection, deletion/rollback, plan comparison/integration, local revision, error reporting, clarification requests, and exploratory inquiry.
Evaluation Pipeline (Section 3.5): Applies 12 general constraints divided into 4 basic feasibility checks (JSON structural validity, POI existence in database, trip completeness including correct dates/cities/transit/hotels/activities, temporal coverage) and 8 planning soundness checks (temporal reasonableness — no overlaps, plausible durations, opening hour compliance, intercity transit buffers; spatial logic — sensible routing, proximity constraints typically <10km; experience diversity — no repeated attractions/restaurants; product consistency — ticket quantities match party size, hotel capacity sufficient). Aggregates into two metrics: Overall_Strict = 1 only when F_feas = 0 AND F_sound = 0 AND F_user = 0 (zero violations across all categories), and Overall_Loose = 1 when F_feas = 0 AND F_sound ≤ 2 AND F_user ≤ 1 (allowing minor soundness and user constraint violations while keeping feasibility inviolate).
GTPO Training Framework (Section 4.2): Takes groups of multi-turn rollouts sampled from the current policy interacting with the user simulator, computes per-constraint raw binary scores across all turns, applies three-stage reward normalization: (a) Global Instruction Normalization — z-score normalizes each constraint's satisfaction scores across all turns where it applies within each rollout, then averages normalized scores per turn; (b) Turn-wise Reward Differencing — subtracts the previous turn's normalized reward (or the group maximum if the previous turn was infeasible) from the current turn's reward, isolating incremental improvement; (c) Turn-level Reward Normalization — z-score normalizes the differenced advantages across rollouts at each turn, producing per-turn advantage estimates. Optimizes a PPO-style clipped surrogate objective with per-token KL penalty to the reference policy, where each turn's advantage is turn-local (does not propagate across turns) and tokens from incomplete turns are masked.

Information flows through the system as follows. In the benchmark construction phase: real-world POI database → combinatorial sampling of itinerary seeds → rubric-based constraint generation with generator/validator pairs → modification chain synthesis with redundancy trimming → difficulty-conditioned task assembly with behavior pattern injection → quality control via plan sampling and manual review. In the evaluation/training phase: task specification → user simulator generates initial query with selected constraint IDs → agent plans via iterative tool calls → user simulator evaluates agent response, consults dialogue graph for next instruction selection, generates follow-up query → loop continues for up to 15 turns → final plan evaluated against 12 general constraints plus user-specific constraints → loose/strict scores computed.

3.3 Roadmap for the Deep Dive

First, the task synthesis pipeline — how itinerary seeds, constraint rubrics, modification chains, and difficulty levels are constructed — because this is what creates the benchmark's distinctive challenge and must be understood before the interaction dynamics make sense.
Second, the user simulator architecture — how the dialogue graph, instruction pools, and behavioral patterns produce the multi-turn dynamics that distinguish TRIP-Bench from simpler benchmarks.
Third, the evaluation metrics — what the 12 general constraints and user-specific checks measure, how loose versus strict aggregation works, and why the rule-based design enables scalable automated evaluation.
Fourth, the GTPO algorithm — the hierarchical reward normalization, the mathematical reasoning behind each component (global instruction normalization, turn-wise reward differencing, turn-level normalization), and how the final PPO objective integrates them for stable multi-turn credit assignment.
Fifth, the SFT data construction pipeline (Section 4.1) that provides the cold-start model for GTPO, including the three-round error-feedback repair procedure and trajectory filtering strategy.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a benchmark construction and training methodology paper whose core technical contribution operates at two levels: a data synthesis engine that programmatically generates complex, multi-constraint travel-planning scenarios with controllable difficulty, and a reinforcement learning algorithm that addresses the credit assignment problem in long-horizon tool-use dialogues through hierarchical reward normalization.

Task Synthesis: Meta-Information, Rubrics, and Modification Chains

The task synthesis pipeline (Section 3.2, Figure 1 left) constructs each TRIP-Bench instance from three layers of specification: itinerary meta-information (where, when, how many people), constraint rubrics (what the user requires), and modification chains (how those requirements evolve across turns). The design principle is that each layer can be independently controlled, enabling systematic difficulty manipulation, while their composition produces the emergent complexity of realistic travel planning.

Itinerary meta-information synthesis. The paper samples from the 40-city database all two-city and three-city combinations, then assigns stay durations (2–7 days) based on intercity distances, departure dates, and group sizes. Transportation tools are used at synthesis time to filter out infeasible candidates — for instance, a three-city itinerary where no flights or trains connect the cities within reasonable time windows is discarded. For three-city cases, an additional geometric constraint is enforced: either two cities must be within 500 km, or the three cities must be approximately collinear, matching typical travel route patterns. This produces approximately 6,000 two-city and 4,000 three-city itinerary seeds that define the spatial-temporal skeleton onto which constraints will be layered.

This pre-filtering step is critical for benchmark validity. Without it, the pipeline might generate itineraries that are structurally impossible regardless of constraint choices — for example, a three-city trip where the only flight connection between cities B and C departs before the earliest possible arrival in city B. By running actual tool queries during synthesis, the paper ensures that every seed itinerary is at minimum transportation-feasible, guaranteeing that at least some constraint configurations on each seed can produce valid plans. This eliminates the "impossible by construction" failure mode that would make benchmark scores hard to interpret — if a model scores zero, it should be because it failed at reasoning, not because the task was unsolvable.

Rubric and constraint construction. The paper collects approximately 40 common requirement categories from real-world travel planning and curates over 80 diverse natural-language expressions. The full rubric taxonomy (Appendix B.2) spans five domains:

Transportation: departure/return timing constraints (broad periods like "morning," specific windows like "18:00–20:00," before/after cutoffs), per-person budget caps (one-way, round-trip, or total), booking platform restrictions (allow or exclude specific platforms), schedule reliability requirements (minimum on-time performance rate, maximum delay tolerance), and airline exclusions.
Attractions: category inclusion/exclusion (e.g., must include museums, must exclude amusement parks), specific attraction requirements (include/exclude by name), popularity thresholds (heat score bands), review count minimums, ticket price constraints (free only, below threshold), maximum distance from hotel or city center, category priority ordering, and official sight level (e.g., 5A or at least 4A).
Hotels: budget constraints at multiple aggregation levels (per night per room, per night per person, per-person total, overall total), hotel type/tier restrictions (include or exclude specific levels), review count minimums, positive review rate thresholds, star rating minimums, aspect rating requirements (product/environment/service, either jointly or individually), cancellation policy flexibility (free cancellation by a deadline), pet-friendliness, breakfast count requirements (exact or minimum), window requirements, and location proximity (within distance of city center, with special handling for final night near airport/station).
Restaurants: per-person per-meal cost constraints (less than, more than, around, within range), overall star rating minimums, review count minimums, cuisine inclusion/exclusion, reservation availability constraints, and sub-ratings for food quality, environment, and service.
General: Dietary constraints and accessibility requirements (the paper mentions these categories but detailed rubrics are in the appendix).

For each expression e, the paper defines two paired functions — a generator G(e) and a validator V(e, i). The generator takes the expression text and produces two outputs: a fine-grained selection range R (the parameter constraints that implement the expression, e.g., rating ≥ 4.5 for "well-rated restaurants") and the corresponding feasible ID set F (the actual POI IDs in the database that satisfy the expression). The validator takes an expression and a single POI ID and returns a binary judgment: does this specific item satisfy the expression? This generator-validator architecture is the key to scalable task synthesis. The generator creates the constraint specification that will be given to the agent (in natural language or as search parameters), while the validator enables automated checking of whether the agent's plan actually satisfies the constraint — no human judgment required.

Modification chain construction. A modification chain is a sequence of 1–3 constraint modifications that becomes progressively more restrictive, simulating how real users iteratively refine their requirements. For example: initial constraint "restaurants rated ≥ 4.0" → first modification "now require ≥ 4.5 and add Korean cuisine requirement" → second modification "also require within 5 km of hotel." At each step, the candidate set of satisfiable items shrinks, and the agent must revise its plan accordingly.

The paper prompts a model (for data synthesis, not the agent under test) to generate these chains given meta-information and a rubric-specific candidate set. The core technical challenge in chain construction is redundancy: earlier constraints may already entail later ones. For instance, if the user first requires "hotel within 5 km of city center" and later adds "hotel within 3 km of city center," the second constraint makes the first redundant — but in a synthetic benchmark, this creates a trivial "modification" that doesn't actually test the agent's ability to handle changing requirements.

To address this, the paper uses two strategies:

Trajectory-based trimming: Sample trajectories of POI selections, check whether earlier constraints already satisfy later ones. If they do, discard the redundant prefix of the chain and retain only the suffix where constraints actually induce change. For example, if a 3-step chain has steps (A, B, C) but A already entails B, the pipeline keeps only (B, C) or just (C) depending on the entailment pattern. This is verified empirically by sampling trajectories rather than relying on logical analysis — if sampled plans satisfying constraint A also satisfy constraint B with high probability, B is considered redundant given A.
Rubric-level adjustment: For rubrics that are structurally prone to redundancy (e.g., nested budget constraints where "under ¥1000 total" subsumes "under ¥300 per night"), shorten the target chain length so the pipeline doesn't force the model to generate trivial steps.

The paper notes that some redundancy is intentionally preserved for realism — real users do sometimes restate or slightly refine already-satisfied constraints. The goal is to prevent systematic redundancy that would make a large fraction of benchmark instances trivially easy, while allowing the occasional mild redundancy that occurs in natural conversation.

Task generation and difficulty control. Tasks are partitioned into three difficulty tiers (easy, mid, hard) along two axes: plan complexity (trip length, number of cities, number of constraints) and interaction complexity (types of user behaviors exhibited). Table 4 specifies the exact criteria:

Easy: 2–5 days, two cities, 2–6 total constraints (0–4 in the first turn), user behaviors limited to instruction additions, modifications, feasible-only deletions/rollbacks, and issue pointing. The first turn typically provides most constraints, with only minor modifications in later turns.
Mid: 3–7 days, two or three cities, 7–10 total constraints (4–7 in the first turn), includes all Easy behaviors plus content corrections, clarification/explanation requests, and exploratory questions. More constraints are deferred to later turns, requiring the agent to build the plan incrementally.
Hard: 3–10 days, two or three cities, 11–14 total constraints (typically 8–11 in the first turn), includes all Mid behaviors plus four composite hard behavior subsets.

The constraint assignment process targets approximately uniform distribution over rubric counts along the four dimensions (transportation, attractions, restaurants, hotels). For each sampled rubric, the modification chain length is set to match the target chain length for that difficulty tier. The pipeline then derives the initial filtered candidate set as the intersection of feasible ID sets across all constraint expressions: C_0 = ∩_{e ∈ E} F_e. Because subset/containment constraints (e.g., "must include at least one restaurant of type X") may not fully filter candidates or certify solvability through intersection alone, the paper further verifies feasibility by applying the validator to each candidate: C = {i ∈ C_0 : ∀e ∈ E, V(e, i) = 1}. Finally, the pipeline requires |C| ≥ (4–10) × trip_length to ensure sufficient flexibility for itinerary construction — too few valid options would make the task essentially a lookup rather than a reasoning problem.

The four hard behavior subsets are constructed by composing modification chains with specific interaction patterns:

LIT (Long Interaction Task): Uses fewer initial constraints in the first turn and smaller per-turn update granularity, forcing the dialogue to span more turns to fully specify requirements. Where an easy task might provide 4 constraints upfront and 2 modifications across 3 turns, a LIT task might provide 2 constraints upfront and spread 10 total constraints across 8–10 turns with 1–2 per turn. This tests whether the agent can maintain plan consistency when constraint information is distributed across a very long context window — a different failure mode than "too many constraints to satisfy simultaneously."
FIT (Feasible–Infeasible Transition): Selects modification chains that become infeasible at the current step but become feasible again after rolling back one step. When the chain length is 1, "rolling back" is equivalent to deleting the most recent constraint. The pipeline composes 2–4 such infeasible requirements (requiring 2–4 rollbacks to reach feasibility) and injects rollback instructions dynamically during execution according to three trigger patterns: when the agent explicitly declares infeasibility, at simulator-chosen narrative moments, or at the dialogue's end. The final requirement set after all rollbacks is guaranteed feasible. This tests metacognitive ability — the agent must recognize that no plan can satisfy the current constraints, communicate this, and correctly incorporate the user's rollback rather than hallucinating a plan that silently violates constraints.
AIS (Ambiguous Intent Shifts): Introduces constraints phrased ambiguously (e.g., "I want good food" without specifying rating threshold, cuisine, or budget) and reveals explicit preferences or corrections only when the agent makes an incorrect assumption or proactively asks clarifying questions. Uses five interaction styles varying in assertiveness, patience, and level of detail provided in corrections. This tests whether the agent can recognize underspecification, ask targeted clarification questions rather than guessing, and avoid over-committing to interpretations of vague preferences that are later contradicted.
PMR (Plan Merge Redirect): Constructs two similar itineraries that share 6–9 modification chains but differ on other dimensions (e.g., same city pair but different attraction preferences, or same constraints but different city). Inserts trigger nodes in the dialogue where the simulator switches between itineraries, optionally rolls back several turns to an earlier plan state, or requests merging elements from both plans. This tests version control — the agent must maintain multiple plan states, track which modifications apply to which version, and correctly execute merges (e.g., "take the hotel from plan A and the restaurant selections from plan B") and rollbacks.

User Simulation Architecture

The user simulator (Section 3.4) is not an off-the-shelf LLM prompted to "act like a user." It is a structured system that maintains a dialogue graph — a representation of which instructions are currently active, which have been satisfied, which are pending, and which represent modifications or overrides of prior instructions. The graph ensures that the simulator's behavior is both diverse (covering the nine behavior categories) and controlled (guaranteeing that the underlying constraint structure is coherent, that later changes don't leak information visible only at later turns, and that preference switches occur only at designated key nodes).

At each turn, the simulator receives:

All dialogue context and the agent's most recent response
The history instruction pool (constraints already communicated to the agent)
The new instruction pool (constraints to be introduced in this turn, if any)
The modify instruction pool (constraints to be modified or overridden)
The issue pool (errors or inconsistencies the simulator should report, based on the evaluation of the agent's plan)
Special instruction templates for ContentMod, ClarifyExp, and ExploreQues behaviors

The simulator selects up to 4 instruction IDs to activate in the current turn — this cap simulates the gradual exposure of requirements that characterizes real conversations, where users don't dump all constraints at once. The selection is constrained: instructions from the history pool are not re-selected by default (they've been addressed unless the agent explicitly asks for confirmation), selected modify instructions override their corresponding history instructions, and special instruction content must not conflict with new/modify instructions.

The simulator prompt (Appendix F.2) then instructs a language model (DeepSeek-V3.2, temperature 0.7) to generate a natural, conversational user query that reflects the selected instructions while following behavioral rules: answer agent questions immediately, admit ignorance rather than fabricating, paraphrase without changing meaning, stick to requirements when the agent pushes back, show impatience if the same question is asked within 3 turns, and never reveal that it is a model. The output is a JSON object with instruction_ids (tracking which instructions were used) and user_query (the natural language message).

The dynamic update pipeline enforces temporal causality: modifications chosen at turn t become visible to the simulator at turn t+1, not retroactively. Preference switches occur only at a small set of key nodes in the dialogue graph, preventing the simulator from oscillating arbitrarily. This balances the competing demands of autonomy (the simulator can generate diverse, natural-sounding queries), diversity (the nine behavior categories ensure coverage of real interaction patterns), and controllability (the underlying constraint structure is preserved across turns, ensuring that evaluation remains well-defined and fair).

The paper reports a manual evaluation (Section 5, Appendix E) validating the simulator's reliability. On 20 randomly sampled trajectories (104 turns), instruction ID consistency in subsequent queries — measured as the fraction of turns where key constraints are retained without contradiction or unwanted specification — achieved 98% accuracy. On 10 AIS trajectories (62 turns), annotators rated ambiguity capture and style fidelity on a 1–5 scale, obtaining an average of 4.7/5.

Evaluation Metrics: Rule-Based Verification of Feasibility, Soundness, and User Constraints

The evaluation system (Section 3.5, Appendix B.4) is entirely rule-based — no LLM judges, no human annotation during evaluation. This is essential for scalability (the benchmark can evaluate thousands of agent trajectories automatically) and reproducibility (scores are deterministic given the agent's output). The verifier operates on the agent's final JSON plan (the trip_plan output) and the history of tool calls and responses.

Basic feasibility (4 checks):

Structural validity: The output must parse as valid JSON conforming to the required schema. Field names must match exactly (no additions, deletions, or renaming), and parameters must be correctly formatted (dates as YYYY-MM-DD, times as HH:MM-HH:MM). This is the first gate — if the output isn't parseable, all other checks are moot.
POI validity: Every referenced POI (restaurants, attractions, hotels) must exist in the database inventory and belong to the correct planning city. The verifier cross-references all IDs against the database. A common failure mode is agents hallucinating POI IDs — the verifier catches this deterministically.
Information completeness: The plan must specify correct trip dates and party size, include the required city stays and intercity transport legs, cover essential daily POIs (at least one restaurant and one attraction on non-transfer days), and include hotels for all nights except the return day. This ensures the agent didn't skip entire components of the itinerary.
Temporal coverage: Not explicitly named in the paper's four-point list but implied by the "temporal reasonableness" checks — the schedule must span from the start date to the end date without gaps.

Planning soundness (8 checks):

No temporal overlaps: Activities must not have overlapping time slots. Two activities at 09:00–10:00 and 09:30–10:30 would trigger a violation.
No excessive idle gaps: Except on transfer days (where transit time is unavoidable), gaps between consecutive activities must not exceed two hours. This prevents the agent from inserting long empty periods that would make the itinerary unrealistic.
Reasonable daily start/end bounds: Activities should respect typical waking hours and not schedule attractions at 2:00 AM unless explicitly requested.
Plausible durations: Attractions must have durations exceeding 30 minutes and matching the tool's recommended visit time within ±1.5 hours. Meal durations must be 45–90 minutes.
Opening hour compliance: Attraction visits and meals must fall within the POI's opening hours, with a buffer of up to 30 minutes allowed (start up to 30 min before opening, end up to 30 min after closing). Stricter compliance is preferred.
Intercity transit buffers: Flights require a 1.5–2.5 hour "Flight Check-in" activity before departure. Trains require 15–30 minute arrival before departure as a buffer (incorporated into the local transportation activity, not a separate check-in). The verifier checks that these buffers exist and that the check-in time + flight duration doesn't exceed schedule bounds.
Spatial logic: The route formed by consecutive activity locations should be sensible — no unnecessary long-distance backtracking. Restaurant-to-adjacent-activity distance should typically stay within 10 km (up to 20 km tolerated if necessary). Local transportation durations must match get_route_estimate tool outputs within 20 minutes.
Experience diversity: No repeated restaurants or attractions across the itinerary (unless explicitly requested by the user). The verifier checks for duplicate POI IDs.
Product consistency: Attraction ticket quantities must equal the number of travelers; restaurant set-menu quantities must match the party size; hotel room capacity must accommodate the group. The verifier cross-references the plan's products arrays against the number_of_people field.

User constraint verification: Beyond these 12 general constraints, the verifier applies the validator functions V(e, i) for each user-specific constraint e to each relevant POI selection in the plan. For example, if the user required "restaurants with rating ≥ 4.5," the verifier checks whether every restaurant in the plan satisfies restaurant.stars ≥ 4.5 (for that specific user constraint, not just the general planning soundness rating check — these are separate checks). The count of violated user constraints is F_user.

Aggregation into loose and strict metrics:

The strict metric demands zero violations across all three categories:

$\text{Overall}_\text{Strict} = \mathbb{I}(F_\text{feas} = 0 \wedge F_\text{sound} = 0 \wedge F_\text{user} = 0)$

where F_feas is the number of violated feasibility constraints, F_sound is the number of violated planning soundness constraints, and F_user is the number of violated user-specific constraints. I(...) is the indicator function, so the result is binary — 1 for perfect compliance, 0 otherwise.

The loose metric relaxes soundness and user constraints while keeping feasibility inviolate:

$\text{Overall}_\text{Loose} = \mathbb{I}(F_\text{feas} = 0 \wedge F_\text{sound} \leq 2 \wedge F_\text{user} \leq 1)$

This allows up to two soundness violations (e.g., slightly suboptimal routing, a minor duration violation) and one user constraint violation (e.g., a restaurant at 4.4 stars when 4.5 was requested) while still counting the task as successful. The feasibility requirement remains absolute — a plan with invalid JSON, nonexistent POIs, or missing components is always a failure.

Why this dual metric? The strict metric measures whether the agent can produce a completely correct, deployment-ready plan. This is what matters for fully autonomous deployment where no human reviews the output. The loose metric measures whether the agent can produce a plan that's essentially correct — feasible and mostly sound, with only minor spec violations that a human could quickly fix. This captures the scenario where the agent serves as an assistant to a human planner who does final review. The paper's results show that many models that score near zero on the strict metric achieve non-trivial loose scores (e.g., Claude-Sonnet-4.5 with thinking achieves 32.0 loose but only 8.5 strict overall), indicating they produce plans that are structurally reasonable but have small errors that compound to failure under strict checking.

Turn-level evaluation during interaction: While the final metrics apply to the terminal plan, the evaluation pipeline also computes per-turn scores using the same rubric functions. These intermediate scores feed into the user simulator's issue pool — if the verifier detects that the agent's current plan violates a user constraint, the simulator may inject an error-reporting behavior in the next turn. This creates a closed loop where evaluation drives interaction, and the agent must respond to concrete, automatically-detected issues rather than generic user complaints.

GTPO: Group Turn-Level Preference Optimization

GTPO (Section 4.2) is an online multi-turn reinforcement learning algorithm designed to address the credit assignment problem in long-horizon tool-use dialogues. The fundamental challenge is that in a 15-turn conversation with 150 tool calls, the final plan's correctness is a function of decisions made at every turn, but not all turns contribute equally — and the contribution of early decisions may only become apparent much later. Standard outcome-based RL (giving the same reward to every action if the final plan is correct) provides a weak and noisy signal. Standard per-turn RL without inter-turn structure ignores that turn t's reward is heavily influenced by what happened at turns 1...t-1.

GTPO operates on groups of K complete multi-turn rollouts sampled from the current policy π_θ for the same dialogue context x. Each rollout is a sequence of user-model turns:

$\tau^{(k)} = \{(u_1, a_1^{(k)}), \dots, (u_{T_k}, a_{T_k}^{(k)})\}, \quad k = 1, \dots, K$

where u_t is the user input at turn t (identical across rollouts at turn t, since the user simulator responds to the agent's previous output), a_t^{(k)} is the assistant's response (including tool calls and plan output) in rollout k at turn t, and T_k is the number of completed turns in rollout k (may vary across rollouts if some terminate early due to context limits or infeasibility declarations).

The algorithm proceeds through three stages of reward transformation before computing advantages and performing policy updates.

Stage 0: Raw Turn-Level Reward Computation

For each turn t in each rollout k, the evaluator computes per-constraint binary scores. Let I_t be the set of constraints applicable at turn t. For each constraint i ∈ I_t, the verifier checks whether the agent's current plan satisfies it, producing c_{t,i}^{(k)} ∈ {0, 1}. Additionally, basic feasibility is a hard gate: I_feas^{(k,t)} = 1 if the plan at turn t in rollout k has zero feasibility violations (F_feas = 0), and 0 otherwise.

The raw turn reward aggregates constraint satisfaction rates, gated by feasibility:

$r_{t,\text{raw}}^{(k)} = \mathbb{I}_{\text{feas}}^{(k,t)} \cdot \frac{1}{|\mathcal{I}_t|} \sum_{i \in \mathcal{I}_t} c_{t,i}^{(k)}$

where |I_t| is the number of applicable constraints at turn t, and the sum computes the fraction of satisfied constraints.

What it computes: For each turn, count how many user constraints are satisfied, divide by the total number of constraints, and multiply by 1 if the plan is feasible (0 otherwise). This produces a value between 0 and 1 — 1 means all constraints satisfied and the plan is structurally valid, 0 means either the plan is infeasible or no constraints are satisfied, and fractional values mean partial constraint satisfaction with a feasible plan structure.

Why this form: The feasibility gate is multiplicative rather than additive because an infeasible plan is useless regardless of how many specific constraints it satisfies — you can't deploy a plan with nonexistent hotels or unparseable JSON, even if the hotel choice would have satisfied the user's budget constraint. The constraint fraction normalizes for varying numbers of constraints across turns (some turns introduce additional constraints, so the number of constraints grows over the dialogue), enabling cross-turn comparison. However, this raw reward has a critical flaw: the score at turn t is heavily influenced by decisions at turns 1...t-1, making it a poor signal for the contribution of turn t specifically.

Stage 1: Global Instruction Normalization

The first transformation addresses the problem that different constraints have different baseline difficulty. Some constraints (e.g., "restaurant rating ≥ 3.0") are nearly always satisfied by random sampling; others (e.g., "hotel within 1 km of city center with specific amenities and under a tight budget") are rarely satisfied. Without normalization, the reward signal is dominated by easy-to-satisfy constraints, and the agent receives weak gradient signal for improving on hard ones.

For each constraint i and each rollout k, let T_i be the set of turns where constraint i applies. The paper computes the mean and standard deviation of that constraint's satisfaction scores across those turns within rollout k:

$\mu_i^{(k)} = \frac{1}{|\mathcal{T}_i|} \sum_{t \in \mathcal{T}_i} c_{t,i}^{(k)}, \quad \sigma_i^{(k)} = \sqrt{\frac{1}{|\mathcal{T}_i|} \sum_{t \in \mathcal{T}_i} (c_{t,i}^{(k)} - \mu_i^{(k)})^2}$

Then each constraint's score is z-score normalized within its rollout:

$\hat{c}_{t,i}^{(k)} = \frac{c_{t,i}^{(k)} - \mu_i^{(k)}}{\sigma_i^{(k)} + \epsilon}, \quad t \in \mathcal{T}_i$

where ε is a small constant to prevent division by zero.

The globally normalized turn reward is computed using these normalized constraint scores:

$r_t^{(k)} = \mathbb{I}_{\text{feas}}^{(k,t)} \cdot \frac{1}{|\mathcal{I}_t|} \sum_{i \in \mathcal{I}_t} \hat{c}_{t,i}^{(k)}$

What it computes: For each constraint, compute how many standard deviations above or below its rollout-mean satisfaction rate the current turn's score is. A constraint that is satisfied at turn t when most turns fail it receives a large positive normalized score (deserving credit); a constraint that is satisfied at turn t when most turns also satisfy it receives a near-zero score (no special credit). These normalized scores are then averaged across constraints at the turn, again gated by feasibility.

Why this form (per-constraint, per-rollout normalization): Normalizing per-constraint rather than globally across all constraints is essential because constraints have different inherent difficulty scales — mixing them in a single normalization would wash out the signal from difficult constraints. Normalizing per-rollout rather than across rollouts at the same turn preserves relative ordering within each rollout while removing the cross-constraint scale differences. The z-score specifically maps each constraint's satisfaction pattern to a zero-mean, unit-variance scale, which has the property that consistent performance (always satisfied or always violated) produces near-zero normalized scores, while changes in satisfaction produce large-magnitude scores — this connects naturally to the next stage's focus on incremental improvement.

What would be wrong without it: Without global instruction normalization, the agent would optimize primarily for easy constraints (which dominate the raw reward magnitude) and might learn to ignore hard constraints entirely, since the marginal reward for satisfying a hard constraint would be swamped by the base reward from easy ones.

Stage 2: Turn-Wise Reward Differencing

The second transformation addresses the problem of reward inheritance: a turn that slightly degrades the plan might still receive a higher raw reward than an earlier turn that built the plan from scratch, simply because the later turn inherited most constraints already satisfied. The raw reward at turn t conflates the contribution of turn t with the contributions of all previous turns. To isolate the incremental contribution of each turn, GTPO subtracts the previous turn's reward:

$d_t^{(k)} = \begin{cases} r_1^{(k)}, & t = 1, \\ r_t^{(k)} - r_{t-1}^{(k)}, & t \geq 2. \end{cases}$

However, this simple differencing has a problem when the previous turn was infeasible. If turn t-1 produced an infeasible plan, its reward is zero (due to the feasibility gate), so the differencing would just be r_t - 0 = r_t, treating the current turn as if it solved the entire problem from scratch — which over-credits it, since earlier turns laid groundwork (even if they failed feasibility).

GTPO handles this by substituting the maximum reward among all rollouts at the previous turn for infeasible turns:

$r_{t-1}^{\max} = \max_{k' \in \mathcal{K}_{t-1}} r_{t-1}^{(k')}$

where K_{t-1} is the set of rollouts that are evaluable at turn t-1. The differencing for t ≥ 2 becomes:

$d_t^{(k)} = r_t^{(k)} - \mathbb{I}_{\text{feas}}^{(k,t-1)} r_{t-1}^{(k)} - \left(1 - \mathbb{I}_{\text{feas}}^{(k,t-1)}\right) r_{t-1}^{\max}$

In plain language: if the previous turn in this rollout was feasible, subtract its actual reward from the current reward (standard differencing). If the previous turn was infeasible, subtract the best reward any rollout achieved at that turn — the rationale being that this rollout's current turn should be credited for recovering from infeasibility beyond what the best alternative achieved without that recovery.

What it computes: For each turn, the change in normalized constraint satisfaction relative to the previous turn (or relative to the group's best at the previous turn, if the previous turn was infeasible). Positive values mean improvement; negative values mean degradation; near-zero means no change. The first turn's differenced reward is just its raw normalized reward (no predecessor to compare against).

Why this form: The differencing converts the absolute reward trajectory (which conflates inheritance with contribution) into a marginal contribution signal. A turn that maintains all previously satisfied constraints and adds one more gets credit only for the addition, not for the constraints it inherited. A turn that breaks a previously satisfied constraint gets penalized even if its absolute reward is still high (because the differenced reward will be negative). This is the key insight that distinguishes GTPO from outcome-based RL: it rewards improvement rather than absolute state, making the credit assignment much sharper for long-horizon tasks where early turns do heavy lifting and later turns refine.

The substitution of r_max for infeasible predecessors prevents an over-crediting artifact: without it, a rollout that jumps from infeasibility to partial feasibility would get full credit for all satisfied constraints, as if the current turn achieved them all — when in reality, earlier turns may have set up constraint satisfaction that only became "visible" once the feasibility gate opened. By using the group max as the baseline, GTPO credits only the excess improvement beyond what other rollouts managed without the same recovery.

Stage 3: Turn-Level Reward Normalization

The final transformation addresses a practical training stability issue: different turns have different variance in their differenced rewards. Early turns might show high variance (small changes in initial constraint satisfaction have large downstream effects), while later turns might show low variance (fine-tuning near an optimum). Directly using raw differenced rewards as advantages would cause the policy gradient to be dominated by high-variance turns.

For each turn t, let K_t be the set of rollouts that are complete and evaluable at that turn. GTPO normalizes the differenced rewards across rollouts at turn t:

$\mu_t = \frac{1}{|\mathcal{K}_t|} \sum_{k \in \mathcal{K}_t} d_t^{(k)}, \quad \sigma_t = \sqrt{\frac{1}{|\mathcal{K}_t|} \sum_{k \in \mathcal{K}_t} (d_t^{(k)} - \mu_t)^2}$

The turn-level advantage for rollout k at turn t is:

$A_t^{(k)} = \frac{d_t^{(k)} - \mu_t}{\sigma_t + \epsilon}, \quad k \in \mathcal{K}_t$

To ensure stable normalization statistics, GTPO only normalizes turns where the number of evaluable rollouts is at least half the group size: |K_t| ≥ K/2. Turns that exceed the context budget are masked in the loss and do not contribute to the policy update.

Critical property: advantages are turn-local. A_t^{(k)} depends only on other rollouts at the same turn t — it does not propagate forward or backward. Each turn gets its own independent advantage estimate. This prevents early-turn variance from contaminating later-turn training signals and vice versa.

What it computes: For each turn, how many standard deviations above or below the group mean this rollout's differenced reward is. A differenced reward that is much higher than other rollouts at the same turn produces a large positive advantage; one that is much lower produces a large negative advantage.

Why this form: Turn-level normalization removes the turn-dependent variance scale, ensuring that every turn contributes equally to the training signal regardless of its inherent noisiness. The minimum sample-size requirement (≥ K/2) prevents normalization on degenerate groups where one or two rollouts happened to complete at a turn while most terminated — such statistics would be unreliable. Masking incomplete turns prevents the model from being penalized for decisions in rollouts that ran out of context budget before reaching a natural conclusion.

Final Objective: PPO with Turn-Level Advantages

GTPO optimizes a clipped surrogate objective with per-token KL penalty, using the turn-level advantages computed above. For a batch of dialogue contexts and sampled rollout groups:

$J_{\text{GTPO}}(\theta) = \mathbb{E}_{x, \{\tau^{(k)}\}_{k=1}^K} \left[ \frac{1}{K} \sum_{k=1}^K \frac{1}{T_k} \sum_{t=1}^{T_k} \frac{1}{L_{k,t}} \sum_{j=1}^{L_{k,t}} m_{t,j}^{(k)} \left( \min \left( \rho_{t,j}^{(k)}(\theta) A_t^{(k)}, \text{clip}(\rho_{t,j}^{(k)}(\theta), 1 - \epsilon, 1 + \epsilon) \right) - \beta D_{\text{KL}}(\pi_\theta \| \pi_{\text{ref}}; h_{t,j}^{(k)}) \right) \right]$

where:

K is the number of rollouts in the group (set to 8 in experiments)
T_k is the number of completed turns in rollout k
L_{k,t} is the number of tokens in the assistant's response at turn t of rollout k
m_{t,j}^{(k)} ∈ {0, 1} is a token-level mask: 1 for tokens in completed, evaluable turns within context budget, 0 for tokens in truncated or incomplete turns
A_t^{(k)} is the turn-level advantage from Stage 3
ρ_{t,j}^{(k)}(θ) = π_θ(a_{t,j}^{(k)} | h_{t,j}^{(k)}) / π_{θ_old}(a_{t,j}^{(k)} | h_{t,j}^{(k)}) is the importance sampling ratio between the current policy and the policy that generated the rollout, for token j at turn t in rollout k
clip(ρ, 1 - ε, 1 + ε) clips the ratio to prevent destructively large policy updates
D_KL(π_θ || π_ref; h_{t,j}^{(k)}) is the per-token KL divergence between the current policy and a reference policy (typically the SFT checkpoint), preventing the policy from drifting too far from its initialization
β is the KL penalty coefficient (set to 0.05 in experiments)
ε is the PPO clipping threshold (standard value, not separately specified in the paper)

The expectation is over dialogue contexts x and rollout groups sampled from the current policy interacting with the user simulator. The outer averages (over rollouts, turns, and tokens) give equal weight to each token within each evaluable turn, and equal weight to each turn within each rollout.

What it computes: A PPO-style policy gradient objective where the advantage for each token at turn t is A_t^{(k)} — the same scalar for all tokens in that turn. The min of the clipped and unclipped ratio prevents the policy from changing too much in a single update (standard PPO). The KL penalty adds an additional regularization force pulling the policy toward the reference.

Why this form: Using a single turn-level advantage for all tokens in a turn is the key architectural choice. It means the policy is rewarded or penalized for the entire turn's contribution (measured by the differenced normalized reward) rather than for individual token decisions. This is appropriate because the "goodness" of a turn in this benchmark is holistic — it depends on the complete plan output and the tool calls made, not on individual word choices. Token-level credit assignment would be both noisy and misaligned with the actual evaluation metric, which scores the plan as a whole.

Training hyperparameters (Table 6): GTPO uses GRPO as the advantage estimator (not GAE), with train_batch_size = 32, max_prompt_length = 9300 tokens, learning rate 1e-6, ppo_mini_batch_size = 32, ppo_micro_batch_size_per_gpu = 1, KL loss coefficient 0.05 with low_var_kl type, no entropy bonus (entropy_coef = 0), gradient checkpointing and activation/parameter/optimizer offloading enabled, Ulysses sequence parallelism size 8, SGLang as the inference backend, tensor model parallelism size 8, GPU memory utilization 0.5, n = 8 rollouts per prompt, temperature 1.0 for sampling, max_model_len = 32768 tokens, response_length_one_turn = 8192 tokens, log_prob_micro_batch_size_per_gpu = 2, distributed across 4 nodes with 8 GPUs each (32 GPUs total).

SFT Data Construction: Error-Feedback Repair and Trajectory Filtering

Before GTPO training, the paper constructs a supervised fine-tuning dataset to provide a cold-start policy (Section 4.1, Figure 2 left). Starting from 120,000 synthesized prompts, the pipeline uses DeepSeek-V3.2 (no-think mode) to sample trajectories. However, due to the task difficulty, only approximately 500 trajectories are fully correct on the first attempt — far too few for effective SFT.

Rather than discarding the remaining ~119,500 trajectories, the paper applies a three-round error-feedback repair procedure. For each incorrect trajectory, the pipeline fixes the tool calls and outputs (preserving the agent's reasoning structure) and provides only the error feedback — listing which constraints were violated and how — as additional context. The model then generates a revised plan. This process repeats for up to three rounds. Trajectories that pass evaluation after any round are retained. This procedure produces approximately 9,000 trajectories that pass evaluation.

To mitigate the risk that repaired trajectories might "hack" the evaluation (satisfying constraints through superficial fixes that don't reflect genuine planning improvement), the paper applies an additional filter: only trajectories that achieve full scores on both reasoning and planning dimensions (not just constraint satisfaction) are kept. This yields approximately 3,000 high-quality trajectories, which are combined with Toucan data (Xu et al., 2025, a tool-augmented instruction dataset) for SFT training.

The SFT training itself uses standard next-token prediction on these trajectories. The paper does not specify separate SFT hyperparameters, implying standard settings for the Qwen2.5 model family.

Why the repair procedure rather than more sampling? Simply sampling more trajectories from DeepSeek-V3.2 would have diminishing returns — the model's pass rate on these hard tasks is low, and collecting 120k correct trajectories would require orders of magnitude more sampling. The repair procedure exploits the observation that most incorrect trajectories are nearly correct — they have reasonable tool use and coherent reasoning but fail on a small number of specific constraints. Providing explicit error feedback enables targeted fixes that are much cheaper than full re-sampling. The filtering step (requiring full reasoning/planning scores) then removes trajectories where the repair was superficial, ensuring the SFT data maintains quality.

For RL data construction, the paper samples once over the same 120,000 inputs using the SFT-trained model (not DeepSeek-V3.2) and retains trajectories satisfying a relaxed criterion: F_feas = 0 AND (F_sound + F_user ≤ 5). This yields 7,040 samples. The relaxed criterion is necessary because the SFT model, while better than the base model, still produces many imperfect trajectories — and GTPO needs a diverse set of trajectories (some good, some mediocre, some bad) to compute meaningful advantages through the normalization procedure. Using only perfect trajectories would give GTPO no negative signal to learn from.

Design Choices and Their Justifications: A Synthesis

Why a generator-validator architecture for constraints rather than LLM-based evaluation? LLM judges are increasingly common in benchmark evaluation (used in Chatbot Arena, AlpacaEval, etc.), but they introduce several problems for this setting: they are stochastic (same plan might get different scores), they can be gamed (agents might learn to produce plans that look good to the judge but are actually wrong), and they are expensive at scale (evaluating thousands of trajectories with a large LLM judge would cost more than the agent's own inference). Rule-based validators are deterministic, ungamable (they check ground-truth database facts), and cheap (simple lookup operations). The cost is that the paper must define validators for each constraint type — but this is a one-time engineering cost amortized over all evaluations.

Why paired modification chains rather than free-form user interactions? Free-form interactions (letting a user simulator generate arbitrary queries without constraint on the underlying task structure) would make it impossible to guarantee that evaluation is well-defined. If the user can change requirements arbitrarily, there may be no "correct" plan to check against — or worse, the plan that satisfied requirements at turn 5 might be invalid by turn 6 through no fault of the agent. Modification chains provide a middle ground: the underlying constraint structure is predetermined and guarantees solvability (at the final step after all rollbacks), but the presentation of those constraints — their timing, phrasing, and interaction style — is handled by the user simulator with substantial diversity. This decouples task coherence (guaranteed by the synthesis pipeline) from interaction richness (provided by the simulator).

Why per-constraint global normalization rather than per-turn? Normalizing per-turn (computing means and standard deviations across constraints within each turn) would conflate constraint difficulty with turn difficulty. A turn with many easy constraints would have a high raw mean, making even fully satisfying all its constraints appear "average" after normalization — this would perversely penalize good performance on easy turns. Per-constraint normalization across turns preserves the relative difficulty signal: satisfying a hard constraint is always rewarded more than satisfying an easy one, regardless of which turn it occurs in.

Why reward differencing rather than advantage estimation with a learned value function? Standard PPO uses a learned value function V(s) to compute advantages A = r + γV(s') - V(s). In the multi-turn tool-use setting, learning an accurate value function is extremely difficult because the state space is enormous (arbitrary conversation histories, tool call results, partial plans) and the credit assignment problem means the value of a state is poorly determined by immediate outcomes. Reward differencing provides a simpler, model-free alternative that directly computes marginal contributions without requiring a value function approximator. The cost is that it requires pairwise comparison with the previous turn's reward, which assumes the reward function changes smoothly — but the paper's normalization stages are designed to make this assumption approximately true.

Why the substitution of r_max for infeasible predecessors? Without it, a rollout that transitions from infeasibility to feasibility would receive an advantage equal to the full reward at the transition turn, crediting that single turn for all constraint satisfaction even though earlier turns (despite being infeasible) may have set up the structure that made the satisfaction possible. Using the group max as the baseline ensures that the advantage reflects only the excess improvement over what other rollouts achieved — if every rollout that became feasible at turn t had similar reward, the advantages would be near zero, preventing the policy from overfitting to the specific timing of the feasibility transition.

Why is the advantage turn-local (no temporal discounting, no bootstrapping)? In a 15-turn dialogue, decisions at turn 3 affect what's possible at turn 12, but the agent at turn 12 should not be credited or penalized for what happened at turn 3 — it can only work with the state it inherits. Turn-local advantages implement this philosophy: each turn is evaluated on how much it improved (or worsened) the plan given the state it received. Temporal credit flows implicitly through the differencing (if turn 3 made a great decision that enabled turn 12's success, turn 3 gets positive advantage and turn 12 gets a smaller advantage reflecting only its marginal refinement), but turn 12 is never directly penalized for turn 3's mistakes. This is more appropriate for tool-use dialogues than standard RL credit assignment because the "state" at each turn is the conversation history and partial plan, which the agent cannot retroactively change.

4. Key Insights and Innovations

Innovation 1: The Interaction of Capabilities — Not Any Single Capability — Is What Defines Real-World Agent Difficulty

The paper's most fundamental intellectual contribution is the insight that existing benchmarks fail not because they miss individual capabilities, but because they fail to test their interaction. Prior work has evaluated constraint following, multi-tool orchestration, long-horizon reasoning, and multi-turn adaptation as separable problems — often in dedicated benchmarks that isolate each dimension. TravelPlanner tests planning under many constraints but in a single turn with no behavioral dynamics. τ²-Bench tests constraint adherence under verbose policies but with shallow per-turn interactions and no long-horizon goal management. COMPASS and VitaBench add behavioral diversity but without the depth of constraint interaction (global rules, spatiotemporal dependencies, joint feasibility across tool chains) that real deployment demands.

The distinctive move here is not "we made a harder benchmark." It is the recognition that the difficulty ceiling in agent deployment is a product of capability interactions, not a sum. An agent that handles 12 constraints in a single pass may collapse when those same constraints are introduced progressively across 10 turns because each turn forces re-planning from an inherited partial plan that may lock in earlier suboptimal choices. An agent that gracefully handles clear instruction updates may fail when instructions are deliberately ambiguous (AIS) because the tendency to over-commit to interpretations interacts destructively with the requirement to maintain global feasibility — an incorrect early assumption cascades into a plan that cannot be salvaged by later clarification without rollback. An agent that correctly rejects infeasible constraint combinations (FIT) must simultaneously maintain enough plan state to resume correctly after rollback, testing whether feasibility awareness and version control can coexist.

This interaction-centric framing is what makes TRIP-Bench genuinely novel rather than "TripTailor with more turns and tools." The paper's Table 1 comparison is not just a feature checklist — it is an argument that a benchmark's value lies in the joint distribution of capabilities it forces agents to exercise, not in any individual column. This is why models that perform reasonably on single-turn travel planning (TripTailor, TravelPlanner) or on multi-turn simple interactions (τ²-Bench) score near zero on TRIP-Bench's hard subsets under the strict metric — the interaction effects create failure modes that no individual-dimension benchmark ever exposes.

The evidence for this interaction effect is in the per-subset results of Table 2. GPT-5.2 with thinking achieves 66.0 loose / 49.0 strict on Easy (where constraints are fewer and interactions simpler) but drops to 18.0 loose / 0.0 strict on FIT (where feasibility awareness, rollback, and re-planning must all work together) and 20.0 loose / 0.0 strict on AIS (where ambiguity handling, clarification, and constraint satisfaction interact). The fact that strict scores drop to zero on FIT and AIS even for the strongest model — while remaining non-trivial on Easy — demonstrates that the difficulty is not mainly from individual constraint complexity but from the interaction of reasoning capabilities under behavioral pressure. If FIT only tested "can the agent detect infeasibility" and AIS only tested "can the agent ask clarifying questions," stronger models would score non-zero. The zero scores indicate that the combination — detect infeasibility while maintaining enough plan context to resume after rollback; ask clarifying questions while avoiding premature commitment that violates later-revealed preferences — is what breaks current systems.

This insight matters beyond travel planning. It implies that progress on agent benchmarks should be measured not by improving individual capability metrics but by improving performance on capability-combination stress tests — subsets designed specifically to force interactions between reasoning dimensions. A model that improves on constraint satisfaction in isolation but degrades when constraints interact with behavioral dynamics has not actually improved for deployment. The paper's difficulty-controlled splits (LIT, FIT, AIS, PMR) provide a template for constructing such interaction stress tests in other domains.

Innovation 2: Difficulty as a Controllable Synthesis Variable, Not a Post-Hoc Label

The paper's second conceptual contribution is a methodology for generating tasks with controllable, multidimensional difficulty rather than labeling existing tasks by difficulty after the fact. Most benchmarks inherit difficulty from their data source — MATH problems come with human-assigned difficulty levels, coding benchmarks use contest divisions, dialogue benchmarks rely on naturally occurring conversation complexity. The benchmark creator can measure difficulty but cannot systematically manipulate it along specific axes. TRIP-Bench inverts this: difficulty is a synthesis parameter, specified before task generation, with independent control over plan complexity (trip length, city count, constraint count) and interaction complexity (behavior categories, modification chain length, ambiguity injection).

This is not merely an engineering convenience. It enables the paper's central diagnostic capability: disentangling what makes tasks hard. Because the synthesis pipeline can independently vary the number of constraints and the types of user behaviors while holding other factors constant, the benchmark can answer questions like "Is this model's degradation on hard tasks driven by constraint count or by behavioral complexity?" and "Does thinking help more with plan complexity or with interaction complexity?" The difficulty tiers in Table 4 are not discovered correlations — they are designed axes, making analysis causal rather than observational.

The specific mechanism that enables this controllability is the generator-validator architecture described in Section 3.2. By defining each constraint rubric through paired functions G(e) and V(e, i) — one that produces the feasible ID set and one that checks satisfaction — the pipeline can guarantee that any combination of constraints it assembles has a known feasible set size, can verify solvability, and can systematically introduce infeasibility (for FIT) by selecting constraint combinations whose intersection is empty. This is qualitatively different from the approach in prior travel-planning benchmarks. TripTailor (the paper's own prior work) collected real user requirements and labeled difficulty post-hoc, meaning it could report that certain tasks were harder but couldn't explain why (more constraints? harder constraints? both?) or guarantee that "hard" tasks were hard in the intended way rather than accidentally hard due to database artifacts.

The practical significance of controllable difficulty extends beyond this paper. The synthesis methodology — define a rubric taxonomy with generator/validator pairs, construct modification chains with redundancy pruning, compose tasks at specified difficulty tiers by sampling from the taxonomy — is domain-agnostic. It could be applied to trip planning in other regions (different city databases), to other planning domains (conference scheduling, logistics routing, event planning), or to any task where constraints can be formalized as verifiable predicates over structured choices. The paper's release of the benchmark, evaluation scripts, and supporting resources is intended to enable this transfer.

Innovation 3: Structured Credit Assignment as the Bottleneck for Multi-Turn Tool-Use RL

The third conceptual contribution is diagnostic rather than algorithmic: the identification of credit assignment across turns with inherited state as the central challenge in multi-turn tool-use reinforcement learning, and the demonstration that naive outcome-based RL or single-turn RL formulations are fundamentally mismatched to this structure.

Prior work on tool-use RL (SimpleTIR, Search-R1, AgentGym-RL) treated multi-turn interaction as concatenated single-turn episodes — the full conversation history is the prompt, the agent produces one response, and the reward is the final outcome. This formulation ignores that the agent at turn 7 is working with a state (partial plan, constraint satisfaction status, tool call results) it inherited from its own decisions at turns 1–6. A reward at turn 15 for a correct final plan provides the same signal to all 15 turns, even though turn 3 may have done the heavy lifting of selecting a hotel that satisfied 8 of the user's 10 constraints, while turn 14 merely adjusted a restaurant time by 15 minutes. The gradient signal is diluted across tokens that contributed very differently.

The paper's insight — embodied in GTPO but conceptually independent of the specific algorithm — is that the unit of credit should be the turn-level marginal improvement, not the absolute state quality. Turn 3 should be credited for the constraints it satisfied that turn 1 didn't, not for constraints it inherited from turn 1. Turn 12 should be credited (or penalized) for what it changed relative to turn 11, not for the overall plan quality at turn 12. This reframes multi-turn RL from "optimize the final outcome" to "optimize the improvement trajectory."

Why is this a conceptual innovation rather than just good engineering? Because it challenges a default assumption in the RL-for-LLMs literature: that per-token or per-turn rewards should reflect the absolute quality of the state. Most RLHF and tool-use RL work gives the same reward to all tokens in a response (outcome-based) or uses a learned value function to estimate per-token advantages (actor-critic). GTPO's reward differencing argues that in multi-turn settings with strong state inheritance, the relative change is more informative than the absolute value. A turn that produces a plan scoring 0.8 (out of 1.0) might be penalized if the previous turn scored 0.9 — it degraded the plan — while a turn scoring 0.6 might be rewarded if the previous turn scored 0.2 — it substantially improved a bad situation. Outcome-based RL would reward the 0.8 turn more than the 0.6 turn, exactly backward from the actual contribution of each turn to eventual success.

The paper provides evidence for this diagnostic in the ablation study (Table 3). Comparing GTPO variants:

GTPO without Global Instruction Normalization and Turn Reward Differencing (i.e., basically per-turn normalized outcome rewards) achieves 32 loose / 12 strict on Easy and 16 loose / 0 strict on Mid.
Adding Global Instruction Normalization (GTPO w/o TRD) improves to 34 loose / 10 strict on Easy and 20 loose / 0 strict on Mid — better loose scores because constraints are better calibrated, but strict scores don't improve because the "reward inheritance" problem means turns aren't properly penalized for degrading previously satisfied constraints.
Full GTPO achieves 35 loose / 13 strict on Easy and 18 loose (slightly lower mid-loose than w/o TRD) / 0 strict on Mid — the strict score improvement on Easy (from 10 to 13) is the key signal that reward differencing helps the model avoid the specific failure of losing previously satisfied constraints during later refinement.

The fact that strict scores improve most from TRD — which specifically addresses the "did this turn break something that was working?" question — validates the diagnosis that credit inheritance, not just constraint difficulty calibration, is a primary bottleneck.

This insight generalizes beyond GTPO. Any multi-turn RL method for tool-use agents must grapple with the fact that later turns operate on inherited state, and that the credit for good inherited state should go to the turns that established it. GTPO's differencing is one solution; learned value functions with proper temporal structure, hierarchical credit assignment, or counterfactual baseline methods could be others. But the conceptual prerequisite — recognizing that the problem exists and that naive outcome rewards get the credit assignment systematically wrong — is the paper's contribution.

Innovation 4: Verifier-Driven Interaction as a Training Signal Generator

The fourth contribution is a methodological insight about how to close the loop between evaluation and training in tool-use benchmarks. Most benchmarks are pure evaluation instruments: you run your agent, you get a score, you go back to the lab and try to improve your agent. The benchmark itself provides no signal about what went wrong or how to fix it. TRIP-Bench is designed so that its evaluation pipeline generates structured, actionable feedback that can drive both user simulation (injecting issue reports at the right turns) and training data repair (the three-round error-feedback procedure in Section 4.1).

The enabling mechanism is the rule-based verifier (Section 3.5). Because all constraint checks are deterministic functions of the agent's plan and the database, the evaluation system can produce, for every turn of every trajectory, a precise inventory of which constraints are violated and how. This inventory serves three functions:

User simulation: The simulator's issue pool is populated by verifier output — when the agent's plan violates a constraint, the simulator can generate a turn where the user points out the specific error, creating a realistic interaction pattern (error reporting) that tests whether the agent can respond to concrete, accurate feedback.
Training data repair: The SFT data construction pipeline uses the same verifier output to tell the data-generation model exactly which constraints are violated, enabling targeted revision rather than blind re-sampling. This is what makes the 9k repaired trajectories possible from 120k attempts — without structured error feedback, the repair model would have to re-derive what went wrong from scratch.
RL reward computation: GTPO's per-constraint binary scores c_{t,i}^{(k)} come directly from the verifier. The granularity of per-constraint (rather than per-plan) rewards is what enables global instruction normalization — without it, there would be no per-constraint satisfaction signal to normalize.

This verifier-driven architecture is not standard in agent benchmarks. Most benchmarks use either LLM judges (stochastic, expensive, no structured error decomposition), simple string matching (no constraint-level granularity), or human evaluation (not scalable for training data generation). The paper's paired generator-validator functions for each rubric type make this possible — the validator is the same code path used in evaluation, training data validation, and RL reward computation, creating a unified signal pipeline.

The significance is that this blurs the line between "benchmark" and "training environment." TRIP-Bench is not just something you measure against; it is something you can train with, using the same verifier that evaluates you to generate repair feedback, RL rewards, and simulated user complaints. This is a design philosophy that could be adopted by other benchmarks: if you define your evaluation criteria as verifiable predicates over structured outputs (not just final scores), those predicates become reusable training signals. The paper demonstrates the full pipeline — benchmark → verifier → simulator feedback → training data repair → SFT → RL with verifier rewards — as an integrated system rather than separate components.

5. Experimental Analysis

Evaluation Methodology

Dataset. All experiments use the TRIP-Bench benchmark described in Section 3, spanning 40 cities with 6k+ attractions, 80k+ hotels, 400k+ restaurants, and 1M+ products. The benchmark is partitioned into three difficulty tiers (Easy, Mid, Hard) with the Hard tier further split into four behavioral subsets: LIT (Long Interaction Task), FIT (Feasible–Infeasible Transition), AIS (Ambiguous Intent Shifts), and PMR (Plan Merge Redirect). The paper does not specify exact sample counts per split, but the synthesis pipeline generates approximately 6,000 two-city and 4,000 three-city itinerary seeds, with tasks sampled from these seeds at each difficulty level.
Base model(s). The paper evaluates 16 model configurations spanning 8 model families: Kimi-K2 (Bai et al., 2025), Qwen3-235B-A22B (Yang et al., 2025), GLM-4.7 (Zeng et al., 2025), DeepSeek-V3.2 (Liu et al., 2025a), Gemini-3 (Flash and Pro variants), GPT-5.2, Claude-Sonnet-4.5, and Qwen2.5 (14B-Instruct and 32B-Instruct for training experiments). Models are tested both with and without explicit reasoning ("thinking") modes enabled, except for Qwen2.5-14B/32B which are used only in training experiments and evaluated without thinking. The Qwen2.5 variants are chosen as training baselines because they represent open-weight models at scales amenable to the RL training infrastructure (14B serves as the primary ablation platform, 32B tests scalability of GTPO gains). The broader evaluation set spans both open-source (Kimi, Qwen, GLM, DeepSeek) and closed-source (Gemini, GPT, Claude) models to establish performance ceilings across model capabilities.
Metrics. Two aggregate metrics are reported: Overall_Strict and Overall_Loose, as defined in Section 3.5. Overall_Strict requires zero violations across all three error categories — basic feasibility (F_feas = 0), planning soundness (F_sound = 0), and user constraints (F_user = 0). Overall_Loose keeps feasibility strict but allows up to two soundness violations and one user-constraint violation (F_feas = 0 ∧ F_sound ≤ 2 ∧ F_user ≤ 1). Both metrics are binary indicators per task, and reported percentages are averages over the task set for a given split. Additionally, the paper reports per-constraint score rates (Figure 4), pass@k metrics (Figure 5), and per-turn intermediate scores during training (Figure 6). All evaluation is rule-based using the verifier functions described in Section 3.5 — no LLM judges or human annotators are used for scoring, ensuring deterministic, reproducible evaluation.
Baselines. For the main benchmark evaluation (Table 2), the baselines are the off-the-shelf model configurations listed above — there is no single "baseline method" since the evaluation measures absolute model performance rather than comparing training algorithms. For the training experiments (Table 3), four baselines are compared against GTPO: (1) Base model — Qwen2.5-14B-Instruct or Qwen2.5-32B-Instruct with no fine-tuning, evaluated zero-shot; (2) +SFT — the same base models fine-tuned on the ~3,000 high-quality trajectories produced by the three-round error-feedback repair procedure (Section 4.1); (3) +GRPO (ST) — single-turn GRPO training where each turn is treated as an independent episode and only the final-turn reward is used; (4) +GRPO (MT) — multi-turn GRPO training where turn-level rewards are computed but without GTPO's hierarchical normalization components (Global Instruction Normalization, Turn Reward Differencing, or both). The SFT baseline also implicitly serves as the cold-start policy for all RL variants, since GTPO and GRPO are initialized from the SFT checkpoint. For the FLOPs-matched comparison in Section 7 (if any — but the paper does not report one; this is handled in the analysis of Figure 3), the performance vs. cost analysis uses all evaluated models as data points rather than a controlled pretraining-vs-inference comparison.
Generation budget / compute accounting. The paper does not measure compute in FLOPs or GPU-hours for fair comparison across model sizes. Instead, it reports (1) number of dialogue turns (x-axis in Figure 3 left), (2) output tokens in units of 10k (Figure 3 middle), and (3) average reasoning cost in USD on a log scale (Figure 3 right). For training experiments, compute is reported as the model scale (14B vs. 32B parameters) and training algorithm (SFT, GRPO, GTPO), with training hyperparameters in Table 6 specifying distributed configuration (4 nodes × 8 GPUs = 32 GPUs total). The paper does not provide wall-clock training time or total FLOPs for GTPO training. For evaluation, all models use default temperature settings (temperature 0.7 when unspecified), and the paper notes that trained models are only evaluated on Easy and Mid subsets because the Hard subset often requires context lengths exceeding 128k tokens, which is beyond the maximum context length supported by the Qwen2.5 models used for training.
Cross-validation / statistical protocol. The paper does not report cross-validation or statistical significance testing for the main benchmark results in Table 2. For the training experiments in Table 3, the paper reports results on fixed Easy and Mid splits without specifying whether these are single evaluation runs or averages over multiple seeds. The user simulator reliability is manually evaluated on 20 randomly sampled trajectories (104 turns) for instruction consistency, achieving 98% accuracy, and 10 AIS trajectories (62 turns) for ambiguity and style fidelity, achieving an average 4.7/5 rating. These manual evaluations serve as quality control for the simulator rather than statistical validation of model performance. The absence of confidence intervals, standard deviations, or multiple random seeds for model evaluation is a limitation — with 50–100 tasks per difficulty split (estimated from the 500-task test split in the prior MATH example, though TRIP-Bench's exact split sizes are not specified), score differences of a few percentage points may not be statistically distinguishable.

Main Quantitative Results

Benchmark Difficulty: Most Models Score Near Zero Under Strict Evaluation

Table 2 presents the headline results. Under the strict metric, performance is extremely poor across all models and splits, with the best overall strict score reaching only 18.5% (GPT-5.2 with thinking). Several striking patterns emerge:

On Easy tasks, the strict metric reveals substantial variance across model families. Non-thinking models achieve at most 22.0% (Gemini-3-Flash), with most clustering in the 0–12% range. Thinking models dramatically improve Easy-strict performance: GPT-5.2 with thinking reaches 49.0%, DeepSeek-V3.2 with thinking reaches 31.0%, and Claude-Sonnet-4.5 with thinking reaches 27.0%. However, not all thinking models benefit equally — Qwen3-235B-A22B-Thinking scores 0.0% on Easy-strict, and Kimi-K2-Thinking reaches only 5.0%, suggesting that thinking capability alone is insufficient without strong base planning ability. The gap between non-thinking and thinking variants is most pronounced on Easy tasks, with improvements of 26–47 percentage points for the strongest models (DeepSeek-V3.2: 5.0 → 31.0; GPT-5.2: 2.0 → 49.0).

On Mid tasks, the strict metric remains at or near zero for most models. Only GPT-5.2 with thinking reaches 13.0%, DeepSeek-V3.2 with thinking reaches 9.0%, and Claude-Sonnet-4.5 with thinking reaches 6.0%. Non-thinking models are uniformly at 0.0% on Mid-strict except DeepSeek-V3.2 (3.0%), which is an outlier among non-thinking models — it achieves better Mid-strict than several thinking models (Gemini-3-Pro thinking: 0.0%, GLM-4.7 thinking: 0.0%). This suggests DeepSeek-V3.2's architecture or training provides some mid-level planning capability even without explicit chain-of-thought decoding.

On Hard subsets, the strict metric is essentially zero across all models, with only two exceptions: GPT-5.2 with thinking achieves 14.0% on Hard LIT-strict and 10.0% on Hard PMR-strict, and Claude-Sonnet-4.5 with thinking achieves 2.0% on Hard PMR-strict. Hard FIT-strict and Hard AIS-strict are zero for every model without exception — not a single model across 16 configurations can produce a fully correct, verifiable plan under the FIT (feasibility transitions with rollbacks) or AIS (ambiguous intent shifts) interaction patterns. This is the paper's strongest evidence that the interaction of capabilities — reasoning under infeasibility, ambiguity resolution, and constraint satisfaction — creates genuinely new difficulty that no current system surmounts.

Under the loose metric, performance is substantially higher but still challenging. GPT-5.2 with thinking achieves 45.0% overall loose, followed by DeepSeek-V3.2 with thinking at 40.0% and Claude-Sonnet-4.5 with thinking at 32.0%. However, even loose scores drop sharply on Hard subsets — GPT-5.2 achieves 44.0% on LIT-loose but only 18.0% on FIT-loose and 20.0% on AIS-loose. The gap between loose and strict scores widens on harder subsets, with almost no model bridging it on FIT or AIS — the best FIT-loose is 18.0% (GPT-5.2 thinking) with 0.0% strict, and the best AIS-loose is 26.0% (DeepSeek-V3.2 thinking and Gemini-3-Flash thinking) with 0.0% strict. This indicates that models are producing plans that are structurally feasible and mostly sound (passing loose criteria) but contain specific constraint violations that trigger strict failure — a pattern consistent with incremental correctness that breaks under exhaustive verification.

A notable performance inversion on Easy-loose: Gemini-3-Flash without thinking achieves 36.0% loose — higher than Gemini-3-Pro without thinking at 44.0%? No — correction: Gemini-3-Flash without thinking achieves 36.0% loose, which is lower than Gemini-3-Pro without thinking at 44.0% loose. However, Gemini-3-Flash with thinking (44.0% loose, 25.0% strict) outperforms Gemini-3-Pro with thinking (42.0% loose, 11.0% strict) on Easy-strict by 14 percentage points, despite being the smaller/cheaper model. This suggests that thinking mode can sometimes compensate for base model scale, at least on Easy tasks — though this pattern does not hold on Mid or Hard splits where Pro models regain advantage.

The Qwen3-235B-A22B-Thinking anomaly: This model scores 0.0% across all splits under both strict and loose metrics — the worst performance of any thinking model by a wide margin. The paper does not analyze this failure specifically, but it is striking given that the non-thinking Qwen3-235B-A22B achieves 16.0% Easy-loose and 2.0% Easy-strict, and the thinking variant is presumably the same base model with chain-of-thought decoding enabled. This complete collapse under thinking mode suggests a systematic failure mode — possibly the model generates reasoning traces that consume context budget without producing actionable plans, or its thinking process leads to tool call patterns incompatible with the benchmark's strict formatting requirements.

Scaling Behavior: Thinking Improves Performance, But With Diminishing Marginal Returns

Figure 3 examines the relationship between performance (loose metric) and resource usage across three dimensions: number of turns, output tokens generated, and inference cost (USD):

Performance vs. turns (Figure 3 left): Non-thinking models show a flat or slightly negative relationship — performance does not improve with more dialogue turns, and in some cases (notably Qwen3-235B-A22B at 5.8% loose) is essentially zero regardless of turn count. Thinking models show positive scaling, with performance improving approximately linearly with turn count. However, the slope varies dramatically: DeepSeek-V3.2 thinking achieves ~40% at the upper turn count while GPT-5.2 thinking reaches ~45%, but the costs (Figure 3 right) differ by more than an order of magnitude.

Performance vs. output tokens (Figure 3 middle): A stronger linear relationship emerges — thinking models generating more output tokens tend to achieve higher loose scores. This is consistent with chain-of-thought reasoning producing longer outputs that enable better planning. However, the relationship is not deterministic: Claude-Sonnet-4.5 thinking generates roughly 50k output tokens (estimated from the 5 on the x-axis in units of 10k) and achieves ~32% loose, while DeepSeek-V3.2 thinking generates roughly 35k output tokens and achieves ~40% — fewer tokens, better performance. This indicates that token count alone does not determine quality; the efficiency of reasoning matters.

Performance vs. cost (Figure 3 right): The relationship is approximately logarithmic — large increases in cost yield diminishing improvements in performance. GPT-5.2 thinking costs roughly $2.50 per task on average and achieves ~45% loose, while DeepSeek-V3.2 thinking costs approximately$ 0.25 per task (about 10% of GPT-5.2's cost) and achieves ~40% loose. The paper highlights this as evidence that "for error-tolerant applications, DeepSeek-V3.2 offers a highly economical alternative without pursuing peak performance at all costs." The gap between these two models is much larger under the strict metric (GPT-5.2: 18.5% overall strict vs. DeepSeek-V3.2: 10.5% overall strict), suggesting that the cost-performance tradeoff depends on the stringency of verification.

The trend lines in Figure 3 use dashed fits, and the paper notes a "pronounced generational gap" between open-source models (DeepSeek-V3.2, Kimi-K2, Qwen3, GLM-4.7) and leading closed-source systems (GPT-5.2, Claude-Sonnet-4.5, Gemini-3-Pro). Open-source models cluster at lower performance levels across all resource axes, with DeepSeek-V3.2 as the notable exception that approaches closed-source performance at much lower cost.

Multi-Turn vs. Single-Turn: Global Consistency Erodes Across Turns

Figure 4 decomposes constraint satisfaction by domain and type, comparing single-turn and multi-turn settings for DeepSeek-V3.2 thinking:

The top-15 highest-error constraints (Figure 4 left) are broken down by domain (transportation, attraction, hotel, restaurant) and constraint type (Global vs. Pointwise). Global constraints — those requiring cross-activity consistency, such as temporal feasibility across the full schedule or spatial routing logic — dominate the error distribution. Pointwise constraints (individual POI requirements like "rating ≥ 4.5") appear less frequently among the highest errors. This supports the paper's argument that the interaction of constraints, not individual constraint difficulty, is the primary failure mode.

Single-turn vs. multi-turn performance (Figure 4 right) shows a consistent pattern: single-turn accuracy exceeds multi-turn by approximately 10 percentage points on average for strong global constraints. Table 5 quantifies this across all splits. For DeepSeek-V3.2 thinking, single-turn loose scores are higher than multi-turn loose scores on Easy (79% vs. 71%), Mid (53% vs. 41%), AIS (32% vs. 26%), and PMR (30% vs. 20%). The gap is most pronounced on Easy-strict: single-turn achieves 27% while multi-turn achieves 31% — actually slightly higher for multi-turn on this metric, but the pattern reverses on Mid-strict (10% vs. 9%) and Hard PMR-strict (4% vs. 2%).

The "no issue" ablation (multi-turn without issue reporting) shows substantially worse performance: Easy-loose drops to 68% (vs. 79% single-turn), Mid-loose to 32% (vs. 53%), and Hard PMR-loose to 0% (vs. 30% single-turn). This indicates that the user simulator's error-reporting behavior — pointing out specific constraint violations based on verifier output — is providing crucial guidance that the agent uses to correct its plans. When issue reporting is removed, the agent lacks the feedback loop that enables progressive refinement, and performance degrades sharply, especially on harder tasks.

The interpretation nuance: The paper frames multi-turn degradation as "global consistency gradually erodes," but the "no issue" results suggest an alternative interpretation: multi-turn interaction helps only when the user provides specific, accurate error feedback. Without such feedback, the additional turns introduce more opportunities for the agent to make mistakes without correction, net-degrading performance. This has implications for deployment — if real users are less accurate at diagnosing planning errors than the verifier-driven simulator, multi-turn interaction may not provide the same benefits observed with synthetic issue reporting.

GTPO Training Results: Consistent Gains Over SFT and GRPO, Scaling to Larger Models

Table 3 reports the training experiments on Qwen2.5-14B-Instruct and Qwen2.5-32B-Instruct, evaluated on Easy and Mid splits only (Hard splits exceed the 128k context limit of Qwen2.5 models):

Base models score zero on all splits under both strict and loose evaluation — Qwen2.5-14B-Instruct achieves 0 across the board, as does Qwen2.5-32B-Instruct. This establishes that the base models, without any fine-tuning, cannot produce feasible travel plans in this benchmark. Given that these are strong general-purpose models (Qwen2.5-32B is competitive with much larger models on standard benchmarks), this underscores the domain-specific difficulty of TRIP-Bench — general instruction-following and reasoning capability does not transfer to multi-constraint tool-use planning without targeted training.

SFT provides a non-trivial cold start: Training on the ~3,000 high-quality repaired trajectories lifts Qwen2.5-14B-Instruct from 0 to 16 Easy-loose / 4 Easy-strict / 8 Mid-loose / 0 Mid-strict. For Qwen2.5-32B-Instruct, SFT achieves 32 Easy-loose / 3 Easy-strict / 5 Mid-loose / 0 Mid-strict. The gap between loose and strict scores — 16 vs. 4 for 14B, 32 vs. 3 for 32B — is notable: the 32B model is much better at producing mostly-correct plans (high loose) but not better at producing fully correct plans (low strict). The SFT data construction procedure (three-round error feedback repair) successfully transfers planning ability but the repaired trajectories may embed patterns that satisfy constraints without teaching the model to avoid all violation categories simultaneously.

GRPO baselines underperform GTPO: On Qwen2.5-14B-Instruct, single-turn GRPO achieves 29 Easy-loose / 0 Easy-strict (worse strict than SFT's 4), and multi-turn GRPO achieves 30 Easy-loose / 4 Easy-strict. Both GRPO variants outperform SFT on loose metrics but the strict regression for single-turn GRPO (from 4 to 0) is concerning — optimizing for outcome rewards may cause the model to sacrifice the precise constraint satisfaction that strict evaluation demands. Multi-turn GRPO partially recovers this (matching SFT's 4 strict) but does not improve on it.

GTPO achieves the best results: Full GTPO on Qwen2.5-14B-Instruct reaches 35 Easy-loose / 13 Easy-strict / 18 Mid-loose / 0 Mid-strict. This is a 3-point loose improvement and a 9-point strict improvement over SFT on Easy, and a 10-point loose improvement on Mid. On Qwen2.5-32B-Instruct, GTPO achieves 49 Easy-loose / 21 Easy-strict / 40 Mid-loose / 5 Mid-strict — substantially exceeding the 14B results and notably achieving a non-zero Mid-strict score (5%) for the first time among trained models. The paper claims GTPO-trained Qwen2.5-32B-Instruct "surpasses Gemini-3-Pro under the same evaluation" — comparing Easy-loose 49 vs. 44 and Easy-strict 21 vs. 12 from Table 2, this holds. However, Gemini-3-Pro (without thinking) achieves 44 Easy-loose / 12 Easy-strict while GTPO-32B achieves 49/21, and comparing on Mid: Gemini-3-Pro achieves 9 Mid-loose / 0 Mid-strict while GTPO-32B achieves 40 Mid-loose / 5 Mid-strict — a much larger margin on Mid. This is a genuinely strong result, showing that targeted multi-turn RL training on a 32B open model can exceed the performance of a much larger closed-source model (Gemini-3-Pro's parameter count is not disclosed but is presumed to be substantially larger).

Training curves (Figure 6) show that GTPO training converges and stabilizes, but the paper does not report the number of training steps, total wall-clock time, or the variance across random seeds. The curve shape is not described in detail — the figure is referenced but not discussed in the main text, appearing only in the appendix.

Ablation Studies and Robustness Checks

Global Instruction Normalization (GIN) ablation: GTPO without GIN and without TRD (i.e., only Turn-level Reward Normalization remains) achieves 32 Easy-loose / 12 Easy-strict / 16 Mid-loose / 0 Mid-strict on Qwen2.5-14B (Table 3). This is already better than SFT (16/4/8/0) and competitive with GRPO (30/4/16/0), showing that per-turn normalization alone provides meaningful training signal. However, the loose score on Easy (32) is lower than full GTPO (35), and adding GIN alone (GTPO w/o TRD: 34/10/20/0) improves Easy-loose to 34 and Mid-loose to 20 while Easy-strict slightly decreases from 12 to 10. The paper attributes this to GIN calibrating constraint satisfaction across dialogue history — improving average rewards (loose scores) — while the "reward inheritance" issue (later turns being credited for earlier turns' work) continues to hinder the complete pass rate (strict metric). The Mid-loose improvement from 16 to 20 with GIN addition suggests that constraint calibration matters more for medium-difficulty tasks where multiple constraint categories interact.

Turn Reward Differencing (TRD) ablation: The full GTPO configuration (adding TRD to GIN+TRN) achieves 35 Easy-loose / 13 Easy-strict / 18 Mid-loose / 0 Mid-strict. Compared to GTPO w/o TRD (34/10/20/0), TRD improves Easy-strict (+3) but reduces Mid-loose (-2). This is the key evidence for the credit assignment hypothesis: reward differencing helps the model avoid breaking previously satisfied constraints (improving strict pass rate on Easy), but the sharper per-turn credit signal may cause the model to be more conservative on Mid tasks, slightly reducing the rate of producing mostly-correct plans while not yet achieving fully correct ones (Mid-strict remains 0). The paper frames this as TRD "prioritizing incremental gains, substantially boosting the complete pass rate while maintaining high overall rewards," which is supported for Easy but the Mid tradeoff is not fully explained.

Turn-level Reward Normalization (TRN) implicitly ablated: All GTPO variants include TRN because without it, the differenced rewards would have uncontrolled variance across turns, making PPO training unstable. The paper does not report a "GTPO without TRN" variant, likely because training would fail to converge. This is a reasonable omission — TRN is a training stability mechanism, not a contribution being tested — but it means we cannot separate TRN's contribution from the other components.

Single-turn vs. multi-turn GRPO: Multi-turn GRPO (30/4/16/0) outperforms single-turn GRPO (29/0/12/0) on Easy-strict (+4) and Mid-loose (+4). This confirms that training on multi-turn trajectories with per-turn rewards, even without GTPO's hierarchical normalization, is better than treating each turn independently. The single-turn variant's Easy-strict regression to zero (from SFT's 4) is a negative result that the paper does not discuss in detail — it suggests that optimizing for independent per-turn outcomes can cause the model to unlearn the cross-turn consistency that SFT provided, a form of catastrophic forgetting in RL fine-tuning.

Model scale ablation: Comparing GTPO on Qwen2.5-14B (35/13/18/0) vs. Qwen2.5-32B (49/21/40/5), the gains from scaling are substantial: +14 Easy-loose, +8 Easy-strict, +22 Mid-loose, +5 Mid-strict. The disproportionate improvement on Mid-loose (+22 vs. +14 on Easy-loose) suggests that scale helps more with the harder planning tasks, consistent with scaling laws observed in other domains. The emergence of non-zero Mid-strict at 32B (5%) but not 14B (0%) indicates a potential capability threshold — below some critical model capacity, fully correct plans on medium-difficulty tasks are essentially unattainable regardless of training algorithm.

User simulator reliability manual evaluation (Appendix E, reported in Section 5): On 20 randomly sampled trajectories (104 turns), instruction ID consistency — measured as the fraction of turns where key constraints from issued instructions remain present without contradiction or unwanted specification — achieved 98%. On 10 AIS trajectories (62 turns), ambiguity capture and style fidelity received an average rating of 4.7/5. These are strong results supporting the simulator's reliability, but the sample sizes are small (20 and 10 trajectories, respectively), and the evaluation is internal (five volunteer annotators, motivated by personal interest). The paper does not report inter-annotator agreement metrics, making it difficult to assess the reliability of the 4.7/5 style fidelity score — a single score without variance information is not a robust validation.

Pass@k analysis (Figure 5): The paper reports pass@k (probability that at least one of k sampled plans is correct) for varying k. Pass@k increases with k, indicating non-trivial exploratory ability — the model can sometimes produce correct plans when allowed multiple attempts. However, pass@1 remains low and strict evaluation is substantially worse than loose across all k. The avg^k metric (average score across k samples) stays stable across k, suggesting the benchmark's difficulty is consistent rather than being driven by a few outlier hard tasks that dominate the failure distribution. This is a robustness check for the benchmark itself — if difficulty were driven by a small number of impossible tasks, avg^k would increase as k grows and the model occasionally passes those tasks; the stability of avg^k indicates that difficulty is broadly distributed.

User behavior breakdown (Figure 4 and Table 5): The decomposition of errors by constraint type (Global vs. Pointwise) and the comparison of multi-turn vs. single-turn performance serve as implicit ablations of the interaction complexity axis. The finding that multi-turn performance degrades most sharply on global constraints (requiring cross-activity consistency) while remaining competitive on local pointwise constraints aligns with the paper's claim that interaction effects — maintaining global consistency across turns where constraints are introduced incrementally — are the primary failure mode, rather than individual constraint difficulty.

Critical Assessment

Claim 1: "TRIP-Bench poses a significant challenge" with even advanced models achieving at most 50% success on the easy split and below 10% on hard subsets.

This claim is strongly supported by Table 2. The best model (GPT-5.2 with thinking) achieves 66.0% Easy-loose but only 49.0% Easy-strict — and this is on the easiest split. On every Hard subset, strict scores are near or exactly zero: Hard FIT-strict and AIS-strict are 0.0% for all models, Hard LIT-strict is at most 14.0% (GPT-5.2 thinking), and Hard PMR-strict is at most 10.0% (GPT-5.2 thinking). The claim that "performance drops below 10% on hard subsets" is actually an overestimate for FIT and AIS under strict evaluation — the true figure is 0%.

However, there is a genuine weakness: the paper does not report the number of tasks per split. Without knowing whether Easy contains 50, 100, or 500 tasks, we cannot assess the statistical reliability of percentage differences. A 5 percentage point difference on a 50-task split is within sampling noise; on a 500-task split it is more meaningful. The synthesis pipeline generates ~6,000 two-city and ~4,000 three-city seeds, but how many are sampled into each difficulty tier, and how many constitute each Hard subset, is not specified. This is a significant omission for a benchmark paper — users need to know the sample sizes to interpret score differences.

Additionally, the benchmark's difficulty calibration relies on the synthesis pipeline guaranteeing solvability (Section 3.2: |C| ≥ (4–10) × trip_length). The paper does not report what fraction of generated tasks were verified as actually solvable by any model or by exhaustive search. If some tasks in the benchmark are, despite the pipeline's feasibility checks, actually impossible (due to bugs in the generator/validator functions, database inconsistencies, or spatiotemporal interactions the pipeline didn't model), then zero scores on those tasks reflect benchmark error rather than model incapability. A human baseline or an exhaustive-solver baseline would address this concern but is not provided.

Claim 2: "Thinking dramatically improves performance" but "remains insufficient for fully satisfying Hard cases."

This claim is supported with clear quantitative evidence. On Easy-strict, the best non-thinking model (Gemini-3-Flash) achieves 22.0% while the best thinking model (GPT-5.2) achieves 49.0% — a 27-point absolute gain. On Overall-strict, the best non-thinking is 5.5% (Gemini-3-Flash) vs. 18.5% (GPT-5.2 thinking), a 13-point gain. These are large, consistent improvements across model families.

However, the claim that thinking is "insufficient" for Hard cases is empirically supported but conceptually ambiguous. It is possible that thinking would be sufficient given longer context windows — the paper notes that Hard subsets require >128k tokens, which exceeds the Qwen2.5 context limit but not necessarily the limits of the frontier models. If GPT-5.2 with thinking had more inference budget or a longer context window, would Hard-strict scores improve? The paper cannot distinguish "thinking is fundamentally insufficient" from "thinking needs more tokens than current architectures support" without controlled context-length experiments.

Moreover, the Qwen3-235B-A22B-Thinking anomaly (0.0% on all splits) suggests that thinking can also be actively harmful for some models — it is not a uniformly beneficial intervention. The paper does not analyze this failure, which could reveal important boundary conditions on when chain-of-thought reasoning helps vs. hurts in tool-use settings. Possibly the Qwen3 model's thinking traces consume context budget without producing structured plans, or its reasoning leads to tool call patterns incompatible with the benchmark's formatting requirements.

Claim 3: "GTPO better aligns training with dynamic user interaction and multi-constraint reasoning, with gains that scale to stronger models."

This claim is supported by Table 3, but with several important qualifications:

The evaluation is limited to Easy and Mid splits. GTPO-trained models are not evaluated on Hard splits at all, because the Qwen2.5 context window (128k) is too small. This means we cannot assess whether GTPO's credit assignment improvements transfer to the interaction patterns (FIT, AIS, PMR) that most distinguish TRIP-Bench from simpler benchmarks. The claim that GTPO "better aligns training with dynamic user interaction" is tested only on interactions up to Mid difficulty — where behavioral diversity includes instruction changes, error reporting, and clarification but not the composite Hard behaviors.
The absolute performance ceiling is low. GTPO-32B achieves 5% on Mid-strict — a genuine improvement over 0%, but still means 95% of Mid tasks are not solved perfectly. The loose scores (40% Mid, 49% Easy) suggest the model is producing mostly-correct plans, but the strict scores indicate persistent small errors. Whether these errors are fixable with more training, better data, or architectural improvements is unclear.
The comparison to Gemini-3-Pro is incomplete. GTPO-32B outperforms Gemini-3-Pro (without thinking) on Easy and Mid, but Gemini-3-Pro with thinking is not compared (Table 2 shows Gemini-3-Pro thinking: 42 Easy-loose, 11 Easy-strict, 16 Mid-loose, 0 Mid-strict). Against the thinking variant, GTPO-32B (49/21/40/5) still wins on all metrics, but the paper's claim of "surpassing Gemini-3-Pro" should specify the configuration.
Training data leakage is a concern. The SFT data is constructed from the same task distribution as the evaluation benchmark (though presumably from a training split). The paper does not describe a train/test split for the benchmark itself — are the Easy and Mid evaluation tasks drawn from the same seed itineraries and constraint combinations used to generate SFT training trajectories? If so, the SFT and GTPO results may partially reflect memorization of specific constraint patterns rather than generalized planning ability.

Claim 4: "Structured turn-level credit assignment yields robust multi-turn gains."

The ablation study (Table 3) provides evidence for this claim, but the evidence is nuanced:

TRD (Turn Reward Differencing) improves Easy-strict from 10 to 13 (GTPO w/o TRD vs. full GTPO), supporting the claim that differencing helps avoid breaking previously satisfied constraints. This is a 3 percentage point improvement — meaningful if the split size is large enough, but the paper does not report sample sizes.
However, TRD reduces Mid-loose from 20 to 18. The paper frames this as TRD "prioritizing incremental gains" but doesn't explain why incremental gains would hurt Mid-loose performance. One possibility: on harder tasks, the model makes fewer improvements per turn (the plan is harder to improve), so reward differencing produces mostly negative advantages (each turn slightly degrades the plan), creating a pessimistic training signal that discourages exploration. This would be a limitation of differencing-based credit assignment — it works well when monotonic improvement is possible but may be counterproductive when search is necessary.
The consistent finding that Mid-strict remains 0% across all GTPO variants (except 5% at 32B scale) suggests that credit assignment improvements alone, without better base planning capability or more training data, cannot bridge the gap to fully correct plans.

Missing experiments that would strengthen the paper:

Human performance baseline. What is human accuracy on TRIP-Bench tasks? Without a human ceiling, it is impossible to know whether 49% Easy-strict is surprisingly high or disappointingly low. The paper implicitly treats the benchmark as a model evaluation tool, but its difficulty claims ("significant challenge," "highly challenging") are relative to model performance — a human baseline would calibrate these claims.
Task solvability verification. For a subset of tasks (especially FIT and AIS), verify that at least one model configuration can solve each task by enumerating the constraint satisfaction space or using a symbolic planner as an oracle. This would distinguish "the task is genuinely unsolvable with current models" from "the task is impossible due to benchmark construction errors."
Context length ablation. Test whether model performance on Hard subsets improves with longer context windows (for models that support them). This would distinguish context-length limitations from fundamental reasoning limitations.
GTPO on Hard splits with larger-context models. Train a model with 256k+ context (if available) and evaluate on Hard subsets. The current training evaluation is limited to Easy/Mid, which underrepresents the benchmark's most distinctive challenges.
Multiple random seeds for training. Report mean and standard deviation over 3–5 training runs for each GTPO variant. The current single-run results cannot distinguish algorithmic improvement from random seed effects, especially given the small difference sizes (2–3 percentage points on some metrics).
SFT data quantity ablation. How much does performance improve with more SFT data? The paper uses ~3,000 trajectories for SFT; would 10k or 30k trajectories (achievable with more repair rounds or more initial sampling) substantially improve performance, or does SFT plateau? This would contextualize GTPO's contribution relative to simpler data-scaling approaches.
Component importance ordering. The ablation removes components cumulatively (full → w/o TRD → w/o GIN,TRD) rather than independently (full, w/o TRD only, w/o GIN only, w/o TRN only). This conflates component contributions — we cannot isolate GIN's effect because it is always removed together with TRD in the most ablated variant.

6. Limitations and Trade-offs

A. Difficulty Estimation Cost: The $4\times$ Efficiency Gain Does Not Account for Simulator Overhead

The assumption or constraint. The headline efficiency results — GTPO improving performance by over 10 percentage points over SFT, GTPO-trained Qwen2.5-32B surpassing Gemini-3-Pro — are measured purely in terms of agent output quality. The training pipeline's computational cost is reported only as hardware configuration (4 nodes × 8 GPUs, Table 6), without wall-clock time, total FLOPs, or monetary cost. Critically, the RL training loop requires an operational user simulator (DeepSeek-V3.2 at temperature 0.7, Section 5.1) and a rule-based verifier that evaluates every turn of every rollout across groups of K = 8 parallel trajectories — the simulator and verifier must run continuously during online RL to generate the per-constraint binary scores and next-turn user queries that GTPO requires. This inference cost is not amortized or included in any reported efficiency metric.

The consequence. A practitioner seeking to apply GTPO to their own domain must budget not only for policy model training (which the paper specifies at 32 GPUs) but also for running a separate, capable LLM as the user simulator and the rule-based verifier at training time. For the 7,040 RL training samples × 8 rollouts per sample × up to 15 turns per rollout × multiple tool calls per turn, the simulator inference cost may dominate the total training budget. In the TRIP-Bench setting, DeepSeek-V3.2 is used as the simulator — a model that itself costs approximately $0.25 per task for single-turn inference (Figure 3 right). Multiplied by the number of simulator calls during RL training, this cost could be substantial. Without reporting it, the paper's claim that GTPO provides an "effective online RL recipe" (Section 1) is incomplete — "effective" should be qualified by cost, not just accuracy.

What evidence exists in the paper. Table 6 lists training hyperparameters but contains no entry for simulator inference cost, simulator model specification, or total training wall-clock time. Section 4.1 reports that 7,040 samples are used for RL training, and Section 4.2 specifies K = 8 rollouts per prompt, with rollouts spanning up to T_k turns. The number of simulator calls per training step can be estimated from these figures, but the paper never performs this calculation or reports the result. Figure 6 (training curve) has an unlabeled x-axis — we cannot determine how many steps or how much compute GTPO training consumed. The manual evaluation of simulator reliability (Appendix E) involved 20 trajectories and 5 annotators, but this is a quality check, not a cost measurement.

Mitigation status. The paper does not acknowledge this as a limitation. It reports training hyperparameters transparently (Table 6) but does not discuss the cost of operating the simulator and verifier during RL training. The introduction frames GTPO as providing "an effective online RL recipe for robust long-horizon training" without qualifying that this recipe requires a capable LLM to serve as the interactive training environment — a dependency that may limit adoption by groups without access to models of DeepSeek-V3.2's caliber for simulation.

B. Hardest Subsets Remain Unsolved Under the Strict Metric: GTPO Was Not Evaluated on FIT, AIS, or PMR

The assumption or constraint. All GTPO training and evaluation (Table 3) is performed exclusively on Easy and Mid difficulty splits. The paper explicitly states (Section 5.1): "For the trained models, evaluation is performed only on the easy and mid subsets, as the hard subset often requires context lengths exceeding 128k tokens, which is beyond the maximum context length supported by the models." The Qwen2.5 models used for training (14B-Instruct, 32B-Instruct) have a 128k context limit, while Hard subsets — particularly LIT (Long Interaction Tasks with 15 turns and ~150 tool calls) — can exceed 200k tokens of context (Section 1, Appendix G example spanning 161+ turns). The four Hard behavioral subsets (LIT, FIT, AIS, PMR) are precisely where the most distinctive interaction challenges reside: recognizing infeasibility and executing rollbacks (FIT), handling deliberate ambiguity (AIS), and maintaining version control across plan merges (PMR). TRIP-Bench's strongest claim to novelty over prior benchmarks is that it tests these composite behaviors — but GTPO is never evaluated on them.

The consequence. The paper's central training contribution cannot be assessed on the benchmarks' most challenging and most distinctive tasks. Table 2 shows that even GPT-5.2 with thinking achieves 0.0% strict on FIT and AIS — these are the subsets where any improvement would be most scientifically significant. GTPO's credit assignment innovations (global instruction normalization to balance constraint difficulty, turn-wise reward differencing to isolate incremental contributions) are precisely motivated by the challenges that Hard subsets amplify: cross-turn consistency under infeasibility, recovery after rollbacks, resolving ambiguity without premature commitment. The ablation study (Table 3) shows that TRD (Turn Reward Differencing) improves Easy-strict from 10 to 13 but reduces Mid-loose from 20 to 18 — a nuanced pattern that might look very different on FIT (where recognizing that no progress is possible and requesting rollback is the correct behavior, which reward differencing might either reward or penalize depending on the baseline). Without Hard-subset evaluation, we cannot determine whether GTPO's structured credit assignment generalizes to the interaction patterns that most distinguish TRIP-Bench from simpler benchmarks, or whether it overfits to the incremental-refinement pattern of Easy/Mid tasks.

What evidence exists in the paper. Table 3 reports Easy and Mid results only. Section 5.1 acknowledges the context-length constraint explicitly: "the hard subset often requires context lengths exceeding 128k tokens, which is beyond the maximum context length supported by the models." The paper does not report any experiments with larger-context models (e.g., fine-tuning a model with 256k+ context window) that could evaluate GTPO on Hard subsets. The Appendix G conversation trajectory shows a Hard task spanning 161+ turns with extensive tool calls — the paper includes this as illustration but does not use such trajectories for training evaluation.

Mitigation status. The paper partially acknowledges this limitation by stating the context-length constraint, but does not frame it as a limitation of GTPO evaluation specifically — it is presented as a practical constraint on the models used. The authors do not suggest training on models with larger context windows as future work, though this is an obvious next step. The limitation is fundamental to the current results: GTPO's effectiveness is demonstrated only on tasks where the interaction pattern is incremental refinement (Easy/Mid) rather than the feasibility transitions, ambiguity resolution, and version control that define the Hard subsets.

C. Single Benchmark Domain: Travel Planning May Not Transfer to Other Tool-Use Settings

The assumption or constraint. TRIP-Bench is a travel-planning benchmark built on a specific database (40 cities, 6k+ attractions, 80k+ hotels, 400k+ restaurants) with 18 domain-specific tools (flight search, hotel search, restaurant search, route estimation, etc.) and 40 travel-specific rubric categories (Section 3.2). GTPO is trained and evaluated exclusively within this domain — its reward normalization components (Global Instruction Normalization over constraint-specific satisfaction scores, Turn-wise Reward Differencing using plan-level feasibility gates) are designed for the travel-planning constraint structure. The paper does not evaluate GTPO or any model on a second domain to test whether the benchmark's difficulty patterns or GTPO's improvements generalize.

The consequence. A practitioner building an agent for customer service, healthcare scheduling, logistics routing, or any non-travel domain cannot determine from this paper whether TRIP-Bench results predict performance in their setting. Travel planning has structural properties that may not generalize: constraints are formalizable as verifiable predicates over database lookups (enabling the generator-validator architecture and rule-based evaluation), the action space is tool calls against a fixed API, and "correctness" is defined by constraint satisfaction rather than open-ended quality. In a domain where correctness is subjective (dialogue quality, creative writing) or where constraints cannot be deterministically verified (legal compliance, medical appropriateness), neither TRIP-Bench's evaluation methodology nor GTPO's reward structure would directly apply. The paper's claim that TRIP-Bench "advance[s] practical long-horizon interactive agents" (Section 1) and that GTPO provides "an effective online RL recipe" (Section 1) is stated in general terms, but the evidence is entirely domain-specific.

What evidence exists in the paper. All experiments (Tables 2, 3, 5; Figures 3–6) are on TRIP-Bench. The paper does not include any cross-domain evaluation (e.g., applying GTPO-trained models to τ²-Bench or Tool Decathlon). The related work (Section 2) compares TRIP-Bench to benchmarks in other domains at the design level (Table 1), but this is a feature comparison, not an empirical transfer study. The GTPO algorithm description (Section 4.2) uses domain-agnostic notation but its components — Global Instruction Normalization over constraint satisfaction scores, feasibility gating — assume the existence of per-constraint binary verifiers and a well-defined feasibility condition, which are travel-domain-specific artifacts.

Mitigation status. The paper does not claim cross-domain generalization — it positions TRIP-Bench as a travel-planning benchmark and GTPO as a method evaluated on that benchmark. However, the introduction frames the contributions broadly ("advance practical long-horizon interactive agents"), creating an implicit generalization claim that the evidence does not support. The limitation is not acknowledged as such; the paper could have strengthened its claims by either (a) restricting them to travel planning specifically or (b) including a second-domain evaluation, but does neither.

D. The SFT Data Construction Uses an Oracle Model and May Leak Evaluation Information

The assumption or constraint. The SFT training data for GTPO's cold-start policy is constructed by prompting DeepSeek-V3.2 (no-think) on 120,000 synthesized prompts and applying a three-round error-feedback repair procedure using the rule-based verifier (Section 4.1, Figure 2 left). DeepSeek-V3.2 is also one of the strongest models evaluated on TRIP-Bench (Table 2: 40.0% overall loose, 10.5% overall strict with thinking). The same verifier that evaluates final agent performance is used during data construction to provide error feedback for repair and to filter trajectories. The paper does not describe a strict separation between training prompts and evaluation prompts — Section 4.1 states that "120k samples" are synthesized for SFT sampling, and RL training uses "the same 120k inputs," but it is not specified whether these 120k prompts are disjoint from the prompts used for benchmark evaluation in Table 2.

The consequence. Two potential issues arise. First, if the training and evaluation prompts overlap or share substantial structural similarity (same itinerary seeds, similar constraint combinations), the SFT and GTPO results in Table 3 may reflect memorization of specific constraint patterns rather than generalized planning ability. The repair procedure specifically teaches the model to fix common error patterns in DeepSeek-V3.2's outputs — if evaluation tasks exhibit the same error patterns and constraint structures, the SFT model may perform well without having learned robust planning. Second, the use of DeepSeek-V3.2 as the data generation model means the SFT data inherits whatever systematic biases or failure modes that model exhibits — the SFT policy is learning to imitate a model that itself achieves only 18.5% overall strict (Table 2). The repair procedure mitigates this by filtering for trajectories that pass evaluation, but the underlying reasoning patterns in the repaired trajectories still originate from DeepSeek-V3.2. GTPO is then initialized from this SFT policy and trained with RL — improvements over the SFT baseline may reflect the RL algorithm's ability to correct DeepSeek-V3.2-specific errors rather than general multi-turn planning improvement.

What evidence exists in the paper. The paper does not report a train/test split for the benchmark or specify whether SFT data prompts are held out from evaluation. Section 4.1 describes the SFT data construction at a high level but provides no information about prompt overlap with evaluation splits. The fact that RL training "sample[s] once over the same 120k inputs" suggests a fixed prompt set — but whether this set is the evaluation set, a subset of it, or a disjoint training set is unspecified. This is a significant methodological gap: in a benchmark paper, training/evaluation separation is a basic requirement for valid claims about generalization.

Mitigation status. The paper does not acknowledge this as a potential limitation. The data construction section (4.1) describes the pipeline without discussing contamination risks. Standard benchmark practice would require an explicit statement that training prompts are disjoint from evaluation prompts, and ideally a description of how the split was constructed. The absence of this information means that GTPO's gains over the Base model (0 → 49 Easy-loose) cannot be confidently attributed to learning generalizable planning skills rather than fitting to a specific prompt distribution.

E. No Human Baseline or Solvability Oracle: The Difficulty Ceiling Is Unknown

The assumption or constraint. The paper repeatedly characterizes TRIP-Bench as "highly challenging" and "a significant challenge," with scores interpreted as evidence of model limitations (e.g., Section 5.2: "performance is extremely poor even on the Easy subset, with many models near zero accuracy"). However, no human performance baseline is reported, and no solvability oracle (exhaustive search, symbolic planner, or constraint solver) is run to determine the fraction of tasks that are genuinely solvable — as opposed to unsolvable due to database inconsistencies, generator/validator bugs, or spatiotemporal interactions the synthesis pipeline did not model.

The consequence. When GPT-5.2 with thinking achieves 49.0% Easy-strict, we cannot determine whether this means (a) the model is missing 51% of tasks that a competent human could solve, indicating substantial room for improvement, or (b) some fraction of those 51% contain subtle infeasibilities that the pipeline's feasibility checks missed, making 49% close to the true ceiling. If the true solvability ceiling for Easy-strict is, say, 70% (due to a small fraction of tasks with undetected infeasibilities), then 49% represents substantial model failure. If the ceiling is 50%, then GPT-5.2 is essentially saturating the benchmark and the remaining "failures" are benchmark artifacts. The paper's central claim — that TRIP-Bench reveals "substantial limitations of current models" (Section 5.2) — depends on the solvability ceiling being well above observed performance. Without establishing this ceiling, the difficulty claims are relative to model performance, not absolute.

The FIT and AIS subsets are particularly concerning. Every model scores 0.0% strict on FIT and AIS (Table 2). The paper interprets this as models failing to handle feasibility transitions and ambiguity (Sections 5.2, 6), but an alternative explanation is that the FIT and AIS task construction pipeline contains a systematic error — for example, the rollback mechanism in FIT might not correctly restore feasibility in all cases, or the ambiguity patterns in AIS might sometimes create genuinely unresolvable underspecification. If even one task per subset is unsolvable-by-construction, the strict metric (which requires zero errors across all constraints) would be zero for that task regardless of model quality, dragging down the aggregate score.

What evidence exists in the paper. The paper provides no human baseline, no exhaustive-solver baseline, and no per-task solvability certificate beyond the pipeline's internal feasibility checks (|C| ≥ (4–10) × trip_length and validator-based verification, Section 3.2). The quality control process (Section 3.3) involves "prompt-based model scoring plus manual review" and "two-stage validation" where full plans are sampled and manually checked for repairability — but this is a construction-phase quality filter, not a solvability guarantee on the final benchmark instances. The paper does not report what fraction of generated tasks were rejected during quality control or what specific infeasibility patterns were detected. The user simulator reliability evaluation (Appendix E) is a necessary but insufficient validation — it checks that the simulator behaves consistently, not that the underlying tasks are solvable.

Mitigation status. The paper partially acknowledges the need for quality control (Section 3.3) but does not address the absence of human or oracle baselines. The construction pipeline's feasibility checks (|C| ≥ (4–10) × trip_length, validator intersection) provide a local feasibility guarantee (individual POI selections exist that satisfy constraints), but do not guarantee global feasibility (a complete itinerary exists satisfying all constraints simultaneously with spatiotemporal consistency). The paper states that manual review checks "whether flagged issues are repairable," implying that some generated tasks are flagged as potentially problematic — but the rate of flagging and the repair success rate are not reported. Without these numbers, the benchmark's solvability ceiling remains unknown, and claims about model failure must be interpreted cautiously.

F. Latency and Serial Dependency: Sequential Multi-Turn Interaction Is Inherently High-Latency

The assumption or constraint. TRIP-Bench tasks require agents to engage in multi-turn dialogues (up to 15 turns, Section 1) where each assistant turn involves iterative tool calls (50–150+ total, Table 1) and each new user turn depends on the agent's previous response — evaluated by the verifier and processed by the user simulator before the next query is generated. This architecture is inherently serial: the agent cannot begin planning its response to turn t+1 until it has received the user's query at turn t+1, which cannot be generated until the verifier has processed turn t's output. GTPO's training framework amplifies this serial dependency by requiring K = 8 complete multi-turn rollouts per prompt, each of which must run to completion (or context truncation) before advantages can be computed (Section 4.2).

The consequence. Even if GTPO achieves higher accuracy than SFT or GRPO at equal generation budgets, the wall-clock latency of GTPO training and GTPO-trained inference is substantially higher than alternatives. During training, the simulator and verifier must run sequentially for each turn of each rollout — with 7,040 prompts × 8 rollouts × up to 15 turns, this is potentially hundreds of thousands of sequential simulator calls, each requiring LLM inference (DeepSeek-V3.2) plus rule-based verification. During deployment, a GTPO-trained agent making 50–150 tool calls across 15 turns will have end-to-end latency dominated by the cumulative tool-call and response-generation time, which is orders of magnitude higher than a single-turn agent. The paper reports performance vs. number-of-turns (Figure 3 left) and performance vs. inference cost in USD (Figure 3 right), but never reports performance vs. wall-clock time. For latency-sensitive applications (interactive user-facing agents where users wait for responses), a method that achieves higher accuracy but takes minutes per turn may be less deployable than a faster but slightly less accurate alternative.

The serial dependency also limits parallelism. While multiple rollouts during GTPO training can be parallelized across GPUs (the paper uses 32 GPUs, Table 6), the turns within each rollout are strictly sequential — turn t+1's user query depends on turn t's agent output. This means the critical path through training cannot be shortened by adding more GPUs beyond the per-rollout parallelism limit. Similarly, at inference time, the agent's tool calls within a turn may be parallelizable (if independent), but the turn-by-turn dialogue structure creates an irreducible serial bottleneck.

What evidence exists in the paper. The paper reports performance against number of turns and output tokens (Figure 3) and inference cost in USD (Figure 3 right), but wall-clock latency is never measured or discussed. Table 6 reports distributed training configuration (4 nodes, 8 GPUs each) but does not report training time. The SFT data construction uses a three-round repair procedure (Section 4.1) that is explicitly serial (each round uses the previous round's output plus error feedback), adding latency to data generation. The paper does not discuss whether the benefits of multi-turn interaction and GTPO's credit assignment justify the latency cost compared to single-turn approaches.

Mitigation status. The paper does not acknowledge latency or serial dependency as a limitation. The evaluation framework is designed for batch evaluation where latency is not a primary concern, and the training framework assumes access to substantial distributed compute (32 GPUs). However, the paper's positioning — "advancing practical long-horizon interactive agents" (Section 1) and targeting deployment at Meituan (a production setting where user-facing latency matters) — creates a tension with the omission of latency analysis. Future work on deploying GTPO-trained agents would need to address the latency implications of multi-turn interaction, possibly through speculation (generating multiple turn responses in parallel), early stopping, or hybrid single-turn/multi-turn policies that use multi-turn refinement only when needed.

7. Implications and Future Directions

How This Work Changes the Landscape

TRIP-Bench represents a reframing of agent evaluation from individual capability testing to capability-interaction stress testing, and GTPO represents a diagnostic contribution identifying credit inheritance as the central bottleneck in multi-turn tool-use RL. Neither is a paradigm shift — the components (constraint-following benchmarks, tool-use environments, PPO-based RL for LLMs) are well-established. The contribution is conceptual integration: showing that the joint exercise of long-horizon planning, multi-constraint reasoning, tool orchestration, and behavioral adaptation creates failure modes that no individually-tested capability predicts, and that naive outcome-based RL systematically misattributes credit across turns in tool-use dialogues.

The most landscape-changing finding is the interaction of difficulty dimensions. Prior work treated constraint count, interaction length, and behavioral complexity as separable axes — a model that improved on one was assumed to be improving overall. TRIP-Bench's Hard subsets (FIT, AIS, PMR) demonstrate that this assumption is false: GPT-5.2 with thinking scores 49.0% Easy-strict but 0.0% on FIT-strict and AIS-strict (Table 2). This is not a smooth degradation — it is a qualitative collapse when feasibility awareness must coexist with ambiguity resolution, or when version control must coexist with constraint satisfaction. The implication for benchmark design is that evaluation suites must include interaction-stress subsets specifically constructed to test capability combinations, not just capability levels. A benchmark reporting only aggregate scores or per-capability breakdowns will miss precisely the failures that matter for deployment.

This finding also reconciles a tension in the multi-turn agent literature. Several prior works reported that multi-turn interaction degrades performance (e.g., Huang et al., 2023, finding LLMs "cannot self-correct reasoning") while others found that iterative refinement helps (e.g., Madaan et al., 2023, on self-refinement). TRIP-Bench's analysis of DeepSeek-V3.2 in single-turn vs. multi-turn settings (Table 5) provides a unified explanation: multi-turn performance exceeds single-turn on local, pointwise constraints where error feedback enables progressive correction, but degrades on global constraints requiring cross-activity consistency, where incremental introduction of requirements erodes coherence. The resolution depends on constraint type and interaction structure, not on a universal "multi-turn helps/hurts" property. This reframes the research question from "does multi-turn interaction improve agents?" to "under what interaction structures and constraint types does multi-turn interaction improve agents, and how do we design training to maximize the improvement while minimizing the degradation?"

The paper also shifts the relative priority of research investments in tool-use agent development. Before this work, the primary bottlenecks were assumed to be (a) base model reasoning capability and (b) search/planning algorithm sophistication. TRIP-Bench's results suggest a different prioritization: (1) verifier quality and robustness is the critical bottleneck, because the entire evaluation and training pipeline (user simulation, error feedback, RL rewards) depends on reliable constraint verification; (2) credit assignment across turns is the critical training bottleneck, because outcome-based rewards provide systematically wrong gradient signals; and (3) context management across long horizons is the critical architectural bottleneck, because Hard subsets require 200k+ tokens that exceed current open-model context windows. Base model scale and search sophistication matter, but their benefits are gated by these three infrastructure-level capabilities — a more powerful model with poor credit assignment or broken context management will still score zero on FIT-strict.

For the RL-for-agents community specifically, GTPO's reward differencing approach challenges the default assumption that absolute state quality is the right optimization target for multi-turn dialogues. The ablation showing that TRD improves Easy-strict (correctness on all constraints simultaneously) while slightly reducing Mid-loose (mostly-correct plans) — from 20 to 18, Table 3 — demonstrates that rewarding improvement rather than absolute quality fundamentally changes what the policy learns. This is a concrete empirical finding, not a theoretical argument: the optimization objective matters, and the standard outcome-reward objective is mismatched to the structure of inherited-state tasks. Future multi-turn RL methods will need to justify their credit assignment scheme against this finding, not just against raw performance.

Follow-Up Research This Work Enables

Training GTPO on Hard subsets using models with extended context windows. The most immediate gap is that GTPO was evaluated only on Easy and Mid splits because Qwen2.5's 128k context limit excludes Hard tasks. A direct follow-up would fine-tune a model with 256k+ context (e.g., a LongLoRA-extended Qwen2.5 variant, or a Gemini/Claude model with accessible fine-tuning APIs) using GTPO and evaluate on FIT, AIS, and PMR subsets. The key question is whether GTPO's credit assignment components — particularly Turn Reward Differencing, which rewards incremental improvement — remain effective when the "correct" action at a turn might be to not improve the plan but instead to declare infeasibility and request rollback (FIT) or ask a clarifying question rather than commit to an interpretation (AIS). In these settings, the differenced reward r_t - r_{t-1} might be zero or negative when the agent correctly identifies infeasibility (because plan quality didn't improve), creating a perverse incentive to hallucinate improvements. A strong follow-up would compare GTPO against a variant where the reward function explicitly credits metacognitive actions (declaring infeasibility, asking clarifying questions) rather than only plan-quality improvements.

Characterizing the solvability ceiling of TRIP-Bench tasks with a human baseline and constraint-solver oracle. The paper's difficulty claims are model-relative — we don't know whether 49% Easy-strict (GPT-5.2 thinking) represents near-saturation or substantial headroom. A rigorous follow-up would: (a) recruit 3–5 human annotators familiar with travel planning to solve a random sample of 50–100 TRIP-Bench tasks (across all difficulty tiers) using the same tool interface, measuring both strict and loose scores as well as time-per-task; (b) implement a constraint-solver baseline (e.g., encoding the generator-validator constraints into a mixed-integer program or SAT formulation and using an off-the-shelf solver to produce provably optimal or feasible plans) on the same sample to identify any tasks that are unsolvable-by-construction; (c) report the human performance ceiling and the fraction of tasks where the constraint solver fails to find a solution (indicating benchmark construction errors). This would calibrate all reported model scores in absolute terms and either validate the paper's difficulty claims or reveal that some "model failures" are actually benchmark infeasibilities. The FIT and AIS subsets, where all models score 0.0% strict, are the highest priority for this analysis.

Cross-domain transfer of the GTPO credit assignment structure. GTPO's three-stage normalization (Global Instruction Normalization, Turn-wise Reward Differencing, Turn-level Reward Normalization) is formulated in domain-agnostic mathematics (Section 4.2) but evaluated only on travel planning. A critical test of generality would apply GTPO to a structurally different multi-turn tool-use domain — for instance, τ²-Bench's customer service tasks (refund processing, order management) or a software engineering benchmark where agents debug code across multiple turns of user feedback. The hypothesis is that GTPO's components are beneficial whenever (a) multiple constraints must be satisfied simultaneously, (b) constraints vary in inherent difficulty, and (c) turn-to-turn reward inheritance confounds credit assignment. A strong follow-up would test each component's contribution independently in the new domain (via the ablation structure from Table 3) and measure whether the same pattern holds: TRD improves strict pass rates while potentially reducing loose pass rates on harder tasks. Negative results — e.g., TRD providing no benefit in a domain without strong state inheritance — would refine our understanding of when differencing-based credit assignment is appropriate.

Adaptive difficulty estimation for compute-efficient GTPO training. The current GTPO training pipeline treats all prompts uniformly — every prompt gets K = 8 rollouts regardless of difficulty. But Table 2 shows enormous variance in model performance across difficulty tiers: Easy tasks are solvable with non-trivial probability by strong models, while FIT/AIS tasks are essentially unsolvable. A compute-efficient training scheme would estimate prompt difficulty online (using early-rollout reward statistics or a lightweight classifier trained on the SFT model's per-prompt success rate) and allocate rollouts adaptively — more rollouts for prompts in the "learnable" difficulty regime where the policy has non-zero but imperfect success, fewer for prompts that are trivially easy or impossibly hard. This connects GTPO to the compute-optimal inference scaling literature (e.g., the reference example paper on test-time compute scaling) and would substantially reduce the simulator inference cost, which the paper identifies as a major unaccounted expense. The metric would be GTPO's final policy performance per unit of total training compute (including simulator calls), not just final accuracy.

Combining GTPO with hierarchical credit assignment across tool calls within a turn. GTPO assigns turn-level advantages — every token in the assistant's response at turn t receives the same advantage A_t^{(k)} (Equation 11). But within a turn, the agent makes 20–50 tool calls (Appendix G example), and not all tool calls contribute equally to the turn's incremental improvement. A natural extension would decompose the turn-level advantage into tool-call-level advantages using a similar differencing approach: within a turn, compute the plan quality (constraint satisfaction) after each tool call, apply differencing to isolate which tool calls improved the plan, and use these finer-grained advantages in the policy gradient. This would provide sharper credit assignment for long tool-call chains and could address the Mid-loose regression observed with TRD (Table 3: 20 → 18) if that regression is caused by the turn-level advantage being too coarse to distinguish productive tool calls from unproductive ones within a turn.

Stress-testing GTPO against distribution shift in the user simulator. GTPO trains against a DeepSeek-V3.2-based user simulator (temperature 0.7, Section 5.1) whose behavioral patterns — though diverse (nine categories) — are generated by a single model with a specific interaction style. A critical robustness check would train GTPO against one simulator model (e.g., DeepSeek-V3.2) and evaluate against a different simulator model (e.g., GPT-5.2 or Claude-Sonnet-4.5) playing the same user role with the same underlying constraint structure. This tests whether GTPO's credit assignment improvements are robust to the specific interaction patterns of the training simulator or whether they overfit to DeepSeek-V3.2's particular error-reporting style, question-asking patterns, and ambiguity-resolution behavior. The REFUEL paper (Gao et al., 2024) predicts that covariate shift in multi-turn RL is a major failure mode; this experiment would quantify how much of GTPO's gain survives simulator shift and identify which components (GIN? TRD? TRN?) are most vulnerable.

Practical Applications and Downstream Use Cases

Automated travel-planning assistants with verifiable constraint guarantees. The most direct application is a production travel-planning agent that uses TRIP-Bench's verifier during inference as a correctness guard: before returning a plan to the user, the agent internally runs the rule-based verifier on its own output and, if violations are detected, enters a repair loop (similar to the SFT data construction's three-round error feedback procedure, Section 4.1) before the user ever sees the plan. The paper shows that SFT alone achieves 32% Easy-loose / 3% Easy-strict (Qwen2.5-32B, Table 3) — meaning 68% of Easy tasks have at least minor errors. A verifier guard that catches and repairs even half of those errors before user exposure would substantially improve deployed reliability. The verifier is deterministic, fast (rule-based lookups), and already implemented — the engineering cost of wrapping it around an agent's output is low. For Meituan's deployment context (local services booking), where incorrect bookings create real operational costs, this guard could be deployed immediately with the existing SFT model, without waiting for GTPO training.

Cost-efficient training data generation for tool-use agents via structured error feedback. The paper's three-round error-feedback repair procedure (Section 4.1) — taking 120,000 initially-incorrect trajectories and producing 9,000 correct ones through targeted revision using verifier error messages — is a general recipe for amplifying small amounts of correct trajectories into large SFT datasets. The key ratio: 500 initially correct trajectories (0.4% of attempts) → 9,000 repaired trajectories (7.5% yield) → 3,000 high-quality trajectories after filtering (2.5% yield). This 6× amplification of correct trajectories (500 → 3,000) cost only three rounds of model inference plus verifier evaluation per incorrect trajectory. Organizations building tool-use agents in any domain with verifiable constraints (code generation with unit tests, data extraction with schema validation, form filling with completeness checks) can apply the same pipeline: (1) define verifier functions for their constraints, (2) generate a large number of candidate trajectories using a strong model, (3) run the three-round repair with error feedback, (4) filter for high-quality trajectories. The paper demonstrates this works for travel planning; the transfer to other domains requires only writing domain-specific validators — the repair-and-filter logic is domain-agnostic.

Interactive agent training environments powered by rule-based user simulation. The user simulator architecture (Section 3.4) — maintaining a dialogue graph of active instructions, selecting up to 4 instruction IDs per turn, generating natural-language queries constrained by the underlying task structure — provides a template for building controllable, evaluable interactive training environments in domains beyond travel. The key design principle is the separation of task coherence (guaranteed by the underlying constraint graph and instruction pools) from interaction richness (provided by LLM-based query generation with behavioral diversity parameters). A customer-service agent trainer could adopt this architecture: define a set of user intents (return item, change order, request refund) with verifiable success conditions, construct modification chains (add item to order → change shipping address → apply discount code), and use an LLM simulator to generate diverse interaction styles (polite/impatient, detail-oriented/vague, cooperative/adversarial) while the underlying task structure ensures evaluability. The paper's manual validation of simulator reliability (98% instruction consistency, 4.7/5 style fidelity, Appendix E) provides initial evidence that this separation works, though the sample sizes are small (20 trajectories, 104 turns for consistency; 10 trajectories, 62 turns for style).

When to Prefer This Method

The paper does not articulate an explicit tradeoff between GTPO and named alternative training methods for multi-turn tool-use RL beyond the baselines in Table 3 (SFT, GRPO single-turn, GRPO multi-turn). The comparison is empirical rather than prescriptive — GTPO outperforms these baselines on the specific setting tested (Qwen2.5 models, TRIP-Bench Easy/Mid, SFT cold-start from repaired DeepSeek-V3.2 trajectories). The paper does not claim that GTPO should be preferred over, for example, MUA-RL (Zhao et al., 2025) or UserRL (Qian et al., 2025b) in general, nor does it specify conditions under which GTPO's credit assignment components are necessary versus when simpler outcome-based RL would suffice. The absence of Hard-subset evaluation (Section 6, Limitation B) and cross-domain evaluation (Section 6, Limitation C) means the conditions under which GTPO's benefits generalize are unknown from the paper's evidence alone. A forced decision matrix would therefore be speculative rather than paper-grounded, and is omitted.

Dependency tree

Papers this one builds on, walking backwards through the same domain and shared topics.

Why Do Multi-Agent LLM Systems Fail?2025· agents← LLM-judged similar
- PokéChamp: an Expert-level Minimax Language Agent2025· agents← in-domain predecessor
MEnvAgent: Scalable Polyglot Environment Construction for Verifiable Software Engineering2026· agents← in-domain predecessor
- CodeClash: Benchmarking Goal-Oriented Software Engineering2025· code← LLM-judged similar
- DeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraints2026· agents← in-domain predecessor
- Diversity Empowers Intelligence: Integrating Expertise of Software Engineering Agents2024· agents← similar topic
MobilityBench: A Benchmark for Evaluating Route-Planning Agents in Real-World Mobility Scenarios2026· agents← similar topic
- SWE-Perf: Can Language Models Optimize Code Performance on Real-World Repositories?2025· code← LLM-judged similar
- Decoding ML Decision: An Agentic Reasoning Framework for Large-Scale Ranking System2026· agents← in-domain predecessor
WildClawBench: A Benchmark for Real-World, Long-Horizon Agent Evaluation2026· agents← similar topic
- MolmoAct2: Action Reasoning Models for Real-world Deployment2026· agents← in-domain predecessor
- Vision2Web: A Hierarchical Benchmark for Visual Website Development with Agent Verification2026· agents← similar topic
- Long-horizon Reasoning Agent for Olympiad-Level Mathematical Problem Solving2025· agents← similar topic
HINT-SD: Targeted Hindsight Self-Distillation for Long-Horizon Agents2026· agents← similar topic
- TCOD: Exploring Temporal Curriculum in On-Policy Distillation for Multi-turn Autonomous Agents2026· training-methods← topic thread
AgentFold: Long-Horizon Web Agents with Proactive Context Management2025· agents← similar topic
- WebLeaper: Empowering Efficiency and Efficacy in WebAgent via Enabling Info-Rich Seeking2025· agents← in-domain predecessor
- ExpSeek: Self-Triggered Experience Seeking for Web Agents2026· agents← similar topic
- A Subgoal-driven Framework for Improving Long-Horizon LLM Agents2026· agents← similar topic
Generative Agents: Interactive Simulacra of Human Behavior2023· agents← similar topic
- Reflexion: Language Agents with Verbal Reinforcement Learning2023· agents← in-domain predecessor
Learning Interactive Real-World Simulators2023· agents← similar topic
- Revisiting Energy Based Models as Policies: Ranking Noise Contrastive Estimation and Interpolating Energy Models2023· agents← in-domain predecessor

What it influenced

Later papers in the same chain. Direction reversed.

SWE-Universe: Scale Real-World Verifiable Environments to Millions2026· agents→ in-domain predecessor
- SEAD: Self-Evolving Agent for Multi-Turn Service Dialogue2026· agents→ in-domain predecessor
- CUA-Gym: Scaling Verifiable Training Environments and Tasks for Computer-Use Agents2026· agents→ similar topic
Generative Agents: Interactive Simulacra of Human Behavior2023· agents→ similar topic
- Proact-VL: A Proactive VideoLLM for Real-Time AI Companions2026· agents→ LLM-judged similar
- Unlocking the Power of Representations in Long-term Novelty-based Exploration2023· agents→ in-domain predecessor
MobilityBench: A Benchmark for Evaluating Route-Planning Agents in Real-World Mobility Scenarios2026· agents→ similar topic
- MAI-UI Technical Report: Real-World Centric Foundation GUI Agents2025· agents→ similar topic
- WildClawBench: A Benchmark for Real-World, Long-Horizon Agent Evaluation2026· agents→ similar topic