程序合成的"楚河汉界"：Transformers 到底能不能 extrapolate？

> 作者：小凯 | 来源：arXiv:2604.27551v1 [cs.LG] | 机构：GECCO Companion '26 --- ## 一、两个数学问题 先考你两道"数学题"： **问题 A**：已知 2x + 3 = 7，求 x。 **问题 B**：设计一个函数，输入任意整数 n，输出第 n 个斐波那契数。 对于人类来说，A 是"在已学题型里套公式"，B 是"需要构造全新结构"。对于 Transformer 来说，A 和 B 的区别远比我们想象的大——**A 它可能做对了，B 它很可能根本做不出来**。 这就是 **支持泛化（Support Generalization）** vs **密度泛化（Density Generalization）** 的分水岭。 --- ## 二、现有评估的盲区 程序合成领域有个尴尬的事实：主流 benchmark（如 HumanEval、MBPP）的测试集和训练集之间是什么关系，**没人说得清楚**。 - **数据污染**：模型可能在预训练时见过类似题目 - **距离未知**：测试题离训练分布有多远？是"稍微变个花样"还是"全新题型"？不知道 - **黑箱语料**：训练数据不透明，无法系统分析 这就像考试完了，老师告诉你"分数不错"，但不告诉你考的是课本原题还是奥赛题。你不知道自己是真学会了，还是只会背答案。 这篇论文的做法是：**扔掉所有 benchmark，从零造一个完全透明的沙盒**。 --- ## 三、严格控制的实验沙盒 ### 3.1 算术文法：定义程序空间 作者定义了一个上下文无关文法（CFG），生成简单的算术程序。每个程序是输入到输出的映射，可以精确验证对错。 然后，他们**系统性地枚举了数百万个程序**，并构建了两个连续的度量空间： - **语义流形（Semantic Manifold）**：程序在固定输入网格上的输出行为，z-score 标准化后用 PCA 降维 - **句法流形（Syntactic Manifold）**：程序的 AST（抽象语法树），用 PQ-Grams 编码后用 SVD 降维 这两个流形让研究者可以精确回答：**"这道题离训练集有多远？"** ### 3.2 两种泛化：密度 vs 支持 有了度量空间，就可以严格定义两种泛化： **密度泛化（Density Generalization）**：训练集和测试集在同一个"支持集"内，但概率密度分布不同。类比：课本例题多是偶数，考试多考了奇数——题型没变，只是侧重不同。 **支持泛化（Support Generalization）**：测试集完全落在训练集的**支持集之外**。类比：课本只教了加减乘除，考试考了微积分——这是全新的结构，需要外推 extrapolation。 --- ## 四、核心发现：Transformers 的"舒适区"和"死区" ### 4.1 密度泛化：可以教，但有上限 在密度泛化场景下，作者比较了三种训练策略： | 训练策略 | 语义测试 | 句法测试 | 多样化测试 | |---------|---------|---------|----------| | Semantic-only | **30.5%** | ~10% | ~10% | | Syntactic-only | ~15% | ~19% | ~15% | | **Diverse（语义+句法）** | ~19% | ~19% | **~19%** | 三个值得细品的发现： 1. **Semantic-only 在语义测试上最强（30.5%），但跨域崩溃到 10%**。这意味着：如果你只在"语义多样性"上做文章，模型学会了"表达不同意思"，但换种写法就懵。 2. **Diverse 策略在所有测试上稳定 ~19%**。虽然单科不是最高，但**鲁棒性最强**。这验证了一个朴素但重要的原则：**训练数据要在多个维度上都分散开**。 3. **密度泛化的天花板很低**。即使是最好的情况，pass@1 也只有 10%-30%。这说明 transformer 在程序合成上的 in-context learning 能力，远没有人类那么灵活。 ### 4.2 支持泛化：Transformers 的"死穴" 当测试题落在训练集的**支持集之外**时，情况急转直下： - 句法外推（syntactic extrapolation）：**性能下降超过 30%** - 语义外推（semantic extrapolation）：类似幅度的下降 这意味着什么？**Transformers fundamentally 不擅长"创造全新结构"**。它们在训练分布的 convex hull 里 interpolating 很强，但一步跨出这个 hull，就手足无措。 这和人类的直觉相符：给一个学生 1000 道代数题，他可能解得很溜；但如果突然考一道需要构造递推关系的题，他就懵了——因为这不是"在已有题型里变花样"，而是"需要一种他从未见过的问题表征"。 ### 4.3 对数线性扩展定律：Scaling 的残酷真相 作者进一步验证了 scaling law：增大模型规模（22 层到 88 层，hidden dim 64 到 384），性能确实会提升。 但提升的幅度是 **严格对数线性的**。 这意味着：你投入 10 倍的算力，可能只换来不到 2 倍的性能提升。而且，这个规律在 support generalization 上同样成立——**scaling 无法突破结构外推的瓶颈**，它只是把死区里的性能从"很差"提升到"稍微不那么差"。 论文的结论很直接： > "纯神经扩展是不够的。构建鲁棒的、开放式程序合成系统，需要将神经模型与符号搜索或进化技术结合。" --- ## 五、对 LLM 训练的启示 ### 5.1 数据多样性 > 数据量 Diverse 训练策略的表现告诉我们：**在语义和句法两个流形上都分散采样，比在一个维度上追求极致多样性更有效。** 这给实际训练的启示是：不要只追求"更多的代码"，而要追求 **"更多样的代码"**——不同编程语言、不同算法范式、不同抽象层级的代码混合在一起，可能比单一语言的大量代码更有助于泛化。 ### 5.2 支持集边界是可测量的 这篇论文的方法论价值在于：它证明了 **"训练分布的支持集边界"不是玄学，是可以严格测量的**。 通过双流形投影，研究者可以精确计算任意测试题到训练集的距离。这为 future work 打开了一扇门：也许我们可以主动探测模型的"能力边界"，在部署前就知道哪些任务它会做、哪些会崩。 ### 5.3 神经+符号混合的必要性 transformers 在 support generalization 上的失败，不意味着它们没用。恰恰相反，它们在 density generalization 上的表现证明：**transformers 是极好的"已知题型库"** ——在训练分布内，它们能高效地检索和组合已知模式。 但 extrapolation 需要另一种能力：**符号搜索、逻辑推理、结构变换**。这正是遗传编程（Genetic Programming）和神经符号 AI（Neuro-symbolic AI）的领地。 未来的程序合成系统，也许不是"纯 GPT-7"或"纯遗传算法"，而是两者的混合：transformer 负责在已知空间内快速检索候选，符号搜索负责在未知空间外探索新结构。 --- ## 六、一句话总结 这篇论文用严格的数学语言，划清了 transformers 在程序合成中的 **"楚河汉界"**：河这边（密度泛化），它可以高效 interpolating，但天花板低；河那边（支持泛化），它几乎无能为力，scaling 也救不了。 真正学会编程的标志，不是你会做 1000 道变体题，而是你能写出一个从未有人教过你的算法。对 transformers 来说，后者仍然是一座尚未攀登的山。 --- **参考链接** - 论文原文：https://arxiv.org/abs/2604.27551 **标签：** #深度研究 #小凯 #程序合成 #泛化 #Transformer #ScalingLaw #外推 #GECCO