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

May combine two claims.

For fixed n, depth d at least 1, and s at least 1, with H = TC0_{d,s}, there exists f in H with cert(f, H) at most O_s((n+s)^2); in particular, if d is fixed and s = n^{O(1)}, then H contains some function with polynomial certificate size.

“Then there exists f ∈ H with cert(f, H) ≤ O s (n + s) 2 .”

• Also stated in: § B.1 Counting bounds for circuit classes · plain

  “In particular, if d is fixed and s = n O(1) , then H contains some function with polynomial certificate size.”

May combine two claims.

Adding one threshold gate that detects a = pi lets us modify the output gate so that the circuit accepts every input in B_pi and agrees with the target outside B_pi; the resulting disagreement sets E_pi are disjoint.

“Adding one threshold gate that detects a = π lets us modify the output gate so that the circuit accepts every input in B π and agrees with the target outside B π .Denote the resulting circuit by g π and its disagreement set by E π .Since E π ⊆ B π and the blocks are disjoint, the sets {E π } π∈{0,1} n are disjoint.”

May combine two claims.

In bounded fan-in circuits such as NC1, exact trigger detection costs Theta(t) extra gates and Theta(log t) extra depth, so extra k gates give lower bounds of 2^{Omega(k)}.

“In bounded fan-in circuits such as NC 1 , exact trigger detection costs Θ(t) extra gates and Θ(log t) extra depth, so extra k gates give lower bounds of 2 Ω(k) .”

May combine two claims.

For m = poly(n), almost all constructed deceivers survive, and the decay only becomes visible on an exponential scale in n.

“For m = poly(n), almost all constructed deceivers survive, and the decay only becomes visible on an exponential scale in n.”

May combine two claims.

A depth-2 threshold circuit recognizes addition by checking Z - A - B >= 0 and A + B - Z >= 0, and feeding the two tests into a final threshold gate; the target recognizer uses three threshold gates.

“A depth-2 threshold circuit recognizes addition by checking Z -A -B ≥ 0 and A + B -Z ≥ 0, and feeding the two tests into a final threshold gate.”

• Also stated in: § Constructed threshold circuits. · plain

  “Thus the target recognizer uses three threshold gates.”

May combine two claims.

Among the 150 accepted models, 87 are test-exact, and 63 have residual test errors.

“Among the 150 accepted models, 87 are test-exact, and 63 have residual test errors.”

May combine two claims.

For fixed epsilon > 0, an epsilon-certificate only needs to eliminate hypotheses whose relative error is larger than epsilon; in the block construction, a deceiver with trigger length t has error at least 2^{-t-1} and at most 2^{-t}; thus Proposition 4.2 gives a nontrivial lower bound only when epsilon < 2^{-t-1}, which forces t < log2(1/epsilon) - 1.

“For fixed ε > 0, an ε-certificate only needs to eliminate hypotheses whose relative error is larger than ε.In the block construction, a deceiver with trigger length t has error at least 2 -t-1 and at most 2 -t .Thus Proposition 4.2 gives a nontrivial lower bound only when ε < 2 -t-1 , which forces t < log 2 (1/ε) -1.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The enumeration in Section D.3 shows that the deterministic halving rule selects OR_n in the completed runs.

“The enumeration in Section D.3 shows that the deterministic halving rule selects OR n in the completed runs.”

Probably not a substantial claim: may not pass S3 (load-bearing).

D is the set of 63 Transformer deceivers.

“Let D be the set of 63 Transformer deceivers.”

Classified as probably not a substantial claim. May combine two claims.

If a certificate candidate S_m is sampled uniformly without replacement from Q, then h survives exactly when S_m misses E^Q_h, giving p^Q_h(m) = (|Q|-|E^Q_h| choose m)/(|Q| choose m) and E^Q(m) = sum_{h∈D} p^Q_h(m).

