CS Paper Radar

Reaching Every Position Without Searching: Rotating Sparse Wiring on the Hypercube as a Substitute for Attention

Yoshiaki Takashita

cs.LG ·submitted 2026-09-16 05:27 UTC · v1

Abstract

Attention pays, at every layer and for every input, the cost of searching for whom to connect. We ask how far one can get with wiring that is fixed, sparse, and simply rotated from layer to layer. Treating the $n$ positions of a sequence as the vertices of a $\log_2 n$-dimensional hypercube and connecting each position, at layer $\ell$, to its neighbour along dimension $\ell \bmod \log_2 n$, information from every position reaches every other in $\log_2 n$ layers with $2n$ links per layer instead of $n^2$. On a synthetic task that is unsolvable unless all positions are reached, this rotation matches all-to-all wiring at $1/32$ of the links, while the same sparse pattern held fixed across layers fails; what matters is that every dimension is touched, not the order. On character-level language modelling of a public corpus (the first $12$M characters of enwik8), a hybrid that keeps two attention layers among sixteen sparse ones reaches $0.06$ bits-per-character lower held-out loss than a fully attentive model of the same width at the same step budget (three seeds each, no overlap), with $1/7$ of the links, $42\%$ fewer parameters, and $2.4\times$ less wall-clock time; the purely rotated schedule is level with the hybrid. The same ordering holds on a second corpus of mixed Japanese, English and code, where the gap widens to $0.16$. The usable learning-rate window is four to eight times wider than attention's on both. We also report what did not work - learned coordinates, and a "dynamics" variant whose apparent gains turned out to be an artefact of a saturated kernel - and the measurement discipline (frozen corpus, full-coverage evaluation, seed spread as the bar for ranking) that we found necessary to say anything at all at this scale.

Comment
13 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Attention Is Only as Good as Its Witnesses: When Higher-Order Layers Help, and When They Do Not

cs.LG cs.AIcs.NE ·2026-11-09 ·Mostafa 'Neo' Mohsenvand
code/data similarity 0.61
Abstract · 25 pages, 5 figures, 7 supplementary tables. Code (Apache 2.0): https://github.com/NeoVand/witnesses ; demo and tutorial: https://neovand.gi…

Transformers stop learning graph search as graphs grow, and learn the card game SET only after many distinct questions, although attention can represent both. We read these failures, and the uneven record of higher-order attention, from what a layer sums over: each layer we study computes the partition function of a family of witnesses and reads it at a temperature. Two laws follow. The depth law is a known result of logic, which we state for these layers: L layers over two-step walks reach exactly 2^L - 1 steps, just as a logical statement with L nested clauses of the form "there is a vertex such that" sees exactly that far. We build a construction that reaches this far, checked in Lean, and, when vertices carry no names, no such network reaches further. The size law is the cost of reading at a temperature, which logic does not have: existence is read correctly at every size, in the worst case, if and only if inverse temperature times margin is at least the logarithm of the number of candidates. Layers built on these laws, and on two principles that we test, learn where Transformers fail. One propagator layer trained on 49-vertex graphs answers every question at every search depth on 250-vertex graphs. Given the modulus 3, exponential Newton computes the softmax of 2-simplicial attention over pairs exactly in 3^d n operations for d clocks; with six clocks it learns SET from as few deals as 2-simplicial attention and transfers from 8- to 20-card tables. On CLRS-30 without hints, a 186,000-parameter block of OR-join and power-mean channels matches (within half a point) or beats a model of at least 73 million parameters on 9 of 12 graph tasks of the official test set, and on 8 of 12 with freshly drawn test graphs. The same account explains where pair layers did not help and where parallel layers must loop.

0.37

Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors

cs.CC ·2026-11-04 ·Nikolai Chukhin
theory similarity 0.59
Abstract

A hyperclique in an $r$-uniform hypergraph is a set of vertices in which every $r$-subset is an edge. A simple exhaustive search algorithm detects a hyperclique on $\ell$ vertices in an $r$-uniform hypergraph on $m$ vertices by checking all $\binom{m}{\ell}$ sets of $\ell$ vertices. This algorithm can be expressed as a depth-two circuit with at most $m^\ell$ gates and wires. For hypercliques of *constant* size, Amano (2010) showed that this circuit is almost optimal: for large $r$, constant-depth circuits need $m^{\ell(1-O(\log r/r))}$ wires. We prove that this circuit remains hard to beat even for hypercliques of *polynomial* size. More precisely, circuits of depth $h$ need $m^{Ω(\ell)}$ gates for $\ell\leq m^{1/h-\varepsilon}$, and $m^{\ell(1-O(\log r/r))}$ gates for $\ell=m^{o(1)}$ that tends to infinity. Our hyperclique bound and the method behind it also lead to lower bounds for two central problems of fine-grained complexity. First, we extend the bound $n^{k/4}$ of Rossman (2008) for $k$-Clique from cliques of *constant* size to cliques of *polynomial* size: circuits of depth $h$ detecting a clique on $k$ vertices in an $n$-vertex graph need $n^{Ω(k)}$ gates for $k\leq n^{1/(h-1)-\varepsilon}$. Second, a reduction of Choudhury, Limaye, Sreenivasaiah, and Srinivasan (2026) turns our hyperclique bound into a lower bound of $n^{k-\varepsilon}$ gates for $k$-Orthogonal Vectors ($k$-OV) at every fixed depth for vectors of dimension $\log^{O(1)} n$; this proves the $k$-OV Conjecture for constant-depth circuits in polylogarithmic dimension. Finally, for $2$-OV in logarithmic dimension, we give a simple proof that depth-three circuits need $Ω(n^2)$ wires, which answers a question of Kane and Williams (2019).

