Conceptio › Archive › arXiv CS

arXiv CSopen access

Exactness at Inference: A Representational Criterion for Out-of-Distribution Generalization

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Exactness at Inference: A Representational Criterion for Out-of-Distribution Generalization

arXiv:2609.24942v1 [cs.LG] 21 Sep 2026

Filipe Marinho Rocha*1,2

Inês Dutra1,3

Vítor Santos Costa1,2

Luís Paulo Reis4,5

1 Faculdade de Ciências da Universidade do Porto, Porto, Portugal 2 INESC TEC, Campus da FEUP, Porto, Portugal 3 CINTESIS@RISE-Health, Porto, Portugal 4 Faculdade de Engenharia da Universidade do Porto, Rua Dr. Roberto Frias, Porto, Portugal 5 LIACC, FEUP, Porto, Portugal

Abstract A model generalizes outside its training distribution only when it computes a representation structurally equivalent to the underlying data-generating mechanism, rather than a fitted approximation calibrated on data. Structural equivalence is necessary for exactness both in-distribution and out-of-distribution, and extrapolation is governed by this exactness at inference, independent of how the representation is realized, provided the structural equivalence holds. Tensor Logic exemplifies this independence. A zero-temperature tensor contraction achieves strict mathematical equivalence to discrete logic, executing exact deductions in place, in the tensor language itself, with no artefact extracted. At zero temperature the inferred tensors are Boolean and the embeddings are orthonormal, so what remains continuous is the arithmetic rather than the values. The realization still has strict geometric limits. Lacking infinite functional recursion, it is equivalent only to Datalog and not to full Prolog, and while it is exact over closed domains, binding variables to novel entities requires external-memory indirection or explicit rule extraction, since a fixed tensor cannot dynamically expand its index. Evaluated broadly, this criterion of exactness is sharper than it appears in three ways. First, it does not require a discrete representation: a sum-product tensor contraction computing an exact marginal satisfies it across [0, 1], whereas a fitted Neural Network thresholded to output a hard label does not. Second, it does not require an extracted symbolic expression: a continuous relaxation collapsed in place works natively as a rule. Third, it applies strictly to inference time, which allows approximate continuous search during training. Under this criterion, Logic Tensor Networks fail, whereas differentiable ILP and zero-temperature Tensor Logic pass. The two long-known failure modes of deep networks are the continuous and relational expressions of a shortfall in exact representability: piecewise-affine extrapolation divergence and an inability to bind novel entities. For hybrid architectures we introduce an inference-path propagation rule: the output inherits the representational bounds of every fitted estimator along its path. This explains, for example, which coordinate axes fail in equivariant models, and predicts the empirical divide on ARC-AGI, where inductive programs dominate precise compositions and transductive networks dominate perceptual matching. An epistemic corollary follows: only models that commit to a hypothesis within an exact class can certify what their training data leaves underdetermined. We give an example: on a law-derived evaluation partition, an exact model identifies the 56.3% of distant * Corresponding author: [email protected].

queries that are definitively answerable, whereas deep network ensembles exhibit false confidence and distance-based uncertainty metrics rank them backwards. These findings reveal an upper bound on current architectures: the common inductive biases, from hardcoded symmetries to external memory, achieve exactness only because humans manually inject representations structurally equivalent to the generating processes. Overcoming this limitation requires architectures capable of inducing exact representations autonomously, rather than fitting continuous surrogates constrained to representations such as the piecewise-affine maps of Multilayer Perceptrons (MLPs), which compose Neural Networks and are incorrect unless the generating mechanism is itself of that form, and it seldom is. While such surrogates can approximate in-distribution data, their residual errors, even when driven to the arithmetic floor on the training data, diverge out-of-distribution and compound under composition.

Introduction

A model generalizes outside its training distribution only when it computes a representation structurally equivalent to the underlying data-generating mechanism, rather than a fitted approximation calibrated on data. That is the claim this paper defends, and two failures of deep networks, documented for long enough that neither is news, are where it is most visible. A Neural Network built from affine layers and piecewiselinear activations extends the affine map attached to its outermost region indefinitely, so it cannot continue a target that curves [45, 90]. And a Neural Network that represents an entity by a free parameter fitted to that entity has nothing to say about an entity it has never seen, so it cannot apply a universally quantified rule to it [63, 64, 83]. The usual readings of these results are that Neural Networks need more data, more scale, or a better inductive bias. We think the more useful reading is representational and that it applies to both at once: what a model can compute correctly outside its training data is what it can compute exactly, and everything else is an approximation whose validity was established on the training distribution and does not transfer. Exactness is in turn a representational condition rather than a numerical one: an operation is exact when the representation it executes is structurally equivalent to the mechanism that generated the data, and a surrogate calibrated on a region is not rendered exact by being accurate on that region, which is why the condition binds inside the training distribution as well as outside it. This is not a claim about accuracy. A model can be highly accurate and still fail the criterion, and the difference shows up precisely where accuracy was never measured, on Out-of-Distribution (OOD) data. This paper has two purposes: it brings together the account of the two representational limits in a form we could not find presented anywhere, and it states a criterion we believe to be new, and uses it to do work that the existing vocabulary cannot. Sections marked as such are review, and §2 says plainly what belongs to whom. Our own contribution is the criterion, and its consequences. (i) Exactness, not discreteness (§5). What must hold at inference is that the operation executes a representation structurally equivalent to the data-generating mechanism, so that it computes the intended relation rather than approximating it in a region where there is training data to calibrate on. Structural equivalence is necessary for exactness in both regimes and not only beyond the training data, since a surrogate calibrated on a region carries a residual there too and is merely tolerable where it was fitted (§3.2). Discreteness is what exactness reduces to when the intended semantics is classical logic; it is not the criterion itself. A sum-product tensor contraction computing an exact marginal is continuous-valued and exact; a fitted Neural Network thresholded to a hard label is discrete-valued and not exact.

(ii) A sorting that cuts across the usual taxonomy (§5.4). Applied to neuro-symbolic systems the criterion does not separate them by whether they contain a logical component. Logic Tensor Networks (LTN) [5] fail it, ∂ ILP [36], a differentiable form of Inductive Logic Programming (ILP), passes it by extracting a program, and Tensor Logic [32] at zero temperature passes it over a closed domain without extracting anything, since its equations are already equivalent to rules, though an open domain returns it to one of the other two routes (§5.4). What matters is not whether a rule is extracted but whether an approximation using a wrong representation is consulted when the inference is made. (iii) A propagation rule for composed architectures (§5.3). Nearly every Deep Learning (DL) architecture in use contains a Multilayer Perceptron (MLP) somewhere, and the conclusion that all of them inherit its limits is false. A quantity inherits the limits of every fitted component on its inference path, and not of components outside this path. In the case of an equivariant model, this predicts in which axis the model fails, why external-memory indirection buys binding, and why energy conservation and trajectory accuracy come apart in the same Neural Network, and it is answerable by inspecting an architecture before running anything. (iv) One shortfall, two faces (§3, §4). The continuous and relational failures are the same shortfall in exact representability, the class of functions and relations an architecture computes exactly rather than approximates, and they appear in the continuous and discrete domains respectively. Both failures are established results and the unification is the novel contribution; we argue it earns its place by predicting where each failure does not occur, and by scoping each against its known counterexamples. (v) The epistemic corollary (§6). A model can know that it is right only where it is using the correct underlying rule, since abstention is a statement about what the training data determines and determination is relative to a hypothesis class. On a radial chirp, recovering the exact rule fixes 56.3% of the distant queries from the training data alone, while deep network ensembles fail confidently on those same queries and distance-based estimators flag them as the most uncertain, so an estimator added on top abstains exactly where the answer is already determined. Only a system that commits to an exact hypothesis carries a reliable internal signal of its own recovery. (vi) Epistemic dependence (§7). Every known repair supplies exactness by having a person program the structure into the architecture in advance: the group in an equivariant architecture, the indirection in an external-memory controller, the symplectic form in a Hamiltonian Neural Network. Each works only where the designer supplied the right structure. If a model does not induce the structure, someone must inject it, and that is a bound on what scaling alone reaches. We also argue that the epistemic dependence commonly charged against symbolic systems is universal rather than specific to them, and that what distinguishes the paradigms is whether the dependence is visible and measurable. Our representational criterion should not be confused with the representation bottleneck of Deng et al. [31], which names the finding that Neural Networks encode interactions of low and high complexity but not intermediate ones, a claim about interaction order and not about extrapolation. Nor should it be confused with the relational bottleneck of Webb et al. [89], which is a beneficial architectural constraint restricting information flow to relations, close to the opposite of a limitation.

What Is Already Established

Before introducing a new representational criterion for generalization, it is necessary to delineate the boundaries of what the field has already established. This section is strictly a review of prior work. Its purpose is to make the remainder of our argument checkable, since the value of any proposed criterion de3

pends heavily on its being rigorously distinguishable from the several phenomena it resembles and seeks to explain. Currently, the literature recognizes two primary modes of OOD failure in DL architectures. In the continuous domain, models fail to extrapolate because they are trapped by the asymptotic geometry of piecewise-affine maps. In the relational domain, models fail at open-domain logic due to an inability to dynamically bind variables to novel entities. Historically, these have been treated as separate pathologies, diagnosed by different communities using different vocabularies. By assembling the accepted scope, mechanisms and known counterexamples of both limits into a single account, we separate the empirical symptoms, which are widely documented, from our theoretical diagnosis. Laying this foundation ensures that when we introduce our criterion of exactness at inference, it is clear exactly which previous theoretical gaps it bridges, why simply scaling data or parameters does not resolve these limits, and why a unified representational theory is required.

2.1

The continuous limit

This limit is established in the literature. Hein et al. [45] show that ReLU networks produce arbitrarily high-confidence predictions far from the data, because the outermost regions of the partition are unbounded and the affine map on each is prolonged without termination. Xu et al. [90] prove the sharper statement that ReLU MLPs converge to linear functions along any direction from the origin, so they do not extrapolate most nonlinear targets, but that they do learn linear targets given a sufficiently diverse training distribution. That success on linear targets is not a coincidence of optimization. They learn such targets because the piecewise-affine representation native to an MLP, formalized in §3.1, is structurally equivalent to a linear generating mechanism. This condition is important, and we return to it as the positive control of §3.5. The partition itself is characterized by Montúfar et al. [67]. Two remarks on the scope of these results are needed, because both are often overstated. First, Xu et al. [90] argue via the neural tangent kernel, which describes what gradient descent converges to, whereas the polytope picture describes what the architecture can represent. The two agree here, but they are different claims, and only the second is what our criterion needs. Second, the theorem is about ReLU. Extending it to the smooth activations used in practice is not automatic, and §3.4 reports a case where the intuition drawn from a single unit gives the wrong answer for the Neural Network: a GELU unit is asymptotically linear on one tail and asymptotically zero on the other, which suggests that a GELU network should diverge on one side and flatten on the other, and the measurement shows that it diverges on both (Figure 3).

2.2

The relational limit

Also established in the literature, and older. McCarthy [65] named the phenomenon propositional fixation. Fodor and Pylyshyn [37] gave the systematicity argument that the modern versions instantiate. Marcus [63] showed that Neural Networks whose representation of an item is a free parameter cannot extend a universally quantified mapping to items outside the training space, and Marcus [64] develops the argument at book length. Teru et al. [83] state the modern embedding version plainly: methods that learn latent representations of entities “do not explicitly capture the compositional logical rules” and “are limited to the transductive setting, where the full set of entities must be known during training.” Greff et al. [43] give the general form as a binding problem. Barceló et al. [6] supply the precise expressiveness result for GNNs, which is that they capture a fragment of First-Order Logic (FOL) with two variables and counting, given a readout, more than propositional and less than first-order. Two constructive results bound the claim from the other side. Smolensky [81] showed that connectionist variable binding is constructible in principle via tensor products, and Webb et al. [88] built a Neural 4

Network that binds and generalizes to novel entities. §4.5 takes both seriously. For Large Language Models (LLMs) the pattern is documented empirically. Mirzadeh et al. [66] conclude that models “cannot perform genuine logical reasoning” and instead “replicate reasoning steps from their training data,” and Dziri et al. [34] report the corresponding compositional collapse.

2.3

And what is not established

Three things, all of which our criterion supplies. The literature does not offer a criterion for when a hybrid system inherits the limitation. That a system contains a logical component says nothing; the sorting in §5.4 shows that systems containing a full firstorder syntax fail while systems containing no separately extracted artefact pass. The nearest antecedent is Ahmed et al. [2], who observe that loss-based neuro-symbolic methods “cannot guarantee that the predictions will be consistent at test time” and construct a layer that guarantees it instead. That is our distinction, made for constraint satisfaction, and we generalize it. The literature does not distinguish exactness from discreteness. This is the crux, and getting it wrong in either direction misclassifies real systems, as §5.1 shows. Delétang et al. [30] come close from the empirical side, showing across 20,910 models that architecture class forecasts OOD generalization and that “even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity”. Kim [50] comes close from the analytic side, deriving both the continuous approximation limit and the difficulty of universal quantification over unbounded domains from the assumptions of the Universal Approximation Theorem (UAT). We regard our contribution as the criterion, not just the observation that the two failures meet.

The Continuous Face

3.1

Neural Networks as piecewise-affine partitions

A feedforward Neural Network consists of affine transformations interspersed with nonlinear activations. When those activations are piecewise linear, or when smooth activations are analysed at their local linear limits, the Neural Network as a whole, regardless of depth or width, partitions the input space into a large number of convex regions [67]. Within a single region Ωi the Neural Network applies one affine map, f (x) = Wi x + bi

for

x ∈ Ωi ,

(1)

