PaperlayerView exact revision on arXiv

Source-linked AI summary

The Structure Gap: When More Data Cannot Replace Structured Reasoning

Kheer Sagar Patel, Mojtaba Soltanalian

arXiv:2610.37523v1cs.LGcs.AI

TL;DR

The paper asks whether enough data and capacity can make known task structure optional, focusing on finite-data identification rather than representational capacity. It defines the structure gap and analyzes it through proofs and experiments. In a favorable linear setting, a dense empirical learner has greater expected risk than the known-operator solver at every finite sample size, approaching it only asymptotically.

  • Problem

    Even when a dense network can represent a structured map, finite examples may not identify it, certify its behavior on unseen regimes, or recover its generating law.

    Source: Introduction · p. 1

  • Method

    The paper defines structure-encoded problems and the structure gap, then proves lower bounds and studies a known-operator linear setting alongside numerical experiments.

    Source: Introduction · p. 1, Known-Operator Solvers and Asymptotic… · p. 3

  • Results

    For every finite N > m + 1 with m > 0 and tr(Σe) > 0, the dense empirical learner has strictly greater expected risk than the known-operator solver, and approaches it only as N →∞.

    Source: Known-Operator Solvers and Asymptotic… · p. 3

  • Takeaways & Limitations

    When correct structure is available in compact form, relearning its consequences from examples imposes an avoidable finite-data burden.

    Source: Introduction · p. 2

    The claim is class-relative to correct structure; wrong, incomplete, or costly-to-specify structure can make structure-aware methods biased or brittle.

    Source: Introduction · p. 2, Limitations · p. 5

Abstract

from arXiv · show

A persistent belief in modern AI is that sufficiently large learners trained on sufficiently much data can make explicit domain knowledge optional. This paper examines a limitation of that belief. We define structure-encoded problems: tasks whose input-output map is determined, or sharply constrained, by known structure such as a solver, symmetry group, graph, physical law, measurement operator, grammar, combinatorial search space, or optimization objective. For such tasks, the central question is not expressivity--a dense neural network may contain the desired map--but finite-data identification, extrapolation, and certification. We introduce the structure gap: the finite-resource gap between a method that receives the governing structure and a learner that receives only examples. The strongest useful form of the claim is asymptotic rather than absolute: structure-agnostic learning may approach a structured solver as coverage grows, but every finite dataset can leave residual uncertainty that the structure resolves by construction. We prove this exactly for a Gaussian inverse problem: the known-operator Wiener solver attains Bayes risk, while the dense empirical learner in the correct linear class has persistent expected excess risk. We also prove a cell-coverage lower bound and an unobserved-orbit non-identifiability result. Controlled experiments in known-operator inversion, sparse recovery, and graph reachability with size extrapolation instantiate the mechanisms. When validated structure is available, it can constrain the hypothesis space before learning begins, leaving learning to address components the structure does not specify.

Introduction

The paper argues that known task structure can resolve finite-data identification and extrapolation problems that expressivity alone does not address. It frames this resource difference as the structure gap and relates it to work on inductive bias, structured architectures, and solver-based learning.

Introduction

  • Universal approximation does not ensure that finite examples identify a structured map, certify its behavior on unseen regimes, or recover its generating law.The distinction is between a network containing the map and finite data identifying the right extension.Source: Introduction · p. 1
  • Known structure can restrict the hypothesis space before learning, while a data-only learner must infer the governing law from examples and may pay in samples, parameters, coverage, and extrapolation.The paper frames the gap as finite-resource: data-only learning may approach the structured method asymptotically, but finite data do not replace the law.Source: Introduction · p. 1, Figure 1 · p. 2
  • The paper defines structure-encoded problems and structural separation, proves lower-bound mechanisms and an exact asymptotic-catch-up theorem, and reports numerical studies including graded graph-reachability extrapolation.In that experiment, a dense FCN interpolates training graph size, a message-passing GNN extrapolates more strongly, and exact BFS closes the remaining gap.Source: Introduction · p. 1
  • The claim is class-relative: it compares methods given correct structure with learners denied it, and does not claim wrong or approximate structure is always beneficial.When correct structure is compact, relearning its consequences from examples imposes an avoidable finite-data burden.Source: Introduction · p. 2

