acceptodds
Under review as a conference paper at ICLR 2027

Constraint Tree Exploration for Learning from Language Feedback

Abstract

Natural language feedback in interactive learning often explains *why* an action failed by pointing to violated requirements. We study this constraint-level regime 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 (Test-and-Refine Algorithm for Constraint Exploration), a test-before-commit algorithm that organizes candidate constraints in a tree, treats extracted identities as proposals rather than facts, and uses multi-round falsification tests before committing to a refinement. We distinguish two oracle-access regimes induced by the same feedback: (i) *falsification*, which only refutes the constraint set currently being tested, and (ii) *identification*, which may additionally name a violated atomic constraint. Under refutation and separation assumptions, we prove high-probability coverage upper bounds with candidate-class dependence for TRACE-Falsification. With sound extraction and a discovery-progress condition, TRACE-Identification replaces this dependence by , where is the number of latent constraints and lower-bounds the probability of extracting a missing true constraint from informative feedback. Experiments across six language-feedback tasks demonstrate the benefits of identification-aware constraint exploration. 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. Controlled identity-corruption experiments further show greater robustness than direct accumulation when the falsification detector remains reliable.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Learning from Language Feedback, Interactive Learning, Constraint Learning, Pure Exploration, Sample Complexity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Ko7sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to discover and satisfy users’ latent constraints through language feedback. The authors formulate the problem as feasible-region exploration over a finite candidate constraint class and propose TRACE. The method proposes constraints sequentially and tests each through multiple rounds of feedback before accepting it. TRACE-F proposes candidates uniformly, while TRACE-I prioritizes constraints extracted from feedback. The paper provides complexity upper bounds. Experiments demonstrate the benefits of structured constraint handling and robustness to extraction errors when the detector is reliable.

Critical strengths
  1. The paper is easy to read. The problem formulation, algorithm, and theoretical assumptions are clearly presented. The appendix provides detailed descriptions.

  2. The constraint exploration formulation is interesting. This perspective is valuable and provides a useful starting point for further research.

  3. The experiments include substantial controls. The authors compare methods under shared feedback interfaces and equal output budgets. Component ablations further clarify the method’s behavior.

Critical weaknesses
  1. I do not view the method as tree exploration, and the theoretical contribution is limited. TRACE maintains a single accepted constraint set, tests candidates sequentially. It does not retain multiple branches for further expansion. Although the search history can be represented as a tree, the actual procedure tests and accumulates constraints in some order. I do not see what the tree representation adds over sequential testing with a constraint set. The theoretical results are also relatively trivial.

  2. The method requires substantial task-specific design, and comparisons with general-purpose baselines do not establish its algorithmic advantage. TRACE relies on a predefined candidate constraint set, a parser, and a generator. The main experiments use rule-based parsing of feedback templates. In contrast, Reflexion and Self-Refine do not require these task-specific annotations. The authors should include strong baselines that also exploit structured information, beyond general-purpose prompting methods. I do not find the current method applicable to unseen tasks (w/o templated feedback).

Questions for authors
  1. What does the tree representation add? Would the algorithm’s decisions and theoretical guarantees remain unchanged if it maintained only the current constraint set, and next constraint candidate?

  2. How much additional design is needed for unseen tasks? More specifically, how is the finite hypothesis space constructed? Is the system better suited to domains such as recommendation (w/ label) than to the general natural language interactions illustrated in the introduction?

  3. Could the authors report success rates as a function of the number of feedback samples? Under ideal extraction and reliable testing, I expect success rates to approach 100% as the budget increases. The more informative comparison would then be the number of samples needed to reach the same success rate.

4 comments

Thank you for the clear review and the precise questions. Each question led to a new experiment, summarized below.


Weakness 1 and Question 1: Tree representation and theoretical contribution

Q1, whether the decisions and guarantees change: they do not. A node of the constraint tree is a constraint set with its feasible region, so an algorithm that maintains the current constraint set, the next candidate, and the pool of extracted identities for TRACE-I, together with any rejection records used by the proposer, is the same algorithm. With the same proposal, testing, and rejection policies, this representation change preserves the algorithm's decisions and its guarantees under the original assumptions. We verified this directly: a set-based implementation gives identical results to the original on every seed in all 14 configurations we ran (7 task settings, uniform and identity proposers, 100 seeds each; Appendix C.10). The guarantees are proved along the committed path and use only the committed set and the candidate under test.