with Wi and bi the effective weight matrix and bias for that region. Every claim in this section follows from that fact and from where the regions are placed.

3.2

Inside the data: what more data buys, and what it does not

Within the training domain the Neural Network minimizes empirical risk by packing linear regions densely where the target bends. This tightly woven polygonal chain makes the approximation look smooth and locally accurate. Accurate is not exact, and we state the gap precisely, because the in-distribution part of the criterion lives in it. Between two adjacent breakpoints the Neural Network is affine while the target curves, so on an interval of width h the residual against a twice-differentiable target is of order h2 max | f ′′ |/8 and vanishes only where f ′′ = 0. Interpolating the training points exactly does not remove it. It pins the chain near the 5

sample points and leaves the chords between them, in the way that a polygon meets a circle at a few points and misses it everywhere else, and no number of corners makes the polygon a circle. Figure 1 measures this on trained Neural Networks. A Neural Network given the angle of a point on the unit circle returns a twelve-cornered polygon whose radius is wrong by up to 0.08, and a Neural Network trained on samples of x2 carries a residual that is zero only at isolated crossings and curved between them. The same figure separates the floor from what training reaches: for a map of n equal pieces the residual cannot fall below f ′′ h2 /16, and a map through every sample gives f ′′ h2 /8, twice that. The factor of two is the Chebyshev equioscillation theorem in its simplest instance, since the best affine approximant on a subinterval is the chord displaced by half its maximum deviation (§A). The trained Neural Networks lie above the first at every width, by between 1.3 and 14.9 times, and above the second in twenty-three of twenty-four runs. The architecture sets a floor and the optimizer does not reach it. The residual is therefore non-vanishing on the whole continuous support rather than only outside the data, and what a dense training distribution buys is that it stays small enough to disappear into the aggregate error. Two later arguments rest on this. The same residual is what diverges once the input leaves the region where the spacing was made small, the subject of the next two subsections, and what compounds when fitted modules are composed (§5.3). Accurate is not exact. A piecewise-affine map is wrong everywhere between the samples, and a trained one is wrong by more than the best such map. (b) trained on the samples, wrong between them maximum residual 0.270

ReLU network

f(x)

circle

0.6

true f(x) = x2 ReLU network training samples

15.0 12.5 10.0 7.5 5.0 2.5 0.0

0.4 0.2 0.0

residual maximum residual

(a) a trained network tracing a circle 12 corners, radius off by up to 0.08

100 10 1

0.2

10 2

0.4

10 3

through the samples, f 00h 2/8 best possible, f 00h 2/16 trained networks, 3 seeds

100

101

affine pieces actually used

Figure 1: Accurate is not exact, measured. (a) A ReLU network with one hidden layer of twelve units, trained to trace the unit circle from the angle of a point on it: the output is a polygon of twelve corners whose radius is wrong by up to 0.08, and whose corners do not lie on the circle, the map being fitted rather than inscribed. (b) A Neural Network of ten units trained on samples of f (x) = x2 over [−1, 4]; the residual, on the right axis, is zero only at isolated crossings and curved everywhere between them, reaching 0.270. (c) Maximum residual against the number of affine pieces the trained Neural Network actually uses, three seeds at each of eight widths, against two analytic curves: the error of the piecewise-affine map through the samples, f ′′ h2 /8, and the error of the best piecewise-affine map of the same number of pieces, f ′′ h2 /16, which is the chord bound halved by the Chebyshev equioscillation theorem. Every trained Neural Network lies above the second, which is the floor its architecture imposes, and all but one above the first. Refining the partition lowers the floor as h2 and never to zero. This geometry is a sufficient account of why such models are data-hungry, and it needs no appeal to optimization or to scale. Lacking any deductive mechanism, the Neural Network can raise fidelity only by placing boundaries where the target actually curves. In high dimensions the volume to be covered grows exponentially, so the number of examples required to position those boundaries grows with it, which is the curse of dimensionality [7] in its approximation-theoretic form. √ The count follows from the bound above. Driving the residual below ε requires a cell of width of order ε along every axis, so covering a d-dimensional domain takes on the order of ε −d/2 affine pieces, and matching upper and lower complexity 6

bounds of this form are established for ReLU networks by Yarotsky [91]. Where data is sparse the regions stay large and rigid, drawing straight lines across curved space. It also separates two things that are easily conflated, capacity and placement, and the separation is a controlled dissociation. Figure 2 fits f (x) = x2 with one-hidden-layer ReLU networks of fixed width from an increasing number of evenly spaced points, and marks the breakpoints the trained Neural Network actually uses, meaning those whose slope change exceeds 0.05 against a true slope ranging over [−6, 6]. Across N = 5, 10, 25, 150 the usable count runs 10, 10, 11, 12 while the error falls from 0.399 to 0.052, a factor of about eight. The number available is fixed by the architecture at twelve, since each hidden unit contributes at most one, and it does not grow when more data arrives. What data buys is knowing where to put them. The rightmost panel is at the architectural ceiling, so the eightfold improvement over the leftmost cannot have been bought with additional pieces; two extra usable breakpoints accompany it, and the rest is placement.

AA ReLU network network cannot cannot bend. bend. It It can can only only place place breakpoints breakpoints (vertical (vertical lines) lines) and and run run straight straight between between them, and and it it needs need A ReLU network cannot bend. ItReLU can only place breakpoints (vertical lines) and run straight between them, and it them, needs data to know where to put them. N= N 5, = 5,1010 effective effective breakpoints breakpoints RMSE RMSE to to truth truth = 0.399 = 0.399

N= N 10, = 10,1010 effective effective breakpoints breakpoints RMSE RMSE to to truth truth = 0.259 = 0.259

N= N 25, = 25,1111 effective effective breakpoints breakpoints RMSE RMSE to to truth truth = 0.080 = 0.080

2 2 true true f(x)f(x) = x= x

ReLU ReLU network network training training data data

f(x) f(x)

66 44 22 00

nly only place place breakpoints breakpoints (vertical (vertical lines) lines) and and run run straight straight between between them, and it 1 it needs needs to know know where where to put put them. them. −3 −3 −2−2 −1−1them, 0 0and 1 2 data 2 data 3to 3 −3 −3 −2 −2 to−1 −1 00 xx N= N 10, = 10,1010 effective effective breakpoints breakpoints RMSE RMSE to to truth truth = 0.259 = 0.259

−2−2

−1−1

N= N 25, = 25,1111 effective effective breakpoints breakpoints RMSE RMSE to to truth truth = 0.080 = 0.080 2 2 true true f(x)f(x) = x= x

2 2 true true f(x)f(x) = x= x

ReLU ReLU network network training training data data

ReLU ReLU network network training training data data (thinned) (thinned)

33 −3−3

−2−2

−1−1

00 xx

33 −3−3

−2−2

−1−1

N= N 150, = 150,1212 effective effective breakpoints breakpoints RMSE RMSE to to truth truth = 0.052 = 0.052

2 2 true true f(x)f(x) = x= x

00 xx

33 −3−3

−2−2

−1−1

00 xx

Figure 2: What more data buys inside the training region. One-hidden-layer ReLU networks of fixed width fit f (x) = x2 on [−3, 3] from N evenly spaced points; vertical lines mark the breakpoints the trained Neural Network actually uses. The count barely changes across the panels while the error falls by almost an order of magnitude, because the data is not buying additional breakpoints, which the architecture fixes, but better placement of the ones it already has. This matters twice for what follows. It is the mechanism behind the observability condition of §3.5: data is what pins down which member of the representable class the Neural Network has settled on, and it does so by positioning pieces rather than by supplying new ones. And it is a small, controlled instance of the scaling argument of §7: enlarging the fitted part of a system changes the quality of an approximation 7

00 xx

and leaves the class being approximated within exactly where it was.

3.3

Extrapolation as asymptotic extension

The structural vulnerability of the partition appears at the boundary of the training manifold. There are no data points outside that domain to prompt the formation of further bounding hyperplanes, so the outermost regions Ωext extend outward indefinitely [45]. An OOD input falls into one of these unbounded regions, and the Neural Network applies the terminal state that defined the boundary of the data, whether an affine projection or a saturated constant, projecting it endlessly into space the data never constrained. This is the mechanism behind confident and badly wrong predictions off-distribution [90], and we call it piecewiseaffine extrapolation divergence, both to name the continuous face of the shortfall for the propagation rule of §5.3 and to separate it from the regime of §3.6, where a bounded representation converges toward a constant instead. We state the point in the form that matters for this paper. The Neural Network does not fail to answer. It answers with the same fluency it shows on familiar input, because the operation it performs off-distribution is the same operation it performs on it.

3.4

Case study: the quadratic, across three activations

Consider f (x) = x2 on x ∈ [−3, 3], evaluated on [−6, 6]. Because the neural network resolves into a continuous piecewise-linear function, its regions are defined by first-degree polynomials, so an MLP has no intrinsic mechanism for quadratic growth, for higher-degree polynomials, or for transcendental functions such as sin(·) and cos(·). This is a representational limitation of standard Neural Networks, and it holds before any question of optimization or scale arises. It can join short affine segments into a convincing local approximation inside a dense data manifold, and outside it the approximation is governed entirely by the asymptotic behaviour of the activation rather than by the shape of f . Figure 3 shows the three activations at the level of a single unit, and Figure 4 shows three trained Neural Networks. The three activations fail differently, and the difference is set by what each unit does far from the origin. ReLU extends the terminal slope, since a unit is exactly affine beyond its own breakpoint (Figure 3a). If the tangent near x = 3 has slope about 6, the prediction beyond it is approximately 6x − 9, growing linearly where the true function accelerates, so the error grows without bound. Sigmoid fails differently, and more gently, because the unit is bounded on both tails (Figure 3a). Preactivations saturate one by one as the input leaves the training range, and the output bends toward a plateau instead of continuing to accelerate, so the error is bounded rather than unbounded. The plateau does not sit at the boundary value f (±3) = 9; it is set by the sum, over the hidden units still active at that extreme, of their output-layer contributions. In the Neural Network measured here the two tails level off near 20 and 23 rather than at 9, and they need not agree with each other, since a different subset of units survives at each extreme. GELU is the interesting case, and the one where the natural inference is wrong. Modern Transformers rely on xΦ(x), with Φ the standard normal CDF. A single GELU unit is asymptotically linear for large positive pre-activations and asymptotically zero for large negative ones, and it could be tempting to conclude that a GELU network should diverge on one side and flatten on the other. It does not: it diverges on both. For a hidden unit with input weight wi > 0 the pre-activation grows large and positive as x → +∞, contributing a linear term, and large and negative as x → −∞, contributing nothing; for wi < 0 the roles are reversed. Fitting an even target such as x2 generically requires hidden units of both weight signs, so each tail of the extrapolation region is dominated by a different subset of units, and both subsets contribute

(b) two units, opposite weight signs each flat on one tail, the sum diverges on both

ReLU max(0, x) linear tail GELU x (x) Sigmoid 1/(1 + e x)

bounded flat tail

pre-activation x

7 6 5 4 3 2 1 0

|x|, the asymptote unit with wi > 0 unit with wi < 0 their sum = xerf(x/ 2)

slope contribution aiwi

6 5 4 3 2 1 0 1

(a) one unit, the three activations ReLU and GELU: linear right, flat left

output

activation

A property of the activation is not a property of the network. One GELU unit is flat on its left tail, and a network of them is not.

tail 1.5 wia<w0,=left5.93 i i 1.0

wi > 0, right tail aiwi = +5.50

0.5 0.0 0.5 1.0 1.5

input weight wi

Figure 3: The three activations at unit level, and the step that the unit-level reading does not survive. (a) ReLU and GELU are asymptotically linear on one tail and flat on the other, while Sigmoid is bounded on both. (b) Two √ GELU units whose input weights carry opposite signs are each flat on one tail, and their sum is x erf(x/ 2), with erf the error function, which grows like |x| on both (§A). (c) A one-hidden-layer GELU network of 64 units trained on f (x) = x2 over [−3, 3] by full-batch Adam, with each hidden unit’s asymptotic slope contribution ai wi plotted against its input weight wi . Units of both signs are present, the two groups sum to the left and right tail slopes of the Neural Network, and those sums agree with the slopes measured directly at x = ±200. Panels (a) and (b) are exact evaluations of closed-form functions, panel (c) is a trained Neural Network. an unbounded linear term to√their own tail. The elementary case is two units of opposite input-weight sign, whose sum is x erf(x/ 2), with erf the error function (§A). It grows like |x| on both sides, since erf(z) → ±1 as z → ±∞, even though neither unit grows on more than one (Figure 3b), and a trained Neural Network is assembled the same way. Of the 64 hidden units fitting x2 on [−3, 3] in Figure 3c, 34 carry a positive input weight and 30 carry a negative one, and the two groups sum to tail slopes of +5.50 and −5.93, so the Neural Network grows without bound in both directions. Evaluated at x = 200 and x = −200 it returns 1.10 × 103 and 1.18 × 103 , where the target is 4 × 104 at both, which is linear divergence on each tail against quadratic growth. The word generically is doing real work, and we measured what it covers: across widths from 4 to 128 and three seeds, 14 of 15 trained networks carried units of both signs and diverged on both tails, and the single exception, the worst fit in its row, ended with every input weight positive, so its left tail returns to the output bias rather than diverging. That exception is the convergence regime of §3.6 rather than a bounded extrapolation, so both outcomes lie inside the account given here. This matters twice over. GELU inherits ReLU’s unbounded divergence rather than gaining Sigmoidlike boundedness on either side, which is the worse asymptotic failure mode and applies directly to contemporary practice, since GELU and the closely related SiLU and Swish are standard in Transformer architectures. And it is a reminder that properties of an activation function do not transfer directly to properties of a Neural Network built from it, which is exactly why extending Xu et al. [90] from ReLU to smooth activations requires the measurement rather than the intuition. Within the window measured the GELU network in fact tracks the true quadratic more closely than the other two, since two opposing linear tails approximate a parabola tolerably over a bounded range; the divergence is asymptotic and widens further out.

