The Complexity Kink: A Prompt-Side Structural Complexity Index for Code-Generation Reliability¶

会议: NeurIPS 2026
arXiv: 2609.19616
代码: https://github.com/uwm-se/ComplexityKink
领域: 其他
关键词: 代码生成、结构复杂度、逆阈值问题、门限回归、可靠性断点

一句话总结¶

针对传统以生成代码圈复杂度评估模型可靠性时因失败截断导致的度量偏倚，本文提出仅依赖提示词的六维结构复杂度指数与门限回归断点估计方法，揭示了评测中通过率突增假象背后的任务构成偏差。

研究背景与动机¶

代码大模型的评估长期依赖单元测试通过率（Pass Rate）等功能性指标，但这只能反映整体表现，无法刻画模型可靠性随任务内在结构复杂度的演变规律。传统软件工程通常利用 McCabe 圈复杂度等静态分析工具测量代码复杂度，然而在评测代码生成模型时，研究人员往往只能对模型自身生成的输出代码进行度量。这一后置度量方式存在严重的内生性偏倚：当模型面对高难度任务产生幻觉、语法崩溃或生成简短代码桩（stub）而失败时，其输出代码在静态分析工具眼中反而呈现出极低的圈复杂度。

这种失败依赖的测量失真被称为“逆阈值问题”（Reverse Threshold Problem）。在实验数据中，高达 25.0% 的失败样例将高复杂度提示词转化为圈复杂度不超过 10 的极简残缺代码，这一比例是成功样例的两倍。若直接按生成代码复杂度对样本分桶，自动化评估管线会系统性地将困难失败样本错误归入低难度区间，从而抹平甚至扭曲真实难度与可靠性之间的关系。与此同时，基于提示词表层关键词计数的浅层代理又无法有效捕捉控制流与状态依赖等深层算法逻辑。

本文的切入角度是完全切断评估度量与模型生成结果之间的依赖链条，构建完全独立于生成代码和测试结果的提示词侧结构复杂度指数，并结合非线性计量经济学方法探究可靠性断点。核心 idea：通过解耦生成代码后置度量、仅基于提示词文本从分支/循环/状态等六个维度构建集成结构复杂度指数，利用 Hansen 门限回归识别模型可靠性断点，并通过任务类型与数据源固定效应控制揭示复杂度“跃升扭结”背后的样本构成偏差。

方法详解¶

整体框架¶

本文构建了一套完全在提示词侧进行的结构复杂度评估与可靠性断点检测管线。整个流水线包含提示词抽取与六维专家裁判打分、多模型大规模生成与独立测试审计、门限回归断点搜索，以及多层级控制变量下的稳健性与计量诊断四个核心阶段。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入代码生成提示词<br/>(OpenCodeInstruct 5,000题)"] --> B["提示词侧六维结构复杂度指标构建<br/>4个独立评委LLM打分集成 (0-24分)"]
    B --> C["多模型代码生成与独立测试审计<br/>21款LLM生成10.5万样本 + MiMo审计"]
    C --> D["门限回归与自举断点估计<br/>网格搜索Sup-Wald最大化检验断点"]
    D --> E["多源构架控制与计量诊断<br/>固定效应控制 + IV过度识别检验"]
    E --> F["输出各模型可靠性断点与脆弱性分析"]

关键设计¶

1. 提示词侧六维结构复杂度指标构建：消除生成失败导致的逆阈值测量偏倚 为了防止模型失败将高难度任务退化为低复杂度代码，该指标完全依据提示词文本定义，评分者完全看不到模型生成代码或测试结果。评估体系解构为 6 个相互独立的算法结构维度：分支深度（Branching）、迭代/递归复杂度（Iteration）、状态追踪复杂度（State）、复合数据结构交互（Data Structures）、边界与组合条件（Edge Cases）以及算法组合流水线（Composition）。各维度按 0 至 4 分严格锚定结构特征，由 4 个不在评测名单内的独立大模型评委（o4-mini、gpt-5.5、llama-4-maverick、command-a）进行打分并取均值，得到综合复杂度指数 $C_i = \sum_{d=1}^6 Z_{i,d} \in [0, 24]$。在 4,998 个完整评分样本上，评委间组内相关系数 ICC(2,1) 达到 0.872，展现了高度的评分一致性与跨语言转移能力。

2. 门限回归与自举断点估计：非参数化定位代码生成可靠性跃变阈值 为刻画模型在不同复杂度区间的非单调行为，研究引入 Hansen 门限回归框架，避免人工预设任意难度门槛。模型设定分段线性关系，通过在复杂度支撑集上进行网格搜索，寻找使截距与斜率突变最显著的候选阈值 $\gamma$。具体利用 Rademacher 野生自举（Wild Bootstrap）重采样残差，严格检验无结构突变的原假设，并基于配对自举计算断点置信区间。在 21 款前沿大模型共 105,000 次生成结果的综合平均表现中，该方法在 $\hat{\gamma}=14.0$ 处精确定位到一个统计显著的突变点，低复杂度区间（$\le 14$）平均通过率为 83.4%，而高复杂度区间（$> 14$）却反常跃升至 90.1%。

