The Structure Gap: When More Data Cannot Replace Structured Reasoning

Kheer Sagar Patel; Mojtaba Soltanalian

cs.LGOct 27, 2026

The Structure Gap: When More Data Cannot Replace Structured Reasoning

Authors: Kheer Sagar Patel, Mojtaba Soltanalian

Organizations: University of Illinois Chicago

Abstract

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.

Figures & tables

Figure 1: Conceptual view of the structure gap. A structure-aware system uses a known law, solver, graph, symmetry, grammar, or objective to restrict the hypothesis class before learning. A structure-agnostic learner can fit examples, but must infer the law from data and therefore pays with samples, parameters, coverage, and weaker extrapolation. The gap is a finite-resource phenomenon: the data-only path may approach the structured path asymptotically, but the structure certifies the extension at finite sample size.

Figure 2: Problem classes where structure changes the learning problem. Each box summarizes a compact structural description—known operators, symmetry, combinatorial rules, optimization constraints, relational structure, or variable dimension—that induces a large family of input-output constraints. When the structure is correct, it acts as information that shrinks the effective hypothesis space; a structure-agnostic learner must infer these implications from examples.

Figure 3: Finite data fits observed examples, but does not certify unobserved orbits, supports, or symbolic regimes. A structure-free learner remains underconstrained outside the sample, whereas a structured solver propagates the governing law by construction.

Figure 4: Structured information improves finite-data performance and extrapolation. (a) In known-operator inversion, the dense learner contains the Bayes map but must estimate it from examples; its finite-sample risk follows Theorem 1 . (b) In sparse recovery, OMP/ISTA use the sensing matrix and sparsity model directly, while the FCN must learn a support-indexed inverse. (c) All learned graph models are trained only on balanced 8-node reachability instances with $N=16{,}384$ . The FCN nearly solves the training graph size but degrades on larger graphs; a four-layer message-passing GNN retains much stronger performance, while BFS is exact. Bands are 95% confidence intervals over five seeds. (d) Paired accuracy loss from 8 to 24 nodes. Tests are within a shared 24-node padded representation envelope.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Problem class	Structural object	Structure-aware method	Why a data-only learner pays
Known inverse problems	Forward operator, likelihood, noise model	Wiener/Kalman filtering ( Wiener 1949 ; Kalman 1960 ) , variational solvers and proximal methods ( Boyd and Vandenberghe 2004 ; Rockafellar 1976 )	Must estimate an operator-induced map; finite-sample excess persists.
Symmetry and invariance	Group action, permutation, translation, rotation	Equivariant networks, group convolution, invariant solvers ( Cohen and Welling 2016 ; Zaheer et al. 2017 ; Bronstein et al. 2021 )	Must cover or infer group orbits; finite data cannot certify unobserved transformations.
Sparse and low-dimensional signals	Sensing matrix, sparsity, low rank, dictionary	OMP ( Tropp and Gilbert 2007 ) , LASSO ( Tibshirani 1996 ) , ISTA/FISTA ( Daubechies et al. 2004 ; Beck and Teboulle 2009 ) , AMP ( Donoho et al. 2009 ) , unrolling ( Gregor and LeCun 2010 ; Monga et al. 2021 )	Must learn a combinatorial atlas of supports, ranks, or active sets.
Spectral and signal models	Fourier basis, array manifold, convolutional template	FFT ( Cooley and Tukey 1965 ) , matched filter ( Turin 1960 ) , MUSIC/ESPRIT ( Schmidt 1986 ; Roy and Kailath 1989 ) , beamforming ( Van Trees 2002 )	Must rediscover harmonic geometry and phase relationships from examples.
Optimization-defined maps	Objective, constraints, KKT conditions	Convex solvers ( Boyd and Vandenberghe 2004 ) , dynamic programming ( Bellman 1957 ) , proximal algorithms ( Rockafellar 1976 )	Must learn active-set or recurrence structure rather than use optimality conditions.
Symbolic and algorithmic reasoning	Grammar, rule base, graph recurrence, program	Parsers ( Hopcroft and Ullman 1979 ) , SAT ( Davis et al. 1962 ) , MILP ( Nemhauser and Wolsey 1988 ) , shortest paths and breadth-first search (BFS) ( Dijkstra 1959 ; Cormen et al. 2022 ) , theorem proving ( Robinson 1965 )	Must learn exact discrete transitions and extrapolate to unseen sizes or symbols.