Extrapolation behaviour of one-hidden-layer MLPs trained on f(x) = x2, x [ 3, 3] extrap.

ReLU (train RMSE 6.8e-03) true f(x) = x2 ReLU MLP

output y

Sigmoid (train RMSE 1.6e-03)

extrap.

true f(x) = x2 Sigmoid MLP

extrap.

GELU (train RMSE 1.5e-03) true f(x) = x2 GELU MLP

extrap.

20 10 0 6

input x

Figure 4: Three one-hidden-layer MLPs (64 units, full-batch Adam) fitting f (x) = x2 on [−3, 3] and evaluated on [−6, 6]; shaded bands mark the extrapolation region. All three fit the training domain almost exactly and all three depart from the true function immediately outside it, in a manner set by the asymptotic behaviour of the activation rather than by the shape of f . GELU diverges on both tails, for the networklevel reason given in the text.

3.5

The boundary condition, which is the argument’s positive control

The condition on the limit is representational. A Neural Network built from affine layers and piecewiselinear activations represents exactly one class exactly: the piecewise affine functions, each piece a firstdegree polynomial. When the generating mechanism lies inside that class, the Neural Network can recover it and extrapolate indefinitely far from any training point, because the map it prolongs beyond the outermost region is the correct continuation rather than an artefact of where the data stopped. The canonical case is f (x) = |x|, which is x for x ≥ 0 and −x otherwise. It is piecewise affine with a single vertex, and a ReLU network trained on a bounded interval containing that vertex recovers it and extrapolates with essentially zero error. This is the same conditional Xu et al. [90] prove for linear targets, and it is why they report successes alongside failures in extrapolation. A second and distinct exception arises for bounded targets: where the true function saturates, a saturating activation’s plateau cannot diverge far from it, so the error stays small even though nothing was learned about the region. Two distinct conditions must therefore hold together, representability and observability, and separating them matters because they are easily conflated. Representability requires that the target mechanism lie within the hypothesis class the architecture can express. Observability requires the training data to determine the correct member of that class. For a piecewise-affine network this means that every vertex of the target lies inside the training region: the outermost affine pieces of the target are then observed on segments of positive length, and the pieces the Neural Network prolongs outward coincide with them. A ReLU network can represent a sawtooth with fifty teeth exactly, but trained on three of the teeth it does not extrapolate the remaining forty-seven, because the vertices it never observed are not in the data. This conditional success is what the representational argument rests on. Were the deficit caused by something diffuse, insufficient data, imperfect optimization, or inadequate scale, failure would be broadly uniform. It is not. Failure is predicted precisely by whether the generating mechanism falls outside the representable class, and success returns the moment it falls inside it. That is a controlled dissociation, and it isolates representation as the cause rather than merely a correlate. The cases where a Neural Network extrapolates perfectly consequently do not contradict this account. They are its positive control. What follows is a sharper claim than the one usually made. DL does not fail at extrapolation as such. It fails specifically at extrapolating any generating mechanism that is not piecewise affine, and the mechanisms we actually care about, whether the inverse-square laws of physics, the compositional rules 10

of abstraction benchmarks [16, 17], or the universally quantified relations of §4, overwhelmingly are not.

3.6

Scope: when Neural Networks converge instead of diverging

The divergence picture has a real counterexample and it should be stated rather than managed. Kang et al. [48] find that Neural Networks with high-dimensional inputs tend, as inputs become more OOD, toward a constant that closely approximates the constant solution: the input-independent prediction that minimizes average training loss, which Kang et al. call the optimal constant solution, optimal only among constants. They observe this across eight shift datasets, on Convolutional and Transformer architectures, under cross-entropy, squared-error and Gaussian likelihood losses. The regimes differ, and both results are correct in their own. A softmax output is confined to the simplex and cannot diverge; normalization layers bound activations; and in high dimensions a sufficiently distant input drives features toward a region where the Neural Network emits little more than its bias, which is approximately that constant, the best input-independent prediction the training loss admits. An unnormalized regression head on a low-dimensional input has none of these boundaries, and diverges. We therefore scope the divergence claim to unbounded-output regression networks without normalization, which is the setting of Figure 4. What matters for the criterion is that convergence is not a different kind of event. A Neural Network falling back to the training mean is not computing the generating mechanism either; it has substituted a data-derived default for a law. Both behaviours are the same shortfall in exact representability, differing in what the architecture does when it runs out of evidence: prolong the last affine piece, or emit the prior. Neither is the target. We add that the converging case is in some respect the more dangerous, since a plausible mid-range constant causes less suspicion than a visibly diverging ramp.

3.7

The reach across architecture families

It is tempting to treat the deficit as a symptom of insufficient capacity, and to expect scale to resolve it. But it is instead a structural property of the representation [90], and it propagates: an MLP sits inside nearly every DL architecture in use, and wherever it lies on the path of a computed quantity, that quantity inherits its limits. §5.3 states the propagation rule precisely, including the cases where it does not apply, which are as informative as the cases where it does. Increasing Neural Network depth does not help, and the reason is a detail of the UAT that is often overlooked. The theorem guarantees approximation within a compact subset K ⊂ Rn [26, 46]. When affine maps are composed with standard nonlinearities, the partition they induce is local, so additional layers increase the density of hyperplanes inside K [67]. Outside K no data constrains the optimization, and however deep or wide the Neural Network, the outermost regions remain unbounded. • Convolutional Neural Networks (CNNs). A convolutional layer is a sparse affine transformation with weight sharing, followed by an activation, so a CNN is a structurally constrained curve-fitting function across spatial dimensions. They fail to extrapolate even to modest spatial transformations [4]. • Transformers. Every Transformer block ends in a position-wise feed-forward Neural Network, which is an MLP, and is mathematically required to prevent the attention matrix from rank-collapsing [33, 85]. Despite dynamic context routing, a Transformer remains subject to the same region geometry and activation asymptotes at the boundary of its learned distribution, which pushes it toward structural pattern matching rather than compositional reasoning off-distribution [34]. • Graph Neural Networks (GNNs). Message passing aggregates neighbourhood features and updates 11

node representations through MLPs [51]. The relational inductive bias helps interpolation within known topologies, but on graphs of unseen size or with node features outside the training manifold, the underlying MLPs must extrapolate, with the same asymptotic consequences [90, 92]. Geometric DL deserves a separate treatment, since it is the strongest form of the objection. By imposing invariance or equivariance to a symmetry group G, it mitigates the curse of dimensionality and improves generalization [11, 18]. But does operating intrinsically on manifolds overcome the asymptotic limit? It does not, and the reason is instructive rather than dismissive: it expands the interpolation space. A model with the added equivariance constraint no longer operates on the original unbounded space but on the quotient X /G, and inside that quotient the constraint is exact at any distance from the data, since it was imposed as an algebraic identity and never estimated. If a shift moves along a direction the group does not act on, the quotient is left and the model goes into extrapolation mode, as before. Approaches combining invariance with information bottlenecks to bound generalization error [3] inherit the same boundary. Standard pointwise nonlinearities are defined on Euclidean coordinates rather than intrinsically on a curved manifold, so such models apply them in local Euclidean tangent spaces, through exponential and logarithmic maps in hyperbolic Neural Networks [39] and through local coordinate charts in gauge-equivariant architectures [19], and once outside the protected quotient, the underlying MLPs converge to their asymptotes. This is the constructive reading we return to in §7: an imposed group provides some directions with exactness and leaves the remainder without it, so the question becomes who determines this group.

The Relational Face

4.1

Propositional and first-order representations

There is a parallel limitation in relational reasoning. If asking DL architectures to learn rules governing relational data, whether knowledge graphs, family trees, or physical interactions, these default to propositional representations rather than abstract, universally quantified rules [37, 62]. The distinction is the classical one. A propositional system evaluates the truth of specific ground statements. A first-order system uses variables that can be instantiated across an unbounded domain, as in ∀X,Y : Parent(X,Y ). Knowledge graph embeddings and GNNs operate predominantly at the propositional level: they learn geometric vectors for specific known entities, and therefore lack the mechanism of variable binding, the ability to instantiate an abstract logical variable with a novel entity at inference time [43]. Presented with an entity absent from training, such a model has no learned vector, and deduction collapses.

4.2

Case study: the transitive kinship discrepancy

Consider inferring Grandparent from Parent. The mechanism generating the data is an exact, universally quantified rule: ∀X,Y, Z : Parent(X,Y ) ∧ Parent(Y, Z) ⇒ Grandparent(X, Z). (2) Because the rule is stated over unbound variables, its truth is independent of the entities themselves. Learn it, and it extrapolates exactly to any entities whatever. Trained on such data, an embedding model does not learn the rule. TransE [10] and R-GCN [77] instead learn a continuous approximation, assigning a vector to each known entity and adjusting those

vectors until the geometry agrees with the propositions observed: eAlice + vParent ≈ eBob

(3)

eBob + vParent ≈ eCharlie

(4)

from which eAlice + vGrandparent ≈ eCharlie follows by interpolation. Introduce a disjoint family of novel entities, as in Figure 5, and the arithmetic has nothing to operate on: the vectors for the new entities were never fitted, so they carry no information about the relation. The model did not learn the rule, it learned the geometry of the training examples [64]. Parent

Alice

Parent

Bob

Charlie

Grandparent (interpolated) Parent

David

Parent

Eve

Frank

No fitted embeddings for David, Eve, Frank. The relation cannot be deduced geometrically.

Figure 5: An architecture that represents an entity as a free per-entity parameter memorizes propositional geometry and has nothing to apply to a disjoint set of novel entities, because the rule was never represented as a first-order rule.

4.3

Propositional memorization and LLMs

When an architecture of this kind fails to learn a rule with quantifiers it succeeds at something else: it memorizes the propositional geometry of the training set. When observing (Paris → France → Europe) it assigns and fits vectors until the distances agree, and predicts that Paris is in Europe not because it represents transitivity but because it is stored in that geometry. Asked about (Kyoto → Japan → Asia) with no vector for Kyoto, the arithmetic breaks down. Because LLMs generate fluent text they project the impression of an internal symbolic engine, when they are autoregressive predictors over token co-occurrence [8]. Answering a syllogism correctly is not executing Human(X) ⇒ Mortal(X); it is predicting a highly probable token sequence whose structure is dense in the training distribution. When the semantics of a puzzle are inverted, or entities are replaced with novel synthetic nouns, performance degrades sharply [34], and Mirzadeh et al. [66] reach the same conclusion from perturbed mathematical word problems. Lee et al. [59] reach it from the other side, by scoring the process rather than the answer on ARC-AGI: the models that reproduce a correct output grid frequently fail the intermediate steps that would have produced it, so the output is not evidence that a rule was applied. Such models learn what logic looks like rather than the true rules of logic.

4.4

The limits of Turing-complete neural architectures

Neural architectures explicitly designed to simulate algorithmic reasoning are provably Turing complete, and theoretical capacity is not empirical realization. Because these designs remain fully continuous and 13

differentiable, they do not escape the representational limit. • Memory-augmented networks. Neural Turing Machines [41] and Differentiable Neural Computers [42] decouple computation from memory, which is the right move. To stay end-to-end differentiable they cannot use discrete pointers, and rely instead on continuous addressing driven by similarity. Introduce an entity outside the training distribution and the similarity search has no reliable target. • Adaptive computation and Universal Transformers. Halting computation dynamically [29, 40] achieves length generalization, and the loop applies the same continuous affine transformations recursively, so abstract relational generalization does not follow from it. • Relational Networks. Imposing a structural prior by evaluating every pair (xi , x j ) [76] does not change what processes each pair, which is a standard MLP receiving coordinates outside its empirical region. The pattern is the one already stated, and it is the compositional rule of §5.3 seen from the relational side: Turing completeness describes what an architecture could compute given the right weights, and says nothing about what lies on the inference path of any particular quantity. In each of these designs the quantity that must generalize to a novel entity has a fitted similarity computation, a fitted addressing mechanism, or a fitted inner Neural Network on its route, so it inherits the approximation limits accordingly.

4.5

Stated at the right scope

The previously described failure belongs to architectures that represent an entity as a free parameter fitted to that entity. It must not be claimed that neural architectures cannot bind variables. Two published systems show they can, and both are instructive. ESBN [88] augments a recurrent controller with an external memory whose key column holds abstract variables and whose value column holds perceptual embeddings. The controller never receives entity embeddings directly; it emits keys and receives back retrieved keys and confidences, so the rule-learning pathway is structurally entity-independent. It attains near-perfect generalization of learned rules to novel entities. Its scope is narrow: its tasks, same/different, relational match-to-sample, distribution-of-three and identity rules, concern relations among items presented together within a single problem, not multi-step chained inference binding an intermediate variable across steps over an open domain of constants. The grandparent rule example we gave is of the latter kind. GraIL [83] reasons over subgraph structure with node labelling relative to the target nodes, making the representation entity-independent, and generalizes to unseen entities and entire unseen graphs. Its own theoretical claim is to represent “a useful subset of first-order logic.” Neither refutes the representational thesis. Both confirm it, and this is the cleanest evidence available for it. ESBN binds variables because indirection was built into its representation. If one removes the indirection the capability goes with it. GraIL generalizes to unseen entities because entity identity was designed out of what it represents. In each case the generalization capability arrived exactly when the alternative representation did, which is our thesis, and §5.3 says why in architectural terms: both designs work by removing a fitted component from the inference path of the quantity that had to generalize. And Barceló et al. [6] give the precise version for GNNs, a fragment of FOL with counting rather than propositional logic, so the real limit consists of a representational boundary and not an unsurpassable wall. The binding problem persists in frontier multimodal systems and is documented by Campbell et al. [13], from authors who elsewhere advocate architectural solutions to it. GraIL also draws the distinction this paper is about. It is entity-independent, it generalizes, but it still scores candidate triples with a function approximation rather than executing a relation. Its generalization

