arXiv：cs.CL· Shaoang Li, Daniel R. Jiang, Jian Li·· 3 小时前AI 评分44
TRACE：用约束树探索从语言反馈中学习
Constraint Tree Exploration for Learning from Language Feedback
AI 导读
研究者提出 TRACE 算法，将语言反馈学习建模为对可行域的纯探索，把候选约束组织成树，通过反复生成满足约束的动作来验证细化，仅当反馈不与之矛盾时才确认。理论证明 TRACE-Falsification 的覆盖界依赖候选类大小 H，而在可靠识别下 TRACE-Identification 可将该依赖替换为 K/p_ext。
正文
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.
| Subjects: | Artificial Intelligence (cs.AI); Computation and Language (cs.CL) |
| Cite as: | arXiv:2610.09107 [cs.AI] |
| (or arXiv:2610.09107v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.09107 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Shaoang Li [view email]
[v1]
Tue, 6 Oct 2026 20:57:37 UTC (146 KB)
来源：arXiv：cs.CL · arxiv.org