Summary (Overview)

• Novel Benchmark: AdaPlanBench is a dynamic interactive benchmark designed to evaluate LLM agents’ ability to adaptively plan and re-plan under progressively revealed dual constraints—world constraints (tool availability, environmental limits) and user constraints (preferences, priorities).
• Scalable Construction: Built on 307 household tasks from the MacGyver dataset, the benchmark uses a multi-agent pipeline to automatically generate dual-constraint profiles at three difficulty tiers (low, mid, high), with constraints hidden until the agent proposes a violating plan.
• Evaluating Leading LLMs: Ten models (proprietary: GPT-5, Gemini-3, DeepSeek-v4; open-weight: Qwen3, Llama-3.3) are tested in a multi-turn interaction protocol where agents iteratively revise plans after receiving feedback on violated constraints.
• Key Findings: The best model (GPT-5) reaches only 67.75% accuracy; open-weight models stay at or below 30%. Performance degrades as constraints accumulate, with user constraints causing disproportionate difficulty compared to world constraints.
• Failure Analysis: Failures stem from degraded task effectiveness and weak physical grounding under accumulated dual constraints, and are only partially mitigated by explicit constraint tracking or rubric-based feedback.

Introduction and Theoretical Foundation

Large Language Model (LLM) agents must interact with both users (inferring goals and preferences) and the external world (gathering information, taking actions). This dual interaction requires planning—agents must anticipate future outcomes and dynamically adapt as interaction unfolds. Real-world planning is constrained along two dimensions:

• World constraints: environmental limitations, tool availability, resource restrictions.
• User constraints: personal preferences, priorities, prohibitions.

Existing benchmarks typically handle only one side (e.g., CostBench for world constraints, UserBench for user constraints). Two key challenges remain underexplored:

1. Progressive constraint disclosure: constraints are often implicit, revealed only when violated.
2. Large action and solution spaces: open-ended tasks with vast possible solutions make evaluation difficult.

Central research question: Can LLM agents plan effectively under both user and world constraints that are progressively disclosed in an interactive, open-ended planning setting?

The paper introduces AdaPlanBench to fill this gap. It is grounded in household tasks where both constraint types naturally arise.

Methodology

Data Construction

Each benchmark instance is a pair $(q, \mathcal{E})$, where $q$ is a rewritten, method-agnostic household query and $\mathcal{E} = (B_w, B_u)$ is a dual-constraint profile (world constraint set $B_w$, user constraint set $B_u$). Construction uses a multi-agent framework with specialized models: $\{M_{rw}, M_{flt}, M_{plan}, M_{ext}, M_{merge}, M_{chk}\}$.

Query Rewriting and Filtering

• Raw MacGyver queries are rewritten to remove explicit resource constraints while preserving the goal.
• A binary filter retains only concrete, multi-step household tasks.

Constraint Profile Construction (iterative, at most $R$ rounds)

Step 1: Plan Sampling – Sample diverse candidate plans using $J$ planners:

$$\pi^{(j)}_r = M^{(j)}_{plan}(q, B^{(j)}_{w,r-1}, B^{(j)}_{u,r-1})$$

where $B^{(j)}_{w,r-1}$ and $B^{(j)}_{u,r-1}$ are accumulated constraint pools from previous rounds.

Step 2: Constraint Extraction – Extract tools used in each plan:

$$T^{(j)}_r = M_{ext}(q, \pi^{(j)}_r)$$

Convert these into:

• World constraints $\mathcal{C}^{(j)}_{w,r}$: restrict availability or use of tools (e.g., no iron at home).
• User constraints $\mathcal{C}^{(j)}_{u,r}$: infer attributes of tool usage that matter to the user (e.g., dislike using high-heat tools).

Step 3: Constraint Merging – Merge and canonicalize new constraints with prior pools:

$$B^{(j)}_{w,r} = M_{merge}(B^{(j)}_{w,r-1} \cup \mathcal{C}^{(j)}_{w,r}), \quad B^{(j)}_{u,r} = M_{merge}(B^{(j)}_{u,r-1} \cup \mathcal{C}^{(j)}_{u,r})$$

Final Profile Formation

After $R$ rounds, aggregate planner-specific constraints and validate:

$$B_w = M_{chk}\left(\bigcup_{j=1}^J B^{(j)}_{w,R}, q\right), \quad B_u = M_{chk}\left(\bigcup_{j=1}^J B^{(j)}_{u,R}, q\right), \quad \mathcal{E} = (B_w, B_u)$$

$M_{chk}$ removes vague or contradictory constraints. Three difficulty tiers are created:

• $\mathcal{E}_{low}$, $\mathcal{E}_{mid}$, $\mathcal{E}_{high}$ with increasing average number of constraints.

Runtime Interaction Protocol

At turn $t$, the agent proposes plan $p_t$. LLM judges check:

