PaperlayerView exact revision on arXiv

Source-linked AI summary

HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel

The Viet Bui, Wenjun Li, Yong Liu

arXiv:2603.04750v1cs.AIcs.CL

TL;DR

Long-horizon LLM planners struggle to maintain coupled hard constraints as context and tool traces grow. HiMAP-Travel uses hierarchical coordination with parallel day-level execution, synchronized constraint enforcement, bargaining-based re-planning, and a shared role-conditioned policy. It reports state-of-the-art benchmark performance, including 52.65% test FPR on TravelPlanner and 2.5× lower latency, while its global state remains limited to resource-conflict enforcement.

  • Problem

    Long-horizon travel planning requires satisfying coupled hard constraints while optimizing user preferences, but sequential LLM planners are vulnerable to Constraint Drift as traces accumulate.

  • Method

    HiMAP-Travel decomposes planning into Coordinator-led strategic allocation and parallel tactical execution, using synchronized global state, cooperative bargaining, and a unified role-conditioned GRPO policy.

  • Results

    HiMAP-Travel achieves state-of-the-art performance across TravelPlanner and FlexTravelBench, including 52.65% test FPR on TravelPlanner and 2.5× latency reduction.

  • Takeaways & Limitations

    Transactional monitoring with parallel local planning provides a practical blueprint for scalable long-horizon planning with coupled constraints.

  • Takeaways & Limitations

    The synchronized global state prevents resource conflicts but does not solve route feasibility, temporal consistency, cuisine coverage, or other commonsense constraints.

Abstract

from arXiv · show

Sequential LLM agents fail on long-horizon planning with hard constraints like budgets and diversity requirements. As planning progresses and context grows, these agents drift from global constraints. We propose HiMAP-Travel, a hierarchical multi-agent framework that splits planning into strategic coordination and parallel day-level execution. A Coordinator allocates resources across days, while Day Executors plan independently in parallel. Three key mechanisms enable this: a transactional monitor enforcing budget and uniqueness constraints across parallel agents, a bargaining protocol allowing agents to reject infeasible sub-goals and trigger re-planning, and a single policy trained with GRPO that powers all agents through role conditioning. On TravelPlanner, HiMAP-Travel with Qwen3-8B achieves 52.78% validation and 52.65% test Final Pass Rate (FPR). In a controlled comparison with identical model, training, and tools, it outperforms the sequential DeepTravel baseline by +8.67~pp. It also surpasses ATLAS by +17.65~pp and MTP by +10.0~pp. On FlexTravelBench multi-turn scenarios, it achieves 44.34% (2-turn) and 37.42% (3-turn) FPR while reducing latency 2.5x through parallelization.

1. Introduction

Long-horizon travel planning exposes a gap between LLMs’ short-horizon capabilities and reliable satisfaction of coupled hard constraints. HiMAP-Travel addresses this with hierarchical coordination, parallel execution, transactional enforcement, bargaining, and a shared role-conditioned policy.

  • Motivation: Long-horizon LLM planning degrades when budgets, temporal feasibility, route consistency, and user preferences must be satisfied simultaneously.A single early logistical error can invalidate an otherwise strong multi-day itinerary.
  • Motivation: Constraint Drift arises as long tool traces dilute attention to initial global constraints, reducing feasibility in sequential planners.Post-hoc refinement can add super-linear latency and token overhead without addressing strategic resource entanglement.
  • Framework: HiMAP-Travel separates strategic resource allocation by a Coordinator from tactical planning by parallel Day Executors.The Coordinator distributes global constraints into local sub-goals, while Executors plan at the day level.
  • Framework: HiMAP-Travel integrates transactional global-state enforcement, cooperative bargaining, and a unified role-conditioned GRPO policy for consistent parallel execution.Executors can reject infeasible sub-goals, triggering structured resource re-allocation.
  • Results: 52.65% test Final Pass Rate on TravelPlanner accompanies 2.5× latency reduction, while FlexTravelBench reaches 44.34%/37.42% on 2-turn/3-turn scenarios.The reported results surpass prior methods across the stated benchmarks.

2. Related Work

