Constraint Tree Exploration for Learning from Language Feedback

Shaoang Li; Daniel R. Jiang; Jian Li

cs.AIOct 6, 2026

Constraint Tree Exploration for Learning from Language Feedback

Authors: Shaoang Li, Daniel R. Jiang, Jian Li

Organizations: Stony Brook University · Meta Platforms

Abstract

Natural-language feedback in interactive learning often explains why an action failed by pointing to violated requirements. Misinterpreting this feedback can lead an agent to rule out valid solutions. We study this setting by modeling user intent as latent constraints over an action space and formulating learning from language feedback as pure exploration over feasible regions. We introduce TRACE, an algorithm that organizes candidate constraints in a tree and tests each proposed refinement by generating actions that satisfy it. TRACE commits to the refinement only if the resulting feedback does not contradict it over repeated tests. We distinguish two ways of using the same feedback: (i) falsification, which detects contradictions to the constraint set currently being tested, and (ii) identification, which may additionally name a violated constraint. We prove high-probability coverage bounds with dependence on the candidate class size $H$ for TRACE-Falsification. With reliable identification, TRACE-Identification can replace this dependence by $K/p_{\mathrm{ext}}$ , where $K$ is the number of latent constraints and $p_{\mathrm{ext}}$ lower-bounds the probability of extracting a missing true constraint from informative feedback. We evaluate TRACE across six language-feedback tasks. On RecMovie, TRACE-Identification achieves 73% and 86% final-output success under caps of 20 and 60 evaluated outputs, compared with at most 42% and 48% for the evaluated prompting baselines given the same feedback and output caps. Controlled identity-corruption experiments further show greater robustness than direct accumulation when the falsification detector remains reliable.

Figures & tables

Figure 1: Constraint-tree exploration in TRACE . At a committed node

v

with constraint set

C_{v}

, a candidate constraint

c_{\mathrm{new}}

proposes a child

u

with

C_{u}=C_{v}\cup\{c_{\mathrm{new}}\}

. The child is tested by sampling actions satisfying

C_{u}

: feedback contradicting

C_{u}

rejects the child, while survival for a fixed number

m_{\mathrm{exp}}

of tests leads to commitment. Extracted identities guide proposals; falsification tests determine commitment.

	RecMovie			20Q			EDA
Method	Natural	Falsif.	Identif.	Natural	Falsif.	Identif.	Natural	Falsif.	Identif.
Random	$\phantom{1}5\%$	–	–	$41\%$	–	–	$74\%$	–	–
DirectLLM	$17\%$	$27\%$	$40\%$	$12\%$	$43\%$	$\mathbf{100\%}$	$43\%$	$84\%$	$\mathbf{100\%}$
Reflexion	$26\%$	$35\%$	$42\%$	$11\%$	$29\%$	$\mathbf{100\%}$	$55\%$	$69\%$	$\mathbf{100\%}$
Self-Refine	$21\%$	$26\%$	$32\%$	$73\%$	$19\%$	$\mathbf{100\%}$	$78\%$	$40\%$	$\mathbf{100\%}$
TRACE	–	$\mathbf{51\%}$	$\mathbf{90\%}$	–	$\mathbf{84\%}$	$\mathbf{100\%}$	–	$\mathbf{87\%}$	$99\%$

Table 1: Main comparison under three oracle-access regimes. Random does not consume feedback. Wilson

95\%

intervals in Tables 7 and 10 ; Mastermind /Haiku/Tanka in Appendix C.2 .

Figure 2: RecMovie under equal output budgets (

100

seeds; final-output success with Wilson

95\%

intervals). (a) Common caps of

B=20

and

B=60

environment-evaluated outputs. Hatched bars are the Table 1 baseline configurations, which were run only with

T=20

; solid baseline bars are the W8/NoCycle variants run with

60

outputs. (b) TRACE-I success versus mean feedback rounds for test windows

m=m_{\mathrm{exp}}\in\{1,3,5\}

; dashed lines mark the strongest baseline at each cap.

