覆盖原理：组合泛化的理论框架

1. 引言

组合泛化（Compositional Generalization）是人工智能的核心挑战之一：模型能否理解从未见过的概念组合？尽管现代Transformer在许多任务上表现出色，但它们在系统性的组合泛化上仍然失败。

覆盖原理（Coverage Principle）提供了一个理论框架，解释了这种失败的根本原因：当泛化仅依赖模式匹配时，覆盖（Coverage）—— 即训练数据通过功能等价替换能触及的输入范围——决定了泛化的边界。¹

2. 功能k-等价

2.1 基本定义

定义（功能等价）：两个片段 $a, a^{'} \in X^{∣ I ∣}$ 是功能等价的，如果它们在所有共享上下文中产生相同的输出：

f (x_{1}, \dots, x_{n}) = f (x_{1}^{'}, \dots, x_{n}^{'}) 当 x_{I} = a, x_{I}^{'} = a^{'}

这意味着我们无法通过观察输入-输出对来区分 $a$ 和 $a^{'}$ 。

2.2 功能k-等价

定义（功能k-等价）：对于正整数 $k$ ，片段 $a, a^{'}$ 是功能k-等价的，如果在所有最多k个位置不同的上下文中，它们产生相同输出。

这个定义捕捉了局部功能依赖的概念——片段在不同上下文中的行为可能不同，但在有限上下文下可能无法区分。

2.3 示例

考虑一个简单的字符串处理函数：

f (x_{1} x_{2} \dots x_{n}) = x_{1} + x_{2}

对于输入 $a = ab$ 和 $a^{'} = c d$ ：

在上下文 $f (__)$ 中， $a$ 和 $a^{'}$ 功能等价（都产生 $a + b$ 和 $c + d$ ，但不相等）
它们不是功能1-等价的，因为改变上下文（如 $f (_b)$ ）可能产生不同结果

3. 替换图与覆盖集

3.1 替换图的构建

基于功能 $k$ -等价，可以构建一个替换图 $G_{k} (X^{n})$ ：

顶点：所有可能的输入 $x \in X^{n}$
边：如果 $x$ 和 $y$ 仅在功能 $k$ -等价的片段上不同，则在 $x$ 和 $y$ 之间添加边

直观上，替换图连接了可以通过局部替换相互转换的输入。

3.2 覆盖集

定义（覆盖集）：给定训练数据 $D \subseteq X^{n}$ ，覆盖集是替换图中与 $D$ 中某点连通的所有节点：

Coverage_{k} (D) = {x \in X^{n} : \exists y \in D 使得 x 与 y 在 G_{k} 中连通}

覆盖集包含：

训练数据 $D$ 本身
所有可以通过有限次功能 $k$ -等价替换到达的输入

3.3 覆盖边界

覆盖原理的核心观点：

覆盖是模式匹配泛化的必要条件。当预测仅依赖模式匹配时，模型在覆盖集之外的预测变得不可靠。

这意味着：

如果测试输入不在覆盖集中，模型缺乏”经验基础”进行泛化
增加训练数据会扩大覆盖集
模型规模不影响覆盖集大小

4. 数据规模要求

4.1 主要结果

定理（数据规模下界）：对于可靠的二跳组合泛化，训练数据规模至少与令牌集大小的平方成正比：

∣ D ∣ \geq Ω (k^{2})

其中 $k = ∣ X ∣$ 是令牌集大小。

这个二次方下界是严格的——无法通过改进架构或增加模型规模来规避。

4.2 证明直觉

考虑一个二跳组合任务：

f (x_{1}, x_{2}, \dots, x_{n}) = g (h (x_{i_{1}}, \dots, x_{i_{k}}), h (x_{j_{1}}, \dots, x_{j_{k}}))

为了泛化到新的组合 $(a^{'}, b^{'})$ ，需要：

至少观察到 $a$ 在第一个位置和 $b$ 在第二个位置
至少观察到 $a^{'}$ 和 $b^{'}$ 分别出现在某些位置

对于 $k$ 个令牌的集合，组合数为 $k^{2}$ ，因此需要 $Ω (k^{2})$ 规模的训练数据。

4.3 实验验证

研究团队训练了参数量从1M到20M不等的模型，测试了不同训练数据规模下的泛化性能。结果显示：

参数量	20x规模	泛化改善
1M	20x	无显著改善
10M	20x	无显著改善
20M	20x	无显著改善

关键发现：20倍的参数增长没有改善训练数据效率，验证了数据规模下界的理论预测。

5. 三种泛化机制

覆盖原理揭示了三种不同的组合泛化机制：

5.1 Structure-based（基于结构）

定义：模型通过识别输入的功能结构进行泛化，即利用功能 $k$ -等价。

特点：

受覆盖集限制
需要覆盖所有相关功能组合
是模式匹配的精确形式

示例：SCAN任务的某些版本，其中组合规则是透明的。

5.2 Property-based（基于属性）

定义：模型利用属性不变性进行泛化，即识别哪些操作具有哪些属性。

特点：

不受覆盖集限制
可以泛化到全新组合
需要对操作有更深层的理解

示例：利用”加法交换律”泛化到任意顺序的加法。

5.3 Shared-operator（共享操作符）

定义：模型在不同位置重用相同的操作实现。

特点：

部分受覆盖集限制
允许位置无关的泛化
是Transformer注意力的天然形式

示例：相同的注意力头在不同位置处理相同类型的输入。

5.4 对比表

机制	覆盖限制	泛化范围	可解释性
Structure-based	强	受限	高
Property-based	弱	广泛	中
Shared-operator	中	中等	低

6. 路径歧义问题

6.1 问题的定义

当一个变量影响输出通过多条计算路径时，会产生路径歧义：

z = h_{1} (x) = h_{2} (x) = \dots = h_{m} (x)

如果 $h_{1}, h_{2}$ 是不同的函数但计算结果相同，模型面临歧义。

6.2 对组合泛化的影响

关键发现：路径歧义会破坏所有三种泛化机制：

Structure-based：无法唯一识别哪个路径对应哪个片段
Property-based：无法分离不同操作的属性
Shared-operator：上下文依赖导致不一致的操作实现

6.3 链式思维的困境

链式思维（Chain-of-Thought）在标准组合任务上有效，但在路径歧义任务上失败：

标准任务：链式思维提高数据效率
路径歧义任务：链式思维无法解决根本问题

这暗示链式思维可能通过增强Structure-based泛化（更清晰地分解结构）来工作，而非引入Property-based泛化。

7. 解释性挑战

7.1 标准解释方法的失效

对于路径歧义任务，标准解释技术失效：

Logit Lens：基于激活解码，但激活在歧义场景下不可靠
注意力可视化：显示相关性而非因果关系
特征归因：无法区分多条等效路径的贡献

7.2 因果解释的需求

路径歧义问题表明，组合泛化研究需要因果解释方法，而非相关性方法。

8. 实践建议

8.1 任务设计

避免路径歧义：如果可能，重新设计任务消除歧义
明确属性：在训练数据中明确标注功能属性
层次结构：使用层次化标签帮助模型学习结构

8.2 数据策略

覆盖优先：确保训练数据覆盖关键功能组合
数据增强：主动构造功能等价样本扩大覆盖
平衡采样：避免某些组合过度稀疏

8.3 架构选择

任务类型	推荐架构
结构透明	Transformer + 链式思维
属性丰富	符号推理增强模型
路径歧义	需要新的泛化机制

9. 与其他理论的关系

9.1 与组合零样本泛化的联系

覆盖原理与组合零样本泛化（Compositional Zero-Shot Generalization）密切相关：

覆盖集为空 ⇒ 无法零样本泛化
覆盖集非空但不包含目标 ⇒ 需要额外泛化机制

9.2 与覆盖测试的关系

覆盖原理提供了覆盖测试（Coverage Testing）的理论基础：

def compute_coverage_set(training_data, k, equivalence oracle):
    """
    计算训练数据的k阶覆盖集
    
    Args:
        training_data: 训练样本集合
        k: 功能k-等价的阶数
        equivalence_oracle: 判断功能k-等价的预言机
    
    Returns:
        coverage: 覆盖集
    """
    from collections import deque
    
    # 构建替换图
    graph = {}
    all_inputs = set()
    
    for x in training_data:
        all_inputs.update(generate_substitutions(x, k))
    
    # BFS扩展覆盖集
    queue = deque(training_data)
    visited = set(training_data)
    
    while queue:
        current = queue.popleft()
        for neighbor in get_neighbors(current, equivalence_oracle):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited
 
def check_generalization(test_input, coverage_set):
    """检查测试输入是否在覆盖集中"""
    return test_input in coverage_set

9.3 与系统泛化能力的联系

覆盖原理与系统泛化能力（Systematic Generalization）的关系：

系统泛化需要超越覆盖集
需要Property-based或其他新型泛化机制
当前Transformer主要依赖Structure-based泛化

10. 开放问题与未来方向

10.1 理论问题

覆盖集的精确计算：如何在没有完备预言机的情况下估计覆盖集？
混合机制泛化：当多个机制同时作用时，泛化边界如何确定？
覆盖与泛化的量化关系：能否建立从覆盖度到泛化误差的定量不等式？

10.2 实践问题

覆盖集估计：如何从有限数据估计覆盖集？
任务设计原则：如何设计避免路径歧义的任务？
架构创新：如何设计超越模式匹配的架构？

10.3 认知科学联系

覆盖原理与认知科学中的组合性研究相关：

人类如何实现系统性组合泛化？
儿童如何学习抽象规则？
覆盖原理是否描述了人类认知的某些方面？

11. 总结

覆盖原理为理解组合泛化提供了清晰的理论框架：

核心概念：功能 $k$ -等价和替换图定义了覆盖集
关键结果：二次方数据规模下界（ $Ω (k^{2})$ ）是模式匹配的硬限制
三种机制：Structure-based、Property-based、Shared-operator提供了泛化机制的分类
路径歧义：揭示了模式匹配的根本局限

覆盖原理的实践意义在于：

指导任务设计避免已知的泛化陷阱
为数据收集提供理论指导
揭示需要架构创新的方向

Chang, H., et al. “The Coverage Principle: A Framework for Understanding Compositional Generalization.” arXiv 2025. https://arxiv.org/abs/2505.20278 ↩

Metaphor

探索