复杂度拐点：一种用于代码生成可靠性的提示侧结构复杂度指数

# 复杂性拐点：面向代码生成可靠性的提示侧结构复杂性指数
来源：https://arxiv.org/html/2609.19616  
田昭，所属机构：威斯康星大学密尔沃基分校，邮箱：[tzhao@uwm\.edu](mailto:)

###### 摘要

基于生成代码度量的复杂性依赖于失败与否：一个困难的提示可能产生一个简短的失败程序，从而被赋予低输出复杂性。我们引入了一个六维提示侧结构复杂性指数，该指数在生成前评分，并与功能正确性保持分离。我们首先在一个初步的单评分者评分标准的六个分数段中，选取了5,000个Python提示。然后，四位非评审团队的大型语言模型评分员对这些锁定的提示重新评分，提供了19,997个评分行；在全部四位评分员都参与评分的4,998个提示上，综合评分者间信度为ICC=0.872。我们在每个提示上评估了21个模型，产生了105,000个模型-提示生成结果。在未调整的平均池化分析中，通过率在综合分数γ^=13.75处出现一个非单调拐点，低于或等于该值的提示通过率为79.9%，高于该值的为87.6%。这种池化模式并非一个普遍的失败分界线。任务类型的固定效应将拐点移至10.75，并将区间差距从7.6个百分点缩小到2.1个百分点。事后构建框架控制将拐点移至8.50，原始区间差距为-3.5个百分点，且单独任何一个框架都无法复现池化分析中+7.6个百分点的变化。模型特定拟合还包括16个向上变化和5个向下变化。一个包含365个提示的审计清理扩展集在支持充分的区间15和16处与原始匹配的五个模型的点估计值非常接近，但在区间16以上只增加了14个提示。在具有可计算Lizard复杂性的零通过生成中，有28.5%的案例将综合分数高于8的提示与生成输出复杂性不超过10的输出配对，这说明了测量问题。在专门用于校准的、包含分歧案例的人工评分集上，人类一致性中等且因评分员而异，而通过改写和跨语言重新评分保留了分数排序。过度识别检验强烈拒绝了对六个评分维度的联合限制，因此我们将复合指数视为一个指数，并不对2SLS估计进行因果解释。其贡献在于建立了一个生成前测量框架，并对可靠性区间进行了有界观察性分析。

## 1引言

大型语言模型正日益被评估和部署为代码生成器。标准的评估问题是功能性的：生成的程序是否通过了测试？HumanEval、MBPP和SWE-Bench等基准测试已使这一问题能够被大规模量化。它们并未直接回答可靠性如何随编程任务所需的结构而变化。两个具有相似平均通过率的模型，在需要交互分支、数据结构、边界情况或算法步骤的提示上，表现可能大相径庭。

困难在于，任务复杂性通常在生成之后，从模型生成的程序中度量。当模型成功时，生成的程序可能是对所请求解决方案的一种实现的有用代理。当它失败时，输出通常是一个简短的代码桩、部分解决方案、语法错误或其他损坏的程序，其测得的圈复杂性较低。因此，一个结构要求高的提示，恰恰因为模型失败了，反而可能被归入低复杂性区间。这种失败依赖的测量可能削弱、转移或隐藏任务结构与通过率之间的关系。我们称之为*逆向阈值问题*：简单生成代码的表面上的不可靠性，可能部分反映了从未生成的更复杂的代码。

一个自然的基线是使用关键词特征来近似提示复杂性，例如指令中分支、循环、递归或数据结构相关术语的数量。这类特征廉价、透明且在生成前固定，但将交互式程序结构简化为了表面线索。我们则使用一个评分标准，分别对分支、迭代、状态、数据结构、边界情况和组合性提出独立问题。结果仍然是一个代理，而非基准真相，但它在正确的时间被度量：在被评估模型产生答案之前。

我们提出了Complexity Kink基准测试，这是一项提示侧测量研究，旨在将预期解决方案结构与生成输出复杂性及功能正确性分离。我们从OpenCodeInstruct构建了5,000个Python提示，这些提示根据初步单评分者评分标准的六个分数段分层。四位非评审团队的LLM评委对锁定的提示重新评分，21个评估模型每个提示生成一个解决方案。我们的主要分析估计了通过率作为未分箱综合指数函数的形状。我们还比较了输出侧的圈复杂性，并报告了2SLS诊断结果，但候选工具变量未能通过其联合排他性限制，因此不进行因果解释。

