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

# Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
Source: [https://arxiv.org/html/2605.22964](https://arxiv.org/html/2605.22964)
###### Abstract

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\\geq 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\.

## 1Introduction

Frontier models can tackle a wide range of tasks, yet studies have revealed inconsistencies in reasoning and algorithmic settings\[[25](https://arxiv.org/html/2605.22964#bib.bib25),[20](https://arxiv.org/html/2605.22964#bib.bib20)\]\. Even when a model achieves high average\-case accuracy, such inconsistencies suggest that it may fail to implement the intended reasoning behavior, and these failures are difficult to detect from average\-case evaluation alone\.

This motivates a broader exact certification question: after a learner returns a candidate hypothesis, how many labeled input\-output examples are needed to certify, from behavior alone, that the candidate equals the intended target?György et al\. \[[14](https://arxiv.org/html/2605.22964#bib.bib14)\]flag this certification problem as a foundational challenge for the exact\-learning setting, illustrating the worst\-case certification in a bit comparison task\. In this work, we give a quantitative form of certification hardness, mainly focusing on two formal hypothesis classes closely related to reasoning and computation\.

Because certification uses only labeled input\-output data, we formalize the question using a perspective closely related to the teaching set literature\[[4](https://arxiv.org/html/2605.22964#bib.bib4),[29](https://arxiv.org/html/2605.22964#bib.bib29),[13](https://arxiv.org/html/2605.22964#bib.bib13)\]\. The key quantity for our purposes is the certificate size, namely the minimum number of labeled examples needed to uniquely identify a target within a hypothesis class\. This quantity depends not only on the target but also on the surrounding class\. Our main observation is that even a minimal enlargement of the hypothesis class, increasing model capacity by only a constant factor, can make certification exponentially hard for every target in the original class, even when some targets originally admit small certificates\.

##### Contributions\.

Our contributions are as follows\.

1. 1\.We provide a quantitative form of hardness for exact certification by examples\. We show that certification can be highly sensitive to the surrounding hypothesis class\. Even a constant enlargement can make certification exponentially hard for every target in the original class, despite the presence of targets with small certificates in that class\. We instantiate this phenomenon in two settings related to algorithmic computation\. 1. \(a\)In the circuit setting, we study unbounded fan\-in classes such asTC0\\mathrm\{TC\}^\{0\}andAC0\\mathrm\{AC\}^\{0\}, together with the bounded fan\-in classNC1\\mathrm\{NC\}^\{1\}\. Our sharpest result is forTC0\\mathrm\{TC\}^\{0\}, where circuits of depthd≥2d\\geq 2with a single additional gate already force certification to require exponentially many examples in the input dimension\. 2. \(b\)In the Transformer setting, motivated by connections between Transformers and circuit complexity\[[15](https://arxiv.org/html/2605.22964#bib.bib15),[24](https://arxiv.org/html/2605.22964#bib.bib24),[21](https://arxiv.org/html/2605.22964#bib.bib21),[23](https://arxiv.org/html/2605.22964#bib.bib23),[9](https://arxiv.org/html/2605.22964#bib.bib9)\], we study projected\-pre\-norm log\-precision Transformers with averaging hard attention \(AHAT\)\[[15](https://arxiv.org/html/2605.22964#bib.bib15),[23](https://arxiv.org/html/2605.22964#bib.bib23)\]\. We show that a slight overparametrization with one extra attention head and six auxiliary embedding/residual coordinates already makes certification hard\. 3. \(c\)We extend the hardness analysis to approximate certification\. We show that allowing only polynomially many absolute mistakes still requires exponentially large certificates, while constant relative\-error guarantees may still allow exponentially many absolute mistakes\.
2. 2\.We complement the theory with two empirical certification analyses for the task of recognizing binary addition\. First, we construct aTC0\\mathrm\{TC\}^\{0\}circuit for recognizing addition, together with a collection of incorrect circuits, each agreeing with the target except on a different block of inputs\. We then compute how many of these circuits remain consistent with a uniformly sampled certificate candidate\. Second, we study Transformers trained to recognize binary addition\. After selecting trained models that pass extensive validation checks, we evaluate them on a large held\-out test set\. We observe that even polynomial\-sized certificate candidates can leave multiple non\-exact trained hypotheses consistent\.

## 2Related work

Our certification setting is most closely related to the classical teaching complexity literature\[[4](https://arxiv.org/html/2605.22964#bib.bib4),[29](https://arxiv.org/html/2605.22964#bib.bib29),[13](https://arxiv.org/html/2605.22964#bib.bib13)\]\. Subsequent work develops a range of teacher\-learner protocol variants\[[30](https://arxiv.org/html/2605.22964#bib.bib30),[11](https://arxiv.org/html/2605.22964#bib.bib11),[12](https://arxiv.org/html/2605.22964#bib.bib12)\]and relates teaching parameters to structural properties of the hypothesis class, such as class complexity\[[11](https://arxiv.org/html/2605.22964#bib.bib11),[8](https://arxiv.org/html/2605.22964#bib.bib8),[19](https://arxiv.org/html/2605.22964#bib.bib19)\]\. In the circuit setting, the closest work isServedio \[[28](https://arxiv.org/html/2605.22964#bib.bib28)\], who proves worst\-case exponential lower bounds on the size of certificates for polynomial\-size monotone circuits using input\-output examples alone\. The main distinction is that our lower bounds do not isolate a single worst\-case target\. This distinction is sharpest in our threshold\-circuit result in[Theorem˜4\.1](https://arxiv.org/html/2605.22964#S4.Thmtheorem1), which shows that for every target in a smaller threshold\-circuit class, adding one same\-depth gate already makes exact certification exponentially hard\.

Related to certification by examples is exact learning, which often studies active, query\-based interaction between a learner and an oracle, including membership queries, equivalence queries, and related oracle access\[[1](https://arxiv.org/html/2605.22964#bib.bib1),[2](https://arxiv.org/html/2605.22964#bib.bib2),[3](https://arxiv.org/html/2605.22964#bib.bib3),[16](https://arxiv.org/html/2605.22964#bib.bib16),[18](https://arxiv.org/html/2605.22964#bib.bib18),[7](https://arxiv.org/html/2605.22964#bib.bib7)\]\. A central theme in this literature is that learnability depends both on the interaction model and on the hypothesis class the learner may output\. For example, proper and improper learning of DNFs exhibit different learnability behavior\[[27](https://arxiv.org/html/2605.22964#bib.bib27),[17](https://arxiv.org/html/2605.22964#bib.bib17)\], while richer oracle access can make circuit learning tractable\[[6](https://arxiv.org/html/2605.22964#bib.bib6)\]\. In our input\-output\-only certification setting, we isolate the role of the hypothesis class and show that even a small enlargement of the class can make certification hard\.

In the context of neural networks, several recent works advocate for exact guarantees, rather than average\-case accuracy alone, as a foundation for reliable reasoning and algorithmic behavior\[[14](https://arxiv.org/html/2605.22964#bib.bib14),[10](https://arxiv.org/html/2605.22964#bib.bib10),[26](https://arxiv.org/html/2605.22964#bib.bib26)\]\. In particular,György et al\. \[[14](https://arxiv.org/html/2605.22964#bib.bib14)\]emphasizes both the importance and the challenge of certifying exact correctness\. Our work builds on this perspective by quantifying the size of certificates needed for log\-precision Transformers\. Most theoretical work on log\-precision Transformers has focused on expressive power, whose computation is captured by threshold\-circuit models\[[24](https://arxiv.org/html/2605.22964#bib.bib24),[21](https://arxiv.org/html/2605.22964#bib.bib21),[23](https://arxiv.org/html/2605.22964#bib.bib23),[22](https://arxiv.org/html/2605.22964#bib.bib22),[9](https://arxiv.org/html/2605.22964#bib.bib9)\]\. While these results characterize what such models can compute, our results address the complementary question of how many input\-output examples are needed to certify their behavior\. We show that certifying log\-precision Transformers within a slightly overparametrized class requires exponentially many examples in the input size, even for exact and near\-exact certification\.

## 3Preliminaries and notation

In this section, we introduce the notation and background definitions used throughout the paper\. We write\[n\]\[n\]to indicate the set\{1,2,…,n\}\\\{1,2,\\dots,n\\\}\. For a vectorx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}and an index setI⊆\[n\]I\\subseteq\[n\], we writexIx\_\{I\}for the restriction ofxxto the coordinates indexed byII\. For a finite setSS, we let\{0,1\}S=\{π:S→\{0,1\}\}\\\{0,1\\\}^\{S\}=\\\{\\pi:S\\to\\\{0,1\\\}\\\}denote the set of binary patterns onSS\.

Circuit complexity and circuit classes\.We use circuits as finite semantic hypothesis classes because they let us measure how much computational power is added by one or a few gates\. Circuits also connect directly to the Transformer result, since log\-precision Transformer expressivity is commonly compared with threshold\-circuit computation\[[24](https://arxiv.org/html/2605.22964#bib.bib24),[23](https://arxiv.org/html/2605.22964#bib.bib23)\]\.

A Boolean circuit on inputsx1,…,xnx\_\{1\},\\ldots,x\_\{n\}is a directed acyclic graph with input nodes, internal gates, and one output gate\. Its size\|C\|\|C\|is the number of non\-input gates, and its depth is the length of the longest input\-to\-output path\. At polynomial size, the standard containments are

AC0⊊TC0⊆NC1\.\\mathrm\{AC\}^\{0\}\\subsetneq\\mathrm\{TC\}^\{0\}\\subseteq\\mathrm\{NC\}^\{1\}\.HereAC0\\mathrm\{AC\}^\{0\}consists of constant\-depth circuits with unbounded\-fan\-in AND/OR gates over input literals,TC0\\mathrm\{TC\}^\{0\}adds constant\-depth threshold gates, andNC1\\mathrm\{NC\}^\{1\}allows bounded\-fan\-in circuits of logarithmic depth\. The first containment is strict, while strictness of the second is open\.

For finite gate budgets,ACd,s0\\mathrm\{AC\}^\{0\}\_\{d,s\}andTCd,s0\\mathrm\{TC\}^\{0\}\_\{d,s\}denote thenn\-input functions computable by depth\-dd, size\-sscircuits of the corresponding type\. InTCd,s0\\mathrm\{TC\}^\{0\}\_\{d,s\}, a threshold gate is defined asTHRw,θ​\(z\)=𝟏​\[∑iwi​zi≥θ\]\\mathrm\{THR\}\_\{w,\\theta\}\(z\)=\\mathbf\{1\}\[\\sum\_\{i\}w\_\{i\}z\_\{i\}\\geq\\theta\], withwi,θ∈ℤw\_\{i\},\\theta\\in\\mathbb\{Z\}\. ForTC0\\mathrm\{TC\}^\{0\}, the class can also be expressed using Boolean disjunctions/conjunctions and majority gates\. All of these gates can be expressed as a threshold gate, but the converse simulation can change the finite gate budget, so the statedTC0\\mathrm\{TC\}^\{0\}bounds should be read under the threshold gate convention\. The classNCs1\\mathrm\{NC\}^\{1\}\_\{s\}denotes bounded\-fan\-in Boolean circuits of size at mostssand depth at mostcNC1​log⁡\(n\+1\)c\_\{\\mathrm\{NC\}^\{1\}\}\\log\(n\+1\), for a fixed constantcNC1c\_\{\\mathrm\{NC\}^\{1\}\}\.

Input\-output certificates\.All certificates are over a fixed finite domain𝒳\\mathcal\{X\}\. Fix a hypothesis classℋ\\mathcal\{H\}and a targetf⋆∈ℋf^\{\\star\}\\in\\mathcal\{H\}\. We record a labeled sample by its input setS⊆𝒳S\\subseteq\\mathcal\{X\}where the corresponding labels attached tox∈Sx\\in Saref⋆​\(x\)f^\{\\star\}\(x\)\. The version space after seeingSSis

VSf⋆,ℋ​\(S\):=\{h∈ℋ:h​\(x\)=f⋆​\(x\)​for every​x∈S\}\.\\mathrm\{VS\}\_\{f^\{\\star\},\\mathcal\{H\}\}\(S\):=\\\{h\\in\\mathcal\{H\}:h\(x\)=f^\{\\star\}\(x\)\\text\{ for every \}x\\in S\\\}\.The setSSis an input\-output certificate forf⋆f^\{\\star\}inℋ\\mathcal\{H\}if every surviving hypothesis agrees withf⋆f^\{\\star\}on the full domain:

∀h∈VSf⋆,ℋ​\(S\),h​\(x\)=f⋆​\(x\)​for every​x∈𝒳\.\\forall h\\in\\mathrm\{VS\}\_\{f^\{\\star\},\\mathcal\{H\}\}\(S\),\\qquad h\(x\)=f^\{\\star\}\(x\)\\text\{ for every \}x\\in\\mathcal\{X\}\.The certificate size is

cert⁡\(f⋆,ℋ\):=min⁡\{\|S\|:S⊆𝒳​and​S​is an input\-output certificate for​f⋆​in​ℋ\}\.\\operatorname\{cert\}\(f^\{\\star\},\\mathcal\{H\}\):=\\min\\Bigl\\\{\|S\|:S\\subseteq\\mathcal\{X\}\\text\{ and \}S\\text\{ is an input\-output certificate for \}f^\{\\star\}\\text\{ in \}\\mathcal\{H\}\\Bigr\\\}\.SinceS=𝒳S=\\mathcal\{X\}is a certificate, this minimum is well defined\. The definition is semantic\. It certifies the input\-output behavior of the target and does not distinguish hypotheses that behave identically on𝒳\\mathcal\{X\}\. This is the usual teaching/specification notion\[[29](https://arxiv.org/html/2605.22964#bib.bib29),[13](https://arxiv.org/html/2605.22964#bib.bib13),[4](https://arxiv.org/html/2605.22964#bib.bib4)\]\.

Approximate certificates\.Keep the same finite domain𝒳\\mathcal\{X\}, hypothesis classℋ\\mathcal\{H\}, and targetf⋆f^\{\\star\}\. Forh∈ℋh\\in\\mathcal\{H\}, define its absolute and normalized errors relative tof⋆f^\{\\star\}by

Δ​\(h\):=\|\{x∈𝒳:h​\(x\)≠f⋆​\(x\)\}\|,err​\(h\):=Δ​\(h\)\|𝒳\|\.\\Delta\(h\):=\|\\\{x\\in\\mathcal\{X\}:h\(x\)\\neq f^\{\\star\}\(x\)\\\}\|,\\qquad\\mathrm\{err\}\(h\):=\\frac\{\\Delta\(h\)\}\{\|\\mathcal\{X\}\|\}\.Forρ∈\{Δ,err\}\\rho\\in\\\{\\Delta,\\mathrm\{err\}\\\}, the worst remaining error after seeingSSis

Mρ​\(S\):=maxh∈VSf⋆,ℋ​\(S\)⁡ρ​\(h\)\.M\_\{\\rho\}\(S\):=\\max\_\{h\\in\\mathrm\{VS\}\_\{f^\{\\star\},\\mathcal\{H\}\}\(S\)\}\\rho\(h\)\.Forε,R≥0\\varepsilon,R\\geq 0, the approximate certificate sizes are

certε⁡\(f⋆,ℋ\):=min⁡\{\|S\|:S⊆𝒳​and​Merr​\(S\)≤ε\},\\operatorname\{cert\}\_\{\\varepsilon\}\(f^\{\\star\},\\mathcal\{H\}\):=\\min\\\{\|S\|:S\\subseteq\\mathcal\{X\}\\text\{ and \}M\_\{\\mathrm\{err\}\}\(S\)\\leq\\varepsilon\\\},and

certR⁡\(f⋆,ℋ\):=min⁡\{\|S\|:S⊆𝒳​and​MΔ​\(S\)≤R\}\.\\operatorname\{cert\}\_\{R\}\(f^\{\\star\},\\mathcal\{H\}\):=\\min\\\{\|S\|:S\\subseteq\\mathcal\{X\}\\text\{ and \}M\_\{\\Delta\}\(S\)\\leq R\\\}\.Thuscertε\\operatorname\{cert\}\_\{\\varepsilon\}certifies that every surviving hypothesis has uniform error at mostε\\varepsilon, whilecertR\\operatorname\{cert\}\_\{R\}certifies that every surviving hypothesis makes at mostRRmistakes on𝒳\\mathcal\{X\}\. Exact certification is the caseε=0\\varepsilon=0, equivalentlyR=0R=0\.

## 4Certification hardness from overparametrization

Throughout this section, we lower\-bound the number of labeled examples required to certify a target uniquely within an enlarged hypothesis class\. The proof follows a combinatorial strategy to construct many alternative hypotheses around a fixed target so that each labeled example eliminates only a few of them\. In our setting, the alternatives are deceivers supported on pairwise disjoint sets\.

### 4\.1Proof idea: trigger blocks and deceivers

Fix some target functionf⋆:\{0,1\}n→\{0,1\}f^\{\\star\}:\\\{0,1\\\}^\{n\}\\to\\\{0,1\\\}from the hypothesis space\. Then, pick a setI⊆\[n\]I\\subseteq\[n\]ofttinput coordinates, where for each patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, we define the trigger blockBπ:=\{x∈\{0,1\}n:xI=π\}B\_\{\\pi\}:=\\\{x\\in\\\{0,1\\\}^\{n\}:x\_\{I\}=\\pi\\\}, for a total of2t2^\{t\}blocks that are pairwise disjoint and partition the domain\. For each blockBπB\_\{\\pi\}, we build one deceivergπg\_\{\\pi\}that agrees withf⋆f^\{\\star\}outsideBπB\_\{\\pi\}and changes the output on at least one point ofBπB\_\{\\pi\}\. Since the blocks are disjoint, a labeled value can reveal at most one of these changes\. Therefore, any exact certificate must contain at least one point from every block, as formally expressed in the following proposition\.

###### Proposition 4\.1\(Disjoint\-disagreement principle\)\.

Let𝒳\\mathcal\{X\}be a finite domain, letℋ⊆\{h:𝒳→\{0,1\}\}\\mathcal\{H\}\\subseteq\\\{h:\\mathcal\{X\}\\to\\\{0,1\\\}\\\}, and letf⋆∈ℋf^\{\\star\}\\in\\mathcal\{H\}\. LetTTbe a finite index set, and suppose that for eachπ∈T\\pi\\in Tthere is a hypothesisgπ∈ℋg\_\{\\pi\}\\in\\mathcal\{H\}\. Define

Eπ:=\{x∈𝒳:gπ​\(x\)≠f⋆​\(x\)\}\.E\_\{\\pi\}:=\\\{x\\in\\mathcal\{X\}:g\_\{\\pi\}\(x\)\\neq f^\{\\star\}\(x\)\\\}\.If the sets\{Eπ:π∈T\}\\\{E\_\{\\pi\}:\\pi\\in T\\\}are nonempty and pairwise disjoint, thencert⁡\(f⋆,ℋ\)≥\|T\|\.\\operatorname\{cert\}\(f^\{\\star\},\\mathcal\{H\}\)\\geq\|T\|\.

While the full proof appears in[Section˜A\.1](https://arxiv.org/html/2605.22964#A1.SS1), the key point is that each labeled example can eliminate only the deceivers that disagree withf⋆f^\{\\star\}at that point, so disjoint disagreement regions force any certifying sample to hit every block\.

In the following sections, we instantiate this principle for circuit classes and Transformers by showing that the enlarged hypothesis class contains exponentially many deceivers in the input dimension\.

### 4\.2Circuit classes

We instantiate the deceiver mechanism for circuits, focusing on threshold circuits where the construction is sharpest\. Starting from threshold circuits withssgates, overparametrizing them withs\+1s\+1gates of the same depth suffices to override the output on a chosen block while preserving depth\. We also state the corresponding results for the other circuit classes, deferring the details to[Appendix˜B](https://arxiv.org/html/2605.22964#A2)\.

![Refer to caption](https://arxiv.org/html/2605.22964v1/x1.png)Figure 1:Same\-depth deceiver construction inTC0\\mathrm\{TC\}^\{0\}\. Left: the original threshold circuit computingf⋆f^\{\\star\}\. Right: one additional threshold gateCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}detects the trigger block and feeds the top threshold, which forces the output on that block while leaving the circuit unchanged elsewhere\.###### Theorem 4\.1\(One\-gate certification hardness inTC0\\mathrm\{TC\}^\{0\}\)\.

Fix a constant depthd≥2d\\geq 2\. For everynn, every gate budgetss, everyf⋆∈TCd,s0f^\{\\star\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\}, and every1≤t≤n1\\leq t\\leq n,

cert⁡\(f⋆,TCd,s\+10\)≥2t,\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}\\bigr\)\\geq 2^\{t\},consequently, for any trigger lengtht=t​\(n\)t=t\(n\)satisfyingc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some constantc\>0c\>0, the lower bound is2Ω​\(n\)2^\{\\Omega\(n\)\}\. Moreover, ifs​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}, then for all sufficiently largennthere existsfn∈TCd,s​\(n\)0f\_\{n\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}such that

cert⁡\(fn,TCd,s​\(n\)0\)≤nO​\(1\)whilecert⁡\(fn,TCd,s​\(n\)\+10\)≥2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}\\bigr\)\\leq n^\{O\(1\)\}\\quad\\text\{while\}\\quad\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\+1\}\\bigr\)\\geq 2^\{\\Omega\(n\)\}\.

###### Proof sketch\.

Fix a size\-ss, depth\-ddcircuit andf⋆∈TCd,s0f^\{\\star\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\}\. We build a deceiver circuit using one additional gate\. The construction consists of two mechanisms: a trigger detector and an output\-overwrite mechanism\. For the first, choose a trigger setI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=t, and for each patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, letBπ=\{x∈\{0,1\}n:xI=π\}B\_\{\\pi\}=\\\{x\\in\\\{0,1\\\}^\{n\}:x\_\{I\}=\\pi\\\}be the corresponding trigger block\.

We use the extra threshold gate, denotedCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}, to detect membership inBπB\_\{\\pi\}by thresholding the signed literals that encode the equalitiesxi=πix\_\{i\}=\\pi\_\{i\}\. Once this gate is activated, we overwrite the output off⋆f^\{\\star\}\. Feeding the output of the new gate into the top gate with a sufficiently large positive or negative weight forces the circuit to output a chosen constant onBπB\_\{\\pi\}, while leaving the original circuit unchanged whenCHECKI,π=0\\mathrm\{CHECK\}\_\{I,\\pi\}=0\. This is exactly the same\-depth, one\-gate override shown in[Figure˜1](https://arxiv.org/html/2605.22964#S4.F1)\.

For each trigger block, choose a constant labelσπ∈\{0,1\}\\sigma\_\{\\pi\}\\in\\\{0,1\\\}that disagrees withf⋆f^\{\\star\}on at least half ofBπB\_\{\\pi\}, and letgπ∈TCd,s\+10g\_\{\\pi\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}be the corresponding override circuit\. Thengπg\_\{\\pi\}agrees withf⋆f^\{\\star\}outsideBπB\_\{\\pi\}and disagrees with it on a nonempty subset ofBπB\_\{\\pi\}\. Since the trigger blocks are pairwise disjoint, the disjoint\-block principle from[Section˜4\.1](https://arxiv.org/html/2605.22964#S4.SS1)givescert⁡\(f⋆,TCd,s\+10\)≥2t\\operatorname\{cert\}\(f^\{\\star\},\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}\)\\geq 2^\{t\}, and takingt=Ω​\(n\)t=\\Omega\(n\)yields an exponential dependence on the input size\.

For the second part of the argument, we use the finiteness of the circuit class to prove the non\-vacuity claim\. A size\-ssthreshold circuit has at mostssgates, and each gate computes one of at most2O​\(\(n\+s\)2\)2^\{O\(\(n\+s\)^\{2\}\)\}threshold functions of the previously available Boolean signals\. Hence\|TCd,s0\|≤2O​\(s​\(n\+s\)2\)\|\\mathrm\{TC\}^\{0\}\_\{d,s\}\|\\leq 2^\{O\(s\(n\+s\)^\{2\}\)\}\. Every finite class contains some hypothesis with a certificate of size logarithmic in the class cardinality, by repeatedly keeping the smaller side of a split until one hypothesis remains\. Therefore, whens​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}, somefn∈TCd,s​\(n\)0f\_\{n\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}satisfiescert⁡\(fn,TCd,s​\(n\)0\)≤nO​\(1\)\\operatorname\{cert\}\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}\)\\leq n^\{O\(1\)\}\. Applying the target\-wise lower bound above to this samefnf\_\{n\}, with a linear\-size trigger set, givescert⁡\(fn,TCd,s​\(n\)\+10\)≥2Ω​\(n\)\\operatorname\{cert\}\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\+1\}\)\\geq 2^\{\\Omega\(n\)\}\. ∎

Certification hardness in other circuit classes:The deceiver construction has two parts: detecting a trigger block and overriding the output on that block without changing the computation elsewhere\. While inTC0\\mathrm\{TC\}^\{0\}, both have constant cost, the deceiver constructions forAC0\\mathrm\{AC\}^\{0\}andNC1\\mathrm\{NC\}^\{1\}, which are described in[Appendix˜B](https://arxiv.org/html/2605.22964#A2), require extra components\. In particular, forAC0\\mathrm\{AC\}^\{0\}, trigger detection still costs one gate, but the override function requires an additional combining gate and typically one extra depth level\. Thus targets inACd,s0\\mathrm\{AC\}^\{0\}\_\{d,s\}satisfy the same2t2^\{t\}certification bounds insideACd\+1,s\+20\\mathrm\{AC\}^\{0\}\_\{d\+1,s\+2\}\. In bounded fan\-in circuits such asNC1\\mathrm\{NC\}^\{1\}, exact trigger detection costsΘ​\(t\)\\Theta\(t\)extra gates andΘ​\(log⁡t\)\\Theta\(\\log t\)extra depth, so extrakkgates give lower bounds of2Ω​\(k\)2^\{\\Omega\(k\)\}\.

### 4\.3Transformers

The circuit computations described so far also underlie many reasoning tasks studied in Transformers\. Beyond this task connection, there is a stronger relationship between Transformers and circuits: existing expressivity results show that log\-precision Transformer computations can be simulated by threshold circuits\[[24](https://arxiv.org/html/2605.22964#bib.bib24),[21](https://arxiv.org/html/2605.22964#bib.bib21),[23](https://arxiv.org/html/2605.22964#bib.bib23),[9](https://arxiv.org/html/2605.22964#bib.bib9)\]\. However, these results are one\-way, as they do not imply that arbitrary threshold\-circuit computations can be realized by Transformers\. We therefore prove the certification barrier directly inside a Transformer model\.

For the result below, we use a standard theoretical abstraction of Transformers withp=O​\(log⁡n\)p=O\(\\log n\)precision\[[22](https://arxiv.org/html/2605.22964#bib.bib22)\], average hard attention\[[15](https://arxiv.org/html/2605.22964#bib.bib15)\], and projected pre\-norm components\[[23](https://arxiv.org/html/2605.22964#bib.bib23)\]\. This model is idealized relative to deployed Transformer implementations, but it keeps the architectural features relevant to our argument while allowing an exact finite\-precision analysis\. The formal definition of the class and the block\-override construction are given in[Appendix˜C](https://arxiv.org/html/2605.22964#A3)\.

For a fixed choice of heads, layers, and dimensions at input lengthnn, let𝖠n\\mathsf\{A\}\_\{n\}denote the resulting architecture, and let𝒯𝖠n,p​\(n\)\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\}\(n\)be the class of Boolean functions on\{0,1\}n\\\{0,1\\\}^\{n\}computable by that architecture with variablepp\-precision parameters and embeddings\. The following theorem shows that a slight overparametrization of𝖠n\\mathsf\{A\}\_\{n\}can make certification exponentially harder\.

###### Theorem 4\.2\(Transformer certification hardness under overparametrization\)\.

There is an absolute precision constantp0p\_\{0\}such that the following holds\. Fix an input lengthnn, an AHAT architecture𝖠n\\mathsf\{A\}\_\{n\}, and a precisionp≥p0p\\geq p\_\{0\}\. Let1≤t≤n1\\leq t\\leq n, and let𝖠n\+\\mathsf\{A\}\_\{n\}^\{\+\}be the architecture obtained from𝖠n\\mathsf\{A\}\_\{n\}by adding at least one attention head in the final layer and at least six residual/embedding coordinates\. Then every target computed by the original architecture is hard to certify in the enlarged one:

∀f⋆∈𝒯𝖠n,p​\(n\),cert⁡\(f⋆,𝒯𝖠n\+,p​\(n\)\)≥2t\.\\forall f^\{\\star\}\\in\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\}\(n\),\\qquad\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\}^\{\+\},p\}\(n\)\\bigr\)\\geq 2^\{t\}\.Moreover, this lower bound is not vacuous\. If\{𝖠n\}\\\{\\mathsf\{A\}\_\{n\}\\\}is a projected\-pre\-norm AHAT family withnO​\(1\)n^\{O\(1\)\}finite\-precision scalar parameters, including embeddings, andp​\(n\)=O​\(log⁡n\)p\(n\)=O\(\\log n\), assume there existsn0n\_\{0\}such thatp​\(n\)≥p0p\(n\)\\geq p\_\{0\}for alln≥n0n\\geq n\_\{0\}\. Then for everyn≥n0n\\geq n\_\{0\}there is a functionfn∈𝒯𝖠n,p​\(n\)​\(n\)f\_\{n\}\\in\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\(n\)\}\(n\)such that

cert⁡\(fn,𝒯𝖠n,p​\(n\)​\(n\)\)≤nO​\(1\)while, taking any​t=Ω​\(n\),cert⁡\(fn,𝒯𝖠n\+,p​\(n\)​\(n\)\)≥2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\(n\)\}\(n\)\\bigr\)\\leq n^\{O\(1\)\}\\quad\\text\{while, taking any \}t=\\Omega\(n\),\\quad\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\}^\{\+\},p\(n\)\}\(n\)\\bigr\)\\geq 2^\{\\Omega\(n\)\}\.Thus the exponential lower bound is not merely inherited from a function that was already hard to certify in the smaller Transformer class\.

###### Proof sketch\.

Fixf⋆∈𝒯𝖠n,p​\(n\)f^\{\\star\}\\in\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\}\(n\)and choose app\-precision TransformerT⋆T^\{\\star\}of architecture𝖠n\\mathsf\{A\}\_\{n\}computing it\. Pick a trigger setI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=t\. For each patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, define the block

Bπ:=\{x∈\{0,1\}n:xI=π\}\.B\_\{\\pi\}:=\\\{x\\in\\\{0,1\\\}^\{n\}:x\_\{I\}=\\pi\\\}\.Choose a labelσπ∈\{0,1\}\\sigma\_\{\\pi\}\\in\\\{0,1\\\}that disagrees withf⋆f^\{\\star\}on at least half ofBπB\_\{\\pi\}\. By the block\-override construction in[Theorem˜C\.2](https://arxiv.org/html/2605.22964#A3.Thmtheorem2), for everyπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}the enlarged architecture contains a same\-precision hypothesis

gπ∈𝒯𝖠n\+,p​\(n\)g\_\{\\pi\}\\in\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\}^\{\+\},p\}\(n\)such that

gπ​\(x\)=f⋆​\(x\)for all​x∉Bπ,gπ​\(x\)=σπfor all​x∈Bπ\.g\_\{\\pi\}\(x\)=f^\{\\star\}\(x\)\\quad\\text\{for all \}x\\notin B\_\{\\pi\},\\qquad g\_\{\\pi\}\(x\)=\\sigma\_\{\\pi\}\\quad\\text\{for all \}x\\in B\_\{\\pi\}\.Hence the disagreement setEπ:=\{x:gπ​\(x\)≠f⋆​\(x\)\}E\_\{\\pi\}:=\\\{x:g\_\{\\pi\}\(x\)\\neq f^\{\\star\}\(x\)\\\}is nonempty and contained inBπB\_\{\\pi\}\. The blocks\{Bπ:π∈\{0,1\}I\}\\\{B\_\{\\pi\}:\\pi\\in\\\{0,1\\\}^\{I\}\\\}are pairwise disjoint, so the disagreement sets\{Eπ:π∈\{0,1\}I\}\\\{E\_\{\\pi\}:\\pi\\in\\\{0,1\\\}^\{I\}\\\}are pairwise disjoint as well\. By the disjoint\-disagreement principle,[Proposition˜4\.1](https://arxiv.org/html/2605.22964#S4.Thmproposition1), any exact certificate forf⋆f^\{\\star\}relative to the enlarged class must hit every one of these disagreement sets\. Therefore

cert⁡\(f⋆,𝒯𝖠n\+,p​\(n\)\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\}^\{\+\},p\}\(n\)\\bigr\)\\geq 2^\{t\}\.
For the non\-vacuity claim, use only finiteness\. In the log\-precision regime, the smaller Transformer class has at most2poly​\(n\)2^\{\\mathrm\{poly\}\(n\)\}hypotheses, since it is specified bynO​\(1\)n^\{O\(1\)\}finite\-precision scalar slots withO​\(log⁡n\)O\(\\log n\)bits each\. By[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1), somefn∈𝒯𝖠n,p​\(n\)​\(n\)f\_\{n\}\\in\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\(n\)\}\(n\)satisfies