Q1, what the tree adds. The tree is the space that is searched: constraint sets ordered by refinement, each with its nested feasible region. TRACE explores it by irrevocable descent along a single path. Sequential testing with a constraint set is an accurate description of the state that TRACE keeps; the tree describes the space in which these tests take place, and the analysis is stated on it. First, each test is a test of a node. Actions are sampled from the region of $C_v\cup\lbrace c\rbrace $, and the gap and the falsification condition of Section 4 are properties of that region, so the same constraint can be acceptable at one node and refuted at another. Second, as you note, TRACE retains a single branch. It can open several children at a committed node and discards the refuted ones, and it keeps only one because a committed node contains an optimal action with high probability (Section 4), so no alternative has to be kept for later expansion. Tree search with numeric values (for example MCTS and LATS) retains branches because a value estimate only ranks them, whereas a refutation removes one. Third, the bounds count tested children against a space with about HKH^K nodes at depth KK: O~(H)\widetilde{\mathcal{O}}(H) under blind proposal, and O~(K/pext)\widetilde{\mathcal{O}}(K/p_{\mathrm{ext}}) when feedback names which child to open.

Theory. The analysis answers the question posed in the introduction: how much does feedback that names a constraint save over feedback that can only refute one? With refutation alone, the learner must find the KK true constraints by proposing blindly from a class of size HH, and coverage costs on the order of HH tests (Theorem 2). When feedback also names constraints, the cost falls to the order of K/pextK/p_{\mathrm{ext}} (Theorem 3). Section 5.3 tests this prediction on Mastermind with K=3K=3: blind proposal tests about 9, 19, 29, 45, and 51 candidates for H=9H=9, 18, 30, 45, and 60, while proposal from named constraints tests 4 to 18. The analysis also gives the length of the test window (Lemma 1) and the condition under which a commitment never has to be withdrawn.

Weakness 2 and Question 2: Task-specific design, structured baselines, and unseen tasks

Strong structured baselines. We added stronger structured baselines that use the same feedback extractor, catalog, and generator as TRACE-I, but accumulate extracted constraints without multi-round falsification tests. They combine extractions using the AND, OR, and RANKED rules of the paper, or a majority Vote across feedback messages. The published RecMovie direct-commit baseline had an implementation error (General Response, item 2); corrected, it reaches 96% on clean feedback (published: 23%). These baselines are strong. With reliable extraction they match or beat TRACE-I (96% vs. 90%, in about 3 rounds instead of about 60), and under random per-round corruption up to a rate of 0.3 the count-based Vote is the most robust method, because repeated feedback averages random errors out. Testing before commitment pays off when extraction errors are systematic, which repetition cannot average out, and the detector is reliable: with a Qwen3-4B extractor and the rule-based detector, TRACE-I reaches 60% while OR and Vote accumulation stay at or below 23% at the same budget. The revised Section 5.4 reports both the settings in which simpler accumulation performs better and this learned-extractor setting in which testing before commitment improves performance.

LLM modules and rewritten feedback. To test reliance on surface templates within RecMovie, we replaced both rule-based modules with Qwen3-4B, for extraction and for violation detection, and rewrote every feedback sentence as free-form text, five times independently (Appendix C.14). With Qwen3-4B as both modules, TRACE-I's final output succeeds on 87% of seeds on average over the five rewrites. These results demonstrate operation without template matching within the existing RecMovie schema.

Q2: design for a new task. A new task needs three components: the hypothesis space H\mathcal{H}, i.e., the attribute-value predicates over which constraints are expressed; a proposer and a detector, rule-based or LLM; and a generator that samples actions satisfying a constraint set. In our tasks, H\mathcal{H} comes from the action space: catalog attributes in RecMovie (36 predicates over 4 attributes), the five attribute dimensions of 20Q (17 predicates) and of EDA Things, position-color pairs in Mastermind (K⋅ncolorsK\cdot n_{\mathrm{colors}} predicates), line-syllable pairs in Haiku and Tanka (6K6K), and user-stated constraint types in TravelPlanner. With LLM modules, the remaining task-specific inputs are H\mathcal{H} and the generator. TRACE applies whenever the requirements can be expressed over a finite class of candidate constraints. The three examples in the introduction (recommendation, travel planning, and poem generation) are tasks we evaluate. Preferences with no attribute vocabulary are future work.


Question 3: Success as a function of feedback samples

Yes; the revision reports this (Appendix C.12). On clean RecMovie feedback, the table below reports cumulative any-success: the number of seeds, out of 100, with at least one accepted output among the first tt environment-evaluated outputs. This measures how quickly a method encounters a satisfying output, whereas final-output success evaluates the single output returned by the method.

