Abstract:We study transformers' generalization behavior on boolean domains from the perspective of the Fourier spectra of their target functions. In contrast to prior work (Edelman et al., 2022; Trauger & Tosh, 2024), which derived generalization bounds from Rademacher complexity, we investigate the feasibility of obtaining generalization bounds via PAC-Bayes theory. We show that sparse spectra concentrated on low-degree components enable low-sharpness constructions with good generalization properties. Our idea is to show the existence of flat minima implementing any boolean function of sparsity no greater than the context length, and then apply a PAC-Bayes bound to an idealized low-sharpness learner, resulting in a non-vacuous generalization bound. We use this to give a formal account of why chain-of-thought improves generalization for high-degree target functions, and show that the complexity parameters in our bound can be efficiently estimated via property testing. We evaluate predictions empirically and conduct a mechanistic interpretability study to support the realism of our theoretical construction in real transformers.
| Comments: | 10 pages, 9 figures, 41 pages of supplementary material |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2605.20988 [cs.LG] |
| (or arXiv:2605.20988v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.20988 arXiv-issued DOI via DataCite |
From: Paul Lintilhac [view email]
[v1]
Wed, 20 May 2026 10:23:03 UTC (1,209 KB)
[v2]
Tue, 26 May 2026 07:29:50 UTC (1,213 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。