is empirical and graded. Better representability bought better generalization without buying exactness, so exact generalization is still out of reach for this system.

Exactness at Inference

Criterion 1 (Exactness at inference). A system generalizes outside its training distribution on a given input only if the representation it consults on that input is structurally equivalent to the underlying datagenerating mechanism, so that the operation performed computes the intended function or relation, rather than evaluating a continuous surrogate with the wrong representation, whose agreement with that function or relation was calibrated on a region of input space that the given input does not lie in. What structural equivalence requires. We mean the previous definition in the algebraic sense rather than the physical one, since the objection that a model executes arithmetic on silicon and not on the mechanism itself is correct but beside the point. A representation is structurally equivalent to a mechanism when its constituents and its composition operations map onto the mechanism’s in a way that preserves the mechanism’s relations on every admissible input, so that agreement holds by construction over the whole domain and not by calibration on a sampled part of it. This is the sense of universal algebra and model theory, a homomorphism of structures that preserves the operations and relations. Floating-point arithmetic evaluating x2 is structurally equivalent to squaring, to within a rounding error that is a property of the number system and not of the data; resolution over a clause is structurally equivalent to the quantified rule the clause states; a partition of affine pieces fitted to samples of a curved law is not structurally equivalent to that law, however small the error on the samples can be. The definition also makes the criterion’s scope plain: equivalence is to the mechanism as the problem presents it, so an encoding that is itself wrong cannot be rescued by exact execution downstream of it, a point we return to in §7. Three clarifications are still needed.

5.1

Exactness is not discreteness

Discreteness is what exactness reduces to when the intended semantics is classical logic, whose ground atoms and truth values are discrete. Discreteness is not the right criterion, and conflating them misclassifies systems in both directions. In one direction, an exact operation may be continuous-valued. A sum-product tensor contraction computing an exact marginal has codomain [0, 1], has nothing fitted in it, and extrapolates for the same reason f (x) = x2 does: it computes the intended function rather than a surrogate calibrated on data. Figure 6 shows the operation in both of its readings. A system may therefore reason under uncertainty and satisfy Criterion 1, which matters for any domain where the evidence is partial. In the other direction, a discrete-valued operation may be inexact. A standard Neural Network whose output is thresholded to a hard label emits a discrete value, but this threshold is a fitted boundary; hardening it changes the codomain and not the epistemic status. Exactness is a property of what is computed. Discreteness is a property of the codomain. The distinction that survives is between the function computed and the substrate computing it, and it is the function that must be exact. One qualification applies throughout. Exactness is always exactness relative to the object being executed: an exact marginal is exact given the factors, and a logic program is exact given the clauses. Where those were themselves induced, the induction remains fallible. The claim is not that induction is infallible but that its fallibility and the execution’s exactness are separable, which is what makes the error localizable.

(a) Boolean tensors, T = 0: the Grandparent rule Pxy

Pyz

A 0 1 0 B 0 0 1 C 0 0 0 A B C

A 0 1 · B 0 0 C 0 0 A B y

(b) Real tensors: an exact marginal

Gxz 0 1 0 C

A 0 0 1 A→C −−→ B 0 0 0 C 0 0 0 A B C ∑y

p(x)

p(y | x)

p(z | y)

p(z) = ∑x ∑y p(x) p(y | x) p(z | y) Same operation, same diagram, entries in [0, 1]. The contraction of the chain’s factors is the exact marginal of z: its codomain is continuous, nothing in it is fitted, and it holds for every input for the same reason f (x) = x2 does. A box is a tensor, a line an index, a joined line a summed index, an open line an index of the result. Reading (a) is Datalog; reading (b) is a PGM. The criterion is satisfied in both, since what is executed is the relation itself.

Gxz = σ ∑y Pxy Pyz over {A, B, C}: the shared index y is summed out and the step function at T = 0 keeps the values in {0, 1}. The incidence tensor of Grandparent is computed, not fitted.

Figure 6: A sum-product tensor contraction in its two readings. (a) With Boolean incidence tensors and a step function, the contraction over the shared index executes the Grandparent rule of §4 exactly, over the closed domain the indices enumerate. (b) With the same shape over real factors, it computes an exact marginal with codomain [0, 1]. Discreteness is a property of the entries; exactness is a property of the operation, and the operation is the same in both panels.

5.2

It is a property of inference, not of training

Nothing in Criterion 1 constrains how the right structure can be found. A system may search by gradient descent, by relaxation, by enumeration or by sampling, and satisfy the criterion provided that what it consults at inference time is the resulting structure and not the search mechanism. This is why the criterion does not imply avoiding Neural Networks, and why it allows for the whole of neurally guided search approaches. The consequence is a qualitative difference in how systems fail. Where an approximation is consulted at inference, failure is graded: it degrades as inputs move away from the data, continuously and without a signal. Where a structure is executed, failure is discrete: if the wrong structure was induced, then the structure is wrong everywhere in the same way, which is inspectable and which the induction can be blamed for. Fallible induction with exact execution is a different epistemic situation from fallible execution, and only the first localizes the error at training time, as will be shown in §6.1.

5.3

Composition: containing an MLP, and inheriting its limits

Almost every current DL architecture uses, somewhere inside itself, a standard MLP. The Transformer’s position-wise feed-forward block is one, and is mathematically required to keep attention from rankcollapsing [33]. A message-passing Neural Network updates node states through one [51]. A Relational Network processes every object pair with one [76]. An LTN grounds each predicate in one [5]. A scalarinvariant model applies one to the invariants it computes [86]. The temptation is to conclude that all of them therefore inherit the limits of §3, but this would be an unqualified version of our criterion. Three cases in this paper refute the unqualified version. As mentioned before, an ESBN controller is built from standard components and nonetheless binds variables to novel entities [88]. A scalar-invariant model is an MLP applied to r, and it is exact along every direction its group acts on. A Hamiltonian Neural Network’s Hamiltonian is an arbitrary fitted Neural Network, and energy is still conserved exactly [44]. There is a further technical objection: an MLP receiving normalized activations is never evaluated far outside its own training domain, because it is constrained by the normalization independently of the 16

Neural Network’s input, which is the same mechanism that produces convergence rather than divergence in §3.6. Presence of a fitted component is evidently not sufficient for the inheritance of MLP limits. The correct statement is the compositional form of Criterion 1, and it is a statement about paths rather than about components. A computed quantity inherits the limits of every fitted component lying on its inference path. If the fitted component is not in its inference path, it constrains other quantities and not this one. This resolves all the cases at once. The Transformer’s feed-forward block lies on the path of the output, so the output inherits its limits. The message-passing update lies on the path of every node representation, so the nodes inherit the limits. The invariant model’s MLP lies on the path from r to its prediction but on no path from angular position to anything, since the angle is discarded before the MLP is reached, which is why such a model is simultaneously exact on the group’s orbits and fitted along the law, a dissociation observable directly in a controlled setting (§6.3). ESBN’s indirection is precisely a device for keeping entity embeddings off the controller’s path, and the binding capability it buys is the capability of the quantity that no longer has a fitted component on its route. In a Hamiltonian Neural Network the symplectic integrator lies on the path of energy conservation while the fitted Neural Network lies on the path of the dynamics, and the two properties behave accordingly: conservation is exact, and the trajectory is not. The criterion has a quantitative aspect that matters where modules are chained. Exactness is preserved under composition and approximation is not. A module that computes its relation exactly contributes a residual of zero, and zero is a fixed point of composition, whereas a fitted module contributes a residual ε > 0 that every later stage transforms rather than removes. Across n stages with downstream Lipschitz constants Lk the accumulated error is bounded by ∑k≤n εk ∏ j>k L j , a bound derived in §A, which grows geometrically in n wherever the composed map expands, so a residual of 10−4 that is invisible at one hop is not invisible at twenty. This is the mechanism behind a familiar observation, that architectures with excellent single-step accuracy degrade on multi-hop reasoning and on long rollouts while their one-step error in distribution looks perfect, and it is the reason the composition evidence of §8.4 favours systems whose stages are exact: what they compose is a residual that stays at zero. Two consequences follow. The first is diagnostic. To predict where an architecture will fail OOD, one does not ask whether it contains a fitted component but which quantities have one on their path. That question is answerable by inspection of the architecture, before any experiment, and it is what makes the criterion useful rather than merely correct. The second is that placing a Neural Network off the inference path is a design move available to anyone, and it is the same move §8.3 recommends for search guidance: an MLP-based model that ranks candidate structures influences which hypothesis is selected without being on the inference path. The unqualified reading is nonetheless right for the general case, and the exceptions usually share the same feature. This feature is that something was deliberately built to keep the fitted component off a path, and someone had to know which path to protect. That is §7’s point arriving from another direction: architectures are exact where a designer arranged for them to be, and fitted everywhere else, which corresponds to the totality of standard Neural Network architectures.

5.4

Sorting neuro-symbolic systems

The failure of the architectures above reveals an apparent paradox: the very mechanism that allows Neural Networks to learn end-to-end, differentiability, is what prevents them from executing abstract logic. To compute a gradient the loss landscape must be continuous and smooth, but to execute logic reliably the 17

operation performed must be exact rather than approximate. This becomes clear on differentiable neurosymbolic systems, and our Criterion 1 sorts them in a way that a surface taxonomy of neuro-symbolic systems [49], which classifies them by how the neural and the symbolic components are wired together, does not. Logic Tensor Network fails it. LTNs unify connectionism and logic by relaxing FOL into a continuous domain using fuzzy t-norms [5, 27]. Logical rules can then act as differentiable loss functions during training, and the predicates remain parameterized by Neural Networks. Crucially no standalone discrete rule is extracted. To evaluate a relation between novel entities at inference, an LTN must pass them through its continuous layers, which on unseen inputs produces an asymptotic geometric artefact, and the fuzzy operators aggregate those arbitrary continuous outputs into a confident truth value. Thresholding would not repair it because the predicates are fitted Neural Networks, so a hard decision boundary is still a fitted, approximate boundary. Note also that on interior values the product t-norm equals the probability of a conjunction only under independence, which generally fails, so a composed formula is a surrogate for both the Boolean reading and the probabilistic reading, and an instance of neither. Two qualifications are owed: LTN defines a proof-by-refutation mode we do not analyse here, and practitioners often apply a post-hoc threshold at 0.5, which changes the output’s type without changing what produced it. Differentiable ILP passes it. ∂ ILP [36] appears to contradict the requirement but it does not. The continuous relaxation is used only during training, to smooth a combinatorial search space; weights are regularized toward {0, 1}; at inference the system extracts a strictly discrete symbolic rule and discards the Neural Network entirely. It succeeds precisely because it abandons the continuous manifold before inference, using differentiability as a temporary search heuristic to discover a discrete extrapolative structure. Evans and Grefenstette report the signature of exactness directly: trained on integers from 0 to 6, “the learned program works effectively on test integers of any size,” with “no chance of the learned program suddenly failing when the integers reach a certain size.” Tensor Logic at zero temperature passes it. This case is instructive because it first appears to be a counterexample. Tensor Logic [32] proposes a language whose unifying construct is the tensor equation, resting on the observation that a logical rule and an Einstein summation are essentially the same operation, so that neural and symbolic computation are dual aspects of the same construct. Reasoning runs over learned embeddings throughout, with no separate artefact written out and no Neural Network discarded, which on the surface groups it with LTNs. Its behaviour is the opposite, and a temperature parameter makes the difference. Applying σ (x, T ) = 1/(1 + e−x/T ) to each equation, Domingos observes that T = 0 “effectively reduces the Gram matrix to the identity matrix, making the program’s reasoning purely deductive,” and that the system is “immune to hallucinations at sufficiently low temperature.” Temperature is settable per rule, so rules expressing mathematical truths may run at T = 0 while rules accumulating weak evidence may run high. Our reading is that at T → 0 the sigmoid applied to every equation approaches a step function. Consequently, the inferred tensors become Boolean and the computed function becomes discrete, which is necessary for classical logic as noted in §4, even though the underlying arithmetic remains continuous. This zero-temperature limit is not merely a discretization. A Gram matrix equal to the identity implies that the embeddings are orthonormal, functioning as a one-hot encoding up to an unobservable rotation: any orthonormal family is the image of the standard basis under an orthogonal transformation, and a contraction sees its embeddings only through inner products, which such a transformation leaves unchanged. The computational carrier, dense real tensors contracted by real multiplications and sums, remains en18