Prior work establishes tool-augmented, hierarchical, and multi-agent planning, but dynamic coupled constraints remain difficult for sequential or verbally coordinated systems. HiMAP-Travel combines day-level decomposition with deterministic invariant enforcement and structured bargaining.

  • Travel Planning Benchmarks: TravelPlanner evaluates itineraries under shared invariants, while FlexTravelBench tests adaptation as constraints are progressively revealed across multiple turns.DeepTravel applies end-to-end reinforcement learning but generates itineraries sequentially.
  • Tool-Augmented Planning: ReAct and Toolformer established interleaved reasoning and API use, but monolithic sequential planners suffer Constraint Drift as tool traces lengthen.The resulting loss of attention to initial global constraints makes long-horizon planning brittle.
  • Hierarchical and Multi-Agent Reasoning: Hierarchical and multi-agent systems separate roles or sub-plans, yet static assignments and natural-language negotiation remain brittle under shared budgets and non-duplication constraints.Coordination can become slow and error-prone when constraints are dynamically coupled.
  • HiMAP-Travel: HiMAP-Travel addresses these limitations with a Synchronized Global State and Cooperative Bargaining Protocol for deterministic enforcement and structured re-allocation.Table 1 situates these design choices against representative agentic planning methods.

3. Preliminaries and Problem Formulation

The paper formulates constrained travel planning as a GC-POMDP in which a policy must optimize soft preferences while satisfying hard logical invariants. It identifies Constraint Drift as the central sequential-planning challenge and evaluates complete constraint satisfaction with FPR.

  • Problem Formulation: Travel planning is modeled as a Goal-Conditioned Partially Observable Markov Decision Process with API-mediated observations of a latent world state.The query specifies hard constraints, soft constraints, and available tools.
  • Problem Formulation: The objective maximizes expected soft-constraint utility subject to near-certain validity of hard constraints.Hard constraints include inviolable logic such as budget caps and temporal causality.
  • Constraint Drift: Constraint Drift occurs when accumulating tool outputs and reasoning traces diminish attention to initial global constraints as the planning horizon grows.Sequential planners may then prioritize local coherence over global feasibility.
  • Evaluation Metrics: Final Pass Rate is the percentage of queries producing complete itineraries satisfying all hard constraints.Delivery Rate instead measures syntactic validity regardless of constraint satisfaction.

4. Methodology: HiMAP-Travel

HiMAP-Travel separates long-horizon travel planning into strategic resource allocation and parallel tactical execution, coordinating agents through shared state and feasibility feedback. Its design combines transactional constraint enforcement, bargaining-based re-allocation, role-conditioned parameter sharing, and memory-efficient multi-role training.

  • Strategic and Tactical Planning: HiMAP-Travel transforms the planning horizon from T to T/D by separating strategic allocation from parallel day-level execution.The Coordinator allocates resources, while D Executors resolve temporal sub-problems independently.
  • Strategic and Tactical Planning: The Coordinator projects each query into day-level sub-goals with city, semantic-role, and budget boundary conditions satisfying the total-budget constraint.Per-day budget hints guide choices, while the synchronized monitor applies the hard budget cap during atomic commits.
  • Synchronized Execution: Parallel Executors generate isolated day trajectories while a synchronized global state transactionally enforces budget, venue uniqueness, and transport-mode consistency.CHECK validates actions without mutation, whereas COMMIT updates shared state only when invariants remain satisfied.
  • Role Conditioning and Concurrency: A single policy serves the Coordinator and Executors through system-prompt role conditioning, with inference instantiating D+1 logical threads and capping concurrency at P = 3 workers.This design avoids separate parameter sets while preserving distinct strategic and tactical roles.
  • Cooperative Bargaining: Executors can reject infeasible sub-goals with typed feedback, causing the Coordinator to revise routes, cities, or day roles in subsequent iterations.The bargaining payload reports feasibility status, estimated budget deficit, and violation type.
  • Training: GRPO training decomposes hierarchical rewards into global and role-specific signals, while a shared FIFO rollout buffer reduces memory pressure from multi-agent trajectories.The naive implementation stores approximately (D + 1) × G × T × dmodel activations; the buffer partitions trajectories by role prompt.