“If a certificate candidate S m is sampled uniformly without replacement from Q, then h survives exactly when S m misses E Q h .Hence p Q h (m) = |Q| -|E Q h | m |Q| m , E Q (m) = h∈D p Q h (m).”

• AssumptionThe authors state this as an assumption: The survivor formula assumes uniform sampling from the chosen set Q, not uniformly distributed or independent errors.

May combine two claims.

Each constructed deceiver has e_n = |Eπ| = 2^n(2^{n+1}-1) errors, all of them false positives.

“Hence each constructed deceiver has e n = |E π | = 2 n (2 n+1 -1) errors, all of them false positives.”

May combine two claims.

For every fixed c > 0, the same conclusion holds for NC1_s, the class of fan-in-2 circuits with n inputs, size at most s, and depth at most c log n; in particular, if s = n^{O(1)}, then NC1_s contains a function with polynomial certificate size.

“Moreover, for every fixed c > 0, the same conclusion holds for NC 1 s , the class of fan-in-2 circuits with n inputs, size at most s, and depth at most c log n.In particular, if s = n O(1) , then NC 1 s contains a function with polynomial certificate size.”

May combine two claims.

The compact test subset curve asks whether the coarse structure is enough to make certification easy, and it is not.

“The compact test subset curve asks whether this coarse structure is enough to make certification easy.It is not.”

May combine two claims.

The trigger head outputs the trigger bit z(x) = 1[x ∈ B_{I,π}] ∈ {0,1} inside the stated model; no hidden second view is used, and query, key, and value are all affine functions of the same projected-pre-norm code block.

“The trigger head outputs the trigger bit z(x) = 1[x ∈ B I,π ] ∈ {0, 1} inside the stated model.No hidden second view is used: query, key, and value are all affine functions of the same projected-pre-norm code block.”

• Also stated in: § Step 4: trigger head, trigger bits, and final classifier. · plain

  “If x / ∈ B I,π then J(x) ̸ = ∅ and the unique maximal score is 2, attained exactly on J(x), so AHAT averages the corresponding values v G (β) = 0 and outputs z ′ i = 0.If x ∈ B I,π then J(x) = ∅ and the maximal score is 1, attained exactly on I (all positions are coded as γ), so AHAT averages the corresponding values v G (γ) = 1 and outputs z ′ i = 1.”

• Also stated in: § Step 4: trigger head, trigger bits, and final classifier. · plain

  “Therefore z ′ i = 1[x ∈ B I,π ] ∈ {0, 1} for all i ∈ [n].”

Probably not a substantial claim: may not pass S3 (load-bearing).

The trigger-head parameters use only fixed dyadic constants, so they are representable once p ≥ p0 for an absolute constant p0.

“The trigger-head parameters below use only fixed dyadic constants, so they are representable once p ≥ p 0 for an absolute constant p 0 .”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

If a deceiver has no errors in Q_tgt, then |E^{Q_tgt}_h|=0 and the formula gives p^{Q_tgt}_h(m)=1 for every targeted certificate size m.

“Moreover, if a deceiver has no errors in Q tgt , then |E Qtgt h | = 0 and the formula gives p Qtgt h (m) = 1 for every targeted certificate size m.”

May combine two claims.

If the output gate of C⋆ is an OR gate, then g_{π,1}(x) := f⋆(x) ∨ CHECK_{I,π}(x) belongs to AC0_{d,s+1}, equals 1 on Bπ, and equals f⋆(x) outside Bπ.

“(iii) if the output gate of C ⋆ is an OR gate, then g π,1 (x) := f ⋆ (x) ∨ CHECK I,π (x) belongs to AC 0 d,s+1 , and g π,1 (x) = 1, x ∈ B π , f ⋆ (x), x / ∈ B π ;”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The standard 1/√d head scaling applied to attention scores is a fixed positive constant and does not change which positions attain the maximum.

“The standard 1/ √ d head scaling applied to attention scores is a fixed positive constant and does not change which positions attain the maximum.”

May combine two claims.

