Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence
Open accessAbstract
Sound deductive reasoning -- the ability to derive new knowledge from existing facts and rules -- is an indisputably desirable aspect of general intelligence. Despite the major advances of AI systems in areas such as math and science, especially since the introduction of transformer architectures, it is well-documented that even the most advanced frontier systems regularly and consistently falter on easily-solvable deductive reasoning tasks. Hence, these systems are unfit to fulfill the dream of achieving artificial general intelligence capable of sound deductive reasoning. We argue that their unsound behavior is a consequence of the statistical learning approach powering their development. To overcome this, we contend that to achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions on reasoning problems and algorithmic tasks to embracing the more ambitious exact learning paradigm, which demands correctness on all inputs. We argue that exact learning is both essential and possible, and that this ambitious objective should guide algorithm design.
Verified 2026-10-23 · 2 references not checked yet
AI snapshot
Written from the paper’s full text.
TL;DR
The paper argues that statistical learning is fundamentally misaligned with reliable deductive reasoning and that AI should pivot to exact learning, which demands correctness on all well-formed inputs. It supports this with lower bounds showing statistical learners can need exponentially many samples to identify simple linear classifiers, plus a small transformer experiment where reasoning traces improve but do not achieve exactness.
Key findings
- Proposition 3.1: For \(X=\{0,1\}^d\), with \(n=o(2^d)\) uniform samples, any learner fails to identify the target function with constant probability, even for simple linear classifiers.
- Theorem 3.2 gives a lower bound: with fewer than \(1/(2 \inf_{h,h'\in H,h\neq h'} P(h(X)=h'(X)))\) samples, all learners fail to identify the labeling function for at least one \(h^*\in H\) with probability at least \(1/4\). Theorem 3.3 gives a similar bound for \(G\)-symmetric learners.
- For the linear classifiers \(h_\geq(x)=1(\mathrm{left}(x)\geq \mathrm{right}(x))\) and \(h_>(x)=1(\mathrm{left}(x)>\mathrm{right}(x))\), no learner can distinguish them unless it sees \(2^{d/2}\) samples or more; a maximum-margin classifier can be taught with a dataset of size at most \(2d+2\) (Proposition B.1).
- In a decoder-only transformer experiment on propositional logic, training with reasoning traces achieved near-perfect but not exact performance: Figure 3 caption reports 1.0 on RP data and 0.999 on LP data.
Methods
- Position paper combining formal analysis of statistical versus exact learning, including new lower bounds for exact learning and symmetric learners, with a small synthetic reasoning experiment.
- The experiment trains a decoder-only transformer on propositional logic problems generated using the RP and LP recipes from Zhang et al. (2023a), with 5–20 predicates, 0–40 rules, reasoning depth up to 6, generated on-the-fly, and evaluated on 2048 randomly generated RP and LP problems using greedy decoding.
- Architecture/training: 10 layers, embedding size 1024 split across 8 heads, MLP hidden size 1024 with GELU, RoPE positional embeddings, AdamW with batch size 256, peak learning rate 0.0001, warmup and final rate 0.00001, 2000 warmup steps, gradient clipping by global norm 1, custom logic tokenizer, and conditional training on tokens following the prompt.
Limitations
- The paper states that verifying exact learning is very hard, especially for neural networks, and that calculating a minimal teaching set for a powerful learner may not be feasible.
- It also states that natural language problem specifications are rarely fully specific, though it argues this is not a fundamental issue.
- Evident from the text: the work is primarily a position and theoretical paper, the experiment is limited to simple propositional logic with a small transformer, and exact learning is not achieved in that experiment.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
5 of 40 cited sources checked · 4 supported · 0 flagged · accuracy not yet measured
- Premisecitation§ 4 Beyond the naive approach · p. 11
Leaving out from the loss computation the tokens that are part of the input has been documented to harm performance.
“this has been documented to harm performance (Shi et al., 2024; Huerta-Enochian and Ko, 2024).”
Quote in the paperNot a substantial claim2 of 2 sources checked - Findingreasoning§ To achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions of reasoning problems and algorithmic tasks to embracing the exact learning criterion, which necessitates universal correctness. · p. 3
The paper gives lower bounds on the critical sample size for symmetric learners that are specific for both the target hypothesis and the training distribution.
“We next use this to give lower bounds on this critical sample size for symmetric learners that is specific for both the target hypothesis and the training distribution .”
Quote in the paperSubstantial claim - Findingreasoning§ 2 From statistical to exact learning · p. 5
Exact learning is identical to the worst-case out-of-distribution generalization.
“It is not hard to see that sup ρ L ρ ⊗ µ Y | X ( θ ) = L ∗ µ Y | X ( θ ) ; that is, exact learning is identical to the worst-case out-of-distribution generalization.”
Quote in the paperSubstantial claim - Findingnone given§ 3 Naive statistical approaches to exact learning fail · p. 7
Theorem 3.2: Fix a distribution ρ over X and let X∼ρ. With a sample from ρ that has fewer examples than 1/(2 inf_{h,h'∈H,h≠h'} P(h(X)=h'(X))), all learners fail to identify the function used to label the sample for at least one of the labeling functions h*∈H with probability of at least 1/4.
“Theorem 3.2 (All learners fail on some task for small samples) . Fix a distribution ρ over X and let X ∼ ρ . With a sample from ρ that has fewer examples than 1 / (2 inf h,h ′ ∈H ,h = h ′ P ( h ( X ) = h ′ ( X ))) , all learners fail to identify the function used to label the sample for at least one of the labeling functions h ∗ ∈ H with probability of at least 1 / 4 .”
Quote in the paperSubstantial claim - Findingnone given§ 3 Naive statistical approaches to exact learning fail · p. 6
Proposition 3.1: For X={0,1}^d, two linear classifiers f*1(x)=1(x=0) and f*0(x)≡0, and n=o(2^d) samples drawn independently from the uniform distribution over X, any learner fails to identify the target function f* with constant probability either when f*=f*0 or when f*=f*1.
“Proposition 3.1. Let X = { 0 , 1 } d , and consider the two linear classifiers f ∗ 1 ( x ) = 1 ( x = 0 ) and f ∗ 0 ( x ) ≡ 0 . Let n = o (2 d ) and let X 1 , . . . , X n be drawn independently from uniform distribution over X . Then any learner fails to identify the target function f ∗ with constant probability either when f ∗ = f ∗ 0 or when f ∗ = f ∗ 1 .”
Quote in the paperNot a substantial claim
- Findingreasoning§ 3 Naive statistical approaches to exact learning fail · p. 7
For any h,h': X→{0,1} functions that return 0 on about a constant proportion of the domain elements and differ on only o(2^d) elements, no learner is able to reliably solve the exact learning problem in polynomial time in d where the labeling function could be either h or h'.
“Now take any h, h ′ : X → { 0 , 1 } functions that return 0 on about a constant proportion of the domain elements and differ on only o (2 d ) elements. The above theorem immediately shows that no learner is able to reliably solve the exact learning problem in polynomial time in d where the labeling function could be either h or h ′ .”
Quote in the paperSubstantial claim - Findingreasoning§ 3 Naive statistical approaches to exact learning fail · p. 7
Theorem 3.2 gives a lower bound on the minimum sample size needed for exact learning that depends on the interplay between the input distribution and the hypothesis class H.
“The theorem gives a lower bound on the minimum sample size needed for exact learning that depends on the interplay between the input distribution and the hypothesis class H .”
Quote in the paperSubstantial claim - Findingreasoning§ 2 From statistical to exact learning · p. 6
Since the labels are generated by a linear classifier, it is always possible to find a weight vector that makes the empirical loss zero.
“Since we assumed the labels are generated by a linear classifier, it is always possible to find a weight vector that makes the empirical loss zero: L n ( θ n ) = 0 .”
Quote in the paperSubstantial claim - Findingown data§ To achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions of reasoning problems and algorithmic tasks to embracing the exact learning criterion, which necessitates universal correctness. · p. 3
The paper gives a new lower bound that characterizes the critical number of examples needed by a statistical learner to achieve nontrivial performance on exact learning.
“We give a new lower bound that characterizes the critical number of examples needed by a statistical learner to achieve nontrivial performance on exact learning.”
Quote in the paperSubstantial claim - Findingreasoning§ 3 Naive statistical approaches to exact learning fail · p. 7
The previous result allows deriving a similar lower bound for any specific symmetric learner on any given learning problem.
“As it turns out, the previous result allows us to derive a similar lower bound for any specific symmetric learner on any given learning problem.”
Quote in the paperSubstantial claim - Findingcitation§ 4 Beyond the naive approach · p. 10
For training a maximum-margin classifier over the binary hypercube, no matter the target linear classifier, there exists a dataset of size at most 2d+2 such that the maximum-margin classifier matches the target.
“one can prove that no matter the target linear classifier, there always exist a dataset of size at most 2 d +2 such that the maximum margin classifier matches the target (Proposition B.1 in the appendix).”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Proposition B.1
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Findingown data§ 3 Naive statistical approaches to exact learning fail · p. 9
In the simple h_ge problem, the number of examples needed before exact learning is achieved grows exponentially with m.
“Even in this simple problem, the number of examples needed before exact learning is achieved grows exponentially with m .”
Quote in the paperSubstantial claim - Findingreasoning§ B Proofs · p. 23
For any linear classifier f ∈ F_lin(X) with finite domain X ⊂ R^d, there exists a dataset D with |D| ≤ 2d+2 such that the maximum-margin classifier on D is equal to f.
“Proposition B.1. Suppose that f ∈ F lin ( X ) , a linear classifier with finite domain X ⊂ R d , i.e., f ( x ) = sgn( ⟨ w,x ⟩ ) + b for some w ∈ R d and b ∈ R . Then there exists a dataset D with |D| ≤ 2 d +2 such that the maximum-margin classifier on D is equal to f .”
Quote in the paperSubstantial claim - Findingreasoning§ B Proofs · p. 22
For any distribution ρ over X, with a sample from ρ that has fewer examples than 1/(2 inf_{h,h'∈H, h≠h'} P(h(X)=h'(X))), all learners fail to identify the function used to label the sample for at least one labeling function h*∈H with probability at least 1/4.
“Theorem 3.2 (All learners fail on some task for small samples) . Fix a distribution ρ over X and let X ∼ ρ . With a sample from ρ that has fewer examples than 1 / (2 inf h,h ′ ∈H ,h = h ′ P ( h ( X ) = h ′ ( X ))) , all learners fail to identify the function used to label the sample for at least one of the labeling functions h ∗ ∈ H with probability of at least 1 / 4 .”
Quote in the paperSubstantial claim - Findingcitation§ 3 Naive statistical approaches to exact learning fail · p. 8
Convergence, if it happens at all, can be very slow when neural networks are trained with gradient descent and cross-entropy loss.
“convergence (if it happens at all) can be very slow when neural networks are trained with gradient descent and cross-entropy loss.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Soudry et al. (2018)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Premisenone given§ 1 Introduction · p. 2
Generalization to all novel scenarios is impossible in general when the solution to a problem is only defined through data, as in image or speech recognition.
“While this is clearly impossible to achieve in general (e.g., when the solution to a problem is only defined through data, as in image or speech recognition)”
Quote in the paperNot a substantial claim - Premisecitation§ 1 Introduction · p. 1
Modern AI systems are powered by large language models trained to minimize next-token prediction error against some data.
“This is because these systems are powered by large language models (LLM) trained to minimize next-token prediction error against some data (e.g., OpenAI et al., 2024; Gemini Team et al., 2023; Anthropic, 2023; LLama Team et al., 2024)”
Quote in the paperSubstantial claim0 of 3 sources checked- cites OpenAI et al., 2024
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Gemini Team et al., 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Anthropic, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Premisecitation§ 1 Introduction · p. 1
Frontier AI systems regularly and consistently falter on easily-solvable deductive reasoning tasks.
“Accordingly, frontier AI systems are well-documented to regularly and consistently falter on easily-solvable deductive reasoning tasks.”
Quote in the paperSubstantial claim0 of 3 sources checked- cites Nezhurina et al. (2025)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites McCoy et al. (2024a,b)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Xie et al. (2024)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Premisereasoning§ 2 From statistical to exact learning · p. 6
Only Ω(d log(d/δ)) examples are needed before the expected on-distribution performance becomes better than choosing labels uniformly at random.
“Moreover, the upper bound decreases rapidly as n increases, and only Ω( d log( d/δ )) examples are need before the expected on-distribution performance becomes better than choosing labels uniformly at random.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Zhang, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 7
Even simple learning problems with seemingly ideal conditions can be very hard if the goal is exact identification.
“Hence, even simple learning problems with seemingly ideal conditions can be very hard if the goal is exact identification.”
Quote in the paperSubstantial claim- Rests on an assumption: In applications, the input space has a combinatorial structure similar to {0,1}^d and is subject to the same explosion as in the paper's example.
- Premisereasoning§ 3 Naive statistical approaches to exact learning fail · p. 7
Transformers trained with gradient descent do not have variable symmetry.
“Transformers trained with gradient descent do not have variable symmetry”
Quote in the paperSubstantial claim - Premisecitation§ 3 Naive statistical approaches to exact learning fail · p. 7
Multilayer perceptrons trained with various gradient methods have variable symmetry.
“multilayer perceptrons trained with various gradient methods have variable symmetry (see e.g. Ng (2004)).”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites Ng (2004)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 8
The argument applies to any symmetric learner, not just connectionist methods.
“Firstly, our argument applies to any symmetric learner, not just connectionist methods.”
Quote in the paperSubstantial claim - Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 8
The more symmetries a learner has, the harder exact learning becomes.
“the more symmetries the learner has the harder exact learning will become.”
Quote in the paperSubstantial claim - Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 6
Coverage of the input distribution in terms of having full support over the input domain is far from sufficient for exact learning.
“The example also demonstrates that coverage of the input distribution in terms of having a full support over the input domain is far from sufficient for exact learning.”
Quote in the paperSubstantial claim - Interpretationreasoning§ 2 From statistical to exact learning · p. 5
There is no guarantee that a statistical learner that will do well in the statistical sense will also do well on exact learning.
“However, there is no guarantee that a statistical learner that will do well in the statistical sense will also do well on exact learning (as we also shall see in the next section).”
Quote in the paperSubstantial claim - Interpretationreasoning§ 2 From statistical to exact learning · p. 6
By contrast, in exact learning, a learner with the same information cannot be expected to perform well without seeing almost all possible inputs.
“By contrast, in exact learning, a learner with the same information cannot be expected to perform well without seeing almost all possible inputs .”
Quote in the paperSubstantial claim - Premisereasoning§ 2 From statistical to exact learning · p. 5
Learning to perform well on a well-defined set of deductive reasoning tasks described in some formal language is a problem of learning an algorithm.
“Learning to perform well on a well-defined set of deductive reasoning tasks described in some formal language is a problem of learning an algorithm .”
Quote in the paperNot a substantial claim - Premisereasoning§ 3 Naive statistical approaches to exact learning fail · p. 7
Transformers trained on a binary classification problem have label symmetry.
“but if they are trained on a binary classification problem, they would have label symmetry.”
Quote in the paperSubstantial claim - Interpretationreasoning§ 2 From statistical to exact learning · p. 5
The standard practice of developing algorithms that do well on a fixed set of benchmarks does not guarantee good performance on a new benchmark.
“This is why the standard practice of developing algorithms that do well on a fixed set of benchmarks does not guarantee good performance on a 'new' benchmark.”
Quote in the paperSubstantial claim - Premisenone given§ 1 Introduction · p. 2
Flawless deduction is achievable, as formal systems demonstrate.
“Indeed, on the one hand, flawless deduction is achievable, as formal systems demonstrate.”
Quote in the paperNot a substantial claim - Premisecitation§ 2 From statistical to exact learning · p. 4
For well-behaved losses, concentration of measure shows that with overwhelming probability Lμ(θ)-Ln(θ) is of order O(1/√n) or less for any prespecified θ.
“At least for well-behaved losses, the concentration of measure phenomenon shows that with overwhelming probability L µ ( θ ) -L n ( θ ) is of order O (1 / √ n ) or less for any prespecified θ (Boucheron et al., 2003).”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Boucheron et al., 2003
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Premisenone given§ 3 Naive statistical approaches to exact learning fail · p. 7
Multilayer perceptrons have label symmetry when the last layer weights are initialized from a centrally symmetric distribution.
“They also have label symmetry when the last layer weights are initialized from a distribution that is centrally symmetric.”
Quote in the paperNot a substantial claim - Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 8
The symmetry of a learner can be used to argue that the learner will take some time before finding a specific hypothesis.
“Thus, we see that the symmetry of a learner can be used to argue that the learner will take some time before finding a specific hypothesis.”
Quote in the paperSubstantial claim - Premisecitation§ To achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions of reasoning problems and algorithmic tasks to embracing the exact learning criterion, which necessitates universal correctness. · p. 3
Formal systems require all knowledge to be explicitly encoded, which quickly becomes cumbersome and makes such systems brittle.
“Another advantage of learned natural language systems over formal systems is that formal systems require all knowledge to be explicitly encoded, which quickly becomes very cumbersome and makes such systems brittle (Clark et al., 2021).”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Clark et al., 2021
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Interpretationreasoning§ 1 Introduction · p. 3
This misalignment is at the heart of the documented unpredictability and limitations of current advanced AI systems.
“We contend that this misalignment is at the heart of the documented unpredictability and limitations of current advanced AI systems.”
Quote in the paperNot a substantial claim - Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 8
Multilayer perceptrons trained with gradient descent will fail to learn h_ge unless the sample size is at least 2^{d/2}.
“As such, one gets that these methods will fail on learning the specific hypothesis h ≥ unless the sample size is at least 2 d/ 2 .”
Quote in the paperSubstantial claim - Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 8
h_ge is just one of many hypotheses that are hard to learn with symmetric learners.
“h ≥ is just one of the many hypothesis which are hard to learn with learners with symmetries like the one mentioned.”
Quote in the paperNot a substantial claim - Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 6
Lack of coverage of the input distribution is only one of many reasons that a learner will fail to generalize to unseen examples.
“Yet, this example should remind everyone that lack of coverage of the input distribution (which is almost always what is blamed when learning does not 'succeed') is only one of the many reasons that a learner will fail to generalize to unseen examples.”
Quote in the paperSubstantial claim - Premisecitation§ 2 From statistical to exact learning · p. 6
In linear binary classification, if one cares about finding a classifier with a small probability of error on a new random input, it is sufficient to find a parameter vector that makes the empirical loss the smallest possible.
“Now, if one cares about finding a classifier with a small probability of error on a new random input, as it turns out, it is sufficient to find a parameter vector θ n ∈ R d +1 that makes the empirical loss L n ( · ) the smallest possible.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Zhang, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Premisenone given§ 3 Naive statistical approaches to exact learning fail · p. 7
Transformers have input alphabet symmetry (token space symmetry): they do not treat any input tokens as special.
“Moreover, they also have input alphabet symmetry (or token space symmetry): They do not treat any of the input tokens as special.”
Quote in the paperNot a substantial claim - Interpretationreasoning§ 6 Conclusion · p. 13
The current approach to develop AI systems, heavily reliant on statistical learning, is fundamentally misaligned with the demands of general intelligence.
“We have argued that the current approach to develop AI systems, heavily reliant on the paradigm of statistical learning, is fundamentally misaligned with the demands of general intelligence.”
Quote in the paperNot a substantial claim - Premisecitation§ 3 Naive statistical approaches to exact learning fail · p. 9
Van den Broeck (2023) shows that if the weights of a transformer are initialized to exactly solve a particular logical reasoning problem, training the transformer on instances using next-token prediction can destroy the exactness of the solution.
“Van den Broeck (2023) shows that if the weights of a transformer are initialized to exactly solve a particular logical reasoning problem, training the transformer on instances of the problem using next-token prediction can destroy the exactness of the solution.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Van den Broeck (2023)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Interpretationreasoning§ 4 Beyond the naive approach · p. 10
Calculating a minimal teaching set for a powerful learner may not be feasible.
“calculating a minimal teaching set for a powerful learner may not be feasible.”
Quote in the paperSubstantial claim- Rests on an assumption: The more powerful the learner is, the larger the minimal teaching set will be.
- Interpretationreasoning§ 4 Beyond the naive approach · p. 10
Aiming for increased generality by introducing more symmetries to the learner will delay exact learning.
“aiming for increased generality (introducing more symmetries to the learner) will delay exact learning.”
Quote in the paperSubstantial claim - Premisecitation§ 3 Naive statistical approaches to exact learning fail · p. 8
For linearly separable data, gradient descent weights converge to the maximum-margin linear classifier.
“Soudry et al. (2018) showed that for linearly separable data the weights converge to the maximum-margin linear classifier.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Soudry et al. (2018)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Interpretationreasoning§ 4 Beyond the naive approach · p. 10
Using the teaching set with a multi-layer perceptron instead of the maximum-margin classifier is expected to lead to very poor performance.
“Using the teaching set just mentioned with a multi-layer perceptron instead of the maximum margin classifier is expected to lead to very poor performance.”
Quote in the paperNot a substantial claim - Interpretationreasoning§ 5 Alternative views · p. 12
The symbolic-input approach is limited to problems where inputs are available in, or are easy to transform to, a symbolic form, such as games or formal mathematics.
“Unfortunately, this approach is limited to problems where inputs are available in, or are easy to transform to a symbolic form, such as in games, or formal mathematics.”
Quote in the paperSubstantial claim - Interpretationcitation§ 4 Beyond the naive approach · p. 11
Correctness of a system can be ensured by training a verifier, a binary classifier that decides whether a purported solution is correct.
“By rejecting incorrect solutions, correctness of a system can be ensured by training a verifier, that is, a binary classifier that decides whether a purported solution is correct”
Quote in the paperNot a substantial claim - Interpretationreasoning§ 5 Alternative views · p. 13
Prominent systems using a symbolic backend with a learnt autoformalizer still rely on a learning component that must perform flawlessly to ensure correct solutions.
“at their core, these approaches still rely on a learning component that must perform flawlessly to ensure correct solutions.”
Quote in the paperSubstantial claim - Interpretationcitation§ 3 Naive statistical approaches to exact learning fail · p. 9
The bias of a learning method coming from gradient descent and cross-entropy loss negatively interferes with the success of exact learning.
“Note that in this example we see that the bias of a learning method (coming from gradient descent and the cross-entropy loss) negatively interferes with the success of exact learning.”
Quote in the paperSubstantial claim - Interpretationreasoning§ 5 Alternative views · p. 12
Verifying that the learner has obtained the exact solution is a difficult problem by itself, especially for non-trivial models such as neural networks.
“Verifying that the learner has obtained the exact solution is a difficult problem by itself, especially if we consider non-trivial models such as neural networks.”
Quote in the paperSubstantial claim - Interpretationreasoning§ 4 Beyond the naive approach · p. 10
The dependence of the teaching set on the target function and the learner is absolutely essential.
“The dependence of the teaching set on the target function and the learner is absolutely essential.”
Quote in the paperSubstantial claim
- Classified as probably not a substantial claim. 33
- May combine two claims. 24
Probably not a substantial claim: may not pass S3 (load-bearing).
Premisecitation§ 3 Naive statistical approaches to exact learning fail · p. 8Symmetries of learners have been used in the past to construct similar lower bounds in the statistical setting.
“Unsurprisingly, symmetries of learners have been used in the past to construct similar lower bounds in the statistical setting (e.g., Malach and Shalev-Shwartz, 2021; Abbe and Boix-Adserà, 2022; Abbe et al., 2022)”
Quote in the paperNot a substantial claim1 of 3 sources checked- cites Malach and Shalev-Shwartz, 2021
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Abbe and Boix-Adserà, 2022 source
- cites Abbe et al., 2022
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).
Premisecitation§ 4 Beyond the naive approach · p. 11Wang et al. (2025) proved and empirically demonstrated the benefit of training with a good mixture of problems where the number of functions to be composed was appropriately controlled.
“Wang et al. (2025) who, in the context of learning to compose functions, proved and also empirically demonstrated the benefit of training with a 'good mixture' of problems where the number of functions to be composed was appropriately controlled.”
Quote in the paperNot a substantial claim1 of 1 sources checked- cites Wang et al. (2025) source
Classified as probably not a substantial claim. May combine two claims.
Premisecitation§ 5 Alternative views · p. 13Lin et al. (2025) reports an on-distribution correctness of autoformalization of 76% and an off-distribution correctness of 46%.
“Lin et al. (2025) reports an on-distribution correctness of autoformalization of 76% and an off-distribution correctness of 46% (cf. Table 7).”
Quote in the paperSubstantial claim1 of 1 sources checked- cites Lin et al. (2025) source
Appendix A.2 (page unavailable) describes the formalization quality tests and refers to Table 7, but the retrieved passages do not contain that table’s statistics. Searches for 76%, 46%, and on- versus off-distribution correctness found no passage reporting the claimed figures. (LLM, conf=0.72)
Experimental — accuracy not yet measured
May combine two claims.
Findingreasoning§ 3 Naive statistical approaches to exact learning fail · p. 6From Equation (2) it follows that O(d^2) samples are sufficient to bring the average loss below 1/d with high probability, while Proposition 3.1 shows that any learner that exactly identifies the correct labeling hypothesis with probability at least 1/2 needs to see Ω(2^d) examples, essentially all possible inputs.
“For example, from Equation (2) it follows that ˜ O ( d 2 ) samples are sufficient to bring the average loss below 1 /d with high probability, while the proposition shows that any learner that exactly identifies the correct labeling hypothesis with probability at least 1 / 2 needs to see Ω(2 d ) examples, which is essentially all of the possible inputs.”
Quote in the paperSubstantial claimMay combine two claims.
Findingown data§ To achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions of reasoning problems and algorithmic tasks to embracing the exact learning criterion, which necessitates universal correctness. · p. 3Even for simple problems like finding the coefficients of a linear classifier over a binary hypercube, statistical learners will pick up statistical shortcuts and fail to acquire the target rule, unless the learner and the distribution are carefully tailored to the task or an exorbitant number of training examples are used.
“To illustrate how significant this mismatch is, we prove that even for simple problems like finding the coefficients of a linear classifier over a binary hypercube, statistical learners will pick up 'statistical shortcuts' and fail to acquire the target rule, unless the learner and the distribution is carefully tailored to the task or an exorbitant number of training examples are used.”
Quote in the paperSubstantial claim- Rests on an assumption: In applications, the input space has a combinatorial structure similar to {0,1}^d and is subject to the same explosion as in the paper's example.
Probably not a substantial claim: may not pass S3 (load-bearing).
Findingcitation§ 3 Naive statistical approaches to exact learning fail · p. 7There is an elementary upper bound that matches the lower bound up to an O(log|H|) factor.
“Note that there is an elementary upper bound that matches the lower bound up to an O (log |H| ) factor (Shalev-Shwartz and Ben-David, 2014).”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites Shalev-Shwartz and Ben-David, 2014 source
May combine two claims.
Findingown data§ 4 Beyond the naive approach · p. 11Both in-distribution and out-of-distribution performance is much better, near-perfect, with reasoning traces, though exact learning is still not achieved.
“We find that both in-distribution and out-of-distribution performance is much better (near-perfect) with reasoning, though exact learning is still not achieved (see Figure 3).”
Quote in the paperSubstantial claimMay combine two claims.
Findingcitation§ 3 Naive statistical approaches to exact learning fail · p. 8Upper bounds by Soudry et al. suggest convergence might be rather slow, which is confirmed experimentally in Figure 1.
“The upper bounds provided by Soudry et al. (2018) suggest the convergence might be rather slow, which is confirmed experimentally (Figure 1)”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Soudry et al. (2018)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
May combine two claims.
Premisecitation§ 1 Introduction · p. 2Bidirectional transformers fail to learn to solve simple reasoning problems even though they have the representation capacity, and their performance drops to chance level on an alternative distribution.
“Another work, that is particularly relevant for us, is due to Zhang et al. (2023a) who demonstrates that (bidirectional) transformers fail to learn to solve simple reasoning problems even though they do have the representation capacity. In particular, the authors of this latter work observe that for various non-adversarially chosen distributions, even if the trained models perform perfectly on new”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Zhang et al. (2023a)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
May combine two claims.
Premisecitation§ 1 Introduction · p. 1The statistical approach guarantees good results only on average and only over distributions close to that of the training data, that is, only under small covariate shift.
“the statistical approach guarantees good results only on average and only over the distributions close to that of the training data, that is, only under 'small covariate shift' (Quiñonero-Candela et al., 2022; Ben-David et al., 2010).”
Quote in the paperSubstantial claim0 of 2 sources checked- cites Quiñonero-Candela et al., 2022
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Ben-David et al., 2010
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
May combine two claims.
Premisecitation§ 1 Introduction · p. 2Transformers learn statistical shortcuts to finite-state semi-automata, which generalize near-perfectly in-distribution but lack out-of-distribution robustness.
“While studying their capabilities to learn finite-state semi-automata, Liu et al. (2023) find that transformers learn 'statistical shortcuts' to them, which 'generalize near-perfectly in-distribution [..] {but} lack out-of-distribution robustness [..].'”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Liu et al. (2023)
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Probably not a substantial claim: may not pass S4 (based).
Interpretationreasoning§ 1 Introduction · p. 2The extensive work documenting and addressing failures on off-distribution data indicates that developers expect their systems to generalize to new, unseen data regardless of its origin.
“The extensive work devoted to documenting and addressing the failures of these AI systems on 'offdistribution' data clearly indicates that developers expect their systems to be able to generalize to new, unseen data regardless of its origin.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S2 (checkable), S4 (based). May combine two claims.
Premisenone given§ 1 Introduction · p. 2In reasoning, the rules are clear and for well-formed inputs the set of correct responses is well-defined.
“In reasoning, the rules are clear and, as such, for well-formed inputs the set of correct responses is well-defined.”
Quote in the paperNot a substantial claimMay combine two claims.
Premisecitation§ 2 From statistical to exact learning · p. 4In reality, and in particular in training LLMs, system designers try to collect data that appears to have good coverage, minimize empirical loss, and test on an ever-expanding set of benchmarks.
“In reality, and in particular in the training of AI systems based on LLMs, system designers try hard to collect data that appears to have 'good coverage'. Then they minimize the empirical loss and subsequently spend considerable effort testing the system on an ever-expanding set of benchmarks; for example, the reports accompanying the release of each new LLM always contain performance report on a”
Quote in the paperSubstantial claim0 of 3 sources checked- cites OpenAI et al., 2024
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Gemini Team et al., 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Anthropic, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Classified as probably not a substantial claim.
Interpretationnone given§ To achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions of reasoning problems and algorithmic tasks to embracing the exact learning criterion, which necessitates universal correctness. · p. 3These results apply to neural networks like transformers when trained with gradient methods.
“Importantly, these results apply to neural networks like transformers when trained with gradient methods.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S2 (checkable). May combine two claims.
Interpretationreasoning§ 2 From statistical to exact learning · p. 5Since algorithms are meant to be general, distributions reflecting their deployment are not necessarily available, in which case it is natural to require that the algorithm is always correct, leading to the exact learning criterion.
“Since algorithms are meant to be general, such distributions are not (necessarily) available, in which case it is natural to require that the algorithm is always correct , leading to the exact learning criterion.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S2 (checkable), S4 (based).
Interpretationreasoning§ 1 Introduction · p. 3The widespread adoption of statistical learning paradigms in AI systems, which optimize for performance against distributions rather than guaranteeing universal correctness, is fundamentally misaligned with the demands of exactness.
“As explained above, we argue that the widespread adoption of statistical learning paradigms in AI systems, which optimize for performance against distributions rather than guaranteeing universal correctness, is fundamentally misaligned with the demands of exactness.”
Quote in the paperNot a substantial claim- Rests on an assumption: Deductive reasoning is a fundamental and indisputably desirable aspect of general intelligence.
Probably not a substantial claim: may not pass S2 (checkable), S4 (based). May combine two claims.
Interpretationreasoning§ To achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions of reasoning problems and algorithmic tasks to embracing the exact learning criterion, which necessitates universal correctness. · p. 3Because natural language is highly variable, the best chance of achieving useful systems that interact with the real world is through learning systems that can capture its semantics, including differences in phrasing.
“Since natural language is highly variable, our best chance of achieving this is through learning systems that can capture its semantics, including differences in phrasing.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S4 (based). May combine two claims.
Interpretationreasoning§ 2 From statistical to exact learning · p. 4The explanation for failure is that the model cannot be expected to generalize to parts of the input space not covered by the training distribution, and also because the loss functions used in training and test might be significantly different.
“The explanation for the failure is that the model cannot be expected to generalize to parts of the input space not 'covered' by the training distribution, and also because the loss functions used in training and test might be significantly different.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S4 (based).
Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 8A similar failure result applies to transformers.
“A similar result applies to transformers”
Quote in the paperNot a substantial claimClassified as probably not a substantial claim.
Premisereasoning§ 2 From statistical to exact learning · p. 5The most celebrated result of statistical learning is that learning is largely insensitive to the distribution of inputs.
“The most celebrated result of statistical learning is that learning is largely insensitive to the distribution of inputs.”
Quote in the paperSubstantial claimClassified as probably not a substantial claim.
Premisecitation§ 2 From statistical to exact learning · p. 4The fundamental principle in statistical learning is that in great generality it suffices to approximately minimize the empirical loss.
“The fundamental principle in statistical learning is that in great generality it suffices to approximately minimize the empirical loss, which is L n ( θ ) = 1 n ∑ n i =1 ℓ ( Z i , θ ) .”
Quote in the paperSubstantial claim0 of 3 sources checked- cites Boucheron et al., 2003
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Shalev-Shwartz and Ben-David, 2014 source
- cites Zhang, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
May combine two claims.
Premisecitation§ 2 From statistical to exact learning · p. 6The VC dimension of the set of linear classifiers over X is O(d), and classical learning theory shows that for any n≥1 and δ∈(0,1), with probability at least 1-δ, the expected loss is bounded as given.
“The so-called VC dimension of the set F lin ( X ) is known to be O ( d ) and thus classical learning theory (Zhang, 2023, Thm 4.17, Prop 4.18) shows that for any n ≥ 1 and δ ∈ (0 , 1) , with probability at least 1 -δ ,”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites Zhang, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Probably not a substantial claim: may not pass S2 (checkable). May combine two claims.
Interpretationreasoning§ 2 From statistical to exact learning · p. 4The developer of a general purpose system is forced to consider all possible input distributions, while keeping the conditional distribution of the labels, μY|X, fixed.
“As such, the developer is forced to consider all possible input distributions , while keeping the conditional distribution of the labels, µ Y | X , fixed.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S4 (based).
Interpretationnone given§ 3 Naive statistical approaches to exact learning fail · p. 8Methods specialized to exact learning can avoid slow learning even if neural networks are involved.
“Secondly, as we will discuss later, methods that are specialized to exact learning can avoid slow learning even if neural networks are involved.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S2 (checkable), S4 (based).
Interpretationreasoning§ 2 From statistical to exact learning · p. 4The iterative process of training models and adding new training data to fill gaps in test performance is a symptom of the mismatch between the statistical approach to machine learning and the true underlying hidden goals of the developers of these systems, especially those that have a general purpose.
“We claim that the above iterative process of training models and adding new training data which tries to fill the gaps in the test performance is a symptom of the mismatch between the statistical approach to machine learning and the true underlying hidden goals of the developers of these systems, especially those that have a general purpose.”
Quote in the paperNot a substantial claimMay combine two claims.
Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 7On some problems, statistical shortcuts are unavoidable and thus it is not the fault of a particular learner that they learn a shortcut.
“Moreoever, on some problems, the shortcuts are unavoidable and thus it is not the fault of a particular learner that they learn a shortcut!”
Quote in the paperSubstantial claimClassified as probably not a substantial claim.
Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 6Proposition 3.1 illustrates the separation between the hardness of exact learning and statistical learning.
“This result illustrates the separation between the hardness of exact learning and statistical learning.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S4 (based).
Premisenone given§ 2 From statistical to exact learning · p. 4The statistical learning principle works well when the data arising in deployment has the same distribution as the training data.
“The statistical learning principle works well when the data arising in deployment has the same distribution as the training data.”
Quote in the paperNot a substantial claimMay combine two claims.
Interpretationown data§ To achieve reliable deductive reasoning in learning-based AI systems, researchers must fundamentally shift from optimizing for statistical performance against distributions of reasoning problems and algorithmic tasks to embracing the exact learning criterion, which necessitates universal correctness. · p. 3Good statistical performance does not imply good performance in exact learning, and hence statistical learners cannot be expected to do well on exact learning tasks in general.
“The most important message is that good statistical performance does not imply good performance in exact learning, and hence we cannot expect statistical learners to do well on exact learning tasks in general.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Interpretationcitation§ 3 Naive statistical approaches to exact learning fail · p. 8The argument that learner symmetry slows exact learning is a precise mathematical version of Fodor and Pylyshyn (1988)'s main argument.
“Our argument that learner symmetry slows exact learning can be seen as a precise, mathematical version of one of Fodor and Pylyshyn (1988)'s main argument”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites Fodor and Pylyshyn (1988) source
Probably not a substantial claim: may not pass S2 (checkable). May combine two claims.
Interpretationreasoning§ 1 Introduction · p. 2Achieving perfection in deduction ensures safety and reliability and relieves designers from deciding which failures are acceptable.
“Achieving this perfection ensures safety and reliability, which has the added benefit of relieving designers from the challenging task of deciding which failures are acceptable-a problem with no perfect answers.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S4 (based).
Premisenone given§ 1 Introduction · p. 3Exact learning is not an explicit goal in statistical learning.
“As noted beforehand, exactly learning is not an explicit goal in statistical learning.”
Quote in the paperNot a substantial claimMay combine two claims.
Premisecitation§ 2 From statistical to exact learning · p. 6All these conclusions hold regardless of the size of X, the choice of the input distribution, and the classifier generating the labels.
“All this holds regardless of the size of X . In particular, there is no requirement to see all elements of X during training. Furthermore, all these conclusions hold regardless of the choice of the input distribution and the classifier generating the labels.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Zhang, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Probably not a substantial claim: may not pass S2 (checkable), S4 (based).
Premisenone given§ 2 From statistical to exact learning · p. 4Having a general purpose system means that even if there were some distribution underlying the future inputs to be used with the system, this distribution ρ is not available to the developer.
“Indeed, having a general purpose system means that even if there were some distribution underlying the future inputs to be used with the system, this distribution ρ is not available to the developer.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing), S4 (based).
Interpretationnone given§ A Further Related Works · p. 22Exact learning would prevent adversarial examples.
“The main connection between our work and this areas is that exact learning would prevent adversarial examples.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S2 (checkable), S4 (based).
Interpretationnone given§ 4 Beyond the naive approach · p. 11A gain is expected if learning the elementary reasoning steps is a lower-complexity learning problem.
“A gain is expected if learning the elementary reasoning steps is a lower-complexity learning problem.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing), S4 (based).
Interpretationnone given§ 5 Alternative views · p. 12Language ambiguity can be removed by instructing models to produce output in a particular format.
“language ambiguity can be removed by instructing models to produce output in a particular format.”
Quote in the paperNot a substantial claimMay combine two claims.
Interpretationown data§ A Further Related Works · p. 22For a benign distribution such as the uniform distribution over a discrete domain, exponentially many examples may be needed for exact learning, which gives a hard limit on OOD generalization abilities.
“Our result that shows that for a benign distribution, such as the uniform distribution over a discrete domain, exponentially many examples may be needed for exact learning also gives a hard limit on OOD generalization abilities.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.
Interpretationnone given§ 5 Alternative views · p. 12When learning is used with symbolic inputs to speed up reasoning, the correctness of the whole system is guaranteed; failure of learning may slow down the system but will not make it produce incorrect answers.
“When learning is used this way, the correctness of the whole system is guaranteed - failure of learning may slow down the system, but it will not make it produce incorrect answers.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Premisecitation§ 4 Beyond the naive approach · p. 10Removing some symmetries by forcing the predictor to be symmetric has been shown, at least in the statistical setting, to reduce sample complexity.
“which, at least in the statistical setting, has been shown to reduce sample complexity (Bietti et al., 2021; Tahmasebi and Jegelka, 2023).”
Quote in the paperNot a substantial claim0 of 2 sources checked- cites Bietti et al., 2021
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Tahmasebi and Jegelka, 2023 source
Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing), S4 (based).
Interpretationnone given§ 5 Alternative views · p. 12The verification problem appears especially difficult in the case of natural language reasoning, where there are many different ways to express the same statement.
“The verification problem appears especially difficult in the case of natural language reasoning, where there are many different ways to express the same statement.”
Quote in the paperNot a substantial claimMay combine two claims.
Interpretationnone given§ A Further Related Works · p. 22Our framework demands the ultimate extreme form of OOD generalization: learning exactly is equivalent to perfect generalization regardless of the target distribution.
“In a way, our framework demands the ultimate extreme form of OOD generalization: learning exactly is equivalent to perfect generalization regardless of the target distribution.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Study design and conductnone given§ C Experiment details · p. 24To ensure balanced labels, the query was selected uniformly at random from the true predicates with probability 0.5.
“To ensure balanced labels, the query was selected uniformly at random from the true predicates with probability 0.5.”
Quote in the paperNot a substantial claimMay combine two claims.
Premisecitation§ 4 Beyond the naive approach · p. 11Zhang et al. (2023a) train a BERT model from scratch on such data without reasoning and show that training on RP to near-perfect accuracy does not generalize to LP and vice versa.
“Zhang et al. (2023a) train a BERT model from scratch on such data (without reasoning) and show that training on RP to near-perfect accuracy does not generalize to LP and vice versa.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites Zhang et al. (2023a)
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).
Interpretationreasoning§ 5 Alternative views · p. 12Even on the simple problem of comparing two m-bit integers, one might need to evaluate the network on all 2^{2m} inputs to verify exactness.
“Even on the simple problem of comparing two m -bit integers discussed earlier, we might need to evaluate the network on all 2 2 m inputs to verify exactness.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S2 (checkable), S4 (based).
Interpretationnone given§ 6 Conclusion · p. 13The misalignment is most acute when AI systems are applied in engineering, mathematics, or science, where flawless formal reasoning is paramount.
“This misalignment is the most acute when the AI systems are applied in engineering, mathematics, or science, where flawless formal reasoning is paramount.”
Quote in the paperNot a substantial claimMay combine two claims.
Interpretationreasoning§ 3 Naive statistical approaches to exact learning fail · p. 9Gradient descent with cross-entropy loss eventually converges to the maximum-margin solution, which for datasets that are not very large or carefully chosen teaching sets does not yield exact learning.
“Gradient descent with this loss eventually converges to the maximum-margin solution, which for datasets that are not either very large or carefully chosen teaching sets does not yield exact learning.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing).
Interpretationreasoning§ 4 Beyond the naive approach · p. 11Training such a verifier may be easier than solving the problem in one step, especially if other system components break up the original problem into small manageable components.
“Training such a verifier may be easier than solving the problem in one-step, especially, if other system components are responsible for breaking up the original problem into small manageable components.”
Quote in the paperNot a substantial claim
The paper relies on this without support.
Deductive reasoning is a fundamental and indisputably desirable aspect of general intelligence.
“Deductive reasoning , the ability to derive new knowledge from existing facts and rules, is a fundamental aspect of intelligence.”
“Sound deductive reasoning-the ability to derive new knowledge from existing facts and rules-is an indisputably desirable aspect of general intelligence.”
The paper relies on this without support.
In applications, the input space has a combinatorial structure similar to {0,1}^d and is subject to the same explosion as in the paper's example.
“In connection to this, we note that we choose the domain { 0 , 1 } d as in the applications we can think of, the input space has a similar combinatorial structure and is subject to the same explosion as what we see here.”
The paper relies on this without support.
The flexibility of natural language forces one to use learning methods that may need to have a lot of symmetries.
“Then the flexibility of natural language forces one to use learning methods that may need to have a lot of symmetries”
The paper relies on this without support.
When an input is sufficiently specific, there is no debate about what the correct solution is.
“when an input is sufficiently specific, there is no debate about what the correct solution is.”
The paper relies on this without support.
The more powerful the learner is, the larger the minimal teaching set will be.
“the more the powerful the learner is, the larger the minimal teaching set will be”
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Proof uses a negative label outside the defined label set
MinorThe paper defines linear classifiers as having labels 0 and 1, but the proof of Proposition B.1 requires a point with label −1. Under the stated definition, that point does not exist, so the proof's construction cannot work as written.
“In linear binary classification the input set X is a subset of a Euclidean space R d and the label set is binary: Y = { 0 , 1 } .”
“Given a dataset D let D δ = { x -x ′ : x, x ′ ∈ D , f ( x ) = 1 , f ( x ′ ) = -1 } .”
Proposition B.1 changes the definition of a linear classifier
MinorThe earlier definition places the bias inside the threshold defining the positive halfspace. Proposition B.1 instead writes the sign of the dot product plus the bias, which generally defines a different function and need not return binary labels.
“For θ = ( w,b ) ∈ R d × R ≡ R d +1 , a linear classifier f θ over X is a binary-valued map that returns 1 for any point x in the halfspace { x : ⟨ w,x ⟩ + b ≥ 0 } ⊂ R d .”
“Proposition B.1. Suppose that f ∈ F lin ( X ) , a linear classifier with finite domain X ⊂ R d , i.e., f ( x ) = sgn( ⟨ w,x ⟩ ) + b for some w ∈ R d and b ∈ R .”
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 48
- Dana Angluin. Learning regular sets from queries and counterexamples. In Proceedings of the fourth annual workshop on Computational learning theory , pages 37-52. ACM, 1987.
- Dana Angluin. Queries and concept learning. Machine learning , 2(4):319-342, 1988.
- Dana Angluin. Queries revisited. Theoretical Computer Science , 313(2):175-194, 2004. Special issue for ALT 2001.
- Anthropic. The Claude 3 model family: Opus, Sonnet, Haiku, 2023. URL https://api.semanticscholar. org/CorpusID:268232499 .
- Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: What is required and can it be learned? In International Conference on Learning Representations , 2019b.
- Shai Ben-David, Tyler Lu, Teresa Luu, and David Pal. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages 129-136, 2010.
- Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under invariance and geometric stability. In NeurIPS . Curran Associates Inc. Red Hook, NY, USA, 2021.
- Róbert Csordás. Systematic generalization in connectionist models . PhD thesis, Università della Svizzera italiana, 2023. URL https://sonar.ch/global/documents/326205 .
- Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In International Conference on Learning Representations , 2019.
- Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, et al. Neural networks and the Chomsky hierarchy. In The Eleventh International Conference on Learning Representations , 2023.
- Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. NeurIPS , 33:13049-13061, 2020.
- Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is a good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations , 2020.
- Richard M Dudley. Uniform central limit theorems , volume 142. Cambridge university press, 2014.
- Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI , 2018.
- Daniel Y Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re. Hungry hungry hippos: Towards language modeling with state space models. In The Eleventh International Conference on Learning Representations , 2022.
- Artur D'avila Garcez, Marco Gori, Luis C Lamb, Luciano Serafini, Michael Spranger, and Son N Tran. Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning. Journal of Applied Logics - IfCoLog Journal of Logics and their Applications , 6(4):611-632, 2019.
- E Mark Gold. Language identification in the limit. Information and Control , 10(5):447-474, 1967.
- Sally A Goldman, Michael J Kearns, and Robert E Schapire. On the complexity of teaching. Journal of Computer and System Sciences , 46(1):20-43, 1993.
- Seungwook Han, Jyothish Pari, Samuel J Gershman, and Pulkit Agrawal. General reasoning requires learning to reason from the get-go. In ICML , 2025.
- Henry A. Kautz. The third AI summer: AAAI Robert S. Engelmore memorial lecture. AI Magazine , 43(1): 105-125, 2022.
- Brenden M Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In International conference on machine learning , pages 2873-2882. PMLR, 2018.
- Tor Lattimore, Csaba Szepesvári, and Gellért Weisz. Learning with good feature representations in bandits and in RL with a generative model. In International conference on machine learning , pages 5662-5670, 2020.
- Joel Z Leibo, Edgar A Dueñez-Guzman, Alexander Vezhnevets, John P Agapiou, Peter Sunehag, Raphael Koster, Jayd Matyas, Charlie Beattie, Igor Mordatch, and Thore Graepel. Scalable evaluation of multi-agent reinforcement learning with melting pot. In ICML , pages 6187-6199, 2021.
- Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages 5315-5333, 2023.
- Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning , 2(4):285-318, 1988.
- Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations (ICLR) , 2023.
- Ji Liu and Xiaojin Zhu. The teaching dimension of linear learners. Journal of Machine Learning Research , 17 (162):1-25, 2016.
- Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B Smith, James M Rehg, and Le Song. Iterative machine teaching. In International Conference on Machine Learning , pages 2149-2158. PMLR, 2017.
- Po-Ling Loh. A theoretical review of modern robust statistics. Annual Review of Statistics and Its Application , 12, 2024.
- Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics , pages 3420-3428. PMLR, 2019.
- Andrew Y Ng. Feature selection, l 1 vs. l 2 regularization, and rotational invariance. In Proceedings of the twenty-first international conference on Machine learning , page 78, 2004.
- Xuezhou Zhang Hrag Gorune Ohannessian, Ayon Sen, Scott Alfeld, and Xiaojin Zhu. Optimal teaching for online perceptrons. In NIPS 2016 workshop on Constructive Machine Learning , 2016.
- Andreas Opedal, Haruki Shirakami, Bernhard Schölkopf, Abulhair Saparov, and Mrinmaya Sachan. MathGAP: Out-of-distribution evaluation on problems with arbitrarily complex proofs. In The Thirteenth International Conference on Learning Representations , 2025.
- Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms . MIT press, 2017.
- Joaquin Quiñonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning . MIT Press, 2022.
- Alessandro Raganato, Yves Scherrer, and Jörg Tiedemann. Fixed encoder self-attention patterns in transformerbased machine translation. In Findings of the Association for Computational Linguistics: EMNLP 2020 , pages 556-568, 2020.
- R. Tyrrell Rockafellar. Convex analysis . Princeton Mathematical Series. Princeton University Press, Princeton, N. J., 1970.
- Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations , 2014.
- J. Uesato, A. Kumar, Cs. Szepesvári, T. Erez, A. Ruderman, K. Anderson, K. Dvijotham, N. Heess, and P. Kohli. Rigorous agent evaluation: An adversarial approach to uncover catastrophic failures. In ICLR , pages 3692-3702, 2019.
- Karthik Valmeekam, Kaya Stechly, Atharva Gundawar, and Subbarao Kambhampati. A systematic evaluation of the planning and scheduling abilities of the reasoning model o1. Transactions on Machine Learning Research , 2025.
- Guy Van den Broeck. AI can learn from data. But can it learn to reason? In MATH-AI: The 3rd Workshop on Mathematical Reasoning and AI , 2023.
- Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International conference on machine learning , pages 5286-5295. PMLR, 2018b.
- Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. TravelPlanner: a benchmark for real-world planning with language agents. In Proceedings of the 41st International Conference on Machine Learning , ICML'24. JMLR.org, 2024.
- Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K Jain. Adversarial attacks and defenses in images, graphs and text: A review. International journal of automation and computing , 17: 151-178, 2020.
- Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems , pages 3391-3401, 2017.
- Tong Zhang. Mathematical analysis of machine learning algorithms . Cambridge University Press, 2023.
- Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In International Conference on Machine Learning , pages 62138-62160. PMLR, 2024.
- Sandra Zilles, Steffen Lange, Robert Holte, Martin Zinkevich, and Nicolo Cesa-Bianchi. Models of cooperative teaching and learning. Journal of Machine Learning Research , 12(2), 2011.
Cited by
Sorted by citations
VeriEquivBench: An Equivalence Score for Ground-Truth-Free Evaluation of Formally Verifiable Code
Zeng, L., Che, F.-D., Huang, X., et al. (2025) · arXiv.org · doi:10.48550/arxiv.2510.06296 · Cited by 9
“While several benchmarks (Ye et al., 2025b; Thakur et al., 2025) target at building a reliable reasoning system by formally ensuring the exact code generation (Gy¨orgy et al., 2025), their progress N atural Language Query Generated Spec”
DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs
Zhang, Y., Kuzborskij, I., Lee, J. D., Leng, C.-L., & Liu, F.-H. (2025) · International Conference on Learning Representations · doi:10.48550/arxiv.2510.19842 · Cited by 6
“1 These operations must be exact , in line with the exact learning requirements in György et al. (2025).”
On Learning Verifiers and Implications to Chain-of-Thought Reasoning
Balcan, M.-F., Blum, A., Li, Z., et al. (2025) · Neural Information Processing Systems · doi:10.52202/085713-5169 · Cited by 5
“This is surprising as verifying a proof is usually believed to be easier than generating it (although formally an open question, for instance determining whether P ̸ = NP ), but the strong “guiding” abilities of our verifiers can be used for generation.”
Exact Learning of Arithmetic with Differentiable Agents
Papazov, H., D'Angelo, F., & Flammarion, N. (2025) · arXiv.org · doi:10.48550/arxiv.2511.22751 · Cited by 1
“The dream of AGI envisions systems capable of exact learning of algorithmic skills – such as searching, sorting, or arithmetic – from a reasonable dataset of examples [39, 9, 17].”
On the Brittleness of LLMs: A Journey around Set Membership
Hergert, L., Berend, G., Szegedy, M., et al. (2025) · arXiv.org · doi:10.48550/arxiv.2511.12728 · Cited by 1
“While LLMs show impressive performance, it is important to understand their various deficiencies as well (McCoy et al., 2024; Cuskley et al., 2024; Passerini et al., 2024; Shojaee et al., 2025; György et al., 2025).”
Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
de Luca, A. B., & Fountoulakis, K. (2026) · arXiv · doi:10.48550/arxiv.2605.22964
“György et al. [14] flag this certification problem as a foundational challenge for the exact-learning setting, illustrating the worst-case certification in a bit comparison task.”
LaCy: What Small Language Models Can and Should Learn is Not Just a Question of Loss
Ujv'ary, S., Béthune, L., Ablin, P., et al. (2026) · Trans. Mach. Learn. Res. · doi:10.48550/arxiv.2602.12005
“György et al. (2025) argue that not all contexts should be answered with a statistical prediction – indeed, some contexts, like facts, require exact predictions to prevent hallucinations.”
- Authors
- György, A., Lattimore, T., Lazić, N., & Szepesvári, C.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2025
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2506.23908
- OpenAlex
- W4416523094
- Semantic Scholar
- bd44d5db77dd40fd13db159f3e140e034ea3e679
- Cited by
- 0
- References
- 0
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence Applications
- Keywords
- deductive reasoning, exact learning, statistical learning, artificial general intelligence, sound reasoning, algorithm design, transformer models
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-23.
Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-23.
Cited sources are checked by gpt-6-sol.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