$n_{\mathrm{colors}}$	$\|\mathcal{H}\|$	Falsification		Identification
		env.succ.	attempts	env.succ.	attempts
$3$	$9$	$\mathbf{100\%}$	$\phantom{1}9.08$	$\mathbf{100\%}$	$\phantom{1}3.91$
$6$	$18$	$\mathbf{100\%}$	$18.75$	$\mathbf{100\%}$	$\phantom{1}4.84$
$10$	$30$	$\phantom{1}98\%$	$29.35$	$\mathbf{100\%}$	$\phantom{1}6.77$
$15$	$45$	$\phantom{1}88\%$	$45.38$	$\mathbf{100\%}$	$10.54$
$20$	$60$	$\phantom{1}74\%$	$50.82$	$\phantom{1}99\%$	$18.08$

Table 2:

H

-sweep on Mastermind (

K=3

m_{\mathrm{exp}}=15

N_{\max}=80

). Wilson

95\%

intervals in Table 8 .

Table 5

LLM	Identification	Final Pass
Qwen3-4B	$84\%$ [ $72$ , $92$ ]	$16\%$ [ $\phantom{0}8$ , $29$ ]
DeepSeek-V4-Flash	$\mathbf{86\%}$ [ $74$ , $93$ ]	$\mathbf{90\%}$ [ $79$ , $96$ ]

Table 5: TRACE-I on TravelPlanner ,

n{=}50

. Identification : committed

C_{v}\supseteq C^{*}

. Final Pass : plan passes every env check.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Mastermind	Haiku	Tanka
Random	$\phantom{1}4\%$	$\phantom{1}7\%$	$\phantom{1}0\%$
DirectLLM	$15\%$	$20\%$	$\phantom{1}4\%$
Reflexion ( Shinn et al., 2023 )	$\phantom{1}9\%$	$\phantom{1}2\%$	$\phantom{1}1\%$
Self-Refine ( Madaan et al., 2023 )	$29\%$	$14\%$	$\phantom{1}0\%$
TRACE-F	$54\%$	$54\%$	$14\%$
TRACE-I	$\mathbf{99\%}$	$\mathbf{100\%}$	$\mathbf{100\%}$

Appendix

Table 6: Main-comparison env.success on the three task instances moved out of Table 1 for headline focus. Entries are env.success within each method’s interaction budget; higher is better.

Method	Rec.	20Q	EDA	Mmind	Haiku	Tanka
Random	$[2,11]$	$[32,51]$	$[65,82]$	$[2,10]$	$[3,14]$	$[0,4]$
DirectLLM	$[11,26]$	$[7,20]$	$[34,53]$	$[9,23]$	$[13,29]$	$[2,10]$
Reflexion	$[18,35]$	$[6,19]$	$[45,64]$	$[5,16]$	$[1,7]$	$[0,5]$
Self-Refine	$[14,30]$	$[64,81]$	$[69,85]$	$[21,39]$	$[9,22]$	$[0,4]$
TRACE-F	$[41,61]$	$[76,90]$	$[79,92]$	$[44,63]$	$[44,63]$	$[9,22]$
TRACE-I	$\mathbf{[83,94]}$	$\mathbf{[96,100]}$	$\mathbf{[95,100]}$	$\mathbf{[95,100]}$	$\mathbf{[96,100]}$	$\mathbf{[96,100]}$

Appendix

Table 7: Wilson

95\%

confidence intervals for natural-feedback baselines and TRACE rows. The first three columns correspond to the Natural columns (for baselines) and the Falsif. / Identif. columns (for TRACE ) of Table 1 ; the other three columns correspond to the columns of Table 6 . Entries are intervals for env.success percentages.

$n_{\mathrm{colors}}$	$\|\mathcal{H}\|$	TRACE-F CI	TRACE-I CI
$3$	$9$	$[96,100]$	$[96,100]$
$6$	$18$	$[96,100]$	$[96,100]$
$10$	$30$	$[93,99]$	$[96,100]$
$15$	$45$	$[80,93]$	$[96,100]$
$20$	$60$	$[65,82]$	$[95,100]$

