Source-linked AI summary
AdaPlanBench: Evaluating Adaptive Planning in Large Language Model Agents under World and User Constraints
Jiayu Liu, Cheng Qian, Zhenhailong Wang, Bingxuan Li, Jiateng Liu, Qing Zong, Heng Wang, Jeonghwan Kim, Yumeng Wang, Bingxiang He, Xiusi Chen, Yi R. Fung, Heng Ji
TL;DR
Existing benchmarks largely treat user and world constraints separately, leaving adaptive planning under progressively revealed dual constraints underexplored. AdaPlanBench evaluates interactive plan revision on 307 household tasks with constraints disclosed after violations, finding that even the strongest model achieves only 67.75% accuracy and that adaptation remains difficult as constraints accumulate.
Problem
Existing benchmarks largely examine user or world constraints alone, leaving whether LLM agents can plan effectively under both progressively revealed constraint types underexplored.
Method
AdaPlanBench combines 307 household tasks with automatically constructed world and user constraints and a runtime protocol that progressively reveals violations to prompt adaptive re-planning.
Results
Even the strongest evaluated model achieves only 67.75% accuracy, with planning quality deteriorating as constraints accumulate and user constraints posing particular difficulty.
Takeaways & Limitations
Reliable adaptation to dynamically evolving dual constraints remains a major challenge for current LLM agents.
Takeaways & Limitations
AdaPlanBench is currently limited to the household domain, so phenomena from travel, office workflows, and robotics are not yet covered.
Abstract
from arXiv · showhide
Planning for real-world problems by language models often involves both world and user constraints, which may not be fully specified upfront and are progressively disclosed through interaction. However, existing benchmarks still underexplore adaptive planning under such progressively revealed dual constraints. To address this gap, we introduce AdaPlanBench, a dynamic interactive benchmark for evaluating whether Large Language Model (LLM) agents can adaptively plan and re-plan under progressively revealed world and user constraints. AdaPlanBench is built on 307 household tasks, with a scalable constraint construction pipeline that augments each task with dual constraints. At runtime, agents interact with the environment in a multi-turn protocol where hidden constraints are revealed only when the agent proposes a plan that violates them, requiring iterative plan revision under accumulating feedback. This makes planning challenging, as agents must infer and track constraints from feedback while re-planning effectively. Experiments on ten leading LLMs show that adaptive planning under dual constraints remains challenging, with the best model reaching only 67.75% accuracy. We further observe that performance degrades as more constraints accumulate, with user constraints posing a particularly large challenge and failures often stemming from weaker physical grounding and reduced effectiveness. These results establish AdaPlanBench as a testbed for dual-constrained interactive planning and highlight the challenge of reliable adaptation to dynamically revealed constraints in LLM agents.
1 Introduction
AdaPlanBench targets the underexplored problem of adaptive planning under jointly imposed user and world constraints. Its evaluation shows that this capability remains difficult for leading LLMs, especially as constraints accumulate.
- Motivation: Existing benchmarks largely address either user constraints or world constraints, leaving their joint handling underexplored.User constraints include preferences and priorities, whereas world constraints include tool availability and resource limitations.
- Benchmark: AdaPlanBench evaluates adaptive planning under world and user constraints using 307 curated household-domain instances from the MacGyver dataset.A scalable automated pipeline augments each task with environmental limitations and grounded personal preferences.
- Results: 67.75% accuracy is achieved by the strongest model among ten evaluated open-source and proprietary LLMs.Open-weight models typically remain at or below 30%.
- Results: Planning quality deteriorates as progressively disclosed constraints accumulate and as the overall constraint burden increases.Explicit constraint tracking and rubric-based feedback do not easily alleviate these challenges.
2 AdaPlanBench Construction
AdaPlanBench constructs household-task instances with automatically generated world and user constraint profiles, then evaluates agents through interactive plan revision as violated constraints are progressively disclosed. Its design combines multi-agent constraint construction with runtime feedback that makes adaptive re-planning central to successful performance.
- Benchmark overview: AdaPlanBench combines an automatic dual-constraint construction pipeline with a runtime protocol that progressively reveals violated constraints and elicits iterative re-planning.The benchmark evaluates planning under both world and user constraints in an interactive setting.
- Instance construction: Each instance maps a rewritten, filtered household query to a profile containing world and user constraint sets constructed with a multi-agent framework.Queries are retained only when they are concrete household tasks requiring multi-step planning.
- Constraint construction: Constraint construction iteratively samples plans, extracts salient tools, converts them into grounded world or user constraints, and merges them to guide subsequent sampling.World constraints represent environmental tool availability or usability, while user constraints represent preference alignment with tools or their inferred attributes.
- Constraint validation: Final profiles aggregate planner-specific constraint pools and use validation to remove vague, invalid, contradictory, or jointly exhaustive constraints.The resulting profiles are divided into low-, medium-, and high-difficulty tiers according to accumulated constraint burden.
- Runtime interaction protocol: At each turn, agents propose plans that judges assess for world-constraint satisfaction, user-constraint satisfaction, and planning quality; disclosed violations produce feedback for the next plan.Trajectories terminate when a valid plan is found, the turn budget is reached, or no new violations occur for two consecutive turns.
3 Experiment
Experiments across proprietary and open-source LLMs show that adaptive planning under progressively disclosed dual constraints remains difficult. Final accuracy is limited, constraint burden reduces performance, and proactive exploration is strongly associated with success.
- Experimental Setup: The evaluation covers proprietary GPT, DeepSeek, and Gemini models alongside open-source Qwen3 and Llama3 models.The reliability of the construction and runtime judge models was manually validated.
- Main Results: 67.75% accuracy is achieved by GPT-5, the best-performing model, while Gemini-3.1-Pro scores around 35% and most models remain below 45%.Open-weight models typically achieve around 30% or lower.
- Main Results: Over 90% VPR does not ensure final success: Gemini-3.1-Pro and Gemini-3-Flash maintain high valid-plan rates but remain below 45% accuracy.Their relatively low AWRV and AURV suggest constraint tracking and avoidance of repeated violations without corresponding end-task success.
- Constraint Burden: Performance drops steadily as the environment profile becomes more constrained, indicating sensitivity to increasing dual-constraint complexity.The trend is shown under increasing constraint burden.
- Proactive Exploration: Accuracy correlates strongly with proactive exploration, with coefficients of 0.898 for ATWC and 0.919 for ATUC.GPT-5 and GPT-5-Mini have both the highest accuracy and the highest ATWC and ATUC values.
- Model Comparisons: Conventional model strength does not reliably predict adaptive-planning performance: GPT-5-Mini matches GPT-5, and Gemini-3-Flash surpasses Gemini-3.1-Pro despite lower VPR.Qwen3-8B, Qwen3-14B, and Qwen3-32B also show similarly low accuracy.
4 Analysis
Model planning quality declines as environment complexity and progressively disclosed constraints increase, with user constraints causing especially severe degradation. Failures primarily reflect weakened task effectiveness and physical grounding, while tracking and feedback provide only limited recovery.
- Constraint burden: Accuracy and valid plan rate both decline as environments become more constrained by aggregated world and user requirements.The trend is observed across the Elow, Emid, and Ehigh profiles.
- Constraint burden: Progressively revealed constraints increasingly destabilize coherent, constraint-consistent planning during interaction, although stronger models degrade more mildly.Models struggle to incorporate newly revealed requirements into existing plans while maintaining stable quality across the trajectory.
- Mitigation: Explicit constraint tracking and rubric-based refinement yield only limited gains, with additional feedback sometimes destabilizing revised plans.Tracking brings limited accuracy improvement, while rubric feedback provides modest and unstable recovery.
- Constraint sources: User constraints cause larger performance degradation than world constraints, while the dual-constraint condition is hardest across models.The comparison uses World-Constraint Only, User-Constraint Only, and Both Constraints conditions evaluated with accuracy and VPR.
- Error analysis: Accumulated dual constraints expose weak task effectiveness and physical grounding, including failures to preserve effective plans and reason about accessibility or spatial compatibility.Effectiveness declines especially in later interaction stages, while physical grounding weaknesses can leave plans coherent-looking but physically infeasible.
5 Conclusion
AdaPlanBench is introduced as a dynamic interactive benchmark for evaluating adaptive planning and re-planning under progressively disclosed world and user constraints. It simulates open-ended household planning where new constraints emerge after plan violations, providing a realistic feedback-based setting while exposing limitations of current LLM agents.
- Benchmark and evaluation: AdaPlanBench evaluates whether LLM agents can adaptively plan and re-plan under progressively disclosed constraints from both the world and the user.The benchmark targets dual constraints that are revealed over interaction rather than fully specified upfront.
- Benchmark and evaluation: The benchmark simulates open-ended household planning in which new constraints emerge only after agents violate their proposed plans.This interaction protocol requires agents to revise plans in response to feedback.
- Findings: AdaPlanBench provides a more realistic setting for studying adaptive planning under feedback while revealing clear limitations of current LLM agents.Its realism comes from progressively emerging constraints and feedback-driven plan revision.
6 Limitations
AdaPlanBench has several scope and validity limitations: it currently covers only household tasks, relies partly on LLM-based evaluation, uses text-only interactions, and simplifies real-world constraints. These design choices improve control, scalability, clarity, and diversity, but limit coverage of deployment conditions and realistic preferences.
- Limited Domain Coverage: AdaPlanBench is currently limited to the household domain, leaving phenomena from travel, office workflows, and robotics uncovered.The household setting provides a controlled testbed for interactions between user preferences and world constraints.
- Potential Bias in LLM-based Evaluation: LLM judges may introduce model-specific preferences or systematic bias, and their scalable evaluation is not equivalent to fully manual assessment.The authors use multiple judges with aggregated rubric scores and report high consistency with human annotation to mitigate this risk.
- Text-only Evaluation Setting: The text-only setting omits visual perception, embodied execution, and direct environmental contact, limiting how well the benchmark captures real-world deployment difficulty.Removing perception errors and low-level control noise deliberately isolates adaptive planning.
- Simplified Constraint Modeling: Object-based world constraints and attribute-based user constraints simplify the fine-grained, compositional, ambiguous, and softer nature of real-world requirements.Multi-planner sampling and aggregation improve constraint diversity, but the resulting space remains a simplified approximation of real-world planning.
Ethics statement … C Experiment Details
The paper reports ethical safeguards and open licensing, situates AdaPlanBench against prior constraint-planning work, and details a multi-agent pipeline that builds progressively richer, solvable world–user constraint profiles. It also specifies model execution practices for reproducible experiments.
- Ethics statement: The household-domain benchmark was manually checked for offensive content, and the authors report no expected negative societal impact.The authors state that a subset of data was manually validated and that they are confident the benchmark poses no such risk.
- Ethics statement: The code will use the MIT license, while AdaPlanBench will be distributed under a Creative Commons license for free academic access.The authors also state that existing models and tools are used consistently with their original licenses and intended research purposes.
- C Experiment Details: Open-source models were run locally with vLLM, whereas closed-source models were accessed through official APIs, with experimental settings provided in Section C.1.These execution choices are stated as part of the paper’s reproducibility procedure.
- A Related Works: Prior evaluations mainly isolate world-side or user-side constraints, while newer methods increasingly address both in settings such as travel planning.Examples include PDDL, time and availability, workflow, and API rules for world constraints, alongside methods targeting user constraints and joint handling.
- A Related Works: Existing approaches generally assume constraints are available upfront and do not model repeated environmental interventions that force iterative plan revision.This gap motivates evaluating adaptive planning under progressively revealed constraints.
- C Experiment Details: The construction pipeline uses query rewriting and filtering, multi-agent plan proposal, constraint extraction, aggregation, and validation to create benchmark instances.It starts from MacGyver queries, removes explicit resource constraints, and retains concrete household tasks requiring non-trivial planning.
- B Formalization: Each retained household query is paired with three hierarchical profiles, Elow, Emid, and Ehigh, each containing one world-constraint set and one user-constraint set.The profiles are produced after r = 1, r = 2, and r = 3 constraint-induction rounds, respectively.
- C Experiment Details: Three iterative rounds combine parallel multi-planner sampling with feedback from accumulated constraint pools, increasing exploration breadth and later-round diversification.The procedure separately handles world and user constraints before round-level aggregation and validation.
C.1 Experiment Setup · C.2 Model Choice · C.3 Runtime Interaction Details
The experiments standardize model decoding and validate model choices, while runtime interaction progressively reveals constraint violations through prioritized feedback and evaluates plans with multidimensional rubrics. GPT-5.4 supports filtering and judging, and rubric scores assess practical plan quality beyond binary constraint satisfaction.
- C.1 Experiment Setup: Models use temperature 0.0 and maximum completion length 16,000, except GPT-5-series models, which use default temperature 1.0 and average three runs.Accuracy variation across GPT-5-series runs does not exceed 3%; open-source experiments run on four NVIDIA H100 GPUs.
- C.1 Experiment Setup: Temperature changes affect accuracy and valid plan rate by no more than 3% across models, whereas GPT-5-series models differ from others by substantially more than 3% in accuracy.The ablation compares T = 0.0 and T = 1.0.
- C.2 Model Choice: Data-construction planners use GPT-4.1, DeepSeek-V3.2, and Qwen3.6-Flash, while GPT-5.4 filters invalid constraints.The planner samplers are introduced in Section 2.1.
- C.2 Model Choice: Runtime world-constraint and user-constraint judges use GPT-5.4, while rubric evaluation uses GPT-4.1, DeepSeek-V3.2, and Qwen3.6-Flash as independent judges.These are the same three models used in data construction for rubric-based evaluation.
- C.3 Runtime Interaction Details: At each turn, judges identify violated constraints, select a revealed set, and pass it to a user simulator that rewrites the selected items as direct feedback.The revealed constraint set is determined solely by judge-identified violations.
- C.3 Runtime Interaction Details: Feedback reveals only one constraint type per turn, prioritizing all world-constraint violations over user-constraint violations when both occur.User constraints are revealed only when no world constraint is violated; previously disclosed violations can be explicitly reminded, while non-selected violations remain withheld.
- C.3 Runtime Interaction Details: Plans are checked against the full constraint profile each turn, while repeated violations are measured only over the disclosed constraint history.The feedback rule controls revelation but does not alter underlying constraint checking.
- C.3 Runtime Interaction Details: Rubric judges score feasibility, physical plausibility, ordering, effectiveness, concreteness, safety, consequence awareness, and autonomy on a 1–5 integer scale for every model and turn.Higher scores indicate better plan quality, with anchor descriptions at 1, 3, and 5 and intermediate scores at 2 and 4.
C.4 Metric Details … C.8 Confidence Intervals
The appendix defines metrics for constraint validity, rubric success, repeated violations, and triggered constraints, then details prompts, tracking and refinement analyses, and 95% confidence intervals. These procedures operationalize adaptive planning evaluation and controlled analyses of constraint memory and rubric feedback.
- C.4 Metric Details: Accuracy requires the terminal-turn plan to satisfy all world and user constraints and pass the rubric threshold.A plan passes rubric evaluation only when every aggregated dimension score reaches at least γ.
- C.4 Metric Details: Valid Plan Rate measures the proportion of instances whose trajectories terminate with a valid plan.The appendix also reports average turns, repeated world violations, repeated user violations, and triggered world and user constraints.
- C.5 Prompt Details: Runtime prompts cover agent planning, world-constraint judging, user-constraint judging, and rubric-based evaluation, with full templates supplied for reproducibility.The rubric scoring prompt is assembled using Tables 11 and 12.
- C.6 Constraint Tracking Analysis Experiment Setup: The constraint-tracking experiment prepends an external memory block containing all previously disclosed world and user constraints to the agent input.The input combines standard conversation history, current user feedback, and the up-to-date memory block while removing earlier duplicated memory blocks to control context length.
- C.7 Rubric Refinement Analysis Experiment Setup: Rubric refinement evaluates failed dimensions and rationales, generates natural-language improvement suggestions, and conditions the next plan on that refinement signal.Refinement applies only after all world and user constraints are satisfied; constraint violations instead follow the standard feedback priority rule.
- C.8 Confidence Intervals: 95% confidence intervals model accuracy as a binomial proportion over 307 evaluation samples using a two-sided Wald interval.Reported intervals are expressed as percentages after multiplying empirical accuracy and bounds by 100.
D Additional Experiment Results … E Discussion
Additional experiments broadly support the main findings across the full rubric, while sensitivity analyses clarify that stopping parameters mainly regulate inefficient interaction and rubric strictness affects absolute accuracy more than model ranking.
- D.1 Full Rubric Scores: Table 8 extends evaluation to eight planning dimensions, adding logical step ordering, concreteness, consequence awareness, and autonomy to the four dimensions analyzed in the main text.The additional results are described as broadly consistent with the main-text findings.
- D.2.1 Max Turns Threshold T: T = 20 functions primarily as a safeguard against pathological long-horizon loops rather than an active bottleneck.Only GPT-5 reached the maximum-turn limit once, while models averaged 4.7–6.2 turns.
- D.2 Discussion on Parameter Choice: Most trajectories stop through successful completion or early stopping instead of exhausting the turn budget.The maximum-turn limit was reached in only 1/307 GPT-5 trajectories.
- D.2.2 Early Stop Threshold τ: τ = 2 detects stagnation when agents fail to violate any new constraint for two consecutive turns.Repeated violations of previously disclosed constraints suggest that further interaction is unlikely to produce meaningful progress.
- D.2 Discussion on Parameter Choice: Smaller τ values can terminate unproductive trajectories earlier, whereas larger values mainly increase interaction length without substantially improving final success rates.The patience parameter controls how long unproductive interaction continues rather than directly determining whether a valid plan can be found.
- E Discussion: Stagnation is common across models, with a non-trivial fraction of trajectories ending after repeated violations fail to trigger new constraints.This empirical pattern supports using early stopping to prevent inefficient interaction.
- D.2.3 Rubrics Pass Threshold γ: Accuracy consistently decreases as γ increases, but model accuracy rankings remain largely unchanged across rubric thresholds from 3.00 to 5.00.Stricter thresholds require plans to satisfy all rubric dimensions at a higher level.
E.1 Benchmark Traits Elaboration … F.1 Constraint Checking
AdaPlanBench is designed as an interactive benchmark for adaptive planning under progressively revealed user and world constraints, emphasizing iterative re-planning, open-ended solutions, and scalable difficulty. Its construction isolates planning, uses tool-access restrictions and early stopping, and is supported by human evaluations of feedback reasonableness and constraint clarity.
- E.1 Benchmark Traits Elaboration: AdaPlanBench covers seven traits for realistic interactive planning, including iterative re-planning, user and world interaction, dual constraints, progressive disclosure, open-ended evaluation, and scalable constraints.These traits require agents to adapt to newly revealed requirements while satisfying subjective user preferences and objective environmental limitations.
- E.2 Data Filtering Rules: AdaPlanBench filters household queries to retain concrete, method-agnostic planning tasks while excluding knowledge-centric questions, external delegation shortcuts, and prescribed methods or tools.The filtering aims to preserve realistic, open-ended scenarios where iterative re-planning is meaningfully testable.
- E.3 Constraints Extraction Standard: The constraint extraction standard treats blocked tool access as the most direct and enforceable world constraint because household-task agents interact with environments through tools.The supplied passage characterizes the effective action space largely by which tools the agent can choose and use.
- E.4 Early Stop Mechanism: τ = 2 consecutive turns without eliciting a previously undisclosed constraint or terminating with a valid plan triggers early stopping and marks the trajectory unsuccessful.This mechanism identifies locally repetitive behavior that neither reaches a valid solution nor exposes additional hidden requirements.
- E.5 Significance of AdaPlanBench: AdaPlanBench isolates adaptive planning from perception, grounding, navigation, low-level control, and physical interaction, measuring whether models revise initially plausible plans when constraints become relevant.The formulation gives agents a goal and lets them discover whether the assumptions underlying their initial plans hold.
- E.5 Significance of AdaPlanBench: Constraint revelation drives re-planning when missing tools, unavailable resources, or user-specific preferences invalidate an otherwise reasonable plan.The benchmark represents these undisclosed constraints as a central challenge in household planning.
- F Human Annotation: 8 PhD-level annotators reviewed 240 trajectories, with each annotator covering 30 trajectories across 3 queries and 10 model trajectories per query.Each trajectory was annotated once by a single annotator to validate progressively disclosed constraint feedback and rubric-based evaluation.
- F.1 Constraint Checking: 4.45 and 4.66 were the average scores for feedback reasonableness (Q1) and constraint clarity (Q2), respectively, across the 240 annotated trajectories.Q2 compared user feedback against the actually violated constraints determined by the judge model.
F.2 LLM Judge Quality Check · G Case Study
The study evaluates rubric-based LLM judges by measuring alignment with human ratings and consistency among three judges. Across rubric dimensions, the judges show relatively stable behavior, with mean standard deviations below 0.30 despite mild disagreement.
- F.2 LLM Judge Quality Check: The quality check measures both agreement with human ratings and consistency among the three LLM judges.Human alignment and inter-judge consistency are evaluated as separate perspectives.
- F.2 LLM Judge Quality Check: For Q3 to Q10, annotators rate only the final plan, matching the 8 rubric dimensions used for automatic evaluation.For each trajectory and rubric, the analysis compares the human score with the mean score of three LLM judges.
- F.2 LLM Judge Quality Check: Human–judge score differences are computed as absolute differences between integer human ratings and the three-judge mean.Because human scores range from 1 to 5 while judge averages are finer-grained, small differences such as 0.33 or 0.67 can occur under close agreement.
- F.2 LLM Judge Quality Check: Figures 20 to 23 visualize absolute score-difference distributions across all 8 rubric dimensions.The supplied passage begins reporting that 6 of the 8 dimensions exclude an unspecified remainder, so no further dimension-level result is stated here.
- F.2 LLM Judge Quality Check: Inter-judge consistency is summarized by the mean population standard deviation of the three judge scores for each rubric dimension.The calculation first obtains the standard deviation across judges for each model and rubric, then averages these values over models.
- F.2 LLM Judge Quality Check: All rubric dimensions have mean judge standard deviation below 0.30.Lower values indicate higher agreement among judges.
- F.2 LLM Judge Quality Check: The results indicate relatively stable multi-judge behavior rather than severe disagreement, although the judges are not perfectly identical.The paper characterizes the remaining variation as mild disagreement and cites prior work using dispersion as a practical stability signal.
G.1 Error Case Study
Representative error cases for GPT-5 and Gemini-3.1-Pro qualitatively illustrate failures in physical grounding and effectiveness, complementing the paper’s quantitative analysis.
- Error Case Study: GPT-5 and Gemini-3.1-Pro exhibit representative failures in physical grounding and effectiveness.Figures 7–10 present two error cases for each model, covering these failure types.
G.2 Data Case Study
The case study illustrates AdaPlanBench through progressively enriched environment profiles that accumulate, merge, and validate world and user constraints. It also shows how constraint violations and rubric failures are evaluated through simulated feedback and judge prompts.
- Environment profiles: AdaPlanBench presents three progressively enriched profiles—Elow, Emid, and Ehigh—for the same tightly sealed pickle-jar task.The profiles begin with relatively light constraints and iteratively accumulate, merge, and validate newly induced constraints.
- Environment profiles: The Ehigh profile combines unavailable or nonfunctional household tools with numerous user preferences restricting hygiene, specialized gadgets, leverage, slipping, breakage, and hand safety.Examples include avoiding dishwashing gloves, single-purpose gadgets, wrench-like tools, tapping or striking, and sharp tools near the hands.
- Error analysis: The case-study appendix documents GPT-5 and Gemini-3.1-Pro error cases involving physical grounding and effectiveness.Examples cover juicing an orange, fixing damaged lamp wiring, unclogging a toilet, and smoothing wrinkles from a shirt.
- Interactive evaluation: The benchmark generates user feedback that identifies problematic plan components and requests revision when plans violate tool constraints, preferences, or rubric-level quality requirements.The feedback prompt is based on judge feedback and supports multi-turn interaction.
- Interactive evaluation: Separate strict judge prompts check whether proposed plans violate banned environment objects or user preferences.The world-constraint judge checks unavailable tools, while the user-constraint judge checks subjective preferences.