Exact-Distance Domination in Grid Graphs
arXiv:2607.29648
2026
Architecture
1 ideas extracted · analyzed Aug 31, 2026
What the math gives to ML
The paper gives a constructive periodic exact-distance covering of the integer grid using a finite cyclic labeling, rather than merely proving that a sparse set exists. The transferable asset is a deterministic sparse connectivity pattern in which every non-anchor grid location has at least one anchor exactly k Manhattan steps away, with asymptotic anchor density approximately 1/(3k). This can build sparse landmark attention or grid message-passing layers with guaranteed k-step access to an anchor, avoiding quadratic all-to-all attention. The construction is especially suitable for image grids, spatial world models, and graph neural networks with fixed lattice structure.
Ideas from this paper
Unverified
2026
Replace dense spatial attention on a 2D feature grid by attention from every non-landmark token to a small periodic set of landmark tokens. Choose landmarks using the paper's residue construction so that every non-landmark token has at least one landmark exactly k Manhattan steps away. Use this guaranteed edge as a sparse global-information route, combined with a cheap local convolution or residual path for accuracy.
Useful6/10
Difficulty5/10
Novelty7/10