tirely continuous, with no separate logical rule store or symbol table. Only the values become discrete. A Boolean tensor indexed by an orthonormal family is simply the incidence tensor of a finite relation, that is, the table of which tuples of index values stand in the relation. This explains why the mathematical equivalence reaches Datalog and no further, and why introducing a novel entity requires a new index dimension rather than just a new constant. The symbolic content is natively present because the tensor equation, written in contraction syntax, already serves as the symbolic program. Unlike ∂ ILP, which searches via continuous relaxation but must extract a discrete rule and discard the Neural Network, Tensor Logic collapses the relaxation in place. The difference between the two is implementation, not semantics. This physical implementation imposes strict geometric boundaries on the tensors. Because the system computes via fixed-dimensional linear algebra, it cannot natively represent infinite functional recursion: a tensor of fixed shape enumerates a fixed set of index values, whereas a function symbol builds new terms without bound, and those terms have no index to range over. It therefore achieves equivalence only with Datalog, which uses finite constants and function-free terms, and not with full Prolog, which requires an infinite Herbrand universe and terms of unbounded depth. Also, this equivalence holds only under two familiar conditions for finite and complete Datalog evaluation [1]: the rules must be range-restricted, and each index must cover the active domain. Attempting to dynamically expand dense tensors to bind novel entities multiplies costs across the remaining dimensions and shatters the static execution graphs that accelerators compile once and reuse [47]. Consequently, while the in-place tensor is exact over a known, closed domain, binding variables to novel entities requires abandoning the strict in-place constraint. The system must either use externalmemory indirection to allocate new symbols without reshaping the core reasoning tensors [42, 88], or explicitly extract the rule for a standard logic engine to execute, as ∂ ILP does [36]. Both approaches align with the propagation rule of §5.3 by keeping a fitted representation of the entity off the inference path. Conversely, if T > 0, the continuous embedding geometry carries inferential weight, entity representations revert to fitted surrogates, and the relational limits of §4 fully return inside the closed domain. Per-rule temperature therefore acts as a declaration of which parts of a model hold exactly and which remain approximate. Temperature above zero is a relaxation of the logical reading, in which the embedding geometry rather than the relation carries the inference, and it is not the same thing as probabilistic inference. Tensor Logic also executes the latter, as a sum-product contraction over factor tensors rather than a softened contraction over embeddings, and that regime can be exact in its own semantics; §5.5 says under which conditions. One qualification applies to both passing cases: the exactness of the execution depends on a fallible induction. Tensor Logic’s exactness relies on the learned embeddings being near-orthogonal, just as ∂ ILP’s exactness relies on accepting the specific extracted clause. In both systems the induction is fallible, but the execution remains exact. These cases therefore corroborate our criterion: even when beginning from the premise that logic is fundamentally a continuous Einstein summation, reliable logical reasoning still requires the zero-temperature limit, with exact probabilistic reasoning available under the different semantics of §5.5. A fully differentiable system achieving high zero-shot accuracy on novel entities does not refute this sorting. Our criterion concerns what is computed, not what is scored. High accuracy on a specific test distribution shift does not guarantee structural exactness. To falsify this criterion, an unthresholded continuous system would need to demonstrate exact, non-degrading agreement on an adversarially chosen distribution shift. We are not aware of any such demonstration.

5.5

Graded semantics without surrendering exactness

One clarification prevents reading the criterion too narrowly. Discreteness is what exactness reduces to when the intended semantics is classical logic, and classical logic is not the only semantics available. Tensor Logic can also implement Probabilistic Graphical Models (PGMs) [52] directly, with a factor as a tensor, the partition function as a projection, forward chaining as loopy belief propagation, and sampling as backward chaining with selective projection (Figure 7). A sum-product tensor contraction computing an exact marginal is exact and continuous-valued at the same time: its codomain is [0, 1], nothing in it is fitted, and it extrapolates correctly for the same reason f (x) = x2 does. A system may therefore reason under uncertainty without surrendering anything our criterion requires, which matters wherever the evidence is partial or noisy. Probabilistic logic programming makes the same point from the logic side. ProbLog [28] computes the exact probability of a query under the distribution semantics, so its inference is an exact operation with codomain [0, 1], and DeepProbLog [61] keeps that inference exact while letting neural predicates supply the probabilities it operates on, which is the division of labour the propagation rule of §5.3 describes: the logical inference is exact relative to the probabilities the neural predicates emit, but inherits their limits on the quantities that pass through them, in this case the probabilities themselves. A neural predicate is a fitted estimator of a conditional probability, and being a statistical estimate does not exempt it from the criterion: the probability it emits is a function of its input like any other, approximated rather than computed, so outside its training support it is subject to the same limits as any other fitted output. Probabilistic Graphical Model

Tensor Logic y

A factor φ (x, y, z) is a tensor Φxyz .

x Σy

The partition function Z = ∑x,y,z φ is a projection onto no index: every line is summed.

Σx

Σz =

∑x,y,z

Forward chaining is loopy belief propagation: messages pass along the graph until nothing changes.

contract −−−−−→ T (k+1) iterate to a fixpoint

T (k)

Σy

Sampling is backward chaining with selective projection: fix the query, sum out the rest.

x z

∑x,y

Σx

z left open

Figure 7: The correspondence Tensor Logic provides between PGM operations and tensor operations [32]. Each row pairs the graphical object on the left with the contraction that computes it on the right, in the diagram notation of Figure 6: a box is a tensor, a line an index, and a line closed by Σi an index i summed out. Under this correspondence a marginal is a contraction with one line left open, which is why an exact marginal is continuous-valued and exact at the same time. This is also the sharpest way to separate the three presented neuro-symbolic architectures on uncertainty, and the ordering may not be intuitive. An LTN appears built for uncertain environments and is not exact under any semantics: a t-norm agrees with Boolean conjunction on {0, 1}, but an LTN never operates there, and on interior values the product t-norm equals the probability of a conjunction only when the conjuncts are probabilistically independent, P(a ∧ b) = P(a) P(b), an assumption that many real-world 20

applications violate. ∂ ILP’s relaxation is a device for searching a discrete space rather than a choice of semantics for uncertainty, since the graded values it carries express confidence about which clause is correct, not uncertainty about the world those clauses describe, and what it delivers is a Boolean program. It therefore performs no probabilistic inference in ProbLog’s sense: no distribution over possible worlds is defined, and no query is assigned a probability. Tensor Logic is the only one of the three in which graded reasoning is a semantic choice rather than a relaxation, which is what per-rule temperature makes explicit, holding mathematical truths at T = 0 and evidence accumulation with T > 0, within a single program. Whether Tensor Logic reasons exactly under uncertainty, in the way ProbLog does, therefore has a definite answer: in its PGM reading it computes an exact marginal relative to the factors it is given, under two conditions. The contraction must be carried out exactly, since, on a graph with cycles, loopy belief propagation approximates the marginal, and an approximated marginal is a surrogate whatever its codomain. But to fulfil our criterion, the factors must be given rather than fitted on the inference path, which is the same condition DeepProbLog’s neural predicates respect. The temperature relaxation of §5.4 is a third thing, a softened logical reading, and it is not exact under either semantics. The two readings should not be confused: the PGM reading involves no temperature at all, and its exactness is governed by the two conditions just stated. A rule executed at T > 0 therefore never meets the criterion, in an uncertain, noisy or partially observed environment as much as in any other, unless the softened similarity it computes is itself the generating mechanism. Where the evidence is uncertain, exactness is available through the PGM reading over given factors, while raising the temperature does not provide it. The approach we proposed in previous work [72–74], and to which we return in §8, inducing firstorder clauses executed by a resolution engine, secures exactness by the most direct route available, which is to induce the discrete structure and run it. This is a proposed design choice, also made for tractability and inspectability, but is not the only route available.

The Epistemic Corollary: Competence Is a Property of the Hypothesis Class

The application of our criterion so far was concerned with where a model is correct outside its training data. But it has a second consequence, which concerns where a model can know whether or not it is correct outside of its training data, and the two boundaries turn out to coincide. The prevailing treatment of notknowing is additive: train a Neural Network, then append an uncertainty estimator computed from the fitted model or from the geometry of its training data rather than from a hypothesis (an ensemble’s disagreement [56], a distance score in input or feature space [58, 82]), and abstain where the estimator sounds the alarm. Our criterion explains why this cannot work in general. Abstention is a statement about what the training data determines and does not determine, and determination is always relative to a hypothesis class and its constraints: the same training data that leaves a query open under one constraint may fix it completely under another. A model that consults no exact hypothesis at inference has nothing definite to abstain from, and no estimator bolted on afterwards can supply the structural bounds the hypothesis class itself lacks. This section makes that argument concrete on a single experiment.

6.1

A fitted model carries no internal signal of recovery

The target function throughout is a radial chirp, f (x, y) = sin(x2 + y2 ), trained on 1200 points from the annular wedge r ∈ [1, 2.2], θ ∈ [0, π/2] and probed on fresh points in distribution, at unseen angles, and at unseen radii r ∈ [2.2, 4] (Figure 8). The first observation is the criterion’s central distinction appearing inside a training run. A sine-activation network [80], whose basis is matched to the target, improves 21

training loss over ReLU by one to two orders of magnitude (2.5–46 × 10−6 against 2.9 × 10−4 across a sweep of seeds and initialization scales) with no corresponding gain at unseen radii, error 1.10–1.31 against 2.33, and the best-fitting configuration is one of the worst extrapolators. Training loss measures agreement on the region where agreement was calibrated, which is exactly the quantity that, according to Criterion 1, does not transfer, so a model of this kind has no internal signal on the difference between fitting the target law and fitting the training region.

4.0

2.2

1.0

2.2 x

4.0

training support determined (56.3%) novel (43.7%)

Figure 8: Training annulus (r ∈ [1, 2.2]) and radial query region (r ∈ [2.2, 4]) on the same wedge. Periodicity in u = x2 + y2 folds alternating query bands back inside the training u-support (determined, 56.3% in aggregate) or leaves them outside it (novel, 43.7%). Membership is fixed by radius but alternates in bands, so it is not monotone in distance from the training boundary (dashed). A system that commits to a hypothesis by explicit selection does. Given only raw coordinates and a fixed operator set, the bottom-up enumerative search of §8 recovers sin(x2 + y2 ) with coefficient one and intercept zero, at a selection residual of 8.8 × 10−33 , and the recovery is visible from the inside, on training data alone: the winner separates from the best semantically distinct runner-up by roughly thirty orders of magnitude in residual. Removing sin(·) from the operator set, an ablation of an operator the answer needs rather than of the answer itself, leaves the top candidates within 4% of one another at residual 2.2 × 10−2 , returned with no warning: hypothesis wrong, and diagnosably so, though the diagnosis is not the missing gap. Candidates are scored throughout this section by a description length, the Bayesian information criterion of Schwarz [79], n log(mse) + k log n for n training points and a candidate with k parameters, which reads as the length of a two-part code that transmits the parameters and then the residual; differences in it are quoted in nats on the deviance scale. A winner is isolated when it leads by more than 2 log(|H | − 1), below which it holds less than half of the posterior mass under a uniform prior on the class H . The ablated winner is still isolated, by 64 nats against a threshold of 27; what it lacks is adequacy, a residual four orders of magnitude above the noise floor, and a companion paper [75] shows why this is the part of the signal that generalizes. The separation is a property of commitment, not of discreteness, in the same sense as §5.5: a continuous three-parameter family A sin(ωu + ϕ) over u = x2 + y2 , scored by the same description-length criterion against the second-best mode of its likelihood surface, earns a certificate on the same scale as the discrete search’s, up to 71.0 nats per point against the search’s 70, stable under grid refinement, while a Neural Network blending the same basis functions by unconstrained gradient descent obtains none of the significant separation obtained in the two previous examples: the discrete search’s comparison against its runner-up and the continuous family’s comparison against its second-best mode.

6.2

Distance is not unanswerability

The induced symbolic expression entails two global constraints that were supplied by no one: the range bound | f | ≤ 1, and periodicity in u = x2 + y2 with period 2π. The training wedge covers u ∈ [1, 4.84], 0.61 of a period, so folding a distant query’s u back modulo 2π lands part of the radial extrapolation region inside the training support (Figure 8). The determined fraction is 56.2% rather than 0.61, because the query range spans 1.776 periods and the last folded copy is truncated (§A); the measured count over the queries is 56.3%. Relative to the induced constraint the training data already provides the answer on that subset, and evaluating the induced symbolic expression there, we obtain an error of 1.3 × 10−16 . The remaining 43.7% is novel, in the sense that data plus constraint do not determine it. Table 1: Radial queries by periodicity partition. A K=6 deep ensemble fails equally on both subsets and is falsely confident on both (ratio is disagreement over error); a Nearest-Neighbour distance detector abstains on both, which on the determined 56.3% is a false abstention. “N/A” marks what training data alone can certify. radial subset determined (56.3%) novel (43.7%)

ensemble err.

ratio

symbolic err.

distance detector

4.43 4.21

0.23 0.24

1.3 × 10−16 N/A

abstains (falsely) abstains (correctly)

Every additive estimator ranks this partition backwards. The determined queries sit farther from the training data on average, mean Nearest-Neighbour distance 1.16 against 0.82, and draw more ensemble disagreement, 0.78 against 0.57: as predictors for determined queries, the two signals score AUC: 0.69 and 0.67 in the wrong direction, moderate effect sizes pointed backwards rather than chance, because the periodic bands are placed by the law, to which neither signal has access. A distance-aware detector therefore abstains precisely on the queries whose answers the training data already provides. Being far from the training data and being unanswerable are distinct, measurable conditions, and the quantity that separates them exists in the hypothesis class.

6.3

The competence boundary coincides with the inductive bias

The propagation rule of §5.3 has an epistemic reading, and it is testable. On a radially symmetric target g(r) = r−2 , an O(2)-invariant ensemble, which computes r exactly and fits g, stays accurate and calibrated at unseen angles, where only its exact component is exercised (0.049 → 0.046 error, ratio 1.78 → 1.85), and at unseen radii, where its fitted component is consulted, it is worse than the generic Neural Network (error 4.88 against 2.42) without its disagreement becoming reliable. The generic ensemble on the same axis is the worst case: error 2.42 at ratio 0.09, consensus without competence, because every ReLU member extrapolates affinely in the same direction for the same representational reason, so their agreement certifies nothing [56, 71]. The model is exact precisely where its exact component acts, it fails silently precisely where its fitted component is consulted, and its self-report has the same boundary as its competence. Nothing in the uncertainty machinery sees that boundary; it is visible only from the architecture, by the inspection §5.3 describes.

