🤖 machine learning

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

This paper demonstrates that even minimal overparametrization in threshold circuits and log-precision Transformers can render exact and approximate certification exponentially hard, a theoretical barrier that is empirically validated by the difficulty of detecting errors in trained models performing binary addition.

Original authors: Artur Back de Luca, Kimon Fountoulakis

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Artur Back de Luca, Kimon Fountoulakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a teacher trying to verify that a student has truly learned a specific math rule, like "how to add two numbers." You have a list of examples (input-output pairs) and you want to be 100% sure the student isn't just guessing or following a trick.

This paper asks a fundamental question: How many examples do you need to show a student to prove they know the exact rule, and not just a very similar one?

The authors, Artur Back de Luca and Kimon Fountoulakis, discovered a surprising and somewhat scary truth: Even a tiny, almost invisible change to the student's "brain" (the model) can make it impossible to prove they are correct, no matter how many examples you show them.

Here is the breakdown of their findings using simple analogies:

1. The "Imposter" Problem

Imagine you have a perfect student who knows the rule for adding numbers. You want to prove they are the only one who knows it.

The Easy Scenario: If the student is the only one in the room, you might only need to show them 5 or 10 examples to prove they know the rule.
The Hard Scenario: Now, imagine you invite 1,000 "imposters" into the room. These imposters are almost perfect. They get the answer right 99.9% of the time. The only time they get it wrong is on a very specific, hidden set of numbers (like numbers that start with the digit '7').

The paper shows that if you add just one extra "neuron" (a tiny bit of extra brain power) to a model, you can create millions of these imposters. Each imposter agrees with the perfect student on almost everything, but they all disagree on a different, tiny, hidden set of numbers.

2. The "Needle in a Haystack" Analogy

To prove the student is the real one and not an imposter, you have to find the specific number where they disagree.

If you have 1,000 imposters, and each one hides their mistake in a different, tiny corner of the universe of numbers, you have to check every single corner to be sure.
The paper proves that if you add just one extra gate to a circuit (or one extra "attention head" to a Transformer AI), the number of these hidden corners explodes.
The Result: To catch all the imposters, you might need to check billions of examples. If you only check a few thousand (a "polynomial" number), you will likely miss the imposters, and the student will pass your test even though they are actually wrong.

3. The Two Main Characters

The authors tested this on two types of "students":

Circuits: Think of these as simple, rigid logic machines (like a calculator). They found that adding just one extra switch to a circuit of depth 2 or more makes it exponentially harder to certify the answer.
Transformers: These are the powerful AI models behind tools like chatbots. The authors showed that adding just one extra attention head (a tiny architectural tweak) and a few extra numbers to the model's memory makes it impossible to certify with a reasonable number of examples.

4. The "Almost Perfect" Trap

You might think, "Okay, but what if we just accept that the student makes a few mistakes? What if we say, 'If they get 99% right, that's good enough'?"
The paper says: Be careful.

Absolute Mistakes: If you say, "You can only make 10 mistakes total," the imposters still hide. You still need billions of examples to find those 10 mistakes because they are scattered across billions of possibilities.
Relative Mistakes: If you say, "You can make 1% mistakes," the imposters can hide millions of errors, as long as that 1% is small enough. The model can be wildly wrong in absolute terms but still pass your "99% accuracy" test.

5. The Real-World Experiment

To prove this isn't just math theory, they actually built these models:

The Circuit Experiment: They built a circuit that adds numbers and then created thousands of "broken" versions that only fail on specific inputs. They showed that even with a huge number of test examples, many of these broken circuits still looked perfect.
The Transformer Experiment: They trained AI models to add numbers. Even after training them until they passed strict validation tests (getting 99.9% right), they found that some models still had hidden errors. When they tried to "audit" these models with random examples, the models kept passing the test even though they weren't actually perfect.

The Bottom Line

The paper concludes that certification is extremely fragile.
If you want to guarantee that an AI or a circuit is doing exactly what you think it's doing, you cannot rely on average performance. If the model has even a tiny bit of "extra capacity" (overparametrization), it can hide an exponential number of ways to be wrong.

To be truly sure, you might need to test the model on a number of examples so large it becomes impossible to do in practice. It's like trying to prove a magician isn't cheating by watching them perform a trick a few times; if they have a secret extra card in their sleeve, you might never see it unless you check every single card in the deck.

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

Problem Statement

As state-of-the-art neural networks are increasingly deployed on reasoning and algorithmic tasks, ensuring their exact correctness becomes critical. High average-case accuracy often masks inconsistent behaviors, making it difficult to detect failures that deviate from the intended reasoning logic. This paper addresses the problem of exact certification: determining the minimum number of labeled input-output examples required to uniquely identify a target hypothesis $f^*$ within a hypothesis class $\mathcal{H}$ , such that no other hypothesis in $\mathcal{H}$ agrees with $f^*$ on the entire domain.

The central question is how sensitive this certification complexity is to the size of the surrounding hypothesis class. Specifically, the authors investigate whether a minimal enlargement of the hypothesis class (e.g., adding a single gate or a constant number of parameters) can render certification exponentially harder, even for targets that were previously easy to certify.

Methodology

The paper employs a theoretical framework rooted in teaching complexity and circuit complexity, complemented by empirical validation on binary addition tasks.

Theoretical Framework

