Research map / Architectures and efficiency / Attention and transformers

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

NeurIPS 2026 · Architectures and efficiency › Attention and transformers · approach: Transformer expressivity and learnability · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that minimal overparametrization (one extra threshold gate, or one extra attention head plus constant width in log-precision AHAT Transformers) makes exact certification by labeled examples exponentially hard, with approximate-certification bounds and binary-addition experiments.

Problem

How many labeled input-output examples are needed to certify from behavior alone that a learned hypothesis equals the target, and how this certificate size depends on the surrounding hypothesis class (threshold circuits, AC0, NC1, log-precision Transformers).

Approach

Certificate size is highly sensitive to the ambient class: for any target in a smaller class, adding one gate or one attention head allows constructing exponentially many deceivers supported on disjoint trigger blocks, forcing any certificate to hit every block (disjoint-disagreement principle).

Key results

• Among 150 accepted trained Transformers for 10-bit addition, 87 are test-exact and 63 have residual test errors, which are treated as deceivers.
• For constructed threshold-circuit deceivers, almost all 2^n deceivers survive polynomial-size uniform certificate candidates, with decay visible only on an exponential scale in n.
• Theory: for TC0 targets in class of depth d>=2, cert(f, TC0_{d,s+1}) >= 2^t for any trigger length t, giving 2^{Omega(n)} with t=Theta(n); analogous Transformer bound holds with one extra head and six auxiliary coordinates.

Surprising findings

• Even polynomially many examples leave multiple trained non-exact Transformers consistent with sampled labels, even after validation accuracy of 99.9%.
• Targeting a compact error-rich subset helps but uniformly sampled certificate candidates remain large; deceivers with errors outside the subset survive every compact subset sample.

Limitations

• Transformer result uses an idealized log-precision AHAT abstraction rather than deployed Transformers.
• Trained-Transformer analysis tests survival over a finite set of 63 deceivers, not the full class's minimum certificate size.
• Approximate-certification lower bounds shrink with fixed relative tolerance, so constant-error guarantees remain weak.

Experimental setup

Datasets: 10-bit binary addition operand pairs with correct sums and one-bit flips

Benchmarks: held-out binary addition test set (10-bit, 3,145,728 examples)

Metrics: expected number of surviving deceivers under uniformly sampl test exactness (zero mistakes on held-out set)

Builds on: teaching dimension / teaching sets AHAT (average hard attention transformers) threshold circuit simulation of log-precision transformers

Closest papers by meaning

• Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees (ICLR 2026 · similarity 0.86)
• Certified but Private: Scalable Zero-Knowledge Proofs for the Formal Verification of Neural Networks (NeurIPS 2026 · similarity 0.85)
• Neural Model Checking (NeurIPS 2024 · similarity 0.85)
• Et Tu Certifications: Robustness Certificates Yield Better Adversarial Examples (ICML 2024 · similarity 0.84)
• Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (ICML 2025 · similarity 0.83)
• Algorithmic Capabilities of Random Transformers (NeurIPS 2024 · similarity 0.83)