Paper deep dive

Constraint Tree Exploration for Learning from Language Feedback

Shaoang Li, Daniel R. Jiang, Jian Li

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 123

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%

Last extracted: 10/8/2026, 6:52:50 AM

Summary

The paper introduces TRACE (Test-and-Refine Algorithm for Constraint Exploration), a framework for learning from natural language feedback by modeling user intent as latent constraints. TRACE organizes candidate constraints in a tree and uses a 'test-before-commit' strategy to avoid prematurely ruling out valid solutions. It distinguishes between falsification (detecting contradictions) and identification (naming violated constraints). Theoretical analysis provides coverage bounds, showing that identification access reduces sample complexity dependence from the candidate class size H to K/p_ext. Empirical evaluation on tasks like RecMovie demonstrates superior success rates compared to prompting baselines.

Entities (10)

Daniel R. Jiang · person · 99%Jian Li · person · 99%Shaoang Li · person · 99%Meta Platforms · organization · 98%Stony Brook University · organization · 98%TrACE · algorithm · 98%TRACE-Falsification · algorithm-variant · 95%TRACE-Identification · algorithm-variant · 95%RecMovie · datasettask · 92%Constraint Tree · data-structure · 90%

Relation Signals (7)

Shaoang Li → affiliatedwith → Stony Brook University

confidence 99% · Shaoang Li Affiliation: Stony Brook University

Daniel R. Jiang → affiliatedwith → Meta Platforms

confidence 99% · Daniel R. Jiang Affiliation: Meta Platforms

Jian Li → affiliatedwith → Stony Brook University

confidence 99% · Jian Li Affiliation: Stony Brook University

TrACE → hasvariant → TRACE-Falsification

confidence 95% · We distinguish two ways of using the same feedback: (i) falsification... and (ii) identification... TRACE-Falsification... TRACE-Identification

TrACE → hasvariant → TRACE-Identification

confidence 95% · With reliable identification, TRACE-Identification can replace this dependence by K/p_ext

TRACE-Identification → achievessuccesson → RecMovie

confidence 92% · On RecMovie, TRACE-Identification achieves 73% and 86% final-output success

TrACE → uses → Constraint Tree

confidence 90% · TRACE, an algorithm that organizes candidate constraints in a tree

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

119,485 characters extracted from source content.

Expand or collapse full text