Epistemic Dependence: Who Supplies the Structure

7.1

The pattern in the successful cases

There is a common thread in the successful cases. Every architecture that achieves exactness on some region does so because a person injected, in advance, a representation structurally equivalent to the process generating the data on that region. Equivariant networks are exact along the orbits of a group that a designer chose [11, 18, 86]. In Hamiltonian and Lagrangian networks the conservation of energy is exact because a symplectic structure was written into the architecture, while the Hamiltonian itself is left as an arbitrary fitted Neural Network [23, 44]. ESBN binds variables because indirection was built into its memory [88]. GraIL generalizes to unseen entities because entity identity was designed out of its representation [83]. In every case, the model did not discover the structure; it was given it, and the model is exact precisely where this structure operates and nowhere else. This is a coherent and often excellent engineering strategy, and we are not arguing against it. We are observing what it costs. Structure supplied by a designer is bounded by what the designer knew to supply, and it does not accumulate: a Neural Network given the rotation group does not thereby acquire the inverse-square law, and one given a symplectic form does not thereby acquire the Hamiltonian. Each new domain requires a new specification, produced by a person, and the model contributes nothing to producing it. The consequence for scaling is direct. If the exactness a system exhibits was injected rather than induced, then scaling the system enlarges the fitted part and leaves the exact part exactly where it was. This is consistent with the finding of Delétang et al. [30] that architecture class, and not training data or training time, predicts OOD generalization, and with Campbell et al. [13], who report that frontier visionlanguage models still exhibit binding failures. It also explains why apparent extrapolation successes so often turn out, on inspection, to be a human supplying the linearizing encoding: representability is a property of a problem as encoded, and the encoding is where the knowledge went in.

7.2

The objection against hand-designed priors, and why it fails

One objection is that a hand-designed language bias sneaks in the answer, where a connectionist model learns just from the data. It does not, because the connectionist model is underdetermined in precisely the same way. A Neural Network carrying more parameters than data admits infinitely many weight settings that fit the training set exactly and disagree everywhere off it, and capacity is not the binding constraint, as is demonstrated by the fact that such Neural Networks fit randomly assigned labels perfectly well [93]. Nothing in the data selects among those settings. What selects is the architecture, the imposed symmetry group, the implicit regularization of the optimizer, the initialization scale and the stopping criterion, which are all priors, and none of them comes from the data. The two paradigms are therefore not divided by whether they depend on a prior, but by whether the prior is declared. A vocabulary of primitives, once given, can be read, audited, disputed and replaced; a CNN trained by Stochastic Gradient Descent (SGD) has no less of a prior over the space of hypotheses, but it is distributed across design choices with no single object to point at, and it is fixed at design time all the same. Being hand-designed does not carry the cost it appears to, provided the vocabulary is chosen on principled grounds. The design cost is paid once and amortized across a class of tasks rather than incurred per task, and this amortization is stronger the more general the designed priors are. On the other hand, learn-

ing a vocabulary automatically from experience, whether by library learning or predicate invention, is an alternative answer to the same question and the two compose naturally, a principled seed vocabulary being exactly the kind of starting point such methods extend; but a learned vocabulary is itself fixed relative to the distribution of tasks that produced it, so it relocates the choice into the selection of that distribution rather than dissolving it.

7.3

The residual failure modes, and why they are universal

Systems that induce and execute first-order structure are not immune to OOD failure either, and two failure modes remain that are not exclusive to them. The first is search. Even when the hypothesis language contains the correct solution, the search may not find it: the time allowed for training or search may be too short, the signal being optimized, a loss or a scoring metric, may not single out the correct hypothesis, or the computation available may not cover the space. This holds for a Neural Network trained by SGD as much as for a symbolic search, and §8 returns to it as the combinatorial problem both paradigms share. The second is missing knowledge, since no system reasons about an entity it has not been told about. A symbolic engine needs the entity’s base relational properties declared at inference time, as in Adjacent(Entitynew , Node5 ), and without them the entity cannot be evaluated against universally quantified rules. A Neural Network needs the same information in a harder form, as weights, so it cannot be told anything after training without being retrained. The difference that matters is detectability. The input space of a Neural Network is total: an unmapped entity, a zero vector and a freshly initialized embedding all produce confident outputs, so the epistemic failure is concealed by the geometric one and surfaces as a confident wrong answer, with no object to point at. A symbolic engine abstains when a required premise is missing, and the missing premise can be located and supplied. The cost is coverage. An engine that abstains whenever a premise is missing also abstains where interpolation would have succeeded, and on a forced-choice benchmark an abstention and a wrong answer score identically, so the value of abstaining is realized only in deployment, and only where the surrounding system treats “unknown” as an outcome. Leaving search aside, which both paradigms share, DL suffers both the geometric and the epistemic failure, with the second hidden behind the first, while systems that execute induced structure suffer only the epistemic one, and it is visible.

What Follows

If our criterion (Criterion 1) is right, the requirement on a system aiming at OOD generalization is to induce a structure that can be executed exactly. Two mature symbolic induction paradigms do this over restricted languages. Symbolic Regression, for the continuous face. In continuous spaces, Neural Networks fail because their piecewise-linear topology traps them in rigid asymptotes [45, 90]. SR abandons continuous optimization: instead of approximating a function by tuning weights to place bounding hyperplanes, it searches a discrete combinatorial space of mathematical expressions for the analytical form that generated the data [78]. Genetic programming [54], sparse regression [12], and modern systems combining the two [22, 84] build and mutate abstract syntax trees over algebraic operators, lifting the empirical relationship into its algebraic structure. Once f (x) = x2 is recovered as a formula rather than as a graph, extrapolation is analytically exact and indifferent to input magnitude along every dimension. The discrete space of expressions is very large, and these methods are ways of searching it, each with limitations of its own, which we take up together with those of ILP below. 25

Inductive Logic Programming, for the relational face. Structured relational domains require the parallel shift. ILP searches a space of clauses and returns a program executed by resolution [24, 68]. A clause with variables can be applied to constants never seen, because nothing in it is referring to a constant, which is exactly the property the embedding models of §4 lack. The combinatorial space, for both. The standing objection to both paradigms is the combinatorial one. In SR the space of expressions grows exponentially with expression size, and finding the best expression is NP-hard [87]; genetic programming, sparse regression and their combinations search it heuristically, and benchmark comparisons find that they still fail to recover a substantial fraction of known groundtruth equations [55]. In ILP, hybrid search unifies bottom-up clause construction, which bounds the space using empirical evidence, with top-down refinement, which maintains logical consistency, pruning the subsumption lattice from both ends. Declarative language biases such as meta-interpretive learning [70] constrain the syntax of the hypothesis space to structurally sound templates. And compiling the induction problem into satisfiability or Answer Set Programming (ASP), as in ILASP [57] and Popper [25], brings conflict-driven clause learning to traverse the search space more efficiently. These methods move the boundary without removing it: the hypothesis space still grows combinatorially with program length, and learning recursive programs is harder still [20, 24]. The size of the combinatorial space is the main weakness the two paradigms share, and it is not yet solved.

8.1

A note on sample efficiency, and on not quantifying it

One practical argument often made for symbolic induction is that it reaches a given level of confidence from far less data than a Neural Network, and at the level of mechanism the argument is sound. Constraining a hypothesis space to a finite, syntactically bounded family of discrete structures trades expressive flexibility for statistical efficiency, which is the classical Occam-style observation. The empirical record bears it out, with ILP systems routinely inducing correct programs from tens or hundreds of examples where a connectionist model of comparable nominal expressive power requires orders of magnitude more [68, 69]. We state that advantage qualitatively rather than numerically. Setting a Vapnik-Chervonenkis (VC) bound for a piecewise-linear network against a finite-class bound for a bounded clause space compares quantities that are not commensurable, and the mismatch runs in opposite directions. The VC bound is agnostic and worst case, and is loose to the point of vacuity for Neural Networks that in practice generalize far better than it predicts, which inflates the Neural Network’s figure. The finite-class bound presupposes that the target clause already lies inside the hypothesis space, which is precisely the difficult part, and is silent on whether search finds it, which deflates the symbolic figure. A ratio assembled from the two would be an artefact of those choices rather than a measurement. We therefore report the mechanism and the empirical record, and decline to quantify it. What a symbolic engine saves in data it spends in search: it exchanges a statistical problem for a combinatorial one, as we have seen previously. Neither paradigm escapes a cost, and which is cheaper depends on the domain and is not a general fact.

8.2

Program synthesis as the general form

The two symbolic induction paradigms described are not sufficient for the general case. Analytical expressions lack state and iteration; logical clauses encode procedures awkwardly; and many generating mechanisms of interest correspond to procedural algorithms. Program synthesis is the general form, and

its costs are real: undecidability, termination, verification, and a worse search problem than either restriction. The mitigations are the familiar ones, a Domain-Specific Language (DSL) as language bias, learned guidance for the search, and library learning to accumulate reusable structure [35]. Our own work applies ILP to the Abstraction and Reasoning Corpus in this spirit [74], and earlier work on Relational Reinforcement Learning found the same pattern from another direction, improving over DL baselines while supplying domain knowledge [72, 73].

8.3

Placing each bias where it is required

The argument so far has treated the hypothesis language as a single choice applied uniformly. This assumption limits the most general case. Within one task some sub-relations are relational, concerning which entity stands in which relation to which and under what condition; some are numeric, an offset, a length, a scale factor; and some are procedural, in that the output of one stage is the input of the next. Each has its own natural language. The choice among them is not only a matter of convenience or of search cost, and this is where the criterion re-enters. The language is the representation the system will execute when a prediction is made, so forcing a relational or a procedural sub-relation into a continuous piecewise-affine surrogate does not merely make it expensive to express, it makes it impossible to express exactly: such a surrogate is not structurally equivalent to a quantified rule, which must hold of constants it was never fitted on, nor to an ordered succession of states, which has no representation at all in a map from inputs to outputs. Choosing the language is therefore choosing which sub-relations the system can compute exactly rather than approximate, and a sub-relation placed in the wrong language is outside our criterion (Criterion 1) before any learning begins. Forcing a single language to carry all three is paid for in description length, and description length is the exponent of the search. A numeric dependency such as “the displacement equals the entity’s width less one” occupies a single literal when the vocabulary contains a bounded algebraic form, and otherwise requires either a chain of literals or a distinct constant for every value the quantity may take. A multistage transformation occupies one short clause per stage when the search may pose each stage as its own problem, and otherwise becomes a single clause whose length is the sum of the stages’, or a recursive clause, and learning recursive clauses is considerably more expensive [20]. Stated as complexity, if a task decomposes into S stages each solvable at length L over a vocabulary of size V , a monolithic search is O(V SL ) where a staged search is O(S ·V L ). When the stages are instances of one step applied repeatedly, a recursive program of a base clause and a recursive clause, each of length at most L, can replace them, so the candidates number O(V 2L ); but each candidate must be unfolded to depth S to be checked, and since termination of a candidate recursive program is undecidable in general, the search must also impose a depth bound, which gives O(S · V 2L ), a factor V L above the staged search and available only when the stages are homogeneous. The reduction from monolithic to staged search is not a constant factor, and it is the difference between a search that terminates within a budget and one that does not. Two of the three languages carry a further requirement that is not merely a matter of vocabulary size. Take the relational part first. Its natural language is a logic programming one, and the reason is Kowalski’s decomposition of a program into logic and control [53]. A synthesizer coming up with relational programs in an imperative or functional language must produce both halves: the declarative content of the target relation, and an execution plan that iterates over entities, binds variables, orders tests, routes branches and unwinds state when a partial construction fails. The search space is the product of the two, and the second factor carries no information about the task. A logic programming language supplies the control half once, as the fixed semantics of resolution, unification and backtracking, so the synthesized

object is the logic alone. Two consequences follow. Constraints that hold simultaneously are expressed by conjunction rather than by sequencing: where a functional composition f (g(x)) imposes an order the problem does not impose, a conjunction of literals asks only for a binding satisfying all of them at once. And context dependence is expressed by multiple clauses for the same head rather than by explicit branching, so contexts add to the search space rather than multiplying it, and a clause whose guards are unmet simply fails and yields to the next. Take next the procedural part, where the requirement is sharper, because it is a limitation of FOL itself rather than of a particular programming language. Pure FOL is atemporal: it states what holds, not what happens next, and has no native notion of a state that is superseded. A transformation whose stages must run in order cannot be stated as an ordinary clause. It can be forced into one, by reifying time and quantifying over situations in the manner of the Situation Calculus [9], or by resorting to extra-logical database side effects, and both routes lengthen the clause with machinery encoding the passage of state rather than the content of the transformation. The alternative is to leave the logic atemporal and place the sequencing outside it, in a procedure that applies an induced program, observes the resulting state, and poses the next stage as a fresh induction problem against that state, which is exactly what we did with our proposed system, ILPAR [74]. This converts the exponent above into a coefficient, and it has an information-theoretic reading. Universal induction identifies the best explanation of the data with the shortest program that generates it [15], and searching directly for that program is intractable. The theory of incremental compression [38] observes that the tractable form of the same objective is a succession of partial compressions, each removing some residual structure and handing the remainder to the next, and a procedural loop over atemporal inductions is that construction carried out in FOL. Domains with this character are not rare: physical simulation, visual reasoning benchmarks built from staged spatial edits [16], and matrix-completion tests of fluid intelligence such as Raven’s Progressive Matrices [14] all present transformations whose stages are ordered and whose intermediate states are never observed. Three costs attach and should not be glossed over. Something must perform the decomposition, and that something is itself an inductive bias, so an incorrect decomposition is not repaired by correct per-part biases downstream of it. The parts must interoperate, since the output of one paradigm has to be a legal input to another. And composing languages enlarges the vocabulary, so the gain depends on the program length L shrinking faster than the program vocabulary V grows, which is an empirical claim about a domain and not a theorem. What this analysis yields is a specification of four parts rather than a system. 1. A relational core expressed in a logic programming language, supplying the universal quantification and dynamic variable binding that §4 showed the connectionist paradigm lacks, in a form where the synthesized object is the logic and the control is baked into the interpreter. 2. A bounded algebraic primitive for numeric dependencies, so a quantitative relation between a target quantity and a property of the situation costs one literal rather than an enumeration of constants. 3. An explicit procedural stage structure external to the logic, so state transformation is carried by sequence rather than clause length, which is what converts the exponent into a coefficient and makes incremental compression available in a FOL setting. 4. A vocabulary chosen on principled grounds rather than for convenience, since it is the vocabulary that renders the induction well posed at all. One further element is permitted by this specification, because our criterion (Criterion 1) is what licenses it. A learned model may propose or rank candidate fragments during search without appearing anywhere in the inference path of the induced hypothesis, so search guidance is a legitimate place for a 28

