ATLAS: Constraints-Aware Multi-Agent Collaboration for Real-World Travel Planning
Authors: Jihye Choi
Jinsung Yoon
Jiefeng Chen
Somesh Jha
Tomas Pfister
Venue: ICLR 2026 Poster (2026)
Keywords: Multi-agent orchestration
Real-world travel planning
Constraints-aware planning
Primary area: foundation or frontier models, including LLMs
TL;DR: General multi-agent framework for real-world constrained travel planning with information search

Abstract: While Large Language Models (LLMs) have shown remarkable advancements in reasoning and tool use, they often fail to generate optimal, grounded solutions under complex constraints. Real-world travel planning exemplifies these challenges, evaluating agents’ abilities to handle constraints that are explicit, implicit, and even evolving based on interactions with dynamic environments and user needs. In this paper, we present ATLAS, a general multi-agent framework designed to effectively handle such complex nature of constraints awareness in real-world travel planning tasks. ATLAS introduces a principled approach to address the fundamental challenges of constraint-aware planning through dedicated mechanisms for dynamic constraint management, iterative plan critique, and adaptive interleaved search. ATLAS demonstrates state-of-the-art performance on the TravelPlanner benchmark, improving the final pass rate from 23.3% to 44.4% over its best alternative. More importantly, our work is the first to demonstrate quantitative effectiveness on real-world travel planning tasks with live information search and multi-turn feedback. In this realistic setting, ATLAS showcases its superior overall planning performance, achieving an 84% final pass rate which significantly outperforms baselines including ReAct (59%) and a monolithic agent (27%).

Published as a conference paper at ICLR 2026
ATLAS: CONSTRAINTS- AWARE MULTI-AGENT COL- LABORATION FOR WOALWWOLD TRAVEL PLANNING
Jihye Choi'; Jinsung Yoon', Jiefeng Shen",,ommete Jha', Tomas Pfister
University of Wisconsin-Madison, ?Google Cloud (iihy, j @cs. wisc. edu, (jinsungyoon, jiefenge, tonpsseeppttttt (googlee com
ABSTRACT
While Large Language Models (LLMs) have shown remarkable advancements in reasoning and tool use, they often fail to generate optimal, grounded solutions un- der complex constraints. Real-world travel planning exemplifies these challenges, evaluating agents' abilities to handle constraints that are explicit, implicit, and even evolving based interactions with dynamic environments and user needs. In this paper, we present A7LAS, a general multi-agent framework designed to effectively handle such complex nature of constraints awareness real-world travel planning tasks. ATLAS introduces principled approach to address the fundamental chal- lenges of constraint-an aware planning through dedicated mechanisms for dynamic constraint management, iterative plan critique, and adaptive interleaved search. ATLAS demonstrates sate--of-theaan performance on the TravelPlanner bench- mark, improving the final pass rate from 23.3% to 44.4% over its best alternative. More importantly, our work is the first to demonstrate quantitative effectiveness real-world travel planning tasks with live information search and multi-tur feedback. In this realistic setting, ATLAS showcases its superior overall planning performance, achieving 84% final pass rate which significantly outperforms baselines including ReAct (59%) and a monolithic agent (27%).
INTRODUCTION
Constraint awareness and compliance is a fundamental aspect of intelligence, crucial for reasoning and problem-solving (Dechter, 2003; Holyoak & Simon, 1999). Solving real-world problems under constraints requires a delicate interplay of understanding requirements, searching for information, and synthesizing solution that respects all rules. While Large Language Models (LLMs) have made rapid advancements in reasoning and tool use (Schick et al., 2023; Nakano et al., 2021) 1), their reliability is still limited in practical tasks with complex, multifaceted constraints. Despite their capabilities, they often produce plans that are incoherent or invalid, a critical shortcoming for real-world deployment (Valmeekam et al., 2023; Kambhampati et al., 2024).
Existing research often sidesteps the core challenge. Some methods focus on constraint compliance but assume all necessary information is provided upfront (Parmar et al., 2025; Lee et al., 2025), while others incorporate search but presume all constraints are known in advance (Hao et al., 2025a). The more realistic and challenging scenario, where an agent must simultaneously search for context information and discover the constraints, remains largely unsolved. This intricacy is clear in quintessential, daily task like travel planning. As shown in Figure 1, even state-of- thether models satisfy user's explicit requests (e.g., budget, dates) yet fail implicit commonsense rules, such as creating a logical itinerary or avoiding hallucinated details. The problem is further magnified in multi-turn conversations where user constraints dynamically evolve, task where current LLMs and LLM agents still fall short (Xie et al., 2025).
like -cmmnni-2.5PPrt
To address this gap, we introduce general multi-agent framework designed systemically tackle three fundamental challenges in practical constraint-aware question answering tasks:
Constraint Construction: Identifying the complete set of explicit and implicit constraints from user queries and search results without prior knowledge. We leverage LLMs' vast repository of
"This work done while Jihye was research intern Google Cloud.

---

Published as a conference paper at ICLR 2026
Can you please give me 7-day kinarary for me and a labmate traveling from San Frandisoo Ri de Jandrro from April 20267
Our combined budget la $5000, and we would like to try Breailann Mexican, and Korean cullinos. We want to explore two nearby chies possible.
Nothing should hallchatted iti lirrrrryy
series waatt have experfancc
2-ppo
ATLAS (ours)
Transportation: NVBCE. Departur: 14.00, Artival: C9000.
Transportation: AA2802, Departure: 13:27, Antvvt 08 04 2026 Breakfast: Curtivar
04 2026
Hallucinated
Breakfast: Culliarr
Attraction: Christ the Redeomer Janero
Attraction: the Redeemer Rio Jandlro
Lunch:
Misaing necessary
Lunch: Restaurante Guacamole Taquerfa Dinner: Churaasario
Dinner: Churraccaria
Hotel
Santa
Transportation: Salf
Ro Janeiro Petropollss
Transportation: Tadd, Janeiro Potropolls
Breakfast: Culvar
suggestions
Breakfast: Galeto 163
Attraction: Outtandinha Palace: Imperial Museum,
Attraction: Gultard Falace: Imperial Museum. Petrópolls
Petrópollss
Lunchi Puailla Cafe, Bio
city sequence
Restaurante Alcintara Petrápoli épols
Figure I: Monolithic agent cannot solve real-world travel planning. The true challenge in real- world travel planning is satisfying both explicit user requests and implicit, commonsense expectations (in dotted bubble )). Even advanced models like Gemini- 2.5-Pro fall short, as seen in critical failures like omitting lunch after 9 a.m. arrival suggesting restaurant in different city. This highlights the vital need for a multi-agentic solution like ATLAS.
world knowledge and commonsense reasoning (Zhao et al., 2023; Krause & Stolzenburg, 2023; Ismayilzada et al., 2023) to infer and codify a full set of constraints.
Constraints-Awaae Answering: Generating coherent, valid solution that is verified to adhere to all identified constraints. For this, implement an iterative refinement loop where one agent's generation is rigorously verified against constraints by another, with targeted feedback guiding subsequent revisions (Gou et al., 2024: Choi al., 2024).
Resolving Information Gap: Diagnosing failures to determine they stem from logical errors or insufficient information from search. We utilize agent with high-level reasoning diagnose the specific information gaps and recommend new search actions (Gou et al., 2025; Wu et al., 2025), effectively turning dead-end into opportunity adaptively gather more information.
We demonstrate the effectiveness of framework, ATLAS (Agent-based Travel planning with Live Adaptive Search), using travel planning tasks as a testbed, as it naturally embodies all three of these challenges. Our contributions threefold: First, the TravelPlanner benchmark (Xie et al., 2024), ATLAS presents superior performance than existing multi-agent baselines by up to 14% on the test set. Second, multi-turn variants (Oh al., 2025), ATLAS effectively adapts to evolving user feedback where other methods stagnate. Finally, we demonstrate its utility beyond sandbox settings by showing quantitative success in live, dynamic setting that combines real-time web search with multi-turn interaction. In this realistic scenario, ATLAS achieves an 84% final pass rate with high factual grounding, while baselines like ReAct (59%) and a monolithic agent (27%) fall significantly behind.
Related Work. Most of existing approaches assume that all necessary information is readily available (Kambhampati et al., 2024; Yuan et al., 2025; Lee et al., 2025; Xie et al., 2025; Lu et al., 2025; Singh et al., 2024), or when integrating search tools, exhibit limited performance (Zhang et al., 2025), or lack rigorous evaluation (Chen et al., 2024). ATLAS is designed to fill these specific gaps by handling constrained travel planning with search, also with effective extension to beyond sandbox, open-domain, multi-turn setting. A detailed discussion of related work is in Appendix A.
PROBLEM SETUP
In this section, we introduce a formal definition of our target travel planning task as generalized constrained question answering problem. In particular, given user's natural language query Q, we
The commonsense examples here are adopted from the TravelPlanner benchmark (Xic al., 2024).
2

---

Published as a conference paper at ICLR 2026
translate it into a Constraint Satisfaction Problem (CSP) (Mackworth, 1977; Brailsford al., 1999b),
P = DC) The components are defined as follows:
X = = (2.......... . is finite set of n variables. In travel planning, these represent the decisions be made. For instance, includes variables such as Day rransporrtatiio Day Accommodetion::
Daylpinner: Day Breakfast and so on (including all relevant plan details for each day).
D = =(Dz1: Dry...., ......,.,. is set of domains, where each Da, is the finite set of possible values for variable 24. These domains are dynamically constructed from external information sources rather than given a priori. That is, the agent populates D from observations O yielded by executing a series of tool calls. For instance, the domain for the variable Day1 Lunch would be the set of candidate restaurants available in the relevant city on Day 1, obtained via a live search.
{ci (c1,c2. Cg..... Cm is a finite set of m constraints that must be satisfied. Each constraint сj E C is a pair of (scope(c)), rel(e,)), where scope(c,) S X is the subset of variables involved in the constraint G,, and rel(cy) S [soopp(())) Dr a relation specifying the allowed combinations of values for the variables in its scope. For instance, consider constraint G that the restaurant for all meals must be different throughout trip. The scope would be all meal-related vari- ables, scope(c;)
{Dayl Lunch, Daylpinner: Day2greakfact:... J. The relation rel(c;) would +
be rel(e,) = ( .T)) Vi,j E {l...., k), $J - Ti * r, which is the set of all k-tuples of restaurant assignments satisfying the constraint.
Within this CSP framework, we categorize the overall constraint set C' into two subsets based on their source and nature (analogous to classical planning distinctions between goals and state constraints (Fikes& Nilsson, 1971)). (i) Explicit Constraints (Cç) are the requirements or preferences (i.e., goals that the solution must satisfy) explicitly stated implied by Q. such budget limits, desired destination, or dates. Cg could also include any new constraints that arise from observations O, such as accommodations requiring minimum nights stay or maximum occupancy. (ii) Implicit constraints (C₂) are not explicitly given but stem from commonsense domain rules and physical realities, which are analogous to the state invariants in classical planning literature. All explicit and implicit constraints together form the complete constraint set for the problem: C = CE U C₁. The objective of the static travel planning problem can now be stated formally.
Definition 2.1 (Static Travel Planning Objective). Given a CSP instance P = (X, D, C), a complete assignment is function a X Uzex Da that maps every variable E X to value in its respective domain, i.e., a (xx) E Dz. A complete assignment is a feasible solution if it satisfies all constraints in C. That is, for every constraint ej E C, the combination of values assigned to the variables in its scope must be allowed tuple in its relation:
(a<))< E scope(c;)) E rel(c,)
If a feasible solution a exists, the problem is satisfiable. no such assignment exists for the given domains D, the problem is unsatisfiabl. The goal is to return a feasible solution if one is found, or an indication of unsatisfiability otherwise.
Evolving Constraints. The above static CSP represents a single-turn travel planning where a plan is generated in response to one-time user query. In real-world scenarios, however, users may wish to refine the plan by providing feedback or by adding, removing, or modifying constraints in a multi-turn conversation (e.g., adjusting the budget). The updated query often requires the system to gather further information, resulting in an augmented observation set and, ultimately, an evolving set of constraints. This dynamic nature transforms the problem from a static CSP into a Dynamic CSP, which can be viewed as sequence of static CSPs, Pl. p2 ....., Pt, where each problem in the sequence is a transformation of the previous one (Mittal & Falkenhainer; Dechter & Dechter, 1988).
Definition 2.2 (Dynamic Travel Planning Objective). Let a multi-turn conversation produce a For each turn E {1,..., T), the agent obtains observations O" and consequently forms a problem instance p = (X, Dt, C*). A solution trajectory is sequence of assignments (ax, {o=)?== where each o is a feasible solution for its corresponding problem pt:
sequence of queries (Q',Q2--. Q2...... )T).
VI (I,...,,T), Ve C* (ox(r)) scope(e)) E rel(c)
Ultimately, the objective is to produce a final travel itinerary 57 that is feasible for PT_ Intermediate o¹ serves as (provisional) plan consistent with each intermediate problem P This calls for system that can manage an evolving set of constraints, generate solutions that satisfy them, and gather information according to the dynamics.
3

---

Published as a conference paper at ICLR 2026
need 5-day joumey for two. leaving from Charlotte and visiting cities in Wisconsin
Query Q
from March 18-28 2022. Our budget $2500. am bringing kid under 10, and prefer private rooms.
Search
Plan
Plan
Tool Calling
find
Day
Day Trerepottellere Breakfinnt (ng))
Search
Observation
Teraaprteeeer Breakfent AX.)
Planner
Notepad D
Acczoms
Accommoocation Madison! Domain D(x))
A Interactions
Room No pets childre under 10, Minimum
masimum couupeeegn-..
Verdict V
[estauraans Madison)
Feedback plan
Checker
acpormemdatioo serlidfying ling both "children under 10 and "private rooms.
Explicit C. Room slow under 10
2. Roam type: prefer private rooms.
3. eccommocaaions mn right stay 4...
Feedback
Suggested Accommodation(Grenn Bay] currently
Constraint Manager
Implicit
1. Ralum to the origin city on the last day
hard accommecitiion the
missing eccommodations
Search Advisor
ail constraints lry Wiscomsin,
interleaved search
Figure An overview of our framework's workflow on a task in TravelPlanner (Xie et al., 2024). Initially, the Search Agent populates domain of available options, while the Constraint Manager identifies all constraints that should be considered. These include explicit constraints from the user (e.g., must allow children 10) and search results (e.g., minimum night stays), well implicit, commonsense constraints. The Planner then proposes a plan, which iteratively validated by the Checker. If the Checker finds the problem is unsatisfiable, it triggers interleaved search. The Search Advisor diagnoses the failure and provides feedback to guide a new, more informed search.
ATLAS: AGENT-BASED TRAVEL PLANNING WITH LIVE ADAPTIVE SEARCH
Challenges Constraints-Awan Planning. The design ATLAS directly motivated by three fundamental challenges inherent to constraint-aware planning with search. (i) Challenge 1: Constraint construction where the goal is to identify the complete set of implicit and explicit constraints. (ii) Challenge 2: Planning under constraints, reliably generating valid plan that satisfies all identified constraint. (iii) Challenge 3: Resolving information gaps where the goal is to handle cases where plan fails due logical error, but due to insufficient information from the initial search. We refer the readers to Appendix B for the discussion on the connection of these challenges to the well-established planning literature in classical artificial intelligence (Brailsford et al., 1999a).
Notations. We now provide concrete descriptions of our framework. To model the system's operation, we use 1,... for the conversation turn, = ...... L for the interleaved search loop within turn, and k: = O, ...... K for the interaction loop between the Planner and Checker agents. We use calligraphic notation to denote
space of all possible instances for these objects: Q for queries, X' for variable sets, O for observations, 'D for domain sets, and C for constraint sets. Each agent is defined as typed function (summarized Table 3). Figure and Algorithm illustrate the overview.
3.1 CONSTRAINT MANAGEMENT (CHALLENGE 1)
The first phase of the ATLAS pipeline is to establish the factual basis for planning and handled by two agents: The Search Agent is responsible for all interactions with external environments via tool calls, while the Constraint Manager uses the collected information identify the constraints.
Search (tool interaction). Given the user query Q'. it retrieves set of raw observations O from all tool calls, and then extracts a structured domain t (e.g., the set relevant piece of information, such as available flights or hotels, recorded in notepad). This process can be refined iteratively. Search Agent may receive feedback Mearch E F Frearhh from previous failed planning attempt, guiding
4

---