Appendix

Table 8: Wilson

95\%

confidence intervals for the Mastermind fixed-

K

H

-sweep in Table 2 . Entries are intervals for env.success percentages.

Configuration	RecMovie	20Q	EDA Things
TRACE-I	$\mathbf{[83,94]}$	$\mathbf{[96,100]}$	$[95,100]$
Direct-Commit (best variant)	$[16,32]$	$\mathbf{[96,100]}$	$\mathbf{[96,100]}$

Appendix

Table 9: Wilson

95\%

confidence intervals for the same-decoder structured comparison in Table 4 . Entries are intervals for env.success percentages.

Group A: binary oracle
Method	Rec.	20Q	EDA
DirectLLM	$[19,36]$	$[34,53]$	$[76,90]$
Reflexion	$[26,45]$	$[21,39]$	$[59,77]$
Self-Refine	$[18,35]$	$[13,28]$	$[31,50]$
TRACE-F	$\mathbf{[41,61]}$	$\mathbf{[76,90]}$	$\mathbf{[79,92]}$
Group B: identity oracle

Appendix

Table 10: Wilson

95\%

confidence intervals for the binary and identity oracle baselines in the Falsif. and Identif. columns of Table 1 . Entries are intervals for env.success percentages.

Method	final env.	$U_{\mathrm{final}}$	soft regret
TRACE-F	$51\%$	$0.641$	$0.359$
TRACE-I	$\mathbf{90\%}$	$\mathbf{0.831}$	$\mathbf{0.169}$
Direct-AND	$15\%$	$0.496$	$0.504$
Direct-OR	$23\%$	$0.528$	$0.472$
Direct-RANKED	$22\%$	$0.527$	$0.473$
Random	$\phantom{1}5\%$	$0.328$	$0.672$

Appendix

Table 11: RecMovie final-output soft-score / soft-regret over

100

seeds.

U_{\mathrm{final}}

is mean partial-credit utility and

1-U_{\mathrm{final}}

is soft regret. The final env. column matches the headline RecMovie numbers in the main tables.

Proposer	any-success
TRACE-F (uniform)	57%
Incremental-LM (atomic per-feedback)	74%
TRACE-I (decoded)	95%

Appendix

Table 12: Proposer variants inside TRACE on RecMovie with the same rule-based detector; entries are interaction-budget any-success.

Detector	Overall	Final Output
Rule-based detector	57%	51%
LLM, zero-shot	21%	12%
LLM, chain-of-thought	21%	1 8%

Appendix

Table 13: Detector variants inside TRACE-F on RecMovie. Overall : any-success. Final Output : final-output env.success (matches Table 1 ).

Configuration	env.success
TRACE-I	90%
Direct-AND (strict)	15%
Direct-OR (per-dim disjunction)	23%
Direct-RANKED (top- $k$ match score)	22%

Appendix

Table 14: Same decoder, with versus without the TRACE test-before-commit scaffold, on RecMovie. Entries are final-output env.success over

100

seeds; for direct-commit baselines, final-output success coincides with any-success since they return on first hit.

Omission rate $p$	any-success
$0\%$	95%
$10\%$	95%
$20\%$	95%
$30\%$	94%
$50\%$	93%
$70\%$	87%

Appendix

Table 15: Interaction-budget any-success of TRACE-I on RecMovie under i.i.d. feedback omission,

100

seeds per cell. Performance is flat through

20\%

omission and degrades gradually afterwards.

$p_{\mathrm{false}}$	Method	any-succ.	$\mathrm{superset}(C^{*})$
$0.0$	TRACE-I	$\mathbf{95\%}$	$59\%$
$0.0$	Direct-AND	$15\%$	$94\%$
$0.0$	Direct-OR	$23\%$	$94\%$
$0.0$	Direct-RANKED	$22\%$	$94\%$
$0.1$	TRACE-I	$\mathbf{90\%}$	$54\%$
$0.1$	Direct-AND	$12\%$	$86\%$

Appendix

Table 16: False-identity-only RecMovie sweep over

100

