# Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

arXiv: https://arxiv.org/abs/2605.22964 · HTML: https://mlsanity.com/paper/2605.22964/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 21 May 2026.

## Builds on (most cited first, 12 of 12)

- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Transformers in Uniform TC0](https://mlsanity.com/paper/2409.13629/) (2024)
- [Frontier LLMs Still Struggle with Simple Reasoning Tasks](https://mlsanity.com/paper/2507.07313/) (2025)
- [Preference-based Teaching](https://mlsanity.com/paper/1702.02047/) (2017)
- [Bounds in Query Learning](https://mlsanity.com/paper/1904.10122/) (2019)
- [Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes](https://mlsanity.com/paper/1702.05677/) (2017)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (2025)
- [Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks](https://mlsanity.com/paper/2502.16763/) (2025)
- [Exact Learning of Arithmetic with Differentiable Agents](https://mlsanity.com/paper/2511.22751/) (2025)

## Abstract (arXiv)

As state-of-the-art neural networks are deployed on reasoning and algorithmic tasks, exactness guarantees become increasingly important. However, high average-case accuracy can still mask inconsistent behaviors. This motivates exact certification, which asks for the smallest set of labeled examples needed to certify that a learned hypothesis equals the target. We show that while some hypotheses are easy to certify, even minimal overparametrization can make certification exponentially hard across several hypothesis classes. For threshold circuits of depth ≥ 2, adding a single extra gate can force certificate sizes exponential in the input dimension. We show an analogous hardness result for log-precision Transformers with only constant architectural overhead. We also characterize approximate certification, showing that allowing only polynomially many mistakes still requires exponentially large certificates, whereas constant relative-error guarantees can hide exponentially many mistakes. Empirically, we study certification for constructed circuits and trained Transformers for recognizing binary addition. While the constructed circuits instantiate the exponential barrier for certification, the trained Transformer analysis shows that imperfect models can evade detection by large uniformly sampled certificate candidates.