cert⁡\(fn,𝒯𝖠n,p​\(n\)​\(n\)\)≤poly​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\(n\)\}\(n\)\\bigr\)\\leq\\mathrm\{poly\}\(n\)\.Applying the target\-wise lower bound above to this samefnf\_\{n\}inside the enlarged class, withtn=Ω​\(n\)t\_\{n\}=\\Omega\(n\), gives

cert⁡\(fn,𝒯𝖠n\+,p​\(n\)​\(n\)\)≥2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\}^\{\+\},p\(n\)\}\(n\)\\bigr\)\\geq 2^\{\\Omega\(n\)\}\.∎

Thus the Transformer result is not just a statement about a function that was already hard to certify\. The smaller architecture contains polynomially certifiable functions, but after adding a single extra head and constant embedding/residual width, the same function can require exponentially many labeled examples to certify against the enlarged Transformer class\.

### 4\.4From exact to approximate certification

The results above concern exact certification\. One may ask whether hardness persists under a more forgiving notion, where a consistent hypothesis is only required to be approximately correct\. The answer depends sharply on how the tolerance is measured\. If only polynomially many mistakes are allowed, the block\-deceiver construction still forces certificates of exponential size\. In contrast, a fixed relative tolerance can leave exponentially many small\-error block deceivers unresolved, at the cost of permitting exponentially many mistakes overall\. The following proposition captures this general argument, and it applies whenever the hypothesis class admits the required block deceivers, as in the circuit and Transformer constructions of the previous sections\.

###### Proposition 4\.2\(Approximate certification lower bounds from block deceivers\)\.

Let𝒳=\{0,1\}n\\mathcal\{X\}=\\\{0,1\\\}^\{n\}and fix a nonempty setI⊆\[n\]I\\subseteq\[n\]oftttrigger coordinates\. For each patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, letBπ:=\{x∈𝒳:xI=π\}B\_\{\\pi\}:=\\\{x\\in\\mathcal\{X\}:x\_\{I\}=\\pi\\\}be the corresponding trigger block\. Suppose that for every patternπ\\pi, there exists a deceivergπ∈ℋg\_\{\\pi\}\\in\\mathcal\{H\}that agrees withf⋆f^\{\\star\}outsideBπB\_\{\\pi\}and disagrees with it on at least half ofBπB\_\{\\pi\}, i\.e\., writingEπ:=\{x:gπ​\(x\)≠f⋆​\(x\)\}E\_\{\\pi\}:=\\\{x:g\_\{\\pi\}\(x\)\\neq f^\{\\star\}\(x\)\\\},

Eπ⊆Bπ,\|Eπ\|≥2n−t−1\.E\_\{\\pi\}\\subseteq B\_\{\\pi\},\\qquad\|E\_\{\\pi\}\|\\geq 2^\{n\-t\-1\}\.Since the blocks partition𝒳\\mathcal\{X\}, the sets\{Eπ\}π∈\{0,1\}I\\\{E\_\{\\pi\}\\\}\_\{\\pi\\in\\\{0,1\\\}^\{I\}\}are pairwise disjoint\. Consequently:

εn<2−t−1⇒certεn⁡\(f⋆,ℋ\)≥2tandRn<2n−t−1⇒certRn⁡\(f⋆,ℋ\)≥2t\.\\varepsilon\_\{n\}<2^\{\-t\-1\}\\;\\Rightarrow\\;\\operatorname\{cert\}\_\{\\varepsilon\_\{n\}\}\(f^\{\\star\},\\mathcal\{H\}\)\\geq 2^\{t\}\\qquad\\text\{and\}\\qquad R\_\{n\}<2^\{n\-t\-1\}\\;\\Rightarrow\\;\\operatorname\{cert\}\_\{R\_\{n\}\}\(f^\{\\star\},\\mathcal\{H\}\)\\geq 2^\{t\}\.

###### Proof\.

The setsEπE\_\{\\pi\}are nonempty and pairwise disjoint, since eachEπ⊆BπE\_\{\\pi\}\\subseteq B\_\{\\pi\}and the blocks partition𝒳\\mathcal\{X\}\. Suppose a labeled setSSmisses someEπE\_\{\\pi\}\. Thengπ∈VSf⋆,ℋ​\(S\)g\_\{\\pi\}\\in\\mathrm\{VS\}\_\{f^\{\\star\},\\mathcal\{H\}\}\(S\), with

err​\(gπ\)=2−n​\|Eπ\|≥2−t−1,Δ​\(gπ\)=\|Eπ\|≥2n−t−1\.\\mathrm\{err\}\(g\_\{\\pi\}\)=2^\{\-n\}\|E\_\{\\pi\}\|\\geq 2^\{\-t\-1\},\\qquad\\Delta\(g\_\{\\pi\}\)=\|E\_\{\\pi\}\|\\geq 2^\{n\-t\-1\}\.Ifεn<2−t−1\\varepsilon\_\{n\}<2^\{\-t\-1\}orRn<2n−t−1R\_\{n\}<2^\{n\-t\-1\}, this deceiver violates the respective guarantee\. Hence any certificate must hit everyEπE\_\{\\pi\}, and therefore has size at least2t2^\{t\}\. ∎