• World-constraint satisfaction → violated world constraints $V^w_t \subseteq B_w$
• User-constraint satisfaction → violated user constraints $V^u_t \subseteq B_u$
• Rubric-based planning quality (four dimensions: Tool-Use Feasibility, Physical Plausibility, Effectiveness, Safety; scale 1–5)

Violated constraints are passed to a user simulator $M_{user}$:

$$f_t = M_{user}(V^w_t, V^u_t)$$

The agent then revises its plan to produce $p_{t+1}$.

Termination conditions:

• Valid plan found: $V^w_t = V^u_t = \emptyset$
• Maximum turn budget $T$ reached
• Early stopping: no new constraints violated for two consecutive turns

Rubric threshold: $\gamma = 4$; all four dimensions must pass on average across three judges.

Metrics

• Acc. (%): percentage of queries where final plan satisfies all constraints and passes rubric.
• VPR (%): percentage of queries terminating with a constraint-satisfying plan (not early/max stop).
• Avg Turns: average interaction turns per instance.
• AWRV / AURV: average number of repeated violations of disclosed world/user constraints per query.
• ATWC / ATUC: query-level ratio of triggered world/user constraints to interaction turns.

Empirical Validation / Results

Main Results (under $\mathcal{E}_{mid}$)

Key observations:

• Even GPT-5 reaches only 67.75% accuracy; open-weight models are ≤30%.
• High VPR does not guarantee high accuracy (e.g., Gemini-3.1-Pro: 91.21% VPR but only 34.53% Acc.).
• Stronger final performance is correlated with higher ATWC/ATUC (proactive exploration).
• Model scale does not reliably predict adaptive planning ability (e.g., Qwen3-8B and Qwen3-32B perform similarly).

Sensitivity to Constraint Burden

• Across difficulty tiers: Accuracy and VPR decline steadily from $\mathcal{E}_{low}$ to $\mathcal{E}_{high}$ (Figure 2). Models are highly sensitive to increasing constraint complexity.
• Within trajectories: Rubric scores on all four dimensions decline as turns progress and constraints accumulate (Figure 3). The degradation is milder for stronger models but consistent across all.

Intervention: Explicit Constraint Tracking

Adding all previously disclosed constraints to the model input at every turn yields:

• Marginal accuracy improvement (<3% for most models).
• More noticeable VPR gain (5–15%).
• Conclusion: Constraint tracking helps validity but not final task success; the core difficulty lies in constructing effective plans under accumulated constraints.

Intervention: Rubric-Based Refinement

Providing feedback on failed rubric dimensions and allowing 1–6 additional refinement turns:

• Accuracy improves modestly (~10%).
• VPR drops sharply (40% for open-source, 20% for proprietary models).
• Models exhibit recency bias, prioritizing local rubric fixes over global constraint consistency.

Ablation: Constraint Source Difficulty

Comparing three conditions: World-Only, User-Only, Both:

User constraints cause greater degradation than world constraints, and the dual setting is the hardest.

Rubric Dimension Analysis (under $\mathcal{E}_{mid}$)

Effectiveness and Physical Plausibility are consistently the weakest dimensions, indicating degraded task effectiveness and weak physical grounding under accumulated constraints.

Theoretical and Practical Implications

• Adaptive planning under dual constraints remains a major challenge for current LLMs. The benchmark reveals a clear gap between initial plan generation and robust plan revision under evolving constraints.
• User constraints are harder than world constraints: they impose broader restrictions on the feasible action space and cause more planning instability. Future models need better handling of user preferences.
• Explicit constraint tracking and rubric feedback are insufficient: they improve local validity but do not ensure global plan consistency. Models need stronger mechanisms for maintaining constraint satisfaction while adapting to new information.
• Recency bias in adaptation: when given new feedback, models tend to prioritize repairing the latest weakness rather than preserving all prior constraints. This suggests a need for more holistic plan revision strategies.
• Implications for real-world deployment: agents operating in dynamic environments (e.g., household robots, personal assistants) must handle progressively revealed constraints from both the world and the user. Current models are far from reliable in such settings.

Conclusion

AdaPlanBench introduces a dynamic interactive benchmark that evaluates LLM agents’ ability to adaptively plan under progressively disclosed world and user constraints. Through a scalable construction pipeline and a multi-turn interaction protocol, the benchmark reveals clear limitations of current models:

• The best-performing model (GPT-5) achieves only 67.75% accuracy.
• Performance degrades as constraints accumulate, especially under user constraints.
• Failures are characterized by reduced task effectiveness and weak physical grounding.
• Partial mitigations (explicit tracking, rubric feedback) offer limited improvement.

Future directions: extending the framework to additional domains (travel, office, robotics), combining with embodied or multimodal environments, and developing models that can dynamically plan and adapt under real-world dual constraints.

Limitations acknowledged: limited domain coverage (household only), potential bias in LLM-based evaluation, text-only interaction setting, and simplified constraint modeling (object-based world constraints, attribute-based user constraints).