实验结果不支持一个普遍的分界线。平均池化曲线在指数中部下降，并在更密集的高分区回升，但任务类型和构建框架显著改变了差距及其估计位置。特别是，两个提示来源框架在得分和通过率上均存在显著差异，且两者都无法单独复现池化分析中+7.6个百分点的变化。五个模型特定拟合在其拐点处呈现向下移动，而16个则向上移动。一个匹配的五模型扩展集在区间15和16处与原始点估计值非常接近，并实质性地增加了该区域的支持度，但16以上的区域仍然过于稀疏，无法得出强有力的端点结论。

主要贡献：
- 我们形式化了失败依赖的输出复杂性，并在本样本中进行了展示：28.5%的零通过完整案例，将一个结构上非平凡的提示与生成输出圈复杂性不超过10的输出配对。
- 我们引入了一个综合评分的提示侧指数，并检验了其相对于人工评分、纯语言改写以及Java和C++重述的可靠性。
- 我们构建了一个5,000提示的Python基准测试集，该集根据初步评分标准分层，并使用单元测试评估了21个模型，包括模型特定、池化、重复采样、任务类型和审计清理尾部检查。
- 我们将测量设计的局限性作为结果报告。任务和构建框架的构成解释了大部分池化拐点，极端尾部仍然稀疏，且候选工具变量限制被拒绝。

## 2相关工作

LLM代码评估。HumanEval、MBPP和SWE-Bench确立了功能测试作为代码生成LLM的核心评估协议。这些基准测试询问生成的代码是否通过隐藏或公开测试，而该功能结果在我们的工作中仍是目标变量。我们的贡献是正交的：我们研究如何度量正在尝试求解的任务的结构复杂性。OpenCodeInstruct提供了大量指令-代码对，可从中抽取此类基准，但生成的代码可能继承求解器失败，而参考代码可能反映一种实现而非潜在的任务结构。

复杂性度量与基准偏差。圈复杂性及相关代码指标因其可从源代码计算而具有吸引力，始于McCabe的图论公式，并通过静态分析工具（如Lizard）得以延续。然而，在代码生成评估中，可用的源代码通常是模型输出本身。这使得该指标成为“后处理”的：测得的复杂性受到模型成功或失败的影响。本研究通过在评估模型生成任何代码之前根据提示对复杂性评分来解决此问题。

工具变量与阈值估计。工具变量是计量经济学中应对内生性回归变量的标准方法，而弱工具检验和过度识别检验是必要的诊断手段。实证软件工程越来越多地采用计量经济学设计来推断内生性。我们考察了单独的评分维度是否可以作为生成输出复杂性的工具变量，但实证限制被拒绝，我们仅将这些拟合作为诊断保留。主要的断点分析转而直接使用评分标准的复合指数。针对该描述性问题，我们采用了Hansen的门槛回归和自举sup-Wald框架。

LLM作为评委与评分员。G-Eval、AlpacaEval和MT-Bench使用LLM来评估开放式模型输出，而基于评分标准的自动评估在自然语言处理领域有更长的历史。我们以不同方式使用LLM评委。评委不对生成的回答评分、不排名模型或确定通过/失败结果。他们在生成前对输入提示进行评分，使用公开的结构化评分标准，并被排除在被评估模型小组之外。这将LLM判断转变为针对潜在输入属性的测量层，而非结果评估器，从而降低了评委简单地再现基准旨在诊断的相同输出侧偏差的风险。

## 3背景：失败依赖的输出复杂性

设κᵢ*表示任务i所需的潜在结构，yᵢₘ表示模型m的功能结果，κᵢₘᵒᵇˢ表示在该模型生成输出上测得的圈复杂性。即使是通过的输出也只是任务的一种实现，因此κᵢₘᵒᵇˢ不一定等于κᵢ*。更重要的是，测量本身依赖于结果：
κᵢₘᵒᵇˢ = g(κᵢ*, yᵢₘ, ηᵢₘ) (1)
其中失败的生成通常坍缩为测量复杂性较低的短程序。因此，按κᵢₘᵒᵇˢ对通过率分层，实际上是条件依赖于一个受成功影响的生成后量。

