cs.AINov 12, 2026

How Should Planning Agents ReSHAPE Their Search Space?

Authors: Yilin Zhang, Xinran Zhao, Tong Chen, Ziming Yuan, Tongshuang Wu

Organizations: Carnegie Mellon University · University of Washington

Abstract

Planning agents and benchmarks treat a user's initial specification as fixed. Yet the requests users write exclude plans they would gladly take, since they rarely discover the possible trade-offs they would accept until seeing the options. Agents already revise requests through interaction, but whether this helps planning is unknown. We formalize this step as the ReSHAPE task, which judges a revision by whether its search space matches the acceptable plans and a planner finds one there. Using ReSHAPE Planter, which builds instances from planning benchmarks with a human-validated simulated user, we analyze 5,800 agent-revised specifications in travel and shopping. We find that reshaping matters: one correct trade-off makes the same planner reach an acceptable plan up to 4.6x as often, and search space quality predicts what the planner finds. Current agents, however, admit at most 32% of the acceptable plans, where that trade-off alone admits over 52%, because they ask about preferences instead of showing plans; in travel, showing plans raises F1 by 9.7 points over asking, with two model families. Planning agents should thus treat a request as a hypothesis to test against the user's reactions to concrete plans to recognize user trade-offs.

Figures & tables

Appendix figures & tables29 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Trip+: Benchmarking Agents in Personalized Interactive Travel Planning

    Jun 19, 2026Junle Chen, Wei Chen, Yehong Xu +6LLM Agent EvaluationAI Agent Benchmarks

  2. From Questions to Decisions: Benchmarking How LLM Agents Acquire Decision-Relevant Information from Human Beings

    Nov 9, 2026Yuhan Tang, Ke Fan, Xinkai Zou +9LLM Agent EvaluationLLM Agent Planning