seeds. Each extracted predicate is independently replaced by a wrong same-dimension predicate with probability

p_{\mathrm{false}}

. Success is interaction-budget any-success, unlike the final-output rates in Table 4 .

Method	$B=20$	$B=60$
TRACE-I ( $m_{\mathrm{exp}}=5$ )	$\mathbf{73\%}$ [ $64$ , $81$ ]	$\mathbf{86\%}$ [ $78$ , $91$ ]
DirectLLM (Table 1 config.)	$40\%$ [ $31$ , $50$ ]	n/a
Reflexion (Table 1 config.)	$42\%$ [ $33$ , $52$ ]	n/a
Self-Refine (Table 1 config.)	$32\%$ [ $24$ , $42$ ]	n/a
DirectLLM-W8	$38\%$ [ $29$ , $48$ ]	$48\%$ [ $38$ , $58$ ]
Reflexion-NoCycle	$35\%$ [ $26$ , $45$ ]	$37\%$ [ $28$ , $47$ ]

Appendix

Table 17: Final-output success on RecMovie under common output caps (

100

seeds; Wilson

95\%

intervals). The Table 1 configurations were run only with

T=20

$m_{\mathrm{exp}}$	$B$	Success	Mean rounds	P90 rounds
$1$	$20$	$65\%$ [ $55$ , $74$ ]	$4.43$	$5$
$3$	$20$	$78\%$ [ $69$ , $85$ ]	$13.42$	$19$
$3$	$60$	$77\%$ [ $68$ , $84$ ]	$14.26$	$22$
$5$	$20$	$73\%$ [ $64$ , $81$ ]	$18.61$	$19$
$5$	$60$	$86\%$ [ $78$ , $91$ ]	$22.08$	$27$

Appendix

Table 18: TRACE-I test-window sweep on RecMovie under common output caps (final-output success with Wilson

95\%

intervals; feedback rounds per episode).

Method	Evals	Gen. LLM	Aux. LLM	LLM tokens	Wall (s)
TRACE-I ( $m_{\mathrm{exp}}=5$ )	$22.1$	$0$	$0$	$0$	$0.4$
TRACE-I ( $m_{\mathrm{exp}}=15$ , default)	$60.6$	$0$	$0$	$0$	$0.9$
DirectLLM-W8	$36.3$	$36.3$	$0$	$21{,}275$	$14.4$
Reflexion-NoCycle	$39.9$	$39.9$	$2.0$	$25{,}845$	$14.2$
Self-Refine-W8	$38.4$	$38.4$	$38.0$	$62{,}133$	$42.4$
Best-of- $N$ ( $N=60$ )	$60.0$	$60.0$	$0$	$13{,}479$	$16.7$

Appendix

Table 19: Resource use per seed on RecMovie, averaged over each method’s complete

100

-seed logs (baselines:

60

-output runs). Evals : environment-evaluated outputs. Gen. and Aux. : LLM calls for candidate generation and for reflection or critique.

Root	$B=20$	$B=60$	Rounds ( $B=20$ )	Rounds ( $B=60$ )
$C_{\mathrm{init}}=\emptyset$	$73\%$ [ $64$ , $81$ ]	$86\%$ [ $78$ , $91$ ]	$18.61$	$22.08$
$\|C_{\mathrm{init}}\|\leq 2$ , oracle-trusted	$\mathbf{90\%}$ [ $83$ , $94$ ]	$\mathbf{91\%}$ [ $84$ , $95$ ]	$10.09$	$10.77$

Appendix

Table 20: TRACE-I (

m_{\mathrm{exp}}=5

) on RecMovie with an oracle-trusted root (final-output success with Wilson

95\%

intervals; mean feedback rounds per episode).

	20Q		EDA Things
Configuration	env.succ.	superset $(C^{*})$	env.succ.	superset $(C^{*})$
TRACE-F (uniform)	84%	82%	87%	84%
TRACE-I (decoded)	100%	100%	99%	99%

Appendix

Table 21: Coverage diagnostic versus env.success on 20Q and EDA . On sparse EDA , catalog grounding can decouple env.success from coverage; the theorem-aligned diagnostic is

