解析代码生成中测试反馈的理论机制,揭示高效策略与局限性。
A Theoretical Analysis of Test-Driven Code Generation
- 用概率框架分析环境反馈驱动的代码生成与选择策略。
- 模糊相似性估计比等价性估计信噪比更高,更优。
- 解释回提示效果受限于任务描述模糊性,适合改进提示设计者。
代码助手在测试驱动开发中日益普及,但其环境交互机制的理论基础仍不明确。本文构建了两种主流范式的形式化概率框架:生成后利用执行环境选择代码,以及基于环境反馈生成代码。首先,将多种成熟的选择启发式形式化为环境感知的代码正确性估计器。理论上证明,基于模糊功能相似性的估计器引入归纳偏置,在信噪比上严格优于基于功能等价性的估计器。其次,将回提示建模为上下文内对汤普森采样的近似,推导出含不可观测奖励项的新型后悔界,从理论上解释了回提示效果受限于非正式任务描述的模糊性(不可约后悔)。通过五种先进开源模型,在BigCodeBenchHard、LeetCodeDataset和QiskitHumanEvalSim上验证了上述发现。该形式化还提出有效改进任务描述的方法,由此构建新基准QiskitHumanEvalSimX。
原文摘要 · Abstract (English)
Code assistants are increasingly utilized in test-driven software development, yet the theoretical mechanisms behind their environment-interaction strategies remain underexplored. We provide a probabilistic framework for two dominant paradigms: code selection after generation using the execution environment, and code generation conditioned on environment feedback. First, we formalize several well-established selection heuristics as environment-aware estimators of code correctness. We theoretically prove that estimators based on fuzzy functional similarity add an inductive bias and strictly dominate estimators based on functional equivalence in terms of signal-to-noise ratio. Second, we frame backprompting as an in-context approximation of Thompson sampling. We derive a novel regret bound for reward functions with unobservable components, theoretically explaining why the effectiveness of backprompting is limited by the ambiguity of the informal task description (an irreducible regret). Using five state-of-the-art open weight models, we corroborate these findings across BigCodeBenchHard, LeetCodeDataset, and QiskitHumanEvalSim. Our formalization also suggests how to improve task descriptions effectively, leading to a new benchmark, QiskitHumanEvalSimX.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。