精读笔记

Problem Setting

[Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion]（arXiv preprint / 2026）

这篇论文实际要解决的不是“如何补全一个表”，而是用 Cayley-table completion 构造一个 learning theory 的分离问题：当目标结构的可压缩性来自离散代数公理，而不是连续几何低维性时，现有泛化理论是否从根上失效。

真正困难点在于群表有两种完全冲突的复杂度视角：从矩阵补全看，它通常是线性满秩、没有低秩冗余；从代数看，它被结合律、单位元、逆元和群同构结构强约束，描述长度很低。现有方法卡在把后一种“算法压缩”错误地投影成前一种“几何压缩”，于是 regularization 会奖励错误的结构。

关键矛盾是：现代 deep learning 擅长在连续空间中找 smooth / low-rank / low-norm 解，但 Cayley table 的正确泛化要求恢复 exact symbolic law。近似对称、近似结合、低误差插值都不够；任务要求的是从局部观测推断全局刚性结构。

Motivation

作者的核心观察是：深度学习的很多成功来自几何归纳偏置，但这些偏置并不等价于算法规则发现。matrix completion 之所以是 SLT/optimization 的典范，是因为 nuclear norm 或 factorization + weight decay 可以作为 rank 的连续代理；但 Cayley table 恰好是一个反例：它的规则性不表现为低 rank，而表现为 algebraic consistency。

因此缺口不是“网络不够大”或“训练不够久”，而是 objective 层面没有把 exact discrete axiom 当作低复杂度对象。GDL 中标准网络无法从增强数据自动压缩出精确 weight sharing，是同一个问题的连续版本：模型能拟合对称样本，但不能把样本级规律变成结构级约束。

这也是为什么作者选择 Cayley-table completion 而不是更宽泛的程序学习：它足够小，可以形式化 sample complexity；又足够尖锐，可以让 geometric compression 的失败不可被“实验没调好”掩盖。

Core Idea

核心思想是把 Cayley-table completion 建成 matrix completion 的离散代数对应物，但故意选择一个让低秩假设失效的对象。matrix completion 的成功依赖“低线性秩 = 结构简单”；这里作者要建立的是“低算法复杂度 = 满足代数公理”。如果这个任务能在 O(n log n) 观测下 exact recovery，而所有几何低秩/范数界都给不出非平凡保证，就得到一个清晰的理论分离。

方法上的关键转向是：不再把表看作普通 n×n 矩阵，而是看作三阶结构张量，并用矩阵算子切片 A_a, B_b, C_c 表示元素之间的组合关系。flatness prior 在这个参数化下不是普通意义上的“更平滑泛化更好”，而是变成一种代数复杂度选择器：它偏好那些能由正则表示解释的结构。也就是说，它改变了连续优化中的信息流：从拟合局部 entry，转向寻找能全局一致解释 entry 的 operator algebra。

与 prior 的本质区别在于，它不是把逻辑约束外接到神经网络，也不是用网络引导 symbolic search，而是试图让连续 objective 本身的几何最小值对应 exact algebraic axiom。这是本文最有价值也最冒险的 claim。

Method

1. 结构张量化：把二元运算写为 δ_abc = I[a∘b=c]。这一步解决的是 representation mismatch：普通矩阵视角会把群表误判为高复杂度对象，而三阶张量保留了输入-输入-输出的操作结构。

2. Operator-valued tensor factorization：用 T_abc(Θ)=Tr(A_a B_b C_c)/n 表示表项。它的必要性在于群元素天然可以通过线性算子/正则表示作用，正确结构在该空间中不是低秩矩阵，而是某种 full-rank unitary algebra。核心变化是 inductive bias 从 embedding geometry 转为 operator composition。

3. Hessian trace flatness prior：对经验重构损失的 Hessian trace 做惩罚。普通 flatness 通常只是泛化启发式；这里的特殊点是，在该 factorization 下 flatness infimum 可分解出与 collinearity、inverse L2 相关的变分项，并据称严格诱导结合律和 full-rank unitary structure。

4. 以全局最小值刻画代数复杂度：完全观测时，H_inf(δ) ≥ 3|δ|，且等号当且仅当 operation isotopic to a group。这个结论的作用是给出存在性证明：某个连续可微量确实能区分代数低复杂度结构，而不是只能做近似拟合。

Key Insight / Why It Works

最重要的 insight 是：flatness 的效果完全依赖参数化。一般深度网络里 flat minima 为什么泛化经常含混不清；但在 operator-valued tensor factorization 中，Hessian trace 的变分形式与算子对齐、范数分布、rank pressure 发生耦合，因而可能变成一个精确的代数选择原则。这不是“flatness 普遍有效”，而是“某个 parameterization 下的 flatness 等价于某种 algebraic regularizer”。

真正有效的原因很可能不是 scaling，也不是更多数据覆盖，而是 better inductive bias：把有限群的正则表示放进了可达解空间，并且用 flatness 排除大量仅能局部拟合的非代数解。它更像 representation alignment：参数空间的自然极小值与目标 algebraic structure 对齐。

最可能的核心贡献是 inverse-rank / full-rank unitarity 这一反低秩机制。现代 implicit bias 经常把小范数、低秩、margin 最大化当作泛化来源；本文指出在群表上正确方向恰好相反：需要避免低秩坍缩，走向 full-rank regular representation。这是一个值得迁移的思想：不要默认“简单 = 低维/低秩”，在离散算法域里简单可能意味着“高维但强约束”。