Methodt=2t=2510152060
TRACE-I, m=3m=341877798080
TRACE-I, m=5m=541124778788
DirectLLM (Qwen3-4B)182733383848

TRACE-I reaches 80 seeds after 16 to 17 outputs, while the prompting baseline stays below 50 within 60 outputs. The level that TRACE-I reaches depends on the test window: at budget 226 it is 65, 80, 88, 93, and 95 for m=1,3,5,8,15m=1,3,5,8,15, and for two of the 100 seeds no title in the catalog satisfies the user.


We hope the new structured baselines, the template-free experiments, and the success-versus-budget results address your concerns.

Reviewer_Ko7sOpenReview ↗

Reply

Thanks for your detailed response, especially regarding Q3. I believe including this in the paper would be helpful.

As for the tree structure, as you have verified, it serves as a visualization of the search space. However, I would advise against describing it as "tree exploration," as this could easily lead to misunderstandings.

I guess the theoretical section somewhat weak, given that an O(H)O(H) complexity can be achieved simply by attempting each option one-by-one. Furthermore, if a successful node can be identified with probability pp, the expected number of samples is naturally O(K/p)O(K/p). While the paper contains extensive derivations, I feel it lacks more substantial conclusions. In particular, the assumption that HH is finite is too hard. In my view, thus poses significant challenges for deployment in real-world tasks (the examples provided in your introduction are just benchmarks). The primary contribution of your paper lies in improving sample efficiency (on these benchmarks).

I tend to maintain my score of 2. Perhaps in future work, you could build upon this framework to address more solid questions. Thanks again.

Thank you for reading our response and for the constructive follow-up. We reply briefly to each point.

Q3. Thank you. It is in the revised PDF: Appendix C.12 has the full table and the level reached with each test window.

The term "tree exploration". Thank you for this advice; we see how the phrase could suggest that several branches are kept. By "exploration" we mean what TRACE does at each node: it opens candidate children and tests each one on fresh feedback before committing to it. To prevent the other reading, the revision states that TRACE follows a single path in the tree and never returns to a node it has left (Sections 2.2 and 3).

Theory. Our aim in the analysis was to make precise when the two rates hold for language feedback; the rates themselves are indeed simple. Trying the options one by one costs order HH when each attempt returns a reliable verdict. With language feedback, an attempt is a window of stochastic messages about sampled outputs, its outcome depends on the constraints already committed, and a commitment is never revisited. The analysis gives the length of the window (Lemma 1) and the conditions under which the simple count is valid: a detector without false alarms, ε\varepsilon-separation, and, for the K/pextK/p_{\mathrm{ext}} rate, the absence of zero-gap distractors. Without the last condition the cost returns to order HH (Section 4.1). What we take from the two theorems is their comparison: feedback that only refutes costs order HH, and feedback that names constraints removes HH from the bound.

Finite H\mathcal{H} and real tasks. How much the finite class restricts depends on the feedback. Its size matters only under blind proposal: the bound of Theorem 3 does not contain HH, so the class can be large when feedback names constraints. Many practical systems already have such a class: online stores, booking sites, and recommendation services describe their items with a fixed set of attributes such as price range, date, cuisine, or genre. The user's wording stays free; the extractor maps it onto these attributes. Requirements with no attribute vocabulary are outside the scope of this paper.

Thank you again for the discussion. We would be glad to clarify anything further.

Reviewer_zUHSOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper formulates learning from language feedback as exploration over a finite class of candidate constraints. TRACE maintains a committed constraint set and tests one proposed refinement at a time by sampling actions satisfying the enlarged set. A proposal is rejected if feedback contradicts the tested constraints and is committed after surviving a fixed number of tests. TRACE-F proposes constraints uniformly, whereas TRACE-I prioritizes identities extracted from feedback. The paper derives coverage bounds under assumptions on constrained generation, detector reliability, separation, and identity-discovery progress. Experiments include recommendation, entity deduction, Mastermind, constrained poem generation, and a feedback-enabled TravelPlanner adaptation. The main controlled implementations use task-specific rule-based feedback decoding and constrained generators; LLM-based components are used in separate ablations and the planning extension. The method is an external exploration controller rather than a model-parameter training procedure.

Critical strengths

Separating a constraint proposal from its commitment is a clear and useful design principle. The same-decoder direct-commit comparisons and corrupted-identity experiments directly examine the value of testing before accepting feedback-derived constraints.