5. Empirical Evaluation

HiMAP-Travel is evaluated on single-turn and multi-turn travel-planning benchmarks, controlled baselines, constraint-level failures, latency, and component ablations. It improves feasibility and robustness while reducing latency through parallel execution.

  • Constraint Drift: 98% to 42% budget satisfaction degradation across Days 1–5 in the sequential baseline contrasted with 91% on Day 5 for HiMAP-Travel.The result is consistent with day-level context isolation and proactive invariant checks.
  • Constraint Drift: 34.0% of analyzed failures were budget overflows, reduced from 12.5% to 4.1%, while duplicate venues fell from 8.7% to 1.5%.These reductions accompanied improvements over DeepTravel on all reported constraint-level metrics.
  • TravelPlanner: 52.78% validation FPR and 52.65% test FPR were achieved on TravelPlanner with Qwen3-8B.The validation–test gap was 0.13 percentage points.
  • TravelPlanner: +8.67 pp over DeepTravel, +17.65 pp over ATLAS, and +10.0 pp over MTP were achieved on TravelPlanner test FPR.HiMAP-Travel also showed lower cross-seed variance than DeepTravel and 100% Delivery Rate.
  • Multi-turn Adaptation: 44.34% 2-turn FPR and 37.42% 3-turn FPR were achieved on FlexTravelBench, exceeding ATLAS by 5.14 and 4.72 percentage points.Gains were reported across Local Add, Global Add, Local→Global, and Global→Local scenarios.
  • Efficiency: 2.63× wall-clock speedup on 7-day trips reduced time from 189.5s to 72s, with sub-linear growth as itinerary length increased.Executor concurrency was capped at P = 3, and bargaining overhead was 10.8%.
  • Ablations: Removing the synchronized state, Coordinator, bargaining, or parallelism reduced FPR by 9.58, 12.98, 3.88, or 7.18 percentage points, respectively.Removing the synchronized state also increased diversity violations from 8% to 34%.

6. Conclusion

HiMAP-Travel addresses constraint drift in long-horizon tool-using planning by separating strategic coordination from parallel day-level execution. Its transactional state, bargaining protocol, and shared role-conditioned policy support strong benchmark performance, lower latency, and broader constrained-optimization applicability.

  • Problem: HiMAP-Travel targets Constraint Drift under Long Tool Traces, where global hard-constraint adherence degrades as intermediate outputs accumulate.The framework decouples strategic coordination from parallel day-level execution.
  • Contributions: Its Synchronized Global State enforces coupled invariants, Cooperative Bargaining Protocol supports feasibility feedback, and GRPO trains a unified role-conditioned policy.These mechanisms support deterministic enforcement, structured re-allocation, and shared-policy training.
  • Results: 52.65% test FPR on TravelPlanner and 2.5× lower latency were reported, with an 8.67 pp gain over DeepTravel under controlled conditions.The ablation study further validates the design components.
  • Implications: Decomposing coupled global constraints into parallel local sub-problems with transactional monitoring is presented as applicable beyond travel planning.Examples include software module development, supply chain optimization, and scientific experiment design.

Impact Statement

The paper frames HiMAP-Travel as a travel-planning advance with potential relevance to other resource-coordination tasks, while documenting implementation assumptions and boundaries. Its monitor handles selected shared resource conflicts, whereas other constraints remain policy- or evaluator-dependent.

  • Scope: The evaluation focuses on travel planning, while the methodology is described as generalizing to project management, supply chains, and scientific experiment planning.The paper reports no specific negative impacts warranting addition to the impact statement.
  • Transactional Monitor: The Synchronized Global State is an external structured store that transactionally enforces selected hard constraints through atomic operations and a global mutex.It tracks budget expenditure, committed venues, and transport-mode consistency.
  • Assumption: Rollback assumes tentative actions can be released cost-free, consistent with reserve-then-confirm workflows.The paper maps this abstraction to hotel, flight, and restaurant reservation practices.
  • Boundary: The monitor prevents budget exhaustion, duplicate bookings, and mode inconsistency but does not validate route, temporal, room, cuisine, or commonsense constraints.Those constraints remain the responsibility of the learned policy and post-hoc environment evaluation.
  • Guarantees: Safety guarantees depend on serialized mutations and commit-time invariant validation, while liveness depends on policy exploration and iterative bargaining.Route feasibility and other unrepresented constraints are enforced by external checkers.
  • Reward Design: Global and local reward signals are decomposed to address credit assignment in hierarchical reinforcement learning.The Coordinator objective combines global reward, extraction reward, and an iteration penalty.
  • Reward Design: Executors receive a fail-fast bonus when violations are detected within the first five tool calls.The bonus is part of an objective weighted by global, local, and early-detection terms.