The lower bound in[Proposition˜4\.2](https://arxiv.org/html/2605.22964#S4.Thmproposition2)is essentially the inverse of the tolerance: optimizing overttgivescertεn≳1/εn\\operatorname\{cert\}\_\{\\varepsilon\_\{n\}\}\\gtrsim 1/\\varepsilon\_\{n\}andcertRn≳2n/Rn\\operatorname\{cert\}\_\{R\_\{n\}\}\\gtrsim 2^\{n\}/R\_\{n\}\. Consequently, our lower bound grows withnnonly when the relative tolerance shrinks withnn\.

Certifying near\-perfect accuracy is exponentially expensive:IfRn=poly⁡\(n\)R\_\{n\}=\\operatorname\{poly\}\(n\), then choosingt=n−O​\(log⁡n\)t=n\-O\(\\log n\)gives

certRn⁡\(f⋆,ℋ\)≥2npoly⁡\(n\)=2Ω​\(n\)\.\\operatorname\{cert\}\_\{R\_\{n\}\}\(f^\{\\star\},\\mathcal\{H\}\)\\geq\\frac\{2^\{n\}\}\{\\operatorname\{poly\}\(n\)\}=2^\{\\Omega\(n\)\}\.Thus, allowing only polynomially many mistakes still forces the certificate size to be exponential to cover all deceivers that have more thanRnR\_\{n\}mistakes\.

A fixed relative tolerance allows small\-block deceivers to survive:For fixedε\>0\\varepsilon\>0, anε\\varepsilon\-certificate only needs to eliminate hypotheses whose relative error is larger thanε\\varepsilon\. In the block construction, a deceiver with trigger lengthtthas error at least2−t−12^\{\-t\-1\}and at most2−t2^\{\-t\}\. Thus[Proposition˜4\.2](https://arxiv.org/html/2605.22964#S4.Thmproposition2)gives a nontrivial lower bound only whenε<2−t−1\\varepsilon<2^\{\-t\-1\}, which forcest<log2⁡\(1/ε\)−1\.t<\\log\_\{2\}\(1/\\varepsilon\)\-1\.

Whenε\\varepsilonis fixed, this upper bound onttis a constant, so the lower bound2t2^\{t\}is at most on the order of1/ε1/\\varepsilon, not exponential innn\. This does not mean that approximate certification is always easy\. It means that block deceivers with sufficiently small relative error need not be eliminated\. Such deceivers may still make exponentially many absolute mistakes, but their relative error can be small enough so that a fixed\-relative\-error certificate does not need to eliminate them\.

Relative and absolute tolerances encode different guarantees:The normalized and absolute formulations are related by

Rn=⌊εn​2n⌋\.R\_\{n\}=\\lfloor\\varepsilon\_\{n\}2^\{n\}\\rfloor\.Thus a constantε\\varepsiloncorresponds toRn=Θ​\(2n\)R\_\{n\}=\\Theta\(2^\{n\}\)allowed mistakes, whereas a polynomial mistake budgetRn=poly⁡\(n\)R\_\{n\}=\\operatorname\{poly\}\(n\)corresponds to a vanishing relative toleranceεn=Rn/2n\\varepsilon\_\{n\}=R\_\{n\}/2^\{n\}\.

## 5Experiments

Our goal in this section is to complement the theoretical results above with a more practical perspective\. To this end, we use binary\-addition recognition as a controlled certification case study, since it connects naturally to threshold\-circuit constructions and serves as a reasoning benchmark commonly studied in Transformers\. Each input is a triple\(a,b,z\)\(a,b,z\), wherea,b∈\{0,1\}na,b\\in\\\{0,1\\\}^\{n\}are operands andz∈\{0,1\}n\+1z\\in\\\{0,1\\\}^\{n\+1\}is a proposed sum\. The target isf⋆​\(a,b,z\)=𝟏​\[z=a\+b\]f^\{\\star\}\(a,b,z\)=\\mathbf\{1\}\[z=a\+b\]\.

Both experiments use the same survivor calculation\. LetQQbe a finite set from which a certificate candidateSmS\_\{m\}is sampled uniformly without replacement\. For a hypothesishh, write

EhQ=\{x∈Q:h​\(x\)≠f⋆​\(x\)\}\.E\_\{h\}^\{Q\}=\\\{x\\in Q:h\(x\)\\neq f^\{\\star\}\(x\)\\\}\.Thenhhpasses the certificate candidate exactly whenSm∩EhQ=∅S\_\{m\}\\cap E\_\{h\}^\{Q\}=\\emptyset, so

phQ​\(m\)=\(\|Q\|−\|EhQ\|m\)/\(\|Q\|m\),𝔼Q​\(m\)=∑h∈𝒟phQ​\(m\),p\_\{h\}^\{Q\}\(m\)=\\binom\{\|Q\|\-\|E\_\{h\}^\{Q\}\|\}\{m\}\\Big/\\binom\{\|Q\|\}\{m\},\\qquad\\mathbb\{E\}\_\{Q\}\(m\)=\\sum\_\{h\\in\\mathcal\{D\}\}p\_\{h\}^\{Q\}\(m\),where𝒟\\mathcal\{D\}is the set of non\-exact candidates under consideration\. This is an exact finite\-population calculation\. It does not assume independent survival events or uniformly distributed errors\. The targeted experiment below changes the sampling setQQ, not the assumptions behind the calculation\.

##### Constructed threshold circuits\.

The first experiment instantiates the trigger construction from[Theorem˜4\.1](https://arxiv.org/html/2605.22964#S4.Thmtheorem1)for addition\. LetA,B,ZA,B,Zdenote the integers encoded bya,b,za,b,z\. A depth\-22threshold circuit recognizes addition by checkingZ−A−B≥0Z\-A\-B\\geq 0andA\+B−Z≥0A\+B\-Z\\geq 0, and feeding the two tests into a final threshold gate\. Thus the target recognizer uses three threshold gates\.

For each patternπ∈\{0,1\}n\\pi\\in\\\{0,1\\\}^\{n\}, define the trigger blockBπ=\{\(a,b,z\):a=π\}B\_\{\\pi\}=\\\{\(a,b,z\):a=\\pi\\\}\. Adding one threshold gate that detectsa=πa=\\pilets us modify the output gate so that the circuit accepts every input inBπB\_\{\\pi\}and agrees with the target outsideBπB\_\{\\pi\}\. Denote the resulting circuit bygπg\_\{\\pi\}and its disagreement set byEπE\_\{\\pi\}\. SinceEπ⊆BπE\_\{\\pi\}\\subseteq B\_\{\\pi\}and the blocks are disjoint, the sets\{Eπ\}π∈\{0,1\}n\\\{E\_\{\\pi\}\\\}\_\{\\pi\\in\\\{0,1\\\}^\{n\}\}are disjoint\. A dummy gate may be added to the target if equal gate counts are desired\.

We take𝒟=\{gπ:π∈\{0,1\}n\}\\mathcal\{D\}=\\\{g\_\{\\pi\}:\\pi\\in\\\{0,1\\\}^\{n\}\\\}andQ=𝒳=\{0,1\}3​n\+1Q=\\mathcal\{X\}=\\\{0,1\\\}^\{3n\+1\}\. The2n2^\{n\}terms in the survivor sum have the same size, so the expected number of surviving constructed deceivers is2n​pgπ𝒳​\(m\)2^\{n\}p\_\{g\_\{\\pi\}\}^\{\\mathcal\{X\}\}\(m\)\. The left panel of[Figure˜2](https://arxiv.org/html/2605.22964#S5.F2)plots this quantity for several operand lengths\. Form=poly​\(n\)m=\\mathrm\{poly\}\(n\), almost all constructed deceivers survive, and the decay only becomes visible on an exponential scale innn\.

Appendix[D\.3](https://arxiv.org/html/2605.22964#A4.SS3)gives a complementary finite\-class analysis for restricted threshold circuits andAC0\\mathrm\{AC\}^\{0\}\. It identifies a particular target with certificate sizen\+1n\+1in the base class, while the same target has a2n2^\{n\}lower bound in the corresponding overparametrized class\.

##### Trained Transformer recognizers\.

The second experiment asks whether a related certification issue appears among trained models\. We train encoder\-only Transformers on1010\-bit addition, using a75%75\\%train/validation split and a25%25\\%held\-out test split over operand pairs\(a,b\)\(a,b\)\. For each of the262,144262\{,\}144held\-out operand pairs, the test set contains the correct sum and the1111one\-bit flips of that sum, givingNtest=262,144⋅12=3,145,728N\_\{\\rm test\}=262\{,\}144\\cdot 12=3\{,\}145\{,\}728examples\. We call a model*test\-exact*if it makes zero mistakes on this finite held\-out set\.111This is exactness relative to the held\-out set, not over all possible candidate stringszz\.

Intermediate supervision is used to obtain strong candidate models for certification\. During training, the model also predicts the true sum bits together with intermediate sums and carries\. A final verifier compares the predicted sum bits with the candidatezz\. During evaluation, the model receives only\(a,b,z\)\(a,b,z\)\. A run is accepted once it reaches99\.9%99\.9\\%accuracy on fixed train and validation checks, separately for positive and negative examples\. Further implementation details are given in[Section˜D\.2](https://arxiv.org/html/2605.22964#A4.SS2)\.

Among the150150accepted models,8787are test\-exact, and6363have residual test errors\. Thus, even strong validation checks can leave nonzero residual error sets\. For consistency, we call these non\-test\-exact hypotheses deceivers, without implying that they behave like the constructed deceivers above\. For the survivor curves, we set𝒟\\mathcal\{D\}to the6363Transformer deceivers\. HereSmS\_\{m\}is a uniformly sampled certificate candidate, so this analysis reports candidate\-certificate survival for this finite𝒟\\mathcal\{D\}, not the ultimate minimum certificate size of\{f⋆\}∪𝒟\\\{f^\{\\star\}\\\}\\cup\\mathcal\{D\}\. TakingQQto be the full held\-out test set gives the full\-test curve in the right panel of[Figure˜2](https://arxiv.org/html/2605.22964#S5.F2)\.

The full\-test curve samples uniformly from all held\-out examples\. One potential objection is that this set might be too broad, as the residual errors may lie in a simple region that a better certificate sampler should target\. We therefore also evaluate a compact test subsetQtgtQ\_\{\\rm tgt\}consisting of positives and output\-bit flips in positions8,9,108,9,10\. This set uses44of the1212examples per operand pair, yet contains77\.2%77\.2\\%of the unique error locations\. The residual errors are therefore structured\. Still,QtgtQ\_\{\\rm tgt\}contains1,048,5761\{,\}048\{,\}576examples forn=10n=10, and the targeted curve decreases only after sampling a large part of this set\. Moreover, deceivers with\|EhQtgt\|=0\|E\_\{h\}^\{Q\_\{\\rm tgt\}\}\|=0survive every sample drawn fromQtgtQ\_\{\\rm tgt\}\. Thus, targeting a smaller error\-rich region helps, but uniformly sampled certificate candidates fromQtgtQ\_\{\\rm tgt\}remain large\.222We do not claim thatQtgtQ\_\{\\rm tgt\}is minimal\. More compact a priori criteria may exist, perhaps with more complex structure\. The post\-hoc union of observed error locations has15,49415\{,\}494examples and eliminates every observed deceiver, but is chosen after evaluating the full held\-out set\. If every high\-coverage set remains exponential innn, the certification barrier persists\.

![Refer to caption](https://arxiv.org/html/2605.22964v1/x2.png)

![Refer to caption](https://arxiv.org/html/2605.22964v1/x3.png)

Figure 2:Surviving deceivers under uniformly sampled certificate candidates\.Left\.Expected number of constructed threshold\-circuit deceivers that remain consistent with the sampled labels\. The certificate candidate size is normalized by2n2^\{n\}, wherennis the operand length\. The constructed subfamily already forces an exponential sampling scale\.Right\.Expected number of Transformer deceivers that remain consistent with sampled labels forn=10n=10\. The full\-test curve samples from all held\-out examples\. The compact test subset curve samples from positives and output\-bit flips in positions8,9,108,9,10, a one\-third\-size subset containing most observed errors\. This tests whether error concentration alone explains the full\-test curve\. Targeting helps, but the uniformly sampled certificates remain large, and deceivers with errors outside it survive every compact subset\.The two experiments play different roles\. The circuit experiment is a finite instantiation of the disjoint\-trigger mechanism used in the lower bound\. The Transformer experiment is a finite\-set candidate\-certificate analysis of the trained set𝒟\\mathcal\{D\}, not an asymptotic certificate\-size lower bound for the full Transformer class\. In both cases, a sampled certificate candidate eliminates a deceiver only if it intersects the residual error sets\. Therefore, rare or disjoint errors can leave deceivers consistent with all sampled labels even after strong validation\.

## 6Conclusion and future work

We studied certification from labeled input\-output examples for circuits and log\-precision Transformers\. Our main finding is that exact certification is highly sensitive to the ambient hypothesis class, with even minimal overparametrization, such as one threshold gate or one final\-layer attention head with constant embedding/residual width overhead, creating exponentially many trigger deceivers around every target in the smaller class\. Hence, polynomially many examples may fail to certify that a model has learned the intended computation\.

An important next step is to understand which stronger certification protocols can escape this passive barrier\. A natural direction is active certification, where the certifier can query the candidate model in different ways and compare its answers with a trusted target oracle, verifier, or specification\. The exact learning literature shows that membership and equivalence queries can change learnability and query complexity\[[1](https://arxiv.org/html/2605.22964#bib.bib1),[18](https://arxiv.org/html/2605.22964#bib.bib18)\]\. For Transformers and other neural networks, the same idea could support targeted challenges, counterexample search, or queries about intermediate traces rather than only final labels\. One interesting question in this setting is whether richer interactions can efficiently rule out these trigger deceivers, or whether analogous barriers persist under stronger protocols\.

## References

- Angluin \[1987\]Dana Angluin\.Learning regular sets from queries and counterexamples\.*Information and computation*, 75\(2\):87–106, 1987\.
- Angluin \[1988\]Dana Angluin\.Queries and concept learning\.*Machine learning*, 2\(4\):319–342, 1988\.
- Angluin \[1990\]Dana Angluin\.Negative results for equivalence queries\.*Machine Learning*, 5\(2\):121–150, 1990\.
- Anthony et al\. \[1992\]Martin Anthony, Graham Brightwell, Dave Cohen, and John Shawe\-Taylor\.On exact specification by examples\.In*Fifth annual workshop on computational learning theory*, pages 311–318, 1992\.
- Baldi and Vershynin \[2019\]Pierre Baldi and Roman Vershynin\.Polynomial threshold functions, hyperplane arrangements, and random tensors\.*SIAM Journal on Mathematics of Data Science*, 1\(4\):699–729, 2019\.
- Bshouty et al\. \[1996\]Nader H\. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, and Christino Tamon\.Oracles and queries that are sufficient for exact learning\.*Journal of Computer and System Sciences*, 52\(3\):421–433, 1996\.
- Chase and Freitag \[2020\]Hunter Chase and James Freitag\.Bounds in query learning\.In*Proceedings of Thirty Third Conference on Learning Theory*, volume 125 of*Proceedings of Machine Learning Research*, pages 1142–1160\. PMLR, 2020\.
- Chen et al\. \[2016\]Xi Chen, Yu Cheng, and Bo Tang\.On the recursive teaching dimension of VC classes\.In*Advances in Neural Information Processing Systems*, volume 29, 2016\.
- Chiang \[2025\]David Chiang\.Transformers in uniform TC0\.*Transactions on Machine Learning Research*, 2025\.ISSN 2835–8856\.
- de Luca et al\. \[2026\]Artur Back de Luca, George Giapitzakis, and Kimon Fountoulakis\.Learning to add, multiply, and execute algorithmic instructions exactly with neural networks\.In*The Thirty\-ninth Annual Conference on Neural Information Processing Systems*, 2026\.
- Doliwa et al\. \[2014\]Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, and Sandra Zilles\.Recursive teaching dimension, VC\-dimension and sample compression\.*Journal of Machine Learning Research*, 15\(89\):3107–3131, 2014\.
- Gao et al\. \[2016\]Ziyuan Gao, Christoph Ries, Hans Simon, and Sandra Zilles\.Preference\-based teaching\.In*29th Annual Conference on Learning Theory*, volume 49 of*Proceedings of Machine Learning Research*, pages 971–997\. PMLR, 2016\.
- Goldman and Kearns \[1995\]S\.A\. Goldman and M\.J\. Kearns\.On the complexity of teaching\.*Journal of Computer and System Sciences*, 50\(1\):20–31, 1995\.ISSN 0022\-0000\.
- György et al\. \[2025\]András György, Tor Lattimore, Nevena Lazić, and Csaba Szepesvári\.Beyond statistical learning: Exact learning is essential for general intelligence\.*arXiv preprint arXiv:2506\.23908*, 2025\.
- Hao et al\. \[2022\]Yiding Hao, Dana Angluin, and Robert Frank\.Formal language recognition by hard attention transformers: Perspectives from circuit complexity\.*Transactions of the Association for Computational Linguistics*, 10:800–810, 2022\.
- Hegedüs \[1995\]Tibor Hegedüs\.Generalized teaching dimensions and the query complexity of learning\.In*Proceedings of the Eighth Annual Conference on Computational Learning Theory*, pages 108––117, 1995\.doi:10\.1145/225298\.225311\.
- Hellerstein and Raghavan \[2005\]Lisa Hellerstein and Vijay Raghavan\.Exact learning of DNF formulas using DNF hypotheses\.*Journal of Computer and System Sciences*, 70\(4\):435–470, 2005\.
- Hellerstein et al\. \[1996\]Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, and Dawn Wilkins\.How many queries are needed to learn?*Journal of the ACM \(JACM\)*, 43\(5\):840–862, 1996\.
- Hu et al\. \[2017\]Lunjia Hu, Ruihan Wu, Tianhong Li, and Liwei Wang\.Quadratic upper bound for recursive teaching dimension of finite vc classes\.In*Proceedings of the 2017 Conference on Learning Theory*, volume 65 of*Proceedings of Machine Learning Research*, pages 1147–1156\. PMLR, 2017\.
- Malek et al\. \[2025\]Alan Malek, Jiawei Ge, Nevena Lazic, Chi Jin, András György, and Csaba Szepesvári\.Frontier LLMs still struggle with simple reasoning tasks\.*arXiv preprint arXiv:2507\.07313*, 2025\.
- Merrill and Sabharwal \[2023a\]William Merrill and Ashish Sabharwal\.A logic for expressing log\-precision transformers\.In*Thirty\-seventh Conference on Neural Information Processing Systems*, 2023a\.
- Merrill and Sabharwal \[2023b\]William Merrill and Ashish Sabharwal\.The parallelism tradeoff: Limitations of log\-precision transformers\.*Transactions of the Association for Computational Linguistics*, 11:531–545, 2023b\.
- Merrill and Sabharwal \[2024\]William Merrill and Ashish Sabharwal\.The expressive power of transformers with chain of thought\.In*The Twelfth International Conference on Learning Representations*, 2024\.
- Merrill et al\. \[2022\]William Merrill, Ashish Sabharwal, and Noah A Smith\.Saturated transformers are constant\-depth threshold circuits\.*Transactions of the Association for Computational Linguistics*, 10:843–856, 2022\.
- Nezhurina et al\. \[2024\]Marianna Nezhurina, Lucia Cipolina\-Kun, Mehdi Cherti, and Jenia Jitsev\.Alice in wonderland: Simple tasks reveal severe generalization and basic reasoning deficits in state\-of\-the\-art large language models\.In*NeurIPS 2024 Workshop on Scientific Methods for Understanding Deep Learning*, 2024\.
- Papazov et al\. \[2025\]Hristo Papazov, Francesco D’Angelo, and Nicolas Flammarion\.Exact learning of arithmetic with differentiable agents\.In*The 5th Workshop on Mathematical Reasoning and AI at NeurIPS 2025*, 2025\.
- Pillaipakkamnatt and Raghavan \[1994\]Krishnan Pillaipakkamnatt and Vijay Raghavan\.On the limits of proper learnability of subclasses of DNF formulas\.In*Proceedings of the seventh annual conference on Computational learning theory*, pages 118–129, 1994\.
- Servedio \[2001\]Rocco A Servedio\.On the limits of efficient teachability\.*Information Processing Letters*, 79\(6\):267–272, 2001\.
- Shinohara and Miyano \[1991\]Ayumi Shinohara and Satoru Miyano\.Teachability in computational learning\.*New Generation Computing*, 8:337–347, 1991\.doi:10\.1007/BF03037091\.
- Zilles et al\. \[2011\]Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich\.Models of cooperative teaching and learning\.*Journal of Machine Learning Research*, 12:349–384, 2011\.

## Appendix AGeneric certification tools

### A\.1Disjoint\-block principle

###### Proposition A\.1\(Restatement of[Proposition˜4\.1](https://arxiv.org/html/2605.22964#S4.Thmproposition1)\)\.

Let𝒳\\mathcal\{X\}be a finite domain, letℋ⊆\{h:𝒳→\{0,1\}\}\\mathcal\{H\}\\subseteq\\\{h:\\mathcal\{X\}\\to\\\{0,1\\\}\\\}, and letf⋆∈ℋf^\{\\star\}\\in\\mathcal\{H\}\. LetTTbe a finite index set, and suppose that for eachπ∈T\\pi\\in Tthere is a hypothesisgπ∈ℋg\_\{\\pi\}\\in\\mathcal\{H\}\. Define

Eπ:=\{x∈𝒳:gπ​\(x\)≠f⋆​\(x\)\}\.E\_\{\\pi\}:=\\\{x\\in\\mathcal\{X\}:g\_\{\\pi\}\(x\)\\neq f^\{\\star\}\(x\)\\\}\.If the sets\{Eπ:π∈T\}\\\{E\_\{\\pi\}:\\pi\\in T\\\}are nonempty and pairwise disjoint, thencert⁡\(f⋆,ℋ\)≥\|T\|\.\\operatorname\{cert\}\(f^\{\\star\},\\mathcal\{H\}\)\\geq\|T\|\.

###### Proof\.

LetS⊆𝒳S\\subseteq\\mathcal\{X\}be any labeled sample consistent withf⋆f^\{\\star\}\. A deceivergπg\_\{\\pi\}is eliminated bySSonly ifSScontains a point inEπE\_\{\\pi\}\. Since the sets\{Eπ:π∈T\}\\\{E\_\{\\pi\}:\\pi\\in T\\\}are pairwise disjoint, each labeled example eliminates at most one deceiver\. If\|S\|<\|T\|\|S\|<\|T\|, then someπ∈T\\pi\\in ThasS∩Eπ=∅S\\cap E\_\{\\pi\}=\\emptyset, sogπg\_\{\\pi\}remains consistent with all labels inSSwhilegπ≠f⋆g\_\{\\pi\}\\neq f^\{\\star\}\. HenceSSis not a certificate\. Every certificate must therefore have size at least\|T\|\|T\|, i\.e\.,cert⁡\(f⋆,ℋ\)≥\|T\|\\operatorname\{cert\}\(f^\{\\star\},\\mathcal\{H\}\)\\geq\|T\|\. ∎

In the later sections, the circuit and Transformer lower bounds all reduce to this proposition\. In each case, we construct hypothesesgπg\_\{\\pi\}whose disagreement sets are nonempty and contained in pairwise disjoint trigger blocksBπB\_\{\\pi\}, instantiated below for a binary domain\.

Trigger blocks:For a binary input space ofnncoordinates, fix a coordinate setI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=t\. For each patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, define the trigger block

Bπ:=\{x∈\{0,1\}n:xi=πi​for all​i∈I\}\.B\_\{\\pi\}:=\\\{x\\in\\\{0,1\\\}^\{n\}:x\_\{i\}=\\pi\_\{i\}\\text\{ for all \}i\\in I\\\}\.The blocks\{Bπ\}π∈\{0,1\}I\\\{B\_\{\\pi\}\\\}\_\{\\pi\\in\\\{0,1\\\}^\{I\}\}are pairwise disjoint\. In the instantiations considered for the hypothesis classes covered here, it is useful to view a deceivergπg\_\{\\pi\}as a function that agrees withf⋆f^\{\\star\}outsideBπB\_\{\\pi\}and is fixed to a constant value onBπB\_\{\\pi\}\.

### A\.2Lower bounds on certificate size in finite classes

Our exponential certification lower bounds do not imply that the underlying hypothesis class is uniformly hard\. In fact, every finite hypothesis class contains at least one hypothesis with a certificate of sizeO​\(log⁡\|ℋ\|\)O\(\\log\|\\mathcal\{H\}\|\)\.

###### Lemma A\.1\(A small certificate exists in every finite class\)\.

Let𝒳\\mathcal\{X\}be a domain and letℋ⊆\{0,1\}𝒳\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\mathcal\{X\}\}be finite and nonempty\. Then there existsf∈ℋf\\in\\mathcal\{H\}such that

cert⁡\(f,ℋ\)≤⌈log2⁡\|ℋ\|⌉\.\\operatorname\{cert\}\(f,\\mathcal\{H\}\)\\leq\\lceil\\log\_\{2\}\|\\mathcal\{H\}\|\\rceil\.

###### Proof\.

InitializeV0:=ℋV\_\{0\}:=\\mathcal\{H\}and an empty input setSS\. While\|Vt\|\>1\|V\_\{t\}\|\>1, choose somext∈𝒳x\_\{t\}\\in\\mathcal\{X\}on which two hypotheses inVtV\_\{t\}disagree\. Let

Vtπ:=\{h∈Vt:h​\(xt\)=π\}π∈\{0,1\}\.V\_\{t\}^\{\\pi\}:=\\\{h\\in V\_\{t\}:h\(x\_\{t\}\)=\\pi\\\}\\qquad\\pi\\in\\\{0,1\\\}\.Both parts are nonempty, and the smaller one has size at most\|Vt\|/2\|V\_\{t\}\|/2\. Chooseπt\\pi\_\{t\}with\|Vtπt\|≤\|Vt\|/2\|V\_\{t\}^\{\\pi\_\{t\}\}\|\\leq\|V\_\{t\}\|/2, addxtx\_\{t\}toSS, and setVt\+1:=VtπtV\_\{t\+1\}:=V\_\{t\}^\{\\pi\_\{t\}\}\. The intended label ofxtx\_\{t\}isπt\\pi\_\{t\}\. After at most⌈log2⁡\|ℋ\|⌉\\lceil\\log\_\{2\}\|\\mathcal\{H\}\|\\rceilsteps we obtain a singletonVT=\{f\}V\_\{T\}=\\\{f\\\}\. By construction,ffis the unique hypothesis inℋ\\mathcal\{H\}consistent with the labels prescribed onSS, soSSis a certificate forffof size at most⌈log2⁡\|ℋ\|⌉\\lceil\\log\_\{2\}\|\\mathcal\{H\}\|\\rceil\. ∎

The results in this subsection are best\-case upper\-bound statements\. They prove that for a finite hypothesis classℋ\\mathcal\{H\},

∃h∈ℋ:cert\(h,ℋ\)≤O\(log\|ℋ\|\)\.\\exists h\\in\\mathcal\{H\}:\\quad\\operatorname\{cert\}\(h,\\mathcal\{H\}\)\\leq O\(\\log\|\\mathcal\{H\}\|\)\.The lower bounds in[Section˜4\.2](https://arxiv.org/html/2605.22964#S4.SS2)have a different quantifier order\. For example, the threshold\-circuit result proves that for everyf⋆∈TCd,s0f^\{\\star\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\}, the certificate size in the larger classcert⁡\(f⋆,TCd,s\+10\)\\operatorname\{cert\}\(f^\{\\star\},\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}\)is exponential\. There is no contradiction\. The small certificate size guaranteed inside the enlarged class need not lie in the smaller target class\. Thus the same class can contain large and very small certificate sizes for different targets\.

## Appendix BCircuit constructions and proofs

### B\.1Counting bounds for circuit classes

In the following, we instantiate the principle of[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1), showing that there exist hypotheses with polynomial certificate size across our different circuit classes\.

###### Proposition B\.1\(Existence of a polynomial certificate size inTCd,s0\\mathrm\{TC\}^\{0\}\_\{d,s\}\)\.

Fixn∈ℕn\\in\\mathbb\{N\}, depthd≥1d\\geq 1, ands≥1s\\geq 1, and letℋ:=TCd,s0\\mathcal\{H\}:=\\mathrm\{TC\}^\{0\}\_\{d,s\}be the semantic class of Boolean functions computable by depth\-ddthreshold circuits withnnexternal inputs and at mostssgates\. Then there existsf∈ℋf\\in\\mathcal\{H\}with

cert⁡\(f,ℋ\)≤O​\(s​\(n\+s\)2\)\.\\operatorname\{cert\}\(f,\\mathcal\{H\}\)\\leq O\\bigl\(s\\,\(n\+s\)^\{2\}\\bigr\)\.In particular, ifddis fixed ands=nO​\(1\)s=n^\{O\(1\)\}, thenℋ\\mathcal\{H\}contains some function with polynomial certificate size\. The same holds for the one\-gate enlargementTCd,s\+10\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}by substitutings←s\+1s\\leftarrow s\+1\.

###### Proof\.

For fixednn,ℋ\\mathcal\{H\}is finite \(it is a set of Boolean functions on\{0,1\}n\\\{0,1\\\}^\{n\}\)\.

LetT​\(n\)T\(n\)be the number of distinct Boolean linear threshold functions onnnBoolean inputs\. From\[[5](https://arxiv.org/html/2605.22964#bib.bib5)\], we obtain that

log2⁡T​\(n\)=O​\(n2\)\.\\log\_\{2\}T\(n\)=O\(n^\{2\}\)\.
To canonize each entry, we may delete unused gates and, if necessary, pad with dummy gates\. Then, we topologically order thessgates\. Since gateiidepends on at mostn\+i−1≤n\+sn\+i\-1\\leq n\+spreviously available outputs, it hasT​\(n\+s\)T\(n\+s\)possible Boolean behaviors, hence

\|ℋ\|≤T​\(n\+s\)s≤2O​\(s​\(n\+s\)2\)\.\|\\mathcal\{H\}\|\\leq T\(n\+s\)^\{s\}\\leq 2^\{O\(s\(n\+s\)^\{2\}\)\}\.The claim follows by applying[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1)\. ∎

###### Proposition B\.2\(Existence of a polynomial certificate size inACd,s0\\mathrm\{AC\}^\{0\}\_\{d,s\}\)\.

Fixn,s,d∈ℕn,s,d\\in\\mathbb\{N\}and letℋ:=ACd,s0\\mathcal\{H\}:=\\mathrm\{AC\}^\{0\}\_\{d,s\}be the semantic class of depth\-ddunbounded\-fan\-in Boolean circuits withnnexternal inputs and at mostssgates\. Then there existsf∈ℋf\\in\\mathcal\{H\}such that

cert⁡\(f,ℋ\)≤O​\(s​\(n\+s\)\)\.\\operatorname\{cert\}\\bigl\(f,\\mathcal\{H\}\\bigr\)\\leq O\\bigl\(s\(n\+s\)\\bigr\)\.In particular, for constantddands=nO​\(1\)s=n^\{O\(1\)\}, the class contains at least one function with polynomial certificate size\.

###### Proof\.

Count circuits under the free\-literal convention from[Section˜3](https://arxiv.org/html/2605.22964#S3)and order thessinternal gates\. At gateii, the available signals consist of the2​n2ninput literals and at mosti−1i\-1previous gate outputs\. An AND/OR gate chooses a subset of these available signals and one of two types, giving at most2⋅22​n\+s\+12\\cdot 2^\{2n\+s\+1\}choices per gate\. Therefore\|ℋ\|≤\(2⋅22​n\+s\)s\|\\mathcal\{H\}\|\\leq\(2\\cdot 2^\{2n\+s\}\)^\{s\}and the claim follows by applying[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1)\. ∎

###### Proposition B\.3\(Existence of a polynomial certificate size in bounded\-size fan\-in\-22circuit classes\)\.

Fixn,s,d∈ℕn,s,d\\in\\mathbb\{N\}, and letℋ\\mathcal\{H\}be the semantic class of Boolean functions computable by fan\-in\-22Boolean circuits withnnexternal inputs, size at mostss, and depth at mostdd\. Then there existsf∈ℋf\\in\\mathcal\{H\}such that

cert⁡\(f,ℋ\)≤O​\(s​log⁡\(n\+s\)\)\.\\operatorname\{cert\}\(f,\\mathcal\{H\}\)\\leq O\\bigl\(s\\log\(n\+s\)\\bigr\)\.Moreover, for every fixedc\>0c\>0, the same conclusion holds forNCs1\\mathrm\{NC\}^\{1\}\_\{s\}, the class of fan\-in\-22circuits withnninputs, size at mostss, and depth at mostc​log⁡nc\\log n\. In particular, ifs=nO​\(1\)s=n^\{O\(1\)\}, thenNCs1\\mathrm\{NC\}^\{1\}\_\{s\}contains a function with polynomial certificate size\.

###### Proof\.

We count the circuits after topologically ordering thessgates, where gateiimay read from at mostn\+i−1≤n\+sn\+i\-1\\leq n\+spreviously available signals\. Thus each gate has at most3​\(n\+s\)23\(n\+s\)^\{2\}possible descriptions, accounting for∧,∨,¬\\wedge,\\vee,\\neggates\. Hence\|ℋ\|≤\(3​\(n\+s\)2\)s\|\\mathcal\{H\}\|\\leq\(3\(n\+s\)^\{2\}\)^\{s\}and applying[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1)finishes the proof\. The same argument applies to the subclassNCs1⊆ℋ\\mathrm\{NC\}^\{1\}\_\{s\}\\subseteq\\mathcal\{H\}withd=⌊c​log⁡n⌋d=\\lfloor c\\log n\\rfloor\. Ifs=nO​\(1\)s=n^\{O\(1\)\}, the bound is polynomial innn\. ∎

### B\.2Threshold circuits

###### Proposition B\.4\(Same\-depth threshold\-circuit deceivers\)\.

LetC⋆C^\{\\star\}be a threshold circuit of sizessand depth at mostddcomputingf⋆f^\{\\star\}, whered≥2d\\geq 2\. FixI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=tand a patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}\. Then:

1. \(i\)there is a threshold gateCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}of depth11such that CHECKI,π​\(x\)=1⇔x∈Bπ;\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)=1\\iff x\\in B\_\{\\pi\};
2. \(ii\)for eachσ∈\{0,1\}\\sigma\\in\\\{0,1\\\}there is a threshold circuitCπ,σC\_\{\\pi,\\sigma\}of size at mosts\+1s\+1and depth at mostddsuch that gπ,σ​\(x\):=\{σ,x∈Bπ,f⋆​\(x\),x∉Bπ,g\_\{\\pi,\\sigma\}\(x\):=\\begin\{cases\}\\sigma,&x\\in B\_\{\\pi\},\\\\ f^\{\\star\}\(x\),&x\\notin B\_\{\\pi\},\\end\{cases\}wheregπ,σ∈TCd,s\+10g\_\{\\pi,\\sigma\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}and eithergπ,0g\_\{\\pi,0\}orgπ,1g\_\{\\pi,1\}differs fromf⋆f^\{\\star\}on at least\|Bπ\|/2\|B\_\{\\pi\}\|/2points ofBπB\_\{\\pi\}\.

###### Proof\.

Let the output gate ofC⋆C^\{\\star\}be

f⋆​\(x\)=𝟏​\[∑j=1mwj​zj​\(x\)≥θ\],f^\{\\star\}\(x\)=\\mathbf\{1\}\\\!\\left\[\\sum\_\{j=1\}^\{m\}w\_\{j\}z\_\{j\}\(x\)\\geq\\theta\\right\],where eachzjz\_\{j\}is the output of a depth\-\(d−1\)\(d\-1\)subcircuit\.

For the trigger, let

t1:=\|\{i∈I:πi=1\}\|,t\_\{1\}:=\|\\\{i\\in I:\\pi\_\{i\}=1\\\}\|,and define

CHECKI,π​\(x\):=𝟏​\[∑i∈I:πi=1xi−∑i∈I:πi=0xi≥t1\]\.\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\):=\\mathbf\{1\}\\\!\\left\[\\sum\_\{i\\in I:\\pi\_\{i\}=1\}x\_\{i\}\-\\sum\_\{i\\in I:\\pi\_\{i\}=0\}x\_\{i\}\\geq t\_\{1\}\\right\]\.Ifx∈Bπx\\in B\_\{\\pi\}, then each coordinate withπi=1\\pi\_\{i\}=1contributes11and each coordinate withπi=0\\pi\_\{i\}=0contributes0, so the sum is exactlyt1t\_\{1\}and the gate outputs11\. Ifx∉Bπx\\notin B\_\{\\pi\}, then either some required\-11coordinate contributes0or some required\-0coordinate contributes−1\-1, so the sum is strictly less thant1t\_\{1\}and the gate outputs0\. This proves \(i\)\.

Now choose

M:=∑j=1m\|wj\|\+\|θ\|\+1\.M:=\\sum\_\{j=1\}^\{m\}\|w\_\{j\}\|\+\|\\theta\|\+1\.Because eachzj​\(x\)∈\{0,1\}z\_\{j\}\(x\)\\in\\\{0,1\\\}, the quantity∑jwj​zj​\(x\)\\sum\_\{j\}w\_\{j\}z\_\{j\}\(x\)always lies in the interval

\[−∑j\|wj\|,∑j\|wj\|\]\.\\left\[\-\\sum\_\{j\}\|w\_\{j\}\|,\\ \\sum\_\{j\}\|w\_\{j\}\|\\right\]\.Hence for everyxx,

∑jwj​zj​\(x\)−M<θand∑jwj​zj​\(x\)\+M≥θ\.\\sum\_\{j\}w\_\{j\}z\_\{j\}\(x\)\-M<\\theta\\qquad\\text\{and\}\\qquad\\sum\_\{j\}w\_\{j\}z\_\{j\}\(x\)\+M\\geq\\theta\.
Define the modified output gate by

g~π,0​\(x\):=𝟏​\[∑j=1mwj​zj​\(x\)−M​CHECKI,π​\(x\)≥θ\],\\widetilde\{g\}\_\{\\pi,0\}\(x\):=\\mathbf\{1\}\\\!\\left\[\\sum\_\{j=1\}^\{m\}w\_\{j\}z\_\{j\}\(x\)\-M\\,\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)\\geq\\theta\\right\],and similarly

g~π,1​\(x\):=𝟏​\[∑j=1mwj​zj​\(x\)\+M​CHECKI,π​\(x\)≥θ\]\.\\widetilde\{g\}\_\{\\pi,1\}\(x\):=\\mathbf\{1\}\\\!\\left\[\\sum\_\{j=1\}^\{m\}w\_\{j\}z\_\{j\}\(x\)\+M\\,\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)\\geq\\theta\\right\]\.OutsideBπB\_\{\\pi\}we haveCHECKI,π​\(x\)=0\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)=0, so both modified output gates compute exactlyf⋆​\(x\)f^\{\\star\}\(x\)\. InsideBπB\_\{\\pi\}we haveCHECKI,π​\(x\)=1\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)=1; the first modified gate is forced to0and the second is forced to11by the choice ofMM\. Thusg~π,σ=gπ,σ\\widetilde\{g\}\_\{\\pi,\\sigma\}=g\_\{\\pi,\\sigma\}forσ∈\{0,1\}\\sigma\\in\\\{0,1\\\}\.

The only new gate isCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}\. The output gate is replaced rather than duplicated, so the size increases by at most11\. If the original circuit has depthd⋆≤dd^\{\\star\}\\leq d, then the subcircuits feeding its output gate have depth at mostd⋆−1d^\{\\star\}\-1\. SinceCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}has depth11, the modified output gate has depth at most

1\+max⁡\{1,d⋆−1\}≤d,1\+\\max\\\{1,d^\{\\star\}\-1\\\}\\leq d,usingd≥2d\\geq 2\. All gates remain threshold gates\. ∎

###### Theorem B\.1\(Restatement of Theorem[4\.1](https://arxiv.org/html/2605.22964#S4.Thmtheorem1)\)\.

Fix a constant depthd≥2d\\geq 2\. For every input lengthnn, every gate budgetss, every targetf⋆∈TCd,s0f^\{\\star\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\}, and every trigger length1≤t≤n1\\leq t\\leq n,

cert⁡\(f⋆,TCd,s\+10\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}\\bigr\)\\geq 2^\{t\}\.Consequently, along any sequence of input lengths, if the chosen trigger lengths satisfyc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some fixedc\>0c\>0, then the lower bound is2Ω​\(n\)2^\{\\Omega\(n\)\}\. Moreover, ifs​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}, then for all sufficiently largennthere existsfn∈TCd,s​\(n\)0f\_\{n\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}such that

cert⁡\(fn,TCd,s​\(n\)0\)≤nO​\(1\)whilecert⁡\(fn,TCd,s​\(n\)\+10\)≥2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}\\bigr\)\\leq n^\{O\(1\)\}\\quad\\text\{while\}\\quad\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\+1\}\\bigr\)\\geq 2^\{\\Omega\(n\)\}\.