Although Q_tgt captures most observed errors, it is still large, and the survivor count drops only after sampling a large fraction of it.

“Although Q tgt captures most observed errors, it is still large, and the survivor count drops only after sampling a large fraction of it.”

May combine two claims.

For a threshold circuit C_star of size s and depth at most d computing f_star, with d at least 2, fixed I subset of [n] with |I| = t and pattern pi, there is a threshold gate CHECK_{I,pi} of depth 1 such that CHECK_{I,pi}(x) = 1 iff x in B_pi; and for each sigma in {0,1} there is a threshold circuit C_{pi,sigma} of size at most s+1 and depth at most d such that g_{pi,sigma}(x) = sigma for x in B_p

“there is a threshold gate CHECK I,π of depth 1 such that CHECK I,π (x) = 1 ⇐⇒ x ∈ B π ;”

• Also stated in: § B.2 Threshold circuits · plain

  “for each σ ∈ {0, 1} there is a threshold circuit C π,σ of size at most s + 1 and depth at most d such that g π,σ (x) := σ, x ∈ B π , f ⋆ (x), x / ∈ B π ,”

May combine two claims.

Under the stated hypotheses on a projected-pre-norm p(n)-precision AHAT Transformer binary classifier family, its language belongs to DLOGTIME-uniform TC0; if the parameter family is only logspace-uniform, it belongs to logspace-uniform TC0; if parameters are arbitrary advice, it belongs to non-uniform TC0.

“Then the language L T := {x ∈ {0, 1} * : T |x| (x) = 1} belongs to DLOGTIME-uniform TC 0 .If the parameter family is only logspace-uniform, then L T belongs to logspace-uniform TC 0 .If the parameters are treated as arbitrary advice, then L T belongs to non-uniform TC 0 .”

• AssumptionRests on an assumption: TC0 is closed under polynomially many parallel copies and under a constant number of serial compositions.

May combine two claims.

Among the 150 accepted models, 98 make no mistakes on the fixed validation check used for acceptance, and eleven of these validation-perfect models are nevertheless deceivers on the held-out test set, with between 2 and 61 test errors.

“Among the 150 accepted models, 98 make 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 between 2 and 61 test errors.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The post-hoc union U of observed error locations is the extreme case; in this run |U|=15,494, and querying all examples in U would eliminate every observed deceiver, but this is only a diagnostic comparison since U is chosen after evaluating the full held-out set.

“The post-hoc union U = h∈D E Xtest h is the extreme case.In this run, |U | = 15,494, and querying all examples in U would eliminate every observed deceiver.This is only a diagnostic comparison, since U is chosen after evaluating the full held-out set.”

May combine two claims.

Substantial pruning appears only when the certificate-candidate size moves very close to 2^n, as seen in the 2^{0.95n} and 2^{0.99n} columns, and the constructed family is fully eliminated only at 2^n well-chosen examples.

“Substantial pruning appears only when the certificate-candidate size moves very close to 2 n , as seen in the 2 0.95n and 2 0.99n columns, and the constructed family is fully eliminated only at 2 n well-chosen examples.”

May combine two claims.

For fixed n, s, d, with H = AC0_{d,s}, there exists f in H such that cert(f, H) is at most O(s(n+s)); in particular, for constant d and s = n^{O(1)}, the class contains at least one function with polynomial certificate size.

“Then there exists f ∈ H such that cert f, H ≤ O s(n + s) .”

• Also stated in: § B.1 Counting bounds for circuit classes · plain

  “In particular, for constant d and s = n O(1) , the class contains at least one function with polynomial certificate size.”

May combine two claims.

In both experiments, the results show the same overall pattern, with the semantic classes growing quickly while the target selected by halving remains simple.

“In both experiments, the results show the same overall pattern, with the semantic classes growing quickly while the target selected by halving remains simple.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The process stops when one hypothesis remains; thus, for each n, the procedure returns a target in the base class and a certificate for that target inside the base class, and in the worst case halving uses logarithmically many rounds in the size of the semantic class.