A.3. Training Configuration

Training uses Qwen3 models fine-tuned with GRPO on TravelPlanner, with role-specific tools and hierarchical task decomposition. The evaluation setup covers strict single-turn and multi-turn constrained-planning benchmarks, while training dynamics reflect distinct Coordinator and Executor roles.

  • Optimization: Qwen3-4B-Instruct and Qwen3-8B were fine-tuned for 100 epochs on 45 TravelPlanner queries with full-parameter optimization.Training used Adam, learning rate 5×10^-6, batch size 32, gradient accumulation 4, and an 8192-token context window.
  • Optimization: Decoding used temperature 0.7 and top-p 0.9, with 15 tool calls per day-agent and at most three bargaining iterations.GRPO used group size G = 4 and KL coefficient β = 0.01.
  • Generalization: Trajectory augmentation, pretrained initialization, low validation–test gaps, and low seed variance were cited as factors mitigating overfitting concerns.Same-data sequential-baseline comparisons were used to distinguish architectural from data advantages.
  • Training Dynamics: Coordinators stabilize earlier than Executors because they choose among 5–10 cities, whereas Executors navigate 50–200 venues with sequential tool calls.Bargaining effectiveness improves during training and reward standard deviation decreases.
  • Agent Configuration: The Coordinator extracts queries and distributes day-level sub-goals, while Day Planners use search and meta-tools while interacting with the synchronized state.The tool library includes city, flight, distance, restaurant, attraction, accommodation, cost-enquiry, and finish tools.
  • Agent Configuration: Task decomposition computes transport costs, stores a consistent ground mode, and distributes soft budget hints while the global budget is enforced at commit time.Departure and return days receive 0.7× and 0.5× budget multipliers.
  • Benchmarks: TravelPlanner evaluates complete multi-day itineraries under 13 conjunctive constraints, whereas FlexTravelBench evaluates adaptation as constraints are progressively revealed across turns.TravelPlanner uses 45/180/1,000 train/validation/test splits and includes 3-, 5-, and 7-day trips.

B.2. TravelPlanner Training Data

HiMAP-Travel trains on 45 disjoint TravelPlanner queries, expanding each query into diverse GRPO trajectories and synthetic multi-turn episodes while preserving zero-overlap evaluation. The reported split separation and low validation-to-test gap support generalization beyond the training queries.

  • 45 TravelPlanner training queries are completely disjoint from the 180-query validation and 1,000-query test sets.
  • Episode Construction: Each training episode decomposes a query into day-level sub-tasks, uses database-backed travel tools, and ends when committed day plans are assembled into a final itinerary.Rewards are computed against the ground-truth constraint set through hierarchical reward decomposition.
  • Trajectory Augmentation: (D + 1) × G rollouts generate 16–32 distinct trajectories per query per training step, expanding the distribution beyond the 45 base queries.Here D is trip duration and G = 4 is the group size.
  • Split Integrity: The validation-to-test gap is 0.13 percentage points for Qwen3-8B, with 52.78% validation and 52.65% test Final Pass Rate.
  • FlexTravelBench Training: Synthetic FlexTravelBench training data teaches conflict detection, constraint prioritization, and selective recomputation for multi-turn itinerary revision.The data are constructed from the disjoint TravelPlanner training split by revealing local and global constraints across turns.
  • Generalization: 63.7% overall success and consistent cross-scenario performance are reported for FlexTravelBench training with zero query-level overlap and randomized constraint-removal patterns.Each base query generates 8–9 distinct training episodes.