Published as a conference paper at ICLR 2026
it to search for different information resolve the failure (as detailed in Section 3.3). Search: Q x search - D, D = Search(Q', Freanch) = (T o Q)((', Frerch
search = Ø by default at the start of each turn, Ω : Q Fearchh + O is the function that gathers raw observations from external environment, and r O D is the domain extraction function that filters and structures these observations into domains. We instantiate Search with standard ReAct-based tool calling module (Yao et al., 2023).
where Ft.0
Constraint construction. Once the domains are populated, Constraint Manager identify and codify the complete set of constraints, C+., This set is combination of two types of rules: explicit constraints C that are derived directly from the user query Q' and the current domains D and implicit constraints Cy that reflects fixed domain knowledge or commonsense rules that are often unstated (e.g., for vacation travels, must return to the origin city).
Constrain: QxD +
Che Constrain(Q', D'.) -ht UCC Ch. == Dr.
where O - C the function for explicit-constraint extraction. We note that the Constraint Manager's 's role is where LLMs are particularly effective. An LLM's advanced natural language understanding allows it to expertly parse complex queries and search results to extract explicit constraints. Furthermore, its vast repository of world knowledge and commonsense reasoning enables to infer the crucial implicit constraints that are necessary for creating a coherent and logical plan.
3.2 PLAN VERIFICATION UNDER CONSTRAINTS (CHALLENGE 2)
The objective of this stage find valid solution for the given CSP instance, ptt = (X, Dre, C.e)). This is addressed with an iterative loop between two specialized agents: a Planner and Checker.
Planning. The Planner agent proposes a candidate solution, i.e,, an assignment is the space of all possible assignments. It may not find a complete and valid assignment (as in Definition 2.1) the first attempt. Hence, improve with each attempt, its decision is informed by the history of previously failed assignments and the feedback explaining why they failed:
Σ where Σ
Plan (x,, D, C) x FPlam)))))) + Σ, a L,i.k = Plan (x, D'.& C ((ohte (paan))
where FlLe FFllan is the feedback on the ith attempted planning ofc,,, and initially, F1..00 2. Such feedback is provided by the paired Checker agent follows.
Constraint Checking. The Checker agent verifies the proposed assignment gffc satisfies every constraint in the set C It produces two outputs: a verdict V V, where V (valid, invalid, unsat] and feedback Fplan describing any unsatisfied or unsatisfiable con- straints.
Check : (Q, D, C, Σ) V Fplan:
(VLRk,
E plan
Check (Q',Dh C.e ole.M)
k. The outcome determines the next action. If VLAK = invalid. Flee is sent back to the Planner attempt a revision gf,6,+11 If VLek unsat, the feedback indicates a deeper issue (e.g.. insufficient options in D or incompatibilities in C*.f), which triggers the next major component of our framework: an interleaved search.
3.3 INTERLEAVED SEARCH: RESOLVING INFORMATION GAPS (CHALLENGE 3)
When the Checker returns unsat verdict, it signals that valid plan is impossible with the current information. This triggers the Search Advisor agent to diagnose the underlying information gap. The Search Advisor analyzes the full context (i.e., the user's 's query, the current domains used for planning, the constraints, and the history of failed planning attempts) to pinpoint the root cause of the failure. It then generates targeted feedback message, fi guiding on what new information should be collected to make the problem satisfiable:
SearchAdvise: (Q,D,C, (ExFplan)"
(Ex,C,(EExxpaa))) + Fscarch: FL.E scarch SearchAdvise(Q* Q', D Cf. (.H.H....
where H ((ghi,t p(fti)) )= is the planning history so far. This task is well-suited for an LLM,, which perform high-level reasoning diagnose the information gap and provide feedback
5

---

Published as a conference paper at ICLR 2026
on search. For example, in Figure 2. no available accommodations satisfy both the "children under 10" and "private room" constraints in the currently chosen cities, it suggests searching for options in different city. This new search directive is then fed back to the SearchAgent in Section 3.1, which obtains an augmented domains Dt,(+1 and a refreshed constraint set C1,++1, continuing the loop.
3.4 MULTI-TURN EXTENSION
The single-turn ATLAS in Section 3 can be easily lifted to the multi-turn conversation setting with sequence 'Q'...... " J. When the user updates the query Q' Q ATLAS does not start from scratch. Instead, it uses the final domain from the previous turn, D as a cached memory of known options. The Constraint Manager then immediately processes the new query against this cached domains to generate updated set of constraints, Ch+1,,, That is, at the start of the (t + 1)-th turn, the new CSP instance becomes,
p++1,1 (X, DIL C(+1.1),
:= c C UCI, CE CE -I((Q+I,D'
C++1,1
With this CSP, ATLAS enters the PlaneerChhekke loop in Section 3.2. The goal is to find valid plan using only the information it has already gathered from the previous turn. This is a crucial efficiency step, it avoids unnecessary tool calls if the existing knowledge is already sufficient to satisfy the user's ' new request. Only if this process fails that is, if the Checker concludes with unsat even after K revision steps- does the system determine that the cached information is insufficient. At this point, it triggers the full interleaved search process in Section 3.3, calling the Search Agent to gather new information and resuming the complete single-turn orchestration with caps (K, L).
4 EXPERIMENTS
This section empirically validates our framework. First, we demonstrate its superior performance against competitive baselines on the standard benchmark setup along with a detailed analysis of the contribution of each core component in ATLAS (Section 4)... Second, we extend our evaluation to multi-turn travel planning (Section 4.2). Finally, we demonstrate that ATLAS extends its superior performance even more realistic settings with live web search and multi-turn feedback (Section 4.3).
We first introduce the common experimental setup. Full implementation details are in Appendix D.1.
Benchmark. Our evaluations are built the TravelPlanner benchmark (Xie et al., 2024), standard for assessing travel planning methods in the literature (Lee et al., 2025; Kambhampati et al., 2024).
provides a sandbox environment with APIs for accommodations, restaurants, and transportation, elc. This benchmark is suitable for our study because it is designed to test the capability of satisfying complex constraints under two categories: (i) Hard constraints, which are strict rules derived directly from the user query or search results, such as not exceeding the budget or adhering to accommodation rules; (ii) Commonsense constraints, are based on implicit, practical logic (see Table for details).
Evaluation Metrics. We assess performance using the TraveIPlanner benchmark's ' four official metrics, all reported %: (i) Delivery rate the percentage of queries for which a plan is successfully delivered. (ii) Micro pass rate is the ratio of passed constraints to total constraints considered, for both commonsense and hard constraints. (iii) Macro pass rate is the percentage of delivered plans that pass all constraints of specific type (commonsense or hard). (iv) Final pass rate is the percentage of delivered plans that satisfy all commonsense and hard constraints.
4.1 SINGLE-TURE TRAVEL PLANNING
Baselines. We highlight our setup requiring agents to perform tool-based information searches and discover constraints without any prior knowledge. In the considered setting, we compare our method against three key baselines: (i) ReAct (Yao et al., 2023), the standard for tool use; (ii) Reflexion (Shinn et al., 2023) and EvoAgent (Yuan et al., 2025), popular open-sourced sole-planning baselines in the literature (Xie et al., 2024), but augmented with ReAct-based search; (iii) PMC (Zhang et al., 2025), a mulli-agem framework that relies on LLM- b-ssed task decomposition and delegation. To ensure a fair comparison, all methods are limited to maximum 120 tool calls. For ATLAS, set K = 3 (the maximum check steps) and L = 10 (the interleaved search steps). We use 2.55-n (Comanici et al., 2025) and Claude-Sonnes (20250514) (Anthropic, 2025) as base models.

---

Published as a conference paper at ICLR 2026
Table 1: ATLAS consistently achieves the highest performance on the TravelPlanner benchmark.
Commonsennee 1
Iard Constraint 1
Dataset
Base Model
Method
Delivery
Final Pass
Micro
Macro
Micro
Macro
ReAct
98.33
80.32
29.63
55.55
20.56
ReAct+Reflexion
100.00
79.10
27.22
59.29
50.00
22.22
Gemini-2.5-PP5
ReAct+EvoAgent
100.00
78.06
23.89
$7.86
40.56
12.22
PMC
100.00
78.68
30.56
43.33
37.22
23.33
Validation
ATLAS (ours)
100.00
88.54
48.33
82.62
74.44
44.44
(#180)
ReAci
100.00
79.38
22.78
56.19
38.89
11.67
ReActtReflexion
99.44
74.79
18.33
45.48
28.33
10.00
ReAct-FroAgent
99.44
74.08
19.71
38.05
20.33
8.03
PMC
96.67
76.11
21.67
39.52
30.56
14.44
ATLAS (ours)
100.00
83.40
37.78
56.43
38,89
23.33
ReAct
98.10
78.96
26.00
55.37
47.80
19.50
ReActtReelexion
99.90
77.94
25.90
65.85
$6.70
22.70
Gemini-2.5-Pon
ReAct-EvoAgent
100.00
78.06
26.23
60.41
49.23
15,58
PMC
100.00
79.37
28.30
57.10
46.10
21.08
Test (#1000)
ATLAS (ours)
100.00
85.81
40.50
77.64
70.60
35.00
ReAct
99.20
75.26
16.50
49.04
39.10
10.40
ReAct-Reflexion
99.80
71.84
13.67
37.84
26.70
9.13
Hluue--Soneeer
ReAct-EEoAgent
98.89
67.01
10.00
33.71
20.42
6.11
PMC
100.00
73.89
15.59
45.19
33.56
12.12
ATLAS (ours)
100.00
78.88
31,00
49.43
42.00
18,00
Results. In Table 1, ATLAS consistently achieves the best performance across all metrics, including commonsense and hard constraint satisfaction. ATLAS outperforms PMC, another multi-agent frame- works, because its systemic cichestration-epliiiii designed to handle fundamental challenges like constraint discovery, constraints-awant answering, and information gaps-is more reliable than depending on the emergent decomposition abilities of current LLMs. Furthermore, we find that simply adding search to advanced planners (i.e., Reflexion, EvoAgent) yields no benefit. In fact, complex planning on poor search results can degrade performance, as seen when ReAct+EvoAAgen underperforms ReAct. This failure highlights the information gap created by a single, non-adaptive search and underscores the critical importance of our interleaved search mechanism, which adaptively gathers more context as needed. We present ablation studies on travel days and task difficulty levels in Appendix D.6 and a comprehensive cost analysis of all methods in Appendix D.7.
Sterraa Marage
01.7%
76,7
58.0%
71.2%
53.3%
46 65
40.3%
42.29
29.4%
31.1%
32.25
40.0%
45,0%5
40
Commonsence (Menn))
Hard Constraimt Wacro
31.1%
Herd Constrene (Mtccro)
Rnal
Final Pass
(a) Without vs with Constraint Man- (b) Varying the maximum number ager during the planning phase.
(c) Varying the number of inter- leaved search steps (I.).
of revisions by Checker (K).
Figure Understanding the individual contribution of key components in ATLAS. (a) compares the full ATLAS framework with a variant where the Constraint Manager is disabled. In (b), the baseline (K = 0) is sequential search-then-plan pipeline by ReAct. In (c), the baseline (L = 0) is ReAct augmented with three check steps after each search. Refer to Table 5 for full results.
Analyzing Key Components of ATLAS. In Figure 3, we perform an ablation study to verify that each component of ATLAS successfully addresses its intended challenge. Analysis is on the validation set using Gemini-2.5-Pre First, Figure 3a confirms the importance of explicit constraint management where disabling Constraint Manager causes 14.4% absolute drop in the macro hard constraint pass rate. Second, to improve plan validity under constraints, ATLAS decouples planning from verification using iterative revisions by Checker, and its effectiveness evident Figure 3b. A single check step (K 1) boosts the final pass rate from 20.6% to 29.4%. However, the performance plateaus after
7

---

Published as a conference paper at ICLR 2026
K = 3. suggesting that repeated checks yield diminishing returns when the root cause is information insufficiency from the search, making further checks inefficient 2. This limitation highlights the need for our final component: interleaved search. In Figure 3c, activating it on plan that has already been revised three times increases the final pass rate from 31.1 % to 44.4% with I. = 5, confirming that adaptively resolving information gaps is critical for achieving higher reliability. Collectively, these results show that each component offers a targeted and significant contribution, validating our framework's s design. Additional analysis on failure cases is in Appendix D.5.
4.2 MULTI-TURN TRAVEL PLANNING
Setup. While TravelPlanner only simulates a single-turn travel planning. Flex TravelPlanner (Oh al.. 2025) modify their validation set to simulate multi-turn travelplanning by omitting certain constraints from the original query to be introduced in subsequent turns. We follow their setup to create 2-turn and 3-turn variants of TravelPlanner benchmark, varying the type of new constraints (local like cuisine types or room types, global like budget or the number of people) and the order in which they are introduced. We compare ReAct (i.e., ours without any plan revisions or interleaved search, K = L 0) and ATLAS with K 3, L = 10, to validate the effectiveness of our framework in handling incremental constraints introduced over multiple turns.
Table 2: Main results the Flex- Mlx--rravelllanee benchmark for multi-turn planning.
Tumss
Constraint Type (# of samples)
Method
Delivery
Commonsense Pass
Micro
Macro
Micro
Hard Constraint Pass
Macro
Final Pass
Local (189)
ReAct
100.00
86.51
45.83
66.79
42.86
30.16
2-Turn
ATLAS
100,00
88,23
48.15
75.79
62,96
39.15
Global (240)
ReAct
100.00
85.68
40.00
68.34
51.67
26.25
ATLAS
100.00
87.55
48.75
75.97
64.16
39.59
ReAct
100.00
83.70
33.07
59.59
36.51
15.34
Local- becal-then-globn (378)
ATLAS
100.00
87.96
49.21
73.58
53.97
33,60
3-Tum
Glohal-tten than-llthen-nccll (378)
100.00
32.80
59.43
36.24
17.20
ATLAS
100.00
86.81
47.09
71.38
52,12
31.75
Results. In Table 2, we observe that ATLAS consistently outperforms ReAct across all multi-turn settings. As the number of turns and complexity increases, the performance gap widens. For instance, in the 2-turn setting with local constraints introduced, we observe 9% and 13% absolute final pass rate gain over ReAct, when local and global constraints introduced, respectively. As the number of turns increase to 3-turn, we observe even larger performance gain; while ReAct only shows 15.34% or 17.20 % final pass rate, ours doubles the performance regardless of the order of constraint types introduced. Full detailed results with constraint type-wise breakdowns can be found in Table 6.
4.3 MULTI-TURN TRAVEL PLANNING WITH LIVE SEARCH
Setup. To validate ATLAS's utility in a more practical setting, we evaluate it multi-turn travel planning with live web search. We adapt the TravelPlanner validation set by replacing its sandboxed tools with a Google Search tool, enabling agents to find real-time travel information 3. To ensure data availability, all query dates are set to a onc-month period starting from our experiment runtime (August 4th to 18th, 2025). A unique challenge of using a live search tool is the potential for the agent to hallucinate the search results. Hence, we introduce no hallucination rate, a new metric measuring the percentage of plans where all information is not only derived from the search results but is also factually accurate. Factual accuracy is confirmed by independent LLM judge equipped with its own search tool. For ATLAS, we set K = 3, L. = 5. To simulate a realistic user interaction, implement multi-turn feedback loop. After agent generates a plan, we provide corrective feedback for any constraint violations, which is added to the original query for the next turn, creating of evolving constraints (see Figure 4d). This is designed to model how user collaborate with the system to iteratively revise and improve a travel plan which a quite common scenario. Finally, to assess the value of our multi-agent system, we compare ATLAS against ReAct and a monolithic agent baseline that does not use multi-agent decomposition.
In Figure the Appendix, we show that ATLAS effectively diagnoses such unsatisfiable cases and procceds to the next interlcaved search step rather than exhausting its check limits. "eg., www. goog e travel. For detailed specification in the prompts, refer to Appendix F.2
8

---

Published as a conference paper at ICLR 2026
ATLAS
83.9%
ATLAS
ATLAS
83.9%
ReAct Monolithic
92.2%
ReArt
Monolthic
70.0%
Monolithic
58.0%
84.4%.
52.2%
51.7%
76.1%
76.1%
26.1%
31.1%
76.2%
26.1%6
27.25
21.7%
18.3%
65.0%
65.6%
21.1%
17.2%
5.0%
62.2%
3.9%
1.3m
2-Tam
3.um
1-Tum
2-Turn
3.tmm
1-Tum
2-7im
2-Tum
(a) Commonsense (Macro) Pass
(h) No Hallucination
(c) Final Pass
First Turn (T=1)
Second Turn (T=2)
Third Turn (T=3)
Coulc youpect bogetter de tood play startin Charketee
Maroi ray our tf grons sain Tights
www.sccoaaatioooooooooo aolonee
Sepacttion thoue bbugge
Reaadfe Char Houm Aluen Ciy
Brcal Chall thecu Siteei City
Ereaifert iiuus Adattc
Diwan Aukep Timar'
Diwee Adlie Cell Sahaeh
foowe Mowe
Foom
Trme 3000 Artal Time 2030 O6 2015 Land' Graad Roc faruar
Dry
Clpaturs Tim 2007 Artia Time 200002300000 10-300 Lanee Cas Fuoo Nevers
Dac
Yraspertalos TAJEAN
26 th 31-000
Dapacaes
Adractinn Calacin Cankic 1he stcrec Heves Accommicaaaioe
Actommodaatee
(d) Demonstration with ATLAS. End-to-end examples and the user-facing demo are in Appendix E.
Figure 4: Live travel planning with multi-turn feedback. See Table 7 for full results.
Results. Figure 4 confirm the necessity a multi-agent approach, as the monolithic agent presents significantly lower pass rates and more hallucinations. Between ReAct and ATLAS, the performance gap is modest initially, unlike in the sandbox settings of previous sections. We attribute this to the different nature of the two environments: the original benchmark's s sparse sandbox tests an agent's 's ability to handle information gaps and discover a single, hidden solution, whereas the live environment's 's abundant options make the initial task of finding any valid plan simpler, thereby reducing the immediate need for advanced search and revision capabilities. Nonetheless, the effec- tiveness of ATLAS emerges through the multiple turns where the user feedback acts as a series of evolving constraints. After three turns, ATLAS's final pass rate improves from 26. 1 1% to 83.9%, while ReAct and the monolithic agent stagnate at 58.9%, and 27.2%, respectively. More importantly, ATLAS effectively uses feedback to reduce factual errors, achieving a no- no-hallucination rate of over 92%. contrast, ReAct's rate stagnates at 76%, showing it cannot learn from feedback to improve its factuality. This demonstrates that our proposed framework can effectively handle the evolving constraints and reliability demands of dynamic, multi-turn planning process with live search.
CONCLUSION
In this paper, we formalized the general constrained planning tasks, and addressed its three funda- mental challenges: dynamically managing complete set of explicit and implicit rules, ensuring plan validity through iterative revision, and resolving information gaps via adaptive search. We introduced ATLAS, multi-agent framework where specialized components systematically tackle each of these challenges. Using travel planning as a demanding testbed, ATLAS achieves state-of sfute-of-the-ee mance on the TravelPlanner benchmark and its multi-turn variants. Furthermore, we demonstrated its robust performance in a highly realistic setting with a live web environment and multi-turn feedback.
fit--thertt art perfor-
Future Work. Our work opens several exciting directions for reliable agents that can operate within the complex open-world constraints. While we used effective, simple instantiations for each compo- nent, future work could explore more advanced modules; e.g., the Planner could incorporate parallel test-time scaling techniques for efficiency (Chen et al., 2025), or the Checker could be augmented with a formal CSP solver for more robust verification (Hao et al., 2025b). Beyond enhancing in- dividual components, the framework itself could be applied to new domains requiring grounded, constraint-adhere solutions; e.g., enforcing privacy policy compliance in agent guardrails (Xiang al., 2025) or modeling personalized user preferences (Jiang et al., 2025; Li al., 2025).

---

Published as a conference paper at ICLR 2026
REFERENCES
Anthropic. System Card:
Claude Opus 4 & Claude Sonnet 4. Anthropic, May 2025. URL https: //www-cdn, anthropic com/ (aw.000000000000.ee0aaaaa2888882 pdf. Accessed: August 25, 2025.
Christian Bessiere, Rémi Coletta, Barry O'Sullivan, and Myriam Paulin. Query-driven constraint acquisition. In Proceedings of IJCAI-07, pp. 50-55, 2007.
Sally C. Brailsford, Chris N. Potts, and Barbara M. Smith. Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3)5557-581, 1999a. ISSN 0377-2217. doi: http:///ccceeeeettttt///////////
URL https:
// //www www.sceiieccccccc.ooo rect. com/ wtw.teeett...ceeeeeeeeeeeeeeeeee
Sally C. Brailsford, Chris N. Potts, and Barbara M. Smith. Constraint satisfaction problems: Algo- rithms and applications. European Journal of Operational Research, 119(3):557-581, December
1999b. ISSN 03772217. doi: 10. 101101650077-2211700000333
Aili Chen, Xuyang Ge, Ziquan Fu, Yanghua Xiao, and Jiangjie Chen. TravelAgent: An Al Assistant for Personalized Travel Planning, September 2024. URL http: : htlp://azze http://axwv..rg./.......ooo..o.t abs 2400.. 08069. arXiv:2409.0800 08069 [cs].
Jiefeng Chen, Jie Ren. Xinyun Chen, Chengrun Yang, Ruoxi Sun, and Sercan Ô Ark. SETS: Leveraging veff-Verification and Self-Correction for Improved Test-Time Scaling, February 2025.
Jihye Choi, Nils Palumbo, Prasad Chalasani, Matthew Engelhard, Somesh Jha, Anivarya Kumar, and David Page. Malade: Orchestration of llm-powered agents with retrieval augmented generation for pharmacovigilance. In Machine Learning for Healthcare Conference. PMLR, 2024.
Gheorghe Comanici, Eric Bieber, Mike Schackermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261, 2025.
Rina Dechter. Constraint Processing. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003. ISBN 1558608907
Rina Dechter and Avi Dechter. Belief maintenance in dynamic constraint networks. Proceedings of the Seventh AAAI National Conference on Artificial Intelligence, AAAI'88, pp. 37-42. AAAI Press, 1988.
George Ferguson, James Allen, and Brad Miller. Trains-95; Towards assistant. In Proceedings of AIPS-96, pp. 70-77, 1996.
planning
Richard E. Fikes and Nils J. Nilsson. Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3):189-208 1971. ISSN 0004-3702. doi: 10.1016/ (004-37002(7))00000-5
Maria Fox and Derek Long. Pdd12.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20:61-124, 2003.
Eugene C Freuder and Richard Wallace. Suggestion strategies for constraint based matchmaker agents. In International Conference on Principles and Practice of Constraint Programming, pp. 192-204. Springer, 1998.
Boyu Gou, Zanming Huang, Yuting Ning, Yu Gu, Michael Lin, Weijian Qi, Andrei Kopanev, Botao Yu, Bernal Jiménez Gutiérrez, Yiheng Shu, et al. Mind2web 2: Evaluating agentic search with agedde arXiv preprint arXiv:2506.21500
2025.
Zhibin Gou, Zhihong Shao, Yeyun Gong, yelong shen, Yujiu Yang, Nan Duan, and Weizhu Chen. CRITIC: Large language models self-correct with tool-interactin critiquing. In The Twelfth International Conference on Learning Representations, 2024, URL https::/openreee /pppreevie.. net/ met//form2i0 (tt.rrmmmmixxx000xxxxxx
10

---

Published as a conference paper at ICLR 2026
Atharva Gundawar, Mudit Verma, Lin Guan, Karthik Valmeekam, Siddhant Bhambri, and Subbarao Kambhampati. Robust Planning with LLM-Modulo Framework: Case Study in Travel Planning. May 2024.
Yilun Hao, Yongchao Chen, Yang Zhang, and Chuchu Fan. Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools, January 2025a.
Yilun Hao, Yang Zhang, and Chuchu Fan. Planning anything with rigor: General-purpose zero-shot planning with lim-based formalized programming. The Thirteenth International Conference on Learning Representations, 2025b.
Marti A. Hearst. Mixed-initiative interaction. IEEE Intelligent Systems, 14(5):14-23, 1999.
Keith J Holyoak and Dan Simon. Bidirectional reasoning in decision making by constraint satisfaction. Journal of Experimental Psychology: General, 128(1):3, 1999.
Richard Howey, Derek Long, and Maria Fox. VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL. In Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 294-301, 2004.
Mete Ismayilzada, Debjit Paul, Syrielle Montariol, Mor Geva, and Antoine Bosselut. CRoW: Benchmarking commonsense reasoning in real-world tasks. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 9785 9821, Singapore, December 2023, Association for Computational Linguistics. doi: 10. 16.1/6 00/33/1/22222 wetp://0.3mmmmmiinnammmm 2023. emnlp-maiie 607/.
URL https: / /tc//acaaao wnwhhlogthhoyy....ooooooooooooo. org/
Bowen Jiang, Zhuoqun Hao, Young-Min Cho, Bryan Li, Yuan Yuan, Sihao Chen, Lyle Ungar, Camillo Taylor, and Dan Roth. Know me, respond to me: Benchmarking Ilms for dynamic user profiling and personalized responses scale. arXiv preprint arXiv:2504.1422 2025.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B. Murthy. Position: LLMs can't 't plan, but can help planning in Loouuo frameworks. In Proceedings of ICML 2024 (PMLR Vol. 235), pp. 22907729007 2024.
Stefanie Krause and Frieder Stolzenburg. Commonsense reasoning and explainable artificial in- telligence using large language models. In European Conference on Artificial Intelligence, pp. 302-319. Springer, 2023.
Kuang-Huce Huei Lee, Ian Fischer, Yuch-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schuurmans, and Xinyun Chen. Evolving Deeper LLM Thinking, January 2025.
Hao Li, Chenghao Yang, An Zhang, Yang Deng, Xiang Wang, and Tat-Seng Chua. Hello again! I1 llm-pwwered personalized agent for long-term dialogue. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume Long Papers), pp. 5259-5276, 2025.
Zhengdong Lu, Weikai Lu, Yiling Tao, Yun Dai, ZiXuan Chen, Huiping Zhuang, Cen Chen, Hao Peng. and Ziqian Zeng. Decompose, plan in parallel, and merge: A novel paradigm for large language models based planning with multiple constraints. arXiv preprint arXiv:2506.0268.3 2025.
Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 801)99--188, 1977.
ISSN 0004-3702. doi: (2.100660000433227779000000
Sanjay Mittal and Brian Falkenhainer. 1990-Dynamic Constraint Satisfaction Problems.
Rejichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vincet Kosaraju, William Saunders, et al. Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:21 2021.
Juhyun Oh, Eunsu Kim, and Alice Oh. TreeeeervePl,:::::: A Benchmark for Flexible Planning with Language Agents, June 2025.
11

---

Published as a conference paper at ICLR 2026
Mihir Parmar, Xin Liu, Palash Goyal, Yanfei Chen, Long Le, Swaroop Mishra, Hossein Mobahi, Jindong Gu, Zifeng Wang, Hootan Nakhost, Chitta Baral, Chen- Yu Lee, Tomas Pfister, and Hamid Palangi. PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving, February 2025.
Ronald P. A. Petrick and Fahiem Bacchus. A knowledge-based approach to planning with incomplete information and sensing. In Proceedings of AIPS-02, pp. 212-222, 2002.
Ronald P. A. Petrick and Fahiem Bacchus. Extending the knowledge-basee approach to planning with incomplete information and sensing. In Proceedings of ICAPS-04, 2004.
Francesca Rossi and Allesandro Sperduti. Acquiring both constraint and solution preferences in interactive constraint systems. Constraints, 9(4):311-332, 2004.
Timo Schick, Jane Dwivedi-Yo Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems, 36:68539-68551, 2023.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 00:8634-8652. 2023.
Harmanpreet Singh, Nikhil Verma, Yixiao Wang, Manasa Bharadwaj. Homa Fashandi, Kevin Ferreira, and Chul Lee. Personal Large Language Model Agents: A Case Study on Tailored Travel Planning. In Franck Dernoncourt, Daniel Preotiuc-Pietro and Anastasia Shimorina (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track, pp. Miami, Florida, US, November 2024. Association for Computational I Linguistics. doi: 10.18653/v
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambham- pati. On the planning abilities of large language models: A critical investigation. In Proceedings of NeurlPS 2023, 2023.
Junde Wu, Jiayuan Zhu Yuyuan Liu, Min Xu, and Yueming Jin. Agentic reasoning: A streamlined framework for enhancing LLM reasoning with agentic tools. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 28489-28503, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-89176- 251-0. doi: 00.18653/v1/2255 acl--ong............-.. 1383. URL acl- acl-long 1383/.
http:///aaaaaagga//////// 2222
Zhen Xiang, Linzhi Zheng, Yanjie Li, Junyuan Hong, Qinbin Li, Han Xie, Jiawei Zhang, Zidi Xiong, Chulin Xie, Carl Yang. Dawn Song, and Bo Li. GuardAgent: Safeguard LLM Agents by Guard Agent via Knowledge-Enables Reasoning, May 2025.
Chengxing Xie and Difan Zou. A Human-Like Reasoning Framework for Multi-Phasee Planning Task with Large Language Models, May 2024.
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. TravelPlanner: A Benchmark for Real-World Planning with Language Agents, October 2024.
Jian Xie, Kexun Zhang, Jiangjie Chen, Siyu Yuan, Kai Zhang, Yikai Zhang, Lei Li, and Yanghua Xiao. Revealing the Barriers of Language Agents in Planning. In Luis Chiruzzo, Alan Ritter, and Lu Wang (eds.). Proceedings of the 2025 Conference of the Nations of the Americus Chupter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). pp. 1872-1888, Albuquerque, New Mexico, April 2025. Association for Computational Linguisties. ISBN 1---88887776111111
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Synergizing Reasoning and Acting in Language Models. arXiv, March 2023. doi: 10. 10.44550/arXiiv22200555
12

---

Published as a conference paper at ICLR 2026
Siyu Yuan, Kaitao Song, Jiangjie Chen, Xu Tan, Dongsheng Li, and Deqing Yang. EvoAgent: Towards Automatic Multi-Agent Generation via Evolutionary Algorithms, March 2025.
Cong Zhang, Xin Deik Goh, Dexun Li, Hao Zhang, and Yong Liu. Planning with Multi-Constraints via Collaborative Language Agents. In Owen Rambow, Leo Wanner, Marianna Apidianaki, Hend Al-Khalifa, Barbara Di Eugenio, and Steven Schockaert (eds.). Proceedings of the s1 International Conference on Computational Linguisties, pp. 10054-10082 Abu Dhabi, UAE, January 2025. Association for Computational Linguistics.
Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models commonsense knowledge for large-scale task planning. Advances in neural information processing systems, 36:31967-31987, 2023.
Huaixiu Steven Zheng, Swaroop Mishra, Hugh Zhang, Xinyun Chen, Minmin Chen, Azade Nova, Le Hou, Heng-Tze Cheng, Quoc V. Le, Ed H. Chi, and Denny Zhou. NATURAL PLAN: Bench- marking LLMs Natural Language Planning, June 2024.
13

---

Published as a conference paper at ICLR 2026
APPENDIX
A EXTENDED RELATED WORK
Constrained question answering. Constrained question answering a classic planning problem where a system must process natural language query into variables, options, and relations, then search for a feasible assignment of variables that satisfies the objective. Recent work with LLMs has advanced this capability through various approaches, including test-time schemes that amplify reasoning through sampling, self-verification, and revision (Lee et al., 2025; Chen et al., 2025), LLM-modulo paradigms that pair LLMs with external verifiers/solvers (Kambhampati al., 2024; Gundawar et al., 2024), or multi-agent orchestration that strengthens planning via division of roles and iterative verification (Parmar et al., 2025). However, these lines largely assume sole-planning where all necessary information is presumed to be available upfront (Zheng et al., 2024). They focus on improving planning capability itself, rather than the critical, real- world challenge of acquiring the necessary context information, which is often beyond the LLM's ss internal knowledge.
The challenge of search in practical planning. Real-world tasks like travel planning require both searching for viable options (e.g., flights, hotels) and composing them into a constraint-coniise plan. The TravelPlanner benchmark (Xie al., 2024) provides a realistic sandbox with tools and millions of records to test this compound competence, revealing the task's difficulty: even strong LLMs like UPT-4-TTurbo achieve near-zero final pass rate. While multi-agent frameworks show improvement, their performance still remains limited, with reported final pass rates often staying in the single digits (Xie Zou, 2024; Yuan et al., 2025) and rarely exceeding 33% on simpler subsets of the benchmark (Zhang et al., 2025).
Limitations of existing approaches. There exist recent works that achieve much higher scores in this setting; for instance, a satisfiability modulo theories-backen approach reaches 93.9% with GPT-4 (Hao et al., 2025a). However, such performance hinges on having prior, benchmark-speciffi knowledge of all constraints and evaluation metrics (e.g., local constraints) into the solver. Such knowledge is unavailable in practical scenarios that require open-world discovery is required, where an agent must dynamically extract and reconcile constraints from varied sources. Furthermore, existing work is rarely evaluated in truly realistic settings. Prior approaches are demonstrated within sandbox, considering live information search handling multi-furn user interaction. While recent benchmarks like Flex-Trre TravelPlanner (Oh et al., 2025) provide a setup with dynamic, multi-turn constraints, they still operate within a sandbox and focus on exploring sole-planning performance. The critical investigation of constraint- planning with live search remains largely unaddressed.
Our positioning. To this end, we contribute general multi-agent framework that addresses these gaps. Our work presents reliable performance on complex planning task without relying on prior knowledge of the constraints. Furthermore, we are the first to validate our approach in highly practical setting that combines live information search with multi-turn conversational feedback, showing that our framework extends effectively to handle the demands of real-world travel planning.
14

---

Published as a conference paper at ICLR 2026
B CONNECTIONS TO CLASSICAL PLANNING AND CSP LITERATURE
The design of ATLAS is motivated by challenges that are modern incarnations of well-studied prob- lems classical artificial intelligence, particularly in automated planning and Constraint Satisfaction Problems (CSP). Here, we elaborate on the connections between our three core challenges and this foundational literature.
Challenge 1: Constraint Construction. The first challenge, identifying the complete set of implicit and explicit constraints, mirrors the classic knowledge-acquiistion bottleneck. In the CSP literature. this is known as constraint acquisition, a line of work focused on learning or eliciting missing constraints that are not explicitly stated in the initial problem definition. Early systems explored interactive methods to acquire constraints from users, while later work developed techniques to automatically learn them from examples or interaction, which is analogous to how ATLAS must infer rules from natural language query and search results (Freuder & Wallace, 1998; Bessiere et al., 2007; Rossi & Sperduti, 2004).
Challenge 2:
Constraints-Awar Planning. The second challenge, generating valid plan that principle in automated planning
verifiably adheres to all known rules, follows a long-cstabling Classical systems often relied strict separation between plan synthesizer (the generator) and a plan validator (the checker). A plan would be generated and then formally validated against a world model and set of rules, often expressed languages like PDDL (Fox & Long, 2003; Howey et al., 2004). Our Planner- Verifier architecture directly implements this robust "generate-then- paradigm, technique now being adapted to improve the reliability and conformance of modern LLMs (Gou et al., 2024; Choi et al., 2024).
Challenge 3: Resolving Information Gap. The third challenge addresses failures caused by insufficient information rather than logical errors. This problem was central to classical planning in partially observable environments, where agents had to interleave planning with sensing actions to gather new information about the world before proceeding (Petrick & Bacchus, 2002; 2004). This concept also drove the development of mixed-initiative systems, where the most effective approach involves alternating between proposing partial plans and fetching missing facts, often in collaboration with a human user (Ferguson et al., 1996; Hearst, 1999). ATLAS's s adaptive interleaved search is a direct implementation of this principle, enabling the agent to diagnose and resolve information gaps on the fly.
15

---

Published as a conference paper at ICLR 2026
C
ADDITIONAL DESCRIPTIONS OF ATLAS
Function (Agent)
Input types
Output types
Role
Search
Q¹ spupt
Doe O
Tool interaction & domain construction Identify explicit implicit constraints
Constrain
Q¹ Deit
Plan
pte, Iiathe, pltt
) Mil plai
glick Viek
Propose candidate plan
Check
Q' Q'peee otied
pack plun
Verify plan: provide feedback on violations
SearchAdvise
Q¹, pie (lotes plas Mimi
Diagnose unsatisfiability suggest search
Table 3: Typed function signatures for the agents in ATLAS. We use ptf as shorthand for the CSP instance (X, Dr. C. The indices t, kt represent the conversation turn, the (interleaved) search step, and the planner-checker interaction step, respectively.
We provide the algorithmic overview of ATLAS Algorithm 1.
Algorithm 1 Multi- Turn Travel Planning with ATLAS
Require: Sequence of user queries {Q' ,Q..,... Q²) }; Max loops (L, K) Initialize domain memory b Loop over conversation turns Start with cached domain from the previous turn b Loop for interleaved search
1: Denche f- 0
2: for = 1 to T do
3:
D t- Deuche
4: for = 1 to L do
5:
Ct. Constrain(Q', D4.)
6:
pL, 4 (X, DC, C..)
7:
historyplan + []
8:
V +- invalid K do + Plan(Pt.f, histor
b> Initialize verdict for this search loop Inner loop for plan-and-check attempts
9:
for
10:
11:
(V. Fptm) + Check(Q', pt,t .))
historyphan apwpndd(paa ((a, Fptan))
13:
V valid then
14:
Deache + DT.
> Update memory with the successful domain Exit inner and outer loops for this turn
15:
break
16:
else if = unsat then
break
Exit inner loop trigger new search
18:
end if end for
20:
if V = valid then
Output solution o and proceed to next turn. break
22:
else
no solution found, diagnose failure to guide the next search Fscarch f- SearchAdvise( pt.E, historyypan)
24:
25:
D1.+1 +- Search(Q" Q', Feearch)
Get new domain for the next iteration
26:
end
27:
end for
28:
end for
16

---

Published as a conference paper at ICLR 2026
D ADDITIONAL EXPERIMENTS
D.1 ADDITIONAL DETAILS ON THE EXPERIMENTAL SETUP
TravelPlanner (Xie et al., 2024). This benchmark includes 180 queries for validation set, and 1000 queries for the test, where each query specifies explicit requests (e.g., trip duration, budget, cuisine preferences, etc.) that define the constraints the final plan must satisfy. These are categorized into: (i) Hard constraints, which are strict rules derived directly from the user query, such as not exceeding the budget or adhering to a required cuisine types; (ii) Commonsense constraints, are based on implicit, practical logic, such as ensuring reasonable route during the given trip duration, or planning a day's 's activities in the same city. This benchmark provides a sandbox environment including accommodations, restaurants, and transportation, and the agent is expected search information relevant to the query within the sandbox. Detailed descriptions on the constraint types are in Table 4.
Table 4: Descriptions on the considered constraint.
Legend in Figures
Description
Commonsense Constraini
Confieting Transportations
Transpartation choices within the trip must be reasonable. "fight" would be considered contlict.
example, having both "self-driving" No key information should be left out of the plan (e.g. lock of accommcdation) Changes in citess during the trip must be reasonable.
Incomplete Information Unreusonable City Route
The number of consccutive days speat in a specific accommodation during the trip must meet the corresponding required minimum number of nights' stay Restaurunt choices
Minimum Nights Stay
Repeated Restaurants
not he repeated throughout trip.
Hallucinated Details
All information in the plan must be within the closed sandbox; otherwise, will be considered a hallucination. day
Outside Current City
scbeduled activities
located within day 's city(s).
Hard Constraint
Eval unqualificd
Chocking hard constraint not meaningful since some details are missing or ballucinsted.
Rudget exceeded
The total budget of the trip.
Cuisine
Cuisines include "Chinese", "American" "Itliin", "Mexican", "Indian", "Mediterranenn" and "French".
Roem Rule
Room rules include "No parties". "No smoking". - "No children under 10", "No pets", and "No visitors" types inclode "Entire Room", "Private Room". "Shared Room", and "No Shared Room"
Type
TravelPlanner with Live Search. We adapt the TravelPlanner benchmark to assess performance in a realistic, open-domain setting. While retaining the queries from the validation set, replace the benchmark's 's static, sandboxed data for accommodations, flights, restaurants, and attractions with a live Google Search tool. This required modifying certain unrealistic constraints present in the original data. For instance, accommodation attributes such as "Room type" (e.g., "private room") ") and "Room rule" (e.g., "No parties") are not typically available through real-world search. Consequently. we excluded these specific constraints from both our cntommattonngahhrriin prompts and the final evaluation criteria to ensure a fair assessment under real-world conditions.
Additional Evaluation Metric in TravelPlanner with Live Search. We note that live search introduces a challenge not present in the sandbox setting: the search results themselves can be hallucinated by the search agent. Hence, in addition to the evaluation metrics used in the sandbox setting (Section 2), we introduce an additional metric to capture this aspect: no hallucination rate. measures the ratio of plans with all travel details being drawn from the not hallucinated search results, to total plans attempted. To enable this, we require the search agent to output retrieved information in structured format, exactly the same the sandbox data format for flights, accommodations, restaurants, and attractions, and we use separate LLM-based judge (with the same base model) to verify whether each travel detail in the final plan exists on the web.
17

---

Published as a conference paper at ICLR 2026
D.2 DETAILED RESULTS ON ABLATION STUDY
Table 5: Ablations on the key components of ATLAS Results are on the TraveIPlanner validation set using Gemini-2.5-pro.
(a) Without vs with Constraint Manager using 5 check steps and 10 interleaved search steps.
Delivery
Commonsensee
Hard Constraint
Final
Micro
Macro
Micro
Macro
Pass
w/o Constraint Manager
100.00
86.41
41.67
73.21
60.00
30.00
Construint Manager
100.00
88.54
48.33
82.62
74.44
44.44
(b) Varying maximum number of verificataion steps by Checker. Baseline is the sequential search- then-planning by ReAct.
(c) Varying number interleaved search steps. Baseline is ReAct augmented with three critiques steps after each search.
Stops
Delivery
Micro
Commonsense
Macro
Micro
Hard Constraint
Macm
Final Pass
# Steps
Delivery
Micro
Commonsense
Macro
Micro
Constraint Macro
Pass
Bascline
95.56
77.36
26.11
47.14
38.89
17.78
Baseline
100.00
84.79
40.00
73.81
61.67
31.11
1 step
100.00
85.42
42.22
64.76
53.33
29.44
+ step
100.00
86.81
45.56
80.71
71667
40.56
steps
steps
+ stops
100.00
84.65
40.00
68.33
58.89
32.22
+ steps
100.00
88.12
47.78
84.76
76.67
44.44
Total Interactions
Total Interactions
10
15
10
Ln
5
3 days
days
7 days
3 days
days
7 days
(a) TraveIPlanner.
(b) Live Travel Planning.
Figure 5: Distribution of the total number of check steps. We set maximum three critique steps per each search step including 10 additional interleaved search steps.
As shown in Figure 5, even when we allow for high maximum number of interactions (i.e., 33 steps), ATLAS resolves most cases within total interactions between Planner and Checker. This indicates that ATLAS is mostly efficient at finding valid solution before exhausting its limits. Based on these trends, a strategic tuning of these hyperparameters is crucial for balancing performance and cost in real-world deployment.
18

---

Published as a conference paper at ICLR 2026
D.3 FULL RESULTS ON MULTI-TURN TRAVEL PLANNING
Flex- TravelPlanner. In addition to Table 2, we provide the detailed results on Flex-TravelPlanner benchmark in Table 6.
Table 6: Results of ATLAS on the Flex-TrrvvePlanner benchmark.
Commonsense
Hard Constraint
Constraint Type
Method
Delivery
Final Pass f
Micro
Macro
Miero
Macro
2-Turn (Local)
ReAct
100.00
79,43
31.25
70.95
47.92
22.92
Cuisine (#48)
ATLAS
100.00
85.42
41.67
85.81
75.00
35.42
ReAct
100.00
87.66
48.85
64.55
36.36
29.87
+ Room rule (#77)
ATLAS
100.00
89.29
51.95
66.79
53.25
38.96
100.00
90.43
53.12
66.36
46.88
35.94
Room type (#f44
ATLAS
100.00
89.06
48.44
79.09
65.62
42.19
2-Turn (Global)
ReAct
100.00
86.35
42.50
70.00
51.67
25.83
Number of People (#120)
ATLAS
100.00
87.50
50.83
77.50
65.83
41.67
100.00
85.00
37.50
66.67
$1.67
26.67
+ Budget (#120)
ATLAS
100.00
87.60
46.67
74.44
62.50
37,50
3-Turn
ReAct
100.00
83.70
33.07
59.59
36.51
15.34
Local-then-global (4378)
ATLAS
100.00
87.96
49.21
73.58
53.97
33.60
ReAct
100.00
84.06
32.80
59.43
36.24
17.20
+ Global-then Shobal-teen-loal (H378)
ATLAS
100.00
86.81
47.09
71.38
52.12
31.75
Multi-Turn Travel Planning with Live Search. addition Figure 4, we provide the full results on all metrics in Table 7.
Table ATLAS Multi-turn feedback on live travelplanning.
Commonsense Micro
Hard Constraint
Method
Delivery
No Hallucination
Final Pass 1
Macro
Micro
Macro
Monolithic
81.11
61.60
5.00
10.04
10.00
65.00
3.89
+ I-turn
85.56
72.29
18.33
22.58
22.78
62.22
17.22
+ 2-turn
90.00
79.79
31.11
29.75
27.78
65.56
27.22
ReAct
100.00
80.28
21.67
50.54
51.67
76.22
21.11
+ 1-turn
100.00
91.18
52.22
62.01
62.78
74.44
51.67
+ 2-turn
99.44
92.15
58.89
67.38
67.22
76.11
58.89
ATLAS
100.00
82,08
26.11
64.87
62.78
76.11
26.11
+ I-turn
100.00
94.79
70.0
77.06
75.56
84.44
69.44
+ 2-turn
100.00
96.81
83.89
86.38
86.11
92.22
83.89
19

---

Published as a conference paper at ICLR 2026
D.4 WITHOUT vs WITH UNCONVENTIONAL DENCHMARK-SPECIAS CONSTRAINTS
In addition to Figure 6, we show the full results for all evaluation metrics in Table
Table 8: ATLAS without vs with benchmark-specifie unconventional requirements directly
provided to the Constraint Manager.
Commonsense f
Hard Constraint 1
Base Model
Constraint Manager
Delivery
Final Pass f
Micro
Macro
Micro
Macro
without hint
100.00
88.54
48.33
82.62
74.44
44.44
Gemini-2.5-pro
with hint
100.00
93.61
70.56
79.29
71.11
59.44
without hint
100.00
83,40
37.78
56.43
38.89
23.33
Claude-Sonnet-4
with hint
100.00
85.42
48.33
60.71
47.22
33.33
93.6%
without with hint
88.5%
70.6%
60.2%
44.4%
Pass
Figure 6: Providing the two benchmark-specific rules as constraints to the Constraint Manager further improves the performance, demonstrating our framework's ability to effectively explicit guidance.
20

---

Published as a conference paper at ICLR 2026
D.5 FAILURE ANALYSIS OF ATLAS
TravelPlanner. Constraint failure analysis reveals ATLAS's effectiveness and the nature of its remaining errors (Figure 7). Compared the simplest baseline with K L 0, ATLAS substan- tially reduces failures across all categories, especially in eliminating hallucinations and including necessary details (see light green and green bars in Figure 7a vs. 7b). It excels at enforcing constraints discovered from search results (e.g., an accommodation' 's "minimum nights stay" rule from 33 to 4). This success stems from the Constraint Manager, which reasons over and identifies emergent rules from both the user query and retrieved data.
Despite these gains, two emorr types remained prominent: "Conflicting "ransportations" and "Re- peated Restaurants". These reflect benchmark-speciffe rules, termed unconventional hints in Zhang al. (2025), that may not necessarily align with real-world practices (e.g., user cannot visit the same restaurant twice, or mix flights with self-driving). Adopting the setup by Zhang et al. (2025) that provide them as additional hints to their planning agent, we consider providing these as explicit constraints to our Constraint Manager. This change cause the final pass rate to jump from 44% to 60% Figure 6, and the corresponding failure analysis (Figure 7c) confirms that these two error types were largely eliminated, and now remaining errors primarily due to the base model's inherent reasoning limitations, such as creating illogical city routes or still hallucinating some details. This demonstrates that ATLAS is highly effective at ensuring constraint compliance, pushing performance to the limits of the base model's ' capabilities.
Gemini-2.5-Pro
Canf kiing Ensgoo DWSEnS
Co Corkkcing Densprrattin Repoitedd Resturents
10
23
Iccopleee internation
Detals
60
Mirirrm Myrts Stay Repccaied Rezluannrs listuctrraed Becall
liskudrated Danels innomplate into munion Durs de currert city fay Stay
Duiasee Curest
Cootl ro Trrspomition
50
32
14
26
20
10
(a) ATLAS with K = 0, -
(b) ATLAS
(c) ATLAS with Hints
Claude-Sonnet-4
89
Minirum Miris Hnllcirated Denall
K5
Haltdrettd Decalt Unressomatle City Route Masimum Aight Stay Repaasted Reszaurares Duts de the Current City
lecomp information
Couse tot unes
of
Resested Restarrants
43
2
31
13
(d) ATLAS with K = O, L-
(e) ATLAS
(f) ATLAS with Hints
Figure 7: Breakdown of commonsense constraint failures. The figure illustrates the progressive reduction of errors from the (a) ATLAS without any check interactions or interleaved search (i.e., ReAct), to (b) ATLAS with K 3, 10, and finally to (c) ATLAS supplied with additional benchmark-specifee constraints, following Zhang al. (2025). Results are on the TravelPlanner validation set using Gemini-2.5-pro (top) or 4laude-Sonnet-4 (bottom).
Multi-Turn Travel Planning with Live Search. We analyze the failure modes of each method in the multi-turn live search setting, observing how they address failures from the previous turn. As shown in Figure 8, simple constraint violations like repeated restaurant choices conflicting transportation (light blue and blue bars) are easily resolved by all methods, since live search provides a virtually unlimited pool of alternatives.
21

---

Published as a conference paper at ICLR 2026
However, more complex failures reveal key differences. The monolithic agent consistently fails to actually conduct the search to collect grounded context information rather than solely relying on its internal knowledge (see green bars in Figure 8a). While ReAct uses search to present the searched context information, it still hallucinates the details its itinerary, problem not effectively resolved with explicit feedback (purple bars in Figure 8b). In contrast, ATLAS successfully grounds its plans in the search results and adheres to dynamic constraints from user feedback throughout turns.
Before interaction
After 1-Turn Interaction
After 2-Turn Interaction
100
102
Halh anadiiaa
82
Culas the Curner
Hall-i afrundd Data
60
63
alrard Dara
80
(iaiei city
Faltues
5
Coount netures
50
44
del dhte
60
29
14
11
(a) Monolithic agent.
Before interaction
After 1-Turn Interaction
After 2-Turn Interaction
70-
Craddaa Deaal
lictin rrerporaaics
Gusade
50
Ounn
Outaic Carner
Count of natuues
Nasta
41
30
20
30
24
22
Count
1.5
11
12
10
(b) ReAct.
Before interaction
After 1-Turn Interaction
After 2-Tumn Interaction
80
73
Faym Festrannss aistilua
39
aitrrta Date
31
arwine Data
City
30
bute natale Faxeed
80
havee Ciy
Crurs of metures
25
50
Halh oe Disuls
Seoe atdd Redeernes
20
Arpenttod Mitecc
17
20:
35
20
17
14
(c) ATLAS
Figure Breakdown of commonsense constraint failure types on live travel planning.
22

---

Published as a conference paper at ICLR 2026
D.6 ABLATIONS ON TRAVEL DAYS AND LEVELS
Table 9: Ablation results on travel days. We compare ATLAS to baselines on the TravelPlanner validation set (60 instances per day subset).
Commonsense
Hard Constraint f
Base Model
Subset
Method
Delivery
Final Pass f
Micro
Macro
Micro
Macro
ReAct
100.00
94.38
65.00
67.86
51.67
45.00
ReAct-Reflexin
100.00
93.12
66.67
77.86
68.33
53.33
3 day
AvoeetEv
100.00
92.08
55.00
67.86
46.67
30.00
PMC ATLAS
100.00
96.04
71.67
82.86
70.00
51.67
100.00
97.92
83,33
92.86
86.67
75.00
ReAct
100.00
75.83
16.67
49.29
40,00
11.67
ReAct-Reflexin
100.00
74.58
15.00
49.29
46,67
13.33
Gemini-2.5-Pro
5 day
EvoAeeEn
100.00
71.88
10.00
45.71
31.67
3.33
PMC
100.00
69.58
11.67
25.71
25.00
11.67
ATLAS
100.00
85.42
33,33
77.86
70.00
31.67
ReAct
98.33
73.54
15.00
51.43
48.33
11.67
ReAct+Reflexion
100.00
69.58
0.00
50.71
35.00
0.00
7 day
RvoAteEv
100.00
70.21
6.67
60.00
43.33
3.33
PMC
100.00
70.42
8.33
21.43
16.67
6.67
ATLAS
100.00
82.29
28.33
77.14
66.67
26.67
ReAct
100.00
88.96
45.00
68.51
50,00
28.33
ReActtReelexion
100.00
89.17
36.67
64.29
40.00
20.00
3 day
RcAAt-EvAAgent
100.00
86.67
28.33
43.57
31.67
18.33
PMC
98.33
90.00
46.67
67.86
50,00
30.00
ATLAS
100.00
95.62
73.33
76.43
56.67
46.67
ReAct
100.00
73.12
6.67
44.29
35,00
3.33
ReAct+Reflexion
98.33
71.25
15.00
25.00
8.33
Claude-Sonnet-4
5 day
ReAct-EvaAgent
98.33
57.71
1.67
8.57
6.67
0.00
PMC
93.33
70.42
11.67
19.29
15.00
6.67
ATLAS
100.00
80.21
21.67
44.29
28.33
11.67
ReAct
100.00
68.12
5,00
41.43
30.00
3.33
ReActtReflexion
100.00
63.96
3.33
30.71
20.00
1.67
7 day
ReAct+EvoAgent
98.33
56.67
5.00
3.33
PMC
98.33
67.92
6.67
31.43
26.67
6.67
ATLAS
100.00
74.38
18.33
48.57
31.67
11.67
Interestingly, in Table 10, observe that ATLAS performs better the "hard" set than the "medium" set. We investigated this phenomenon and found that is consistent with the inherent characteristics of the TraveIPlanner benchmark, rather than anomaly specific to ATLAS. For example, this trend observable Table the original TravelPlanner paper (Xie et al., 2024), where pass rates for "medium" are often lower than "hard" for both two-stage and sole-planning setups. Similarly, Table of the PMC baseline (Zhang et al., 2025) reports a final pass rate for "medium" that 88% lower than "hard". In Table 10, the baseline ReAct also exhibits this pattern (Medium: 11.67% Hard: 21.67% final pass rate).
One possible hypothesis explain this counter-intuitive observation is the trade-off between con- straint complexity and domain set size (search space) in the constraint satisfaction problem.
Easy to medium or hard: The increase in constraint complexity (e.g., adding constraints beyond just budget) the dominant factor, making the task strictly harder.
Medium to hard: While "hard" tasks impose more constraints (adding transportation pref- erences on top of "medium" constraints), these specific constraints act as strong filters that prune the domain of applicable search results significantly. This reduces the number of distractor options for the planning agent, making the correct assignment of values for variables clearer.
Indeed, Table 4 of Xie et al. (2024), as transportation preference constraints are added from medium to hard, there is substantial increase in pass rates for transportation-rellvant criteria e.g.,
23

---

Published as a conference paper at ICLR 2026
"Non-conflicing Transportation" rises from 73.3% to 83.1% in two-stage, and 56.5% 87.5% in sole-ple plaanilnnn settings.
Table 10: Ablation results on task difficulty levels. We compare ATLAS to baselines on the TravelPlanner validation set (60 instances per level subset).
Commonsense
t
Hard Constraint f
Base Model
Subset
Method
Delivery
Final Pass f
Micro
Macro
Micro
Macro
ReAct
100.00
84.17
35.00
73.33
73.33
35.00
RcActtRReflxiin
100.00
78.96
30.00
61.67
61.67
28.33
easy
ReAAct+BoAAget
100.00
76.04
16.67
$5.00
$5.00
15.00
PMC
100.00
82.08
38.33
46.67
46.67
35.00
AILAS
45.00
83.33
83,33
ReAct
98.33
74.38
23.33
45.00
31.67
11.67
ReAct-Reflexion
100.00
73.54
21.67
50.83
43.33
18.33
Gemini-2.5-Pro
medium
ReAcetEvAAgent
100.00
72.71
18.33
41.67
33.33
11.67
PMC
100.00
72.50
25.00
37.50
33.33
18.33
ATLAS
100.00
83.54
38.33
77.50
70.00
35.00
ReAct
100.00
85.21
38.33
57.50
35.00
21.67
ReActtRRefexion
100.00
84.79
30.00
62.92
45.00
20.00
hard
RcAct+EvoAgent
100.00
85.42
36.67
66.67
33.33
10.00
PMC
100.00
81.46
28.33
45.42
31.67
16.67
ATLAS
100.00
94.58
61.67
85.00
70.00
55.00
ReAct
100.00
72.50
13.33
50.00
$0.00
ReAct+Reflexion
98.33
18.33
38.33
38.33
16.67
easy
ReveetEv
98.33
64.38
5.00
16.67
16.67
5,00
PMC
100.00
74.38
13.33
36.67
36.67
13.33
ATLAS
100.00
81.25
33.33
53,33
53.33
30.00
ReAct
100.00
73.54
18.33
44.17
35.00
11.67
ReAct+Reflexion
100.00
70.21
15.00
30.00
21.67
6.67
Claude-Sonnct-4
medium
Rvogeee
98.33
63.57
13.33
20.00
16.67
10.00
PMC
93.33
73.12
21.67
31.67
28.33
16.67
ATLAS
100.00
79.58
30.00
46.67
31.67
18.33
ReAct
100.00
84.17
25.00
$5.42
30.00
11.67
ReAct+Reflexion
100.00
85.00
21.67
55.00
25.00
6.67
hard
Rvogeet
100.00
72.92
11.67
19.17
8.33
3.33
PMC
96.67
80.83
30.00
44.17
26.67
13.33
ATLAS
100.00
89.38
50.00
62.08
31.67
21.67
24

---

Published as a conference paper at ICLR 2026
D.7 COST ANALYSIS
To assess the real-world applicability of ATLAS, we conduct a detailed cost analysis of the framework. As shown in Figure 9, we measure the runtime for each agent on the TravelPlanner benchmark using Gemini-2.5-PP as the base model (refer to Figure 10 for input/output token counts). For a three-day plan, the median runtime over 60 instances approximately 6 minutes, and 15 minutes for 5- and 7-day plans. This demonstrates that ATLAS can resolve most planning requests within a reasonable time frame.
The analysis shows that the Planner agent is the most resource- intenssve component, which is an inherent aspect of any complex planning task. In contrast, our constraint-related agents (i.e., Checker and Constraint Manager) add minimal overhead relative to the significant performance gains they provide. Unsurprisingly, when live search is enabled, the Search agent becomes the primary driver of runtime, eclipsing the Planner (in Figure 9b). We also report the input and output token costs each agent ATLAS in Figure 10.
Seac?
10.0
Aarde:
Aunter
2,5
Checker
0.0
(a) TravelPlanner
(b) Live travel planning using Google search tools
Figure 9: Wall clock runtime of ATLAS with Gemini-2.5-
Parcer instancee)
Instancect
days mibered
days
2.0
Mesaen Soare Aeviva
42002
(a) TravelPlanner with maximum critic planner steps and interleaved search steps.
250020
L50000
24500 Acrear
L00000
(b) LivePlanner using Google scarch tools with maximum 3 critic planner steps and 5 interlcaved search steps.
Figure 10: Token counts for ATLAS. Total number of input (left) and output (right) tokens per each module of our framework.
Table 11 shows the cost analysis on all method. Multi-agente approaches indeed take longer and requires more token costs, but when comparing the median, we observe that ATLAS does not take significantly more costs than other multi-agent baselines (i.e., search-augmente EvoAgent or PMC) for the significant improvement it brings the performance.
Table 11: Cost analysis of ATLAS and baselines. We compare the total wall clock runtime and sum of all output tokens. Results are on the TravelPlanner validation set using Gemini-2.5 2.5-ni-2.5-pro... We report the (25th. 50th (median). 75th) percentiles.
day
5 day
day
Mothod
Rumtime (min
Runtime
(K)
Runtime (min)
(K)
ReAst
(1.20) 1.41, 1.74)
(0.33, 1.07. 17.05)
(2,42, 2.79, 3.28)
(0.71 1.38, 2.09)
(3.49, 3,83, 4.49)
(1.03, 1.78. 2.26)
Re-Act&Reflesion
(1.52, 2.29, 1,52)
(0.62, (184, 1.09)
(2.46, 4.37, 6.15)
(1.27. 1.55, 2.35)
(2.96. 5.41, 8.64)
(1.78, 2.01, 2.56)
7..51,7.13,
(7.92.
26.08)
PMC
(2.57, 2.85, 3.10)
(5.90. 6.69. 7.10)
(5.77.
7.19, 10.31)
(11.4,
12.72, 14.12)
(7.00.
8.35, 12.27)
(15.05,
16.56, 19.13)
ATLAS (ours)
(2.42. 4.07, 6.19)
(1.19,9.52, 20.52)
(4,80, 8.26, 26.22)
(5.53, 19.29,63.03)
63.03)
(5:17, 7.97, 19.88)
(5.27,24.07, 43.86)
25

---

Published as a conference paper at ICLR 2026
E
EXAMPLE OUTPUTS OF ATLAS
E.1 END-TO-END EXAMPLES
E.1.1 TRAVELP
Example 1
Query:
Please create travel plan for where 1'11 be departing from Washington and heading to Myrtle Beach for a 3-day trip from March 13th to March 15th, 2022. can you help me keep this journey within budget of $1, 400?
Output from Constraint Manager
The outbound flight from Washington to Myrtle Beach on March 13th 2022 must be either flight F3792603 or F3927581.
2. The return flight from Myrtle Heach to Washington on March 15th, 2022 must be either flight P3791200 or r3926434.
The chosen accommodation the provided 1ist and have minimum stay requirement of nights or less.
Myrtle Beach must be selected from
4. The house rules for the selected accommodation must be adhered to
All restaurants visited in Myrtle Beach must chosen from the provided list.
6. All attractions visited in Myrtle Beach must be chosen from the provided list.
Washington. 9. The trip must take place from March 13th, 2022 to March 15th, 2022.
start in Washington and The destination city Mystle Beach.
The trip
10. The tctal cost of the trip must not exceed $1,400."
Output from Planner
Day
I:Currrent City: from Washington to Myrtle Beach
iitranpportttoon #light Number: F3927581, from Washingtion to Myrtle Beach, Departure Time: 11:03, Arrival Time: 13:311
nßreakfast: -AnAttraction: Myr=le Beach Boardwalk and Promenade, Myrtle Beach'nIureh First Eas, Myrtle Beach\nDinner: Catfish Charlie's, Myrtle Beachhacccmmmdaiioooon Yellow submarine, Myrtle -\
Beach\n\nDay 2:\nCurrent City: Myrtle
nBreakfast: d' Curry House, Myrtle Beach'nattraction: Ripley's Aquarium of Myrtle Beach, Myrtle Beach; SkyWhell Myrtle Beach, Myrtle Beach. \nLunch:
Pino'z Pizza, Myrtle Beach'nDinner: Nizam's a Kathi Kabab, Myrtle BeachhnAccommodaiicc submarine, Myrtle Beach)/n 3:AnCurrent City: from Myrtle Beach to Washington har.aapoooottraaaaaarrrooooo Flight Number: F3791200, from Myrtle Beach to Rashington, Departure Time: 11:36, Arrival Time: 13:06\nBreakkast: Turning Point Fast Food, Myrtle Beach nAttraction Myrtle Beach State Park, Myrtle Beach, \nlunch: -\ nDinner: -
Yellow
Output from Checker
Deci sion: valid
Output from Search Advisor
Final delivered plan
26

---

Published as a conference paper at ICLR 2026
"day": 1,
"current_city"; "from Washington to Myrtle Beach", "transportation"; "Flight Number: F3927581, from Washington to Myrtle Beach, Departure Time: 11:03, Arrival Time: 13:31", "breakfast"; "-",
"attracticn": "Myrtle Beach Boardwalk and Promenade, Myrtle
Beach;";
"Lunch"; "First Eat, Myrtle Beach", "dinner"; "Catfish Charlic's, Myrtle Beach", "accommcdation": "Yellow submarine, Myrtle Beach"
"day": 2,
"current city": "Myrtle Beach", "transportation": "-",
"breakfast"; "d' Curry House, Myrtle Beach", "attraction"; "Ripley's Aquariun of Myrtle Beach, Myrtle Beach, skyWheel Myrtle Beach, Myrtle Beach;", "lunch": "La Pino'z Pizza, Myrtle Beach", "dinner": "Nizam's Kathi Kabab, Myrtle Beach", "accommcdation"; "Yellow submarine, Myrtle Beach"
"day": 3,
"current_city": "from Myrtle Reach Mashington", "transportation" "Flight Number: F3791200, from Myrtle Beach to Washington, beparture Time: 11:36, Arrival Time: 13:06", "breakfast"; "Turning Point Fast Food, Myrtle Beach", "attraction": "Myrtle Beach State Park, Myrtle Beach;",
"Lunch": "_"
"dinner"; "_"
"accommedation" ion":
27

---

Published as a conference paper at ICLR 2026
Example 2 where interleaved search easily addresses the information gap
Query: Can you assist with travel plan for one pezson departing from Pittsburgh to Baltimore for 3 days, from March 4th to March 6th, 2022, with a maximum budget $1, 200?
Output from Search Agent after initial search step (L = 0)
indxx: 0, "Short Description": "Driving from Pittsburgh to Haltimore", "Content": "self-driving, from Pittsburgh to Baltimore, duration hours 58 mins, distance: 400 km, cost: 20"
;ineex" 1, "Short Description", "Accommodation in Baltimoze", "Content";
"index"; 2, "Short Description"; "Attractions in Baltimore", "Content":
"index": 3,
"Short Description": "Restaurants in Baltimore", "Content":
Output from Constraint Manager at L =
1. The miniman mum stay for accommodation in Baltinore must be nights less.
2. The round trip transportation cost between Pittsburgh and Baltimore is $40.
3. The trip must start from Pittsburgh and return to Pittsburgh. The destination city is Baltimore.
The trip is for one person.
6. The trip must be for 3 days, from March 4th, 2022, to March 6th, 2022.
7. The total cost of the trip must not exceed s;, 200.",
Output from Planner at L 0, K
Day 1: AnCurrettt City: from Pittsburgh to BaltimorrelaTransportaaee self-driving, from Pittsburgh to Baltimore nAttraction: Inner Harbor, Baltimore\niunch: Mr. Dunderbak's Biergarten and Marketplatz, Baltimore\wDinner: Los Pablos, Baltimore wnt.oooaenccooooiiiiooon Contemporary Home Away from Home, Entire house, BaltimoreWnknDay 2:AnCurrent City: Baltimorel. nftrnsportation: -\nBreakfast: Amalfi, Baltimoze'nAttraccta National Aquarium, Baltimore;Fort McHenry National Monument and Historic Shrine, Baitimore. InLuchh Salt, Aattimore'nDinnee. The Thai Bowl, Baltimore from Home, Entire house, Halt Haltimoretnnnnay 3:AnCurrent City: from self-driving, from
-\
Contemporary Home Away
Baltimore to Pittsburghnniyaaapprraiii Baltimore to bicrebbugghhsssrkkfaa:::: Tibb's Frankie, Baltimore) nAttraction: The Walters Art Museum, Baltimore. AnLanch: RollsKing, Baltimore\nDimme
AApAccomoodation: -An
Output from Checker at L O =
Deci sion unsatisfiable
28

---

Published as a conference paper at ICLR 2026
Feedback 1: The plan is invalid because the transportation from Baltimore to Pittsburgh on Day not derived from the provided context information. This failure is due to the lack of information about the return trip in the context, which is necessary to fulfill the constraint of returning to the origin city."
Output from Search Advisor at L =0
Suggested actions:
rlightseearch Baltimore, 2022-03-04:
lotescookfritteelightt from Pittsburgh to Baltimore 2022-03-04] [Light Pittsburgh, 2022-03-06]
(Flebook from Baltimore to Pittsburgh on 2022-03-06)"
Output from Search Agent after the first interleaved search step (L = 1)
index"; 0,
"Short Description": "Driving from Pittsburgh to Baltimore", "Content"; "self-driving, from Pittsburgh to Baltimore, duration 3 hours 58 mins, distance: 400 km, cost: 20"
"index"; 1, "Short Description": "Accommodation in Baltimore", "Content";
"index": 2, "Short Description"; "Attractions in Baltimore", "Content";
"index": : 3, "Short Description": "Restaurants in Baltimore", "Content";
"index": 4, "Short Description": "Flights from Pittsburgh Baltimore 2022-03-04", "Content":
"index": : 5,
"Short Description": "Flights from Baltimore to Pittsburgh on 2022-03-06",
"Content";
Output from Constraint Manager at -=
1. The accemmodation in Baltimere must have minimum stay requirement of nights or less.
The trip must start in Pittsburgh and end in Pittsburgh.
3. The trip must be from March 4th, 2022, to March 6th, 2022.
4. The trip is for one person.
5. The total cost must not exceed $1,200. The destination city is 3altimore."
Output from Planner at L = 1, K 0
Day AnCureeett City: from Pittsburgh to Balliioorelirraaspppttttioo
Flight Number: F3969954, from Pittsburgh to Baltimore, Departure Time: 16:51, Arrival Time: 17:49hnBreakfast. -InActraction: -\
29

---

Published as a conference paper at ICLR 2026
nLunch: -AnDinner: Mr. Dunderbak's Biergarten and Marketplate, Baltimore AnAccomoddation. Contemporary Home Away from Home, Entire house, Baltimoreln'nbaa 2: 2:\nCurrent City: Baltimorel #Dransportation: -\rBreakfast: Amalfi, baltimoze National Aquarium, Baltimore;Fort McRenry National Monument and Historic Shrine, Baltimore. \nlunchh: Los Pablos, Baltimore)
Contemporary Home from Baltimore to PitesbrrghhoTTaasootttttta F3994096, from Baltimore to Pictsburgh, Departure Time: 21:45, Arrival Time: 22:4A\nbreakfast: 28 Capri Italy, Haltimore) nAttractions The Walters Art Museum, maltimore. Tresind Nassima Royal Hotel, Baltimore Mazket, Baltimore www.tiooeenAcccooooooooooooo inAcoomodattiionn
nDinner: Farzi Cafe, waa.timmre\nAcccmmmaattttt Away from Home, Entire house, BaltimorelnnnDay 3:\nCurrent city
Flight Number:
Baltimore\nDinnerr AnDinner: The Manhattan Fish
Output from Checker
sicision: valid
Final delivered plan
"day": 1,
coureentcctty"" "from Pittsburgh to Baltinore", "transpertation": "Flight Number: F3969954, from Pittsburgh to Baltimore, Departure Time: 16:51, Arrival Time: 17:49", "breakfast"; "-",
"attraction"; "-",
"Lunch"; "-",
"dinner": "Mr. Dunderbak's s Biergarten and Marketplatz, Baltimore
"accommcdation"; "Contemporary Away from Home, Baltimore"
"day": 2,
couurent_city"" "Baltimore", "transportation": "_",
"breakfast"; "Amalfi, Baltimore",
"attraction"; "National Aquarium, Baltimore;Fors Fort McHenry National Monument and Historic Shrine, Baltimore;", "lunch": "Los Pablos, Baltimore",
ninn"""; "Farzi Cafe, Haltimore", "accommedattion:; "Contemporary Home Away from Home, Haltimore"
"day": 3,
"current city": "from Baltimore to Pittsburgh",
"transportation". "Flight Number: F3994096, from Baltimore to Pittsburgh, Departure Time: 21:45, Arrival Time: 22:44", "breakfast"; "28 Capri Italy, Baltimore", "attraction": "The Walters Art Museum, Baitimore;", "lunch": "Tresind Nassima Royal Hotel, Baltimore", "dinner": "The Manhattan Fish Market, Baltimore", "accommedat ion"; io
n_"
30

---

Published as a conference paper at ICLR 2026
Example 3 where plan is extensively revised
Query:
Can you create travel plan for group of 5 departing from Charlotte heading to Hilton Head, to be carried out over days, from March 26th to March 28th, 2022? The budget for this trip is capped at $7, CCC. we have a preference for Italian and French cuisines during our trip.
Output from Search Agent after initial search step (I. 0)
index"; 0, "hort Description"; "Transportation from Charlotte to Hiltor. Head", "Content": "self-driving from Charlotte to Hilton Head, duration: 3 hours 49 mins, distance: 398 km, cost: 19"
"index" 1, "Shert Description": "Accommodation in Hilton Head", "Content";
NAME
house_rules minimum nights maximum occupancy review rate number city
price room type
Williamsburg Home Away From Home! 164.0 Entire home/apt 4.0
pets
3.0 Hilton Head
COZY Room @Williamsburg (10 mins to Manhattan)
605.0
Private 2.0
room
No visitors
1
4.0 Hilton Head
"index": : 2,
"Short Description": "Restaurants in Hilton Head", "Content";
Nane Average Cost Cuisines Aggregate
Rating Taste of China Fast Food
city
91
Tea, Seafood, Bakery,
4.0 Hilton Head
K Raga's
Tea, BBQ, Mediterranean,
Desserts
2.9 Hilton Head
New Town Pastry Shop
Park Plaza
51
Tea, Cafe, Pizza, BBQ
3.2 Hilton Head
"index": 3, "Short Description"; "Attractions in Hilton Head", "Content"; Longitude
Name Latitude
Address
Phone
Webaite
City
Coastal Discovery Museum 32.211485 -80. 744025 70 Honey Horn Hilton Head Island, SC 29926, USA (843) 689-6767
http://ww..caatallllccoveyy org/ Hilton Head
31

---

Published as a conference paper at ICLR 2026
Output from Constraint Manager at L ==
The minimum stay for accommodation must Less than equal to nights.
2. The plan must include at least one restaurant that serves Italian cuisine and one that serves French cuisine.
3. The mode of transportation must be self-driving. The trip must start in Charlotte and end in Charlotte.
5. The trip must be for 5 people.
6. The trip must take place from March 26th, 2022 to March 28th,
2022.
7. The total cost of the trip must exceed s7,000.
Output from Planner at L = 0, K =0
Day 1: InCurrent City: from Charlotte to Hilton tead self-driving, from Charlotte Bilton k -\ nÅttraction: Harbour Town Lighthouse, Hilton Head\nLunch: Wrapster, Hilton Head'nDinners Dhaba Ambarsariya, Hilton Head) nAccommodation: Hip, Vibrant, COLORFUL Downtown Manhattan 1 Bed, Hilton Head\n\nDay 2:\nCurrent city: Hilton Head)
ntransportation: -\nBreakfast: Cafe Coffee Day, Hilton Bead nAttraction: Coastal scoveryy Museum, Hilton Head; Coligny Beach Park, Hiltor Anlanch: Mr. Brown, Hilton Head'nDinner: sikkim Past Food, Hilton necdoomccooo COLORFUL Downtown Manhattan 1 Bed, Hilton Head\nknDay 3: nCurrent City: from Hilton Head
Hip, vibrant,
SharlottelnTransporre self-driving, from Hilton Head to Iharkattee:Breakkast:: Connoisseur, Hilton Head'nAttraction Sea Fines Forest Preserve, Hilton Head. \nlunch: MR.D Deliciousness Delivered, Hilton -Ancccommoattion:
HoadYaDinner:
Output from Checker = 0, =
Decision: unsatisfiable
Feedback:
The plan is invalid because it includes transportation from Hilton Head to Charlotte Day 3, which is not detailed in the provided context information. This failure is due to the context information being Incomplete, as it lacks the necessary details for the return trip, which is required by the constraint that the trip must end in Charlotte.
Output from Search Advisor at L ==
Flightsearch (Chrrlotee, Hilton Head, 2022-03-26;
(F from Charlotte to Hilton Head on 2022-03-26] [lightsearchhHilton Head, Charlotte, 2022-03-281
OotebookWritteeFlighht from Hilton Head to Charlotte 2022-03-28)
Output from Search Agent after first interleaved search step (L = 1)
index"; 0, "Short Description": "Transportation from Charlotte to Hilton Head", "Content": "self-driving, from Charlotte to Hilton Head, duration: 3 hours 49 mina, distance: 398 km, cost: 19"
"index" 1,
"Short Description"; "Accommodation in Hilton Head", "Content";
NAMR
house_rules minimum nights maxi mum occupancy review rate number city
price room type
32

---

Published as a conference paper at ICLR 2026
williamsburg Home Away
From Home! 164.0 Entire home/apt
pets
4.0
3
3.0 Hilton Head
COZY Room @Williamsburg (10 mins to Manhattan) room
605.0
Private 2.0
No visitors
4.0 Hilton Head
"index": 2, "Short Description": "Restaurants in Rilton Head", "Content":
Name Average Cost
Cuisines Aggregate
Rating Taste Of China
City
91 Hilton Head Tea, BBQ, Mediterranean,
Tea, Seafood, Bakery,
Fast Food
K Raga's s
Desserts
2.9 Hilton Head
New Town Pastry Shop
Park Plaza
51 Tea, Cafe, Pizza, BBQ
3.2 Hilton Head
"index": 3, "Short bescription": "Attractions in Hilton Head", "Content"; Longitude
Name
Latitude
Address
Phone
City Coastal Discovery Museum 32.211485 -80. 744025 70 Boney Horn Dr, Hilton Head Island, 29926, USA (843) 689-6767
Website
http://wwwcoattaalaccceeeeer org/ Hilton Head
"index" 4, "Short Description": "Flights from Charlotte to Hilton Head on 2022-03-26",
"Content"; "Flight Number Price DepTime ArrTime ActualElapsedPime FlightDate OriginCityName DestCityNane Distance
F4055090
92 18:07
19:27
hours 20 minutes 2022-03-26
Charlotte Hilton Head
207.0
F4059890
13:01
14:22
hours 21 minutes 2022-03-26
Charlotte Hilton Head
207.0*
,
index": 5,
"Short Description": "Fligats from Hilton Head Charlotte on 2022-03-28",
"Content": "Flight Number Price DepTime ArrTime
ActualElapsedrimm FlightDate OriginCityName DestCityName
Distancs F4C56985
20:07 21:31 hours
minutes 2022-C3-28
Hilton Head Charlotte 207.0 16:04 hours 12 minutes 2022-03-28
F4059921
45 14:52
Hilton Eead Charlotte 207.0"
Output from Constraint Manager at =
33

---

1. The transpcrtation plan is not logical. The travelers self-drive Hilton Head on Day but take a flight back to Charlotte on Published as a conference paper at ICLR 2026
1. The selected accomnodation in Hilton Head must have minimum stay requirement of nights or less.
2. Meals must be chosen from the following restaurants that serve French or Italian cuisine: sikkin Fast Food, Cafe Coffee Day, Dhaba Ambarsariya, Connoisseur, MR.D Delicicusness Delivered, Mr. Brown,
Wrapster.
The travel plan must use one
two available modes transport: self-driving or one of the specified flights.
4. The trip must start in Charlotte and return to Charlotte.
5. The trip must be for group of 5 people.
The trip
take place from March 26th, 2022, March 28th,
2022.
7. The total cost of the trip must not exceed 50000""
Output from Planner at L K =
Day A:nuuurret city: from Charlotte to Hilton Hoadtarransportation: self-driving, from Charlotte to Hilton Head'kBrraaffat: -\ nAttraction: Coligny Beach Park, Hilton Head)nlanch; -\nDinner: Dhaba Ambarsariya, Hilton HeadknAccommodation COLORFUL Downtown Manhattan Bed, Hilton Head\n\nDay 2: nCurrent City: Hilton #eakkarrasportationn -\nBreakfast: Wrapster, Hilton Head'nnttraccionn Harbour Town Lighthouse, Hilton Head; Coastal Discovery Museum, Hilton Head. AnLunch: Mr. Brown, Hilton HeadVnDinner: Sikkin Fast Food, Hilton Head) nAccommodation: Hip, Vibrant, COLORFUL Downtown Manhattan Bed, Hilton Head\n\nDay 3: \nCurree City: from Hilton Head to self-driving, from Hilton Head to Cafe Coffee Day, Hilton Head\nattraction: Sea Pines Forest Freserve, Hilton Head. AnLunch: Connoisseur, Hilton Head\nDinner: -tnaccommodation:
Hip, Vibrant,
CherlotteelnDrrnspootaaat
Output from Checker at L = 1, K =
Decision: invalid
Feedback:
1. The transportation for Day 3, 'self-driving, from Hilton Head to Charlotte', is not supported by the provided context information The context only includes details for self-driving from Charlotte Hiltor Head.
Output from Planner at L = 1
Day
1: I:Cnurrent City: from Charlotte to Hilton Headkafrrasportattior: self-driving, from Charlotte Hilton Head'nBrraaffatt -\ nAttraction: Coligny Beach Park, Hilton Head'nLunch: -AnDinner: Dhaba Ambarsariya, Hilton tead\nAccomoddtiinnn Hip, Vibrant, COLOREUL Downtown Manhattan 1 Bed, Hilton Head\n\nDay 2: nCurrent City: Hilton Headhanransporttat Wrapster, Hilton HeadynAttraction. Harbour Town Li githosee,, Hi Hilton Head; Coastal Discovery Museum, Hilton Head. Anlunch: Mr. Brow,, Hilton HeadNnDinner: Sikkim Fast Food, Hilton Head' nAccommodation: Hip, Vibrant, COLORFUL Downtown Manhattan 1 Bed, Hilton Head\n\nDay 3:AnCurrent City: from Hilton Head to ThazcooteellTarrprtaatt..o Flight Number: F4059921, from Hilton Head to Charlotte, Departure rime: 14:52, Arrival Time: 16:041 nBreakfast: Cafe Coffee Day, Hilton Head\nattraction: sea Pines Forest Preserve, Hilton Head. AnLunch; Connoisseur, Hilton Head) nDinner: -VnAccomodationn:
-\nBreakfast:
Output from Checker K
Decision: invalid
Feedback:
34

---

Published as a conference paper at ICLR 2026
Day 3, which would result in their car being left behind in Hilton Head.
Output from Planner at I. 1, =
Day 1: AnCurrent City: from Charlotte to Hilton Headhafransportatiorr Flight Number: F4059890, from Charlotte to Hilton Head, Departure Time: 13:01, Arrival Time: 14:22\BBreakiast -\ nAttraction: Coligny Beach Park, Hilton Head -AnDinner: Dhaba Ambarsariya, Hilton Head/nAccommodation. COLORFUL Downtown Manhattan 1 Bed, Hilton Head\n''nDa 2: nCurrent City: Hilton Heaclarrraapootationn: -\nBreakfast: Wrapster, Hilton HeadInAttraction: Harbour Town Lighthouse, Hilton Head; Coastal Discovery Museum, Hilton Head. AnLunch: Mr. Brown, Hilton Hoad\nDinner: Sikkin Fast Food, Hilton Head) naccommodation: Hip, Vibrant, COLORFUL Downtown Manhattan 1 Bed, Hilton Hoad 3: ltCurree city: from Hilton Head to CharlottelnTranse aaaaloooctennaaappttttaioooo Flight Number: P4056985, from Hilton Head to Charlotte, Departure Time: 20:07, Arrival Time: 21:311 näreakfast: Cafe Coffee Day, Hilton HeadynAttractionn Sea Pines Forest Preserve, Hilton Head. AnLunch: Connoisseur, Hilton Head) nDinner: -Vnaccomoddation -An
Hip, vibrant,
Output from Checker at L = K, =
Decis sioision: valid
Final delivered plan
dday": 1,
"current_city": "from Charlotte Hilton Head", "transportation": "Flight Number: F4059890, from Charlotto Hilzon Head, Departure Time: 13:01, Arrival Time: 14:22", "breakfast"; "-",
"attraction": "Coligny Beach Park, Bilton Head;",
"Lunch" "-"
"dinner"; "Dhaba Ambarsariya, Hilton Head", "accommodation" "Hip, Vibrant, COLORFUL Downtown Manhattan 1 Bed, Hilton Head"
"day": 2,
"current_ ccurrent_city;; "Hilton Head", "transpertation": n_",
"brcakfast"; "Wrapster, Hilton Head", "attraction"; "Harbour Town Lighthouse, Hilton Head; Coastal Discovery Museum, Hilton Head;", "Lunch": "Mr. Brown, Hilton Head",
"dinner": "Şikkim Fast Food, Hilton Head", "accommcdationn" "Hip, vibrant, CCICRFFL Downtow Manhattan Bed, Hilton Head"
"day": 3,
"current_city": "from Hilton Head to Charlotte", "transportation", "Flight Number: F4056985, from Hilton Head to Charlotte, Departure Time: 20:07, Arrival Time: 21:31", "breakfast"; "Cafe Coffee Day, Hilton Head", "attraction"; "Sea Pines Forest Preserve, Hilton Head;", "lunch": "Connoisseur, Hilton Head",
"dinner"; "-",
"accommedation ion"; ion":;
35

---

Published as a conference paper at ICLR 2026
E.1.2
LIVE TRAVEL PLANNING WITH MULTI-TURN FEEDBACK
First Turn
Query: Could you help me arrange 7-day solo travel itinerary from Kona to California with budget of $5, 800, intending to visit 3 distinct citics in California from Soptember 7th to September 13th, 2025?
Output from Constraint Manager
1. The traveler must stay in Los Angeles from September 7th to September 9th, 2025.
2. The traveler must stay in San Francisco from September 9th to September 11th, 2025.
The traveler must stay in San Diego from september september 13th, 2025.
4. The three citics to be visited are Los Angeles, San Francisco, and San Diego.
The mode of transportation between cities in California must be f-drivig..
6. The trip must start with a flight from Kona to Los Angeles on September Vth, 2025.
The trip must end with flight from Diego to Kona september 13th, 2025.
8 The total trip duration is 7 days, from September 7th, 2025 to September 13th, 2025.
9. The total budget for the trip must not exceed 800.
10. The trip is for solo traveler.
Final delivered plan
"day": 1,
"current_city"; "from Kona to Los Angeles", "transportation": "Flight Number: HA, from Kona to Los Angeles, Departure Time: 15:19, Arrival Time: 23:51",
"breakfast"; "-",
"attracticn"; "_"
"lunch"; "_"
"dinner"; "_"
"accommcdation": "Modern Homestay 2, Los Angeles"
"day": 2,
"current city": "Los Angeles", "transpertation": n_a
"breakfast"; "Humble Bird, Los Angeles",
"attraction"; "Griffith Observatory, Los Angeles; Hollywood Walk of Fame, Los Angeles;",
"lunch": "Granville, Los Angeles",
"dinner": "Chao Krung Thai, Los Angeles", "accommcdation": "Modern Homestay Los Angeles"
"day": 3,
snttrrent_iity" "from Los Angeles to San Francisco", "transportationn" "self-drivime from Angeles to San Francisco",
"beekfast" "la Pupusa Urban Ratery, los Angeles", "attraction"; "The Getty Center, Los Angeles:", "Lunch": "_",
"dinner"; "Sweet Maple, San Francisco",
36

---

Published as a conference paper at ICLR 2026
"accommedation": "Travelodge by wyndham San Francisco Airport North, Francisco"
"day": 4,
"current_cii _itreent_cttt;.. "San Francisco",
"transportation"; "_"
"beakffast;; "Sweet Maple, san Francisco",
"attraction"; "Golden Gate Bridge, San Franclsco Wharf, San Prancisco;";
"lunch": "Bar Crudo, San Francisco",
"di nner"; "Suní Cafe, San Francisco", "accommddation" "Travelodge by Wyndham San Francisco Airport North, San Francisco"
"dy":: 5, "current_city": "from San Francisco to San Diego", "transportation": "self-driving, from San Francisco to San Diego
"breakfast"; "Flour Water, San Francisco", "attraction;; "Alcatraz Island, San Francisco;",
"Lunch": "-",
"dinner"; "Oscar's Mexican Seafood, San Diego", "accommcdttion"" "Quaint And Cozy One Hedroom Unit with Patio, San Diego"
"day": 6,
"current_ city": :ittreen_citt;::: "transportation" "-",
"San Diego",
"breakfast"; "Las Cuatro Milpas, San Dicgo",
"attracticn"; "Balboa Park, san Diego; USS Midway Museum, San Dicgo;";
"lunch": "Kitch's Seafood, San Diego",
"dinner": "Puesto, San Diego", "accommedatian": "Quaint And Cozy One Bedroon Unit With Patio, San Diego"
"day": 7,
"current_city": "from San Diego Kona", "transportation": "Flight Number: НA, from Diego to Kona, Departure Time: 11:17, Arrival Time: 14:19", "breakfast"; "Kindred, San Diego", "attraction": n-",
"lunch": "_",
"dinner"; "_"
iaccommodation":
37

---

Published as a conference paper at ICLR 2026
Second Turn
Query: Could you help arrange 7-day solo travel itinerary from Kona to California with a budget of $5, 85,800, intending to visit 3 distinct cities in California from September 7th to September 13th, 2025?
And this was the plan you generated previously. Day 1:Current City: from Kona to los eaggeeesttaasstttaaai Flight Number: HA, from Kona to los Angeles, Departure Time: 15:19,
Arrival Time: 23:51Breakfast. -Attraction: -lunch: -Dinner:
Accommodation: Modern Homestay 2, Los AngelesDay 2:Current city: Los Angelestransportatiin: -Breakfast: Humble Bird, Los AngelesAttraction: Griffith Observatory, Los Angeles; Hollywood Walk of Fame, Los Argeles.Lunch: Lunch: Granville, Los AngelesDinner: Chao Krung Thai, Los Angelesccommoation: Modern Homestay 2, Los AngelesDay 3:Current city: from Los Angeles to San FranclecoTTaasporttaiioo
self-driving, from Los Angeles to san PranciscoBreakfast: La Pupusa Urban Eatery, Los
AngelesA:::raction: The Getty Center, Los Lnncles.Lunch: Lunch: Sweet Maple, Pranccscooccoomodatio San Francisco Airport North, San FrancisceDay 4:Current city: San Pranciscoraassprtttiioo PranciscoAttractiion: Golden Gate Bridge, San Francisco; ri risherman's wharf, San Francisco. FranciscoDinner: Zuni Cafe, San connciicccccommaaiiioo Travelodge by wyndham San Francisco Airport North, San FranciscoDay 5:Current City: from San Francisco to San DiegoTransportatior: self-driving, from San Francisco to San Diego3reakfast: Flour Water, San FranciscoAttraction Alcatraz Island, San Francisco. Lunch: -Dinner: Oscar's Mexican Seafood, san DiegoAccommodation.
-Dinner: Travelodge by Wyndham
-Breakfast: Sweet Maple, San
Bar Crudo, San
Quaint And Cozy One Bedroom Unit With Patio, San DicgoDay 6:Current City: San DicgoTaansportation: Breakfast: Las Cuatro Milpas, San DiegoAttraction Balboa Park, Midway Museum,
Diego. Lunch: Mitch's Seafood, San DiegoDinner: Puesto, San DiegoAccommodati One Bedroom Unit With Patio, San DiegoDay 7:Current City: from San Diego to KonaTransportation:: Flight Number: HA, from San Diego to Kona, Departure Time: 11:17, Arrival Time: 14:19 Breakfast: Kindred, San DiegoActraction: -Lunch: -Dinner: Accommodation:
San Diego;
Quaint And Cozy
Let me alsc tell you the major issues on this plan. The restaurant in day breakfast is repeated. want try various
restaurants and attractions.
The transportation is conflicting. If I travel by air or taxi, cannet do self-driving at point of the trip. Conversely, if I'm able to use self-driving car, I will not require taxi flight.
The breakfast day is invalid in the sandbox.
The accommedation information in day is halluci nated.
Output from Constraint Manager
The transportation method must be consistent: either use self- driving for all inter-city travel or use flights/taxis, but not mix of both.
2. All selected restaurants and attractions must be unique and not repeated.
3. The restaurant. Humble Bi rd' must not be inci uded in the plan.
4. The accommedation 'Modern Homestay 2' must not be included in the plan.
38

---

booked from September 11th to Published as a conference paper at ICLR 2026
5. All flights, accommodations. restaurants, and attractions must be selected exclusively from the provided context information.
6. The trip must start in Kona on September 7th, 2025 and end in Kona on September 13th, 2025.
7. The itinerary must include visits to three distinct cities: Los Angeles, San Francisco, and San Diego.
The total budget
trip must not exceed $5, 800.
9. The trip is for a solo traveler.
10. The trip must be closed loop, starting from Kona and returning to Kona.
los Angeles must be booked from September 7th to September 9th, 2025.
Accommedation
12. Accommodation in San Francisco must be booked from September 9th to September 11th, 2025.
13. Accomeedation in September 13th, 2025.
Diego
Output from Search Advisor
Lioglessearchf (Los Angeles, San Francisco, 2025-09-09] Notebookwrite (Flights from Los Angeles to San Francisco on 2025-09-09]
Googlls5carchELight [San Francisco, San Diego, 2025-09-11]
Notebookfritte (Flights from San Francisco to San Diego 2025-09-11]
Final delivered plan
"day": 1,
"current_city"" "from Kona to Los Angeles",
"transportationn: "Flight Number: HA, from Kona to Los Angeles, Departure Time: 15:19, Arrival Time: 23:51",
"breakiast"; "-",
"attraction"; "-",
"lunch": "-",
"dinner": "_",
"accommcdation"; "Modern Hostel, Los Angeles"
"day": 2, "current_city"; "Los Angeles", "traneportation"; "-",
"breakfast"; "La Pupusa Urban Eatery, Los Angeles", "attraction": "Griffith Observatory, Los Angeles; Holl lwood Walk of Fame, Los Angeles;",
"lunch": "Granville, Los Angeles", "dinner"; "Chao Krung Thai, Los Angeles", "accomoddation" "Modern Hostel, los Angeles"
"day": 3,
"current_ctty"" "from Los Angeles to San Francisco", "transportation" "Flight Number: HA, from Los Angeles to Sar Francisco, Departure Time: 22:34, Arrival Time: 23:59", "breakfast": "Holbox, Los Angeles", "attraction": "The Getty Center, Los Angeles;", "lunch": "Niku x, los Angeles",
"dinner"; "The Brothers Sushi, Los Angeles", "accommedation" io "Travelodge by Wyndham San Francisco Airport North, Francisco
"day": 4, "current city": "San Francisco", "transportation"; "-",
39

---

Published as a conference paper at ICLR 2026
"breakfast"; "Sweet Maple, San Francisco", "attraction"; "Golden Gate Bridge, Francisco; Pisherman' Wharf, San Francisco;", "Lunch": "Bar Crudo, San Francisco",
"dinner": "Zuni Cafe, San Francisco", "accommddation": "Travelodge by Wyndham San Francisco Airport North, San Francisco"
"day": 5,
"current_city": "from San Francisco "transportation"" "Flight Number: Southwest, from San Francisco to San Diego, Departure Time: 11:00, Arrival Time: 12:35", "breakfast"; "Flour + Water, San Francisco", "attraction"; "Alcatraz Island, San Francisco;", "lunch" "_",
piego",
dinner"; "Oscar's Mexican Seafood, San Diego",
"accommedation": "Quaint And Cozy One Bedroom Unit with Patio, San Diego"
"dy"": 6,
"current_city" "San Diego",
"transportation": "-",
"breakfast"; "Las Cuatro Mi laa,, Diego" "attraction"; "Balboa Park, San Diego; USS dway Museum, San Diego;",
"Lunch": "Mitch's Seafood, San Diego", "dinner": "Puesto, San Diego", "accommodation"; "Quaint And Cozy One Bedroon Unit With Patio, San Diego"
"day": 7,
"current_ "current_city"; "from San Diego to Kona", "traansortattonns "Flight Number: HA, from San Diego to Kona, Departure Time: 11:17, Arrival Time: 14:19", "breakfast"; "Kindred, San Diego", "attraction": "-",
"Lunch" "-",
"dinner"; n_",
"accommcdation"; n_*
40

---

Published as a conference paper at ICLR 2026
E.2 DEMO
We present comparative demonstration of the user-facing interface for monolithic agent baseline (Figure 11) ATLAS (Figure 12), given the same real-world travel planning query: "Please create travel plan for me where I'll be departing
from Washington and heading Myrtle Beach for a 3-day trip from November 13th to November 15th, 2025. Can you help me keep this Journey within a budget $1, 400?". https://wwx
Demo video available at hwtp://wwwwwwuubb...b.. com hetp:uuue...o//atttt.//vva/eee GmRR.
Select Sample Query Travel Planning
Choose
WERY
create plan departing Woshington heading Myrte 3-day
Show codo
Select Method
Choose the method use the travel planning
НETHO0: monolithic (Gomini-2258
Show code
Run Method
Show codo
generated travel, plan you...
day
current.oity
from Wastington Myrte Beach
Myrtle Seach
from Myitl beach to Waslington
transportation
sul set-driing from Waahington Myrte
from Myrtl Deach Washington
breakfast
Crossarts fitto Mynte
Shonline Cafe. Myrtl Reach
Boodh-lloyy
Caprsina
Thorogghhen
Myr..
ancormociaion
Grance Ooean Myrto
Gronde Shores Oocan Myrtle
generated plan you....
night
Figure 11: Screenshot of demo running monolithic agent for real-world travel planning, Displaying the generated plan and the summary of search results by the monolithic agent (Gemini-2.5-PP)
41

---

Published as a conference paper at ICLR 2026
Q, Commands
Code
Ranall
Select Sample Query for Travel Planning
Choose ond of the quenie from the mena below to try.
<>
Messe create travel olan for where departng from Wash and head ng Myrtle Unech d-y trp from Novamber 1ith to Never
QUIRT:
this journyy within budger of $1,4077
Select Method
Choose the method use for the travel planning.
Running ATLAS and displaying generated plan
Run Method
A
Show code
Flights API looded.
itsractiions loaded.
Accosnodat loaded.
louded.
Bonglei lobissaannaatttiii loaded.
Plannenlgent genini-2. 5-pp loadeed
Craticlqent gentma 2.5 lauded.
labearchhggnt garane-2.3-- Lowdled
Criticfgunt (Aes) gemini-2.5 louded.
Ranning ATLAS
Tats may take sore time lop to 15 minutes), Go grab coffee 42 and cone back!
Bun-ing action: Parner[Pleese create travel plan for 1:11 be departirg free Kestin beadins Nyrt Brach The plan deternired to be unmet inblle by the Constraint thecker, Skip to the rest inter leaved search step.
Myrtle
Inter Leaved Step -
Banning actioo: Planner (P [Plesee create travel. plan for ne where be departing free Kash inghin haading Nyrt Brach
Here is the generated travel plan for you....
cument_ctty
from gtan Myrtle Beach
My the
Myr teach Wivhington
tronsporattinn
-oriorginggg.. from washing gratingtonn Mymte Beach
sett-rniing from Myrte Read Washingttn
breakhett
Crawe its ln Oven Bar Myrlie Beach
Riplyts Oceanhrnt Grlle Rootlop far, Myrt..
stbrat
Myrte Seach Bearchoilt and Promerads, Myrtis
Riplay's Aquart Beach, Myrtee
Beach, Myrte
Boriamin Colobosh Seatood
Domont:
dirner
Copcairs House Myrtle
Myrtle
accommadatian
Matra Durnss Nystle Beach
Marias Dhvende Dureo, My Seach
Displaying the summary of search results by ATLAS
Calarn
Seavort Pec Caltten
Seateel Anggn Pins Statiir
Figure 12: Screenshots of demo running ATLAS for real-world travel planning. Displaying the generated plan and the summary of search results by ATLAS.
42

---

Published as a conference paper at ICLR 2026
F PROMPTS
F.1 TRAVELPLANNEE
For the Search agent and the Planner agent, we basically follow the prompts as provided in Xie et al. (2024) for the search agent and the Planner agent We provide the full prompts for the agents in our framework: Constraint Manager, Checker and Search Advisor. In their prompts, the list of tools and example plan are exactly as provided in the original prompts of the TravelPlanner benchmark.
Prompt used for Constraint Manager
You are an expert logical reasening whose task is to list out constraints that the user must adhere to when creating a travel plan.
Given query AND context information, these constraints
be any relevant factors that may explicitly identifiable from them. The query may explicitly specify some constraints, but you should also consider those that can be inferred from the context information. Do NOT include constraints that cannot be explicitly formulated from query and the context information; for example, do not consider the feasibility the plan i.e., whether the schedule is practical enough for the user to pull off.
Additional nctes:
1. Use the city name exactly as provided; for instance, "Washington" refers to the one in seattle, W&, not "Hashington D.C". Do not infer different city. Only use cities directly relevant to the query, and do not include nearby cities with airports or those the general vicinity.
2. The trip must be a closed loop. Even though it is unclear from the user query whether it should return to the origin city, aLways assume that it should.
As your output, enumerate a list of constraints that the user must adhere to when creating a travel plan. Output must be in structured format with numbered constraints. Keep it succinct and only 1ist the constraints and not add any additional statements. Prioritize the constraints that are not drawn from the query, but that are additionally specified from the context information.
query: [query inserted here] context information: [context information inserted here] constraints:
Prompt used for Checker
You are an expert in logical reasoning whose task is to act as critic.
You are paired with travel planner, and will be given query and the plan generated by the travel planner.
*ZEROSHOT REACT INSTRUCTION' and 'PLANNER INSTRUCTION' respectively from here:
https: /ttts:///gtttiii thu.. com/OSU NOLO-NLL--OE Group/Traveel py
'The prompt for Checker includes sandbox-specifie instructions (e.g.. "Note that transportation duration secondary concern.."", "When it comes to accommodation, don't worry about maximum occupancy constraint." "Implicit Allowance.."" "Strict Filtering..."), This is because the sandbox data often has no feasible options when these constraints are not relaxed, and the evaluation metrics do not check for them. For fair comparison, we provide these instructions to baseline methods well. These instructions are removed for our I LivePlanner setup, where search results longer limited hy andhox-limited fcasibility.
43

---

Published as a conference paper at ICLR 2026
You given the context information, collection of travel information that were referred to when the travel planner created the plan.
You are given constraints, which are list of rules that the plan must comply with.
You alsc given previous planning attempts and your feedback on them, which will provide you with holistic insights the planning process so far.
Your goal is evaluate the travel plan created by the planner, ONLY on the following aspecta:
VERY IMPORTANT: every detail the plan must be derived from the provided information.
2. VERY IMPORTANT: for each day, any necessary applicable details transportation, restaurant, attraction, and accommodation should not missing. Note that transportation duration secondary concern: While long transportation durations (e.g., exceeding 20 hours) might occur, do not let them be the primary basis for rejecting plan or skipping essential elements like accommodation.
3. Every part of the plan must adhere to the provided constraints, whenever applicable.
4. Each day permits the assigament of no more than one transportation method and accommodation, All travelers must stay in the one accommodati inn together and split up multiple accommodat ons. when it comes to accommodation don't worry about maximum occupancy constraint.
5. Overall travel sequence and all details in the plan should align with commonsense. However, when it comes to the feasibility of the plan, focus more on the completeness all necessary plan details included7) rather than meticulously scrutinizing the exact feasibility of transportation durations, for example. Small variations in travel time should not be a major point of eriticism.
the plan (e.g., are
Make sure te only evaluate the travel plan based on the above aspects.
You must net evaluste the format the travel plan, the planner is required to follow specific format. No transportation is needed when not moving between cities. All price is for one person, and all accommodation price is per night.
When evaluating accommodation rules, please adhere the following principles:
1. Implicit Allowance: Unless rule explicitly states prohibition, assume that the activity feature is permitted.
not infer restrictions based on the absence of explicit permission.
2. Strict Filtering for Prohibitions. when a user expresses preference requi rement, strictly filter out any accommodations that explicitly state prohibition against that preference. Avoid overthinking or applying overly broad interpretations to these prohibitions. Focus solely on direct contradictions.
Planning failures may stem from the planner's limitations in utilizing existing information, or from the incompleteness of the provided context information.
If it is the planner's s fault, you should provide feedback the specific reasons why the plan invalid.
If it the fault of the provided context information, you should identify the case as unsatisfiable and provide feedback on what
44

---

Published as a conference paper at ICLR 2026
further information was needed to make the plan valid. Or if it repeats the same failure type previous planning attempts, you should also identify the case as unsatisfiable.
Output your critic results in structured JSON format with two fields in the example:
decision and (2) feedback.
(1) For decision, it must be valid, invalid, or unsatisfiable.
(2) when the decision is valid, do not provide any feedback. when it's invalid, enumerate the reasons for your decision. when the decision is unsatisfiable, it means that the plan cannot be succeasfully generated based on the provided context
information mainly due to inaufficient information. In this case, it is not you and the planner's s fault, but rather has to be zesolved by collecting more information, so you should provide feedback what further information the plan valid.
needed to make
Keep your cutput concise and don't include suggestions for the improvement, focusing on the missing information in the travel plan or the constraints that are not satisfied.
Example *****
Decision: invalid
Feedback: 1. The accommodation choice is missing for Day 1.
2. The plan includes restaurant choice that is not in the provi ded context information.
3. The minimum nights for the accorrodation 'Affordable Spacious Refurbished Room in Bushwick!, Charlotte' is 2, but it is only
booked for night on Day 1.
The plan violates the constraint that the mode of transportation must be self-driving for the entire trip, as a flight is chosen for Day 1.
5. The city sequence does not make sense.
***.. Example Ends
***** Example *****
Decision: unsatisfiable
Feedback: The plan is invalid because it does not include any transportation for Day 1, which is necessary for the trip. However, this failure was because there is no transportation information for Day 1 in the provided context information, hence further information collection is required.
..... Example Ends *....
query: [query insearted here]
context information: [context information inserted here] constraints: [outputs from Constraint Manager inserted here] previous planning attempts and your feedback: [previous planning attempts and corresponding feedback inserted here] travel plan: [current plan to be validated inserted here] critic:
Prompt used for Search Advisor
You are an expert in logical reasoning whose task is to act as critic.
You paired with assistant who will take actions collect information related to transportation, dining, attractions, accommodation for planning vacation trip. Each action by the assistant only calls one function once, each of which MUST be one of the following types:
[List of teols inserted here...
45

---

Published as a conference paper at ICLR 2026
Let me alsc give you an example of a good travel plan, to inform you of the output format from the Planner. The symbol -- indicates that information is unnecessary.
[Example plan insterted here...]
You will be given query and the actions and observations ons taker far. You are also gi given previous planning attempts made based on the observed information along with the feedback.
These planning attempts have failed and the acconpanied feedback explains why they failed.
Now your task, as critic, is to identify any gaps in the information collected so far and suggest additional actions gather the necessary information. See if any of the previous planning failures are because that was the only possible plan outcome given the limited previous information, and the planner could have done better only if the assistant had collected information.
Your output is the 1ist of actions that should be taken for further comprehensive information collection and potentially to help address the previous planning failures. Remember, the actions should be of the speci actions described above, and you should not auggest any actions that go beyond the scope of those actions or have already been taken.
IMPORTANT NOTES:
Your pricrity to ensure that all comprehensive information on transportation, dining, attractions, and accommodation are collected and recorded in Notebook so that the Planner can use them.
Prevent redundant information gathering, Do not suggest calling actions that would collect information already present in the previously gathered data. If correct actions were taken but the observed information remaina insufficient, do NOT repeatedly ask for similar actions until enough information is gathered. If you believe all relevant information has been collected,
suggest calling the Planner tool with the query. In this scenario, do not propose further actions, as previous planning failures might stem from the Planner's limitations in utilizing existing information, rather than lack Use the city name exactly as provided; for instance,
"Washington" refers to the one in Seattle, WA, not "Mashington D.C". or do not infer different city; when calling actions, only use cities directly relevant the query, and do not include nearby cities with airports or those the general vicinity.
5. when gathering information on specific topic from calling an action call, the presence of at least one relevant and satisfying piece of information is considered sufficient, meaning information collection for that topic successful, It is not necessary for the majority of observed items to satisty the query's specifications: the existence of single suitable option is enough. The precise identification of that relevant piece within the observed information are the responsibility the Planner, not the information extraction process.
Regarding accommodations, please adhere to the following principles: Implicit Allowance: Unless rule explicitly states prohibition, assume that the activity or feature permitted.
46

---

Published as a conference paper at ICLR 2026
Do not infer restrictions based on the absence of explicit permission.
2. Strict Filtering for Prohibitions: when a user expresses a preference or requirement, strictly filter out any accommodations that explicitly state prohibition against that preference. Avoid overthinking applying overly broad Interpretations to these prohibitions. Focus solcly on direct contradictions.
Remember, yeu want to efficiently gäther all necessary information. You should not suggest actions that collect information that goes beyond the scope the query or that is not relevant to the query.
Keep your cutput succinet.
Do not include any Action Number in your suggested actions: for example, if you suggest stoggeebistanceeattii/MMM Lake city, self-driving] ' just output it directly, not in the form of 'Action 1: Googlebistanceeatrii [Twin Falls, salt Lake City, self-driving) '
Falls, Salt
47

---

Published as a conference paper at ICLR 2026
F.2 LIVE TRAVEL PLANNING
For live travel planning, instead of the sandbox tools, the Google Search based tools to retrieve live information on flights, accommodations, restaurants, and attractions. For the Search agent, we the same prompt in TravelPlanner, but the list of tools is replaced with those in "Prompt listing the tools used for live travel planning". Search Advisor also uses the same prompt as TravelPlanner, but the list of tools replaced with those in "Prompt listing the tools used for live travel planning".
Prompt listing the tools used for live travel planning
(1) GoogleseearchFiighh [Origin, Destination, Datel:
Description: flight information retrieval tool that Google Search.
Parameters:
Origin: The city you' 11 be flying out from.
Destination: The city you aim to reach.
Date: The date of your travel in TYYY-M--DD fornat.
Example: BaogleSearchh1ight (New York, london, 2025-10-01] would fetic flights from New York to London on October 1, 2025.
(2) GoogLeDistanceMatria (Origin, Destination, Model: Description: Estimate the distance, time and cost between two cities. DO NOT use this tool to find the transportation inside city. Don't worry about the transportation inside a city as part of your travel planning. Parameters:
Origin: The departure city of your journey. nust be just a city name, not other names like airport name, without including state code, etc.
Destinaticn: The destination city of your journey. must be just city name, not other names like airport name, without including state code, etc.
Mode: The method of transportation. Choices include 'self-driving' and 'taxi'.
Example: sooggeeeissaaneeMtiiiii(aaaa Lyon, taxi! or (Paris,, Lyon, self-driving] would provide driving distance, time and cost between Paris and Lyon.
(3) Cogglssaarcacccmmaaattooooooooo Deseriptiont Discover accommodations your desired city using Google Search.
Parameters: searchQuery - the rephrased query that only includes necessary details about the accommodation search.
Example: accogeeaaaaa [Find accomnodations
Rome from
2025-10-01 to 2025-10-03 for 2 guests. We require accommodations in the form of private rooms. would present a 1ist of accomnodations in Rome from October 1 to October 5, 2025, for 2 guests.
(4) GooglesearchRestaurant [searchquery]:
Description: Explore dining options in a city of your choice using Google Search.
Parameter: searchQuery The rephrased query that only includes necessary details about the restaurant search.
Example: CcogleSearchRetaarrnn (Find restaurants in Tokyo. want to tzy Korean and Japanese cuisines.] would show curated list of restaurants in Tokyo.
(5) Boogglleearchhtteattiinn..o :ci
Description; Find attractions in city of your choice using Google Search.
Parameter: City The of the city where you' seeking attractions.
48

---

Published as a conference paper at ICLR 2026
Example: Gocgglessearchhttrrcct...o [London] would return attractions in London.
(6) CitySearch (State [State]
Description: Find cities in state of your choice.
Parameter: State The cities.
the state where you're seeking
Example:
CityScarch (California would return citics in california.
(7) NotebockkKiite [Short Description]
Description: Writes new data entry into the Notebook tool with short description. This tool should be used immediately after FLightSearch, AccommodttionSeare RestaurantSearch or GoogLe in Notebook can be information you need into Notebook.
AttractionSearch
Only the data stored by Planner. So you should write all the
Parameters: Short Description
A brief description or label for the stored data. You don't need to write all the information in the description. The data you've searched for will be automatically stored in the Notebook.
Example: NotebookWrite (Flights from Rome to Paris in 2022-02-01] would store the informatrion of flights from Rome to Paris in 2022-02-01 in the Notebook.
(8) Planner [Qunner[Query]
[Query]
Description: smart planning tool that crafts detailes plans based on user input and the information stored in Notebook.
Parameters:
Query: The query from
that this is exactly the Make paraphrased one.
query given from the user, not a
Example: Planner [Give me 3-day trip plan from Seattle to New York] would return detailed 3-day trip plan.
You should use as many possible steps to collect enough information to input to the Planner tool.
In the input arguments, use the city name exactly as provided; for instance, "Washington" refers the in Seattle, WA, not "Washington D.C". or not infer different city. Only cities directly relevant to the query, and ao not include nearby cities with airports or those in the general vicinity.
Each action enly calls function once. Do not add any description
the action. Output only one action at time. Do NOT include your thought be simply just calling one of the above eight actions.
the action output. Your action must
Do not use the word 'Action' and the number in your output; for Paso, Phoenix,
example, only output coogloDistanceMatriif.. self-driving), not Action 10: GooglebistanceMatiilll Paso, Phoenix, self-driving).
Prompt for live flight search
site: www. google www/ coom/traael/flights CR site:
www.expedia. cwm//oigntst....eeee
Request: [request from the search agent inserted here]
Given the search results, extract all necessary flight information and output in the requested format.
The output should be in structured format with the following columns: FlightNumber, Price, DepTime, ArrTime, Actuall@lapsedTdmm,, FlightDate, OriginCityName, DestCityName.
49

---

Published as a conference paper at ICLR 2026
Try not to miss any fields. For Welightuumber', it's okay to just use the airline code (like DL) if inevitable, without the full flight number (like DL5375). No field should be left blank or None.
Prioritize the cheapest flights. All price
one person.
When there is no available flight option at all, you must return *no information'.
Here are the examples of the desi red output. Val ue for each column should be clearly separated by a semicolon and a tab.
=== Example 1 begins ===
FlightNumbez; Price;
DepTime; FlightDate;
ArrTime;
ActualElapsedrrime:
OriginCityName;
DestCityName
F3502691;
240;
18:48;
20:51;
2 hours 3 minutes;
2022-03-02;
Buffalo;
Atlanta
F3514187;
322;
06:51;
08:40;
hours 49
minutes;
-
Buffalo;
Atlanta
F3555201;
265;
12:44;
14:33;
1 hours 49
minutes;
2022-C3-02;
Buffalo;
Atlanta
Example 1 ends
Example 2 begins
no inrorma icn Example 2 ends ===
DO NOT include anything else but only the collected information exactly structured as requested above. Formatted cutput:
Prompt for live accommodation search
site: www.expedia.co wwt.ee.cccoooeeeeeeeee OR site: www.airbub.co com OR site: www. www.booking.o com.
Request: [request from the search agent inserted here]
Given the search results, extract all necessary accommodation information and output in the requested format.
The output should be in stractured format with the following
columna: name, price, maximum_oconee hompmmmocccacc,, rating, city.
Try not to miss any fields, but inevitable, it's okay to leave the 'maximum 'maximu__occuparce occupancy' and 'rating' fields to be None. Prioritize the cheapest accommodations.
there is no available accommodation option at all, you must return 'no information
All price is for one person per night.
Here the examples of the desired output. Each field should be separated by a semicolon and a tab. = Example 1 begins ===
name; price;
maximum Deximum_occupancyy
rating: Tucson
city
Hilton Hotel;
212.0;
3.0;
Marriott Marquis;
357.0;
5.0;
Tucson
Green Oasis;
118.0;
2;
3.0;
Tucson
Heacon Grand;
58.0;
2
3.0;
Tucson
Sunny Cobble Hill;
107.
0
3;
2.0;
Tucson
Hotel Zetta; 231.0;
2;
5.0;
Tucson
Example ends
50

---

Published as a conference paper at ICLR 2026
Example begins no informa icn Example 2 ends ===
DO NOT include anything else but only the collected information exactly structured as requested above.
Formatted cutput:
Prompt for live attraction search
site: www.tripadrisox wtw.::/aa.r.....oo.ttttaaaaaaaaa
Request: Irequest from the search agent inserted here]
Given the search results, extract
necessary attraction information and output in the requested format.
The output shculd be in a structured format with the following
columns: name, address, phone, website, city, No field should be left blank None.
Please try to return at least restaurants. Prioritize the most popular attractions.
When there is available attraction option at all, you must return 'no information'.
Here are the examples of the desired output. Rach field should be separated by semicolon and tab.
Example 1 begins
Name; Address;
Phone; Website;
Cityln 1801 N Griffin St, Dallas, TX
The Dallas World Aquarium;
75202, USA;
(214) 720-2224;
https:/ wwwp:/wwwww....ooomow com/;
Dallas\n
The Sixth Fleor Museum at Dealey Plaza; (214) 747-6660;
411 Elm St, Dallas, TX https://www. jfk.org//
75202, USA;
Dallas'n Reunion Tower;
300 Reunion Blvd E, Dallas, TX 75207, USA; http://wwel /wwp//www... www.rruniontwwer.oo..t
(214) 296-9950;
Dallas An
Dallas Museum of Art;
1717 Harwood St, Dallas, tX 75201,
USA; (214) 922-1200;
bttps://was ama. org/;
Dallas
Example ends
Example 2 begins no information
Example 2 ends ===
DO NOT include anything else but only the collected information exactly structured requested above. Formatted cutput:
Prompt for live restaurant search
site: www. www.tripadvisod www.:pppaaiooor..ooeesstaaaaaaa
com/Restaurants
Request: [request from the search agent inserted here]
Given the search results, extract
necessary restaurant information and output the requested format.
The output shculd be in a structured format with the following
columns: Nane, AverageCost, Cuisines, Rating, and City. For the average cost, if there is direct price information, depending on the price descriptions or dollar signs, and the
51

---

Published as a conference paper at ICLR 2026
living cost of the city, you MUST determine the average cost specific number.
Try not to miss any fields, but if inevitable, it's okay to leave the 'Rating' field to be None.
Prioritize the most popular restaurants
highly rated restaurants. least 10 restaurants. If there is specific request for cuisines, try to return least restaurants of each cuisinc.
Please try to return
When there is available restaurant option at all, you must return 'no information.
A11 price is for one person.
Here are the examples of the desired output. Each field should be separated by semicolon and tab. Example begins AverageCost;
Name;
Cuisines; Rating;
City 4.5;
Coconuts Fish Cafe;
97.0;
Mediterranean:
Dallas
1918 Bistre Grill;
87.0;
BBQ Seafood;
4.4;
Dallas
Yanki Sizzlers;
56.0;
Cafe French;
4.1;
Dallas
Aravali Owls;
29.0;
Italian; 4.7; Dallas
Example 1 ends
example 2 begins no informat icn
Example 2 ends ===
DO NOT include anything else but only the collected information exactly structured as requested above.
Formatted cutput:
52

---

Published as a conference paper at ICLR 2026
LARGE LANGUAGE MODEL USAGE FOR WRITING
In this paper, we used LLMs, specifically Gemini and ChatGPT, strictly only as general-purpose writing tools. We provided draft text asking the models correct any grammatical errors, refine the
structure, or reduce the redundancy. All edited text was then manually verified and edited as needed. The LLMs were not used for generating any new content or references.
53


Reviews:
[{"review_id": "KGGFcsTQcv", "reviewer": "Reviewer_W8Ma", "summary": "This paper considers the travel planning problem which should follow the real-world constraints. Te authors present a multi-agent framework, ATLAS, to trackle three identified core challenges, constraint construction, constraints-aware answering, and resolving information gap. Specifically, they design a constraint management agent to identify and codify the constraints, a planner agent to propose a travel plan with the extracted constraints in a propose-validate loop, a search agent to diagnose failures and guide the further information collection. They conduct the experiments on the TravelPlanner benchmark and its multi-turn variants, to validate its effectiveness.", "questions": "1. I'm not entirely clear about how the checker component operates in practice. Is it based purely on LLM self-verification, or does it adopt an \"LLM-modulo\" style approach that incorporates additional symbolic verification tools?\n2. Could the proposed method be generalized to first-order logic, particularly how the constraint extraction and verification processes could be generalized?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The most compelling aspect of this work lies in its decomposition of the travel planning problem into three well-justified challenges, a perspective with which I strongly agree, not only in the context of travel planning but also in broader real-world scenarios where agents must fulfill user needs.  \n2. Building upon the identified challenges, the authors have thoughtfully designed distinct agents that collaborate effectively to accomplish the complex and practical goal of travel planning.  \n3. The performance of ALTAS is significant and the effectiveness is well validated based on the ablation study.", "weaknesses": "I don't have major concerns on this work, here are some minor concerns. \n\n1. It is worth noting that the experimental comparison in this paper does not include OpenAI's GPT models. Based on my own experiments with TravelPlanner, GPT-5 in sole-planning mode (i.e., planning under constraints as described in the paper) already achieves performance far exceeding the near-zero result reported for the original TravelPlanner, even approaching the performance of ALTAS in Table 2. Given that constraint extraction in TravelPlanner is relatively straightforward, the main challenge in a multi-agent system would still lie in planning under constraints. Therefore, I would be interested to see the results of ALTAS when integrated with GPT-5.  \n\n2. I agree that the insights and the framework proposed in this paper are generalizable to tasks like travel planning, which require both information gathering and strict constraint satisfaction to meet user needs. However, the validation in this work is limited to the travel planning scenario. Although the TravelPlanner benchmark has gained broad attention, its support for constraint satisfaction is confined to propositional logic, includes only a limited set of constraints, and the process of extracting constraints from its template-synthesized queries is relatively straightforward [1]. In real-world scenarios, users often express diverse needs that require first-order logic (FOL) for proper representation, thereby extending constraint extraction and validation into a combinatorial FOL space. From this perspective, if the authors intend to claim robust constraint satisfaction capability in the travel planning domain, it would be valuable to include evaluation on the ChinaTravel benchmark [2], which assesses first-order logic constraint satisfaction. \n\n[1]. Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools.    \n[2]. ChinaTravel: An Open-Ended Benchmark for Language Agents in Chinese Travel Planning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "afl7rLJQe8", "reviewer": "Reviewer_i4Up", "summary": "- The paper proposes **ATLAS**, an agentic framework for real‐world travel planning that handles several constraints.\n- The authors conduct **experiments** under multiple settings, including single-agent, multi-agent, and multi-agent with live search, showing robustness across settings.\n- Their experiments demonstrate that ATLAS effectively reduces hallucinations and improves planning reliability compared to existing baselines.", "questions": "**Q1 Regarding INTERLEAVED SEARCH** \n\n- INTERLEAVED SEARCH seems to play an important role, in what proportion of test cases was it actually triggered?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall, the paper is well written and covers a comprehensive range of experiments. Here are some breakdowns:\n\n- **Problem design / framework:** Problem settings are well estabilshed, and they are grounded in classic planning research.\n- **Writing:** Well organized and easy to follow.\n- **Experiments:** Comprehensive experiments, divided into single, multi, and multi+live settings.\n- **Results:** Effectively addresses hallucination, which is a major issue, and shows remarkable improvements compared to baselines.\n- **Analysis:** Provides a comprehensive failure analysis with fine-grained breakdowns.", "weaknesses": "### Weaknesses that may affect overall assessment\n\n**W1. Lack of analysis**\n\n> Related part: Section 4, Figure 3\n> \n- Although ATLAS demonstrates strong performance,  it’s crucial to show *why* a method works or fails — that would represent an important contribution.\n- While Figure 3 provides a weak form of analysis, ATLAS follows an agentic workflow with multiple subtasks (e.g., search, plan). It would be valuable to show the success rate of each subtask and how failures in specific stages contribute to overall failure. There could even be interesting cases where later stages compensate for earlier failures.\n- Different models may also show varying strengths across subtasks. Understanding *which model excels at which component* could guide future research into multi-agent workflows for more powerful travel-planning agents.\n\n**W2. Lack of baseline comparison**\n\n> Related part: W1, Appendix A\n> \n- Although the authors mention the paper [1] and note that their problem scope differs, I still think a comparison is needed. (Or with other sand-box based framework)\n- I understand [1] *operates in a sandbox-based setup,* but it remains a strong tool achieving top performance. **The authors could, for example, disable ATLAS’s search component or provide the same searched data to [1] and compare outputs.\n\n---\n\n### Weaknesses that likely affect but not majorly\n\n**W3. Lack of efficiency analysis**\n\n> Related section: 3.4\n> \n- The authors claim ATLAS is efficient due to information reuse. A cost analysis (e.g., API cost comparison with single-model baseline) would strengthen this claim.\n\n---\n\n### Weaknesses unlikely to affect assessment but useful suggestions\n\n**W4. Consideration of “preferences”**\n\n- Recently, several studies [2,3] have explored preference constraints.\n- If the authors show that ATLAS performs well under such conditions, the paper would be even stronger.\n---\nReference:\n    \n    [1] Large language models can solve real-world planning rigorously with formal verification tools. Hao et al, 2025.\n    \n    [2] COMPASS: A Multi-Turn Benchmark for Tool-Mediated Planning & Preference Optimization, Qin et al, 2025\n    \n    [3] Flex-TravelPlanner: A Benchmark for Flexible Planning with Language Agents, Oh et al, 2025", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MznUq7SKD3", "reviewer": "Reviewer_Qh1s", "summary": "This paper proposes ATLAS, a multi-agent framework formalized as a Constraint Satisfaction Problem, to address LLMs’ limitations in handling complex constraints for real-world travel planning. The framework comprises five agents (Search Agent, Constraint Manager, Planner, Checker, Search Advisor) targeting three challenges: constraint construction (explicit/implicit constraint extraction), constraint-aware planning (valid scheme generation), and information gap resolution (adaptive supplementary search).", "questions": "Q1: What is the relationship between the multi-agent design and the CSP formalization?\n\nQ2: Could similar improvements be attained by enhancing single-agent strategies (e.g., ReAct with verifier loops)?\n\nQ3: Why does the algorithm perform well in multi-turn settings where others fail?\n\nQ4: How would ablating specific agents impact performance?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. ATLAS offers a structured approach to constraint discovery and information search, providing valuable heuristic insights.\n\n2. Evaluations are conducted in real-world settings, incorporating live search (via Google Search instead of sandboxed tools) and reporting hallucination rates, demonstrating practical applicability.\n\n3. The method achieves state-of-the-art performance on TravelPlanner, highlighting its effectiveness.\n\n4. The algorithm is clearly described, the writing is accessible.", "weaknesses": "1.The framework, while well-engineered, largely repackages existing multi-agent and verification ideas. The plan–check–revise–search pipeline resembles prior systems like CRITIC, PMC, and LLM-Modulo Planning.\n\n2.Although the task is formalized as a CSP, the link between classical CSP algorithms and the actual implementation remains superficial.\n\n3.Evaluation is predominantly limited to TravelPlanner, raising concerns about overfitting and limited generalizability.\n\n4.The multi-agent design lacks clear justification. While multi-agent systems often boost performance in travel planning, the specific agent roles and structures here appear arbitrary. Comparisons with more baselines (e.g., LLM-Modulo, verifier-aided approaches) and evaluations across diverse models (including open-source ones) and benchmarks are needed to demonstrate generality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bG9sMxMB55", "reviewer": "Reviewer_LbP3", "summary": "This paper presents ATLAS, a multi-agent framework designed to tackle travel planning, which requires reasoning under complex, evolving, and often implicit constraints. ATLAS formalizes the task as a dynamic constraint satisfaction problem and introduces two cooperative agents, including a constraint manager for explicit and implicit constraint construction and a planner-checker pair for iterative plan generation and validation. Through such a multi-agent system design, ATLAS continuously refines plans, resolving information gaps that  single-agent systems often fail to address. Experiments on the TravelPlanner and Flex-TravelPlanner benchmarks show that ATLAS consistently achieves state-of-the-art performance, surpassing strong baselines such as ReAct, Reflexion, and PMC.", "questions": "1. In Table 10 (Appendix D.3.2), it is somewhat surprising that Gemini-2.5-Pro achieves better performance on the hard set than on the medium set. I am curious about this observation, as it appears that only ATLAS exhibits such an uncommon pattern.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is grounded in a clear and compelling motivation The authors effectively articulate why constraint awareness and multi-agent collaboration are essential for complex planning scenarios, making the research direction both timely and impactful.\n2. The experimental evaluation is extensive and rigorous. The authors conduct detailed comparisons with several strong baselines (e.g., ReAct, Reflexion, EvoAgent, and PMC) and perform ablation studies that carefully examine the contribution of each module within ATLAS, such as the constraint manager and checker. The results are analyzed with clear quantitative evidence, supported by thoughtful discussions and visualizations.\n3. The test environments go beyond the standard TravelPlanner sandbox benchmark. The introduction of Flex-TravelPlanner for multi-turn interaction and the integration of live web search in real-world scenarios substantially enhance the ecological validity of the evaluation. These settings convincingly demonstrate ATLAS’s robustness, adaptability, and practical potential for real-world deployment beyond controlled benchmark conditions", "weaknesses": "The only concern is that, after reviewing the prompts provided in the appendix, the framework appears to require a considerable amount of manual effort to design suitable prompts for different agents in each specific scenario. While this is acceptable given that the paper focuses solely on travel-planning tasks, such dependence on handcrafted prompts may limit ATLAS’s generalization and scalability to other domains or broader real-world applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)