\mathrm{superset}(C^{*})

K	TRACE-F succ.	Binary attempts	TRACE-I succ.	Identity attempts
2	$\mathbf{73\%}$	$10.09$	$99\%$	$5.14$
4	$35\%$	$13.84$	$\mathbf{100\%}$	$5.56$
6	$\phantom{1}4\%$	$14.95$	$\mathbf{100\%}$	$7.29$
8	$\phantom{1}1\%$	$15.00$	$\mathbf{100\%}$	$9.11$
10	$\phantom{1}0\%$	$15.00$	$\mathbf{100\%}$	$10.98$

Appendix

Table 22: Fixed-budget

K

-sweep on Mastermind with

n_{\mathrm{colors}}=6

fixed, so

|\mathcal{H}|=6K

	Haiku ( $K=3$ )		Tanka ( $K=5$ )
Method	env.succ.	attempts	env.succ.	attempts
TRACE-F	$54\%$ [ $44$ , $63$ ]	$12.57$	$14\%$ [ $8$ , $22$ ]	$14.77$
TRACE-I	$\mathbf{100\%}$ [ $96$ , $100$ ]	$3.80$	$\mathbf{100\%}$ [ $96$ , $100$ ]	$5.81$

Appendix

Table 23: TRACE on LLF-Bench Poem with Haiku and Tanka forms. We use

100

seeds per cell and

m_{\mathrm{exp}}=N_{\max}=15

. Brackets are Wilson

95\%

confidence intervals. TRACE-I exploits per-line target syllable counts revealed in the feedback; TRACE-F must search over

|\mathcal{H}|=6K

predicates.

Explore similar work

ExTra: Exploratory Trajectory Optimization for Language Model Reinforcement Learning
Jun 23, 2026Wenyang Hu, Junxiang Jia, Zhen Shu +3Verifiable Rewards Trajectory-Level Credit
1National University of Singapore · 2SAP
Efficiently Aligning Language Models with Online Natural Language Feedback
May 5, 2026Christine Ye, Joe BentonLarge Language Model Alignment Reinforcement Learning From Human Feedback
Stanford University · Anthropic Fellows Program for Safety Research · Anthropic
What Drives Interactive Improvement from Feedback?
Jun 29, 2026Bartłomiej Cupiał, Jan Łojek, Mikołaj Garstecki +3Feedback Reinforcement Learning From Human Feedback
University of Warsaw · AKCES NCBR · Princeton University +2

Jun 23, 2026, cs.LGJ/K move · Enter open · S save

ExTra: Exploratory Trajectory Optimization for Language Model Reinforcement Learning

Wenyang Hu, Junxiang Jia, Zhen Shu, Daniel Dahlmeier+2

1National University of Singapore · 2SAP

Verifiable Rewards Trajectory-Level Credit Robust Trajectory

Open paper AskPDF arXiv

Reinforcement Learning with Verifiable Rewards (RLVR) for language-model reasoning can fail at both extremes of task difficulty: easy prompts often produce all-correct, low-diversity rollout groups with little gradient signal, while hard prompts can produce all-incorrect groups with no positive reward. We introduce ExTra (Exploratory Trajectory Optimization), a GRPO-compatible framework that extracts exploration signals from the model's own rollouts. ExTra combines two mechanisms: (i) a novelty reward that adds embedding-based diversity bonuses after GRPO normalization, rewarding diverse correct solutions; and (ii) entropy-guided prefix regeneration, which scores partial trajectories using entropy signals and continues exploration from promising intermediate steps. Across six mathematical reasoning benchmarks, ExTra improves Qwen3-1.7B over GRPO by about +5 points on pass@1 and +7 points on pass@16, showing that trajectory-level exploration signals can improve both single-sample accuracy and inference-time coverage.

Abstract

Explore similar work

ExTra: Exploratory Trajectory Optimization for Language Model Reinforcement Learning

Efficiently Aligning Language Models with Online Natural Language Feedback

What Drives Interactive Improvement from Feedback?