- 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
-
The paper is easy to read. The problem formulation, algorithm, and theoretical assumptions are clearly presented. The appendix provides detailed descriptions.
-
The constraint exploration formulation is interesting. This perspective is valuable and provides a useful starting point for further research.
-
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
-
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.
-
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
-
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?
-
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?
-
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
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 , 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, 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 ( predicates), line-syllable pairs in Haiku and Tanka (), and user-stated constraint types in TravelPlanner. With LLM modules, the remaining task-specific inputs are 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 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.
| Method | 5 | 10 | 15 | 20 | 60 | |
|---|---|---|---|---|---|---|
| TRACE-I, | 4 | 18 | 77 | 79 | 80 | 80 |
| TRACE-I, | 4 | 11 | 24 | 77 | 87 | 88 |
| DirectLLM (Qwen3-4B) | 18 | 27 | 33 | 38 | 38 | 48 |
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 , 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.
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 complexity can be achieved simply by attempting each option one-by-one. Furthermore, if a successful node can be identified with probability , the expected number of samples is naturally . While the paper contains extensive derivations, I feel it lacks more substantial conclusions. In particular, the assumption that 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 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, -separation, and, for the rate, the absence of zero-gap distractors. Without the last condition the cost returns to order (Section 4.1). What we take from the two theorems is their comparison: feedback that only refutes costs order , and feedback that names constraints removes from the bound.
Finite 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 , 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.
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 HK nodes at depth K: O(H) under blind proposal, and O(K/pext) 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 K true constraints by proposing blindly from a class of size H, and coverage costs on the order of H tests (Theorem 2). When feedback also names constraints, the cost falls to the order of K/pext (Theorem 3). Section 5.3 tests this prediction on Mastermind with K=3: blind proposal tests about 9, 19, 29, 45, and 51 candidates for H=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.