EN
Known task structure can resolve gaps left by examples
The Structure Gap: When More Data Cannot Replace Structured Reasoning · arXiv:2610.37523
In plain words
Some problems come with a known rule, such as a measurement operator or a graph algorithm. A learner that sees examples only has to work out that rule from the cases shown, so it may not know what to do with unseen cases.
The paper calls this finite-data difference the structure gap. It proves that, for a Gaussian reconstruction problem, a learner can represent the right answer and still have higher expected error than a solver using the known measurement rule at every finite sample size covered by the theorem. More examples shrink the gap.
The research
When a task already has a known rule, can a learner shown only examples reliably extend that rule to cases it has not seen? The paper studies this finite-data question, including settings where a dense learner can represent the right answer but has not been told the structure that determines it.
The paper defines the structure gap and uses proofs and task comparisons to show how known rules can resolve uncertainty that finite examples leave.
Can examples alone identify a task’s rule when its structure is already known? The paper answers with the structure gap, a finite-resource difference between a method given that structure and a learner given examples only.
It formalizes how finite data can leave unseen cases uncertain, then tests the idea through exact results and task comparisons.
In Gaussian reconstruction, a dense least-squares learner can represent the optimal map, but must estimate it from examples; a Wiener solver uses the known measurement operator. The theorem finds higher expected squared error for the learner at finite sample sizes under its conditions, averaged over training samples and independent test pairs, with the gap shrinking as data grows.
In graph reachability, message passing retains higher mean accuracy than a fully connected network at 24 nodes after both train on 8-node graphs.
The structure gap is conditional on having a compact, correct description of the task’s structure. The graph result covers only the tested graph generator and a shared 24-node padded representation, so it does not establish performance on arbitrary graphs or sizes.
What the evidence shows
- What the gap means
The paper introduces the structure gap: a finite-resource difference between methods that use a task’s known structure and learners given examples only. It focuses on structure-encoded problems, where an object such as an operator, graph, or symmetry constrains the input-output rule.
The issue is whether examples identify and extend that rule to unseen cases, not whether a dense neural network can represent the answer.
- Why unseen cases matter
The paper formalizes why observed examples may not settle unseen cases. In a cellwise labeling problem, an example-only learner cannot know the label of a cell it never sees.
Likewise, if examples miss a whole symmetry orbit, two equivariant maps can agree on every observed point but disagree across that orbit. The paper’s point is that a solver given the cell labels or a method encoding the symmetry resolves this uncertainty by construction.
- A precise risk comparison
A Gaussian reconstruction theorem gives an exact comparison. The dense least-squares learner can represent the Bayes-optimal linear map but estimates it from examples; the Wiener solver uses the known measurement operator.
Averaging expected squared error over training samples and independent test pairs, the theorem finds positive finite-sample excess risk for the learner under its stated conditions, shrinking as sample size grows.
- A bounded graph result
The graph experiment tests source-to-target reachability after training learned models on 8-node graphs. At 24 nodes, mean accuracy over five seeds is 73.05% for the fully connected network and 95.48% for the message-passing graph neural network; breadth-first search is exact.
The authors interpret this as a graded result in the tested setting: relational structure narrows the gap, and the exact algorithm closes it.
Deep
- Original paper authors
- Kheer Sagar Patel, Mojtaba Soltanalian
- Submitted to arXiv
- License
- arXiv non-exclusive