Related Work

  • Related work spans approximation and learning theory, equivariant architectures, inverse-problem solvers, algorithmic reasoning, and neuro-symbolic AI; this paper treats correct structure as side information that changes identification before data arrive.The paper presents the structure gap as a shared resource-separation framing across these lines of work.Source: Related Work · p. 2

Structure-Encoded Problems

The section defines structure-encoded problems through side information that constrains a target map, then characterizes the resource gap between methods that can access that structure and learners that cannot. It identifies operator estimation, orbit coverage, and combinatorial-region coverage as mechanisms behind the gap.

Structure-Encoded Problems

  • Side information describes valid structure, and a method is structure-aware when it may access that information at design or inference time.A structure-agnostic learner does not enforce those constraints and receives only input-output examples.Source: Structure-Encoded Problems · pp. 2–3
  • A structure gap at error level ϵ compares a structured method using poly(n, log(1/ϵ)) resources with a structure-agnostic learner requiring asymptotically more resources on at least one axis.The listed axes include samples, parameters, computation, precision, mode or orbit coverage, and dimension-specific retraining; super-polynomial or exponential requirements constitute structural separation.Source: Structure-Encoded Problems · p. 3
  • The section identifies three mechanisms: operator identification leaves parameter uncertainty, missing equivariance leaves orbit fragments uncovered, and combinatorial atlases require learning regions and switching boundaries.These mechanisms correspond to estimating an operator-induced map, lacking a known group action, and inferring discrete regions such as supports or shortest paths.Source: Structure-Encoded Problems · p. 3

Structure

Even when the dense learner’s class contains the exact linear solution, withholding the known operator leaves a finite-sample risk gap. The dense empirical learner approaches the known-operator solver only as sample size tends to infinity.

Structure

  • For some problem classes, a structure-free learner can only approach the structured solver asymptotically, with the finite-data price controlled by hidden-structure coverage.The paper does not claim neural networks cannot learn structure; its result concerns finite-data cost when structure is withheld.Source: Structure · p. 3, Known-Operator Solvers and Asymptotic… · p. 3
  • The Bayes-optimal map is linear and already lies in a one-layer dense network; the missing ingredient is the known operator used by the Wiener solver.The comparison isolates access to the operator rather than the learner’s representational class.Source: Known-Operator Solvers and Asymptotic… · p. 3
  • For every finite N > m + 1 under the stated nondegeneracy conditions, the dense empirical learner has strictly higher expected risk than the known-operator solver, approaching it only as N →∞.The theorem’s excess risk is positive when m > 0 and tr(Σe) > 0.Source: Known-Operator Solvers and Asymptotic… · p. 3

A Cell-Coverage Lower Bound

Finite examples leave uncertainty wherever cells or group orbits remain unseen. A solver given the structure can resolve those cases by construction, while an example-only learner cannot certify them from observed data alone.

A Cell-Coverage Lower Bound

  • For uniform cells, the example-only learner’s minimax risk is at least 1/2(1 − 1/M)^N, while the structure-aware solver has zero risk.The bound follows because an unseen cell’s label remains an independent fair coin; if M is exponential, the coverage burden is exponential.Source: A Cell-Coverage Lower Bound · p. 4
  • If a finite training set misses an orbit and two admissible outputs fit its stabilizer, two equivariant maps can agree on observed points yet disagree on that orbit.The result applies, for example, to scalar invariant labels or free actions.Source: Finite Samples Cannot Certify… · p. 4
  • Augmentation samples orbit elements, whereas an equivariant architecture or symbolic rule constrains the entire orbit by construction.Finite data may cover only fragments of the orbit space when the group action is not encoded.Source: Finite Samples Cannot Certify… · p. 4

Problem Classes

The paper frames the distinction as whether a system uses known structure as side information, rather than whether it is neural or symbolic. Its controlled experiments probe the resulting finite-data and extrapolation gaps across inverse problems, sparse recovery, and graph reachability.