0.23

Layerwise Repacking: Variable-Length Hybrid-Attention Training without an Extra Redistribution Pass

cs.LG cs.AI ·2026-10-26 ·Jiahao Zhang, Junwei Feng, Dongliang Huang, Xiaoling Zhou, Yiqiao Liao +1 more
similarity 0.58
Abstract

Variable-length training creates conflicting parallelism requirements across the layers of a hybrid-attention model. The longest samples require wide sequence-parallel (SP) groups of 16 or 32 ranks for full attention, whose cost grows quadratically with sequence length. Sparse-attention layers, dominated by near-linear MoE work, can instead balance most evaluated workloads within node-local SP8 groups. Reusing the wide groups for these layers pushes their all-to-all communication across nodes, where the observed effective rate is 7.0x lower. Yet switching to smaller groups changes which ranks own each sample; a separate redistribution at every full-sparse boundary would introduce another data transfer. Layerwise Repacking keeps each SP16/32 parent for full attention and repacks its samples into node-local sparse children at SP{1, 2, 4, 8}, where hidden states persist between full layers. The layout change rides on the two existing full-layer Ulysses sites: at each, one variable-size all-to-all performs both the head exchange and the sample repacking, so no redistribution pass is added. Because the balance the children can reach depends on which samples share a parent, an auxiliary parent solver rebalances parent membership before the children are formed. On all 22 steps with SP16/32 parents among the first 200 training steps of a 1F3S hybrid-attention model (one full-attention layer per three sparse-attention layers), repacking alone reduces the mean end-to-end time by 5.95% and raises model FLOPs utilization (MFU) by 3.75 percentage points over the baseline with repacking disabled; with the improved solver, end-to-end time falls by 7.61% and MFU rises by 4.83 percentage points.

0.16

INTRA: Interleaved Non-contiguous Token spaRse Attention

cs.LG ·2026-10-25 ·Yuxuan Xia, Wenbo Lu, Shaoyi Zheng, Shengjie Wang
code/data similarity 0.57
Abstract · 26 pages, 8 figures, including appendices. v2: Added code link to the abstract; scientific content unchanged. Code: https://github.com/NovTi…

Transformers achieve strong performance across modalities but are bottlenecked by the quadratic cost of attention. Sparse attention can reduce this cost, but effective sparsity must preserve useful long-range communication and map well to GPU hardware. We introduce INTRA--Interleaved Non-contiguous Token spaRse Attention--a hardware-aware static sparse attention design based on a relay-communication view under Computational Query Set (CQS) constraints. Rather than directly covering all token-to-token interactions within each sparse layer, INTRA uses complementary sparse groups to provide short mediated communication paths across layers. Scatter forms relay groups that sample broadly across local neighborhoods, while Gather reconnects these groups in subsequent layers. Under a partition model, this structure guides CQS-compatible sparse patterns with global reachability. Our CQS-aware FlashAttention-style kernel computes structured indices at runtime, loads selected non-contiguous tokens, and packs them densely for computation. On an A100, INTRA achieves a $1.53\times$ speedup in $2K$ FLUX.1-dev generation, with better measured image quality than evaluated CLEAR configurations after LoRA self-distillation. On LLaMA-3.1-8B, it improves long-context prefill efficiency with strong teacher-forced retrieval performance under matched LoRA adaptation. Attention-only benchmarks further show up to $8.4\times$ and $10.4\times$ speedups over MoBA and density-constrained NSA, respectively. Code is available at https://github.com/NovTi/INTRA.

0.31

Block Sparse Attention with Log-Linear Complexity

cs.LG ·2026-09-25 ·Bohao Tang, Zhen Qin, Yuqi Pan, Zheng Li, Pengfei Liu
highly cited similarity 0.57
Abstract

Scaling language models to long contexts is limited by the quadratic cost of self-attention. Block sparse attention offers an efficient alternative, but selecting the retained blocks remains a bottleneck. Conventional block selection requires scoring all query-block pairs and therefore remains quadratic in sequence length. To address this issue, we propose PISA, a block-sparse attention mechanism that employs a pyramid Top-$K$ selection strategy. The main idea is to gradually narrow down the candidates across different levels, making it more efficient to find the most relevant keys. Specifically, we construct a coarse-to-fine hierarchy of keys and perform selection from the coarsest level. At each level, LogSumExp scoring is applied to a bounded candidate set to select candidates for the next finer level, continuing until the finest level is reached. Through pooling, we construct $O(\log N)$ levels of keys, yielding an overall complexity of $O(N\log N)$, where $N$ denotes the sequence length. We develop hardware-aware Triton kernels for both training and inference, fusing hierarchical routing and LogSumExp scoring without materializing the query-key score matrix. We further evaluate our method on language modeling tasks. Compared with the baseline, our method achieves comparable performance on benchmarks such as commonsense reasoning while delivering better results on retrieval tasks.

