Skip to content

TriFlow: A Progressive Multi-Agent Framework for Intelligent Trip Planning

🕒 Published (v1): 2025-12-12 04:27 UTC · Source: Arxiv · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

TriFlow is a three-stage multi-agent framework for trip planning that pipelines retrieval, constraint-aware planning, and iterative governance to transform open-ended user queries into feasible itineraries. It achieves 91.1% and 97.7% final pass rates on TravelPlanner and TripTailor benchmarks respectively, while running 10.9× faster than the previous SOTA (FormalVerify).

Problem

Existing LLM-based trip planners suffer from constraint violations (temporal, spatial, budgetary), poor tool coordination, hallucinated facts, and high token costs. They lack an integrated design that jointly handles orchestration robustness and cost efficiency — prior work on neuro-symbolic planning, multi-agent coordination, and personalisation evolved independently.

Method

TriFlow structures planning as a feasibility-first optimisation across three progressive stages:

  1. Retrieval: LLM agents decompose the query into structured requirements, then parallel modules retrieve flights, distances, restaurants, attractions, and accommodations with integrity checks (geometry, time windows, price consistency) to bound the factual domain.
  2. Planning: A skeleton-first assembly builds city order and time allocation via rule-based logic, then fills transportation, lodging, meals, and attractions through agent–validator loops. A monotonic feasibility principle prevents later steps from violating earlier committed constraints.
  3. Governance: A state-machine controller runs bounded iterative refinement (max 8 iterations) — each pass generates a system report on budget/timing/preference, identifies violations, proposes targeted fixes, validates them, and updates the itinerary only if feasibility is preserved.

A staged temperature schedule (0.0 / 0.3 / 0.6) across the three stages balances determinism in retrieval with creativity in governance.

Key Contributions

  • Progressive three-stage pipeline that progressively contracts the feasible search space via explicit pruning
  • Rule–LLM collaborative division: rule-based skeleton construction + LLM detail refinement within constraint boundaries
  • Modular constraint orchestration with pluggable temporal/spatial/budgetary/preference modules managed by a state-machine controller
  • Empirical SOTA on TravelPlanner (91.1% FPR) and TripTailor (97.7% FPR) with 10.9× runtime speedup over FormalVerify

Results

TravelPlanner (180-instance validation set, GPT-4o): - TriFlow: 91.1% FPR vs. FormalVerify 93.3% and TravelPlanner baseline 4.4% - Micro commonsense 99.3%, macro commonsense 95.0%, micro hard-constraint 99.2%, macro hard-constraint 96.1% - Avg. runtime 22.6s vs. FormalVerify 245.7s (10.9× faster) - Constraint-level: hard constraints (Budget, Room Rule, Cuisine) improved from 0.3–13.8% to 80–100%

TripTailor (GPT-4o-mini): - TriFlow: 97.7% FPR vs. Workflow baseline 63.3% and Direct baseline 21.5% (+34% over strongest baseline) - Macro feasibility 99.1%, macro rationality 97.7% - All individual metrics ≥97.6% (budget compliance 99.9%, Within Sandbox 99.1%, duration consistency 97.6%)

Limitations

  • Evaluated only on offline benchmarks; no real-time or live-data experiments
  • Hard constraint FPR drops from 96.7% (Easy) to 80.0% (Hard) — entangled constraints remain partially unresolved
  • Depends on GPT-4o/GPT-4o-mini; generalisability to smaller or open-weight models is untested
  • Maximum 8 governance iterations is a fixed cap; may be insufficient for highly constrained long-horizon plans
  • 4-page WWW Companion paper — implementation details and ablations are limited

Relevance to Harnesses / Meta-Harnesses

TriFlow is a concrete instantiation of a meta-harness pattern: a controller pipeline that orchestrates multiple specialized agents (retrieval, planning, governance) through explicit stage boundaries, validator loops, and conditional routing, rather than a single monolithic LLM call. The state-machine governance stage — with its generate→check→propose→validate→update loop and early-termination logic — closely mirrors the harness patterns used in paper-digest and similar systems. The monotonic feasibility principle (committed outputs from upstream stages are immutable contracts for downstream stages) is a principled solution to the constraint-propagation problem that any multi-stage harness faces when agents share stateful context.