###### Proof\.

Choose a threshold circuitC⋆C^\{\\star\}of size at mostssand depth at mostddcomputingf⋆f^\{\\star\}\. Fix any coordinate setI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=t\. For eachπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, chooseσπ\\sigma\_\{\\pi\}as in[Remark˜B\.1](https://arxiv.org/html/2605.22964#A2.Thmremark1), and letgπ:=gπ,σπg\_\{\\pi\}:=g\_\{\\pi,\\sigma\_\{\\pi\}\}be the corresponding one\-gate override from[Proposition˜B\.4](https://arxiv.org/html/2605.22964#A2.Thmproposition4)\. Thengπ∈TCd,s\+10g\_\{\\pi\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}and by construction,gπg\_\{\\pi\}agrees withf⋆f^\{\\star\}outside the trigger blockBπB\_\{\\pi\}and differs fromf⋆f^\{\\star\}on at least one point ofBπB\_\{\\pi\}\. Since the blocksBπB\_\{\\pi\}are pairwise disjoint,[Proposition˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmproposition1)gives

cert⁡\(f⋆,TCd,s\+10\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathrm\{TC\}^\{0\}\_\{d,s\+1\}\\bigr\)\\geq 2^\{t\}\.The asymptotic consequence follows wheneverc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some fixedc\>0c\>0\. It remains to justify the best\-case, non\-vacuity statement\. By[Proposition˜B\.1](https://arxiv.org/html/2605.22964#A2.Thmproposition1), for eachnnthere exists somefn∈TCd,s​\(n\)0f\_\{n\}\\in\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}satisfying

cert⁡\(fn,TCd,s​\(n\)0\)≤O​\(s​\(n\)​\(n\+s​\(n\)\)2\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\}\\bigr\)\\leq O\\bigl\(s\(n\)\(n\+s\(n\)\)^\{2\}\\bigr\)\.Whens​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}, this bound is polynomial innn\. Applying the target\-wise lower bound above to this samefnf\_\{n\}with, say,t=⌊n/2⌋t=\\lfloor n/2\\rfloor, yields

cert⁡\(fn,TCd,s​\(n\)\+10\)≥2⌊n/2⌋=2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{TC\}^\{0\}\_\{d,s\(n\)\+1\}\\bigr\)\\geq 2^\{\\lfloor n/2\\rfloor\}=2^\{\\Omega\(n\)\}\.Thus the exponential lower bound in the enlarged class is not inherited from a target that was already hard to certify in the smaller class\. ∎

### B\.3Unbounded\-fan\-in Boolean circuits

###### Proposition B\.5\(Depth\-preserving one\-sided deceivers inAC0\\mathrm\{AC\}^\{0\}\)\.

LetC⋆C^\{\\star\}be a depth\-ddunbounded\-fan\-in Boolean circuit of sizesscomputingf⋆f^\{\\star\}, under the free\-literalAC0\\mathrm\{AC\}^\{0\}convention of[Section˜3](https://arxiv.org/html/2605.22964#S3), withd≥2d\\geq 2\. FixI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=tand a patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}\.

Define

CHECKI,π​\(x\):=⋀i∈Iℓi​\(x\),ℓi​\(x\)=\{xi,πi=1,¬xi,πi=0,\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\):=\\bigwedge\_\{i\\in I\}\\ell\_\{i\}\(x\),\\qquad\\ell\_\{i\}\(x\)=\\begin\{cases\}x\_\{i\},&\\pi\_\{i\}=1,\\\\ \\neg x\_\{i\},&\\pi\_\{i\}=0,\\end\{cases\}and

MISSI,π​\(x\):=⋁i∈Imi​\(x\),mi​\(x\)=\{¬xi,πi=1,xi,πi=0\.\\mathrm\{MISS\}\_\{I,\\pi\}\(x\):=\\bigvee\_\{i\\in I\}m\_\{i\}\(x\),\\qquad m\_\{i\}\(x\)=\\begin\{cases\}\\neg x\_\{i\},&\\pi\_\{i\}=1,\\\\ x\_\{i\},&\\pi\_\{i\}=0\.\\end\{cases\}Then:

1. \(i\)CHECKI,π​\(x\)=1\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)=1iffx∈Bπx\\in B\_\{\\pi\};
2. \(ii\)MISSI,π​\(x\)=0\\mathrm\{MISS\}\_\{I,\\pi\}\(x\)=0iffx∈Bπx\\in B\_\{\\pi\};
3. \(iii\)if the output gate ofC⋆C^\{\\star\}is an OR gate, then gπ,1​\(x\):=f⋆​\(x\)∨CHECKI,π​\(x\)g\_\{\\pi,1\}\(x\):=f^\{\\star\}\(x\)\\vee\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)belongs toACd,s\+10\\mathrm\{AC\}^\{0\}\_\{d,s\+1\}, and gπ,1​\(x\)=\{1,x∈Bπ,f⋆​\(x\),x∉Bπ;g\_\{\\pi,1\}\(x\)=\\begin\{cases\}1,&x\\in B\_\{\\pi\},\\\\ f^\{\\star\}\(x\),&x\\notin B\_\{\\pi\};\\end\{cases\}
4. \(iv\)if the output gate ofC⋆C^\{\\star\}is an AND gate, then gπ,0​\(x\):=f⋆​\(x\)∧MISSI,π​\(x\)g\_\{\\pi,0\}\(x\):=f^\{\\star\}\(x\)\\wedge\\mathrm\{MISS\}\_\{I,\\pi\}\(x\)belongs toACd,s\+10\\mathrm\{AC\}^\{0\}\_\{d,s\+1\}, and gπ,0​\(x\)=\{0,x∈Bπ,f⋆​\(x\),x∉Bπ\.g\_\{\\pi,0\}\(x\)=\\begin\{cases\}0,&x\\in B\_\{\\pi\},\\\\ f^\{\\star\}\(x\),&x\\notin B\_\{\\pi\}\.\\end\{cases\}

###### Proof\.

The identities in \(i\) and \(ii\) are immediate from the definitions\.

For \(iii\), if the top gate ofC⋆C^\{\\star\}is OR, appendCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}as one more input to that same top OR gate\. OutsideBπB\_\{\\pi\}we haveCHECKI,π​\(x\)=0\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)=0, so the circuit still computesf⋆​\(x\)f^\{\\star\}\(x\)\. InsideBπB\_\{\\pi\}we haveCHECKI,π​\(x\)=1\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)=1, so the output is forced to11\. Only one new gate is added, namelyCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}, and the depth remainsdd\.

The proof of \(iv\) is dual: if the top gate ofC⋆C^\{\\star\}is AND, appendMISSI,π\\mathrm\{MISS\}\_\{I,\\pi\}as one more input to that same top AND gate\. OutsideBπB\_\{\\pi\},MISSI,π​\(x\)=1\\mathrm\{MISS\}\_\{I,\\pi\}\(x\)=1, so the output remainsf⋆​\(x\)f^\{\\star\}\(x\)\. InsideBπB\_\{\\pi\},MISSI,π​\(x\)=0\\mathrm\{MISS\}\_\{I,\\pi\}\(x\)=0, so the output is forced to0\. Again, the size increases by at most11and the depth remainsdd\. ∎

One important aspect is that forAC0\\mathrm\{AC\}^\{0\}circuits, we use the standard De Morgan convention that unbounded\-fan\-in AND/OR gates may take literalsxix\_\{i\}and¬xi\\neg x\_\{i\}as inputs, and input negations are not counted toward the gate budget\. Equivalently, NOT gates are allowed only at the input level and are free\.

Under the alternative convention in which every negated literal must be computed by a counted NOT gate, theAC0\\mathrm\{AC\}^\{0\}constant\-slack statement should be weakened fromACd\+1,s\+20\\mathrm\{AC\}^\{0\}\_\{d\+1,s\+2\}toACd\+1,s\+t\+20\\mathrm\{AC\}^\{0\}\_\{d\+1,s\+t\+2\}for a trigger set of sizett\.

###### Theorem B\.2\(Constant\-slack certification hardness inAC0\\mathrm\{AC\}^\{0\}\)\.

Work under the free\-literalAC0\\mathrm\{AC\}^\{0\}convention of[Section˜3](https://arxiv.org/html/2605.22964#S3), and fix a constant depthd≥2d\\geq 2\. For every input lengthnn, every gate budgetss, every targetf⋆∈ACd,s0f^\{\\star\}\\in\\mathrm\{AC\}^\{0\}\_\{d,s\}, and every trigger length1≤t≤n1\\leq t\\leq n,

cert⁡\(f⋆,ACd\+1,s\+20\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathrm\{AC\}^\{0\}\_\{d\+1,s\+2\}\\bigr\)\\geq 2^\{t\}\.Consequently, along any sequence of input lengths, if the chosen trigger lengths satisfyc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some fixedc\>0c\>0, then the lower bound is2Ω​\(n\)2^\{\\Omega\(n\)\}\.

Moreover, ifs​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}, then for all sufficiently largennthere existsfn∈ACd,s​\(n\)0f\_\{n\}\\in\\mathrm\{AC\}^\{0\}\_\{d,s\(n\)\}such that

cert⁡\(fn,ACd,s​\(n\)0\)≤nO​\(1\)whilecert⁡\(fn,ACd\+1,s​\(n\)\+20\)≥2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{AC\}^\{0\}\_\{d,s\(n\)\}\\bigr\)\\leq n^\{O\(1\)\}\\quad\\text\{while\}\\quad\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{AC\}^\{0\}\_\{d\+1,s\(n\)\+2\}\\bigr\)\\geq 2^\{\\Omega\(n\)\}\.

###### Proof\.

Choose anAC0\\mathrm\{AC\}^\{0\}circuitC⋆C^\{\\star\}of size at mostssand depth at mostddcomputingf⋆f^\{\\star\}\. FixI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=t\. For eachπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, chooseσπ∈\{0,1\}\\sigma\_\{\\pi\}\\in\\\{0,1\\\}so that

\|\{x∈Bπ:f⋆​\(x\)≠σπ\}\|≥\|Bπ\|/2\.\|\\\{x\\in B\_\{\\pi\}:f^\{\\star\}\(x\)\\neq\\sigma\_\{\\pi\}\\\}\|\\geq\|B\_\{\\pi\}\|/2\.
Using the trigger gates from[Proposition˜B\.5](https://arxiv.org/html/2605.22964#A2.Thmproposition5), define the override as follows\. Ifσπ=1\\sigma\_\{\\pi\}=1, use one trigger gateCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}and one new top OR gate:

gπ​\(x\)=f⋆​\(x\)∨CHECKI,π​\(x\)\.g\_\{\\pi\}\(x\)=f^\{\\star\}\(x\)\\vee\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)\.Ifσπ=0\\sigma\_\{\\pi\}=0, use one trigger gateMISSI,π\\mathrm\{MISS\}\_\{I,\\pi\}and one new top AND gate:

gπ​\(x\)=f⋆​\(x\)∧MISSI,π​\(x\)\.g\_\{\\pi\}\(x\)=f^\{\\star\}\(x\)\\wedge\\mathrm\{MISS\}\_\{I,\\pi\}\(x\)\.In both cases the trigger gate has unbounded fan\-in and uses input literals for free\. The construction adds one trigger gate and one combining gate above the original circuit, sogπ∈ACd\+1,s\+20g\_\{\\pi\}\\in\\mathrm\{AC\}^\{0\}\_\{d\+1,s\+2\}and it agrees withf⋆f^\{\\star\}outsideBπB\_\{\\pi\}and is equal to the constantσπ\\sigma\_\{\\pi\}onBπB\_\{\\pi\}, hence it differs fromf⋆f^\{\\star\}on at least one point ofBπB\_\{\\pi\}\. The trigger blocks are pairwise disjoint, so[Proposition˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmproposition1)gives

cert⁡\(f⋆,ACd\+1,s\+20\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathrm\{AC\}^\{0\}\_\{d\+1,s\+2\}\\bigr\)\\geq 2^\{t\}\.The asymptotic consequence follows wheneverc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some fixedc\>0c\>0\. For the non\-vacuity statement, apply[Proposition˜B\.2](https://arxiv.org/html/2605.22964#A2.Thmproposition2): whens​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}, the smaller classACd,s​\(n\)0\\mathrm\{AC\}^\{0\}\_\{d,s\(n\)\}contains somefnf\_\{n\}with

cert⁡\(fn,ACd,s​\(n\)0\)≤O​\(s​\(n\)​\(n\+s​\(n\)\)\)=nO​\(1\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{AC\}^\{0\}\_\{d,s\(n\)\}\\bigr\)\\leq O\\bigl\(s\(n\)\(n\+s\(n\)\)\\bigr\)=n^\{O\(1\)\}\.Applying the target\-wise lower bound above to this samefnf\_\{n\}witht=⌊n/2⌋t=\\lfloor n/2\\rfloorgives

cert⁡\(fn,ACd\+1,s​\(n\)\+20\)≥2⌊n/2⌋=2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathrm\{AC\}^\{0\}\_\{d\+1,s\(n\)\+2\}\\bigr\)\\geq 2^\{\\lfloor n/2\\rfloor\}=2^\{\\Omega\(n\)\}\.∎

### B\.4Bounded\-fan\-in circuits andNC1\\mathrm\{NC\}^\{1\}

###### Proposition B\.6\(Bounded\-fan\-in constant\-override deceivers\)\.

LetC⋆C^\{\\star\}be a fan\-in\-22Boolean circuit of sizessand depthddcomputingf⋆f^\{\\star\}\. FixI⊆\[n\]I\\subseteq\[n\]with\|I\|=t≥1\|I\|=t\\geq 1and a patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}\. For eachσ∈\{0,1\}\\sigma\\in\\\{0,1\\\}there is a fan\-in\-22Boolean circuitCπ,σC\_\{\\pi,\\sigma\}of size at mosts\+2​t\+2s\+2t\+2and depth at most1\+max⁡\{d,2\+⌈log2⁡t⌉\}1\+\\max\\\{d,2\+\\lceil\\log\_\{2\}t\\rceil\\\}computing

gπ,σ​\(x\):=\{σ,x∈Bπ,f⋆​\(x\),x∉Bπ\.g\_\{\\pi,\\sigma\}\(x\):=\\begin\{cases\}\\sigma,&x\\in B\_\{\\pi\},\\\\ f^\{\\star\}\(x\),&x\\notin B\_\{\\pi\}\.\\end\{cases\}

###### Proof\.

For eachi∈Ii\\in I, define the literal

ℓi​\(x\)=\{xi,πi=1,¬xi,πi=0\.\\ell\_\{i\}\(x\)=\\begin\{cases\}x\_\{i\},&\\pi\_\{i\}=1,\\\\ \\neg x\_\{i\},&\\pi\_\{i\}=0\.\\end\{cases\}BuildCHECKI,π\\mathrm\{CHECK\}\_\{I,\\pi\}by feeding these literals into a balanced binary AND tree\. This uses at mostttNOT gates andt−1t\-1AND gates, so the trigger circuit has at most2​t−12t\-1gates and depth at most1\+⌈log2⁡t⌉1\+\\lceil\\log\_\{2\}t\\rceil\. It satisfies

CHECKI,π​\(x\)=1⇔x∈Bπ\.\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)=1\\iff x\\in B\_\{\\pi\}\.For the two output overrides, we set

gπ,1​\(x\)=f⋆​\(x\)∨CHECKI,π​\(x\)andgπ,0​\(x\)=f⋆​\(x\)∧¬CHECKI,π​\(x\)\.g\_\{\\pi,1\}\(x\)=f^\{\\star\}\(x\)\\vee\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)\\quad\\text\{ and \}\\quad g\_\{\\pi,0\}\(x\)=f^\{\\star\}\(x\)\\wedge\\neg\\mathrm\{CHECK\}\_\{I,\\pi\}\(x\)\.For the11\-override, outsideBπB\_\{\\pi\}, the trigger is0and the output isf⋆​\(x\)f^\{\\star\}\(x\)\. InsideBπB\_\{\\pi\}, the trigger is11and the output is forced to11\. This adds one OR gate to the trigger circuit\. In contrast, for the0\-override, outsideBπB\_\{\\pi\}, the second input to the final AND is11and the output isf⋆​\(x\)f^\{\\star\}\(x\)\. InsideBπB\_\{\\pi\}, it is0and the output is forced to0\. This adds one NOT gate and one AND gate to the trigger circuit\. In both cases the total size is at mosts\+2​t\+2s\+2t\+2, and the stated depth bound follows from the balanced trigger tree and the final combining gate\. ∎