“The process stops when one hypothesis remains.Thus, for each n, 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.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Figure 3 heatmap reports the best possible remaining count after m labeled examples for the constructed subfamily D={gπ: π∈{0,1}^n}.

“The heatmap reports the best possible remaining count after m labeled examples for the constructed subfamily D = {g π : π ∈ {0, 1} n }.”

May combine two claims.

The bound that each labeled example eliminates at most one constructed deceiver is tight by choosing one error point from a distinct block whenever possible, so the remaining count is max{2^n - m, 0}.

“This bound is tight by choosing one error point from a distinct block whenever possible.Hence the remaining count is max{2 n -m, 0}.”

Classified as probably not a substantial claim. May combine two claims.

For a trigger pattern π ∈ {0,1}^n, the deceiver gπ accepts every input with a=π and agrees with the target outside this block.

“For a trigger pattern π ∈ {0, 1} n , the deceiver g π accepts every input with a = π and agrees with the target outside this block.”

May combine two claims.

If the output gate of C⋆ is an AND gate, then g_{π,0}(x) := f⋆(x) ∧ MISS_{I,π}(x) belongs to AC0_{d,s+1}, equals 0 on Bπ, and equals f⋆(x) outside Bπ.

“(iv) if the output gate of C ⋆ is an AND gate, then g π,0 (x) := f ⋆ (x) ∧ MISS I,π (x) belongs to AC 0 d,s+1 , and g π,0 (x) = 0, x ∈ B π , f ⋆ (x), x / ∈ B π .”

Probably not a substantial claim: may not pass S3 (load-bearing).

Table 1 reports the exact semantic class sizes and the certificates returned by halving for all completed runs.

“Table 1 reports the exact semantic class sizes and the certificates returned by halving for all completed runs.”

May combine two claims.

Inside this block, the target accepts exactly one value of z for each fixed b, while gπ accepts all 2^{n+1} candidates.

“Inside this block, the target accepts exactly one value of z for each fixed b, while g π accepts all 2 n+1 candidates.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

End-to-end training from only the final accept/reject label was less reliable, so intermediate supervision is used to make training produce a large set of strong candidates, and the auxiliary supervision is used only during training.

“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.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The construction keeps the inherited Transformer computation at the same precision p, and the final readout uses two copies of the trigger bit to force the desired output at that same precision.

“Therefore, the construction keeps the inherited Transformer computation at the same precision p, and the final readout uses two copies of the trigger bit to force the desired output at that same precision.”

May combine two claims.

For n=10, the compact test subset Q_tgt has 1,048,576 examples, one third of the full held-out test set, and contains 79.9% of the aggregate error mass across Transformer deceivers and 77.2% of the unique test examples on which at least one deceiver errs.

“For n = 10, this set has |Q tgt | = 262,144 • 4 = 1,048,576 examples, one third of the full held-out test set.It contains 79.9% of the aggregate error mass across Transformer deceivers and 77.2% of the unique test examples on which at least one deceiver errs.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The resulting sample counts are 8,808,036 training examples, 629,148 validation examples, and 3,145,728 held-out test examples.

“The resulting sample counts are 734,003 • 12 = 8,808,036 training examples, 52,429 • 12 = 629,148 validation examples, and 262,144 • 12 = 3,145,728 held-out test examples.”

Classified as probably not a substantial claim.

The block Bπ = {(a,b,z): a=π} has size 2^{2n+1}.

“The block B π = {(a, b, z) : a = π} has size 2 2n+1 .”

May combine two claims.

For each n, certificate candidates of size up through 2^{0.75n} leave almost all of the 2^n constructed deceivers intact, and even at 2^{0.9n} the surviving family remains large.

“For each n, certificate candidates of size up through 2 0.75n leave almost all of the 2 n constructed deceivers intact, and even at 2 0.9n the surviving family remains large.”