The distinction between falsification access and identification access gives a precise way to state what information feedback supplies. The conditional coverage analysis and the implementation details make the assumed interfaces explicit, which helps interpret the scope of the method.

Critical weaknesses

The main method appears largely independent of the language model's capabilities. Where an LLM is used, its role is primarily to generate an answer under the selected constraints. The benefit therefore seems to come mainly from a structure that simplifies the problem, rather than from improving the model's own ability to solve it. The paper should clarify this source of improvement. In particular, how many candidate answers remain after rule-based filtering, and by what percentage has the candidate space been reduced from its initial size? Without this information, it is difficult to tell how much of the gain comes simply from narrowing the choices available to the generator.

The algorithmic necessity of the tree representation is unclear. Algorithm 1 maintains one committed constraint set, tentatively adds a candidate, and either accepts it or discards the tentative addition. After commitment, it provides no operation to remove an accepted constraint, revisit an ancestor, or resume an alternative earlier branch. Rejecting an uncommitted candidate is not backtracking from an accepted node. The same process appears implementable with a current constraint set C, an extracted-candidate pool W, and rejection records for the current C, using exactly the same proposal and multi-round testing rules. The existing direct-commit baselines remove the testing step, so they do not distinguish a tree representation from an equivalent set-based implementation. If the tree is mainly a representation of proposal history or an analysis device, that should be stated explicitly; otherwise, the authors should identify the concrete operation or benefit that requires it. Together with the task-specific structure of the main experiments, this leaves me unconvinced of the claimed framework's methodological significance.

Questions for authors

Please report the number of candidate answers before and after rule-based filtering, together with the percentage reduction relative to the initial candidate set, for tasks where these candidates can be counted. This would help clarify how much of the improvement comes from narrowing the candidate space and simplifying the problem before answer generation.

Please add an ablation that replaces the tree with a simpler data structure, such as a set of accepted constraints, a candidate pool, and rejection records. Keep the detector, proposer, generator, multi-round test-before-commit rule, and interaction budget unchanged. Compare this set-based implementation with TRACE to show whether the tree structure itself provides any additional benefit. The existing Direct-Commit baselines remove the testing step and therefore do not answer this question.

5 comments

Thank you for the precise and constructive review. We ran the ablation you proposed, report the counts you asked for, and explain what the tree provides; the rejection records you mention also improve the uniform proposer. We also correct an error that affects one of the strengths you listed.


Weakness 1 and Question 1: Source of improvement and candidate-space reduction

TRACE improves task execution through explicit constraint discovery and constrained generation; it does not update the model’s parameters. We have clarified this source of improvement and quantified the resulting reduction in candidate space. The table reports the initial candidate count and the count remaining under TRACE-I’s final committed set across 100 seeds. These counts describe the achieved narrowing, while the structured-baseline comparisons separately examine the contribution of testing before commitment.

Taskcandidates beforeafter (median)after (mean)removed (median)
RecMovie678417.7999.4%
20Q43211.0099.8%
EDA Things10035.4097.0%
Mastermind (K=3K=3, 6 colors)21613.1599.5%

The constraints are unknown at the start: the reduction above is what TRACE learns from feedback. TRACE works with rule-based or LLM modules. With Qwen3-4B as the extractor, 63% of the values it extracts are ones the user did not ask for; using them directly gives at most 23%, and testing them before commitment gives 60%.

Weakness 2 and Question 2: Necessity of the tree representation

Your description of Algorithm 1 is accurate: TRACE keeps one committed constraint set, tests one candidate at a time, and never withdraws a commitment. We see the constraint tree as the search space of the problem: a node is a constraint set with its feasible region, and TRACE keeps only the current node. The procedure you describe, with a current set CC, a pool WW, and the same proposal and testing rules, is therefore the same algorithm, and the revision states this explicitly (Section 3). We ran the ablation you proposed to confirm it. The set-based implementation keeps the committed set CC, the pool WW of identities extracted from feedback (TRACE-I only), and the same proposer, detector, generator, multi-round test, and budget. It gives identical results to the original implementation on every seed in all 14 configurations: RecMovie, 20Q, EDA Things, Mastermind with 6 and 20 colors, Haiku, and Tanka, each with the uniform and the identity proposer, 100 seeds each (Appendix C.10). Because the analysis depends on the maintained constraint state, proposal policy, and testing rule, the guarantees carry over to this set-based implementation under the original assumptions.