###### Theorem B\.3\(Bounded fan\-in circuits with trigger\-budget slack\)\.

LetC⋆C^\{\\star\}be a fan\-in\-22Boolean circuit of sizessand depthddcomputingf⋆f^\{\\star\}\. Fix a trigger length1≤t≤n1\\leq t\\leq n, and letℋn,s,d,tBF\\mathcal\{H\}^\{\\mathrm\{BF\}\}\_\{n,s,d,t\}be the class of functions computable by fan\-in\-22Boolean circuits of size at mosts\+2​t\+2s\+2t\+2and depth at most

1\+max⁡\{d,2\+⌈log2⁡t⌉\}\.1\+\\max\\\{d,2\+\\lceil\\log\_\{2\}t\\rceil\\\}\.Then

cert⁡\(f⋆,ℋn,s,d,tBF\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathcal\{H\}^\{\\mathrm\{BF\}\}\_\{n,s,d,t\}\\bigr\)\\geq 2^\{t\}\.Consequently, along any sequence of input lengths, if the chosen trigger lengths satisfyc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some fixedc\>0c\>0, then the lower bound is2Ω​\(n\)2^\{\\Omega\(n\)\}, at the cost of additive gate slack2​t​\(n\)\+2=Θ​\(n\)2t\(n\)\+2=\\Theta\(n\)\.

###### Proof\.

FixI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=t\. For eachπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, chooseσπ∈\{0,1\}\\sigma\_\{\\pi\}\\in\\\{0,1\\\}such that

\|\{x∈Bπ:f⋆​\(x\)≠σπ\}\|≥\|Bπ\|/2\.\|\\\{x\\in B\_\{\\pi\}:f^\{\\star\}\(x\)\\neq\\sigma\_\{\\pi\}\\\}\|\\geq\|B\_\{\\pi\}\|/2\.Letgπ:=gπ,σπg\_\{\\pi\}:=g\_\{\\pi,\\sigma\_\{\\pi\}\}be the constant\-override circuit from[Proposition˜B\.6](https://arxiv.org/html/2605.22964#A2.Thmproposition6)\. Thengπ∈ℋn,s,d,tBFg\_\{\\pi\}\\in\\mathcal\{H\}^\{\\mathrm\{BF\}\}\_\{n,s,d,t\}andgπg\_\{\\pi\}agrees withf⋆f^\{\\star\}outsideBπB\_\{\\pi\}and differs fromf⋆f^\{\\star\}on at least one point ofBπB\_\{\\pi\}\. Since the trigger blocksBπB\_\{\\pi\}are pairwise disjoint,[Proposition˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmproposition1)gives

cert⁡\(f⋆,ℋn,s,d,tBF\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathcal\{H\}^\{\\mathrm\{BF\}\}\_\{n,s,d,t\}\\bigr\)\\geq 2^\{t\}\.∎

###### Corollary B\.1\(NC1\\mathrm\{NC\}^\{1\}with additive slack depending onnn\)\.

Lets,k:ℕ→ℕs,k:\\mathbb\{N\}\\to\\mathbb\{N\}, withk​\(n\)≥4k\(n\)\\geq 4for all sufficiently largenn\. For eachnn, let

𝒞n,sNC:=NCs​\(n\)1,\\mathcal\{C\}^\{\\mathrm\{NC\}\}\_\{n,s\}:=\\mathrm\{NC\}^\{1\}\_\{s\(n\)\},and letℋn,s,kNC\\mathcal\{H\}^\{\\mathrm\{NC\}\}\_\{n,s,k\}be the corresponding enlarged fan\-in\-22class with size at mosts​\(n\)\+k​\(n\)s\(n\)\+k\(n\)and depthO​\(log⁡n\)O\(\\log n\)\. For every targetf⋆∈𝒞n,sNCf^\{\\star\}\\in\\mathcal\{C\}^\{\\mathrm\{NC\}\}\_\{n,s\},

cert⁡\(f⋆,ℋn,s,kNC\)≥2min⁡\{n,⌊k​\(n\)/4⌋\}=2Ω​\(min⁡\{n,k​\(n\)\}\)\.\\operatorname\{cert\}\\\!\\bigl\(f^\{\\star\},\\mathcal\{H\}^\{\\mathrm\{NC\}\}\_\{n,s,k\}\\bigr\)\\geq 2^\{\\min\\\{n,\\lfloor k\(n\)/4\\rfloor\\\}\}=2^\{\\Omega\(\\min\\\{n,k\(n\)\\\}\)\}\.In particular, ifk​\(n\)=Ω​\(n\)k\(n\)=\\Omega\(n\), then

cert⁡\(f⋆,ℋn,s,kNC\)≥2Ω​\(n\)\.\\operatorname\{cert\}\\\!\\bigl\(f^\{\\star\},\\mathcal\{H\}^\{\\mathrm\{NC\}\}\_\{n,s,k\}\\bigr\)\\geq 2^\{\\Omega\(n\)\}\.
Moreover, ifs​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}andk​\(n\)=Ω​\(n\)k\(n\)=\\Omega\(n\), then for all sufficiently largennthere existsfn∈𝒞n,sNCf\_\{n\}\\in\\mathcal\{C\}^\{\\mathrm\{NC\}\}\_\{n,s\}such that

cert⁡\(fn,𝒞n,sNC\)≤nO​\(1\)whilecert⁡\(fn,ℋn,s,kNC\)≥2Ω​\(n\)\.\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathcal\{C\}^\{\\mathrm\{NC\}\}\_\{n,s\}\\bigr\)\\leq n^\{O\(1\)\}\\quad\\text\{while\}\\quad\\operatorname\{cert\}\\bigl\(f\_\{n\},\\mathcal\{H\}^\{\\mathrm\{NC\}\}\_\{n,s,k\}\\bigr\)\\geq 2^\{\\Omega\(n\)\}\.

###### Proof\.

Choose a fan\-in\-22circuitC⋆C^\{\\star\}forf⋆f^\{\\star\}of size at mosts​\(n\)s\(n\)and depthd​\(n\)=O​\(log⁡n\)d\(n\)=O\(\\log n\)\. Set

t:=min⁡\{n,⌊k​\(n\)/4⌋\}\.t:=\\min\\\{n,\\lfloor k\(n\)/4\\rfloor\\\}\.For all sufficiently largenn,k​\(n\)≥4k\(n\)\\geq 4, hence1≤t≤n1\\leq t\\leq n\. By[Theorem˜B\.3](https://arxiv.org/html/2605.22964#A2.Thmtheorem3), there are2t2^\{t\}deceivers, one for each trigger blockBπB\_\{\\pi\}withπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, and each deceiver is computed by a fan\-in\-22circuit of size at most

s​\(n\)\+2​t\+2≤s​\(n\)\+k​\(n\)\.s\(n\)\+2t\+2\\leq s\(n\)\+k\(n\)\.Each deceiver has depth at most

1\+max⁡\{d​\(n\),2\+⌈log2⁡t⌉\}=O​\(log⁡n\),1\+\\max\\\{d\(n\),2\+\\lceil\\log\_\{2\}t\\rceil\\\}=O\(\\log n\),so the whole family lies inℋn,s,kNC\\mathcal\{H\}^\{\\mathrm\{NC\}\}\_\{n,s,k\}\. The certificate lower bound follows from[Proposition˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmproposition1)\.

For the final statement, apply[Proposition˜B\.3](https://arxiv.org/html/2605.22964#A2.Thmproposition3)to the smaller class\. Whens​\(n\)=nO​\(1\)s\(n\)=n^\{O\(1\)\}, it contains somefnf\_\{n\}with polynomial certificate size inside𝒞n,sNC\\mathcal\{C\}^\{\\mathrm\{NC\}\}\_\{n,s\}\. Applying the target\-wise lower bound above to this samefnf\_\{n\}and usingk​\(n\)=Ω​\(n\)k\(n\)=\\Omega\(n\)gives the exponential lower bound in the enlarged class\. ∎

### B\.5Certificate size ofORn\\mathrm\{OR\}\_\{n\}in the base circuit classes

This subsection records two certification facts used to interpret the experiments in[Section˜D\.3](https://arxiv.org/html/2605.22964#A4.SS3)\. Throughout, let

ORn:\{0,1\}n→\{0,1\},ORn​\(x\)=𝟏​\[x1\+⋯\+xn≥1\]\.\\mathrm\{OR\}\_\{n\}:\\\{0,1\\\}^\{n\}\\to\\\{0,1\\\},\\qquad\\mathrm\{OR\}\_\{n\}\(x\)=\\mathbf\{1\}\[x\_\{1\}\+\\cdots\+x\_\{n\}\\geq 1\]\.
We use two base classes\. The classTC0~n,base\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}is the semantic class of Boolean functions computable by depth\-22, size\-22threshold circuits whose gate weights lie in\{−1,0,1\}\\\{\-1,0,1\\\}and whose threshold at fan\-inmmis any integer in\[−m,m\]\[\-m,m\]\. The tilde indicates that this is a bounded finite proxy for theTC0\\mathrm\{TC\}^\{0\}class, rather than the full class used in the general theorem\. The classACn,base0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}is the semantic class of Boolean functions computable by depth\-22, size\-22AC0\\mathrm\{AC\}^\{0\}circuits defined in[Section˜3](https://arxiv.org/html/2605.22964#S3)\. In both definitions, semantic means that two circuits are identified if they compute the same truth table on\{0,1\}n\\\{0,1\\\}^\{n\}\.

For each of these base classes, we show that the certificate size ofORn\\mathrm\{OR\}\_\{n\}is exactlyn\+1n\+1\. The same labeled set certifies it in both cases:

Sn=\{0n,e1,…,en\},ORn​\(0n\)=0,ORn​\(ei\)=1​for all​i∈\[n\]\.S\_\{n\}=\\\{0^\{n\},e\_\{1\},\\ldots,e\_\{n\}\\\},\\qquad\\mathrm\{OR\}\_\{n\}\(0^\{n\}\)=0,\\quad\\mathrm\{OR\}\_\{n\}\(e\_\{i\}\)=1\\ \\text\{for all \}i\\in\[n\]\.The enumeration in[Section˜D\.3](https://arxiv.org/html/2605.22964#A4.SS3)shows that the deterministic halving rule selectsORn\\mathrm\{OR\}\_\{n\}in the completed runs\. The lemmas below explain why the selected target then has minimum certificate sizen\+1n\+1inside the corresponding base class\.

###### Lemma B\.1\(Certification ofORn\\mathrm\{OR\}\_\{n\}in the restricted threshold base class\)\.

LetTC0~n,base\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}be the class of functions computable as

h​\(x\)=𝟏​\[∑i=1nai​xi\+b​z​\(x\)≥θ\],z​\(x\)=𝟏​\[∑i=1nci​xi≥τ\],h\(x\)=\\mathbf\{1\}\\\!\\left\[\\sum\_\{i=1\}^\{n\}a\_\{i\}x\_\{i\}\+bz\(x\)\\geq\\theta\\right\],\\qquad z\(x\)=\\mathbf\{1\}\\\!\\left\[\\sum\_\{i=1\}^\{n\}c\_\{i\}x\_\{i\}\\geq\\tau\\right\],whereai,b,ci∈\{−1,0,1\}a\_\{i\},b,c\_\{i\}\\in\\\{\-1,0,1\\\}and the thresholds are integral in the allowed ranges\. Then

certTC0~n,base⁡\(ORn\)=n\+1\.\\operatorname\{cert\}\_\{\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}\}\(\\mathrm\{OR\}\_\{n\}\)=n\+1\.In particular, the labeled set

Sn=\{0n,e1,…,en\},ORn​\(0n\)=0,ORn​\(ei\)=1​for all​i,S\_\{n\}=\\\{0^\{n\},e\_\{1\},\\ldots,e\_\{n\}\\\},\\qquad\\mathrm\{OR\}\_\{n\}\(0^\{n\}\)=0,\\quad\\mathrm\{OR\}\_\{n\}\(e\_\{i\}\)=1\\ \\text\{for all \}i,certifiesORn\\mathrm\{OR\}\_\{n\}insideTC0~n,base\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}\.

###### Proof\.

First,SnS\_\{n\}is necessary\. If0n0^\{n\}is omitted, then the constant\-one function agrees withORn\\mathrm\{OR\}\_\{n\}on all remaining queried points and disagrees only at0n0^\{n\}\. Ifeie\_\{i\}is omitted, thenx↦⋁j≠ixjx\\mapsto\\bigvee\_\{j\\neq i\}x\_\{j\}agrees withORn\\mathrm\{OR\}\_\{n\}on all remaining queried points and disagrees only ateie\_\{i\}\. Both functions are inTC0~n,base\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}, using the output gate directly and ignoring the hidden gate\. Hence every certificate has size at leastn\+1n\+1\.

It remains to show thatSnS\_\{n\}is sufficient\. Supposeh∈TC0~n,baseh\\in\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}agrees withORn\\mathrm\{OR\}\_\{n\}onSnS\_\{n\}\. Write

s​\(x\)=∑iai​xi\+b​z​\(x\),h​\(x\)=𝟏​\[s​\(x\)≥θ\]\.s\(x\)=\\sum\_\{i\}a\_\{i\}x\_\{i\}\+bz\(x\),\\qquad h\(x\)=\\mathbf\{1\}\[s\(x\)\\geq\\theta\]\.Agreement onSnS\_\{n\}gives

s​\(0n\)<θ≤s​\(ei\)for every​i∈\[n\]\.s\(0^\{n\}\)<\\theta\\leq s\(e\_\{i\}\)\\qquad\\text\{for every \}i\\in\[n\]\.We consider the three possible values ofbb\.

Ifb=0b=0, thens​\(0n\)=0s\(0^\{n\}\)=0, soθ\>0\\theta\>0\. Sinceθ≤ai≤1\\theta\\leq a\_\{i\}\\leq 1for everyii, we haveθ=1\\theta=1andai=1a\_\{i\}=1for allii\. Therefore every nonzeroxxhass​\(x\)≥1=θs\(x\)\\geq 1=\\theta, soh​\(x\)=ORn​\(x\)h\(x\)=\\mathrm\{OR\}\_\{n\}\(x\)\.

Ifb=1b=1, then the hidden gate can add at most one unit\. Ifz​\(0n\)=1z\(0^\{n\}\)=1, thenz​\(0n\)<θz\(0^\{n\}\)<\\thetaforcesθ=2\\theta=2, andθ≤ai\+z​\(ei\)≤2\\theta\\leq a\_\{i\}\+z\(e\_\{i\}\)\\leq 2forcesai=z​\(ei\)=1a\_\{i\}=z\(e\_\{i\}\)=1for everyii\. Every nonzero input is then accepted\. Ifz​\(0n\)=0z\(0^\{n\}\)=0, thenθ∈\{1,2\}\\theta\\in\\\{1,2\\\}\. The caseθ=2\\theta=2again forcesai=z​\(ei\)=1a\_\{i\}=z\(e\_\{i\}\)=1for everyii\. In the caseθ=1\\theta=1, each coordinate satisfiesai\+z​\(ei\)≥1a\_\{i\}\+z\(e\_\{i\}\)\\geq 1\. Thus eitherai=1a\_\{i\}=1, orai=0a\_\{i\}=0andz​\(ei\)=1z\(e\_\{i\}\)=1\. LetJ=\{i:ai=0\}J=\\\{i:a\_\{i\}=0\\\}\. Fori∈Ji\\in J, the conditionsz​\(0n\)=0z\(0^\{n\}\)=0andz​\(ei\)=1z\(e\_\{i\}\)=1force the hidden threshold to haveτ=1\\tau=1andci=1c\_\{i\}=1\. Hencez​\(x\)=1z\(x\)=1on every nonempty input supported insideJJ\. Inputs using a coordinate outsideJJalready have direct score at least one\. Thus every nonzeroxxis accepted\.

Finally supposeb=−1b=\-1\. Ifz​\(0n\)=0z\(0^\{n\}\)=0, then0<θ≤ai−z​\(ei\)≤10<\\theta\\leq a\_\{i\}\-z\(e\_\{i\}\)\\leq 1, soθ=1\\theta=1,ai=1a\_\{i\}=1, andz​\(ei\)=0z\(e\_\{i\}\)=0for everyii\. Singletons are accepted by assumption, and every input of Hamming weight at least two has direct score at least two, so subtracting the hidden gate still leaves score at least one\. Ifz​\(0n\)=1z\(0^\{n\}\)=1, thenθ∈\{0,1\}\\theta\\in\\\{0,1\\\}\. The caseθ=1\\theta=1is the same as before\. In the caseθ=0\\theta=0, the inequalities0≤ai−z​\(ei\)0\\leq a\_\{i\}\-z\(e\_\{i\}\)imply thatai∈\{0,1\}a\_\{i\}\\in\\\{0,1\\\}, and wheneverai=0a\_\{i\}=0we must havez​\(ei\)=0z\(e\_\{i\}\)=0\. LetJ=\{i:ai=0\}J=\\\{i:a\_\{i\}=0\\\}\. Sincez​\(0n\)=1z\(0^\{n\}\)=1andz​\(ei\)=0z\(e\_\{i\}\)=0fori∈Ji\\in J, the hidden gate must satisfyτ=0\\tau=0andci=−1c\_\{i\}=\-1on those coordinates\. Consequentlyz​\(x\)=0z\(x\)=0on every nonempty input supported insideJJ\. Inputs using a coordinate outsideJJhave direct score at least one, and subtracting the hidden gate leaves score at least zero\. Hence every nonzero input is accepted\.

In all cases,h​\(x\)=1h\(x\)=1for everyx≠0nx\\neq 0^\{n\}, whileh​\(0n\)=0h\(0^\{n\}\)=0\. Thereforeh=ORnh=\\mathrm\{OR\}\_\{n\}, andSnS\_\{n\}is a certificate of sizen\+1n\+1\. ∎

###### Lemma B\.2\(Certification ofORn\\mathrm\{OR\}\_\{n\}in the free\-literalAC0\\mathrm\{AC\}^\{0\}base class\)\.

Forn≥2n\\geq 2,

certACn,base0⁡\(ORn\)=n\+1\.\\operatorname\{cert\}\_\{\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}\}\(\\mathrm\{OR\}\_\{n\}\)=n\+1\.In particular, the same labeled set

Sn=\{0n,e1,…,en\}S\_\{n\}=\\\{0^\{n\},e\_\{1\},\\ldots,e\_\{n\}\\\}certifiesORn\\mathrm\{OR\}\_\{n\}insideACn,base0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}\.

###### Proof\.

The lower bound is the same as above\. If0n0^\{n\}is omitted, the constant\-one function agrees withORn\\mathrm\{OR\}\_\{n\}on all remaining queried points\. Ifeie\_\{i\}is omitted, then⋁j≠ixj\\bigvee\_\{j\\neq i\}x\_\{j\}agrees withORn\\mathrm\{OR\}\_\{n\}on all remaining queried points\. Both functions belong toACn,base0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}\. Thus every certificate has size at leastn\+1n\+1\.

For sufficiency, supposeh∈ACn,base0h\\in\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}agrees withORn\\mathrm\{OR\}\_\{n\}onSnS\_\{n\}\. Consider the top gate of a size\-22, depth\-22representative forhh\.

If the top gate is an AND gate, then no direct literal can feed into it\. A positive literalxjx\_\{j\}rejectseie\_\{i\}for everyi≠ji\\neq j, and a negative literal¬xj\\neg x\_\{j\}rejectseje\_\{j\}\. Thus the value must be determined by the lower gate\. That lower gate must be0on0n0^\{n\}and11on everyeie\_\{i\}\. An AND gate cannot have this behavior\. An OR gate can have this behavior only if it contains all positive literalsx1,…,xnx\_\{1\},\\ldots,x\_\{n\}and no negative literal\. Thus the function isORn\\mathrm\{OR\}\_\{n\}\.

If the top gate is an OR gate, then every input to the top gate must be0on0n0^\{n\}\. Hence direct literals at the top can only be positive literals\. The lower gate, if present, must also be0on0n0^\{n\}\. If the lower gate is an OR gate, then it also contains only positive literals, so the whole circuit is an OR of positive literals\. Since all one\-hot inputs are accepted, all variables must appear, and the function isORn\\mathrm\{OR\}\_\{n\}\. If the lower gate is an AND gate, then it can be true on at most one one\-hot input while remaining false on0n0^\{n\}\. All remaining one\-hot inputs must be accepted by direct positive literals at the top\. Any nonzero input is then accepted either by one of those direct literals or, in the single uncovered one\-hot case, by the lower gate\. Thus the function is againORn\\mathrm\{OR\}\_\{n\}\.

ThereforeSnS\_\{n\}is sufficient, and the certificate size isn\+1n\+1\. ∎

## Appendix CAdditional theory for Transformers

### C\.1Background and definitions

###### Theorem C\.1\(Merrill and Sabharwal\[[22](https://arxiv.org/html/2605.22964#bib.bib22)\]\)\.

Every language computed by a log\-precision Transformer family withL=O​\(1\)L=O\(1\)layers and logspace\-uniform access to its parameters and embeddings is contained in logspace\-uniformTC0\\mathrm\{TC\}^\{0\}\.

This containment explains why constant\-depth threshold circuits are a natural class to analyze\. For the present paper, however, we work in a more specific exact\-attention subclass tailored to the deceiver construction\.

### C\.2Precision conventions