Classified as probably not a substantial claim. May combine two claims.

This is a same-target comparison: the blue curve measures the certificate size of OR_n in the base class, while the green curve lower-bounds the certificate size of the same function in the overparametrized class.

“This is a same-target comparison: the blue curve measures the certificate size of OR n in the base class, while the green curve lower-bounds the certificate size of the same function in the overparametrized class.”

May combine two claims.

For the hardness result, the extra gate is used as a trigger gate as in Proposition B.4; unlike the unbounded case, the base class TC0_n,base uses only unit weights and a unit-weight trigger is not sufficient to override every possible base circuit, so TC0_n,over requires the trigger gate to enter the output gate with a larger signed coefficient, and since base scores and thresholds are bounded by

“For the hardness result, the extra gate is used as a trigger gate, as in the block-deceiver construction of Proposition B.4.Unlike the unbounded case in Proposition B.4, however, the base class TC 0 n,base uses only unit weights, and a unit-weight trigger is not sufficient to override every possible base circuit.Thus, TC 0 n,over requires the trigger gate to enter the output gate with a larger”

• cites Proposition B.4Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Projected pre-norm lets the original heads and the original part of the feedforward block project only to the first m coordinates, so the auxiliary coordinates never enter their layer norm; the new trigger head G instead projects to a dedicated 4-dimensional code block and uses only that one normalized code block.

“Projected pre-norm lets the original heads and the original part of the feedforward block project only to the first m coordinates, so the auxiliary coordinates never enter their layer norm.The new trigger head G instead projects to a dedicated 4-dimensional code block and uses only that one normalized code block.”

Classified as probably not a substantial claim. May combine two claims.

In Figure 5, the blue curve is the minimum certificate size of the target selected by halving inside the base class, the orange curve is the generic halving upper bound for the corresponding semantic class, and the green curve is the lower bound 2^n obtained from the block-deceiver overparametrization.

“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 bound 2 n obtained from the block-deceiver overparametrization.”

May combine two claims.

One AHAT head is computable in uniform TC0; all heads and positions are computed in parallel, so the whole attention block is computable in uniform TC0; and bidirectional attention causes no additional difficulty because the circuit simply ranges over all j ∈ [n].

“Thus one AHAT head is computable in uniform TC 0 .All heads and positions are computed in parallel, so the whole attention block is computable in uniform TC 0 .Bidirectional attention causes no additional difficulty: the circuit simply ranges over all j ∈ [n].”

Probably not a substantial claim: may not pass S3 (load-bearing).

The construction is used for the ordinary output-only quantity cert(f*,H).

“The construction is used for the ordinary output-only quantity cert(f ⋆ , H).”

May combine two claims.

The classes grow from 14 functions at n=2 to more than 698 thousand functions for AC0_n,base and 388 million functions for TC0_n,base at n=8.

“The classes grow from 14 functions at n = 2 to more than 698 thousand functions for AC 0 n,base and 388 million functions for TC 0 n,base at n = 8.”

Classified as probably not a substantial claim. May combine two claims.

In the threshold experiment, the overparametrized class TC0_n,over is obtained from the base class by adding one extra threshold gate, and consequently all base functions remain present in the enlarged class.

“In the threshold experiment, the overparametrized class TC 0 n,over is obtained from the base class by adding one extra threshold gate.Consequently, all base functions remain present in the enlarged class.”

Classified as probably not a substantial claim. May combine two claims.

For the AC0 experiment, the overparametrized class AC0_n,over is obtained from the base class by adding one pattern-detection gate and one final combining gate, increasing the original depth by one, and all base functions remain present in the enlarged class at the semantic level.

“For the AC 0 experiment, the overparametrized class AC 0 n,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.”

May combine two claims.

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 to D_{p(n)}, hence is computable in uniform TC0; and the ReLU and final binary threshold are computed by comparison, so they are also in uniform TC0.

