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
Figure 1: ReSHAPE scores the revision step before planning. Top left: the request’s specification excludes Plan B, which the user would accept. Top: an agent revises the specification with the user, and the planner, searching the revised space, finds Plan B. Bottom left: the kinds of interaction found in agents’ logs, which we compare under a fixed feedback budget, and the metrics that score a revision: the recall and precision of its search space against the acceptable plans, and whether a fixed planner delivers an accepted plan. Bottom right: our main findings.
Table 2
Figure 2: (a) Precision (solid) and recall (dashed) of the probing protocols’ specifications and (b) the acceptance rate of all four protocols, after each unit of feedback. Unit 0 is C0 , and Trade-off Probing spends two units per pair. In the shaded region past the fourth unit, recall keeps rising while acceptance has plateaued. Dotted lines mark Cref .
Specification
Acc.
Trade-off
Protocol
F1,w
Pw
Rw
(%)
(%)
Cref (reference)
21.5
26.5
53.8
55
100
Ask-before-Plan
5.3
14.7
9.6
22
7
Self-Directed Revision
3.5
6.9
22.9
19
3
Exception Probing
15.0
14.2
43.6
35
9
Trade-off Probing
12.3
14.6
28.6
26
32
Table 4: Interaction protocols with Gemini 3.6 Flash on 88 instances. Trade-off: runs ending with a meaningful trade-off (Appendix G.5 ). Shading as in Table 1 . Bold: best per column.
Appendix figures & tables29 assets
Supplementary material from the paper’s appendix.
Appendix
Table 5: Related settings , by what each models and what it scores.
Attribute
Imp.
Expects
Prefers
Role
Lodging rating
medium
medium
higher
ck
Attraction type
low
–
historic site
Meal cost
high
medium
lower
j
Restaurant cuisines
low
–
Italian
Cuisine count
low
low
lower
i
Restaurant rating
low
high
higher
Appendix
Table 6: Hidden profile of travel:50. Expects is the expectation of a numeric preference; Prefers is its direction or, for a categorical one, the liked value; the disliked values are markets and fast food. ck marks the deal-breaker, i the sacrificed attribute, and j the compensating one. The interaction style reads “Explains requests in some detail and appreciates specific recommendations with brief context.”
Specification
Pw
Rw
F1,w
Admitted
Accept.
Plan
C∅ (empty)
0.0
100.0
0.0
7,402,780
51,915
rejected
C0 (initial)
58.1
0.0
0.0
20
7
none
Cref (reference)
94.6
6.8
12.8
2,680
2,172
accepted
Ask-before-Plan
58.1
0.0
0.0
20
7
rejected
Self-Directed Revision
19.8
3.6
6.0
6,560
1,646
accepted
Exception Probing
32.9
45.6
38.2
47,420
19,301
accepted
Appendix
Table 7: Specifications on travel:50. Weighted precision, recall, and F1,w ( ×100 ); the number of legal plans each admits and how many of those the user accepts; and whether the plan Gemini 3.6 Flash delivers under it is accepted. Ask-before-Plan submitted C0 unchanged, so its planner row is a second run on the same specification.
Plan component
Transition day
Stationary day
Transportation
Exactly one
None
Meals
None
Exactly three
Attractions
None
Exactly one
Accommodation
One, except final day
Exactly one
Appendix
Table 8: Daily itinerary grammar defining the legal travel plans.
Type
Field
Values
Numeric
importance
low, medium, high
expectation
low, medium, high
orientation
lower, higher (if both apply)
Categorical
importance
low, medium, high
liked
one value of the attribute
disliked
another value of the attribute
Appendix
Table 9: Preference types in the hidden profile.
Reference r
Type
Desirability s
low
med.
high
Numeric
percentile among options
0.25
0.50
0.75
(reversed if lower is better)
Categorical
liked value: 1
0.50
disliked value: 0
any other value: 0.5
Appendix
Table 10: Desirability and reference. Desirability s of an option’s value, and the reference r : set by the profile’s expectation for numeric preferences, else 0.5.
State
Verdict
May name
Strong accept
accept
nothing
Soft accept
accept
one negative aspect
Borderline
accept
one negative aspect
Soft reject
reject
one positive aspect
Strong reject
reject
the deal-breaker, if violated
Appendix
Table 11: Response states of the simulated user.
Figure 3: The four steps of ReSHAPE Planter on the running example of Figure 1 ; step 2 illustrates the three ways ReSHAPE Planter can add an attribute.
Category
Source
Added
Transportation
cost
CO 2
duration
on-time rate
departure time
arrival time
Accommodation
nightly cost
bedroom count
review rating
property type
Appendix
Table 12: Travel attributes available for preferences and specifications.
Method
Model
Added attributes
Rule
GPT-5.6 Sol
CO 2
(writes the rules)
on-time rate
bedroom count
property type
cuisine count
dietary accommodation
Appendix
Table 13: Attribute generation methods supported by ReSHAPE Planter and their use in ReSHAPE Travel.
F1,w
Utility
Trade-off
#
C0
Cref
p0∗
pref
cost ↑→ attr. ↑
31
0.5
15.0
0.247
0.343
attr. ↓→ cost ↓
27
1.2
31.2
0.306
0.398
attr. ↓→ attr. ′ ↑
30
0.4
19.3
0.279
0.387
All
88
0.7
21.5
0.276
0.375
Appendix
Table 14: ReSHAPE Travel by trade-off form , each named as sacrificed → gained attribute, where attr. is a non-cost attribute. F1,w is ×100 ; utilities are means over instances. Instances offer on average 16.6 transportation options, 26.6 lodgings, 64.9 restaurants, and 40.4 attractions.
Travel
Shopping
Instances
88
87
Pw(C0)
0.37
1.76
Rw(C0)
0.03
3.14
Pw(Cref)
7.2
14.2
Rw(Cref)
51.2
51.7
F1,w(Cref)
9.3
22.6
Appendix
Table 15: Instances of ReSHAPE Travel and ReSHAPE Shopping. Specification scores are medians over instances ( ×100 ); acceptance (Acc.) is the share of instances (%).
Model
Identifier (provider)
Travel
Shopping
Claude Sonnet 4.6 ( Anthropic, 2026b )
claude-sonnet-4-6 (Bedrock)
CC, MS, OH
–
Claude Opus 4.6 ( Anthropic, 2026a )
claude-opus-4-6-v1 (Bedrock)
CC
CC
Gemini 3.6 Flash ( Google, 2026b )
gemini-3.6-flash (Vertex)
GC, MS, OH
GC, MS, OH
Gemini 3.1 Pro ( Google, 2026a )
gemini-3.1-pro-preview (Vertex)
GC, MS, OH
GC
gpt-oss-120b ( OpenAI, 2025a )
gpt-oss-120b-1:0 (Bedrock)
MS, OH
MS, OH
Kimi K3 ( Kimi Team, 2026 )
kimi-k3 (Bedrock)
MS, OH
OH
Appendix
Table 16: Models of the off-the-shelf systems and the harnesses each runs in, per domain. CC: Claude Code; GC: Gemini CLI; MS: mini-SWE-agent; OH: OpenHands.
Harness
Model
Done
Early
Limit
Crash
Rerun
Claude
Opus 4.6
88
0
0
0
45
Code
Sonnet 4.6
87
0
1
0
20
Gemini
3.6 Flash
88
0
0
0
11
CLI
3.1 Pro
88
0
0
0
10
mini-SWE-
Sonnet 4.6
88
0
0
0
18
agent
3.6 Flash
77
11
0
0
11
Appendix
Table 17: How the runs ended on ReSHAPE Travel, 88 per system. Done: the agent submitted a specification; Early: it ended the session without submitting; Limit: it reached the call or time limit; Crash: the run failed after all reruns. Rerun: instances that needed at least one rerun after an infrastructure failure. Runs that are not done are scored by their last valid specification.
Specification
Acc. (%)
Trade-off
Protocol
F1,w
Pw
Rw
Flash
Luna
(%)
Claude Sonnet 4.6
Ask-before-Plan
2.6
14.1
5.4
14
16
8
Self-Directed Revision
5.1
10.1
30.1
19
22
5
Exception Probing
13.8
17.2
40.4
39
36
27
Trade-off Probing
12.1
18.5
28.2
32
32
34
Appendix
Table 18: Interaction protocols with Claude Sonnet 4.6 and with Gemini 3.6 Flash on 88 instances. Acc.: acceptance rate under the Gemini 3.6 Flash and the GPT-6 Luna planner. Trade-off: runs ending with a meaningful trade-off (Appendix G.5 ). Bold: best protocol per column within a model.
Instance
Trade-off type
Verified
Decoy
travel:76
pay more, better attribute
7/10
1/10
travel:93
pay more, better attribute
8/10
0/10
travel:99
worse attribute, pay less
6/10
1/10
travel:43
worse attribute, pay less
7/10
5/10
travel:90
one attribute for another
8/10
1/10
travel:45
one attribute for another
6/10
3/10
Appendix
Table 19: User study choices. Participants choosing the plan outside the initial specification (Plan B), by instance and revision. The simulated user picks Plan B for every verified revision and Plan A for every decoy.
Specification revision
Planning outcome
Harness
Model
F1,w
Pw
Rw
Done (%)
Deliv. (%)
Acc. (%)
Uˉ
ΔU
Cref (reference)
21.5 †
26.5
53.8
–
94
55
0.217
+0.033 †
OpenHands
Claude Sonnet 4.6
9.5 †
23.5
22.6
100
90
47
0.210
+0.031 †
Gemini 3.1 Pro
4.4 †
16.2
5.4
100
41
14
0.196
+0.027
Gemini 3.6 Flash
8.7 †
24.5
14.7
100
81
34
0.196
+0.022 †
Kimi K3
12.2 †
19.2
31.5
97
92
36
0.218
+0.030 †
Appendix
Table 20: Full results of Table 1 , with completion and utility, on 88 instances with B=10 . Done: runs ending with the agent’s own submission. Deliv./Acc.: instances where the fixed planner delivers a plan / an acceptable plan; Uˉ : mean utility of delivered plans; ΔU : paired difference from C0 on instances where both deliver. † : the 95% bootstrap CI of the difference from C0 excludes zero. Bold: best system per column.
Within-instance AUC [95% CI]
Measure
Gemini 3.6 Flash
GPT-6 Luna
Pw
.85 [.81, .88]
.83 [.80, .86]
Rw
.71 [.66, .75]
.71 [.67, .75]
F1,w
.87 [.84, .90]
.85 [.82, .88]
F0.5,w
.88 [.85, .91]
.85 [.82, .88]
PwlogRw
.89 [.86, .91]
.85 [.82, .88]
Appendix
Table 21: How well each measure orders specifications by the planner’s acceptance. AUC: the share of same-instance pairs of specifications, one accepted and one not, that the measure orders correctly. Pairs come from the final specifications of the 14 systems and 3 baselines on 88 instances, and 95% CIs from 1,000 bootstrap resamples of instances. PwlogRw is Pw(log(Rw+ϵ)−logϵ) with ϵ=10−4 .
F1,w
Pw
Rw
Trade-off Probing finds a trade-off (28 instances)
Trade-off Probing
20.1
20.4
42.6
Exception Probing
18.2
15.1
57.3
Cref
23.7
29.3
55.3
Trade-off Probing finds none (60 instances)
Trade-off Probing
8.6
11.9
22.1
Appendix
Table 22: Protocols split by trade-off outcome : Gemini 3.6 Flash on the instances where Trade-off Probing ends with a meaningful trade-off and on the rest. Bold: best protocol per column and block.
Gemini 3.6 Flash
GPT-6 Luna
Specification
Deliv.
Acc.
Uˉ
Deliv.
Acc.
Uˉ
C∅ (empty)
98
8
0.091
98
11
0.055
C0 (initial)
66
12
0.156
75
14
0.155
Systems (mean)
71
31
0.203
67
30
0.200
Cref (reference)
94
55
0.217
89
47
0.226
Appendix
Table 23: The planning outcome with two planners on 88 instances. Deliv. and Acc. are in %.
Rw
Pw
0–10
10–30
30–60
60–100
0–5
5
46
22
28
5–15
4
39
54
67
15–30
64
48
43
66
30–100
58
81
77
92
Appendix
Table 24: Acceptance by precision and recall. Acceptance rate (%) of the planner’s delivered plans by the Pw and Rw of the specification, over all 5,368 specifications. Cells hold between 35 and 2,920 specifications.