Following the log\-precision formalization ofMerrill and Sabharwal \[[22](https://arxiv.org/html/2605.22964#bib.bib22),[21](https://arxiv.org/html/2605.22964#bib.bib21)\], we treat*precisionpp*as a*datatype budget*: every scalar that appears in a forward pass lives in a finite setDpD\_\{p\}ofpp\-bit floating\-point values, and every arithmetic operation is evaluated with*pp\-truncation*\(i\.e\., the exact real result is mapped back intoDpD\_\{p\}\)\. Writeτp\\tau\_\{p\}for this truncation/saturation map\.

We will not need the exact bit\-level float encoding\. The arguments in this appendix use only the following standard consequences of the Merrill conventions\.

1. \(a\)Bounded range and saturation\.EachDpD\_\{p\}has a largest representable magnitudeFpmaxF\_\{p\}^\{\\max\}such that\|x\|≤Fpmax\|x\|\\leq F\_\{p\}^\{\\max\}for allx∈Dpx\\in D\_\{p\}\. When an arithmetic operation overflows, the truncation map saturates to±Fpmax\\pm F\_\{p\}^\{\\max\}, preserving sign\.
2. \(b\)Fixed constants\.The trigger\-head gadget below uses only a fixed set of small dyadic rationals \(e\.g\.,0,±12,±1,20,\\pm\\tfrac\{1\}\{2\},\\pm 1,2\), which are exactly representable onceppexceeds a small absolute constantp0p\_\{0\}\.
3. \(c\)Fixed evaluation order\.Finite\-precision addition need not be associative\. Whenever the construction displays a nested expression involvingτp\\tau\_\{p\}, the displayed nesting is part of the finite\-precision arithmetic graph used by that readout\.

The trigger\-head parameters below use only fixed dyadic constants, so they are representable oncep≥p0p\\geq p\_\{0\}for an absolute constantp0p\_\{0\}\. The final readout also usesFpmaxF\_\{p\}^\{\\max\}, which is representable by definition\. Therefore, the construction keeps the inherited Transformer computation at the same precisionpp, and the final readout uses two copies of the trigger bit to force the desired output at that same precision\.

### C\.3Transformers and threshold circuits

We record a Transformer\-to\-circuit containment for the constructions used in this paper\. The statement is phrased for the projected\-pre\-norm AHAT classifiers used in this paper\. The only asymptotic requirement is that the precision remain logarithmic and that the parameters be accessible uniformly\.

###### Proposition C\.1\(Log\-precision AHAT Transformers are inTC0\\mathrm\{TC\}^\{0\}\)\.

Let𝒯=\{Tn\}n≥1\\mathcal\{T\}=\\\{T\_\{n\}\\\}\_\{n\\geq 1\}be a family of projected\-pre\-normp​\(n\)p\(n\)\-precision AHAT Transformer binary classifiers over\{0,1\}n\\\{0,1\\\}^\{n\}\. Assume the following\.

1. \(i\)The number of layers is constant\.
2. \(ii\)The number of heads, residual dimension, projected dimensions, and feedforward widths are bounded bynO​\(1\)n^\{O\(1\)\}\.
3. \(iii\)The precision satisfiesp​\(n\)=O​\(log⁡n\)p\(n\)=O\(\\log n\), and every numerical operation is evaluated in thep​\(n\)p\(n\)\-bit datatypeDp​\(n\)D\_\{p\(n\)\}\.
4. \(iv\)The embedding function and all parameter bits are DLOGTIME\-uniform innn\.

Then the language

L𝒯:=\{x∈\{0,1\}∗:T\|x\|​\(x\)=1\}L\_\{\\mathcal\{T\}\}:=\\\{x\\in\\\{0,1\\\}^\{\\ast\}:T\_\{\|x\|\}\(x\)=1\\\}belongs to DLOGTIME\-uniformTC0\\mathrm\{TC\}^\{0\}\. If the parameter family is only logspace\-uniform, thenL𝒯L\_\{\\mathcal\{T\}\}belongs to logspace\-uniformTC0\\mathrm\{TC\}^\{0\}\. If the parameters are treated as arbitrary advice, thenL𝒯L\_\{\\mathcal\{T\}\}belongs to non\-uniformTC0\\mathrm\{TC\}^\{0\}\.

###### Proof\.

Fix an input lengthnn\. We build a polynomial\-size, constant\-depth threshold circuit that simulatesTnT\_\{n\}on inputs in\{0,1\}n\\\{0,1\\\}^\{n\}\.

Each element ofDp​\(n\)D\_\{p\(n\)\}is represented byO​\(p​\(n\)\)=O​\(log⁡n\)O\(p\(n\)\)=O\(\\log n\)bits\. The standard arithmetic operations onO​\(log⁡n\)O\(\\log n\)\-bit integers, rationals, and finite\-precision floats used by log\-precision Transformers are computable in uniformTC0\\mathrm\{TC\}^\{0\}: addition, multiplication, comparison, maximum, iterated addition, iterated multiplication, truncated division, rounding, and the finite\-precision square\-root/inverse\-square\-root operations used in layer normalization are all in uniformTC0\\mathrm\{TC\}^\{0\}\(see, for example,Merrill and Sabharwal \[[21](https://arxiv.org/html/2605.22964#bib.bib21),[22](https://arxiv.org/html/2605.22964#bib.bib22)\]and the arithmetic summary inChiang \[[9](https://arxiv.org/html/2605.22964#bib.bib9), Theorem 2 and Lemmas 10–12\]\)\. We also use thatTC0\\mathrm\{TC\}^\{0\}is closed under polynomially many parallel copies and under a constant number of serial compositions\.

We first consider the non\-attention components\. Embeddings are computed by DLOGTIME\-uniform lookup\. Every affine map in the query, key, value, feedforward, projection, and final classifier blocks is a polynomial\-size collection of products followed by an iterated sum and a truncation/rounding back toDp​\(n\)D\_\{p\(n\)\}, hence is computable in uniformTC0\\mathrm\{TC\}^\{0\}\. The ReLU and final binary threshold are computed by comparison, so they are also in uniformTC0\\mathrm\{TC\}^\{0\}\. The projected\-pre\-norm operation first applies an affine projection and then performs finite\-precision layer normalization\. The mean, centered coordinates, squared norm, and final rescaling are obtained from iterated addition, multiplication, division, and inverse square root, and hence are computable in uniformTC0\\mathrm\{TC\}^\{0\}under the samep​\(n\)p\(n\)\-precision convention\.

It remains only to check the AHAT operation\. Fix a layer, a head, and a query positionii\. For every key positionjj, the circuit computes the score

si​j=⟨qi,kj⟩s\_\{ij\}=\\langle q\_\{i\},k\_\{j\}\\rangleand the value vectorvjv\_\{j\}in parallel\. It then computes

Mi:=maxj∈\[n\]⁡si​jM\_\{i\}:=\\max\_\{j\\in\[n\]\}s\_\{ij\}using theTC0\\mathrm\{TC\}^\{0\}maximum operation\. For eachjj, it computes the indicator

mi​j:=𝟏​\[si​j=Mi\]m\_\{ij\}:=\\mathbf\{1\}\[s\_\{ij\}=M\_\{i\}\]by comparison\. The number of maximizers is

ci:=∑j=1nmi​jc\_\{i\}:=\\sum\_\{j=1\}^\{n\}m\_\{ij\}which is nonzero, and for each value coordinaterrthe numerator is

Ni,r:=∑j=1nmi​j​\(vj\)r\.N\_\{i,r\}:=\\sum\_\{j=1\}^\{n\}m\_\{ij\}\(v\_\{j\}\)\_\{r\}\.Both sums are iterated additions of polynomially manyO​\(log⁡n\)O\(\\log n\)\-bit values, and the AHAT output coordinate is the finite\-precision quotient

ai,r:=Ni,r/ci\.a\_\{i,r\}:=N\_\{i,r\}/c\_\{i\}\.Thus one AHAT head is computable in uniformTC0\\mathrm\{TC\}^\{0\}\. All heads and positions are computed in parallel, so the whole attention block is computable in uniformTC0\\mathrm\{TC\}^\{0\}\. Bidirectional attention causes no additional difficulty: the circuit simply ranges over allj∈\[n\]j\\in\[n\]\.

Each layer is a constant serial composition of the components above, and the number of layers is constant\. Therefore the entire forward computation and the final classifier are computed by a constant\-depth, polynomial\-size threshold circuit\. The DLOGTIME\-uniformity of the circuit follows from the DLOGTIME\-uniform parameter access and the regular indexing of positions, heads, coordinates, and layers\. Replacing DLOGTIME\-uniform access by logspace\-uniform access gives the logspace\-uniform version, and dropping uniform access gives the non\-uniform version\. ∎

### C\.4Polynomial\-size certificates exist in log\-precision Transformers

In the following, we instantiate the principle of[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1), showing that there exist hypotheses with polynomial certificate size across our Transformer class\.

###### Proposition C\.2\(Polynomial certificate size for fixed\-architecture log\-precision AHAT grids\)\.

Fix an input lengthnnand a fixed projected\-pre\-norm AHAT Transformer classifier architecture𝖠n\\mathsf\{A\}\_\{n\}overΣn=\{0,1\}n\\Sigma^\{n\}=\\\{0,1\\\}^\{n\}\. The architecture fixes the depth, head layout, residual dimension, projected dimensions, feedforward widths, activation convention, AHAT attention rule, and final\-token linear classifier form\.

LetDpD\_\{p\}be thepp\-precision datatype used in[Appendix˜C](https://arxiv.org/html/2605.22964#A3), with\|Dp\|≤2O​\(p\)\|D\_\{p\}\|\\leq 2^\{O\(p\)\}\. LetP𝖠​\(n\)P\_\{\\mathsf\{A\}\}\(n\)be the total number ofDpD\_\{p\}\-valued scalar slots that are allowed to vary in this architecture\. If the embedding is allowed to vary, we count its finite length\-nntable

e:Σ×\[n\]→Dpme:\\Sigma\\times\[n\]\\to D\_\{p\}^\{m\}as\|Σ\|​n​m\|\\Sigma\|nmof these scalar slots\. Likewise, any finite advice used to specify trigger parameters, positional information, or override constants is either encoded in these slots or counted inP𝖠​\(n\)P\_\{\\mathsf\{A\}\}\(n\)\.

Let𝒯𝖠n,p\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\}be the induced semantic class of Boolean functions onΣn\\Sigma^\{n\}\. Then there existsf∈𝒯𝖠n,pf\\in\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\}such that

cert⁡\(f,𝒯𝖠n,p\)≤O​\(P𝖠​\(n\)​p\)\.\\operatorname\{cert\}\\bigl\(f,\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\}\\bigr\)\\leq O\(P\_\{\\mathsf\{A\}\}\(n\)p\)\.In particular, ifP𝖠​\(n\)=nO​\(1\)P\_\{\\mathsf\{A\}\}\(n\)=n^\{O\(1\)\}andp​\(n\)=O​\(log⁡n\)p\(n\)=O\(\\log n\), then the class contains a function with polynomial certificate size\.

###### Proof\.

Each assignment of theP𝖠​\(n\)P\_\{\\mathsf\{A\}\}\(n\)finite\-precision scalar slots gives one Transformer and hence one Boolean function onΣn\\Sigma^\{n\}\. Since\|Dp\|≤2O​\(p\)\|D\_\{p\}\|\\leq 2^\{O\(p\)\}, the number of parameter assignments is at most

\|Dp\|P𝖠​\(n\)≤2O​\(P𝖠​\(n\)​p\)\.\|D\_\{p\}\|^\{P\_\{\\mathsf\{A\}\}\(n\)\}\\leq 2^\{O\(P\_\{\\mathsf\{A\}\}\(n\)p\)\}\.The semantic class may be smaller because distinct parameter assignments can compute the same Boolean function, so

\|𝒯𝖠n,p\|≤2O​\(P𝖠​\(n\)​p\)\.\|\\mathcal\{T\}\_\{\\mathsf\{A\}\_\{n\},p\}\|\\leq 2^\{O\(P\_\{\\mathsf\{A\}\}\(n\)p\)\}\.Applying[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1)gives the claim\. ∎

###### Corollary C\.1\(Uniform Transformer deceivers remain inTC0\\mathrm\{TC\}^\{0\}\)\.

Let\{Tn⋆\}n≥1\\\{T\_\{n\}^\{\\star\}\\\}\_\{n\\geq 1\}be a projected\-pre\-norm AHAT Transformer family satisfying the hypotheses of[Proposition˜C\.1](https://arxiv.org/html/2605.22964#A3.Thmproposition1), with precisionp​\(n\)=O​\(log⁡n\)p\(n\)=O\(\\log n\)andp​\(n\)≥p0p\(n\)\\geq p\_\{0\}for all sufficiently largenn\. For eachnn, choose a trigger setIn⊆\[n\]I\_\{n\}\\subseteq\[n\], a trigger patternπn∈\{0,1\}In\\pi\_\{n\}\\in\\\{0,1\\\}^\{I\_\{n\}\}, and an override labelσn∈\{0,1\}\\sigma\_\{n\}\\in\\\{0,1\\\}\. LetTndecT^\{\\mathrm\{dec\}\}\_\{n\}be the deceiver Transformer obtained fromTn⋆T\_\{n\}^\{\\star\}by[Theorem˜C\.2](https://arxiv.org/html/2605.22964#A3.Thmtheorem2)\.

Assume that the added trigger data\(In,πn,σn\)\(I\_\{n\},\\pi\_\{n\},\\sigma\_\{n\}\)have DLOGTIME\-uniform bit access\. Then the language recognized by\{Tndec\}n≥1\\\{T^\{\\mathrm\{dec\}\}\_\{n\}\\\}\_\{n\\geq 1\}belongs to DLOGTIME\-uniformTC0\\mathrm\{TC\}^\{0\}\.

If the base Transformer family and the added trigger data are only logspace\-uniform, then the resulting language belongs to logspace\-uniformTC0\\mathrm\{TC\}^\{0\}\. If they are treated as arbitrary advice, then the resulting family is contained in non\-uniformTC0\\mathrm\{TC\}^\{0\}\.

###### Proof\.

By[Theorem˜C\.2](https://arxiv.org/html/2605.22964#A3.Thmtheorem2), eachTndecT^\{\\mathrm\{dec\}\}\_\{n\}is again a projected\-pre\-norm AHAT Transformer classifier\. Its depth is the same as that ofTn⋆T\_\{n\}^\{\\star\}, it has one additional head in the final layer, six additional residual coordinates, and the same precisionp​\(n\)=O​\(log⁡n\)p\(n\)=O\(\\log n\)\. These changes preserve the polynomial bounds on the number of heads, dimensions, and feedforward widths\. Under the stated uniformity assumptions, the augmented embeddings and all added parameters remain DLOGTIME\-uniform\. Therefore[Proposition˜C\.1](https://arxiv.org/html/2605.22964#A3.Thmproposition1)applies\. The logspace\-uniform and non\-uniform variants follow by the same argument with the corresponding parameter\-access convention\. ∎

#### C\.4\.1Transformer block\-override construction

Thecert\\operatorname\{cert\}\-based arguments in this paper are fixed\-length statements on a domainΣn\\Sigma^\{n\}\. For each fixednn, starting from one Transformer that computesf⋆f^\{\\star\}on length\-nninputs, we build another Transformer of the same depth and same attention type that agrees with it off one trigger block and overrides the output on that block\. The construction is used for the ordinary output\-only quantitycert⁡\(f⋆,ℋ\)\\operatorname\{cert\}\(f^\{\\star\},\\mathcal\{H\}\)\.

We work with a*projected\-pre\-normpp\-precision AHAT Transformer classifier*\. This combines the projected\-pre\-norm architecture ofMerrill and Sabharwal \[[23](https://arxiv.org/html/2605.22964#bib.bib23)\]with averaging\-hard attention throughout\. Concretely:

1. \(i\)Embedding:e:Σ×\[n\]→Dpme:\\Sigma\\times\[n\]\\to D\_\{p\}^\{m\}, computable inO​\(log⁡n\)O\(\\log n\)time\. All inherited parameters, embeddings, and intermediate values of the original Transformer continue to be evaluated at the same precisionppin the deceiver construction\.
2. \(ii\)A fixed collection of attention heads in each layer\. For the target TransformerTT, there arehhoriginal heads per layer\. In the deceiver construction, we keep thosehhheads and add one extra headGGin the final layer only\.
3. \(iii\)Each head reads a*single*projected\-pre\-norm view h¯i=layer​\_​norm​\(Mproj​hi\)\\bar\{h\}\_\{i\}=\\mathrm\{layer\\\_norm\}\(M\_\{\\mathrm\{proj\}\}h\_\{i\}\)of the current residual statehih\_\{i\}and computes queries, keys, and values as affine functions of that same normalized vector\. FollowingMerrill and Sabharwal \[[23](https://arxiv.org/html/2605.22964#bib.bib23)\]\(Definition 3 therein\), layer norm is defined as layer​\_​norm​\(x\):=x−x¯‖x−x¯‖2,\\mathrm\{layer\\\_norm\}\(x\):=\\frac\{x\-\\bar\{x\}\}\{\\\|x\-\\bar\{x\}\\\|\_\{2\}\},wherex¯\\bar\{x\}denotes the mean of the coordinates ofxx\. Under this convention, any mean\-zero unit\-norm vector is a fixed point of layer norm\. Other normalization conventions are also compatible with the proof, provided the code vectors are chosen to be fixed points of the chosen normalization\. We adopt theMerrill and Sabharwal \[[23](https://arxiv.org/html/2605.22964#bib.bib23)\]convention throughout\.
4. \(iv\)Attention is*AHAT*: for each query position, the head output is the uniform average of the values at the positions attaining the maximum score\.
5. \(v\)Each layer has an activation block that takes the head outputs and the residual state and returns the next hidden state via a two\-layer feedforward network of the form FF​\(x\)=W2​ReLU​\(W1​x\+b1\)\+b2,\\mathrm\{FF\}\(x\)=W\_\{2\}\\,\\mathrm\{ReLU\}\(W\_\{1\}x\+b\_\{1\}\)\+b\_\{2\},followed by a residual connection\. In the final layer, the output projection of the added attention head writes its scalar output directly into two dedicated auxiliary coordinatesz\(1\)z^\{\(1\)\}andz\(2\)z^\{\(2\)\}\. The feedforward block is then extended block diagonally and leaves these auxiliary coordinates unchanged\. No one\-dimensional layer normalization ortt\-dependent thresholding is used on the auxiliary coordinates\.
6. \(vi\)Final linear classifier γ​\(u\)=𝟏​\[⟨a,u⟩\+b≥0\]\\gamma\(u\)=\\mathbf\{1\}\[\\langle a,u\\rangle\+b\\geq 0\]at the final token\.

Projected pre\-norm lets the original heads and the original part of the feedforward block project only to the firstmmcoordinates, so the auxiliary coordinates never enter their layer norm\. The new trigger headGGinstead projects to a dedicated44\-dimensional code block and uses only that one normalized code block\.

The exact\-attention model used below is close to the models appearing in these Transformer\-to\-circuit containment results\. Saturated/AHAT float transformers are contained in non\-uniformTC0\\mathrm\{TC\}^\{0\}, while more general log\-precision transformers admit stronger uniform upper bounds such as logspace\-uniformTC0\\mathrm\{TC\}^\{0\}and the logical characterization byFO​\(M\)\\mathrm\{FO\}\(M\)\. The proof below implements the trigger construction directly inside the projected\-pre\-norm AHAT model\.

###### Theorem C\.2\(Transformer block\-override construction\)\.

Fix an input lengthnnand letTTbe a depth\-ddbinary classifier in the projected\-pre\-normpp\-precision AHAT model onΣn=\{0,1\}n\\Sigma^\{n\}=\\\{0,1\\\}^\{n\}, withp≥p0p\\geq p\_\{0\}, model dimensionmm,hhoriginal heads per layer, and final linear classifier

γ​\(u\)=𝟏​\[⟨a,u⟩\+b0≥0\]\.\\gamma\(u\)=\\mathbf\{1\}\[\\langle a,u\\rangle\+b\_\{0\}\\geq 0\]\.Fix a nonempty setI⊆\[n\]I\\subseteq\[n\]of sizet:=\|I\|t:=\|I\|\. Fix a patternπ=\(πi\)i∈I∈ΣI\\pi=\(\\pi\_\{i\}\)\_\{i\\in I\}\\in\\Sigma^\{I\}and define

BI,π:=\{x∈Σn:xi=πi​for all​i∈I\}\.B\_\{I,\\pi\}:=\\\{x\\in\\Sigma^\{n\}:x\_\{i\}=\\pi\_\{i\}\\text\{ for all \}i\\in I\\\}\.Then for everyσ∈\{0,1\}\\sigma\\in\\\{0,1\\\}there exists a depth\-ddprojected\-pre\-norm AHAT Transformer classifier

with the samehhoriginal heads in every layer, one additional headGGin the final layer, embedding/residual dimensionm\+6m\+6, and the same precisionpp, such that for everyx∈Σnx\\in\\Sigma^\{n\},

fTI,π,σ​\(x\)=\{σ,x∈BI,π,fT​\(x\),x∉BI,π\.f\_\{T\_\{I,\\pi,\\sigma\}\}\(x\)=\\begin\{cases\}\\sigma,&x\\in B\_\{I,\\pi\},\\\\\[2\.84526pt\] f\_\{T\}\(x\),&x\\notin B\_\{I,\\pi\}\.\\end\{cases\}Moreover, layers1,…,d−11,\\dots,d\-1and the originalhhheads of layerddpreserve the computation ofTTexactly on the firstmmcoordinates under the samepp\-precision arithmetic graph\.

###### Proof\.

We constructTI,π,σT\_\{I,\\pi,\\sigma\}in four steps\.

##### Step 1: an exact44\-dimensional code\.

Define the three vectors

α:=\(12,12,−12,−12\),β:=\(12,−12,12,−12\),γ:=\(12,−12,−12,12\)\.\\alpha:=\\Bigl\(\\frac\{1\}\{2\},\\frac\{1\}\{2\},\-\\frac\{1\}\{2\},\-\\frac\{1\}\{2\}\\Bigr\),\\qquad\\beta:=\\Bigl\(\\frac\{1\}\{2\},\-\\frac\{1\}\{2\},\\frac\{1\}\{2\},\-\\frac\{1\}\{2\}\\Bigr\),\\qquad\\gamma:=\\Bigl\(\\frac\{1\}\{2\},\-\\frac\{1\}\{2\},\-\\frac\{1\}\{2\},\\frac\{1\}\{2\}\\Bigr\)\.These vectors have the following properties:

1. \(i\)Each coordinate is dyadic, hence exactly representable inDpD\_\{p\}becausep≥p0p\\geq p\_\{0\}\.
2. \(ii\)Each vector has mean0and Euclidean norm11\.
3. \(iii\)Therefore, if a projected\-pre\-norm projection selects exactly one of these vectors, layer norm acts as the identity on that block: each vector is mean\-zero and unit\-norm, and is therefore a fixed point of the conventionlayer​\_​norm​\(x\)=x−x¯‖x−x¯‖2\\mathrm\{layer\\\_norm\}\(x\)=\\tfrac\{x\-\\bar\{x\}\}\{\\\|x\-\\bar\{x\}\\\|\_\{2\}\}adopted fromMerrill and Sabharwal \[[23](https://arxiv.org/html/2605.22964#bib.bib23)\]\.
4. \(iv\)With the constant query vector q†:=\(2,−1,1,0\),q^\{\\dagger\}:=\(2,\-1,1,0\),we have q†⋅α=0,q†⋅β=2,q†⋅γ=1\.q^\{\\dagger\}\\cdot\\alpha=0,\\qquad q^\{\\dagger\}\\cdot\\beta=2,\\qquad q^\{\\dagger\}\\cdot\\gamma=1\.
5. \(v\)The affine scalar map v​\(c\):=−c2−c3v\(c\):=\-c\_\{2\}\-c\_\{3\}satisfies v​\(α\)=0,v​\(β\)=0,v​\(γ\)=1\.v\(\\alpha\)=0,\\qquad v\(\\beta\)=0,\\qquad v\(\\gamma\)=1\.

Thus a single normalized44\-dimensional code can simultaneously reveal:

- •whether a position is outside the trigger set \(α\\alpha\), a mismatching trigger \(β\\beta\), or a matching trigger \(γ\\gamma\) \(via the score againstq†q^\{\\dagger\}\), and
- •in particular, whether that position matches the patternπ\\pi\(via the scalar value mapvv, wherev​\(γ\)=1v\(\\gamma\)=1andv​\(α\)=v​\(β\)=0v\(\\alpha\)=v\(\\beta\)=0\)\.

##### Step 2: augmented hidden state and embedding\.

We enlarge the residual stream from dimensionmmto dimensionm\+6m\+6\. The hidden state at each position is written as

hi=\(ui,Ci,zi\(1\),zi\(2\)\)∈Dpm×Dp4×Dp×Dp,h\_\{i\}=\(u\_\{i\},\\;C\_\{i\},\\;z\_\{i\}^\{\(1\)\},\\;z\_\{i\}^\{\(2\)\}\)\\in D\_\{p\}^\{m\}\\times D\_\{p\}^\{4\}\\times D\_\{p\}\\times D\_\{p\},where:

- •uiu\_\{i\}is the originalmm\-dimensional hidden state,
- •CiC\_\{i\}is the44\-dimensional trigger code, and
- •zi\(1\)z\_\{i\}^\{\(1\)\}andzi\(2\)z\_\{i\}^\{\(2\)\}are auxiliary scalars, initialized to0, that will store two copies of the trigger bit in the final layer\.

For each positioni∈\[n\]i\\in\[n\]and tokena∈Σa\\in\\Sigma, define the code

Ci​\(a\):=\{α,i∉I,β,i∈I​and​a≠πi,γ,i∈I​and​a=πi\.C\_\{i\}\(a\):=\\begin\{cases\}\\alpha,&i\\notin I,\\\\\[2\.84526pt\] \\beta,&i\\in I\\text\{ and \}a\\neq\\pi\_\{i\},\\\\\[2\.84526pt\] \\gamma,&i\\in I\\text\{ and \}a=\\pi\_\{i\}\.\\end\{cases\}Then define the new embedding

e′​\(a,i\):=\(e​\(a,i\),Ci​\(a\),0,0\)\.e^\{\\prime\}\(a,i\):=\(e\(a,i\),\\,C\_\{i\}\(a\),\\,0,\\,0\)\.
For the fixed\-length certificate construction, this augmented embedding is part of the finite Transformer description\. Equivalently, its tablee′:Σ×\[n\]→Dpm\+6e^\{\\prime\}:\\Sigma\\times\[n\]\\to D\_\{p\}^\{m\+6\}may be supplied as finite advice\. For the asymptotic DLOGTIME\-uniformTC0\\mathrm\{TC\}^\{0\}statement in[Corollary˜C\.1](https://arxiv.org/html/2605.22964#A3.Thmcorollary1), we additionally require uniform bit access to the familiesInI\_\{n\}andπn\\pi\_\{n\}\.

##### Step 3: layers1,…,d−11,\\ldots,d\-1preserve the original computation exactly\.

For every original headkkin every layerℓ<d\\ell<d, set the projected\-pre\-norm matrix to the block\-diagonal padding of the original projection:

Mproj\(ℓ,k\)=\[Mproj,orig\(ℓ,k\)\|0r×6\],M\_\{\\mathrm\{proj\}\}^\{\(\\ell,k\)\}=\\bigl\[M\_\{\\mathrm\{proj,orig\}\}^\{\(\\ell,k\)\}\\;\\big\|\\;0\_\{r\\times 6\}\\bigr\],whererris the row\-count ofMproj,orig\(ℓ,k\)M\_\{\\mathrm\{proj,orig\}\}^\{\(\\ell,k\)\}\. The original query, key, value, output, and feedforward maps are inherited unchanged fromTTand zero\-padded block\-diagonally so that they read only the firstmmcoordinates and write only to the firstmmcoordinates\. Hence the extra six coordinates receive zero from the transformed update and are copied unchanged by the residual connection\.

The additional headGGis present only in the final layer\. Equivalently, it has zero parameters in layers1,…,d−11,\\dots,d\-1\.

It follows by induction that for everyℓ≤d−1\\ell\\leq d\-1, every positionii, and every inputx∈Σnx\\in\\Sigma^\{n\},

hiℓ​\(x\)=\(h~iℓ​\(x\),Ci​\(xi\),0,0\),h\_\{i\}^\{\\ell\}\(x\)=\\bigl\(\\widetilde\{h\}\_\{i\}^\{\\ell\}\(x\),\\,C\_\{i\}\(x\_\{i\}\),\\,0,\\,0\\bigr\),\(1\)whereh~iℓ​\(x\)\\widetilde\{h\}\_\{i\}^\{\\ell\}\(x\)is exactly the hidden state that the original TransformerTTwould compute at positioniiafter layerℓ\\ell\.

To verify the inductive step at layerℓ<d\\ell<d: in the attention sublayer, each original head computes its output entirely in the first\-mm\-coordinate subspace, becauseMproj\(ℓ,k\)M\_\{\\mathrm\{proj\}\}^\{\(\\ell,k\)\}selects only those coordinates and the associatedQQ,KK,VVaffine maps read and write only there\. The output weight matrixWo\(ℓ\)W\_\{o\}^\{\(\\ell\)\}is block\-diagonal with zeros in the rows corresponding to coordinatesm\+1m\{\+\}1throughm\+6m\{\+\}6, so the transformed update contributes nothing to the last six coordinates\. Those coordinates are carried through unchanged by the residual connection\. For the feedforward sublayer, the projected\-pre\-norm matrix is set to\[Mff,orig\(ℓ\)∣0rff×6\]\[M\_\{\\mathrm\{ff,orig\}\}^\{\(\\ell\)\}\\mid 0\_\{r\_\{\\mathrm\{ff\}\}\\times 6\}\], whereMff,orig\(ℓ\)M\_\{\\mathrm\{ff,orig\}\}^\{\(\\ell\)\}is the original feedforward projection for layerℓ\\ellinherited fromTT, so the weight matricesW1W\_\{1\}andW2W\_\{2\}act only on the firstmmcoordinates, and their output is zero\-padded back tom\+6m\{\+\}6\. The last six coordinates again pass through the residual untouched\. Hence the inductive invariant \([1](https://arxiv.org/html/2605.22964#A3.E1)\) is maintained across every layerℓ≤d−1\\ell\\leq d\-1\.

The same block\-diagonal extension is used for the originalhhheads in the final layer: they continue to compute exactly the same updates on the firstmmcoordinates as inTTand ignore the last six coordinates\.

##### Step 4: trigger head, trigger bits, and final classifier\.

*Trigger headGG\.*In layerdd, add one new AHAT headGG\. Its projected\-pre\-norm matrix selects the44\-dimensional code block:

MprojG=\[04×m​\|I4\|​04×2\]\.M\_\{\\mathrm\{proj\}\}^\{G\}=\\bigl\[0\_\{4\\times m\}\\;\\big\|\\;I\_\{4\}\\;\\big\|\\;0\_\{4\\times 2\}\\bigr\]\.By construction, for every positionjj,

layer​\_​norm​\(MprojG​hjd−1\)=Cj​\(xj\),\\mathrm\{layer\\\_norm\}\(M\_\{\\mathrm\{proj\}\}^\{G\}h\_\{j\}^\{d\-1\}\)=C\_\{j\}\(x\_\{j\}\),becauseCj​\(xj\)∈\{α,β,γ\}C\_\{j\}\(x\_\{j\}\)\\in\\\{\\alpha,\\beta,\\gamma\\\}is already mean\-zero and unit norm\.

Now define the query, key, and value maps of headGGon this same normalized44\-vector as follows:

qG​\(c\):=q†,kG​\(c\):=c,vG​\(c\):=−c2−c3\.q\_\{G\}\(c\):=q^\{\\dagger\},\\qquad k\_\{G\}\(c\):=c,\\qquad v\_\{G\}\(c\):=\-c\_\{2\}\-c\_\{3\}\.
Note thatqGq\_\{G\}is a valid affine map with weight matrixWq=0W\_\{q\}=0and biasbq=q†b\_\{q\}=q^\{\\dagger\}, so the query is the same constantq†q^\{\\dagger\}at every positionii\.

As a result, the attention scoressG​\(hi,hj\)s\_\{G\}\(h\_\{i\},h\_\{j\}\)do not depend on the query positionii\. Hence, the set of maximizers \(which may depend onxx\) and the resulting head outputzi′z^\{\\prime\}\_\{i\}are the same for alli∈\[n\]i\\in\[n\]\. Thus the attention score assigned to positionjjis

sG​\(hi,hj\)=q†⋅Cj​\(xj\)\.s\_\{G\}\(h\_\{i\},h\_\{j\}\)=q^\{\\dagger\}\\cdot C\_\{j\}\(x\_\{j\}\)\.From the identities above,

sG​\(hi,hj\)=\{0,j∉I,2,j∈I​and​xj≠πj,1,j∈I​and​xj=πj\.s\_\{G\}\(h\_\{i\},h\_\{j\}\)=\\begin\{cases\}0,&j\\notin I,\\\\ 2,&j\\in I\\text\{ and \}x\_\{j\}\\neq\\pi\_\{j\},\\\\ 1,&j\\in I\\text\{ and \}x\_\{j\}=\\pi\_\{j\}\.\\end\{cases\}The standard1/dhead1/\\sqrt\{d\_\{\\mathrm\{head\}\}\}scaling applied to attention scores is a fixed positive constant and does not change which positions attain the maximum\. For the trigger head,dhead=4d\_\{\\rm head\}=4, so this scale is1/21/2\.

LetJ​\(x\):=\{j∈I:xj≠πj\}J\(x\):=\\\{j\\in I:x\_\{j\}\\neq\\pi\_\{j\}\\\}be the set of mismatching trigger positions\. Ifx∉BI,πx\\notin B\_\{I,\\pi\}thenJ​\(x\)≠∅J\(x\)\\neq\\varnothingand the unique maximal score is22, attained exactly onJ​\(x\)J\(x\), so AHAT averages the corresponding valuesvG​\(β\)=0v\_\{G\}\(\\beta\)=0and outputszi′=0z^\{\\prime\}\_\{i\}=0\. Ifx∈BI,πx\\in B\_\{I,\\pi\}thenJ​\(x\)=∅J\(x\)=\\varnothingand the maximal score is11, attained exactly onII\(all positions are coded asγ\\gamma\), so AHAT averages the corresponding valuesvG​\(γ\)=1v\_\{G\}\(\\gamma\)=1and outputszi′=1z^\{\\prime\}\_\{i\}=1\. Therefore

zi′=𝟏​\[x∈BI,π\]∈\{0,1\}for all​i∈\[n\]\.z^\{\\prime\}\_\{i\}=\\mathbf\{1\}\[x\\in B\_\{I,\\pi\}\]\\in\\\{0,1\\\}\\qquad\\text\{for all \}i\\in\[n\]\.
*Final activation block\.*The firstmmcoordinates of the final activation block reproduce exactly the final activation block ofTT\.

More precisely, the output weight matrixWoW\_\{o\}of the final layer is block\-diagonal: the columns corresponding to the originalhhheads contribute only to the firstmmcoordinates of the residual update, while the column block corresponding to the new headGGplaces the AHAT head outputzi′z^\{\\prime\}\_\{i\}into both auxiliary coordinatesz\(1\)z^\{\(1\)\}andz\(2\)z^\{\(2\)\}, with zeros in all other rows\. This ensures that no cross\-talk occurs between the original computation and the trigger gadget\.

We initializezi\(1\)=zi\(2\)=0z\_\{i\}^\{\(1\)\}=z\_\{i\}^\{\(2\)\}=0in the embedding and preserve these auxiliary coordinates through layers1,…,d−11,\\dots,d\-1and through the original heads of layerdd\. Therefore, after the final\-layer attention residual update, we havezi\(1\)=zi\(2\)=zi′z\_\{i\}^\{\(1\)\}=z\_\{i\}^\{\(2\)\}=z^\{\\prime\}\_\{i\}for every positionii\. By the calculation above,zi′=𝟏​\[x∈BI,π\]∈\{0,1\}z^\{\\prime\}\_\{i\}=\\mathbf\{1\}\[x\\in B\_\{I,\\pi\}\]\\in\\\{0,1\\\}\. Since the trigger bit is already a boolean scalar, we do not need anytt\-dependent thresholding inside the feedforward block; we may leave the auxiliary extension of the final\-layer feedforward identically zero so thatz\(1\)z^\{\(1\)\}andz\(2\)z^\{\(2\)\}are carried through unchanged\.

*Final classifier\.*LetλT\(p\)​\(x\)∈Dp\\lambda\_\{T\}^\{\(p\)\}\(x\)\\in D\_\{p\}denote the scalar logit obtained by evaluating the original final readout ofTTonh~nd​\(x\)\\widetilde\{h\}\_\{n\}^\{d\}\(x\), using exactly the samepp\-precision arithmetic graph and accumulation order as inTT\. Thus

fT​\(x\)=𝟏​\[λT\(p\)​\(x\)≥0\]\.f\_\{T\}\(x\)=\\mathbf\{1\}\[\\lambda\_\{T\}^\{\(p\)\}\(x\)\\geq 0\]\.By definition ofFpmaxF\_\{p\}^\{\\max\}\([Section˜C\.2](https://arxiv.org/html/2605.22964#A3.SS2)\),

\|λT\(p\)​\(x\)\|≤Fpmaxfor all​x∈Σn\.\|\\lambda\_\{T\}^\{\(p\)\}\(x\)\|\\leq F\_\{p\}^\{\\max\}\\qquad\\text\{for all \}x\\in\\Sigma^\{n\}\.Set

F:=Fpmax\.F:=F\_\{p\}^\{\\max\}\.The new final readout first computes the inherited logitλT\(p\)​\(x\)\\lambda\_\{T\}^\{\(p\)\}\(x\)exactly as above and then adds the two override terms in the displayed order:

Lσ​\(x\):=τp​\(τp​\(λT\(p\)​\(x\)\+\(2​σ−1\)​F​zn\(1\)\)\+\(2​σ−1\)​F​zn\(2\)\)\.L\_\{\\sigma\}\(x\):=\\tau\_\{p\}\\\!\\left\(\\tau\_\{p\}\\\!\\left\(\\lambda\_\{T\}^\{\(p\)\}\(x\)\+\(2\\sigma\-1\)Fz\_\{n\}^\{\(1\)\}\\right\)\+\(2\\sigma\-1\)Fz\_\{n\}^\{\(2\)\}\\right\)\.The classifier outputs

γσ​\(hnd​\(x\)\):=𝟏​\[Lσ​\(x\)≥0\]\.\\gamma\_\{\\sigma\}\(h\_\{n\}^\{d\}\(x\)\):=\\mathbf\{1\}\[L\_\{\\sigma\}\(x\)\\geq 0\]\.The two additions inLσL\_\{\\sigma\}are evaluated in the displayed order\. The specified order is part of the readout arithmetic graph, as allowed by the finite\-precision semantics in[Section˜C\.2](https://arxiv.org/html/2605.22964#A3.SS2)\.

Ifx∉BI,πx\\notin B\_\{I,\\pi\}, thenzn\(1\)=zn\(2\)=0z\_\{n\}^\{\(1\)\}=z\_\{n\}^\{\(2\)\}=0, so

Lσ​\(x\)=λT\(p\)​\(x\),L\_\{\\sigma\}\(x\)=\\lambda\_\{T\}^\{\(p\)\}\(x\),and therefore

γσ​\(hnd​\(x\)\)=𝟏​\[λT\(p\)​\(x\)≥0\]=fT​\(x\)\.\\gamma\_\{\\sigma\}\(h\_\{n\}^\{d\}\(x\)\)=\\mathbf\{1\}\[\\lambda\_\{T\}^\{\(p\)\}\(x\)\\geq 0\]=f\_\{T\}\(x\)\.Ifx∈BI,πx\\in B\_\{I,\\pi\}, thenzn\(1\)=zn\(2\)=1z\_\{n\}^\{\(1\)\}=z\_\{n\}^\{\(2\)\}=1\. Forσ=1\\sigma=1, sinceλT\(p\)​\(x\)≥−F\\lambda\_\{T\}^\{\(p\)\}\(x\)\\geq\-F, the first inner sum

τp​\(λT\(p\)​\(x\)\+F\)\\tau\_\{p\}\(\\lambda\_\{T\}^\{\(p\)\}\(x\)\+F\)is a nonnegative element ofDpD\_\{p\}, and adding the secondFFyields a nonnegative, indeed positive, possibly saturated at\+F\+F, final value\. ThusL1​\(x\)≥0L\_\{1\}\(x\)\\geq 0, so the output is11\.

Forσ=0\\sigma=0, sinceλT\(p\)​\(x\)≤F\\lambda\_\{T\}^\{\(p\)\}\(x\)\\leq F, the first inner sum

τp​\(λT\(p\)​\(x\)−F\)\\tau\_\{p\}\(\\lambda\_\{T\}^\{\(p\)\}\(x\)\-F\)is a nonpositive element ofDpD\_\{p\}, and adding the second−F\-Fyields a strictly negative value, possibly saturated at−F\-F\. ThusL0​\(x\)<0L\_\{0\}\(x\)<0, so the output is0\.

Thus the new Transformer agrees withTToffBI,πB\_\{I,\\pi\}and outputs the constantσ\\sigmaonBI,πB\_\{I,\\pi\}\. The depth remainsdd, the original computation on the firstmmcoordinates is preserved exactly at the same precisionpp, and the only changes are one constant\-width trigger head in the final layer together with six added embedding/residual coordinates\. ∎

In[Theorem˜C\.2](https://arxiv.org/html/2605.22964#A3.Thmtheorem2), the trigger advice is placed in the six added embedding/residual coordinates, where the codeCj​\(xj\)C\_\{j\}\(x\_\{j\}\)already specifies whetherj∉Ij\\notin I, whetherj∈Ij\\in Iandxj≠πjx\_\{j\}\\neq\\pi\_\{j\}, or whetherj∈Ij\\in Iandxj=πjx\_\{j\}=\\pi\_\{j\}\. This placement is not essential to the existence of block deceivers\.

If the architecture instead has rich positional encodings, meaning that attention parameters can form exact positional selectors for the sets\{j∈I:πj=0\}\\\{j\\in I:\\pi\_\{j\}=0\\\}and\{j∈I:πj=1\}\\\{j\\in I:\\pi\_\{j\}=1\\\}, then the trigger bit can be computed from the pair consisting of position and input bit\. For example, two mismatch\-detection heads can test whether any selected coordinate disagrees with its prescribed value, and a fixed\-width affine/ReLU combiner such asz=ReLU⁡\(1−m0−m1\)z=\\operatorname\{ReLU\}\(1\-m\_\{0\}\-m\_\{1\}\)computes1​\[xI=π\]1\[x\_\{I\}=\\pi\]from the two Boolean mismatch bitsm0,m1m\_\{0\},m\_\{1\}\. This gives the same block\-override mechanism with a different constant head/width overhead, provided that the positional representation has already been supplied\. If such positional features need to be added for this construction, their cost must also be counted\. For example, one\-hot positional features make arbitrary subsets linearly selectable, but require extrannpositional encoding coordinates\.

For other compressed positional encodings, an exact selector for arbitrary\(I,π\)\(I,\\pi\)should not be treated as free, since the description of the trigger data containslog⁡\(nt\)\+t\\log\{\\binom\{n\}\{t\}\}\+tbits in general, orttbits whenIIis fixed\. Thus, the attention\-based formulation moves the trigger advice from the added embedding coordinates into the positional selectors or attention parameters, rather than removing it\. We use the embedding\-coded version because it keeps the one\-head, six\-coordinate construction explicit and makes the advice accounting transparent\.

###### Corollary C\.2\(Transformer certificate size\)\.

Assume nowΣ=\{0,1\}\\Sigma=\\\{0,1\\\}\. Fix an input lengthnnand letT⋆T^\{\\star\}be a depth\-ddprojected\-pre\-normpp\-precision AHAT Transformer classifier on\{0,1\}n\\\{0,1\\\}^\{n\}, computingf⋆f^\{\\star\}, withp≥p0p\\geq p\_\{0\}\. Fix a trigger codimension1≤t≤n1\\leq t\\leq n\. Let

ℋT⋆,tTr​\(n\):=𝒯d,p\+1​h​e​a​d,\+6​c​o​o​r​d​\(n\)\\mathcal\{H\}^\{\\mathrm\{Tr\}\}\_\{T^\{\\star\},t\}\(n\):=\\mathcal\{T\}\_\{d,\\,p\}^\{\+1\\mathrm\{head\},\+6\\mathrm\{coord\}\}\(n\)denote the enlarged class of depth\-ddprojected\-pre\-norm AHAT Transformer classifiers on length\-nninputs obtained fromT⋆T^\{\\star\}by allowing:

1. \(a\)the inactive augmentation that still computesf⋆f^\{\\star\};
2. \(b\)the single extra trigger head and the66\-dimensional residual augmentation described above; and
3. \(c\)the original embedding on the firstmmcoordinates is kept fixed, while the six added embedding coordinates may be chosen as in[Theorem˜C\.2](https://arxiv.org/html/2605.22964#A3.Thmtheorem2)to encode the fixed trigger parameters\(I,π\)\(I,\\pi\)\.

Then

cert⁡\(f⋆,ℋT⋆,tTr​\(n\)\)≥2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathcal\{H\}^\{\\mathrm\{Tr\}\}\_\{T^\{\\star\},t\}\(n\)\\bigr\)\\geq 2^\{t\}\.Consequently, along any sequence of input lengths, if the chosen trigger codimensions satisfyc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some fixedc\>0c\>0, then the lower bound is2Ω​\(n\)2^\{\\Omega\(n\)\}\.

###### Proof\.

Fix anyI⊆\[n\]I\\subseteq\[n\]with\|I\|=t\|I\|=t\. For each trigger patternπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, chooseσπ\\sigma\_\{\\pi\}as in[Remark˜B\.1](https://arxiv.org/html/2605.22964#A2.Thmremark1)\. Applying[Theorem˜C\.2](https://arxiv.org/html/2605.22964#A3.Thmtheorem2)gives a TransformerGπ:=TI,π,σπG\_\{\\pi\}:=T\_\{I,\\pi,\\sigma\_\{\\pi\}\}in

ℋT⋆,tTr​\(n\)\\mathcal\{H\}^\{\\mathrm\{Tr\}\}\_\{T^\{\\star\},t\}\(n\)such that:

- •GπG\_\{\\pi\}agrees withf⋆f^\{\\star\}on every input outsideBI,πB\_\{I,\\pi\}, and
- •GπG\_\{\\pi\}differs fromf⋆f^\{\\star\}on at least one input insideBI,πB\_\{I,\\pi\}\.

For eachπ∈\{0,1\}I\\pi\\in\\\{0,1\\\}^\{I\}, define

Eπ:=\{x∈BI,π:Gπ​\(x\)≠f⋆​\(x\)\}\.E\_\{\\pi\}:=\\\{x\\in B\_\{I,\\pi\}:G\_\{\\pi\}\(x\)\\neq f^\{\\star\}\(x\)\\\}\.The choice ofσπ\\sigma\_\{\\pi\}makesEπE\_\{\\pi\}nonempty\. Since the blocks\{BI,π:π∈\{0,1\}I\}\\\{B\_\{I,\\pi\}:\\pi\\in\\\{0,1\\\}^\{I\}\\\}are pairwise disjoint, the sets\{Eπ:π∈\{0,1\}I\}\\\{E\_\{\\pi\}:\\pi\\in\\\{0,1\\\}^\{I\}\\\}are pairwise disjoint\. Therefore[Proposition˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmproposition1)gives

cert⁡\(f⋆,ℋT⋆,tTr​\(n\)\)≥\|\{0,1\}I\|=2t\.\\operatorname\{cert\}\\bigl\(f^\{\\star\},\\mathcal\{H\}^\{\\mathrm\{Tr\}\}\_\{T^\{\\star\},t\}\(n\)\\bigr\)\\geq\|\\\{0,1\\\}^\{I\}\|=2^\{t\}\.The asymptotic consequence follows wheneverc​n≤t​\(n\)≤ncn\\leq t\(n\)\\leq nfor some fixedc\>0c\>0\. ∎

## Appendix DExperiment details

This appendix records the details needed to reproduce and interpret the experiments in[Section˜5](https://arxiv.org/html/2605.22964#S5)\. The circuit experiment is a deterministic instantiation of the trigger construction\. The Transformer experiment uses training only to generate strong candidate recognizers, which are then audited by finite held\-out tests\.

### D\.1Constructed threshold\-circuit experiment

The circuit experiment uses the full domain𝒳=\{0,1\}3​n\+1,\\mathcal\{X\}=\\\{0,1\\\}^\{3n\+1\},where an input is a triple\(a,b,z\)\(a,b,z\)witha,b∈\{0,1\}na,b\\in\\\{0,1\\\}^\{n\}andz∈\{0,1\}n\+1z\\in\\\{0,1\\\}^\{n\+1\}\. The target accepts exactly whenz=a\+bz=a\+b\. For a trigger patternπ∈\{0,1\}n\\pi\\in\\\{0,1\\\}^\{n\}, the deceivergπg\_\{\\pi\}accepts every input witha=πa=\\piand agrees with the target outside this block\. The block

Bπ=\{\(a,b,z\):a=π\}B\_\{\\pi\}=\\\{\(a,b,z\):a=\\pi\\\}has size22​n\+12^\{2n\+1\}\. Inside this block, the target accepts exactly one value ofzzfor each fixedbb, whilegπg\_\{\\pi\}accepts all2n\+12^\{n\+1\}candidates\. Hence each constructed deceiver has

en=\|Eπ\|=2n​\(2n\+1−1\)e\_\{n\}=\|E\_\{\\pi\}\|=2^\{n\}\(2^\{n\+1\}\-1\)errors, all of them false positives\. The error sets are disjoint across differentπ\\pi\. For a uniformly sampled certificate candidateSm⊆𝒳S\_\{m\}\\subseteq\\mathcal\{X\}, sampled without replacement, the pass probability of one constructed deceiver is therefore

pn​\(m\)=\(\|𝒳\|−enm\)/\(\|𝒳\|m\)\.p\_\{n\}\(m\)=\\binom\{\|\\mathcal\{X\}\|\-e\_\{n\}\}\{m\}\\Big/\\binom\{\|\\mathcal\{X\}\|\}\{m\}\.Since there are2n2^\{n\}trigger patterns, the expected number of surviving constructed deceivers is

This is the quantity plotted in the left panel of[Figure˜2](https://arxiv.org/html/2605.22964#S5.F2)\. The calculation is exact for this finite construction\. It uses uniform sampling of certificate points, but it does not assume that errors are uniform\.

[Figure˜3](https://arxiv.org/html/2605.22964#A4.F3)makes the sharpness of the constructed deceiver family especially clear\. The heatmap reports the best possible remaining count aftermmlabeled examples for the constructed subfamily𝒟=\{gπ:π∈\{0,1\}n\}\\mathcal\{D\}=\\\{g\_\{\\pi\}:\\pi\\in\\\{0,1\\\}^\{n\}\\\}\. Since the disagreement sets of these2n2^\{n\}deceivers are pairwise disjoint, each labeled example can eliminate at most one constructed deceiver\. This bound is tight by choosing one error point from a distinct block whenever possible\. Hence the remaining count ismax⁡\{2n−m,0\}\\max\\\{2^\{n\}\-m,0\\\}\. For eachnn, certificate candidates of size up through20\.75​n2^\{0\.75n\}leave almost all of the2n2^\{n\}constructed deceivers intact, and even at20\.9​n2^\{0\.9n\}the surviving family remains large\. Substantial pruning appears only when the certificate\-candidate size moves very close to2n2^\{n\}, as seen in the20\.95​n2^\{0\.95n\}and20\.99​n2^\{0\.99n\}columns, and the constructed family is fully eliminated only at2n2^\{n\}well\-chosen examples\. In this sense, the deceiver\-survival curve is sharp, with the collapse concentrated near the endpoint\.

![Refer to caption](https://arxiv.org/html/2605.22964v1/x4.png)Figure 3:Remaining constructed threshold\-circuit deceivers under optimally chosen certificate candidates\. Rows range over operand lengthsn∈\{12,16,20,24,32,40\}n\\in\\\{12,16,20,24,32,40\\\}, and columns range from20\.25​n2^\{0\.25n\}to2n2^\{n\}\. Each cell reportsmax⁡\{2n−⌊m⌋,0\}\\max\\\{2^\{n\}\-\\lfloor m\\rfloor,0\\\}, the number of constructed deceivers that can remain aftermmlabels when one label is chosen from a distinct error set whenever possible\. Thus, only2n2^\{n\}well\-chosen examples eliminate the entire constructed family\.
### D\.2Transformer experiment details

The Transformer experiment asks whether trained recognizers can leave small residual error sets after strong validation\. The goal is not to test whether binary addition is hard to learn\. It is to obtain high\-quality hypotheses and then ask how much labeled data is needed to certify exactness within the trained set\.

For consistency with the main text, we call accepted models with nonzero held\-out test error deceivers\. This name does not imply that they behave like the constructed trigger deceivers\.

#### D\.2\.1Task and data

The task is binary\-addition recognition\. For operandsa,b∈\{0,1\}10a,b\\in\\\{0,1\\\}^\{10\}and a candidate outputz∈\{0,1\}11z\\in\\\{0,1\\\}^\{11\}, the label is

y=𝟏​\[z=a\+b\]\.y=\\mathbf\{1\}\[z=a\+b\]\.The split is made over operand pairs\(a,b\)\(a,b\), so the held\-out test set contains unseen operand pairs rather than new perturbations of operands seen during training\. The held\-out test split contains25%25\\%of the operand pairs\. The remaining75%75\\%is used for training and validation checks\. In the runs reported here, this gives734,003734\{,\}003training pairs,52,42952\{,\}429validation pairs, and262,144262\{,\}144held\-out test pairs\. The same split is used for all trained candidates\.

For each operand pair, we generate one positive example and all one\-bit flips of the true output\. Thus each pair gives1212examples: one correct sum and1111hard negatives\. This choice avoids making the negative class dominated by random outputs that are far from the true sum\. The resulting sample counts are734,003⋅12=8,808,036734\{,\}003\\cdot 12=8\{,\}808\{,\}036training examples,52,429⋅12=629,14852\{,\}429\\cdot 12=629\{,\}148validation examples, and262,144⋅12=3,145,728262\{,\}144\\cdot 12=3\{,\}145\{,\}728held\-out test examples\.

#### D\.2\.2Architecture and input format

All addition models use the same encoder\-only Transformer architecture\. The encoder has four pre\-layer\-normalized Transformer layers, hidden sizedmodel=64d\_\{\\mathrm\{model\}\}=64, two attention heads, feed\-forward dimension256256, and no dropout\. Each model has205,196205\{,\}196trainable parameters\.

The input sequence is

\[CLS\],a0,…,a9,\[SEPB\],b0,…,b9,\[SEPZ\],z0,…,z10,\[\\mathrm\{CLS\}\],\\,a\_\{0\},\\ldots,a\_\{9\},\\,\[\\mathrm\{SEP\}\_\{B\}\],\\,b\_\{0\},\\ldots,b\_\{9\},\\,\[\\mathrm\{SEP\}\_\{Z\}\],\\,z\_\{0\},\\ldots,z\_\{10\},with bits presented in most\-significant\-bit order\.

#### D\.2\.3Intermediate supervision

End\-to\-end training from only the final accept/reject label was less reliable\. We therefore use intermediate supervision to make training produce a large set of strong candidates\. The auxiliary supervision is used only during training\.

The model first processes azz\-blind auxiliary stream: the candidate output bits are masked, and scratchpad tokens are appended\. The encoder then predicts the true sum bits together with the column states used to compute them\. Although the input tokens are presented in most\-significant\-bit order, the arithmetic states below are indexed from least to most significant bit\. We use the convention thata\(10\)=b\(10\)=0a^\{\(10\)\}=b^\{\(10\)\}=0andc0=0c\_\{0\}=0\. For output columnk∈\{0,…,10\}k\\in\\\{0,\\ldots,10\\\},

sk=a\(k\)\+b\(k\),uk=sk\+ck,zk⋆=ukmod2,ck\+1=⌊uk/2⌋\.s\_\{k\}=a^\{\(k\)\}\+b^\{\(k\)\},\\qquad u\_\{k\}=s\_\{k\}\+c\_\{k\},\\qquad z^\{\\star\}\_\{k\}=u\_\{k\}\\bmod 2,\\qquad c\_\{k\+1\}=\\lfloor u\_\{k\}/2\\rfloor\.Fork=10k=10, this emits the final carry bit\.

The training loss includes the final accept/reject prediction and the auxiliary predictions for the column states\. At evaluation time, the auxiliary labels are not provided\. The model receives only\(a,b,z\)\(a,b,z\), computes its implied sum internally, compares the predicted sum bits with the candidatezz, and outputs a scalar accept/reject logit\.

#### D\.2\.4Acceptance process

During training, each run is checked every500500steps\. Before training begins, we fix20,00020\{,\}000operand pairs from the training split and20,00020\{,\}000operand pairs from the validation split\. At each check, we evaluate accuracy separately on positives and negatives in both fixed subsets\. Separating the two classes matters because each operand pair contributes one positive and eleven negatives\.

A run is accepted only after all four checks reach at least99\.9%99\.9\\%accuracy: training positives, training negatives, validation positives, and validation negatives\. The held\-out test set is evaluated only after acceptance\.

#### D\.2\.5Held\-out test set

An accepted model is called*test\-exact*if it makes zero mistakes on the full held\-out test set of3,145,7283\{,\}145\{,\}728examples\. This is exactness relative to the held\-out set\. It is not exactness over all possible triples\(a,b,z\)\(a,b,z\), since the full1010\-bit domain contains2312^\{31\}triples and the held\-out set contains only the correct output and one\-bit output flips for held\-out operand pairs\.[Figure˜4](https://arxiv.org/html/2605.22964#A4.F4)shows a visualization of the error distribution\.

![Refer to caption](https://arxiv.org/html/2605.22964v1/x5.png)Figure 4:Distribution of validation and test errors across accepted models\. Each point is an accepted addition recognizer\. The x\-axis shows the number of errors on the fixed validation selection pool of 240k examples, and the y\-axis shows errors on the full held\-out one\-bit test set of 3\.1M examples\. Open markers denote test\-exact models\. Although many accepted models are test\-exact, several models with zero validation errors still make nonzero errors on the held\-out test set\.Among the150150accepted models,9898make no mistakes on the fixed validation check used for acceptance\. Eleven of these validation\-perfect models are nevertheless deceivers on the held\-out test set, with between22and6161test errors\.

#### D\.2\.6Survivor calculation for trained models

Let𝒟\\mathcal\{D\}be the set of6363Transformer deceivers\. For a finite setQQand a trained modelhh, define

EhQ=\{x∈Q:h​\(x\)≠f⋆​\(x\)\}\.E\_\{h\}^\{Q\}=\\\{x\\in Q:h\(x\)\\neq f^\{\\star\}\(x\)\\\}\.If a certificate candidateSmS\_\{m\}is sampled uniformly without replacement fromQQ, thenhhsurvives exactly whenSmS\_\{m\}missesEhQE\_\{h\}^\{Q\}\. Hence

phQ​\(m\)=\(\|Q\|−\|EhQ\|m\)/\(\|Q\|m\),𝔼Q​\(m\)=∑h∈𝒟phQ​\(m\)\.p\_\{h\}^\{Q\}\(m\)=\\binom\{\|Q\|\-\|E\_\{h\}^\{Q\}\|\}\{m\}\\Big/\\binom\{\|Q\|\}\{m\},\\qquad\\mathbb\{E\}\_\{Q\}\(m\)=\\sum\_\{h\\in\\mathcal\{D\}\}p\_\{h\}^\{Q\}\(m\)\.Thus𝔼Q​\(m\)\\mathbb\{E\}\_\{Q\}\(m\)measures survival under uniformly sampled certificate candidates, not the minimum certificate size\. This is the finite\-set quantity plotted in the right panel of[Figure˜2](https://arxiv.org/html/2605.22964#S5.F2)\. The formula assumes uniform sampling from the chosen setQQ, not uniformly distributed or independent errors\. Below, we changeQQto test whether error concentration is the main obstacle\.

The full\-test curve usesQ=𝒳testQ=\\mathcal\{X\}\_\{\\rm test\}\. This is the natural audit set, but it leaves a possible objection\. If the learner’s residual errors concentrate in a simple part of the domain, then uniform sampling from the full held\-out set may spend most labels outside the relevant region\. To test this, we also evaluate a compact test subsetQtgtQ\_\{\\rm tgt\}consisting of all positives and the one\-bit output flips in positions8,9,108,9,10, where output positions are indexed from least to most significant bit\.

Forn=10n=10, this set has\|Qtgt\|=262,144⋅4=1,048,576\|Q\_\{\\rm tgt\}\|=262\{,\}144\\cdot 4=1\{,\}048\{,\}576examples, one third of the full held\-out test set\. It contains79\.9%79\.9\\%of the aggregate error mass across Transformer deceivers and77\.2%77\.2\\%of the unique test examples on which at least one deceiver errs\. Here, the aggregate error mass counts model\-example pairs\(h,x\)\(h,x\)withh​\(x\)≠f⋆​\(x\)h\(x\)\\neq f^\{\\star\}\(x\), while unique locations count the union of such examples over all deceivers\. Thus the residual errors are structured rather than uniformly spread over the held\-out set\.

The compact test subset curve asks whether this coarse structure is enough to make certification easy\. It is not\. AlthoughQtgtQ\_\{\\rm tgt\}captures most observed errors, it is still large, and the survivor count drops only after sampling a large fraction of it\. Moreover, if a deceiver has no errors inQtgtQ\_\{\\rm tgt\}, then\|EhQtgt\|=0\|E\_\{h\}^\{Q\_\{\\rm tgt\}\}\|=0and the formula givesphQtgt​\(m\)=1p\_\{h\}^\{Q\_\{\\rm tgt\}\}\(m\)=1for every targeted certificate sizemm\.

This does not rule out smaller prospective subsets\. A more compact rule, perhaps involving carries, operand patterns, output positions, or other arithmetic structure, might capture the same errors with fewer examples\. The post\-hoc union

U=⋃h∈𝒟Eh𝒳testU=\\bigcup\_\{h\\in\\mathcal\{D\}\}E\_\{h\}^\{\\mathcal\{X\}\_\{\\rm test\}\}is the extreme case\. In this run,\|U\|=15,494\|U\|=15\{,\}494, and querying all examples inUUwould eliminate every observed deceiver\. This is only a diagnostic comparison, sinceUUis chosen after evaluating the full held\-out set\. The point ofQtgtQ\_\{\\rm tgt\}is that even after moving to a simpler error\-rich subset, uniformly sampled certificate candidates may still need to be large\. That means that if every potential error\-rich subset remains exponential innn, then the certification barrier persists\.

### D\.3Finite\-class certification experiments

This section gives a complementary finite\-class analysis beyond the deceiver elimination analysis\. We run the same certification analysis in two settings\. The first is a restricted threshold\-circuit subclass ofTC0\\mathrm\{TC\}^\{0\}and the second is theAC0\\mathrm\{AC\}^\{0\}class\. In both cases, we first identify a hypothesis that is easy to certify in the base class\. We then compare it with the certification of the same hypothesis inside an enlarged class that supports the block\-deceiver construction from[Section˜4](https://arxiv.org/html/2605.22964#S4)\.

In the threshold circuit analysis, for each input lengthnn, letTC0~n,base\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}be the class of Boolean functions computable by depth\-22, size\-22threshold circuits whose gate weights lie in\{−1,0,1\}\\\{\-1,0,1\\\}and whose threshold at fan\-inmmis any integer in\[−m,m\]\[\-m,m\]\. This is the finite subclass ofTC0\\mathrm\{TC\}^\{0\}used so that we can exhaustively enumerate the circuits\. Without the weight restriction, an exhaustive search would have to range over an unbounded parameter space\. Consequently, the threshold experiment should be read as a finite analogue of theTC0\\mathrm\{TC\}^\{0\}theorem, but with the same easy\-versus\-hard certification mechanism present\.

For theAC0\\mathrm\{AC\}^\{0\}experiment, letACn,base0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}be the semantic class of Boolean functions computable by depth\-22, size\-22circuits with unbounded fan\-in AND/OR gates defined in[Section˜3](https://arxiv.org/html/2605.22964#S3)\. In both experiments, we enumerate the semantic class exactly and keep one representative circuit for each distinct truth table\. We then run the halving strategy described in[Lemma˜A\.1](https://arxiv.org/html/2605.22964#A1.Thmlemma1)using the same fixed deterministic policy\.

1. 1\.scan inputs in increasing binary order until finding the first disagreement point among the surviving hypotheses;
2. 2\.keep the smaller label side;
3. 3\.if the split is tied, keep label0\.

The process stops when one hypothesis remains\. Thus, for eachnn, the procedure returns a target in the base class and a certificate for that target inside the base class\. In the worst case, halving uses logarithmically many rounds in the size of the semantic class\.[Table˜1](https://arxiv.org/html/2605.22964#A4.T1)reports the exact semantic class sizes and the certificates returned by halving for all completed runs\.

Table 1:Exact semantic results for the finite\-class experiments\. In every completed run, the selected target isORn\\mathrm\{OR\}\_\{n\}\.In both experiments, the results show the same overall pattern, with the semantic classes growing quickly while the target selected by halving remains simple\. The classes grow from1414functions atn=2n=2to more than698698thousand functions forACn,base0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}and388388million functions forTC0~n,base\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}atn=8n=8\. Across all completed runs, the selected target isORn​\(x\)=𝟏​\[x1\+⋯\+xn≥1\]\\mathrm\{OR\}\_\{n\}\(x\)=\\mathbf\{1\}\[x\_\{1\}\+\\cdots\+x\_\{n\}\\geq 1\]\. Its certificate size inside the base class isn\+1n\+1in both experiments\.

This behavior comes from the interaction between the base classes and the deterministic halving rule\. The first queried input is always0n0^\{n\}\. At that point, the version space splits evenly, so the tie rule keeps label0\. The next decisive inputs are the one\-hot vectors

e1=\(0,…,0,1\),e2=\(0,…,1,0\),…,en=\(1,0,…,0\),e\_\{1\}=\(0,\\dots,0,1\),\\ e\_\{2\}=\(0,\\dots,1,0\),\\ \\dots,\\ e\_\{n\}=\(1,0,\\dots,0\),and among the surviving hypotheses, the minority label on each of these inputs is11\. Therefore, halving keeps the pattern

f​\(0n\)=0,f​\(ei\)=1​for every​i∈\[n\]\.f\(0^\{n\}\)=0,\\qquad f\(e\_\{i\}\)=1\\ \\text\{for every \}i\\in\[n\]\.
This description identifies what the halving strategy returns in the completed enumerations\. However, it only describes the empirical behavior of the strategy\. It does not by itself prove that the resulting sample set is a certificate forORn\\mathrm\{OR\}\_\{n\}\. To establish this, Lemmas[B\.1](https://arxiv.org/html/2605.22964#A2.Thmlemma1)and[B\.2](https://arxiv.org/html/2605.22964#A2.Thmlemma2)in[Section˜B\.5](https://arxiv.org/html/2605.22964#A2.SS5)show that the above set is indeed a certificate forORn\\mathrm\{OR\}\_\{n\}inside the two base classes\.

Once the easy certification cases have been obtained, we turn to their behavior under overparametrization\. For both circuit families, we use the general block\-deceiver construction from[Section˜4](https://arxiv.org/html/2605.22964#S4), which gives a2n2^\{n\}certificate lower bound for every target in the corresponding base class\.333For some specialized target function, deceiver constructions may be written with less overhead, but the constructions used here are a target\-independent version\.

In the threshold experiment, the overparametrized classTC0~n,over\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{over\}\}is obtained from the base class by adding one extra threshold gate\. Consequently, all base functions remain present in the enlarged class\.

For the hardness result, the extra gate is used as a trigger gate, as in the block\-deceiver construction of[Proposition˜B\.4](https://arxiv.org/html/2605.22964#A2.Thmproposition4)\. Unlike the unbounded case in[Proposition˜B\.4](https://arxiv.org/html/2605.22964#A2.Thmproposition4), however, the base classTC0~n,base\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}uses only unit weights, and a unit\-weight trigger is not sufficient to override every possible base circuit\.

Thus,TC0~n,over\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{over\}\}requires the trigger gate to enter the output gate with a larger signed coefficient\. Since base scores and thresholds are bounded byn\+1n\+1in absolute value, a coefficient of magnitude2​n\+3\>2​\(n\+1\)2n\+3\>2\(n\+1\)can override any base output\. Hence, it suffices to allow the circuit weights to lie in\[−\(2​n\+3\),2​n\+3\]∩ℤ\[\-\(2n\+3\),2n\+3\]\\cap\\mathbb\{Z\}\.

As in[Proposition˜B\.4](https://arxiv.org/html/2605.22964#A2.Thmproposition4), every base target has one deceiver for each singleton block\. Since the2n2^\{n\}singleton blocks are disjoint, the disjoint\-disagreement principle from[Proposition˜4\.1](https://arxiv.org/html/2605.22964#S4.Thmproposition1)gives

certTC0~n,over⁡\(f\)≥2n\\operatorname\{cert\}\_\{\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{over\}\}\}\(f\)\\geq 2^\{n\}for everyf∈TC0~n,basef\\in\\widetilde\{\\mathrm\{TC\}^\{0\}\}\_\{n,\\mathrm\{base\}\}, includingORn\\mathrm\{OR\}\_\{n\}\.

For theAC0\\mathrm\{AC\}^\{0\}experiment, the overparametrized classACn,over0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{over\}\}is obtained from the base class by adding one pattern\-detection gate and one final combining gate, increasing the original depth by one\. Nevertheless, all base functions remain present in the enlarged class at the semantic level\. Unlike in the threshold case, the deceiver construction here is exactly theAC0\\mathrm\{AC\}^\{0\}construction from[Propositions˜B\.5](https://arxiv.org/html/2605.22964#A2.Thmproposition5)and[B\.2](https://arxiv.org/html/2605.22964#A2.Thmtheorem2)\. Thus,ACn,over0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{over\}\}uses only44total gates and has depth33\. Consequently, every function inACn,base0\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}has2n2^\{n\}disjoint deceivers, yielding

certACn,over0⁡\(f\)≥2n\\operatorname\{cert\}\_\{\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{over\}\}\}\(f\)\\geq 2^\{n\}for everyf∈ACn,base0f\\in\\mathrm\{AC\}^\{0\}\_\{n,\\mathrm\{base\}\}, includingORn\\mathrm\{OR\}\_\{n\}\.

![Refer to caption](https://arxiv.org/html/2605.22964v1/x6.png)

![Refer to caption](https://arxiv.org/html/2605.22964v1/x7.png)

Figure 5:Easy\-versus\-hard certification in the two finite\-class experiments\. Left: the restricted threshold\-circuit experiment\. Right: theAC0\\mathrm\{AC\}^\{0\}experiment\. In each panel, the blue curve is the certificate size of the hypothesis selected by halving inside the base class, and the orange curve is the general halving upper bound for the corresponding semantic class\. The green curve is the lower bound for the same selected target inside the target\-independent enlarged class, where singleton\-block deceivers give a2n2^\{n\}lower bound\. In all completed runs, the selected easy target isORn\\mathrm\{OR\}\_\{n\}\.We further illustrate the result in[Figure˜5](https://arxiv.org/html/2605.22964#A4.F5)\. The blue curve is the minimum certificate size of the target selected by halving inside the base class, and the orange curve is the generic halving upper bound for the corresponding semantic class\. The green curve is the lower bound2n2^\{n\}obtained from the block\-deceiver overparametrization\. This is a same\-target comparison: the blue curve measures the certificate size ofORn\\mathrm\{OR\}\_\{n\}in the base class, while the green curve lower\-bounds the certificate size of the same function in the overparametrized class\. Thus, a finite semantic class can contain a very easy target, while a small enlargement that supports block deceivers makes certification of that same target exponentially harder\.