What the tree provides. On the concrete benefit of the tree formulation, we would point to three things.

(i) What is tested. TRACE tests each constraint together with everything already committed: it samples actions from the region of the child $C_v\cup\lbrace c\rbrace $ and checks the feedback against the whole set. The gap, the falsification probability, and the separation condition of Section 4 are defined for nodes for this reason. The accumulation baselines differ here: they accept extracted values, directly or after a vote, without testing them.

(ii) Why TRACE does not backtrack. Under the conditions of Section 4, a refuted child contains no optimal action, and neither does any refinement of it, while every committed node retains one with high probability. For this reason TRACE needs no operation that removes a constraint or revisits an ancestor: testing before commitment is what makes this irrevocable descent safe. Tree search driven by numeric value estimates (for example HOO, MCTS, and LATS) keeps statistics on many branches and returns to them; with feedback that can refute a region, one path suffices.

(iii) What the bounds count. The tree has about HKH^K nodes at depth KK. TRACE-F tests O~(H)\widetilde{\mathcal{O}}(H) children and TRACE-I tests O~(K/pext)\widetilde{\mathcal{O}}(K/p_{\mathrm{ext}}): refutation prunes children, and extracted identities select which child to open.

The contribution is the proposal, validation, and commitment rule and its conditional coverage analysis; neither requires storing a tree.

On the task-specific structure of the main experiments: with LLM modules and feedback rewritten as free-form text, TRACE-I reaches 87% on RecMovie (General Response, item 3).

Rejection records. Adding the rejection records you mention improves TRACE-F on six of the seven task settings, for example from 74% to 98% on Mastermind with 20 colors (Appendix C.10). These records are the per-node memory of refuted children.


Correction affecting a strength you listed. You listed the same-decoder direct-commit comparisons and the corrupted-identity experiments as strengths. While re-auditing our baselines for this response, we found an implementation error in the RecMovie Direct-Commit baseline: its catalog filter read the type, year, and age attributes under the wrong keys, so only genre constraints were applied. We apologize for this error. With the fix, direct commit reaches 96% on clean feedback (published: 23%), above TRACE-I's 90%. In the corrupted-identity table, the comparison at pfalse=0.5p_{\mathrm{false}}=0.5 changes from 60% vs. 8% to 60% vs. 41%, and a count-based accumulation rule that we added is more robust than TRACE-I at moderate corruption rates (pfalse=0.1p_{\mathrm{false}}=0.1 to 0.30.3).

The corrected comparisons show where testing before commitment matters: with a Qwen3-4B extractor, TRACE-I reaches 60% while accumulation reaches at most 23% at the same budget. The revised Section 5.4 presents this benefit together with the clean-feedback and independent-corruption settings in which simpler accumulation performs better.


We hope the ablation, the counts, and the corrected comparisons address your concerns.

AuthorsOpenReview ↗

Follow-up on our response and revised experiments

Dear Reviewer zUHS,

Thank you again for your detailed suggestions. We wanted to follow up on our responses. The revised paper includes the requested set-based implementation comparison, which produces identical results under the same proposal and testing rules (Appendix C.10, Table 25), and the before-and-after candidate counts (Appendix C.11, Table 26). Section 5.4 also reports the corrected and strengthened accumulation baselines, including settings where simpler accumulation performs better.

We would appreciate your feedback on whether these results clarify the source of improvement and the role of the tree representation, and would be happy to address any remaining concerns.

Best,

Authors of Paper #4738

Reviewer_91ACOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes TRACE, which extracts candidate constraints from language feedback and tests them before commitment. The central idea is sensible, but the positioning and comparisons leave its added value unclear.

Critical strengths

The paper addresses the problem of discovering and satisfying unknown user constraints from natural language feedback. It extends the literature on interactive constraint satisfaction into the popular setting of interaction-guided search in language agents.

Critical weaknesses
  1. The introduction should establish earlier that TRACE operates during test-time (and external to the model) and explain where feedback extraction, constraint testing, and constrained generation occur. More broadly, it should situate explicit constraint trees among alternative approaches, including verifier-guided search, look-ahead, reasoning models, and training-based approaches such as RLVR as .

  2. The presented prompting baselines do not establish whether a separate constraint tree offers benefits beyond a strong reasoning model or verifier-guided search under matched feedback and compute budgets. A useful complementary experiment would fine-tune a model on constraint-feedback trajectories, or use verifiable constraint rewards, to test whether constraint filtering can be learned internally.

  3. The bounds formalize the advantage of informative constraint identities under strong reliability assumptions, but provide limited guidance on practical choices such as test-window length, detector errors, or when an explicit tree is preferable to other search mechanisms. The mathematical analysis consequently feels disconnected and rather decorative from the main practical question.

  4. If the intended contribution is mainly machine learning, it's not clear why "text" is the only modality. Given the convenience of using MMLM, constraint satisfaction testing might be much more interesting on images, videos, etc. This way we can have myriad constriants to test.