neural component in a way that inference is not, as explained in §5.3. The extrapolation guarantee is a property of what is executed, and a Neural Network that only influences which candidates are examined leaves that property untouched.

8.4

The evidence from abstraction benchmarks

The evidence from ARC-AGI, the benchmark built to measure exactly the OOD generalization capacity [16], is relevant here, because the distinction that organizes it is the one this paper is about. ARC-AGI state-of-the-art approaches divide into induction, which infers a latent function or relation and then applies it, and transduction, which predicts the test output directly without ever forming a reusable rule [60]. A transductive system consults a fitted model at inference by construction: whatever it has learned is never separated from the act of predicting, so there is nothing that could be executed exactly. Transductive systems have led the reported private-set results [17], and we address the strongest statement of the case for them directly. Cole and Osman [21] argue that “fully committing to deep learning’s capacity to acquire novel abstractions yields state-of-the-art performance on ARC,” and their methodological claim is the interesting part: that both “the neural network and the optimizer (rather than just a pre-trained network)” should be treated “as integral components of the inference process.” Test-time fine-tuning is therefore not the case §7 argues against. It is neither a human injecting structure in advance nor a frozen approximation consulted blindly, but a fresh approximation fitted per task, which is a third position our framing must accommodate rather than dismiss. What it does not do is produce anything that could be executed exactly: the artefact it fits is a set of weights, consulted at inference time, so it falls on the approximate side of Criterion 1 however well it scores. The comparison that bears directly on our criterion has been run. Li et al. [60] train inductive and transductive models on the same problems with the same architecture, differing only in whether a Python program is produced and executed or an output is predicted, and find that the two “solve different kinds of test problems.” Inductive program synthesis “excels at precise computations, and at composing multiple concepts,” while transduction “succeeds on fuzzier perceptual concepts.” This is our criterion’s prediction, arrived at independently: exact execution is what buys precise computation and composition, since a rule composes with another rule only if each computes what it says, whereas an approximation composed with an approximation degrades. Their finding that ensembling the two approaches human-level performance is equally consistent with the position taken here, and with the specification of §8.3: the two do different jobs and a system may want both, placed where each is appropriate. We therefore make no claim that symbolic induction alone is empirically sufficient, and we attach no weight to any particular standing, which is a moving quantity and a poor foundation for an argument about representation. The claim is that where a system generalizes to a novel regime something in it computed the mechanism exactly, and that the open question is whether that something was induced by the system or supplied by a person. The prediction that follows is about problem classes rather than totals: the transductive share should concentrate where approximation suffices, and a composition boundary should appear where it does not, which is what Li et al. [60] report and what further work of that design could test directly. The defining theme of the ARC-AGI 2025 technical report [17] is the refinement loop, “a per-task iterative program optimization loop guided by a feedback signal”, with the strongest instances evolving program solutions in Python. A per-task search for a program that is then executed is symbolic induction, whatever the search is made of.

Scope, Limitations, and Refutation Conditions

Our criterion is not a theorem. We have not proved that exactness is necessary for OOD generalization; we have argued that it predicts the observed pattern of successes and failures better than Neural Network architecture, capacity, data, or scale, and that it sorts neuro-symbolic systems in a way their surface taxonomy [49] does not. The unification of the relational and continuous faces is a conceptual claim, and its parts are established results due to the work of others. The continuous analysis is scoped to unbounded-output regression networks, for the reasons in §3.6. The relational analysis is scoped to DL architectures representing entities as free per-entity parameters, and is false outside that scope, as §4.5 states. The complexity statement in §8.3 assumes a bias decomposition is available and correct, which is itself a bias and not a given. What would refute the position. A fully differentiable system that consults a fitted approximation at inference and nonetheless exhibits exact, non-degrading agreement with a generating mechanism on shifts chosen adversarially, in the case where this mechanism is not a piecewise-linear function, which is the form a piecewise-affine Neural Network represents exactly. Or a demonstration that architectural exactness accumulates across domains without per-domain human specification, which would undercut §7. Or a scaling result in which OOD generalization on a mechanism outside the representable class improves with data or parameters at a rate that does not vanish, which would contradict the representational reading directly.

Conclusion

Deep networks do not always fail at extrapolation. They fail at extrapolating mechanisms they cannot represent exactly, which is the most common case, but they succeed, indefinitely far from any data, on the mechanisms they can. The same statement covers the relational case once it is scoped correctly: an architecture whose representation of an entity is a fitted parameter cannot apply a quantified rule to an entity it never fitted, and an architecture that represents bindings can. What unites these is not a shared pathology but a shared boundary, the boundary of exact representability, and what matters at inference is that the operation performed computes the intended relation rather than approximating it where the data happened to be. That criterion is more permissive than the usual symbolic prescription and more demanding than the usual neuro-symbolic one. It permits continuous arithmetic, graded semantics, and approximate search. It refuses only the consultation of a fitted continuous approximation at the moment an inference is made. And it settles more than accuracy: the boundary of what a model can know about its own predictions is the same boundary, which is why abstention cannot be estimated onto a hypothesis class that cannot state what is being abstained from. The uncomfortable truth for Machine Learning is that most of the exactness in contemporary systems was put there by people. The common repairs, from hardcoded symmetries to external memory to symplectic structure, reach exactness only because a person injected a representation structurally equivalent to the process that generated the data. That is not an argument against building it in. It is an argument for the harder project of inducing it, because injected structure is bounded by what its designer anticipated and induced structure is not. Passing that bound requires architectures able to induce exact representations autonomously, rather than fitting continuous surrogates constrained to representations such as the piecewise-affine maps of MLPs, which are incorrect unless the generating mechanism is itself of that form, and it rarely is. Such surrogates approximate within the training distribution. Their residual error rarely vanishes on the support, and even where a sufficiently flexible approximant drives it to the arithmetic floor 30

there, as a high-degree polynomial can, it diverges outside the support and compounds under composition.

Mathematical derivations

Four results are stated in the body without their algebra, to not interrupt the argument. They are collected here so that a reader who wants to check them does not have to reconstruct them.

A.1

The chord residual and the factor of two (§3.2)

Take f (x) = x2 and an interval [a, b] of width h = b − a. The affine interpolant through the endpoints is L(x) = (a + b)x − ab, and L(x) − x2 = −x2 + (a + b)x − ab = (x − a)(b − x), which is zero exactly at the two nodes, positive strictly between them, and maximal at the midpoint, where it equals (h/2)2 = h2 /4. Since f ′′ = 2, that is h2 f ′′ /8, the bound quoted in §3.2, and it is attained rather than merely bounded. The residual vanishes only at the nodes, so interpolating the samples exactly leaves it everywhere else on the interval. The best affine approximant on [a, b] is not the chord. By the Chebyshev equioscillation theorem the best uniform approximant of degree one is characterized by an error that equioscillates at three points, which here is L displaced downward by half the maximum chord deviation: the displaced map errs by h2 /8 below the chord’s nodes and h2 /8 above it at the midpoint, with equal magnitude and alternating sign at a, (a + b)/2 and b. Its maximum error is therefore h2 /8 = h2 f ′′ /16, half the chord’s. For a general twice-differentiable f the same two statements hold with max | f ′′ | in place of f ′′ , giving h2 max | f ′′ |/8 and h2 max | f ′′ |/16. Panel (c) of Figure 1 plots both curves against the measured residuals.

A.2

Two GELU units of opposite input-weight sign (§3.4)

Write Φ for the standard normal distribution function and erf for the error function, erf(z) = cumulative √ R z −t 2 2 1 √ e dt, so that Φ(z) = 2 1 + erf(z/ 2) . A GELU unit is GELU(x) = xΦ(x). For the normalized π 0 pair, two units with input weights +1 and −1 and output weights both 1, √ GELU(x) + GELU(−x) = xΦ(x) − xΦ(−x) = x (2Φ(x) − 1) = x erf x/ 2 , using Φ(−z) = 1 − Φ(z) at the second step and the definition of erf at the third. Since erf(z) → ±1 as z → ±∞, the sum is asymptotic to |x|, so it grows without bound on both tails although each unit is asymptotically zero on one of them. A general pair a1 GELU(w1 x) and a2 GELU(w2 x) with w2 = −w1 scales the two tails separately, with asymptotic slopes a1 w1 and a2 w2 , which is the decomposition measured in panel (c) of Figure 3.

A.3

The determined fraction on the radial chirp (§6.2)

Training covers r ∈ [1, 2.2], so u = x2 + y2 ranges over [1, 4.84]; the radial query region is r ∈ [2.2, 4], so u ranges over [4.84, 16]. The recovered expression is 2π-periodic in u, so a query at u is determined by the training data exactly when u mod 2π falls in the training interval. The training interval has length 3.84, which is 0.611 of a period, but that is not the determined fraction, because the query interval has length 11.16, which is 1.776 periods and not a whole number of them, 31

so the folded copies of the training interval do not tile it. Two copies meet the query interval: [1 + 2π, 4.84+2π] = [7.283, 11.123], which lies inside it and contributes its full 3.84, and [1+4π, 4.84+4π] = [13.566, 17.406], which is truncated at u = 16 and contributes 2.434. The determined length is 6.274 out of 11.16, or 56.2%. Points drawn uniformly by area give u uniformly, since u = r2 gives dA = r dr dθ = 21 du dθ , which does not depend on r. The geometric fraction is therefore what a finite sample estimates, p and the count over the sampled queries is 56.3%. The binomial standard deviation of such an estimate is 0.562 · 0.438/n, about one point at n = 2000, so the two numbers agree.

A.4

The propagation bound (§5.3)

Let g1 , . . . , gn be the exact stages of a pipeline and ĝ1 , . . . , ĝn the fitted stages standing in for them. Two quantities describe stage k: a uniform error εk ≥ 0 and a Lipschitz constant Lk ≥ 0 for the exact stage, combined in the single hypothesis ĝk (u) − gk (v) ≤ εk + Lk |u − v|

for all u, v,

which says that the fitted stage is wrong by at most εk on an input the exact stage would have received, and that the exact stage magnifies a discrepancy it receives by at most Lk . Write xk = gk (xk−1 ) and x̂k = ĝk (x̂k−1 ) from a common input x0 = x̂0 , and let ek = |x̂k − xk |. The hypothesis applied with u = x̂k−1 and v = xk−1 gives the recursion e0 = 0, ek ≤ εk + Lk ek−1 , and unrolling it by induction on k gives en ≤ ∑ εk ∏ L j , k≤n

j>k

since the inductive step ek ≤ εk + Lk ∑i<k εi ∏i< j<k L j = ∑i≤k εi ∏i< j≤k L j absorbs the new factor Lk into every earlier product. Three consequences follow directly. If every εk is zero the bound is zero whatever the constants, which is the statement that exactness composes and needs no Lipschitz hypothesis at all; the bound is monotone in each εk , so a stage that contributes no error contributes nothing to the composite; and if every downstream constant is at least c, the bound grows by at least a factor of c per stage, which is the compounding claim in the body. Nothing in the argument uses continuity, differentiability or dimension, and |u − v| may be read as any metric.

References [1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. ISBN 0201537710. [2] Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information Processing Systems (NeurIPS), 2022. [3] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean-Christophe Gagnon-Audet, Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-ofdistribution generalization, 2021. URL https://arxiv.org/abs/2106.06607.

[4] Aharon Azulay and Yair Weiss. Why do deep convolutional networks generalize so poorly to small image transformations? Journal of Machine Learning Research, 20(184):1–25, 2019. [5] Samy Badreddine, Artur d’Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence, 303:103649, 2022. doi: 10.1016/j.artint.2021.103649. [6] Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations (ICLR), 2020. [7] Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957. [8] Emily M. Bender and Alexander Koller. Climbing towards NLU: On meaning, form, and understanding in the age of data. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL), pages 5185–5198, 2020. doi: 10.18653/v1/2020.acl-main.463. [9] Patrick Blackburn, Jaap Kamps, and Maarten Marx. Situation calculus as hybrid logic: First steps. Lecture Notes in Computer Science, pages 253–260, 2001. [10] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26 (NeurIPS), pages 2787–2795, 2013. [11] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021. URL https://arxiv.org/abs/2104. 13478. [12] Steven L. Brunton, Joshua L. Proctor, and J. Nathan Kutz. Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proceedings of the National Academy of Sciences, 113(15):3932–3937, 2016. doi: 10.1073/pnas.1517384113. [13] Declan Campbell, Sunayana Rane, Tyler Giallanza, Nicolò De Sabbata, Kia Ghods, Amogh Joshi, Alexander Ku, Steven M. Frankland, Thomas L. Griffiths, Jonathan D. Cohen, and Taylor W. Webb. Understanding the limits of vision language models through the lens of the binding problem. In Advances in Neural Information Processing Systems (NeurIPS), 2024. arXiv:2411.00238. [14] Patricia A. Carpenter, Marcel A. Just, and Peter Shell. What one intelligence test measures: A theoretical account of the processing in the Raven progressive matrices test. Psychological Review, 97(3):404–431, 1990. [15] Gregory J. Chaitin. Algorithmic information theory. In Information, Randomness and Incompleteness, pages 33–37. World Scientific, 1987. [16] François Chollet. On the measure of intelligence, 2019. URL https://arxiv.org/abs/ 1911.01547. [17] François Chollet, Mike Knoop, Gregory Kamradt, and Bryan Landers. Arc prize 2025: Technical report, 2026. URL https://arxiv.org/abs/2601.10904. [18] Taco Cohen and Max Welling. Group equivariant convolutional networks. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 2990–2999, 2016.