Problem Classes

  • Across problem classes, a compact structural description supplies implications such as valid relabelings, supports, constraints, or graph sizes that a data-only learner must infer from examples.The paper’s comparison is structure-aware versus structure-agnostic, not symbolic versus neural.Source: Problem Classes · pp. 4–5

Numerical Investigations

  • The experiments are controlled probes of theoretical mechanisms, not claims of universal benchmark dominance; a GNN or other model encoding structure belongs on the structure-aware side.The configurations, numerical results, and figure-generation scripts are included in the accompanying code-and-data archive.Source: Numerical Investigations · p. 5
  • In known-operator inversion, the dense least-squares learner approaches the Wiener solver, but its excess remains positive for every finite N tested.The experiment uses d = m = 32 and σ = 0.70.Source: Numerical Investigations · p. 5
  • In sparse recovery, OMP and ISTA receive the measurement operator and sparsity model, while the FCN sees only examples and remains far above solver reconstruction error at the tested sample sizes.The experiment uses k = 4 signals in R64, measurements in R28, and SNR 25 dB.Source: Numerical Investigations · p. 5
  • At 8→24 nodes, FCN accuracy falls 97.79%→73.05%, GNN-4 99.97%→95.48%, while BFS is exact; paired losses are 24.74±3.76 versus 4.49 ± 0.79 percentage points.Relational inductive bias closes most of the dense learner’s extrapolation penalty, and explicit algorithmic structure closes the remainder.Source: Numerical Investigations · p. 5

Implications for AI

Correct structure changes the hypothesis space before data arrive, rather than merely regularizing choices after observing data. The paper argues that learning is best used for components the structure does not specify.

Implications for AI

  • A graph, grammar, solver, or conservation law can imply infinitely many labels or constraints, so treating structure as just another empirical bias understates its information content.Regularization chooses among hypotheses after seeing data; correct structure changes the hypothesis space before data arrive.Source: Implications for AI · p. 5
  • The relevant baseline is structure-aware versus structure-agnostic: neural methods such as GNNs or unrolled optimizers count as structure-aware when they encode the relevant structure.A black-box network may instead pay to rediscover what the solver already knows.Source: Implications for AI · p. 5
  • Scaling model size does not remove the need to identify unobserved cells, supports, or regimes, and a larger FCN cannot certify the correct extension without the structural law.Retrieval, tools, symbolic solvers, program execution, and domain-grounded modules remain central to reliable AI systems.Source: Implications for AI · p. 5
  • Combine symbolic and algorithmic components for known laws with neural components for perception, model mismatch, nuisance parameters, and unknown residuals.The paper connects this division of work to model-based deep learning, neural algorithmic reasoning, and neuro-symbolic AI.Source: Implications for AI · p. 5

Limitations

The paper’s structure-gap claim is conditional: correct structure can reduce finite-data burden, but wrong, incomplete, or costly-to-specify structure may make structured methods biased or brittle. The Gaussian result shows that a dense learner can approach the structured solver while retaining positive expected excess risk under the stated nondegeneracy condition.

Limitations

  • The claim is conditional on compact, correct structure: wrong, incomplete, or costly-to-specify structure can make structure-aware methods biased or brittle.The paper advises considering whether structure is available before scaling data and parameters, and encoding it when appropriate.Source: Limitations · p. 5

Conclusion

  • The structure gap is a finite-resource separation, and finite datasets may leave regimes unresolved that access to known structure resolves by construction.The paper does not claim neural networks cannot match structured solvers; they may approach the same risk with infinite data and suitable optimization.Source: Conclusion · pp. 5–6
  • In graph reachability, the FCN degrades on larger graphs, while a four-layer message-passing GNN retains stronger performance and BFS remains exact.Learned models train on balanced 8-node instances; tests use a shared 24-node padded representation.Source: Limitations · p. 5, Figure 4 · p. 6

Proof of the Gaussian asymptotic-catch-up theorem

  • When tr(Σe) > 0, the dense learner has positive expected excess risk over the structured solver, excluding the noiseless degenerate case.The expectation is over both the training sample and an independent test pair.Source: Proof of the Gaussian… · p. 7