Questions for authors

See weaknesses above ^.

4 comments

Thank you for the review and the concrete suggestions. We revised the positioning, ran the comparisons you suggested, and added practical guidance on the test window.


Weakness 1: Test-time positioning and alternative approaches

We agree. TRACE is a test-time controller that operates outside the model without updating its parameters. For each candidate test, the proposer selects a constraint: TRACE-I prioritizes identities extracted from previous feedback, whereas TRACE-F proposes uniformly. The generator produces actions satisfying the committed set together with the candidate under test; and the detector checks subsequent feedback for contradictions with the tested set. A candidate surviving the mm test rounds is committed. At termination, TRACE returns an action sampled from the committed region, and the constraint set remains an explicit, inspectable intermediate state. The revised abstract and introduction state this.

The revised related-work section positions TRACE against the alternatives you list. Verifier-guided methods use evaluations of completed outputs or partial solutions to select and extend candidate solutions. TRACE uses feedback contradictions to decide whether a proposed constraint should restrict subsequent generation. Look-ahead and tree search expand several branches, whereas TRACE commits one constraint at a time and needs no model of the user. Reasoning models can serve as TRACE's extractor and detector (Appendix C.4.3). RLVR updates model parameters with verifiable rewards, whereas TRACE instead updates an explicit constraint state and requires neither training nor reward labels.


Weakness 2: Strong reasoning models, verifier-guided search, and learned filtering

TRACE specifies how language feedback is used: what a feedback message proposes, and when a proposal may be acted on permanently. Whatever reads the feedback is a component of it, and that component can be a set of rules, a small model, or a strong reasoning model. The experiments you suggest change this component, and we ran them on RecMovie. A strong reasoning model reads the feedback reliably: DeepSeek-V4-Flash reaches 95% when the feedback history is placed in its context, and a Qwen3-4B fine-tuned on feedback trajectories, as you proposed, reaches 93% on preferences it has seen in training. When the reading is this reliable, feedback can be used as it arrives, and testing costs rounds without adding accuracy. A weaker reader changes the picture. Qwen3-4B without fine-tuning misreads much of the feedback, so using its extractions directly gives 23%, while testing each extraction before committing to it gives 60%. And with rule-based modules in place of a model, TRACE-I makes no model calls and reaches 90%.

The framework is therefore useful wherever an agent must decide how far to trust what it has read, and most of all when the reader is a small or local model. Verifier-guided selection is in the submission as Best-of-NN with an oracle verifier (Section 5.2); it reaches 21%, since its candidates are generated without the feedback.

Weakness 3: Practical guidance from the theory

The analysis already sets the test window and the number of candidates to test, and the revision adds guidance for an imperfect detector.