[19] Taco S. Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge equivariant convolutional networks and the icosahedral CNN. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019. [20] William W. Cohen. Pac-learning recursive logic programs: Negative results. Journal of Artificial Intelligence Research, 2:541–573, 1995. doi: 10.1613/jair.1917. [21] Jack Cole and Mohamed Osman. Don’t throw the baby out with the bathwater: How and why deep learning for ARC, 2025. URL https://arxiv.org/abs/2506.14276. [22] Miles Cranmer. Interpretable machine learning for science with PySR and SymbolicRegression.jl. arXiv preprint arXiv:2305.01582, 2023. URL https://arxiv.org/abs/2305.01582. [23] Miles Cranmer, Sam Greydanus, Stephan Hoyer, Peter Battaglia, David Spergel, and Shirley Ho. Lagrangian neural networks. ICLR 2020 Deep Differential Equations Workshop, 2020. URL https://arxiv.org/abs/2003.04630. [24] Andrew Cropper and Sebastijan Dumančić. Inductive logic programming at 30: A new introduction, 2020. URL https://arxiv.org/abs/2008.07912. [25] Andrew Cropper and Rolf Morel. Learning programs by learning from failures. Machine Learning, 110(4):801–856, 2021. doi: 10.1007/s10994-020-05934-z. [26] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303–314, 1989. doi: 10.1007/BF02551274. [27] Artur d’Avila Garcez and Luis C. Lamb. Neurosymbolic AI: the 3rd wave. Artificial Intelligence Review, 56(11):12387–12406, 2023. doi: 10.1007/s10462-023-10448-w. [28] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. ProbLog: A probabilistic Prolog and its application in link discovery. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pages 2462–2467, 2007. [29] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In International Conference on Learning Representations (ICLR), 2019. [30] Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the Chomsky hierarchy. In International Conference on Learning Representations (ICLR), 2023. URL https://arxiv.org/abs/2207.02098. arXiv:2207.02098. [31] Huiqi Deng, Qihan Ren, Hao Zhang, and Quanshi Zhang. Discovering and explaining the representation bottleneck of DNNs. In International Conference on Learning Representations (ICLR), 2022. arXiv:2111.06236. [32] Pedro Domingos. Tensor logic: The language of AI. arXiv preprint arXiv:2510.12269, 2025. URL https://arxiv.org/abs/2510.12269. [33] Yihe Dong, Jean-Baptiste Cordonnier, and Andreas Loukas. Attention is not all you need: Pure attention loses rank doubly exponentially with depth. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 2793–2803, 2021.

[34] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers on compositionality. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2023. [35] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B. Tenenbaum. DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning. arXiv preprint arXiv:2006.08381, 2020. URL https://arxiv.org/abs/2006.08381. [36] Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1–64, 2018. [37] Jerry A. Fodor and Zenon W. Pylyshyn. Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1-2):3–71, 1988. doi: 10.1016/0010-0277(88)90031-5. [38] Arthur Franz, Victoria Gogulya, and Michael Löffler. WILLIAM: A monolithic approach to AGI. In International Conference on Artificial General Intelligence, pages 33–43. Springer, 2019. [39] Octavian-Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Advances in Neural Information Processing Systems 31 (NeurIPS), 2018. [40] Alex Graves. Adaptive computation time for recurrent neural networks, 2016. URL https:// arxiv.org/abs/1603.08983. [41] Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines, 2014. URL https:// arxiv.org/abs/1410.5401. [42] Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka GrabskaBarwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, Adrià Puigdomènech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471–476, 2016. doi: 10.1038/nature20101. [43] Klaus Greff, Sjoerd van Steenkiste, and Jürgen Schmidhuber. On the binding problem in artificial neural networks, 2020. URL https://arxiv.org/abs/2012.05208. [44] Sam Greydanus, Misko Dzamba, and Jason Yosinski. Hamiltonian neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019. URL https://arxiv.org/abs/ 1906.01563. [45] Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf. Why ReLU networks yield highconfidence predictions far away from the training data and how to mitigate the problem. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 41–50, 2019. doi: 10.1109/CVPR.2019.00013. [46] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359–366, 1989. doi: 10.1016/0893-6080(89)90020-8. [47] Norman P. Jouppi, Cliff Young, Nishant Patil, David Patterson, et al. In-datacenter performance analysis of a tensor processing unit. In Proceedings of the 44th Annual International Symposium on Computer Architecture (ISCA), 2017. doi: 10.1145/3079856.3080246. 35

[48] Katie Kang, Amrith Setlur, Claire Tomlin, and Sergey Levine. Deep neural networks tend to extrapolate predictably, 2024. URL https://arxiv.org/abs/2310.00873. [49] Henry A. Kautz. The third AI summer: AAAI Robert S. Engelmore memorial lecture. AI Magazine, 43(1):93–104, 2022. doi: 10.1609/aimag.v43i1.19122. [50] Youngsung Kim. Standard neural computation alone is insufficient for logical intelligence, 2025. URL https://arxiv.org/abs/2502.02135. [51] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. [52] Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA, 2009. ISBN 9780262013192. [53] Robert Kowalski. Algorithm = logic + control. Communications of the ACM, 22(7):424–436, 1979. [54] John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992. [55] William La Cava, Patryk Orzechowski, Bogdan Burlacu, Fabrício Olivetti de França, Marco Virgolin, Ying Jin, Michael Kommenda, and Jason H. Moore. Contemporary symbolic regression methods and their relative performance. In Advances in Neural Information Processing Systems, Datasets and Benchmarks Track, 2021. [56] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems (NeurIPS), 2017. URL https://arxiv.org/abs/1612.01474. [57] Mark Law, Alessandra Russo, and Krysia Broda. Inductive learning of answer set programs. In European Conference on Logics in Artificial Intelligence (JELIA), pages 311–325. Springer, 2014. [58] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. In Advances in Neural Information Processing Systems (NeurIPS), 2018. URL https://arxiv.org/abs/1807.03888. [59] Seungpil Lee, Woochang Sim, Donghyeon Shin, Wongyu Seo, Jiwon Park, Seokki Lee, Sanha Hwang, Sejin Kim, and Sundong Kim. Reasoning abilities of large language models: In-depth analysis on the Abstraction and Reasoning Corpus. ACM Transactions on Intelligent Systems and Technology, 2025. doi: 10.1145/3712701. [60] Wen-Ding Li, Keya Hu, Carter Larsen, Yuqing Wu, Simon Alford, Caleb Woo, Spencer M. Dunn, Hao Tang, Michelangelo Naim, Dat Nguyen, Wei-Long Zheng, Zenna Tavares, Yewen Pu, and Kevin Ellis. Combining induction and transduction for abstract reasoning. arXiv preprint arXiv:2411.02272, 2024. URL https://arxiv.org/abs/2411.02272. [61] Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. DeepProbLog: Neural probabilistic logic programming. In Advances in Neural Information Processing Systems 31 (NeurIPS), 2018. [62] Gary Marcus. Deep learning: A critical appraisal, 2018. URL https://arxiv.org/abs/ 1801.00631. 36

[63] Gary F. Marcus. Rethinking eliminative connectionism. Cognitive Psychology, 37(3):243–282, 1998. [64] Gary F. Marcus. The Algebraic Mind: Integrating Connectionism and Cognitive Science. MIT Press, 2001. [65] John McCarthy. Epistemological challenges for connectionism. Behavioral and Brain Sciences, 11 (1):44, 1988. [66] Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. GSM-symbolic: Understanding the limitations of mathematical reasoning in large language models, 2024. URL https://arxiv.org/abs/2410.05229. [67] Guido F. Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems 27 (NeurIPS), pages 2924–2932, 2014. [68] Stephen Muggleton. Inductive logic programming. New Generation Computing, 8(4):295–318, 1991. [69] Stephen Muggleton. Inverse entailment and progol. New Generation Computing, 13(3-4):245–286, 1995. doi: 10.1007/BF03037227. [70] Stephen H. Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited. Machine Learning, 100(1):49–73, 2015. [71] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua V. Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift. In Advances in Neural Information Processing Systems (NeurIPS), 2019. URL https://arxiv.org/abs/1906.02530. [72] Filipe Marinho Rocha, Vítor Santos Costa, and Luís Paulo Reis. Overcoming reinforcement learning limits with inductive logic programming. In Trends and Innovations in Information Systems and Technologies (WorldCIST 2020), volume 1160 of Advances in Intelligent Systems and Computing, pages 414–423. Springer, Cham, 2020. doi: 10.1007/978-3-030-45691-7_38. [73] Filipe Marinho Rocha, Vítor Santos Costa, and Luís Paulo Reis. From reinforcement learning towards artificial general intelligence. In Trends and Innovations in Information Systems and Technologies (WorldCIST 2020), volume 1160 of Advances in Intelligent Systems and Computing, pages 401–413. Springer, Cham, 2020. doi: 10.1007/978-3-030-45691-7_37. [74] Filipe Marinho Rocha, Inês Dutra, Vítor Santos Costa, and Luís Paulo Reis. Program synthesis using inductive logic programming for the abstraction and reasoning corpus. Intelligenza Artificiale, 19: 85–101, 2025. doi: 10.1177/17248035251363178. [75] Filipe Marinho Rocha, Inês Dutra, Vítor Santos Costa, and Luís Paulo Reis. Certifying extrapolation from the training set alone: Leverage blocks, depth, and a precision floor, 2026. Manuscript in preparation. [76] Adam Santoro, David Raposo, David G. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Advances in Neural Information Processing Systems 30 (NeurIPS), pages 4967–4976, 2017.

[77] Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference (ESWC), pages 593–607. Springer, 2018. doi: 10.1007/978-3-319-93417-4_38. [78] Michael Schmidt and Hod Lipson. Distilling free-form natural laws from experimental data. Science, 324(5923):81–85, 2009. doi: 10.1126/science.1165893. [79] Gideon Schwarz. Estimating the dimension of a model. The Annals of Statistics, 6(2):461–464, 1978. doi: 10.1214/aos/1176344136. [80] Vincent Sitzmann, Julien N. P. Martel, Alexander W. Bergman, David B. Lindell, and Gordon Wetzstein. Implicit neural representations with periodic activation functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020. URL https://arxiv.org/abs/2006. 09661. [81] Paul Smolensky. Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial Intelligence, 46(1–2):159–216, 1990. [82] Yiyou Sun, Yifei Ming, Xiaojin Zhu, and Yixuan Li. Out-of-distribution detection with deep nearest neighbors. In International Conference on Machine Learning (ICML), 2022. URL https:// arxiv.org/abs/2204.06507. [83] Komal K. Teru, Etienne Denis, and William L. Hamilton. Inductive relation prediction by subgraph reasoning. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of PMLR, pages 9448–9457, 2020. arXiv:1911.06962. [84] Silviu-Marian Udrescu and Max Tegmark. AI Feynman: A physics-inspired method for symbolic regression. Science Advances, 6(16):eaay2631, 2020. URL https://arxiv.org/abs/1905. 11481. [85] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30 (NeurIPS), pages 5998–6008, 2017. [86] Soledad Villar, David W. Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: Equivariant machine learning, structured like classical physics. Advances in Neural Information Processing Systems (NeurIPS), 2021. URL https://arxiv.org/abs/2106.06610. [87] Marco Virgolin and Solon P. Pissis. Symbolic regression is NP-hard. Transactions on Machine Learning Research, 2022. URL https://openreview.net/forum?id=LTiaPxqe2e. [88] Taylor W. Webb, Ishan Sinha, and Jonathan D. Cohen. Emergent symbols through binding in external memory. In International Conference on Learning Representations (ICLR), 2021. URL https: //arxiv.org/abs/2012.14601. arXiv:2012.14601. [89] Taylor W. Webb, Steven M. Frankland, Awni Altabaa, Simon Segert, Kamesh Krishnamurthy, Declan Campbell, Jacob Russin, Tyler Giallanza, Randall O’Reilly, John Lafferty, and Jonathan D. Cohen. The relational bottleneck as an inductive bias for efficient abstraction. Trends in Cognitive Sciences, 28(9):829–843, 2024. doi: 10.1016/j.tics.2024.04.001. arXiv:2309.06629. [90] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations (ICLR), 2020. 38

[91] Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94: 103–114, 2017. doi: 10.1016/j.neunet.2017.07.002. [92] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 11975–11986, 2021. [93] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization, 2016. URL https://arxiv.org/abs/ 1611.03530.

Record · ID 1028684 · SHA-256 a5a6efa914e55a4e
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.