Filipe Marinho Rocha, Inês Dutra, Vítor Santos Costa, Luís Paulo Reis
5 min
This paper proposes a new criterion for out-of-distribution (OOD) generalization: a model generalizes successfully only if it executes a representation structurally equivalent to the data-generating mechanism. The authors argue that current deep learning architectures fail OOD not because of insufficient scale or data, but because they rely on fitted approximations—such as piecewise-affine maps in MLPs—that are only valid within the training distribution. When these models encounter OOD data, they continue to apply these approximations, leading to divergence or incorrect relational reasoning.
The authors unify two well-documented failure modes of deep networks under this single representational shortfall:
The paper introduces the criterion of "Exactness at Inference," which requires that the operation performed by the model computes the intended function or relation exactly. Crucially, this does not require discrete representations; a sum-product tensor contraction computing an exact marginal is continuous-valued but exact, whereas a neural network thresholded to a hard label is discrete-valued but approximate. The authors demonstrate that architectures like differentiable ILP and zero-temperature Tensor Logic pass this criterion because they extract or execute discrete structures, whereas Logic Tensor Networks fail because they rely on continuous surrogates.
This work provides a diagnostic tool for predicting where architectures will fail before they are even trained. By analyzing the "inference path" of a quantity, researchers can determine if a fitted component (like an MLP) is involved in its computation. If it is, the quantity will inherit the limits of that fitted component. The authors argue that current successes in OOD generalization are largely due to human designers manually injecting exact structures—such as symmetries or indirection—into architectures. The challenge for future AI is to move beyond fitting surrogates and toward inducing exact representations autonomously.
A model generalizes outside its training distribution only when it computes a representation structurally equivalent to the generating mechanism, not an approximation fitted to it. Such equivalence is necessary for exactness in and out of distribution, and extrapolation is governed by this exactness at inference, whatever its realization. Tensor Logic shows this: a zero-temperature contraction is equivalent to discrete logic, deducing in place with no artefact extracted, its tensors Boolean, its embeddings orthonormal, only its arithmetic continuous. Lacking infinite recursion it reaches Datalog, not Prolog, and though exact over closed domains it needs external memory to bind a novel entity. The criterion needs neither a discrete representation nor an extracted expression, and constrains inference, not training: an exact marginal in $[0,1]$ passes, a Neural Network thresholded to a hard label does not. Logic Tensor Networks fail it, while differentiable ILP and Tensor Logic at $T=0$ pass. Piecewise-affine extrapolation divergence and an inability to bind novel entities are two faces of a shortfall in exact representability. For hybrid architectures, a propagation rule follows: the output inherits the bounds of every fitted estimator on its path, explaining which axes fail in equivariant models and the ARC-AGI induction/transduction split. Only an exact hypothesis class certifies what the training data leave underdetermined: on a law-derived partition it finds the $56.3\%$ of distant queries that are answerable, which ensembles meet with false confidence and distance metrics rank backwards. Common inductive biases, from symmetries to memory, reach exactness only because humans inject them, an argument for inducing exact representations rather than fitting surrogates whose residuals, even at the arithmetic floor in training, diverge outside the data and compound under composition.
Alex: [reflective] So the next problem isn't more data — it's architectures that can find that structure themselves, rather than being handed it. [[RP_SECTION:uncertainty-and-epistemic-failure|Uncertainty and epistemic failure]]
Alex: [curious, leaning in] Does this also explain why standard uncertainty estimates — ensemble disagreement, that kind of thing — tend not to warn you when a model is about to fail badly?
Sam: [steady, matter-of-fact] It does. Those estimators are bolted on after the fact, onto a model that's already committed to a flawed representation. If the model never consults an exact hypothesis at inference time, it has no internal signal for what it doesn't know — it's just scoring a continuous surrogate and reporting confidence in that score.
Alex: [slower, processing] So the uncertainty number reflects properties of the training data, not anything the model actually understands. What changes with a search-based system? [[RP_SECTION:search-based-hypothesis-testing|Search based hypothesis testing]]
Sam: [building momentum] That's where what the paper calls the epistemic corollary shows up. Give the system an explicit hypothesis class — an enumerative search over candidate physical laws, say — and it can actually know whether it's found the right structure. In their radial chirp experiment, the search recovers the true function with a residual close to zero, and the winning hypothesis beats the runner-up by orders of magnitude.
Alex: [curious] Is that one case doing a lot of work, or is it representative of something broader?
Sam: [measured] Worth flagging — it's a single worked demonstration, not a benchmark sweep. The authors present it to illustrate the mechanism, not to establish base rates across problems. The ARC-AGI comparison is the broader evidence for the general claim about compositional structure; the certificate argument itself leans on this one clean case.
Alex: [analytical edge] Got it. So within that case, the gap between first and second place is doing the work of a confidence signal — if the system's unsure, the candidates should stay bunched together.
Sam: [measured, precise] Exactly that. When the search lands on the correct law, the margin over the next-best candidate is large. Strip the necessary operator out of the search space, and the candidates cluster together while the residual stays high — the system's version of admitting it hasn't found an answer. It's not just a prediction; it's a certificate of how well that answer explains the data.
Alex: [deliberate] That's a genuinely different epistemic posture. A neural network hands you a point prediction with no sense of whether its own structure is valid. A search-based system can tell you if the hypothesis it landed on is even plausible.
Sam: [nodding, direct] And it changes what failure looks like. In a fitted model, failure is graded and silent — it drifts away from the truth without ever flagging it. In a search-based system, failure is discrete and inspectable: you can see the residual sitting high and the candidates left unseparated. [[RP_SECTION:accountability-in-model-architecture|Accountability in model architecture]]
Alex: [reflective] So the goal isn't just more accurate models — it's models that are accountable to the structures they use. If you can't inspect the inference path, you're just trusting the output.
Sam: [concluding with quiet confidence] That's the position the paper stakes out. Move away from architectures that hide their logic inside continuous surrogates, toward systems that execute the mechanism itself. That's the route the authors see toward generalization that holds up the way a physical law does — not just on the data you happened to train on.