“Embeddings are computed by DLOGTIME-uniform lookup.Every affine map in the query, key, value, feedforward, projection, and final classifier blocks is a polynomialsize collection of products followed by an iterated sum and a truncation/rounding back to D p(n) , hence is computable in uniform TC 0 .The ReLU and final binary threshold are computed by comparison, so they are also in uniform TC 0 .”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

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.

“The DLOGTIME-uniformity of the circuit follows from the DLOGTIME-uniform parameter access and the regular indexing of positions, heads, coordinates, and layers.Replacing DLOGTIMEuniform access by logspace-uniform access gives the logspace-uniform version, and dropping uniform access gives the non-uniform version.”

May combine two claims.

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.

“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, polynomialsize threshold circuit.”

May combine two claims.

Across all completed runs, the selected target is OR_n(x)=1[x1+...+xn≥1], and its certificate size inside the base class is n+1 in both experiments.

“Across all completed runs, the selected target is OR n (x) = 1[x 1 + • • • + x n ≥ 1].Its certificate size inside the base class is n + 1 in both experiments.”

May combine two claims.

As in Proposition B.4, every base target has one deceiver for each singleton block; since the 2^n singleton blocks are disjoint, the disjoint-disagreement principle from Proposition 4.1 gives cert_{TC0_n,over}(f) ≥ 2^n for every f ∈ TC0_n,base, including OR_n.

“As in Proposition B.4, every base target has one deceiver for each singleton block.Since the 2 n singleton blocks are disjoint, the disjoint-disagreement principle from Proposition 4.1 gives cert TC 0 n,over (f ) ≥ 2 n for every f ∈ TC 0 n,base , including OR n .”

• cites Proposition B.4Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Proposition 4.1Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Classified as probably not a substantial claim. May combine two claims.

The description identifies what the halving strategy returns in the completed enumerations, but it only describes empirical behavior and does not by itself prove that the resulting sample set is a certificate for OR_n; Lemmas B.1 and B.2 in Section B.5 show that the above set is indeed a certificate for OR_n inside the two base classes.

“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 for OR n .To establish this, Lemmas B.1 and B.2 in Section B.5 show that the above set is indeed a certificate for OR n inside the two base classes.”

• cites Lemmas B.1Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites B.2Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

The lower bound in Proposition 4.2 is essentially the inverse of the tolerance: optimizing over t gives cert_epsilon_n at least on the order of 1/epsilon_n and cert_R_n at least on the order of 2^n/R_n; consequently, the lower bound grows with n only when the relative tolerance shrinks with n.

“The lower bound in Proposition 4.2 is essentially the inverse of the tolerance: optimizing over t gives cert εn ≳ 1/ε n and cert Rn ≳ 2 n /R n .Consequently, our lower bound grows with n only when the relative tolerance shrinks with n.”

May combine two claims.

A labeled value can reveal at most one of the changes from disjoint trigger blocks; therefore any exact certificate must contain at least one point from every block.

“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.”

May combine two claims.

When epsilon is fixed, the upper bound on t is a constant, so the lower bound 2^t is at most on the order of 1/epsilon, not exponential in n; block deceivers with sufficiently small relative error need not be eliminated, and they may still make exponentially many absolute mistakes while their relative error is small enough that a fixed-relative-error certificate does not need to eliminate them.

“When ε is fixed, this upper bound on t is a constant, so the lower bound 2 t is at most on the order of 1/ε, not exponential in n.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”

May combine two claims.

Both experiments use the same survivor calculation, which is an exact finite-population calculation and does not assume independent survival events or uniformly distributed errors.

“This is an exact finite-population calculation.It does not assume independent survival events or uniformly distributed errors.”

May combine two claims.

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模型has

“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”

May combine two claims.

In both experiments, 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.

“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.”

May combine two claims.

The smaller Transformer 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.

“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.”

Classified as probably not a substantial claim. May combine two claims.