Appendix

Table S1: Representative structure-encoded problem classes. The central separation is between using the structural description and relearning its consequences from examples.

Method	Accuracy, $n=8$	Accuracy, $n=24$	Loss 8–24 (pp)
BFS	$100.00\pm 0.00$	$100.00\pm 0.00$	$0.00\pm 0.00$
FCN	$97.79\pm 0.81$	$73.05\pm 3.61$	$24.74\pm 3.76$
GNN-4	$99.97\pm 0.06$	$95.48\pm 0.80$	$4.49\pm 0.79$
GNN-8	$99.98\pm 0.03$	$96.03\pm 1.80$	$3.95\pm 1.78$

Appendix

Table S2: Graph reachability at

N=16{,}384

. Entries are means

\pm

95% confidence intervals over five seeds.

Figure S1: Graph-size extrapolation for all tested message-passing depths. All learned models are trained on 8-node graphs with

N=16{,}384

. Curves show means and 95% confidence bands over five seeds.

Panel of Figure 8 — Figure S2: Additional controlled examples. The matched filter knows the template orbit; the equivariant computation knows the permutation law. In both cases the FCN must recover the corresponding implications from finite samples.

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 584 papers

Edge Accuracy Is Not Enough: Why Dynamics-Learned Structure Fails to Transfer to Inverse Problems
Oct 7, 2026Nicholas Tan Jerome, Fangnian WangInverse Problems Graph Structure Learning
Institute for Data Processing and Electronics (IPE) Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany · Institute for Thermal Energy Technology and Safety (ITES) Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany
Learning Bayesian and Markov Networks with an Unreliable Oracle
Mar 10, 2026Juha Harviainen, Pekka Parviainen, Vidya Sagar SharmaGraph Structure Learning Bayesian Network Structure Learning
University of Helsinki, Finland · University of Bergen, Norway · Indian Institute of Technology Madras, India
Wide Learning: Learning to Reach Evidence
Aug 30, 2026Junzhou ChenEvidence-Grounded Reasoning Statistical Learning Theory
School of Intelligent Systems Engineering, Sun Yat-sen University Shenzhen 518107, China

Oct 7, 2026J/K move · Enter open · S save

Edge Accuracy Is Not Enough: Why Dynamics-Learned Structure Fails to Transfer to Inverse Problems

Nicholas Tan Jerome, Fangnian Wang

Institute for Data Processing and Electronics (IPE) Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany · Institute for Thermal Energy Technology and Safety (ITES) Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany

Inverse Problems Graph Structure Learning Task Transferability Estimation

Open paper AskPDF arXiv

A natural strategy for inverse problems with scarce labelled data is to transfer relational structure learned from abundant forward-simulation data. We show this strategy fails systematically, even when it satisfies the standard theoretical justification for why structure should help. We prove that approximate structure provides estimation-error benefits whenever the edge error satisfies

Δ< n^2 - kn

, reducing sample complexity from

O(n^2)

O(kn+Δ)

. Structure learned via Neural Relational Inference (NRI) from dynamics prediction satisfies this condition, yet on a source-localisation task across 180 CFD-simulated hydrogen-leak scenarios and 180 acoustic scenarios, it degrades performance by 116% and 201% relative to a flexible, task-optimised attention baseline, while a physics-based prior (Green's function) degrades by only 69-72%. Four independent lines of evidence show this is not a tuning failure: NRI improves only 0.5% when given 18x more training data (versus 16.6% for the task-optimised baseline,

p<0.001

); performance is insensitive to the NRI edge threshold across a wide range; the dynamics-learned graph overlaps the task-optimal graph on only 6% of edges; and two further dynamics-derived structure estimators (correlation- and mutual-information-based) show no measurable benefit over a structure-free baseline, with the correlation-based estimator performing markedly worse. We formalise this gap as a statement about approximation error that the edge-accuracy condition cannot control, and we provide a lightweight transferability test (Jaccard similarity against a partially-observed target-task graph) that separates successful from failed transfer in all four domain/structure pairs we evaluate, using under an hour of computation and 15-20% of target-domain data; we present this as a heuristic calibrated on few cases, not a validated general threshold.

Abstract

Statistical Learning Theory

Explore similar work

Edge Accuracy Is Not Enough: Why Dynamics-Learned Structure Fails to Transfer to Inverse Problems

Learning Bayesian and Markov Networks with an Unreliable Oracle

Wide Learning: Learning to Reach Evidence