0.42

Inside the Loop: A Mechanistic Study of Weight-Tied Transformers on Depth-Bound Algorithmic Tasks

cs.LG cs.CL ·2026-10-16 ·Magnus Sesodia, Juil Sock, Philip Torr, Christian Schroeder de Witt
top venuecode/data similarity 0.56
Abstract · Accepted to NeurIPS 2026. 17 pages, 12 figures

Solving algorithmic tasks with many sequential steps typically requires scaling up transformer depth or chain-of-thought length, incurring unfavorable parameter and inference-compute costs, respectively. Looped transformers, which reuse one block of layers across many iterations, are poised to address this, since they scale effective depth without adding parameters or tokens. Yet, it remains unclear what each iteration is actually computing, or whether the loop merely simulates a deeper untied stack. Here, we study directed permutation traversal, in which a model follows $H$ hops from a starting node and reports the node it reaches, so every intermediate hop has a known ground truth. We find that a minimum effective depth is necessary to solve the task, beyond which the degree of weight tying becomes the determining factor. For instance, a looped transformer with a four-layer block iterated eight times solves the task in every seed, while an identically-trained untied transformer of the same effective depth never does, succeeding only with a lower learning rate or supervision of its intermediate layers. Probing and intervening on the residual stream, we find that the looped model advances through the intermediate nodes gradually, forming a staircase that adapts to its iteration budget, whereas the untied model, at that lower rate, exposes them only in its final layers. Taken together, our results recast looped transformers as iterative program learners, which allocate their iterations to successive steps of the algorithm and solve tasks that identically-trained untied models of the same effective depth do not. Code is available at https://github.com/magnus-sesodia/insidetheloop.

0.39

MoRE: Scaling mixture of experts with hardware-aware low-rank routing

cs.LG cs.AIcs.CLstat.ML ·2026-09-28 ·Honam Wong, Surbhi Goel, Enric Boix-Adserà
theorycode/data similarity 0.56
Abstract

Mixture-of-Experts (MoE) layers are central to frontier language models, and recent architectures push toward more and smaller experts. In this regime, the standard linear router becomes a bottleneck: with $M$ experts and hidden dimension $h$, its per-token cost $Θ(Mh)$ dominates the MoE layer once $M$ is large. We introduce MoRE (Mixture of Rank-reduced-routed Experts), which factorizes the router weight matrix at rank $r$ and reduces the routing cost to $O((h + M)r)$. We prove that rank logarithmic in $M$ suffices for routing expressivity when the number of active experts is fixed, and is necessary up to precision factors. We also prove that logarithmic rank preserves load balance in a Gaussian memorization model, and training on a synthetic phonebook task shows that low rank does not hurt memorization. At matched active FLOPs, the factorization allows a factor of $Θ(h/r)$ more experts. To realize this gain in wall-clock time, we design a fused Triton kernel at inference that avoids expensive memory operations on HBM. Empirically, MoRE improves memorization on the phonebook task and performance on knowledge-intensive Q\&A benchmarks after pretraining, while matching reasoning ability. Code available at https://github.com/Matheart/MoRE_code.

0.33

Recursive Sparse Attention: Million-Token Length Extrapolation at Logarithmic Cost

cs.CL cs.LG ·2026-11-04 ·Ruitian Wang, Xinyu Yang, Minshen Zhang, Hao Zhang
similarity 0.56
Abstract · 24 pages, 6 figures, 17 tables

At context lengths of about 1M tokens, dense attention is costly in prefill and decoding, and training typically relies on long documents, which become scarcer as the target length increases. Most sparse attention methods score all preceding blocks or tokens, so their selection cost per query is $O(L)$ at context length $L$; hierarchical selection reduces it to $O(\log L)$, but prior trainable hierarchical methods report accuracy only within their training length. We propose RecSA (Recursive Sparse Attention), which builds a tree over the KV cache in which each node summarizes its subtree with one key and one mean-pooled value. The keys come from one pooler per layer, shared by all levels and distilled from dense attention. Each level above the tokens selects at most $k$ candidates, so each query has $O(\log L)$ selection cost and reads $O(\log L)$ entries; the summaries of unselected candidates share one softmax with the exact tokens. Each entry's RoPE position is its index among the candidates of its level, so at any length every relative distance stays within the range seen during training. Initialized from Qwen3-4B and trained on 0.62B tokens at the original model's 32K training length, RecSA outperforms all baselines on RULER at every length from 131K to 2M; at 1M, it scores 60.5, compared with 40.0 for the best baseline, Dense + DCA. With our optimized kernels, RecSA is faster than dense attention in end-to-end prefill and decoding from 64K to 2M; at 524K on one H200 GPU, it accelerates prefill by 3.2x and decoding by 3.8x.

0.16