Test-window length and detector errors. Lemma 1 sets the smallest useful window: m≥log⁡(1/δ′)/(cfalεβ)m \ge \log(1/\delta')/(c_{\mathrm{fal}}\varepsilon^\beta) rounds refute a spurious candidate with probability at least 1−δ′1-\delta'. Our analysis assumed no false alarms on viable sets. If the detector raises a false alarm with probability α\alpha per round, a true constraint survives the window with probability (1−α)m≈e−αm(1-\alpha)^m \approx e^{-\alpha m}, so committing it takes about m(1−α)−mm(1-\alpha)^{-m} rounds in expectation when it is re-proposed after each rejection. As a rule of thumb, the window should be the smallest mm that meets Lemma 1, and testing stays efficient only while mm is below about 1/α1/\alpha: longer windows reject spurious candidates more reliably but also reject viable ones more often. A new grid on RecMovie (false alarms injected at rate α\alpha, no missed detections, successes out of 100) is consistent with this estimate:

window mmbudgetα=0\alpha=00.050.050.10.10.20.20.30.3
5608687908255
8608888854214
156078441532
1522690906361

Success drops sharply once mαm\alpha exceeds about 1, and earlier under a tighter budget.

When explicit structure is preferable. The corrected baseline study answers this directly. When extraction is reliable, accumulating extracted constraints is enough (96% on clean RecMovie feedback, versus 90% for TRACE-I). When extraction errs systematically and the detector is reliable, testing before commitment pays off (the 60% versus 23% comparison above). The revised Section 5 states this rule.

What the bounds tell. The bounds answer the question of the introduction: how much feedback that names a constraint saves over feedback that can only refute one. The answer is on the order of HH tests against K/pextK/p_{\mathrm{ext}}, and Section 5.3 confirms it on Mastermind: with K=3K=3, blind proposal tests about 9, 19, 29, 45, and 51 candidates for H=9H=9, 18, 30, 45, and 60, while proposal from named constraints tests 4 to 18. Each reliability assumption is paired with an experiment that breaks it: unreliable extraction in Section 5.4, and detector false alarms in the table above.


Weakness 4: Modalities beyond text

TRACE needs three interfaces: a proposer of candidate constraints, a detector that checks feedback against the tested constraints, and a generator of actions that satisfy a constraint set. These interfaces are not inherently limited to text actions. The analysis applies to other modalities when the same representation, constrained-generation, and oracle assumptions hold. We focused on text because we study learning from language feedback, where constraint identities must be extracted from what users write. Visual tasks with user feedback, such as image generation, could instantiate the same interfaces with a multimodal model as generator and detector.


We hope the new comparisons, the corrected baselines, and the window guidance address your concerns.

AuthorsOpenReview ↗

Follow-up on our response and revised experiments

Dear Reviewer 91AC,

Thank you again for your review. We wanted to follow up on our responses before the discussion closes. The revised paper includes the stronger reasoning-model and fine-tuning comparisons you suggested (Appendix C.15, Table 30), as well as the detector-error and test-window study (Appendix C.13, Table 28). We also clarified TRACE’s external test-time role and revised the empirical claims to reflect where simpler approaches suffice and where testing proposed constraints helps.

We would appreciate your feedback on whether these additions address your concerns, and would be happy to clarify any remaining questions.

Best,

Authors of Paper #4738

AuthorsOpenReview ↗

Follow-up before the discussion closes

Dear Reviewer 91AC,

As the discussion closes today, we would appreciate your feedback on whether our responses and revisions address your concerns. These include the stronger reasoning-model and fine-tuning comparisons (Appendix C.15) and the detector-error and test-window study (Appendix C.13), alongside the clarified positioning and revised empirical claims.

If any questions or concerns remain, we would welcome the opportunity to address them before the discussion ends. Thank you again for your time and consideration.

Best,

Authors of Paper #4738

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We thank the reviewers for careful and constructive reviews. The paper studies how an agent should use language feedback: feedback proposes constraints, repeated tests decide which proposals are committed, and the analysis says what each kind of feedback costs. The reviewers found that the paper extends interactive constraint satisfaction to interaction-guided search in language agents (91AC), the separation of constraint proposal from commitment "a clear and useful design principle" and the distinction between falsification and identification access a precise way to state what feedback supplies (zUHS), and the constraint-exploration formulation "a useful starting point for further research" with experiments that include substantial controls (Ko7s). The reviews led to four changes, all included in the revised PDF.


1. The constraint tree is the search space; TRACE follows a single path in it (zUHS, Ko7s). Constraint-level feedback speaks about whole regions of the action space, and these regions are nested: every added constraint refines the region. The constraint tree of Section 2.2 is this space of nested regions. TRACE descends it along one path and tests each child before committing to it. A committed node contains an optimal action with high probability (Section 4), so no commitment has to be withdrawn and TRACE keeps only the current node. A set-based implementation accordingly gives identical results on every seed in all 14 configurations we ran (Appendix C.10). What the tree formulation contributes is the object of each test, the reason irrevocable descent is safe, and the accounting of cost; our replies to zUHS and Ko7s give the details.


2. A correction, and stronger structured baselines (zUHS, Ko7s). While re-auditing our baselines for this response, we found an implementation error in the RecMovie Direct-Commit baseline: its catalog filter read the type, year, and age attributes under the wrong keys, so only genre constraints were applied. With the fix, Direct-Commit reaches 96% on clean feedback, so the 90% vs. 23% comparison in Section 5.4 does not hold. We corrected Section 5.4 and its tables, added a count-based accumulation rule (Vote), and added unit tests that check the corrected filter against the catalog.

The corrected comparisons show where testing before commitment matters. On clean RecMovie feedback, direct accumulation reaches 96%, compared with TRACE-I's 90%, and count-based voting is more robust under moderate independent corruption. With a Qwen3-4B extractor and the rule-based detector, however, TRACE-I reaches 60%, while accumulation reaches at most 23% at the same budget (p<10−8p<10^{-8}). These results identify a setting in which testing proposed constraints remains useful even after strengthening the accumulation baselines.


3. LLM modules and feedback without templates (Ko7s, zUHS). We replaced the rule-based parser and detector with Qwen3-4B and rewrote every feedback sentence as free-form text, five times independently. TRACE-I's final output succeeds on 87% of seeds on average over the five rewrites. The task and the catalog are unchanged.


4. What the analysis tells, and practical guidance (91AC, Ko7s). The bounds answer how much feedback that names a constraint saves over feedback that can only refute one, and the Mastermind sweep of Section 5.3 confirms the prediction. We added a study of detector false alarms versus test-window length, which illustrates how test-window length interacts with detector false alarms and the output budget; success as a function of the number of feedback rounds; candidate counts before and after filtering; and an early statement that TRACE is a test-time controller that runs outside the model.


We respond to each reviewer below and are happy to provide further details.

AuthorsOpenReview ↗

Closing summary of clarifications, corrected comparisons, and additional evidence

We thank the reviewers for their feedback. To make the outcome of the discussion easy to follow, we summarize the principal clarifications, corrected comparisons, and additional evidence below. Section and appendix references refer to the revised manuscript.

1. Tree representation and source of improvement.
Related comments: zUHS, W1–2/Q1–2; Ko7s, W1/Q1.

TRACE is an external test-time controller that discovers and validates constraints before restricting subsequent generation. The requested set-based implementation produces identical results across all 14 configurations under the same proposal and testing rules (Appendix C.10). The tree represents the constraint-refinement space, and the algorithm can maintain the current constraint set and candidate pool. The contribution is the proposal–testing–commitment mechanism and its conditional analysis. We also report candidate counts before and after filtering (Appendix C.11), quantifying the narrowing achieved through constraint discovery. The structured-baseline comparisons separately examine the benefit of testing before commitment.

2. Stronger baselines and the value of testing.
Related comments: Ko7s, W2; 91AC, W2.

We strengthened the accumulation baselines to share TRACE-I’s extractor, catalog, and generator. During re-auditing, we corrected a catalog-filtering error in the submitted RecMovie baseline. Corrected accumulation reaches 96% on clean feedback, versus TRACE-I’s 90%, and voting also performs better under moderate independent corruption. The revised Section 5.4 replaces the affected comparisons and explicitly reports these findings.

In the separate experiment using a Qwen3-4B extractor and a reliable rule-based detector, TRACE-I achieves 60% final-output success versus at most 23% for OR and Vote accumulation, under the same 226-output cap (p<10−8p<10^{-8}, paired over 100 seeds). This comparison demonstrates a benefit from testing extracted constraints with the extractor, catalog, and generator held fixed. We also added the requested stronger reasoning-model and fine-tuning controls (Appendix C.15). The revised evidence identifies both settings where simpler alternatives suffice and a setting where validation improves outcomes.

3. Feedback templates and requirements for new tasks.
Related comments: Ko7s, W2/Q2.

We replaced both extraction and violation detection with Qwen3-4B and evaluated five independently rewritten feedback sets. TRACE-I averages 87% final-output success (Appendix C.14), demonstrating operation without template matching within RecMovie’s attribute schema. The framework takes the candidate predicate vocabulary, feedback modules, and constrained generator as explicit task interfaces. The vocabulary specifies possible requirements; the user’s active constraints remain unknown and must be discovered from feedback.

4. Theoretical content, practical guidance, and feedback efficiency.
Related comments: 91AC, W3; Ko7s, W1/Q1 and Q3.

The analysis accounts for stochastic validation before irrevocable commitment. Lemma 1 gives a sufficient test window, and the coverage guarantees specify conditions under which committed regions retain an optimal action with high probability. Under the stated assumptions, the upper bounds distinguish candidate-class dependence HH under uniform proposals from effective discovery cost K/pextK/p_{\mathrm{ext}} under sound identification and progress. The analysis therefore specifies when the proposal-count advantage yields a coverage guarantee. The added success-versus-feedback and detector-error/test-window experiments examine interaction efficiency and sensitivity to detector reliability (Appendices C.12–C.13).

The revised manuscript incorporates these corrections, additional results, and clarifications. Together, they characterize when usable constraint identities accelerate exploration and when validating proposed constraints improves outcomes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.