C.1. Latency Analysis

HiMAP-Travel reduces latency through parallel day execution, achieving near-linear day-planning speedup while retaining transactional constraint enforcement and a unified role-conditioned policy. The design trades modest token overhead and fixed coordination costs for faster, more deterministic execution.

  • Parallel Speedup: 2.79× day-planning and 2.63× end-to-end wall-clock speedups are achieved with executor concurrency capped at P = 3.The gap from the theoretical 3× day-planning maximum is attributed to coordinator planning, bargaining, and final-validation overheads.
  • Model Size: 49.80% versus 52.65% FPR and 48s versus 72s latency compare the 4B and 8B models, respectively, with the smaller model reaching 67% of 8B latency.
  • Measured Latency: 72s versus 190s is the measured latency for 7-day itineraries with HiMAP-Travel and sequential DeepTravel, respectively.On 3-day itineraries, the corresponding averages are 48s and 98s.
  • Bargaining Overhead: 89% of queries succeed on bargaining iteration 1 and 97.8% by iteration 3, motivating the cap Kmax = 3.More than three iterations add less than 0.5% gain while substantially increasing latency.
  • Constraint Enforcement: The Synchronized Global State uses transactional locking to prevent shared-resource conflicts, while rollback assumes cost-free tentative booking release in simulated reversible-action evaluations.Average lock wait is 12ms in CPU-bound operations, and deadlocks are theoretically impossible under the single-lock design.
  • Trade-offs: Parallel executors consume 15% more tokens than sequential baselines, alongside a reported 2.5× latency reduction.

C.3. FlexTravelBench: Detailed Scenario Analysis

HiMAP-Travel improves Final Pass Rate across all four FlexTravelBench constraint-revelation scenarios, with gains over ATLAS ranging from 3.92 to 6.10 percentage points. Delivery Rates are perfect, while budget- and room-related hard constraints remain weaker.

  • 2-Turn Local Add: 44.96% versus 38.86% FPR is the 2-Turn Local Add result for HiMAP-Travel and ATLAS, a +6.10 pp gain.
  • Cross-Scenario Comparison: +4.14 pp, +3.92 pp, and +5.57 pp are HiMAP-Travel’s gains over ATLAS on 2-Turn Global Add, 3-Turn Local→Global, and Global→Local scenarios.The reported gains span all four scenario templates.
  • Constraint Outcomes: 100% Delivery Rates are reported across the FlexTravelBench scenarios, while Hard Constraint Macro rates range from 55% to 70%.The remaining hard-constraint weaknesses are concentrated in budget- and room-related constraints.
  • Model Size: The 8B model exceeds the 4B model by 3.2 pp across FlexTravelBench scenarios.

C.4. Comprehensive Results: Complete Breakdown Across Splits and Models

Across splits, model sizes, and controlled architectural comparisons, HiMAP-Travel maintains strong Final Pass Rate performance and substantially reduces variance relative to sequential planning. Its advantages are largest on easier cases, while hard instances remain challenging despite improved robustness.

  • Split Generalization: Final Pass Rate changes by +1.19 pp for 4B and −0.13 pp for 8B from validation to test, indicating stable split transfer.
  • Constraint Metrics: Hard Constraint Micro drops 24–26 pp from validation to test, while Hard Constraint Macro increases by +4.28 pp for 4B and +2.72 pp for 8B.The passages attribute the Micro gap to different query distributions and describe the Macro pattern as constraint-specific learning.
  • Controlled Comparison: HiMAP-Travel improves over identical-backbone, identical-GRPO DeepTravel configurations by 7.22–14.88 pp and reduces variance across seeds by 70.8–93.3%.The controlled comparison isolates hierarchical architecture from model capacity and training algorithm.
  • Stability: 8B test standard deviation falls from 7.18% with DeepTravel to 0.48% with HiMAP-Travel, a 93.3% reduction.
  • Architecture Effect: HiMAP-Travel improves Hard Constraint Micro by +4.81 to +6.94 pp over DeepTravel, with larger total gains for 4B than 8B models.The reported 4B gains are 13.33–14.88 pp, compared with 7.22–8.67 pp for 8B.
  • Difficulty Scaling: +11.1 pp, +11.5 pp, and +3.4 pp are the performance gaps on Easy, Medium, and Hard difficulty tiers, respectively.On Hard queries, standard deviation is 1.5% for HiMAP-Travel versus 12.3% for DeepTravel.