Test-exactness is exactness relative to the held-out set, not exactness over all possible triples (a,b,z), since the full 10-bit domain contains 2^31 triples and the held-out set contains only the correct output and one-bit output flips for held-out operand pairs.

“This is exactness relative to the held-out set.It is not exactness over all possible triples (a, b, z), since the full 10-bit domain contains 2 31 triples and the held-out set contains only the correct output and one-bit output flips for held-out operand pairs.”

May combine two claims.

For a projected-pre-norm AHAT Transformer family satisfying the hypotheses of Proposition C.1, with p(n) = O(log n) and p(n) ≥ p0, and with DLOGTIME-uniform added trigger data, the language recognized by the deceiver Transformer family belongs to DLOGTIME-uniform TC0; with logspace-uniform base and trigger data it belongs to logspace-uniform TC0; with arbitrary advice it is contained in non-unifom

“Then the language recognized by {T dec n } n≥1 belongs to DLOGTIME-uniform TC 0 .If the base Transformer family and the added trigger data are only logspace-uniform, then the resulting language belongs to logspace-uniform TC 0 .If they are treated as arbitrary advice, then the resulting family is contained in non-uniform TC 0 .”

Classified as probably not a substantial claim. May combine two claims.

For each operand pair, one positive example and all one-bit flips of the true output are generated, giving 12 examples per pair: one correct sum and 11 hard negatives, a choice that avoids making the negative class dominated by random outputs far from the true sum.

“For each operand pair, we generate one positive example and all one-bit flips of the true output.Thus each pair gives 12 examples: one correct sum and 11 hard negatives.This choice avoids making the negative class dominated by random outputs that are far from the true sum.”

Classified as probably not a substantial claim.

The split is made over operand pairs (a,b), so the held-out test set contains unseen operand pairs rather than new perturbations of operands seen during training.

“The split is made over operand pairs (a, b), so the held-out test set contains unseen operand pairs rather than new perturbations of operands seen during training.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Every language computed by a log-precision Transformer family with L = O(1) layers and logspace-uniform access to its parameters and embeddings is contained in logspace-uniform TC0.

“Every language computed by a log-precision Transformer family with L = O(1) layers and logspace-uniform access to its parameters and embeddings is contained in logspace-uniform TC 0 .”

• cites Merrill and Sabharwal [22]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S3 (load-bearing).

The threshold experiment should be read as a finite analogue of the TC0 theorem, but with the same easy-versus-hard certification mechanism present.

“Consequently, the threshold experiment should be read as a finite analogue of the TC 0 theorem, but with the same easy-versus-hard certification mechanism present.”

Classified as probably not a substantial claim. May combine two claims.

In both experiments, the semantic class is enumerated exactly and one representative circuit is kept for each distinct truth table, and the halving strategy described in Lemma A.1 is run using the same fixed deterministic policy.

“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 using the same fixed deterministic policy.”

• cites Lemma A.1Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

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.

“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.”

Classified as probably not a substantial claim.

An accepted model is called test-exact if it makes zero mistakes on the full held-out test set of 3,145,728 examples.

“An accepted model is called test-exact if it makes zero mistakes on the full held-out test set of 3,145,728 examples.”

Classified as probably not a substantial claim.

E^Q(m) measures survival under uniformly sampled certificate candidates, not the minimum certificate size.

“Thus E Q (m) measures survival under uniformly sampled certificate candidates, not the minimum certificate size.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

A run is accepted only after all four checks reach at least 99.9% accuracy: training positives, training negatives, validation positives, and validation negatives; the held-out test set is evaluated only after acceptance.

“A run is accepted only after all four checks reach at least 99.9% accuracy: training positives, training negatives, validation positives, and validation negatives.The held-out test set is evaluated only after acceptance.”

Probably not a substantial claim: may not pass S3 (load-bearing).

No one-dimensional layer normalization or t-dependent thresholding is used on the auxiliary coordinates.

“No one-dimensional layer normalization or t-dependent thresholding is used on the auxiliary coordinates.”