A path-summing layer transfers graph search to larger graphs
Attention Is Only as Good as Its Witnesses: When Higher-Order Layers Help, and When They Do Not · arXiv:2611.11937
In plain words
The paper introduces a way to describe attention layers by what they add up: individual items, pairs, or paths. Its central idea is that a layer may learn more easily when it sums over the same kinds of combinations that a task’s answer depends on.
A path-summing layer learned graph search on graphs up to 49 vertices. On 250-vertex graphs, it answered every test question at every tested search depth in all three runs.
Separately, it scored 99.0–100% on the benchmark’s random graphs of that size. These are results on that test, not a guarantee for other graphs.
The research
When a task depends on relations among pairs or paths, choosing a layer that sums over those structures could change whether it learns as inputs grow.
This paper gives a way to reason about that choice and tests it on graph search, card matching, and algorithmic tasks, while also showing where the idea does not account for errors.
The paper frames attention layers by the objects they sum over, proves limits on pair updates, and tests layers that sum over paths or pairs directly.
On a graph-search test that asks for the next useful vertex along a route, none of ten benchmark Transformer runs reached the training convergence criterion of at least 99.5% training accuracy on two consecutive checks, across graph sizes of 31 to 100 vertices, despite at least 5.2 million examples per run.
This training result is separate from the propagator’s test result on 250-vertex graphs: a one-layer propagator trained on graphs up to 49 vertices answered every test question at every tested lookahead there in all three runs.
Separately, it scored 99.0–100% on the benchmark’s random graphs of that size. This shows transfer in that test setting.
The graph-search result covers the test’s random graphs, and the pair-network limit assumes anonymous starting states. The paper’s positive results are on synthetic and algorithmic tasks with small models.
What the evidence shows
- What a layer sums over
The paper introduces a framework for describing attention layers by the objects they sum over, such as tokens, pairs, or paths. It proposes that learning may depend on whether those objects match the combinations needed for a task’s answer.
The framework also yields mathematical limits on stacked pair updates and on reading existence from an exponential sum.
- A path layer transfers
The graph-search results are separate measurements, not a like-for-like comparison: none of ten benchmark Transformer runs met its training convergence criterion on graphs of 31 to 100 vertices, while the propagator answered every test question at every tested lookahead on 250-vertex graphs in all three runs.
Separately, it scored 99.0–100% on the benchmark’s random graphs of that size. The result supports transfer in this benchmark setting, not a general claim about graph search.
- SET transfer to new cards
The transfer test asks whether the SET layer can handle deals that differ from its training examples in both the cards held and table size. Its accuracy remained high on those tested deals, supporting transfer across those changes while leaving other SET settings untested.
- A comparison across graph tasks
This comparison suggests that the paper’s smaller block can perform competitively across many tested graph tasks. Because its training protocol differed from FloydNet’s, the result does not isolate the effect of model size or architecture.
Deep
- Original paper authors
- Mostafa 'Neo' Mohsenvand
- Submitted to arXiv
- License
- CC BY 4.0