Certificate Size Definition: The authors define the certificate size, $\text{cert}(f^*, \mathcal{H})$ , as the minimum size of a labeled sample $S$ such that the version space $V_S^{\mathcal{H}}$ (the set of hypotheses in $\mathcal{H}$ consistent with $S$ ) contains only $f^*$ .
Disjoint-Disagreement Principle: The core proof strategy relies on constructing a set of "deceiver" hypotheses. For a target $f^*$ $f^{*}$ , the authors construct a family of hypotheses $\{g_\pi\}$ ${g_{π}}$ that agree with $f^*$ $f^{*}$ everywhere except on specific, pairwise disjoint "trigger blocks" $B_\pi$ $B_{π}$ .
- If a hypothesis class contains such a family of deceivers where the disagreement sets are disjoint, any exact certificate must contain at least one example from every disagreement set.
- Consequently, the certificate size is lower-bounded by the number of such disjoint blocks.
Overparametrization Analysis: The authors analyze how adding minimal capacity (e.g., one extra gate in circuits, one extra attention head and constant embedding width in Transformers) allows the construction of these exponential families of deceivers for every target in the original, smaller class.

Empirical Analysis

The authors complement the theory with two experiments on binary addition recognition:

Constructed Circuits: They instantiate the theoretical deceiver construction for threshold circuits ( $TC_0$ ) recognizing addition. They generate a set of $2^n$ incorrect circuits, each differing from the target on a distinct block of inputs, and measure how many survive uniform sampling of certificate candidates.
Trained Transformers: They train encoder-only Transformers on 10-bit addition. After selecting models that pass strict validation checks (99.9% accuracy), they evaluate them on a large held-out test set. They analyze the "survival" of these imperfect models (deceivers) when subjected to uniformly sampled certificate candidates, testing whether residual errors can be detected with polynomial-sized samples.

Key Contributions and Results

1. Exponential Hardness from Minimal Overparametrization

The primary theoretical contribution is demonstrating that certification is highly sensitive to the hypothesis class size.

Threshold Circuits ( $TC_0$ ): For circuits of depth $d \ge 2$ , adding a single extra threshold gate (increasing the gate budget from $s$ to $s+1$ ) forces the certificate size for every target in the original class $TC_{d,s}$ to become exponential in the input dimension $n$ . Specifically, $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$ .
Transformers: For log-precision Transformers with averaging hard attention (AHAT), adding one attention head in the final layer and six auxiliary embedding/residual coordinates creates an enlarged class where certification becomes exponentially hard. Even if a target $f^*$ has a polynomial certificate size in the smaller architecture, it requires an exponential number of examples to certify against the slightly larger architecture.
Non-Vacuity: The authors prove that these lower bounds are not vacuous. They show that the smaller classes ( $TC_{d,s}$ and standard Transformers) contain targets with polynomial certificate sizes (specifically $O(\log |\mathcal{H}|)$ ), yet these same targets become exponentially hard to certify once the class is minimally enlarged.

2. Approximate Certification Hardness

The paper extends these results to approximate certification:

Absolute Error Tolerance: If the certification allows only a polynomial number of mistakes ( $R = \text{poly}(n)$ ), the certificate size remains exponential ( $2^{\Omega(n)}$ ).
Relative Error Tolerance: If the certification allows a constant relative error ( $\epsilon$ ), the certificate size can be small (polynomial in $1/\epsilon$ ). However, this comes at the cost of allowing exponentially many absolute mistakes. The authors show that constant relative-error guarantees can hide exponentially many errors, whereas polynomial absolute-error guarantees still require exponential certificates.

3. Empirical Validation

Circuit Experiments: The constructed $TC_0$ deceivers confirmed the theoretical barrier. Even with polynomial-sized certificate candidates, almost all constructed deceivers remained consistent with the sampled labels, requiring exponential sampling to eliminate them.
Transformer Experiments: Among 150 trained models that passed extensive validation, 63 had residual errors on the held-out test set. The analysis showed that even with a targeted subset of error-rich examples, uniformly sampled certificate candidates of polynomial size failed to eliminate all non-exact hypotheses. Imperfect models could evade detection by large, uniformly sampled candidates.

Significance and Claims

The paper claims to provide a quantitative form of certification hardness for exact learning. Its significance lies in the following assertions:

Sensitivity to Model Capacity: Certification is not merely a property of the target function but is critically dependent on the "ambient" hypothesis class. A minimal increase in model capacity (constant overhead) can fundamentally alter the difficulty of verifying a model's correctness.
Limitations of Passive Certification: In passive settings (where examples are sampled without querying the model), polynomial-sized datasets are insufficient to certify that a model has learned the intended computation if the hypothesis class is slightly overparametrized.
Distinction from Learnability: The results highlight a gap between learnability and certification. While a function might be learnable (or have a small certificate in a restricted class), certifying it against a slightly larger class may be intractable.
Implications for Reasoning Models: For models deployed on algorithmic tasks (like addition), high validation accuracy does not guarantee exactness. The paper suggests that without stronger protocols (e.g., active learning or specific queries), large uniformly sampled datasets may fail to detect subtle, structured inconsistencies in reasoning models.

The authors conclude that while exact certification is a foundational challenge, the barrier is not just a worst-case anomaly but a structural consequence of minimal overparametrization in classes relevant to modern reasoning tasks. They suggest that future work should explore active certification protocols to potentially overcome these passive barriers.