我们通过一个提示侧指数Cᵢ解决这个时序问题，该指数在任何评估模型生成代码之前计算。我们的主要目标是描述性的：在构建的基准数据集中，条件期望E[yᵢ | Cᵢ]，其中yᵢ是所有评估模型的平均通过率。六个评分维度也可以被视为κᵢᵒᵇˢ的候选工具变量，但因果解释需要很强的排他性限制。下面的诊断拒绝了这些限制，因此工具变量分析并未识别出因果效应。

## 4方法论

### 4.1数据

我们使用了从OpenCodeInstruct抽取的5,000个Python编程任务。构建过程结合了早期阶段保留的2,246个提示和在自动契约与测试质量过滤后新收集的2,754个候选提示。早期抽取扫描了一个200,000条记录的源序前缀，后期的候选收集则有意补充了高参考复杂性尾部。我们保留了这个二级构建框架指示器以供事后敏感性分析。一个初步的o4-mini评分员使用与下文相同的六维评分标准对候选提示进行了评分。然后，我们在初步分数段0-3和4-6中各选择了834个提示，在7-9、10-12、13-15和16-24中各选择了833个提示。该分数仅用于抽样。

在提示集锁定后，四评委集成对每个提示重新评分。所有报告的分析均使用该集成均值，而非初步抽样分数。重新评分改变了分布：使用连续区间[0,3]、(3,6]、(6,9]、(9,12]、(12,15]和(15,24]，被分析的指数计数分别为319、943、940、898、1,425和475。因此，基准测试是根据初步分数分层的，但在最终指数上并不平衡。两种分布都不代表自然的OpenCodeInstruct频率分布。参考解决方案圈复杂性有助于塑造上游候选池，并保留用于一致性检查；它从不作为分析的提示指数或生成输出复杂性。

评估模型组包含来自多家提供商的21个模型：Claude Opus 4.6、Opus 4.7和Sonnet 4.6；GPT-5.4、GPT-5-mini、GPT-4.1、GPT-OSS-20B和GPT-OSS-120B；Gemini 3.1 Pro Preview和Gemini 3 Flash；Grok-3；DeepSeek V3.2；Kimi K2.5；Qwen 3.6 Plus和Qwen 3.5-9B；Mistral Large-3、Mistral Small 2412和Ministral-3-14B-reasoning；Llama 3.3-70B；GLM 4.7-flash；以及Trinity-large。四位评分评委均未出现在此组中，减少了直接的评分员-模型重叠，但并未建立工具变量有效性。报告的模型组包含21个模型。一个本地部署的、量化的AuroraGPT-IT-v4仅覆盖了早期的提示框架，因此缺少新增的2,754个提示的输出。它在事后决定中被排除在最终模型组分析之外，且没有预先设定的资格规则。为透明起见，其在早期框架上的通过率为20.6%；性能并非记录的排除标准。我们的结论仅限于报告的21个模型组。21个评估模型中每一个都为每个提示生成一个解决方案，总共产生21×5,000=105,000个生成结果。通过率是通过Nvidia提供的单元测试的比例。在随后的合并分析中，通过率在每个提示上对21个模型取平均值，产生一个提示级别数据集，N=5,000。每个模型的分析使用相同的N=5,000行数据（每模型）。对于每个生成结果，我们在清理后的生成Python代码上使用Lizard计算McCabe圈复杂性，并对报告的函数求和。该量在构件中被标记为生成输出复杂性。它不是数据集元数据、生成后评分标准分数或参考解决方案复杂性。105,000个生成结果中有103,948个可用Lizard复杂性；涉及它的分析使用完整案例并报告分母。

### 4.2评分标准评分

#### 4.2.1评分模型与部署

提示由通过Azure AI Foundry部署的四位非评审团队LLM评委进行评分：o4-mini、gpt-5.5、llama-4-maverick和command-a。所有5,000个提示使用相同的评分标准提示获得集成评分。覆盖率实际上完整：4,998个提示有四位评委评分，一个提示有三位，一个提示有两位，共计19,997个总评分行。我们通过对每个提示-维度对在可用评委间取平均分来汇总。生成的集成具有高的综合