Constraint Tree Exploration for Learning from Language Feedback Shaoang Li Affiliation: Stony Brook University Email: shaoang.li@stonybrook.edu Daniel R. Jiang Affiliation: Meta Platforms Email: jian.li.3@stonybrook.edu Jian Li Affiliation: Stony Brook University Email: danielrjiang@gmail.com 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 (i) 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/pextK/p_ext, where K is the number of latent constraints and pextp_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. 1 Introduction Interactive agents built on large language models (LLMs) can receive feedback expressed in natural language rather than as a numerical reward (Cheng et al., 2023; Shinn et al., 2023). A user may reject a movie recommendation by saying “I wanted something from the 90s”, revise a travel plan by saying “this exceeds my budget”, or correct a generated poem by saying “the second line has too many syllables”. Such feedback can explain why an action failed by identifying an unmet requirement. Because this requirement also applies to other candidate actions, the feedback can help narrow the search for acceptable alternatives. The challenge is to infer useful constraints from incomplete or ambiguous feedback and determine when the available evidence justifies enforcing them. Existing approaches have explored how natural-language feedback can be incorporated into LLM agents. Feedback-driven methods, including Reflexion (Shinn et al., 2023), Self-Refine (Madaan et al., 2023), TextGrad (Yuksekgonul et al., 2025), and language-agent tree search (LATS) (Zhou et al., 2024), use feedback to guide generation and search through revised prompts, reflective memories, textual gradients, or value estimates. Recent theoretical work provides complementary abstractions, including regret bounds under hindsight instructions (Misra et al., 2024) and consistency-based elimination over global hypotheses (Xu et al., 2025). We focus on pure exploration over feasible regions: the learner discovers, tests, and accumulates latent constraints to progressively restrict the action space. This formulation makes explicit both the information needed to propose a constraint and the evidence needed to commit to it. Figure 1: Constraint-tree exploration in TRACE. At a committed node v with constraint set CvC_v, a candidate constraint cnewc_new proposes a child u with Cu=Cv∪cnewC_u=C_v∪\c_new\. The child is tested by sampling actions satisfying CuC_u: feedback contradicting CuC_u rejects the child, while survival for a fixed number mexpm_exp of tests leads to commitment. Extracted identities guide proposals; falsification tests determine commitment. We consider episodes with fixed latent requirements represented in a finite candidate class. We distinguish two oracle-access regimes induced by the same natural-language feedback. In the falsification setting, the learner has access to a violation oracle that tests whether feedback contradicts the constraint set currently being tested. In the identification setting, the learner additionally has access to an extractor that may name a violated atomic constraint. These two regimes specify what information the learner can obtain from the same raw feedback. Identification access can accelerate exploration by revealing which constraint to test next. But an extracted identity is only a proposal, not a fact: committing an incorrectly extracted constraint can permanently shrink the feasible region in the wrong direction. Without identities, however, discovering useful constraints may require blind search over a large candidate class. The challenge is therefore to benefit from named constraints without trusting them too early. This leads to the central question of the paper: How can an agent exploit named constraints from language feedback without committing to them prematurely, and when does identification access reduce the sample complexity of exploration? We answer this question with the Test-and-Refine Algorithm for Constraint Exploration (TRACE). The search state in TRACE is the committed constraint set, which indexes a surviving feasible region. Candidate refinements form children in a constraint tree, as illustrated in Figure 1. Rather than committing to a proposed constraint immediately, TRACE performs a multi-round test: it samples actions from the child region and rejects the child if feedback contradicts the tested constraint set. If the child survives repeated tests, the algorithm commits to it and descends the tree. Thus, extracted identities are treated as proposals, not facts. The tree separates proposal from commitment and organizes partially accumulated constraints. The same test-before-commit primitive instantiates the two oracle-access regimes formalized in Section 2.2: TRACE-Falsification (TRACE-F; Assumption 1 only), which uses the violation oracle for falsification, and TRACE-Identification (TRACE-I; Assumptions 1 and 2), which additionally prioritizes constraints extracted from feedback. Our analysis separates the cost of blind falsification from the value of usable identities. In the falsification setting, TRACE-F discovers true constraints by proposing candidates from a finite class of size H, leading to sample complexity ~(H) O(H) up to the per-test cost of falsification (Theorem 2). In the identification setting, under sound extraction and an explicit discovery-progress condition, TRACE-I replaces this dependence by the effective discovery cost ~(K/pext) O(K/p_ext), where K is the number of latent constraints and pextp_ext lower-bounds the probability of extracting a missing true constraint from informative feedback (Theorem 3). These bounds quantify how usable identities can reduce the number of tested refinements relative to uniform blind search. Empirically, we evaluate TRACE across five controlled language-feedback environments spanning six task instances: recommendation, two entity-deduction benchmarks, Mastermind, and constrained poem generation. On RecMovie, TRACE-I achieves 73% and 86% final-output success under common caps of 20 and 60 evaluated outputs, compared with at most 42% and 48% for the evaluated prompting baselines. Controlled Mastermind sweeps show that identification-guided proposals require fewer tested refinements as the candidate class grows. False-identity experiments further show that TRACE-I remains more robust than direct accumulation when extracted identities are corrupted and the falsification detector remains reliable. In summary, we make three contributions. First, we formulate learning from language feedback as pure exploration over latent constraints, where feedback provides local evidence about feasible regions rather than scalar rewards. Second, we introduce TRACE, a parser-agnostic test-before-commit framework that treats extracted identities as proposals rather than facts. Third, we derive high-probability coverage bounds that quantify the benefit of identification access, and we evaluate proposal efficiency, interaction budgets, and robustness to identity corruption. 2 Problem Formulation and Constraint Tree We formulate learning from language feedback as a pure-exploration problem over latent constraints. The learner never observes numerical utility values; instead, it receives natural-language feedback that may reveal violated requirements. We then introduce the constraint tree, which organizes partially accumulated constraints as feasible regions to be tested and refined. 2.1 Language-feedback pure exploration Action space and latent utility. Let X be a finite action space and let U:→[0,1]U:X→[0,1] be an unknown latent utility function. The interaction proceeds for T rounds. In each round t∈[T]t∈[T], an algorithm A selects an action xt∈x_t based on the past observations (x1,f1,…,xt−1,ft−1)(x_1,f_1,…,x_t-1,f_t-1), and receives natural-language feedback ft∈ℱf_t . The algorithm never observes U⁡(xt)U(x_t) directly. Language feedback as constraint evidence. For each action x∈x , feedback is drawn from a conditional distribution PxP_x over ℱF. Conditioned on xtx_t, the feedback ftf_t is independent of the past. We study the regime in which feedback may identify requirements that the action violates, provide qualitative corrections, or confirm that the action is close to satisfying the user’s intent. For example, a user may say “the recommendation is not from the 90s” or “the answer is good, but it misses the required attribute”. We treat such feedback as a constraint signal: progress comes from discovering and testing latent requirements, rather than from comparing observed numerical rewards. Canonical constraint class. Let ℋH be a finite class of canonical candidate constraints, with H:=|ℋ|H:=|H|, within which equality and set membership are well-defined. Each constraint c∈ℋc defines a region Region⁡(c)⊆Region(c) , and we write Sat(x,c):=x∈Region(c)Sat(x,c):=1\x (c)\ for the satisfaction indicator. For a constraint set C⊆ℋC , define Region⁡(C):=⋂c∈CRegion⁡(c)Region(C):= _c∈ CRegion(c), with Region⁡(∅):=Region( ):=X. The latent constraints below are assumed to lie in ℋH, i.e., the algorithm searches over a class that contains them. Latent constraints. The user’s hard requirements are encoded by an unknown subset C∗:=c1∗,…,cK∗⊆ℋC^*:=\c_1^*,…,c_K^*\ of K:=|C∗|K:=|C^*| latent constraints, with feasible region Region⁡(C∗)=⋂k=1KRegion⁡(ck∗)Region(C^*)= _k=1^KRegion(c_k^*). We assume that these constraints are necessary for optimality, i.e., every globally optimal action satisfies all of C∗C^*: ∗:=arg⁡maxx∈⁡U⁡(x)≠∅X^*:= _x U(x)≠ and ∗⊆Region⁡(C∗)X^* (C^*). Let x∗∈∗x^* ^* and U∗:=U⁡(x∗)U^*:=U(x^*). Apart from this compatibility condition, the utility function U is arbitrary: actions outside Region⁡(C∗)Region(C^*) may still have positive utility, and U may take any values in [0,1][0,1] rather than being restricted to 0,1\0,1\. Thus, the constraints define the feasible region containing all global optima, while the utility function determines how costly it is to violate or miss them. Coverage objective and regret consequence. After T rounds, the algorithm outputs a single action x x. The primary objective in this paper is coverage: reach a nonempty region contained in Region⁡(C∗)Region(C^*) and sample the output from that region. The utility function is not observed during interaction; it is used only to express the consequence of coverage for simple regret, ⁡[rT]:=⁡[U∗−U⁡(x^)], [r_T]:=E [U^*-U( x) ], (1) where the expectation is over the algorithm’s randomness and the feedback channel. As formalized below, if the algorithm reaches a region contained in Region⁡(C∗)Region(C^*), then the remaining regret is controlled by the variation of U within the latent feasible region. 2.2 Constraint tree representation The constraint tree organizes partial information about the latent feasible region. Each node corresponds to a set of constraints accumulated so far and therefore to the region of actions satisfying them. Moving deeper in the tree adds constraints and shrinks the feasible region. Nodes as constraint sets. A constraint tree T is a rooted tree of proposal paths. Each node v is associated with the accumulated constraint set Cv⊆ℋC_v and feasible region v:=(Cv):=x∈:Sat(x,c)=1,∀c∈Cv=Region(Cv). _v:=X(C_v):=\x :Sat(x,c)=1,∀ c∈ C_v\=Region(C_v). (2) The root v0v_0 has Cv0=∅C_v_0= and v0=X_v_0=X. Each child u of v adds one new constraint, so Cu=Cv∪cC_u=C_v∪\c\ for some c∈ℋ∖Cvc C_v. The depth of v is h⁡(v):=|Cv|h(v):=|C_v|. Different proposal orders may induce the same accumulated set and feasible region; we keep them as distinct tree nodes because they correspond to different search histories. Viable and spurious nodes. For any node v with a nonempty feasible region, define U⁡(v):=maxx∈v⁡U⁡(x),Δ⁡(v):=U∗−U⁡(v). U(v):= _x _vU(x), (v):=U^*-U(v). (3) We call v viable if Δ⁡(v)=0 (v)=0, i.e., vX_v contains a globally optimal action, and spurious if Δ⁡(v)>0 (v)>0. The condition Cv⊆C∗C_v C^* is sufficient for viability, but not necessary: a redundant or stronger-looking constraint outside C∗C^* may still preserve at least one global optimum. The algorithm uses feedback to reject spurious branches while preserving viable ones. Within-region spread. Even a viable region may contain actions of different utility. We define the within-node spread Spread⁡(v):=U⁡(v)−infx∈vU⁡(x),Spread(v):=U(v)- _x _vU(x), and, for the latent feasible region, Spread⁡(C∗):=supx∈Region⁡(C∗)U⁡(x)−infx∈Region⁡(C∗)U⁡(x). (C^*):= _x (C^*)U(x)- _x (C^*)U(x). (4) If v⊆Region⁡(C∗)X_v (C^*), then any x^∈v x _v satisfies all latent constraints and has regret at most Spread⁡(C∗)Spread(C^*). Thus, the theory focuses on reaching a covered region; Spread⁡(C∗)Spread(C^*) captures the residual difficulty of choosing among feasible actions. Oracle access and the two settings. We distinguish the raw natural-language feedback ft∼Pxf_t P_x from the oracle information that the learner can reliably extract from it. The raw feedback is the same in both regimes; the regimes differ only in the oracle interfaces available to the learner. Assumption 1 (Falsification access). The learner has access to a violation detector Viol:ℱ×2ℋ→0,1Viol:F× 2^H→\0,1\ such that Viol⁡(f,C)=1Viol(f;C)=1 only if f contradicts some constraint already in C. In particular, feedback that reveals a missing constraint outside C is discovery feedback, not a falsification of C. Assumption 2 (Identification access). In addition to Assumption 1, the learner has an extractor Extract:ℱ→ℋ∪∅Extract:F ∪\ \ that returns a canonical violated constraint when one can be reliably identified, and returns ∅ otherwise. For example, consider a tested child with Cu=year=1980sC_u=\ year=1980s\. Feedback “I wanted something from the 90s” can both refute CuC_u and propose year=1990s. By contrast, feedback “I wanted a comedy” can reveal a missing genre constraint without contradicting CuC_u. The falsification setting assumes only Assumption 1, equivalently using a null extractor. The identification setting assumes both Assumptions 1 and 2. The corresponding algorithmic variants are TRACE-F and TRACE-I. Quantitative reliability and soundness conditions, together with the oracle-level noise model used in our analysis, are stated in Appendix B.1. Algorithmic interfaces. Beyond these oracles, TRACE uses a constrained generator QCQ_C for sampling actions satisfying a constraint set C, and a proposer ProposePropose for selecting candidate constraints to test. These modules may be implemented by template decoders, LLM-based modules, database filters, constrained decoders, or domain-specific heuristics. 3 Test-and-Refine Algorithm for Constraint Exploration We now describe the Test-and-Refine Algorithm for Constraint Exploration (TRACE). The goal is to reach a constraint-tree node whose feasible region is contained in the user’s latent feasible region. TRACE maintains a committed node v, proposes candidate constraints to refine CvC_v, and uses language feedback to decide whether each proposed refinement should be rejected or committed. The central design principle is that extracted identities serve as proposals rather than facts: they bias which child is tested next, but enter the committed set only after passing a multi-round falsification test. Algorithm 1 Test-and-Refine Algorithm for Constraint Exploration (TRACE). 1: horizon T, test length mexpm_exp, max tests NmaxN_ , generators QC\Q_C\, detector ViolViol, proposer ProposePropose, extractor ExtractExtract 2: Initialize v←v0v← v_0 with Cv0=∅C_v_0= ; W←∅W← ; Rv′←∅R_v ← for every node v′v ; t←0t← 0; n←0n← 0 3: while t<Tt<T and n<Nmaxn<N_ do 4: cprop←Propose⁡(v,W,Rv)c_prop (v,W,R_v); break if cprop=∅c_prop= 5: u←u← child of v with Cu=Cv∪cpropC_u=C_v∪\c_prop\ 6: if u=∅X_u= then Rv←Rv∪cpropR_v← R_v∪\c_prop\; continue empty region: exclude at v, no budget 7: n←n+1n← n+1; pass←pass← true 8: for s=1s=1 to mexpm_exp do 9: if t≥Tt≥ T then pass←pass← false; break 10: t←t+1t← t+1; sample xt∼QCux_t Q_C_u, receive ftf_t 11: cext←Extract⁡(ft)c_ext (f_t); if cext≠∅c_ext≠ then W←W∪cextW← W∪\c_ext\ store extracted identity 12: if Viol⁡(ft,Cu)=1Viol(f_t;C_u)=1 then pass←pass← false; break 13: if pass=pass= true then v←uv← u else Rv←Rv∪cpropR_v← R_v∪\c_prop\ commit, or exclude at v 14: return x^∼QCv x Q_C_v Feedback use and commitment. During a test of a proposed child u, feedback is used in two ways. The detector Viol⁡(ft,Cu)Viol(f_t;C_u) decides whether u is falsified. When identification access is available, Extract⁡(ft)Extract(f_t) may add a candidate constraint to a global working set W for future proposals. Crucially, entries in W are never committed directly: they only affect which child is tested next. Test-before-commit. Given a proposed constraint cpropc_prop, TRACE forms the child u with Cu=Cv∪cpropC_u=C_v∪\c_prop\ and samples from QCuQ_C_u for up to mexpm_exp rounds. If any feedback contradicts CuC_u, the child is rejected and the algorithm remains at v. A per-node set RvR_v records the candidates ruled out at v (empty region or rejected child), so they are not proposed again at v; this ensures termination and never excludes a missing true constraint while v is viable (Remark 1). If the child survives all mexpm_exp tests, TRACE commits to u and moves deeper in the tree. At the end of the budget, it returns x^∼QCv x Q_C_v, where v is the deepest committed node at termination. If Region⁡(Cv)⊆Region⁡(C∗)Region(C_v) (C^*), then x x satisfies all latent requirements; the remaining simple regret is controlled by Spread⁡(C∗)Spread(C^*). Variants. Both variants propose from ℋv:=ℋ∖(Cv∪Rv)H_v:=H (C_v∪ R_v), and ProposePropose returns ∅ when ℋv=∅H_v= . TRACE-F uses a null extractor and proposes uniformly from ℋvH_v. TRACE-I first proposes from W∩ℋvW _v when nonempty, and otherwise falls back to uniform proposal over ℋvH_v. Both variants use the same falsification test before commitment; operational properties of W, the detector contract, and the role of the counters t,st,s in Algorithm 1 are recorded in Appendix B.2. Implementation and theory bridge. TRACE is parser- and generator-agnostic: in finite recommendation or entity-deduction tasks, QCQ_C can be a filtered catalog sampler, while in constrained generation it can be an LLM prompted with accumulated requirements or a constrained decoder. The detector and extractor can likewise be template-based, rule-based, LLM-based, or hybrid. Our experiments use lightweight decoders where possible, while Section 4 abstracts away these implementation choices and analyzes how many child tests are needed to reach a covered region. 4 Theoretical Analysis We analyze the two oracle-access regimes introduced in Section 2.2. The analysis abstracts away implementation details of the generator, detector, extractor, and proposer, and asks how many interaction rounds suffice for TRACE to reach a covered region. TRACE-F (Assumption 1 only) uses the violation oracle for falsification and searches over the candidate class by blind proposal. TRACE-I (Assumptions 1 and 2) additionally uses extracted constraint identities to bias proposals. Both analyses share the same multi-sample falsification argument; they differ in how many child tests are needed before the latent feasible region is covered. Full proofs are deferred to Appendix B. 4.1 Analysis model and guarantee We work with the finite canonical constraint class ℋ⊇C∗H C^* from Section 2.1. Throughout, H:=|ℋ|H:=|H| is the candidate class size and K:=|C∗|K:=|C^*| is the number of latent constraints; the bounds depend on these together with the extraction probability pextp_ext in the identification setting. The constrained generator QCQ_C is supported on ⁡(C):=x∈:Sat⁡(x,c)=1∀c∈CX(C):=\x :Sat(x,c)=1\ ∀ c∈ C\ and returns independent samples on each call. The identification-setting theorem (Assumption 2) additionally requires sound extracted identities, i.e., ExtractExtract returns either a latent constraint or ∅ . Thus the theorem captures missed identity discoveries; spurious extracted identities are treated empirically in Section 5.4. The implementation may run ExtractExtract on every feedback message; the theorem only requires that informative feedback events, i.e., violations observed while testing a spurious child, add missing true constraints to W with probability at least pextp_ext. Conditions for the guarantees. The formal assumptions are stated in Appendix B.1. Here we summarize their roles. ⊳ Refutational feedback: For a node v, let qv:=Pr[Viol(f;Cv)=1∣x∼QCv,f∼Px]q_v:= [Viol(f;C_v)=1 x Q_C_v,f P_x] be the probability that one test sample falsifies the region. Viable regions are not incorrectly rejected by the contradiction detector: if Δ⁡(v)=0 (v)=0, then qv=0q_v=0. Conversely, spurious regions are falsifiable: if Δ⁡(v)>0 (v)>0, then qv≥min⁡1,cfalΔ(v)βq_v≥ \1,c_fal (v)^β\ for constants cfal,β>0c_fal,β>0. The exponent β captures the resolution of the violation oracle (Assumption 1); larger β means small gaps are harder to detect. ⊳ ε -separation (gap structure): At the target tolerance ε , every child of a viable node either preserves a global optimum, Δ⁡(u)=0 (u)=0, or excludes all optima by margin Δ⁡(u)>ε (u)> . This is a structural condition on (,U,ℋ,C∗)(X,U,H,C^*), not on the generator, detector, or extractor; it ensures that a finite test window can separate viable children from spurious ones. ⊳ Identification-access progress: Theorem 3 additionally assumes two conditions. The first is structural (Assumption 8): every constraint in ℋ∖C∗H C^* with a nonempty region excludes all global optima with gap larger than ε even when imposed alone, so adding it to any viable node yields an empty region or such a gap. In particular, the candidate class contains no zero-gap distractors, i.e., constraints outside C∗C^* that preserve a global optimum when added to a viable node. The second concerns extraction (Assumption 3): on informative feedback, the extractor of Assumption 2 reveals a missing latent constraint with probability at least pextp_ext. Together, the two conditions force every incorrect candidate to be incompatible with the true requirements (Appendix B.1). Reliable template decoders can support the extraction condition, but not the structural one, which depends only on (,U,ℋ,C∗)(X,U,H,C^*). When either condition fails, the ~(K/pext) O(K/p_ext) guarantee of Theorem 3 does not apply. Coverage guarantee. We say that an algorithm enjoys an (ε,δ)( ,δ)-coverage guarantee with budget T if, with probability at least 1−δ1-δ, the deepest committed node v at termination satisfies Region⁡(Cv)⊆Region⁡(C∗) (C_v) (C^*) (5) within T interaction rounds. This target is representation-invariant: exact syntactic recovery of C∗C^* is sufficient, but not necessary. If x^∼QCv x Q_C_v, coverage implies x^∈Region⁡(C∗) x (C^*) and therefore ⁡[rT]≤Spread⁡(C∗)+δ. [r_T] (C^*)+δ. (6) The two theorems below establish coverage under the falsification and identification settings. 4.2 Falsification- and identification-setting guarantees Multi-sample falsification. The core observation is that a spurious child is unlikely to survive many independent feedback tests. We state the lemma for an arbitrary tested node; in Algorithm 1, this node is typically the proposed child. Lemma 1 (Multi-sample falsification). Let v be any node with Δ⁡(v)>ε (v)> . If the algorithm samples xs∼QCvx_s Q_C_v for m independent rounds and observes feedback fs∼Pxsf_s P_x_s, then Pr[Viol(fs;Cv)=0for all s=1,…,m]≤exp(−mcfalεβ). [Viol(f_s;C_v)=0\ for all s=1,…,m ]≤ (-m\,c_fal ^β ). (7) Consequently, if m≥log⁡(1/δ′)/(cfalεβ)m≥ (1/δ )/(c_fal ^β), then a node with gap larger than ε survives m tests with probability at most δ′δ . Falsification-setting guarantee. We first consider TRACE-F, which uses only the violation oracle of Assumption 1 and proposes uniformly from the finite candidate class. Theorem 2 (Coverage in the falsification setting). Suppose the conditions of Section 4.1 hold for refutational feedback and ε -separation. Fix δ∈(0,1)δ∈(0,1) and ε∈(0,1] ∈(0,1]. With Nmax=⌈Hlog⁡2max⁡(K,1)δ⌉,mexp=⌈log⁡(2Nmax/δ)cfalεβ⌉,T=Nmaxmexp, N_ = H 2 (K,1)δ , m_exp= (2N_ /δ)c_fal ^β , T=N_ m_exp, (8) TRACE-Falsification enjoys an (ε,δ)( ,δ)-coverage guarantee with T=~(H/(cfalεβ))T= O(H/(c_fal ^β)). The bound has two main factors. The proposal cost is ~(H) O(H): in the canonical finite-class proof, a sufficient route to coverage is to propose all latent constraints, which uniform proposal achieves in ⁡(Hlog⁡K)O(H K) calls. This cost is over proposal calls from ℋH, not over all ordered root-to-leaf paths in the constraint tree. The testing cost is ~(1/(cfalεβ)) O(1/(c_fal ^β)): by Lemma 1, this many samples reject any child with gap larger than ε with the desired confidence. Viable children survive because qu=0q_u=0 when Δ⁡(u)=0 (u)=0, while spurious children with Δ⁡(u)>ε (u)> are refuted with probability at least cfalεβc_fal ^β per test. Once Region⁡(Cv)⊆Region⁡(C∗)Region(C_v) (C^*), the returned action lies in the latent feasible region, giving ⁡[rT]≤Spread⁡(C∗)+δE[r_T] (C^*)+δ. Identification-setting guarantee. Theorem 2 shows the falsification setting alone suffices for coverage, but requires blind proposal over the ambient candidate class. In a favorable identification regime where extracted identities make reliable progress toward missing latent constraints, we show that this candidate-class dependence can be replaced by the effective discovery cost K/pextK/p_ext. Theorem 3 (Coverage in the identification setting). Suppose the conditions of Section 4.1 hold, including identification-access progress. Fix δ∈(0,1)δ∈(0,1) and ε∈(0,1] ∈(0,1]. With Nmaxid=⌈64pext(K+log⁡4δ)⌉,mexpid=⌈log⁡(2Nmaxid/δ)cfalεβ⌉,T=Nmaxidmexpid,N_ ^id= 64p_ext (K+ 4δ ) , m_exp^id= (2N_ ^id/δ)c_fal ^β , T=N_ ^idm_exp^id, TRACE-Identification enjoys an (ε,δ)( ,δ)-coverage guarantee with T=~(K/(pextcfalεβ))T= O(K/(p_ext\,c_fal ^β)). Theorem 3 replaces the blind-search cost H by the effective discovery cost K/pextK/p_ext. The intuition is that, under identification access, diagnostic feedback can add a missing true constraint to W with probability pextp_ext; once in W, that constraint is proposed before blind candidates and survives the same test window. Thus identification access is most useful when H is large relative to K/pextK/p_ext, and its advantage diminishes when the candidate class is small or extraction is unreliable. Section 5.3 validates this regime distinction. Section 5.4 tests the case where the soundness clause of Assumption 2 is not satisfied (the extractor returns spurious constraints). 5 Experiments We evaluate the practical benefits of TRACE’s constraint-based formulation and test-before-commit mechanism through four questions: (Q1) How does TRACE compare with prompting methods under different feedback interfaces and common output caps? (Q2) Does identification feedback reduce the number of candidate refinements tested as the candidate class grows? (Q3) When does test-before-commit improve over directly accumulating extracted constraints? (Q4) How robust is TRACE to incorrect extracted identities? Setup. We evaluate on five environments spanning six task instances: LLF-Bench RecMovie (Cheng et al., 2023), a synthetic 20-Questions environment (20Q), Apple’s Entity-Deduction Arena (EDA Things) (Zhang et al., 2024), per-position Mastermind (Li & Zhu, 2024), and LLF-Bench Poem (Cheng et al., 2023) with Haiku and Tanka forms. The primary metric is env.success over 100100 seeds per cell; for RecMovie this refers to the returned recommendation list (an interaction-budget any-success diagnostic is in Appendix C.3). We compare TRACE-F, which uses binary falsification with uniform proposals, with TRACE-I, which additionally prioritizes constraints extracted from past feedback. Prompt-based baselines Random, DirectLLM, Reflexion (Shinn et al., 2023), and Self-Refine (Madaan et al., 2023) use Qwen3-4B (Yang et al., 2025) under fixed per-environment interaction budgets (T=20T=20 on RecMovie) that are not matched to TRACE’s default configuration (see Section 5.2 for equal budgets); structured same-interface baselines use the same decoded feedback as TRACE but remove the test-before-commit step. Throughout this section, brackets in result tables denote Wilson 95%95\% confidence intervals; hyperparameters, Viol/ExtractViol/Extract implementation, full-table intervals, attempts, and soft-utility diagnostics are deferred to Appendix C. Table 1: Main comparison under three oracle-access regimes. Random does not consume feedback. Wilson 95%95\% intervals in Tables 7 and 10; Mastermind/Haiku/Tanka in Appendix C.2. RecMovie 20Q EDA Method Natural Falsif. Identif. Natural Falsif. Identif. Natural Falsif. Identif. Random 5% 15\% – – 41%41\% – – 74%74\% – – DirectLLM 17%17\% 27%27\% 40%40\% 12%12\% 43%43\% %100\% 43%43\% 84%84\% %100\% Reflexion 26%26\% 35%35\% 42%42\% 11%11\% 29%29\% %100\% 55%55\% 69%69\% %100\% Self-Refine 21%21\% 26%26\% 32%32\% 73%73\% 19%19\% %100\% 78%78\% 40%40\% %100\% TRACE – %51\% %90\% – %84\% %100\% – %87\% 99%99\% 5.1 Main comparison: explicit constraint structure helps Table 1 reports env.success on three task instances under three oracle-access regimes: Natural feedback, where prompt-based methods consume the environment’s raw text; Falsification access, corresponding to Assumption 1; and Identification access, corresponding to Assumptions 1+2. Within each regime, all methods share the same oracle interface, so cross-method comparisons within a regime are matched. TRACE-F and TRACE-I appear under the Falsification and Identification columns, respectively; they are the test-before-commit instantiations of the falsification and identification settings, not competing variants. At each method’s default budget, within each oracle regime, TRACE improves over the strongest same-regime prompt baseline: TRACE-F by 1616p on RecMovie (51%51\% vs. 35%35\%), 4141p on 20Q, and 33p on EDA; TRACE-I by 4848p on RecMovie (90%90\% vs. 42%42\%), and by at least 3131p when all methods share an equal output cap (Section 5.2). On 20Q and EDA, identity-feedback methods reach 99–100%, leaving little headroom for additional gains in these configurations. Self-Refine’s success on 20Q drops from 73% under natural feedback to 19% under binary projection, illustrating the importance of the information retained in the feedback interface. Three additional task instances (Mastermind with K=3K=3, Haiku, and Tanka) are deferred to Appendix C.2, where the qualitative pattern is identical: TRACE-I reaches 9999–100%100\% while natural-feedback baselines remain below 30%30\%. The candidate-class scaling on Mastermind is studied in Section 5.3. 5.2 Equal output budgets and interaction cost Table 1 uses method-specific default budgets. We therefore compare TRACE-I with prompting and sampling controls on RecMovie, which provides a non-saturated comparison under identification feedback. Figure 2a evaluates common caps of B∈20,60B∈\20,60\ environment-evaluated outputs, scoring one returned output per seed: TRACE-I (mexp=5m_exp=5) uses at most B−1B-1 outputs for tests and returns one within the cap, while each iterative baseline returns its first accepted output or its last output at the cap. All baselines receive the same identity projection as TRACE-I; to run them with 6060 outputs, DirectLLM-W8 and Self-Refine-W8 keep only the eight most recent interactions, and Reflexion-NoCycle disables early trial termination on repeated recommendations. TRACE-I reaches 73%73\% at B=20B=20 and 86%86\% at B=60B=60, versus at most 42%42\% and 48%48\% for the baselines evaluated at each cap; Best-of-N with an oracle selector reaches 17%17\% and 21%21\%. Each test round shows a complete recommendation rather than asking the user to reconfirm a constraint, and smaller test windows trade reliability for fewer rounds (Figure 2b): with mexp=1m_exp=1, TRACE-I reaches 65%65\% with 4.434.43 feedback rounds on average. Under a tight cap a larger window uses up more of the budget (78%78\% for mexp=3m_exp=3 vs. 73%73\% for mexp=5m_exp=5 at B=20B=20), whereas at B=60B=60 it reaches 86%86\%. Appendix C.3 gives the full protocol, intervals, and costs, and shows that seeding the root with up to two oracle-provided constraints raises success to 90%90\% at B=20B=20. Figure 2: RecMovie under equal output budgets (100100 seeds; final-output success with Wilson 95%95\% intervals). (a) Common caps of B=20B=20 and B=60B=60 environment-evaluated outputs. Hatched bars are the Table 1 baseline configurations, which were run only with T=20T=20; solid baseline bars are the W8/NoCycle variants run with 6060 outputs. (b) TRACE-I success versus mean feedback rounds for test windows m=mexp∈1,3,5m=m_exp∈\1,3,5\; dashed lines mark the strongest baseline at each cap. 5.3 Identity feedback reduces blind search Theorem 3 predicts that identity-aware proposal can replace blind dependence on the ambient candidate class size H by the effective discovery cost K/pextK/p_ext. We test this in a controlled Mastermind environment with candidate class ℋ=(i,c):i∈[K],c∈paletteH=\(i,c):i∈[K],\,c \ and |ℋ|=K⋅ncolors|H|=K· n_colors. Table 2 fixes K=3K=3 (with Nmax=80N_ =80 enlarged from the headline Nmax=15N_ =15 to give TRACE-F budget headroom at large |ℋ||H|) and varies ncolors∈3,6,10,15,20n_colors∈\3,6,10,15,20\, thereby increasing H while keeping the number of latent constraints fixed; attempts is the number of proposed children actually tested. Under the uniform binary proposer, success drops from 100%100\% at |ℋ|=9|H|=9 to 74%74\% at |ℋ|=60|H|=60, and mean attempts grow from 9.089.08 to 50.8250.82. In contrast, the decoded identity proposer remains at 9999–100%100\% success across the same sweep and uses substantially fewer attempts (3.913.91 to 18.0818.08). These results support the proposal-efficiency advantage of identification access as the candidate class grows. Table 2: H-sweep on Mastermind (K=3K=3, mexp=15m_exp=15, Nmax=80N_ =80). Wilson 95%95\% intervals in Table 8. ncolorsn_colors |ℋ||H| Falsification Identification env.succ. attempts env.succ. attempts 33 99 %100\% 9.08 19.08 %100\% 3.91 13.91 66 1818 %100\% 18.7518.75 %100\% 4.84 14.84 1010 3030 98% 198\% 29.3529.35 %100\% 6.77 16.77 1515 4545 88% 188\% 45.3845.38 %100\% 10.5410.54 2020 6060 74% 174\% 50.8250.82 99% 199\% 18.0818.08 5.4 Why test-before-commit matters Table 3: Direct-Commit baselines: best of AND,OR,RANKED\AND,OR,RANKED\ per environment; variants in Appendix C.3. Method Rec. 20Q EDA TRACE-I %90\% %100\% 99%99\% Direct-Commit 23%23\% %100\% %100\% Table 4: False-identity robustness on RecMovie (pfalse=0p_false=0 row matches Table 1). pfalsep_false TRACE-I Direct-Commit 0.00.0 %90\% [8383,9494] 23%23\% [1616,3232] 0.20.2 %74\% [6565,8282] 16%16\% [1010,2424] 0.50.5 %60\% [5050,6969] 8% 18\% [44,1515] We examine when test-before-commit improves performance by comparing TRACE-I with direct accumulation using the same decoder, followed by controlled corruption of extracted identities. Same-decoder direct accumulation. Table 4 compares TRACE-I with Direct-Commit baselines that immediately accumulate constraints from the same decoded feedback. Under the reported default configurations, TRACE-I reaches 90%90\% success on RecMovie, compared with 23%23\% for the strongest direct-commit variant. On 20Q and EDA Things, where identity hints are essentially clean, both approaches reach 9999–100%100\%. These saturated cases leave little headroom for further gains from test-before-commit. We next examine the effect of incorrect identities through controlled corruption. False extracted identities. In Table 4, we inject false identities into RecMovie by replacing each decoded feedback predicate with a wrong same-dimension predicate with probability pfalsep_false. TRACE-I uses corrupted identities only as proposals, whereas direct commit immediately accumulates them. As corruption increases, both methods degrade, but TRACE-I remains more robust: at pfalse=0.5p_false=0.5, it still reaches 60%60\% env.success, while the best direct-commit variant reaches only 8%8\%. These results support testing extracted constraints before commitment when identity errors are possible. Additional diagnostics. Component ablations on RecMovie distinguish proposal quality from detector reliability. With the rule-based detector fixed, an LLM-based atomic proposer increases interaction-budget any-success from 57%57\% under uniform proposals to 74%74\%. Replacing the rule-based detector with an LLM detector instead reduces TRACE-F’s any-success from 57%57\% to 21%21\%. Appendix C reports these ablations, soft-utility results, direct-commit variants, feedback-omission robustness, and a complementary Mastermind K-sweep; Appendix C.5 provides an example execution trace. 5.5 TravelPlanner: cross-LLM identification Table 5: TRACE-I on TravelPlanner, n=50n=50. Identification: committed Cv⊇C∗C_v C^*. Final Pass: plan passes every env check. LLM Identification Final Pass Qwen3-4B 84%84\% [7272, 9292] 16%16\% [8 08, 2929] DeepSeek-V4-Flash %86\% [7474, 9393] %90\% [7979, 9696] We use a feedback-enabled adaptation of TravelPlanner’s sole-planning setting (Xie et al., 2024), supplying reference information and evaluating complete candidate plans. User-stated requirements form the candidate constraint class ℋH, and per-check evaluation messages provide feedback for testing candidate refinements. We evaluate on the same 5050 validation queries with two LLM generators: Qwen3-4B (Yang et al., 2025) served locally, and DeepSeek-V4-Flash (DeepSeek-AI, 2026). We report the rate of committing all represented constraints, Cv⊇C∗C_v C^*, and final-plan success under this adapted protocol. The two generator configurations yield similar rates of committing all represented constraints, 84%84\% and 86%86\%, while their final-plan pass rates differ substantially, at 16%16\% and 90%90\%. These results distinguish explicit constraint commitment from producing a plan that passes every evaluation check. Both metrics are needed to assess this adaptation. References Audibert et al. (2010) Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Proceedings of the 23rd Annual Conference on Learning Theory, p. 41–53, 2010. Bubeck et al. (2011) Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12:1655–1695, 2011. Bubeck et al. (2013) Sébastien Bubeck, Tengyao Wang, and Nitin Viswanathan. Multiple identifications in multi-armed bandits. In International Conference on Machine Learning, p. 258–265. PMLR, 2013. Chen et al. (2017) Lijie Chen, Jian Li, and Mingda Qiao. Towards instance optimal bounds for best arm identification. In Conference on Learning Theory, p. 535–592. PMLR, 2017. Cheng et al. (2023) Ching-An Cheng, Andrey Kolobov, Dipendra Misra, Allen Nie, and Adith Swaminathan. LLF-Bench: Benchmark for interactive learning from language feedback. arXiv preprint arXiv:2312.06853, 2023. DeepSeek-AI (2026) DeepSeek-AI. DeepSeek-V4: Towards highly efficient million-token context intelligence. arXiv preprint arXiv:2606.19348, 2026. Kalyanakrishnan et al. (2012) Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC subset selection in stochastic multi-armed bandits. In Proceedings of the Twenty-ninth International Conference on Machine Learning, p. 655–662, 2012. Karnin et al. (2013) Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, p. 1238–1246. PMLR, 2013. Katz-Samuels & Scott (2018) Julian Katz-Samuels and Clay Scott. Feasible arm identification. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, p. 2535–2543. PMLR, 2018. Katz-Samuels & Scott (2019) Julian Katz-Samuels and Clayton Scott. Top feasible arm identification. In The 22nd International Conference on Artificial Intelligence and Statistics, p. 1593–1601. PMLR, 2019. Kleinberg et al. (2019) Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM, 66(4):30:1–30:77, 2019. Krishnamurthy et al. (2024) Akshay Krishnamurthy, Keegan Harris, Dylan J. Foster, Cyril Zhang, and Aleksandrs Slivkins. Can large language models explore in-context? In Advances in Neural Information Processing Systems, volume 37, p. 120124–120158, 2024. Li & Zhu (2024) Renyuan Li and Shenglong Zhu. Playing Mastermind with Wordle-like feedback. The American Mathematical Monthly, 131(5):390–399, 2024. Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-Refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems, volume 36, 2023. Misra et al. (2024) Dipendra Misra, Aldo Pacchiano, and Robert E. Schapire. Provable interactive learning with hindsight instruction feedback. In Proceedings of the 41st International Conference on Machine Learning, p. 35829–35850, 2024. Shao et al. (2026) Jie-Jing Shao, Bo-Wen Zhang, Xiao-Wen Yang, Bai-Zhi Chen, Si-Yu Han, Jing-Hao Pang, Wen-Da Wei, Guohao Cai, Zhenhua Dong, Lan-Zhe Guo, and Yu-Feng Li. ChinaTravel: An open-ended travel planning benchmark with compositional constraint validation for language agents. In The Fourteenth International Conference on Learning Representations, 2026. Shinn et al. (2023) Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems, volume 36, 2023. Slivkins (2019) Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1–286, 2019. Xie et al. (2024) Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. TravelPlanner: A benchmark for real-world planning with language agents. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, p. 54590–54613. PMLR, 2024. Xu et al. (2025) Wanqiao Xu, Allen Nie, Ruijie Zheng, Aditya Modi, Adith Swaminathan, and Ching-An Cheng. Provably learning from language feedback. arXiv preprint arXiv:2506.10341, 2025. Yang et al. (2025) An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025. Yao et al. (2024) Shunyu Yao, Howard Chen, Austin W. Hanjie, Runzhe Yang, and Karthik R Narasimhan. COLLIE: Systematic construction of constrained text generation tasks. In The Twelfth International Conference on Learning Representations, 2024. Yuksekgonul et al. (2025) Mert Yuksekgonul, Federico Bianchi, Joseph Boen, Sheng Liu, Pan Lu, Zhi Huang, Carlos Guestrin, and James Zou. Optimizing generative AI by backpropagating language model feedback. Nature, 639(8055):609–616, 2025. Zhang et al. (2024) Yizhe Zhang, Jiarui Lu, and Navdeep Jaitly. Probing the multi-turn planning capabilities of LLMs via 20 question games. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 1495–1516. Association for Computational Linguistics, 2024. Zhou et al. (2024) Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language Agent Tree Search unifies reasoning, acting, and planning in language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235, p. 62138–62160, 2024. Appendix A Related Work Learning from language feedback. The emerging language-feedback learning paradigm is tightly coupled with the rapid progress of language models. A first line of work treats natural-language feedback as a verbal reinforcement signal at inference time: Reflexion (Shinn et al., 2023) maintains a self-reflective memory across trials, Self-Refine (Madaan et al., 2023) iteratively edits an output using its own critiques, and TextGrad (Yuksekgonul et al., 2025) performs gradient-like updates over prompt tokens guided by language feedback. Tree-based agents such as LATS (Zhou et al., 2024) additionally search over reasoning steps, but rely on numeric value estimates rather than constraint signals. A complementary line studies whether large language models can themselves explore in interactive settings (Krishnamurthy et al., 2024), and a separate body of work develops constraint-rich language tasks that motivate our setup, including LLF-Bench (Cheng et al., 2023), COLLIE (Yao et al., 2024), ChinaTravel (Shao et al., 2026), and TravelPlanner (Xie et al., 2024). Two recent works establish formal guarantees for language-feedback learning under different formalisms: Misra et al. (2024) give T T-regret bounds under hindsight instruction feedback, and HELiX (Xu et al., 2025) studies consistency-based elimination over a global hypothesis class. Our focus is orthogonal: we model a constraint-bearing regime where feedback provides local falsification and optional atomic identity evidence, and the algorithmic state is a partially committed constraint set rather than a full global hypothesis. Pure exploration and identification problems. Our analysis belongs to the pure-exploration tradition in stochastic decision making, where the goal is to cover or identify a target object with high probability rather than to minimize cumulative reward. Best-arm identification under the fixed-budget setting was introduced by Audibert et al. (2010), with subsequent work establishing matching upper and lower bounds via sequential halving and multi-sample concentration arguments (Karnin et al., 2013; Chen et al., 2017). Among extensions, PAC top-K best-arm identification (Kalyanakrishnan et al., 2012; Bubeck et al., 2013) and feasible-arms identification (Katz-Samuels & Scott, 2018; Katz-Samuels & Scott, 2019) share with our setting the goal of recovering a set-like target from a finite candidate class. We extend this perspective to language-feedback learning along two axes: progress comes from gap-dependent falsification of candidate constraint sets rather than reward concentration on individual arms, and identity-bearing feedback can propose atomic constraints that must still be tested before commitment. More broadly related are bandit problems over structured action spaces with numeric rewards (Slivkins, 2019; Bubeck et al., 2011; Kleinberg et al., 2019). Appendix B Complete Theoretical Analysis This appendix provides the complete theoretical analysis for constraint tree exploration. Section B.1 restates the assumptions used by the proofs. Section B.3 gives an exact-gap survival lemma and a safe-commitment lemma shared by both coverage proofs. Section B.4 analyzes an idealized sound-proposer regime. Section B.5 restates Theorem 2 in full as Theorem 7 and proves it for TRACE-F. Section B.6 restates Theorem 3 in full as Theorem 9 and proves it for TRACE-I. Section B.7 records an anytime gap-UCB bound derived from the same survival argument. B.1 Assumptions We use the notation from Section 2. In particular, each tree node v is associated with a constraint set CvC_v, feasible region v=Region⁡(Cv)X_v=Region(C_v), node value U⁡(v):=maxx∈v⁡U⁡(x)U(v):= _x _vU(x), and node gap Δ⁡(v):=U∗−U⁡(v) (v):=U^*-U(v). We write Viol⁡(f,Cv)=1Viol(f;C_v)=1 when the detector concludes that feedback f contradicts at least one constraint in the tested set CvC_v; feedback about a missing but uncommitted constraint does not fire this predicate. The assumptions below also require a refutational feedback condition: if a tested committed set excludes all optima, feedback must contradict that set with positive probability. We write ℋH for the finite candidate class used by the proposer. Throughout, we assume K≥1K≥ 1; if K=0K=0, then Region⁡(C∗)=Region(C^*)=X and the root already satisfies the coverage target. Oracle-level noise model. The raw message f∼Pxf P_x may be stochastic, but the analysis imposes reliability conditions on the oracle outputs: the firing probability of ViolViol and the extraction probability of ExtractExtract. The theoretical model allows false negatives but rules out false positives. This one-sided noise model supports the multi-sample falsification argument, while Section 5.4 empirically evaluates robustness to spurious extracted identities. Assumption 3 (Refutational feedback and extraction). For any node v for which QCvQ_C_v is defined, let qv:=Pr[Viol(f;Cv)=1|x∼QCv,f∼Px].q_v:= \! [Viol(f;C_v)=1\, |\,x Q_C_v,\ f P_x ]. There exist constants cfal>0c_fal>0 and β>0β>0 such that qv=0ifΔ⁡(v)=0,qv≥ϕ⁡(Δ⁡(v)):=min⁡1,cfalΔ(v)βifΔ⁡(v)>0.q_v=0 (v)=0, q_v≥φ( (v)):= \! \1,\,c_fal (v)^β \ (v)>0. The equality qv=0q_v=0 is the no-false-alarm side of the detector contract. The lower bound for Δ⁡(v)>0 (v)>0 is an additional refutation-power assumption on the feedback distribution: a bad tested region must produce feedback that contradicts some committed constraint with probability controlled by its gap. Without this assumption, a user who only mentions missing uncommitted requirements could leave a bad committed constraint unfalsified. Without loss of generality, cfal≤1c_fal≤ 1: replacing cfalc_fal by min⁡cfal,1 \c_fal,1\ preserves this condition, and the normalization lets the rounding in mexpm_exp be absorbed into the ⁡(⋅)O(·) budget bounds below. We call this condition on qvq_v the refutational-feedback condition. Every result in this appendix except Theorem 9 uses only this condition; the extraction clauses (a)–(b) below are needed only in the identification setting, and TRACE-F uses a null extractor. In the identification setting, the extractor Extract:ℱ→ℋ∪∅Extract:F ∪\ \ satisfies the following two conditions. (a) Extraction reliability. Conditional on the event Viol⁡(ft,Cv)=1Viol(f_t;C_v)=1 for the constraint set currently being tested, the extractor returns a violated canonical constraint with probability at least pext>0p_ext>0, independently across rounds. It returns ∅ otherwise. (b) Soundness. If Extract⁡(ft)=c≠∅Extract(f_t)=c≠ , then c∈C∗c∈ C^* and Sat⁡(xt,c)=0Sat(x_t,c)=0. In particular, extraction never returns a spurious constraint. Assumption 4 (Constrained generation). For every constraint set C considered by the algorithm with nonempty feasible region, there exists a distribution QCQ_C supported on Region⁡(C)=x∈:Sat⁡(x,c)=1∀c∈CRegion(C)=\x :Sat(x,c)=1\ ∀ c∈ C\. Each call to QCQ_C returns an independent sample. Assumption 5 (Sound proposer). The proposer ProposePropose is a possibly randomized map from nodes to ℋ∪∅H∪\ \ satisfying: (a) Completeness. If Cv⊊C∗C_v C^*, then Propose⁡(v)∈C∗∖CvPropose(v)∈ C^* C_v. (b) Termination marker. If Cv=C∗C_v=C^*, then Propose⁡(v)=∅Propose(v)= . Assumption 5 is an idealization. It is useful as a warm-up because it isolates the role of tree depth and within-node spread. The main robust analysis below replaces it with a noisy proposer. Assumption 6 (Candidate class and noisy proposer). The finite canonical constraint class ℋH from Section 2.1 satisfies C∗⊆ℋC^* and |ℋ|=H≥K|H|=H≥ K. For every C⊆ℋC with nonempty feasible region, the generator QCQ_C is defined as in Assumption 4. At each proposal call from node v, the proposer returns an element of ℋv=ℋ∖(Cv∪Rv)H_v=H (C_v∪ R_v) sampled uniformly at random, independently of the past given (v,Rv)(v,R_v), where RvR_v is the per-node lazy filter of Algorithm 1. If ℋv=∅H_v= , it returns ∅ . Remark 1 (Per-node lazy filter). The set RvR_v in Algorithm 1 records the candidates that gave an empty region or were rejected at v; it starts empty at each node, and proposals are drawn from ℋv=ℋ∖(Cv∪Rv)H_v=H (C_v∪ R_v). At a viable node, a missing true constraint never enters RvR_v: its child contains a global optimum, so the region is nonempty and, by Assumption 3, the child is never falsified (a test cut short by budget exhaustion also adds its candidate to RvR_v, but ends the run). Hence missing true constraints remain available at viable nodes, which is what the proofs of Theorems 7 and 9 use. Since each proposal at v either enters RvR_v or is committed, at most |ℋ∖Cv|+1|H C_v|+1 proposal calls occur at each node, so Algorithm 1 terminates. Assumption 7 (ε -separated spurious children). Fix ε∈(0,1] ∈(0,1]. For every viable node v (i.e., Δ⁡(v)=0 (v)=0) and every c∈ℋ∖Cvc C_v whose child u=v∪cu=v∪\c\ has a nonempty feasible region uX_u, this child satisfies either Δ⁡(u)=0 (u)=0 (it preserves a global optimum) or Δ⁡(u)>ε (u)> (it excludes every optimum; we call such a child ε -spurious). Assumption 7 is a structural condition on (,U,ℋ,C∗)(X,U,H,C^*), not on the generator QCQ_C, detector ViolViol, extractor ExtractExtract, or proposer ProposePropose. It plays the role of a sub-optimality gap: without it, children with arbitrarily small but positive Δ⁡(u) (u) would require unboundedly many samples to falsify. The gap Δ⁡(u) (u) is defined only when u≠∅X_u≠ . Children with empty regions are never tested by Algorithm 1, so Assumptions 7 and 8 impose no condition on them. Assumption 8 (No zero-gap distractors). For the identification-setting analysis, every c∈ℋ∖C∗c C^* with Region⁡(c)≠∅Region(c)≠ satisfies Δ⁡(c)>ε (\c\)> ; that is, imposing c alone already excludes every global optimum with margin ε . Assumption 8 is the structural condition used by Theorem 9. It extends to every viable node v: a true constraint gives a child that keeps the optimum of v, while for c∉C∗c∉ C^* with a nonempty child, Region⁡(Cv∪c)⊆Region⁡(c)Region(C_v∪\c\) (c) gives Δ⁡(v∪c)≥Δ⁡(c)>ε (v∪\c\)≥ (\c\)> . Hence it implies Assumption 7, and, since K≥1K≥ 1 makes the root such a node, it is equivalent to requiring the same property at every viable node that does not yet contain C∗C^*. It depends only on (,U,ℋ,C∗)(X,U,H,C^*), and extractor reliability cannot ensure it; without it, an identification-aware proposer could spend budget committing harmless but non-informative constraints, reintroducing dependence on their number. The extraction progress used by Theorem 9 follows from Assumption 3(a)–(b). Suppose a test of a child u of a viable node v starts with working set Wstart⊆CvW_start C_v and ends with a violation. Conditional on the history and on u, the rounds of the test are independent, so the feedback at the first violation has the one-round law conditional on a violation, and by (a) the extractor then returns a constraint with probability at least pextp_ext. By (b) this constraint lies in C∗C^* and is violated by the sampled action, which satisfies CuC_u; hence it lies in C∗∖Cu⊆C∗∖(Cv∪Wstart)C^* C_u C^* (C_v∪ W_start), so |Cv∪W||C_v∪ W| has increased during the test, at this round or at an earlier round that returned the same constraint. No independence between different tests is needed. The same conditions restrict the instances covered by Theorem 9: together with Assumption 3, Assumption 8 forces Region⁡(c)∩Region⁡(C∗)=∅Region(c) (C^*)= for every c∈ℋ∖C∗c C^*. Otherwise the node D=C∗∪cD=C^*∪\c\ is nonempty with Δ⁡(D)≥Δ⁡(c)>ε (D)≥ (\c\)> , so the refutational-feedback condition gives qD>0q_D>0; but every action in Region⁡(D)Region(D) satisfies all true constraints, so by (b) no extraction can succeed at D, contradicting (a). The identification guarantee therefore applies when every incorrect candidate is incompatible with the true requirements, as for wrong values of single-valued attributes; Theorem 7 does not use (a)–(b) and is unaffected. B.2 Algorithmic remarks The remarks in this subsection record operational properties of Algorithm 1 that are referenced from the main text. They are not used in any proof. Remark 2 (Working-set persistence and bounded growth). The working set W in Algorithm 1 is initialized once and updated only by union; it is never cleared. Four observations characterize its behavior. (a) |W|≤H|W|≤ H since W⊆ℋW . (b) The identification proposer reads W∩ℋvW _v rather than W directly, so already-committed and already-excluded constraints are filtered at proposal time. (c) Under sound extraction (Assumption 3(b)), every c∈Wc∈ W is a true latent constraint; once proposed at a viable node v, the resulting child has Δ=0 =0, is never falsified by the no-false-alarm clause of Assumption 3, and is committed at the end of its mexpm_exp-round test window whenever the remaining budget covers that window. (d) Under empirically unsound extraction, false entries in W may be repeatedly proposed. Proposing such an entry at a viable node yields an empty child, which is excluded without a test, a zero-gap child, which may be committed but still contains a global optimum, or, by Assumption 7, a child with Δ>ε > . Lemma 5 allows any history-dependent proposer, so with mexpm_exp as in Theorems 7 and 9 and a detector that still satisfies the refutational-feedback condition, no child with positive gap is committed with probability at least 1−δ/21-δ/2; false entries then cost test budget while the committed node remains viable. This controls harmful commitments only; the K/pextK/p_ext guarantee of Theorem 9 additionally requires sound extraction and Assumption 8. This is the algorithmic backing for the false-identity robustness check in Section 5.4. Combined with the per-node lazy filter (Remark 1), TRACE-I cannot loop on a spurious extracted identity once it has been falsified at v: the lazy filter excludes it from subsequent proposals at the same node. Remark 3 (Detector contract, operational reading). Per Assumption 3, ViolViol is used only for falsification: feedback that reveals a missing requirement may update W via ExtractExtract, but does not reject the tested child unless it contradicts a constraint already in CuC_u. Equivalently, the detector fires on contradictions with the tested set, never on discovery feedback alone. As an illustration, if Cu=genre=comedyC_u=\genre=comedy\, then “I did not want a comedy” contradicts CuC_u and fires ViolViol, whereas “I also wanted something from the 1990s” is discovery feedback and must not fire ViolViol. Remark 4 (Counters in Algorithm 1). The variable t is the global interaction-round counter running against the budget T; the inner-loop index s counts tests of the current child running against the per-child cap mexpm_exp. The two counters are independent: s resets on each new child while t is monotone over the entire run. Both caps are needed because the algorithm enforces a global budget T via t and a per-child test window mexpm_exp via s. B.3 Basic lemmas Lemma 4 (Multi-sample falsification, exact-gap form; implies Lemma 1). Let v be a node for which QCvQ_C_v is defined, and let xs∼QCvx_s Q_C_v and fs∼Pxsf_s P_x_s for m independent rounds. Then Pr[Viol(fs;Cv)=0for all s=1,…,m]=(1−qv)m≤exp(−mcfalΔ(v)β). \! [Viol(f_s;C_v)=0\ for all s=1,…,m ]=(1-q_v)^m≤ \! (-mc_fal (v)^β ). In particular, a node with Δ⁡(v)>ε (v)> survives m tests with probability at most exp⁡(−mcfalεβ) (-mc_fal ^β), which is at most δ′δ when m≥log⁡(1/δ′)/(cfalεβ)m≥ (1/δ )/(c_fal ^β). Proof. Since cfal≤1c_fal≤ 1 and Δ⁡(v)≤1 (v)≤ 1, we have cfalΔ(v)β≤1c_fal (v)^β≤ 1, so Assumption 3 gives qv≥cfalΔ(v)βq_v≥ c_fal (v)^β, also when Δ⁡(v)=0 (v)=0. The rounds are independent by Assumption 4, and 1−y≤e−y1-y≤ e^-y gives the bound. ∎ Lemma 5 (Safe commitments). Suppose the refutational-feedback condition of Assumption 3 and Assumptions 4 and 7 hold. Run Algorithm 1 with any history-dependent proposer, test length m, at most N tests, and T=NmT=Nm. Then each test has a complete window of m rounds, and the probability that some child with Δ>0 >0 is committed is at most Nexp⁡(−mcfalεβ)N (-mc_fal ^β). Proof. The n-th test starts after at most (n−1)m(n-1)m rounds, so it has m rounds available, and a child is committed only after m violation-free rounds. Before the first commitment of a child with Δ>0 >0, every committed node is viable, so by Assumption 7 the child tested at that moment has Δ>ε > . Conditional on the history and the proposed child, the test rounds are fresh independent samples, so Lemma 4 bounds its acceptance probability by exp⁡(−mcfalεβ) (-mc_fal ^β). A union bound over the at most N tests at which this first commitment can occur gives the claim. ∎ B.4 Idealized sound-proposer regime We first analyze an idealized regime in which proposed constraints are always true. This result is mainly a warm-up: it shows that once proposals are sound, constraint-tree depth alone is enough to reach the latent feasible region. Theorem 6 (Coverage under a sound proposer). Suppose the refutational-feedback condition of Assumption 3 holds, together with Assumptions 4 and 5. Consider the idealized variant of TRACE that tests the current node for mexp≥1m_exp≥ 1 rounds and then calls ProposePropose whenever the node survives those rounds without falsification. If the budget satisfies T≥KmexpT≥ Km_exp, then with probability one the procedure reaches a node v with Cv=C∗C_v=C^*. Consequently, if x^∼QCv x Q_C_v, then x^∈Region⁡(C∗) x (C^*) and U⁡(x^)≥U∗−Spread⁡(C∗)U( x)≥ U^*-Spread(C^*). Proof. We argue by induction over the committed path. Initially, the root satisfies Cv0=∅⊆C∗C_v_0= C^*. Suppose the current node v satisfies Cv⊆C∗C_v C^*. Since x∗∈Region⁡(Cv)x^* (C_v), we have U⁡(v)=U∗U(v)=U^* and therefore Δ⁡(v)=0 (v)=0. By the no-false-alarm part of Assumption 3, the node is never falsified: qv=0q_v=0. Thus the node survives any test window of length mexpm_exp. If Cv⊊C∗C_v C^*, then by Assumption 5 the proposer returns a constraint c∈C∗∖Cvc∈ C^* C_v. The algorithm moves to the child u with Cu=Cv∪cC_u=C_v∪\c\. This child also satisfies Cu⊆C∗C_u C^* and has depth one larger than v. Therefore, each successful expand step strictly increases |Cv||C_v| while preserving the invariant Cv⊆C∗C_v C^*. After at most K such expansions, the committed node satisfies Cv=C∗C_v=C^*. Each expansion consumes exactly mexpm_exp test rounds, so the budget T≥KmexpT≥ Km_exp suffices. Finally, by the support property of QCvQ_C_v, x^∼QCv x Q_C_v implies x^∈Region⁡(C∗) x (C^*). By the definition of Spread⁡(C∗)Spread(C^*), U⁡(x^)≥U∗−Spread⁡(C∗)U( x)≥ U^*-Spread(C^*). ∎ B.5 Noisy-proposer regime We now analyze the robust test-before-commit algorithm under a noisy proposer. This is the main theoretical setting used in the paper. Theorem 7 (Coverage in the falsification setting; full version of Theorem 2). Suppose the refutational-feedback condition of Assumption 3 holds (its extraction clauses (a)–(b) are not needed), together with Assumptions 4, 6, and 7. Fix δ∈(0,1)δ∈(0,1) and ε∈(0,1] ∈(0,1]. If Nmax:=⌈Hlog⁡2max⁡(K,1)δ⌉,mexp:=⌈log⁡(2Nmax/δ)cfalεβ⌉,T:=Nmaxmexp,N_ := H 2 (K,1)δ , m_exp:= (2N_ /δ)c_fal ^β , T:=N_ m_exp, then with probability at least 1−δ1-δ the deepest committed node v satisfies Region⁡(Cv)⊆Region⁡(C∗)Region(C_v) (C^*). In the canonical finite-class proof, this region inclusion is obtained through the sufficient event Cv⊇C∗C_v C^*; the committed set may also include additional zero-gap constraints from ℋ∖C∗H C^*. Hence, if x^∼QCv x Q_C_v, then x^∈Region⁡(C∗) x (C^*) and U⁡(x^)≥U∗−Spread⁡(C∗)U( x)≥ U^*-Spread(C^*). With LF:=log⁡(2K/δ)L_F:= (2K/δ), the total interaction budget is T=⁡(HLFlog⁡(4HLF/δ)cfalεβ).T=O\! ( HL_F (4HL_F/δ)c_fal ^β ). Proof. Write N:=NmaxN:=N_ and m:=mexpm:=m_exp, and let ℬB be the event that a child with Δ>0 >0 is committed. By Lemma 5 and the choice of m, Pr⁡(ℬ)≤Nexp⁡(−mcfalεβ)≤δ/2 (B)≤ N (-mc_fal ^β)≤δ/2. Index the proposal calls, including those whose candidate gives an empty region, and let ℱjF_j be the history after j calls and their tests. Fix c∈C∗c∈ C^*, and let Aj,cA_j,c be the event that no child with Δ>0 >0 has been committed during the first j calls and c is still uncommitted after them. On Aj,cA_j,c the committed node v is viable, so its region contains a global optimum, which satisfies c; hence the child v∪cv∪\c\ is nonempty with Δ=0 =0, and c∈ℋvc _v by Remark 1. For j<Nj<N, at most j tests and jmjm rounds have been used, so the next call takes place and any test it triggers has a complete window. This call proposes c with conditional probability 1/|ℋv|≥1/H1/|H_v|≥ 1/H, and the resulting child then passes and is committed. Hence Pr(Aj+1,c∣ℱj)≤(1−1H)Aj,c,soPr(AN,c)≤(1−1H)N≤e−N/H. (A_j+1,c _j)≤ (1- 1H )1_A_j,c, (A_N,c)≤ (1- 1H )^N≤ e^-N/H. If ℬB does not occur but some c∈C∗c∈ C^* is never committed, the run makes at least N calls, since a viable run that misses a true constraint cannot stop earlier, and therefore AN,cA_N,c occurs. By the choice of N, Pr(C∗⊈Cv)≤Pr(ℬ)+∑c∈C∗Pr(AN,c)≤δ2+Ke−N/H≤δ. (C^* C_v)≤ (B)+ _c∈ C^* (A_N,c)≤ δ2+Ke^-N/H≤δ. On the complement, Cv⊇C∗C_v C^*, so Region⁡(Cv)⊆Region⁡(C∗)Region(C_v) (C^*); the support of QCvQ_C_v gives x^∈Region⁡(C∗) x (C^*), and the definition of Spread⁡(C∗)Spread(C^*) gives U⁡(x^)≥U∗−Spread⁡(C∗)U( x)≥ U^*-Spread(C^*). Each of the at most N tests uses at most m rounds, so T=NmT=Nm suffices. ∎ Corollary 8 (Expected simple regret). Under the setting of Theorem 7, the expected simple regret satisfies ⁡[rT]≤Spread⁡(C∗)+δ.E[r_T] (C^*)+δ. Proof. Let E be the success event in Theorem 7. Then Pr⁡(E)≥1−δ (E)≥ 1-δ. On E, the output satisfies rT=U∗−U⁡(x^)≤Spread⁡(C∗)r_T=U^*-U( x) (C^*). On EcE^c, since U∈[0,1]U∈[0,1], we have rT≤1r_T≤ 1. Therefore ⁡[rT]≤(1−δ)Spread(C∗)+δ⋅1≤Spread⁡(C∗)+δ.E[r_T]≤(1-δ)Spread(C^*)+δ· 1 (C^*)+δ. ∎ B.6 Identification setting This section analyzes TRACE-I, which augments the falsification-setting test-before-commit core with an identification-aware proposer that biases its candidates toward constraints extracted from past feedback. Identification-aware proposer. The proposer maintains a running set Wt⊆ℋW_t initialized to ∅ . After every round in which Extract⁡(ft)=c≠∅Extract(f_t)=c≠ , it updates Wt+1←Wt∪cW_t+1← W_t∪\c\, matching Line 10 of Algorithm 1; under the soundness clause of Assumption 3, every such c lies in C∗C^*, so the update is sound regardless of whether Viol⁡(ft,C)=1Viol(f_t;C)=1 also fires, and the discovery argument below only uses the subset of these updates that occur on rounds with Viol⁡(ft,C)=1Viol(f_t;C)=1. At each proposal call from node v, it returns a uniform random element of Wt∩ℋvW_t _v when this set is nonempty, and a uniform random element of ℋvH_v otherwise, with ℋv=ℋ∖(Cv∪Rv)H_v=H (C_v∪ R_v) as in Algorithm 1; it returns ∅ if ℋv=∅H_v= . Theorem 9 (Coverage in the identification setting; full version of Theorem 3). Suppose Assumptions 3, 4, and 8 hold (in particular C∗⊆ℋC^* ; Assumption 8 implies Assumption 7). Fix δ∈(0,1)δ∈(0,1) and ε∈(0,1] ∈(0,1]. With Nmaxid:=⌈64pext(K+log⁡4δ)⌉,mexpid:=⌈log⁡(2Nmaxid/δ)cfalεβ⌉,T:=Nmaxidmexpid,N_ ^id:= 64p_ext (K+ 4δ ) , m_exp^id:= (2N_ ^id/δ)c_fal ^β , T:=N_ ^idm_exp^id, TRACE-Identification enjoys an (ε,δ)( ,δ)-coverage guarantee: with probability at least 1−δ1-δ, the deepest committed node v satisfies Region⁡(Cv)⊆Region⁡(C∗)Region(C_v) (C^*). In the canonical proof this follows from the sufficient event Cv⊇C∗C_v C^*. Consequently, if x^∼QCv x Q_C_v, then x^∈Region⁡(C∗) x (C^*) and U⁡(x^)≥U∗−Spread⁡(C∗)U( x)≥ U^*-Spread(C^*). With LI:=K+log⁡(4/δ)L_I:=K+ (4/δ), the total interaction budget is T=⁡(LIlog⁡(4LI/(pextδ))pextcfalεβ)=~(Kpextcfalεβ).T=O\! ( L_I (4L_I/(p_extδ))p_ext\,c_fal ^β )= O\! ( Kp_ext\,c_fal ^β ). Proof. Let N:=NmaxidN:=N_ ^id, m:=mexpidm:=m_exp^id, and p:=pextp:=p_ext. Assumption 8 implies Assumption 7, so by Lemma 5 and the choice of m, with probability at least 1−δ/21-δ/2 no child with Δ>0 >0 is committed during the first N tests, and each of these tests has a complete window. Call recovery the first time at which C∗⊆CvC^* C_v. Before recovery and before any child with Δ>0 >0 is committed, every committed node is viable and, by Assumption 8, every committed constraint is true, so Cv⊆C∗C_v C^*; soundness gives Wt⊆C∗W_t C^*. We track the potential Ψ:=|Cv|+|Cv∪Wt|≤2K, :=|C_v|+|C_v∪ W_t|≤ 2K, which never decreases and gains one unit when a true constraint is discovered and one unit when it is committed. Consider a test in this period. A prioritized test proposes a constraint of Wt∩ℋv⊆C∗∖CvW_t _v C^* C_v, which is committed, so Ψ increases. Otherwise Wt∩ℋv=∅W_t _v= , which at a viable node means Wt⊆CvW_t C_v, because missing true constraints never enter RvR_v (Remark 1). A fallback proposal in C∗C^* is then committed and increases Ψ by two. A fallback proposal outside C∗C^* is either committed, which is a commitment with Δ>0 >0, or rejected after a violation; in the latter case, with conditional probability at least p, the extractor returns a true constraint that is new relative to the working set at the start of the test, so Ψ increases during this test (see the discussion after Assumption 8). Hence, given the history, each such test increases Ψ or commits a child with Δ>0 >0 with probability at least p. For n≤Nn≤ N, let Yn:=1Y_n:=1 if the n-th test increases Ψ or commits a child with Δ>0 >0, and let Yn:=1Y_n:=1 if this test starts after recovery or after such a commitment, or does not take place. Before these events the run does not stop within N tests: a missing true constraint stays in ℋvH_v, and the budget covers N complete windows. Therefore Pr⁡(Yn=1∣ℱn−1)≥p (Y_n=1 _n-1)≥ p for the history ℱn−1F_n-1 before the n-th test, and the tower property gives [exp(−λ∑n=1NYn)]≤(1−p+pe−λ)Nfor every λ>0.E [ (-λ _n=1^NY_n ) ]≤ (1-p+pe^-λ )^N every λ>0. Since Np≥64(K+log⁡(4/δ))Np≥ 64(K+ (4/δ)), we have 2K≤Np/22K≤ Np/2 and e−Np/8≤δ/2e^-Np/8≤δ/2, so the multiplicative Chernoff lower-tail bound gives Pr[∑n=1NYn<2K]≤δ/2 [ _n=1^NY_n<2K]≤δ/2. If recovery does not occur within the first N tests and no child with Δ>0 >0 is committed, then every Yn=1Y_n=1 records an increase of Ψ , which starts at 00 and stays at most 2K−12K-1 because |Cv|≤K−1|C_v|≤ K-1; hence ∑n=1NYn<2K _n=1^NY_n<2K. Therefore recovery occurs within the first N tests, and thus within T=NmT=Nm rounds, with probability at least 1−δ1-δ. Later commitments only add constraints, so at termination Cv⊇C∗C_v C^* and Region⁡(Cv)⊆Region⁡(C∗)Region(C_v) (C^*); the support of QCvQ_C_v and the definition of Spread⁡(C∗)Spread(C^*) give the remaining claims, as in Corollary 8. ∎ B.7 Anytime gap-UCB bound The survival argument also yields an anytime confidence bound on the gap of a tested node. It is not needed for Theorems 7 and 9, but it reads the test of Algorithm 1 as a confidence rule. Lemma 10 (Anytime gap upper confidence bound). Fix a node v for which QCvQ_C_v is defined, and consider an independent sequence of rounds at v. For m≥1m≥ 1, let Am:=Viol(fs;Cv)=0for all 1≤s≤mA_m:=\Viol(f_s;C_v)=0\ for all 1≤ s≤ m\ be the event that the first m rounds at v produce no violation signal. For δ∈(0,1)δ∈(0,1), define Δ^UCB(v,m,δ):=(log⁡(1/δ)cfalm)1/β. _UCB(v;m,δ):= ( (1/δ)c_falm )^1/β. Then, with probability at least 1−δ1-δ, Δ⁡(v)≤Δ^UCB(v,m,δ) (v)≤ _UCB(v;m,δ) holds simultaneously for every m≥1m≥ 1 such that AmA_m occurs. The events AmA_m concern the initial violation-free prefix; violation-free runs that restart after a violation are not covered, since each restart would require additional confidence. Proof. If Δ⁡(v)=0 (v)=0 there is nothing to prove. Otherwise let a:=cfalΔ(v)βa:=c_fal (v)^β. Lemma 4 gives Pr⁡(Am)≤e−ma (A_m)≤ e^-ma. The radius decreases in m, and Δ⁡(v)>Δ^UCB(v,m,δ) (v)> _UCB(v;m,δ) holds exactly when m≥m∗:=⌊log⁡(1/δ)/a⌋+1m≥ m_*:= (1/δ)/a +1. Because Am+1⊆AmA_m+1 A_m, the failure event ∃m≥1:Am occurs and Δ(v)>Δ^UCB(v,m,δ)\∃ m≥ 1:A_m occurs and (v)> _UCB(v;m,δ)\ equals Am∗A_m_*, whose probability is at most e−m∗a<δe^-m_*a<δ. ∎ Interpretation. The bound in Lemma 10 is the gap-dependent analogue of a UCB confidence radius. Because the prefix events are nested, no union bound over m is needed, and for fixed δ the radius decays as (m−1/β)O(m^-1/β) without a logarithmic factor in m; larger β corresponds to a more ambiguous feedback channel and slower decay. Remark 5 (Anytime reading of the test in Algorithm 1). Accepting a child once Δ^UCB(v,m,δ)≤ε _UCB(v;m,δ)≤ and rejecting it at the first violation is exactly the test of Algorithm 1: the radius depends on the data only through survival, so acceptance happens after the fixed window ⌈log⁡(1/δ)/(cfalεβ)⌉ (1/δ)/(c_fal ^β) , which equals mexpm_exp when δ is replaced by δ/(2Nmax)δ/(2N_ ). Lemma 10 therefore certifies, at every round of a test, how large the gap of a surviving child can still be. Appendix C Additional Experimental Details This appendix provides the full experimental details omitted from the main text. Section C.1 describes the environments and implementation choices. Section C.2 reports the three remaining task instances of the main comparison and Wilson confidence intervals for the main success-rate tables. Section C.3 gives the RecMovie ablations, robustness checks, and equal-output-budget comparisons. Section C.4 covers 20Q, EDA, Mastermind, and Poem. Section C.5 gives an example execution trace, and Section C.6 lists the prompts of the LLM-based components. C.1 Environment and implementation details Common setup. Unless otherwise noted, TRACE uses mexp=15m_exp=15 and Nmax=15N_ =15. The headline ViolViol and ExtractExtract modules are rule-based: a regex over each environment’s feedback template, with task-specific decoders that map matched phrases to canonical predicates in ℋH. TRACE-Falsification (TRACE-F) uses a uniform proposer; TRACE-Identification (TRACE-I) uses the same decoder to extract identities and prioritize them in the proposer. Qwen3-4B served locally is used for (i) the prompt-based LLM baselines (DirectLLM, Reflexion, Self-Refine), (i) the Qwen3-4B configuration of TravelPlanner’s constrained plan generator QCQ_C in Section 5.5, and (i) the LLM-based ViolViol / ExtractExtract ablations in Tables 12 and 13; these ablations confirm that headline TRACE rows do not rely on LLM oracle modules, since substituting the LLM detector for the rule-based detector drops TRACE-F’s interaction-budget any-success from 57%57\% to 21%21\% on RecMovie. The Mastermind column of the main comparison (Table 6) fixes K=3K=3 and ncolors=6n_colors=6; Haiku targets the 55–77–55 syllable pattern and Tanka the 55–77–55–77–77 pattern. Wilson 95%95\% intervals for all main-table cells are reported in Section C.2; small differences within overlapping intervals should not be over-interpreted. Prompt-based baselines (DirectLLM, Reflexion, Self-Refine) are operational comparisons under a fixed local model, rather than a multi-model robustness study. All reported results use 100100 seeds per cell, except TravelPlanner, which uses 5050 validation queries (Section 5.5). The primary metric is env.success, the fraction of seeds on which a method produces a satisfying output within its interaction budget; for RecMovie TRACE rows this is the final-output success of the algorithm’s converged recommendation list. Section C.3 additionally reports an interaction-budget any-success diagnostic and a soft-utility breakdown. When available, we also report superset⁡(C∗)superset(C^*), which checks whether the committed constraint set contains all true constraints and serves as a sufficient syntactic proxy for region inclusion. Compute resources. All experiments were run on a local workstation with a single NVIDIA GeForce RTX 5080 GPU. LLM-based baselines, the TravelPlanner plan generator QCQ_C, and the LLM-based ViolViol / ExtractExtract ablation rows used Qwen3-4B on this workstation, and the DeepSeek-V4-Flash configuration of TravelPlanner called the DeepSeek API; headline TRACE runs and the remaining environment simulation, rule-based decoding, and tabulation code ran on CPU. LLM baselines. LLM baselines use Qwen3-4B. We compare against DirectLLM, Reflexion (Shinn et al., 2023), and Self-Refine (Madaan et al., 2023). DirectLLM conditions on the full interaction history. Reflexion follows the original trial-based design with sliding-window reflective memory; Self-Refine follows Madaan et al. (2023) with full-history critique-and-revise. RecMovie. Each seed samples a user profile across multiple attribute dimensions (movie type, year range, genre, age restriction); the corresponding latent constraint set C∗C^* collects the dimensions actually set in the profile, so K=|C∗|K=|C^*| varies per seed. On each round, the agent proposes three movie titles, and the environment returns template-based verbal feedback. All LLM baselines run for T=20T=20 total interaction steps on RecMovie; trial-based Reflexion partitions this budget across trials. Across 100100 seeds, the LLM baselines that succeed do so within roughly 33 steps on average (DirectLLM mean 3.73.7, Self-Refine mean 2.92.9), while failed seeds exhaust nearly the full budget. Appendix C.3 compares all methods under common caps of 2020 and 6060 outputs; there, the windowed baseline variants gain 22–1010p from the larger cap. 20Q. 20Q is a controlled synthetic environment with five categorical attribute dimensions yielding |ℋ|=17|H|=17 candidate predicates over a dense ||=432|X|=432-entity catalog (every attribute combination has exactly one entity). Each episode samples a profile inducing C∗C^* whose size K=|C∗|K=|C^*| varies per seed; feedback is templated per dimension, e.g., “the target is not a mammal”. Because the catalog is dense, Region⁡(Cv)Region(C_v) is nonempty for every consistent constraint set CvC_v. EDA Things. We use the 9999-entity test set of Apple’s Entity-Deduction Arena (EDA Things) (Zhang et al., 2024), annotated by us with five categorical attribute dimensions; annotations were initialized by Qwen3-4B and manually corrected. Each episode samples a profile inducing C∗C^* whose size K=|C∗|K=|C^*| varies per seed. The catalog is sparse, so when a committed constraint set yields an empty region, the generator falls back to the entity satisfying the largest number of committed predicates. Mastermind. We use a per-position Mastermind environment, following the Clear Mastermind feedback style (Li & Zhu, 2024). The hidden code has length K, and each position takes one color from a palette of size ncolorsn_colors. Feedback is per-position: each proposed position is marked as “exact”, “present”, or “absent”. The candidate class is ℋ=(i,c):i∈[K],c∈paletteH=\(i,c):i∈[K],\,c \ with |ℋ|=K⋅ncolors|H|=K· n_colors. This environment allows controlled sweeps over both K and |ℋ||H|. LLF-Bench Poem. For LLF-Bench Poem (Cheng et al., 2023), we use the Haiku and Tanka tasks without changing their reward, feedback content, or target pattern. Haiku has target syllable pattern 55–77–55 and thus K=3K=3 line-level constraints. Tanka has target pattern 55–77–55–77–77 and thus K=5K=5 constraints. We apply a runtime patch to the upstream cmudict lookup so that missing words fall back to the existing heuristic syllable estimator; this patch is used only for words outside the CMU dictionary. The generator is a word-bucket generator that samples words from syllable-indexed buckets and composes each line to satisfy a proposed syllable count. The predicate class is ℋ=(linei,sylls):i∈[K],s∈3,4,5,6,7,8H=$line_i,syll_s):i∈[K],\ s∈\3,4,5,6,7,8\\ with |ℋ|=6K|H|=6K. TRACE reads only feedback, not the task prompt, so the target syllable pattern is discovered from the environment replies. K across environments. K=|C∗|K=|C^*| is fixed per experiment in Mastermind (main comparison: K=3K=3, ncolors=6n_colors=6; H-sweep: K=3K=3; K-sweep: K∈2,4,6,8,10K∈\2,4,6,8,10$ and Poem (Haiku: K=3K=3; Tanka: K=5K=5). In RecMovie, 20Q, and EDA Things, K is sampled per seed by the environment’s profile sampler. C.2 Remaining main-comparison tasks and confidence intervals Remaining task instances. For headline focus, Table 1 reports only the three tasks where the falsification-to-identification gap is non-saturated and the lossy-extraction story (RecMovie) is empirically separable. Table 6 records the corresponding natural-feedback main-comparison numbers on the three remaining task instances: Mastermind (K=3K=3, ncolors=6n_colors=6), LLF-Bench Haiku (K=3K=3 syllable constraints), and LLF-Bench Tanka (K=5K=5). TRACE-I reaches 9999–100%100\% on all three; natural-feedback prompt baselines remain below 30%30\%. Wilson 95%95\% intervals are in Table 7 (Mmind / Haiku / Tanka columns). 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 Mastermind Haiku Tanka Random 4% 14\% 7% 17\% 0% 10\% DirectLLM 15%15\% 20%20\% 4% 14\% Reflexion (Shinn et al., 2023) 9% 19\% 2% 12\% 1% 11\% Self-Refine (Madaan et al., 2023) 29%29\% 14%14\% 0% 10\% TRACE-F 54%54\% 54%54\% 14%14\% TRACE-I %99\% %100\% %100\% Wilson confidence intervals. All success rates in the main tables use 100100 seeds per cell, except Table 5 (5050 queries). Tables 7–10 report Wilson 95%95\% confidence intervals rounded to the nearest percentage point. These intervals are intended for interpreting success-rate differences, not for changing the primary point estimates shown in the main text. Table 7: Wilson 95%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. Method Rec. 20Q EDA Mmind Haiku Tanka Random [2,11][2,11] [32,51][32,51] [65,82][65,82] [2,10][2,10] [3,14][3,14] [0,4][0,4] DirectLLM [11,26][11,26] [7,20][7,20] [34,53][34,53] [9,23][9,23] [13,29][13,29] [2,10][2,10] Reflexion [18,35][18,35] [6,19][6,19] [45,64][45,64] [5,16][5,16] [1,7][1,7] [0,5][0,5] Self-Refine [14,30][14,30] [64,81][64,81] [69,85][69,85] [21,39][21,39] [9,22][9,22] [0,4][0,4] TRACE-F [41,61][41,61] [76,90][76,90] [79,92][79,92] [44,63][44,63] [44,63][44,63] [9,22][9,22] TRACE-I [,][83,94] [96,100][96,100] [95,100][95,100] [95,100][95,100] [96,100][96,100] [96,100][96,100] Table 8: Wilson 95%95\% confidence intervals for the Mastermind fixed-K H-sweep in Table 2. Entries are intervals for env.success percentages. ncolorsn_colors |ℋ||H| TRACE-F CI TRACE-I CI 33 99 [96,100][96,100] [96,100][96,100] 66 1818 [96,100][96,100] [96,100][96,100] 1010 3030 [93,99][93,99] [96,100][96,100] 1515 4545 [80,93][80,93] [96,100][96,100] 2020 6060 [65,82][65,82] [95,100][95,100] Table 9: Wilson 95%95\% confidence intervals for the same-decoder structured comparison in Table 4. Entries are intervals for env.success percentages. Configuration RecMovie 20Q EDA Things TRACE-I [,][83,94] [96,100][96,100] [95,100][95,100] Direct-Commit (best variant) [16,32][16,32] [96,100][96,100] [96,100][96,100] Table 10: Wilson 95%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 Rec. 20Q EDA Group A: binary oracle DirectLLM [19,36][19,36] [34,53][34,53] [76,90][76,90] Reflexion [26,45][26,45] [21,39][21,39] [59,77][59,77] Self-Refine [18,35][18,35] [13,28][13,28] [31,50][31,50] TRACE-F [,][41,61] [,][76,90] [,][79,92] Group B: identity oracle DirectLLM [31,50][31,50] [96,100][96,100] [96,100][96,100] Reflexion [33,52][33,52] [96,100][96,100] [96,100][96,100] Self-Refine [24,42][24,42] [96,100][96,100] [96,100][96,100] TRACE-I [,][83,94] [96,100][96,100] [95,100][95,100] C.3 Full RecMovie results Soft-utility breakdown. Table 11 extends the main RecMovie comparison with a soft-utility breakdown of the final recommendation list. The soft utility UfinalU_final of a list is the mean, over its three recommended titles, of the fraction of canonical C∗C^* predicates satisfied by each title; soft regret is 1−Ufinal1-U_final. The final env. column reproduces the headline final-output success used in the main tables. Table 11: RecMovie final-output soft-score / soft-regret over 100100 seeds. UfinalU_final is mean partial-credit utility and 1−Ufinal1-U_final is soft regret. The final env. column matches the headline RecMovie numbers in the main tables. Method final env. UfinalU_final soft regret TRACE-F 51%51\% 0.6410.641 0.3590.359 TRACE-I %90\% 0.8310.831 0.1690.169 Direct-AND 15%15\% 0.4960.496 0.5040.504 Direct-OR 23%23\% 0.5280.528 0.4720.472 Direct-RANKED 22%22\% 0.5270.527 0.4730.473 Random 5% 15\% 0.3280.328 0.6720.672 Interaction-budget any-success. For completeness, the alternative interaction-budget any-success diagnostic (the fraction of seeds on which any tested recommendation list during the run was accepted by the env, regardless of whether the algorithm subsequently moved past it) gives TRACE-F: 57%57\% and TRACE-I: 95%95\% on the same 100100 seeds; LLM baselines and direct-commit variants return on first success, so for them this any-success rate coincides with the final-output rate above. Proposer ablation. Table 12 fixes the TRACE commit/reject scaffold and varies how candidate identities are proposed. The uniform proposer realizes the falsification setting; Incremental-LM extracts predicate candidates from each feedback message with an LLM; the decoded proposer uses the task’s canonical feedback templates. Table 12: Proposer variants inside TRACE on RecMovie with the same rule-based detector; entries are interaction-budget any-success. Proposer any-success TRACE-F (uniform) 57% Incremental-LM (atomic per-feedback) 74% TRACE-I (decoded) 95% Detector ablation. Table 13 compares detector implementations on RecMovie while fixing the algorithm to TRACE-F. The rule-based detector is stronger in this semi-templated setting. Table 13: Detector variants inside TRACE-F on RecMovie. Overall: any-success. Final Output: final-output env.success (matches Table 1). Detector Overall Final Output Rule-based detector 57% 51% LLM, zero-shot 21% 12% LLM, chain-of-thought 21% 18% Direct-commit variants. The headline same-decoder comparison is reported in Table 4 of the main text. Table 14 separates the three RecMovie direct-commit variants: AND over all wanted predicates, OR over at least one predicate per dimension, and a RANKED top-k match score. Table 14: Same decoder, with versus without the TRACE test-before-commit scaffold, on RecMovie. Entries are final-output env.success over 100100 seeds; for direct-commit baselines, final-output success coincides with any-success since they return on first hit. Configuration env.success TRACE-I 90% Direct-AND (strict) 15% Direct-OR (per-dim disjunction) 23% Direct-RANKED (top-k match score) 22% Feedback omission. We test an i.i.d. feedback-dropout model in which each feedback message is replaced by the empty string with probability p. Table 15 reports RecMovie results. Table 15: Interaction-budget any-success of TRACE-I on RecMovie under i.i.d. feedback omission, 100100 seeds per cell. Performance is flat through 20%20\% omission and degrades gradually afterwards. Omission rate p any-success 0%0\% 95% 10%10\% 95% 20%20\% 95% 30%30\% 94% 50%50\% 93% 70%70\% 87% False identities. Table 16 isolates false extracted identities from feedback omission. For every decoded feedback predicate, with probability pfalsep_false we replace it by a uniformly sampled wrong predicate from the same attribute dimension that is not in the seed’s canonical C∗C^*. The TRACE-I variant uses these corrupted identities only in the proposer while keeping the rule-based detector clean; direct baselines accumulate the same corrupted identities without test-before-commit. To capture degradation across the entire run rather than just the converged output, this sweep uses the interaction-budget any-success diagnostic; at pfalse=0p_false=0 it therefore reports the 95%95\% any-success value rather than the 90%90\% final-output headline. As false identities increase, TRACE-I degrades gradually (95%→67%95\%→ 67\% any-success from pfalse=0p_false=0 to 0.50.5), whereas all direct-commit variants fall to 8%8\%. The direct methods can still have high superset⁡(C∗)superset(C^*) because they accumulate many constraints, including the true ones; the any-success column reveals the cost of unfiltered false positives, while TRACE-I’s test-before-commit filters them out before commitment. Table 16: False-identity-only RecMovie sweep over 100100 seeds. Each extracted predicate is independently replaced by a wrong same-dimension predicate with probability pfalsep_false. Success is interaction-budget any-success, unlike the final-output rates in Table 4. pfalsep_false Method any-succ. superset⁡(C∗)superset(C^*) 0.00.0 TRACE-I %95\% 59%59\% 0.00.0 Direct-AND 15%15\% 94%94\% 0.00.0 Direct-OR 23%23\% 94%94\% 0.00.0 Direct-RANKED 22%22\% 94%94\% 0.10.1 TRACE-I %90\% 54%54\% 0.10.1 Direct-AND 12%12\% 86%86\% 0.10.1 Direct-OR 12%12\% 93%93\% 0.10.1 Direct-RANKED 19%19\% 94%94\% 0.20.2 TRACE-I %83\% 49%49\% 0.20.2 Direct-AND 8% 08\% 78%78\% 0.20.2 Direct-OR 12%12\% 92%92\% 0.20.2 Direct-RANKED 16%16\% 93%93\% 0.30.3 TRACE-I %85\% 53%53\% 0.30.3 Direct-AND 8% 08\% 73%73\% 0.30.3 Direct-OR 8% 08\% 90%90\% 0.30.3 Direct-RANKED 12%12\% 92%92\% 0.50.5 TRACE-I %67\% 38%38\% 0.50.5 Direct-AND 7% 07\% 58%58\% 0.50.5 Direct-OR 7% 07\% 90%90\% 0.50.5 Direct-RANKED 8% 08\% 93%93\% Equal output budgets. All runs use the same 100100 RecMovie seeds and report final-output success, i.e., whether the single output returned by a method satisfies the user. The common budget unit is a generated output that the environment evaluates. Under a cap B, TRACE-I spends at most B−1B-1 outputs on feedback-bearing tests and returns one final output, sampled from its deepest committed node, within the cap; each seed and cap is run independently. Iterative baselines stop at their first accepted output and otherwise return their output at the cap. Best-of-N draws B independent generations and is granted an oracle selector that returns a satisfying sample whenever one exists. All baselines receive the environment’s feedback mapped to the same canonical identity projection over the 3636 predicates used by the TRACE-I decoder. The baseline configurations of Table 1 were run only with T=20T=20. To evaluate baselines with 6060 outputs we use three variants of the same methods: DirectLLM-W8 and Self-Refine-W8 condition only on the eight most recent interactions, and Reflexion-NoCycle keeps four trials but disables the early termination of a trial that repeats the same recommendation. For these variants, success at B=20B=20 is read from the same 6060-output runs as whether the first accepted output occurs within the first 2020 outputs. Tables 17 and 18 give the numbers plotted in Figure 2, and Table 19 reports resource use. Table 17: Final-output success on RecMovie under common output caps (100100 seeds; Wilson 95%95\% intervals). The Table 1 configurations were run only with T=20T=20. Method B=20B=20 B=60B=60 TRACE-I (mexp=5m_exp=5) %73\% [6464, 8181] %86\% [7878, 9191] DirectLLM (Table 1 config.) 40%40\% [3131, 5050] n/a Reflexion (Table 1 config.) 42%42\% [3333, 5252] n/a Self-Refine (Table 1 config.) 32%32\% [2424, 4242] n/a DirectLLM-W8 38%38\% [2929, 4848] 48%48\% [3838, 5858] Reflexion-NoCycle 35%35\% [2626, 4545] 37%37\% [2828, 4747] Self-Refine-W8 37%37\% [2828, 4747] 42%42\% [3333, 5252] Best-of-N (oracle selector) 17%17\% [1111, 2626] 21%21\% [1414, 3030] Table 18: TRACE-I test-window sweep on RecMovie under common output caps (final-output success with Wilson 95%95\% intervals; feedback rounds per episode). mexpm_exp B Success Mean rounds P90 rounds 11 2020 65%65\% [5555, 7474] 4.434.43 55 33 2020 78%78\% [6969, 8585] 13.4213.42 1919 33 6060 77%77\% [6868, 8484] 14.2614.26 2222 55 2020 73%73\% [6464, 8181] 18.6118.61 1919 55 6060 86%86\% [7878, 9191] 22.0822.08 2727 Table 19: Resource use per seed on RecMovie, averaged over each method’s complete 100100-seed logs (baselines: 6060-output runs). Evals: environment-evaluated outputs. Gen. and Aux.: LLM calls for candidate generation and for reflection or critique. Method Evals Gen. LLM Aux. LLM LLM tokens Wall (s) TRACE-I (mexp=5m_exp=5) 22.122.1 00 00 00 0.40.4 TRACE-I (mexp=15m_exp=15, default) 60.660.6 00 00 00 0.90.9 DirectLLM-W8 36.336.3 36.336.3 00 21,27521,275 14.414.4 Reflexion-NoCycle 39.939.9 39.939.9 2.02.0 25,84525,845 14.214.2 Self-Refine-W8 38.438.4 38.438.4 38.038.0 62,13362,133 42.442.4 Best-of-N (N=60N=60) 60.060.0 60.060.0 00 13,47913,479 16.716.7 Trusted initial constraints. Requirements that are already known, for example stated in the user’s initial request or verified in an earlier session, can seed the root: TRACE then starts from Cv0=CinitC_v_0=C_init, never re-tests these constraints, and searches only for the remaining ones; Cinit=∅C_init= recovers Algorithm 1. If Cinit⊆C∗C_init C^*, the root is viable because ∗⊆Region⁡(C∗)⊆Region⁡(Cinit)X^* (C^*) (C_init), and the proofs of Theorems 2 and 3 apply to the residual search, since they only require every committed node, including the root, to be viable. In Table 20, TRACE-I (mexp=5m_exp=5) receives min⁡(2,|C∗|) (2,|C^*|) oracle-provided true constraints at initialization (the four seeds with |C∗|=1|C^*|=1 receive one). Because these constraints are supplied by the oracle, the gain is an upper bound on the value of verified context. Table 20: TRACE-I (mexp=5m_exp=5) on RecMovie with an oracle-trusted root (final-output success with Wilson 95%95\% intervals; mean feedback rounds per episode). Root B=20B=20 B=60B=60 Rounds (B=20B=20) Rounds (B=60B=60) Cinit=∅C_init= 73%73\% [6464, 8181] 86%86\% [7878, 9191] 18.6118.61 22.0822.08 |Cinit|≤2|C_init|≤ 2, oracle-trusted %90\% [8383, 9494] %91\% [8484, 9595] 10.0910.09 10.7710.77 C.4 Full 20Q, EDA, Mastermind, and Poem results 20Q and EDA: coverage versus env.success. Table 21 compares env.success and the superset⁡(C∗)superset(C^*) coverage diagnostic on 20Q and EDA. The theorem directly controls coverage; env.success may also depend on catalog grounding and generator fallback behavior. 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 superset⁡(C∗)superset(C^*). 20Q EDA Things Configuration env.succ. superset(C∗)(C^*) env.succ. superset(C∗)(C^*) TRACE-F (uniform) 84% 82% 87% 84% TRACE-I (decoded) 100% 100% 99% 99% Mastermind: fixed-budget K-sweep. Table 22 varies K at fixed ncolors=6n_colors=6. Since |ℋ|=6K|H|=6K, this sweep varies K and H jointly. It is therefore not a direct test of the theorem’s logarithmic K factor; rather, it is a fixed-budget stress test showing how the uniform proposer degrades as the candidate class grows. The complementary H-sweep at fixed K=3K=3 is reported in Table 2 of the main text; on that sweep, superset⁡(C∗)superset(C^*) tracks env.success exactly except at the largest setting ncolors=20n_colors=20, where TRACE-F reaches env.success 74%74\% but superset⁡(C∗)=72%superset(C^*)=72\% (TRACE-I has both at 99%99\%). Table 22: Fixed-budget K-sweep on Mastermind with ncolors=6n_colors=6 fixed, so |ℋ|=6K|H|=6K. K TRACE-F succ. Binary attempts TRACE-I succ. Identity attempts 2 %73\% 10.0910.09 99%99\% 5.145.14 4 35%35\% 13.8413.84 %100\% 5.565.56 6 4% 14\% 14.9514.95 %100\% 7.297.29 8 1% 11\% 15.0015.00 %100\% 9.119.11 10 0% 10\% 15.0015.00 %100\% 10.9810.98 Poem: open-vocabulary action generation. For LLF-Bench Poem, the action is free-form English text rather than a finite catalog item. We implement (i) a word-bucket generator that composes each line with a proposed syllable count by sampling CMU-dict words from syllable-indexed buckets; (i) a rule-based detector that regex-parses native feedback of the form “The line: X has n syllables. It should only have m syllables.”; and (i) TRACE-F and TRACE-I variants over line-syllable predicates. Table 23 reports Haiku and Tanka results. TRACE-I covers C∗C^* in every seed on both forms. TRACE-F degrades from Haiku to Tanka as K and |ℋ|=6K|H|=6K increase under the fixed proposal budget. Table 23: TRACE on LLF-Bench Poem with Haiku and Tanka forms. We use 100100 seeds per cell and mexp=Nmax=15m_exp=N_ =15. Brackets are Wilson 95%95\% confidence intervals. TRACE-I exploits per-line target syllable counts revealed in the feedback; TRACE-F must search over |ℋ|=6K|H|=6K predicates. Haiku (K=3K=3) Tanka (K=5K=5) Method env.succ. attempts env.succ. attempts TRACE-F 54%54\% [4444,6363] 12.5712.57 14%14\% [88,2222] 14.7714.77 TRACE-I %100\% [9696,100100] 3.803.80 %100\% [9696,100100] 5.815.81 The Poem experiment shows that TRACE is not limited to catalog recommendation. With a suitable constrained generator, the same commit/reject scaffold applies to open-vocabulary text generation. The experiment is still structured: the feedback contains parseable line-level syllable information. Richer unstructured natural-language feedback, where rule-based extraction is unlikely to suffice, remains an important direction for future work. C.5 Example execution trace on RecMovie To make the algorithm’s per-round behavior concrete, the listing below shows the full execution trace of TRACE-I on RecMovie seed 1616 with the headline default mexp=Nmax=15m_exp=N_ =15 (rule-based detector + decoded proposer). The latent constraint set is C∗=type_=TV show,year=80s,genre=SportC^*=\type\_=TV show,\ year=80s,\ genre=Sport\. The trace illustrates three mechanisms central to the framework: • Test-before-commit catches a spurious child cheaply. Attempt n=1n=1 proposes the spurious constraint type_=movie; the very first feedback contradicts it (“not all TV shows”) and also reveals two missing constraints (“not exclusively Sport TV shows”; “not from the 80s”), so ViolViol fires after one round. The child is rejected after consuming only 11 round of the per-test cap mexp=15m_exp=15. • Multi-sample falsification on viable children is silent. Attempts n=2n=2, 33, 44 each propose a true latent constraint; feedback is consistent with the tested set on all 1515 rounds (we elide the 1414 duplicate rounds), so each child survives the test window and is committed. • Identification access guides the proposer. The decoded proposer reads the feedback for extracted identities; by attempt n=2n=2 the working set W already contains the type_=TV show identity extracted from the attempt 11 feedback, leading to a true child being proposed and committed. Subsequent commits (year=80s, genre=Sport) follow the same pattern. After 44 attempts and 4646 interaction rounds (well under the budget T=Nmax⋅mexp=225T=N_ · m_exp=225), the deepest committed node v†v satisfies Cv†=C∗C_v =C^* and the output sample x x consists of three Sport TV shows from the 80s, satisfying every latent constraint. Listing: TRACE-I execution trace on RecMovie seed 1616 ====================================================================== TRACE-I run on RecMovie | seed=16 m_exp=15 N_max=15 ====================================================================== C* (latent constraints) : genre=Sport, type_=TV show, year=80s |H| (candidate class) : 36 ---------------------------------------------------------------------- Attempt n=1 (parent C_v = , depth=0) Proposed: type_=movie [spurious] Child C_u = type_=movie s=1 feedback: "The recommendations are not all TV shows. The suggested titles aren’t exclusively Sport TV shows. The recommendations are not from the 80s." [Viol fired] -> REJECT (rounds used: 1/15) ---------------------------------------------------------------------- Attempt n=2 (parent C_v = , depth=0) Proposed: type_=TV show [true latent] Child C_u = type_=TV show s=1 feedback: "You’ve recommended TV shows, which is awesome! Among the recommended titles, you’l find more than Sport TV shows. The recommendations are not from the 80s." ... (s=2..15: feedback unchanged, child survives) -> COMMIT (rounds used: 15/15) C_v advances to depth 1: type_=TV show ---------------------------------------------------------------------- Attempt n=3 (parent C_v = type_=TV show, depth=1) Proposed: year=80s [true latent] Child C_u = type_=TV show, year=80s s=1 feedback: "You’ve recommended TV shows, which is awesome! Among the recommended titles, you’l find more than Sport TV shows. The recommendations are all from the 80s, great!" ... (s=2..15: feedback unchanged, child survives) -> COMMIT (rounds used: 15/15) C_v advances to depth 2: type_=TV show, year=80s ---------------------------------------------------------------------- Attempt n=4 (parent C_v = type_=TV show, year=80s, depth=2) Proposed: genre=Sport [true latent] Child C_u = genre=Sport, type_=TV show, year=80s s=1 feedback: "You’ve recommended TV shows, which is awesome! The recommendations are all Sport, nice! The recommendations are all from the 80s, great!" ... (s=2..15: feedback unchanged, child survives) -> COMMIT (rounds used: 15/15) C_v advances to depth 3: genre=Sport, type_=TV show, year=80s ---------------------------------------------------------------------- Final v_dagger: C = genre=Sport, type_=TV show, year=80s Output x_hat: "Sport i 2’eren", "ZDF Sport Extra", "A Question of Sport" Termination: empty_region_cap (no more children to test) Total rounds: 46 / 225 Total attempts: 4 / 15 Coverage (C* subset C_v_dagger): True ====================================================================== C.6 Prompts for LLM-based components For reproducibility we record the verbatim prompts used by the LLM-based ablations in Appendix C.3 and by the TravelPlanner runs in Section 5.5. The prompts were written for Qwen3-4B served locally; the DeepSeek-V4-Flash configuration of Section 5.5 sends the same TravelPlanner prompts through the DeepSeek API with thinking mode enabled; the trailing “/no_think” marker disables Qwen3’s chain-of-thought block when not needed. LMViolationDetector: zero-shot (Table 13, 21%21\%) [system] You are a careful logical judge. Answer strictly as instructed. /no_think [user] A movie recommender has committed to the following assumptions about the user’s preferences: - <predicate 1> - <predicate 2> ... The user responded with this feedback after seeing the latest recommendations: """<feedback>""" QUESTION: Does the feedback CONTRADICT any of the committed assumptions? - Answer YES if the feedback indicates that at least one committed assumption is wrong (e.g. the feedback says the recommendations were not of a type/era/genre the assumption claimed). - Answer NO if the feedback is consistent with the assumptions, or only complains about a dimension not in the assumptions. Answer with a single word: YES or NO. /no_think LMViolationDetector: chain-of-thought (Table 13, 21%21\%) [system + user same as zero-shot, replacing the final line:] First, in ONE short sentence, explain your reasoning. Then on a new line, write ANSWER: YES or ANSWER: NO. /no_think IncrementalLMProposer: per-feedback extraction (Table 12, 74%74\%) [system] You extract structured preferences from feedback. Follow the output format precisely. /no_think [user] You are analysing ONE feedback message from a user to a movie recommender. CRITICAL CONVENTION (RecMovie): feedback of the form "The recommendations are not X" / "not all X" / "not from X" is a CORRECTION meaning the user WANTS X on that dimension. Positive phrasing ("... wonderful!" / "... great!") also confirms the user wants that value. Phrase "past few years" refers to the year bucket "recent". Dimensions you can emit (use EXACTLY these names): - type_ (values: movie, TV show) - year (values: 50s, 60s, 70s, 80s, 90s, 2000s, recent) - genre (values: Action, Comedy, Drama, Thriller, Horror, Sci-Fi, ...) Feedback: """<feedback>""" List the user’s preferences revealed by this feedback. Output ONE line per preference in the format ‘dim=value‘. If no preference is revealed, output nothing. No other text, no prose. /no_think TravelPlanner plan generator: system prompt (tp_v6_no_cost_prompt, used in Section 5.5) You are a meticulous travel-planner that produces machine- readable JSON plans. You will receive: - A travel query (origin, destination, days, budget). - Optional committed constraints the user requires. - Reference information listing the only valid entities (flights, restaurants, attractions, accommodations) you may use. Output rules (every plan MUST satisfy ALL of these): 1. JSON-only output: a single object "plan": [...] with one entry per day. No prose, no markdown. 2. Entity-format rule: for breakfast / lunch / dinner / attraction / accommodation fields, write "Name, City" (Name copied verbatim from reference). Multiple attractions per day separated by semicolons. 3. Travel-day current_city format: "from CityA to CityB" on travel days; the city name only on stationary days. 4. Transportation paradigm: pick ONE paradigm for the trip (Flight or Self-driving) and stick to it. Stationary days MUST use transportation = "-". 5. Closed-circle trip: day 1 starts at the origin city; the final day returns to the origin. 6. Sandbox-only entities: every Name MUST appear verbatim in the reference; on any "from/to" pattern only use city names from the reference. 7. Diversity & accommodation: do not repeat restaurants or attractions; use the same accommodation across consecutive nights; respect the reference’s minimum-nights column. 8. Completeness: fill every field; use "-" only when the field genuinely does not apply. 9. Day-1 accommodation: never write "-". 10. Budget is a meaningful target, not an upper bound: prefer balanced choices when budget allows; never exceed the budget; if spending under 50% of budget, reconsider. The user prompt is rendered by build_user_prompt with fields Query / Origin / Destination / Days / People / Budget, the canonicalized Committed block (predicates already accepted by TRACE), the Reference Information (optionally pre-filtered by the committed constraints), and the closing instruction “Respond with only the JSON object: "plan": [...]”. Plans are evaluated by the env’s built-in commonsense and hard-constraint evaluators; we do not implement an additional commonsense prompt of our own.

Instant research discovery