The Structure Gap: When More Data Cannot Replace Structured Reasoning

The paper argues that for tasks whose behavior is tightly constrained by known structure—such as solvers, symmetry groups, or physical laws—finite data alone cannot fully capture the underlying mapping, even with expressive neural networks. It introduces the concept of a "structure gap," the performance difference between a method that incorporates this governing structure and a purely data‑driven learner. The authors prove this gap for a Gaussian inverse problem and provide additional theoretical bounds and experimental evidence in areas like sparse recovery and graph reachability.