D. Ablation Studies

The ablations show that synchronized state, hierarchical coordination, bargaining, parallel execution, and unified role conditioning each materially support HiMAP-Travel’s feasibility and efficiency. Removing these components produces lower FPR, more constraint violations, or greater latency.

  • Execution and Training Choices: 7.18 pp lower FPR results from sequential execution without parallelism, while separate coordinator and executor policies reduce FPR by 8.08 pp.Naive batch updates reduce FPR by 1.58 pp and can trigger memory overflow on 7-day queries.
  • Synchronized Global State: -11.58 pp overall FPR follows removal of synchronized global state, while diversity falls from 92.0% to 65.3%.Budget violations rise from 4.1% to 12.5%, and duplicate restaurants and attractions become common.
  • Hierarchical Coordinator: -14.28 pp overall FPR follows removal of the Coordinator, with budget violations increasing to 28.4%.Budget utilization drops from 0.94 ± 0.08 to 0.67 ± 0.24, while cascading failures rise from 2.1% to 23.4%.
  • Cooperative Bargaining: -3.88 pp overall FPR follows disabling bargaining, while the Hard subset falls from 36.8% to 22.4%.Bargaining corrects infeasible initial allocations; 61.7% succeed on iteration 1, and only 2.2% remain infeasible after three iterations.
  • Coordinator Adaptation: 74.6% of bargaining adaptation attempts succeed, with transport switching achieving 91.7% success and city reduction achieving 100%.City substitution is most frequent at 66.2% of adaptations and succeeds in 78.7% of cases.
  • Early Detection: 36.2% lower mean iteration latency results from early detection, falling from 38.1s to 24.3s.The mechanism shifts early INFEASIBLE reports from 40.8% to 73.2% within the first five tool calls and preserves near-parity wall-clock time.

F. Failure Analysis and Limitations

HiMAP-Travel reduces major failure modes in constrained travel planning, especially budget, duplication, and route errors, but remains limited by temporal reasoning, data quality, and inherently infeasible constraints.

  • Budget Violations: 34.0% of sampled failures are budget violations, while HiMAP-Travel reduces overall budget violations from 12.5% to 4.1%.Early overspend falls from 8.3% to 1.8%, and commit-time enforcement prevents cumulative drift from propagating.
  • Duplicate Venue Selections: 83% fewer duplicate venue selections occur with HiMAP-Travel, decreasing from 8.7% for the sequential baseline to 1.5%.The synchronized global state atomically tracks committed venues and rejects repeated selections; residual failures arise from fuzzy matching false negatives.
  • Geographic and Temporal Inconsistencies: Route infeasibility falls from 3.8% to 1.1%, while hierarchical task distribution explicitly enumerates required cities for complete coverage.The Coordinator validates routes before assigning day-level sub-goals and tracks required-city coverage.
  • Temporal Limitations: Minimum-nights violations decline from 2.6% to 0.9% but remain an architectural limitation requiring enhanced temporal reasoning.Across failures, they comprise 13.7% of the full test-set failures, with cascading variants concentrated near final accommodation days.
  • Data and Feasibility Boundaries: Data-quality issues and unsatisfiable constraint combinations limit performance beyond architectural failures.Geographic inconsistencies reflect database metadata problems, while budget-capacity conflicts may lack feasible database solutions; proposed improvements include dataset curation and early feasibility detection.
  • Design Implications: Joint budget and diversity failures account for 54% of failures, and the paper proposes temporal reasoning, coupled-constraint modeling, and early feasibility detection as next steps.The proposed refinements are presented as pathways toward 70–80% success from the current 52.7%.
Loading 2603.04750v1…