辅助部分是 matrix completion analogy。这个类比很有解释力，但也可能遮蔽问题：Cayley-table completion 与 matrix completion 的统计结构并不只是 rank 换成 associativity；群表存在 Latin-square constraints、同构冗余、元素重标号、生成元覆盖等 combinatorial phenomena。文中未充分说明 O(n log n) 的采样门槛究竟来自信息论、生成集覆盖，还是该 flatness objective 的特殊恢复能力。

需要直接指出：当前文本没有证明部分观测下的 exact recovery，也没有证明优化过程会找到相应 minimizer。因此“gradient descent natively discovers algebraic axioms”在本文中仍是强主张，不是已闭合结论。

Relation To Prior Work

最接近的谱系有三条：matrix completion / implicit regularization、grokking on modular arithmetic / group operations、neurosymbolic learning。

与 matrix completion 的差异最本质：matrix completion 把 rank 作为结构复杂度，factorization + L2 等价于 nuclear norm 代理；本文要找的是 associativity / group isotopy 的连续代理，而且该代理反而推动 full-rank。它不是把现有低秩理论搬到三阶张量，而是在挑战低秩作为普适简单性定义。

与 grokking 工作的关系也很近，尤其是 modular addition、有限群运算从部分样本泛化的现象。但 grokking 多数解释停留在训练动力学、weight decay、representation emergence；本文试图给出一个更结构化的 algebraic complexity functional。看似新的是 Cayley-table completion 的 canonization，实质新增信息是把 flatness infimum 与 group regular representation 的精确刻画联系起来。

与 neurosymbolic 方法相比，本文拒绝两种常见路线：一是 fuzzy/probabilistic logic，把 exact law 软化成连续概率；二是 neural-guided symbolic search，把组合难题交给外部符号引擎。本文的野心是让连续优化本身产生 exact symbolic structure。这个区别是实质性的，但目前只在非常特殊的代数任务上有支撑。

也可以说，这篇文章属于“implicit regularization for algorithmic structure”的技术谱系，而不是传统 program synthesis 或神经符号系统。

Dataset / Evaluation

作为 open problem paper，本文没有独立系统实验；evaluation 主要来自引用的 prior results，包括 Cayley-table completion 的 exact recovery 现象和 fully observed landscape analysis。因此它并没有通过多任务、多场景或真实世界 benchmark 验证 claim。

任务覆盖范围非常窄：有限群/拟群的 Cayley table。这个窄不是缺点，而是刻意设计的理论 testbed；但它不能支持“自动发现广义离散算法公理”的宽 claim。它最多支持一个存在性方向：在某些代数对象上，连续 flatness prior 可能诱导 exact discrete law。

benchmark 是否验证核心 claim？只验证了一部分。它能说明低秩几何先验在群表补全上不合适，也能说明特定 flatness-regularized factorization 经验上有效；但没有证明 formal separation，也没有证明 O(n log n) exact recovery。若后续实验只在小群、循环群、阿贝尔群或采样分布较友好的设置上成立，泛化到非阿贝尔群和复杂代数结构仍可能失败。

没有真实世界/真机 deployment，这本来也不是目标。关键 evaluation 应该是理论恢复界和负结果分离定理，而不是更多表格数字。

Limitation

1. 依赖非常特殊的结构可线性化。有限群能用正则表示进入 operator algebra，这是该方法成立的根。一般算法规则、自动机、程序语义未必有类似的 unitary/full-rank 表示，使 Hessian trace 变成公理选择器。

2. 全局景观结果不等于优化可达性。文中引用的 fully observed infimum characterization 说明正确解在哪里，但不说明有限样本、非凸优化、初始化、噪声下 SGD 是否可靠到达。若需要精心初始化或强 regularization schedule，所谓 native discovery 会弱很多。

3. 样本复杂度核心结论尚未证明。O(n log n) 是 open problem，不是结果。当前最强 claim 只能说“有希望建立”，不能说已经分离 geometric vs algorithmic compression。

4. geometric compression 的失败需要更严谨。说 matrix completion 给 vacuous bound 是合理的，但要证明所有 norm/margin/Rademacher 类几何界都必然 vacuous，需要明确假设空间、观测模型和允许的 representation。否则 separation 容易变成 rhetoric。

5. 增益归因仍可能混杂。经验 exact recovery 可能来自 flatness prior，也可能来自 operator factorization 已经强烈内置了群表示，或者来自采样覆盖了足够生成关系。文中未充分说明不同因素的 ablation。

6. “发现公理”可能只是“匹配已知公理族”。当前机制针对 associativity/group isotopy 设计得很精确；说它能 generalize 到 broader discrete algorithmic axioms，需要新的理论，而不是直接外推。

Takeaway

• 1. 最值得记住的是“低复杂度不等于低秩”。
• 在离散代数任务中，正确归纳偏置可能要求 full-rank 但 algebraically constrained 的表示。
• 2. Cayley-table completion 是一个很好的理论靶子：它小到可以做 sample complexity，大到足以暴露几何泛化理论的盲区。
• 未来如果要证明 neural nets 的 algorithmic generalization，最好先在这种 atomic benchmark 上闭合。

一句话总结

这篇 open problem paper 把 Cayley-table completion 提升为区分 geometric compression 与 algorithmic compression 的标准测试床，真正贡献是指出并形式化一种可能由连续 flatness prior 诱导 exact algebraic structure 的新型归纳偏置。