3. 多源构架控制与计量诊断：剥离任务构成混杂并证伪工具变量因果假说 针对高复杂度区间通过率反常反弹的“复杂度扭结”（Complexity Kink），本文引入任务类别与构建框架固定效应进行因果与控制分析。将 5,000 道题目划分为 9 大任务类型（如数据结构/算法、数值计算、文本处理等），并区分早期未清洗框架（2,246 题，均分 7.92）与后期经过严格质量过滤的候选框架（2,754 题，均分 11.42）。控制分析揭示：高复杂度区间（$> 14$）中 91% 均为数据结构与算法类题目，引入任务固定效应后，断点两侧的通过率跳跃值从 +6.8 个百分点骤降至 +0.4 个百分点（$p=0.66$）。同时，针对试图将六维复杂度作为生成代码圈复杂度工具变量（IV）的 2SLS 设定，Sargan 过度识别检验统计量高达 552.16（$p < 10^{-15}$），严格证伪了工具变量外生性假说，证明该指数应作为描述性诊断指标而非因果工具。

损失函数 / 训练策略¶

本文属于实证与评测计量研究，核心优化与估计目标聚焦于 Hansen 门限回归参数估计、检验统计量优化以及工具变量二阶段最小二乘法（2SLS）诊断：

门限回归目标与 Sup-Wald 统计量：对于给定的候选断点 $\gamma$，两阶段分段回归模型定义为： $$\mathbb{E}[y_i \mid C_i] = \begin{cases} \alpha_1 + \beta_1 C_i, & C_i \le \gamma \\ \alpha_2 + \beta_2 C_i, & C_i > \gamma \end{cases}$$ 在每个候选 $\gamma$（满足两侧各有至少 500 个样本）处计算 Wald 统计量 $W(\gamma)$，断点估计量由上确界决定： $$\hat{\gamma} = \arg\max_\gamma W(\gamma)$$ 在零假设 $H_0: \alpha_1=\alpha_2 \land \beta_1=\beta_2$ 下，采用 Rademacher 分布残差的野生自举（Wild Bootstrap）循环模拟上确界统计量 $W^*$ 的经验分布，计算有限蒙特卡洛 $p_{\text{MC}}$ 值。
控制变量增广与二阶段最小二乘（2SLS）模型：在加入任务类型与框架控制向量 $\mathbf{x}_i$ 时，估计扩展模型： $$y_i = \alpha + \beta C_i + \mathbf{x}_i^\top \boldsymbol{\delta} + \mathbf{1}[C_i > \gamma] \left(\alpha' + \beta' (C_i - \gamma)\right) + u_i$$ 在工具变量诊断中，第一阶段将生成代码的观测圈复杂度 $\kappa_i^{\text{obs}}$ 对六维评分向量 $\mathbf{Z}_i$ 进行回归： $$\kappa_i^{\text{obs}} = \pi_0 + \mathbf{Z}_i \boldsymbol{\pi} + \nu_i$$ 第二阶段以预测值 $\widehat{\kappa}_i$ 回归通过率 $y_i = \alpha + \beta \widehat{\kappa}_i + u_i$，并通过 Sargan $J$ 统计量 $J = n \cdot R_e^2 \sim \chi^2(5)$ 检验排他性约束。

实验关键数据¶

主实验¶

在由 21 款主流模型（涵盖 Claude Opus 4.6/4.7、GPT-5.4、Gemini 3.1 Pro、DeepSeek V3.2、Kimi K2.5 等）构成的 105,000 次生成基准上，主实验考察了不同控制变量对平均模型断点位置与通过率跳跃幅度的影响：

评估规格与控制变量	估计断点 $\hat{\gamma}$	Sup-Wald 统计量	原始通过率跳跃 ($\Delta$)	控制调整后跳跃 ($\Delta_{\text{adj}}$)	统计显著性 (Bootstrap)
无控制基础模型 (Unadjusted)	14.00	151.2	+6.8%	+6.8%	$p < 0.001$ (0/2000 超限)
加入任务类型固定效应 (Task FE)	14.00	78.6	+6.8%	+0.4%	$p = 0.66$ (非显著)
加入构建数据源框架 (Frame FE)	14.25	88.4	+6.8%	+1.8%	$p = 0.03$
同时加入任务与数据源 (Both)	14.25	51.1	+6.8%	-2.0%	$p = 0.001$ (反转)
任务效应按断点两侧异质分解	11.50	26.9	+2.1%	N/A	$p < 0.001$