Proof of the finite-cell lower bound

The finite-cell lower bound comes from cells absent from the training sample: their labels remain uncertain to an example-only learner, while a solver given the labels has zero risk.

Proof of the finite-cell lower bound

  • If the sample misses cell C_j, its label b_j remains a fair coin, giving every deterministic predictor conditional error 1/2 on that cell.The absence probability is (1 − p_j)^N for a cell with probability p_j.Source: Proof of the finite-cell lower bound · p. 7
  • For uniform cells, the example-only learner’s minimax risk is lower-bounded by 1/2(1 − 1/M)^N, while a solver given b has zero risk.Yao’s minimax principle transfers the Bayes-risk lower bound to randomized example-only learners.Source: Proof of the finite-cell lower bound · p. 7

Proof of the unobserved-orbit non-identifiability proposition

A finite sample that misses an orbit cannot identify the equivariant map there when two output values are compatible with the representative’s stabilizer.

Proof of the unobserved-orbit non-identifiability proposition

  • Two equivariant maps can agree on every observed point yet disagree on an unobserved orbit when its representative admits two stabilizer-compatible outputs.The construction makes the maps identical on all orbits intersecting the training set and chooses distinct compatible values on the missed orbit.Source: Proof of the unobserved-orbit… · p. 7

Representative structure-encoded problem classes

Across diverse AI and signal-processing tasks, compact structure induces input-output constraints that learners without it must infer from examples. The section illustrates this through continuous-regime coverage, sparse-recovery support coverage, and graph-reachability evaluation.

Representative structure-encoded problem classes

  • Table S1 frames diverse problem classes around a compact structural object that induces constraints otherwise inferred from examples.The table is illustrative, not an exhaustive taxonomy.Source: Table S1 · p. 8

Continuous-covering variant

  • For a continuum of regimes, distribution-free certification at resolution η requires represented samples in every covering cell; finite-sample certification needs additional regularity or the structural law.With intrinsic dimension q, the covering number typically scales as η^-q.Source: Continuous-covering variant · p. 8

Sparse atlas interpretation

  • Under uniform support sampling, covering every sparse-recovery support with probability 1 − δ requires N = Ω(M log(M/δ)), far exceeding the matrix-and-solver description length.A data-only predictor that does not exploit shared structure across supports must cover the support atlas.Source: Sparse atlas interpretation · p. 9

Graph-reachability experiment

  • Graph reachability is evaluated on sizes 8–24 after training on 8-node graphs; Figure S1 shows mean curves and 95% confidence bands over five seeds across message-passing depths.The evaluation uses a shared 24-node padded representation; Table S2 reports results at N = 16,384.Source: Graph-reachability experiment · p. 9, Figure S1 · p. 9, Table S2 · p. 9
  • The graph experiment demonstrates relational inductive bias within a shared 24-node representation, not arbitrary-size algorithm execution or a universal benchmark of graph reasoning.The fixed edge-probability range also changes expected degree as graph size grows.Source: Graph-reachability experiment · pp. 9–10

Additional numerical controls

The additional controls include matched-filter and permutation-equivariance examples, where the FCN must recover implications from finite samples. The paper also describes the manuscript and experiment archive and classifies architectures that encode relevant structure as structure-aware.

Additional numerical controls

  • The matched-filter and permutation-equivariance experiments add examples of continuous-orbit and finite-augmentation mechanisms.The matched filter knows the template orbit, while the equivariant computation knows the permutation law; the FCN must recover those implications from finite samples.Source: Additional numerical controls · p. 10

Reproducibility

  • The accompanying archive includes experiment scripts, result files, requirements, and figure-generation code, with simulation plots regenerable from included results.Conceptual diagrams are separate schematics.Source: Reproducibility · p. 10
  • Neural architectures that hard-code the relevant operator, group action, graph topology, recurrence, or optimizer count as structure-aware under the paper’s definitions.Source: Reproducibility · p. 10

Related papers

Loading 2610.37523v1…