消融实验¶

消融与稳健性实验检验了测试判定协议（独立审计、提交版审计与原始测试集）、API 缺失值处理策略，以及工具变量假设的有效性：

评测条件 / 稳健性切片	估计断点 $\hat{\gamma}$	低复杂度通过率	高复杂度通过率	突变方向	关键说明
主评测 (MiMo-V2.6 独立审计)	14.00	83.4%	90.1%	上升 (+6.8%)	修正函数改名等评测环境假阴性
投稿期基线 (o4-mini 局部审计)	13.75	79.9%	87.6%	上升 (+7.6%)	仅覆盖早期框架 2,246 题
原始 Harness 单元测试结果	11.25	76.0%	83.3%	上升 (+7.4%)	未经 LLM 审计的原生执行通过率
Gemini 3.1 Pro (缺失记为失败)	10.75	87.2%	79.3%	下降 (-7.9%)	含 156 次 API 超时与空返回调用
Gemini 3.1 Pro (缺失排除分析)	14.25	85.9%	87.6%	上升 (+1.7%)	排除超时样本后重回正向跃变
Kimi K2.5 (后期框架内独立检验)	14.25	84.8%	80.8%	下降 (-4.0%)	唯一在各定义下均稳健下降的模型
6 维 IV 过度识别 Sargan 检验	N/A	$J=552.16$	$\chi^2(5)$ 自由度	严格拒绝	$p < 10^{-15}$，证伪工具变量有效性

关键发现¶

逆阈值现象在失败样本中尤为突出：在 14,247 次判定失败的生成样本中，有 25.0%（3,561 篇）将高复杂度提示词（$C_i > 8$）写成了圈复杂度 $\le 10$ 的极简残片，充分证实了后置代码度量无法表征真实任务难度。
高难度通过率反弹完全由样本构成混杂所驱动：表面上模型在 $\hat{\gamma}=14.0$ 处通过率提升 6.8 个百分点，实则是因为后期框架中 95.4% 的高复杂度题目集中于规范标准的数据结构算法题，且该框架测试用例质量更规范；加入任务与数据源控制后该反弹彻底消失（降为 -2.0%）。
模型个体可靠性具有异质性：在 21 款模型中，19 款在各自断点上方通过率更高（由题库构成驱动），仅 Kimi K2.5 在后期框架及所有测试定义下均展现出真实的可靠性断崖（通过率从 84.8% 下跌至 80.8%）。
工具变量排他性约束完全破产：六个维度作为 IV 产生的单变量估计符号相互矛盾（如状态与组合为负，数据结构为正），过度识别检验在任意子样本中均被绝对拒绝，说明各结构维度直接影响模型解题机制，而非仅仅通过生成代码圈复杂度产生间接影响。

亮点与洞察¶

解耦测度与生成结果的评估范式：首次形式化定义了代码生成评估中的“逆阈值问题”，通过完全前置的提示词侧六维指标，彻底阻断了模型失败对任务难度度量的污染。
引入门限回归与严格计量检验框架：改变了以往按经验固定切分难度等级的随意性，通过 Hansen 门限检验与野生自举在实证数据中精确定位各模型可靠性转变点。
揭示评测基准构成混杂的警示案例：深入剖析了“越难通过率反而越高”的荒谬现象，清晰展现了数据清洗差异和任务类型倾斜如何伪造出非单调难度曲线，对学术界构建代码基准具有极高的警示价值。

局限与展望¶

基准构造非自然分布：5,000 道题目分两批采样自 OpenCodeInstruct 且进行了分层补充，两批题目在测试质量和基准通过率上存在系统性差异，无法代表现实开发中的自然分布。
高复杂度尾部样本支撑不足：在提示词复杂度高于 16 的区间内样本量仅有几十道，即使后续补充了 365 篇经过清洗的扩展集，极高复杂度区间的表现曲线仍缺乏足够的统计功效。
仅局限于单文件 Python 生成：目前的实证执行与评估主要面向 Python 单函数代码生成，尽管跨语言复评分显示该指标在 Java 与 C++ 上评分稳定，但尚未在多文件仓级别软件工程中实测。

评分¶

新颖性: ⭐⭐⭐⭐ [首次系统形式化逆阈值问题并提出提示词侧六维结构复杂度度量]
实验充分度: ⭐⭐⭐⭐⭐ [覆盖 21 款顶尖模型、10.5 万次生成，结合三套测试审计与详尽计量诊断]
写作质量: ⭐⭐⭐⭐⭐ [严谨客观，直面反常实验现象并以扎实的统计与因果检验逐层揭开真相]
价值: ⭐⭐⭐⭐ [为大模型代码生成评测提供了避免后置偏倚的方法论工具与反混杂示范]