✗ Failed on benchmark 2026

Neighborhood-separator attention

Implementation & benchmark of arXiv:2607.07697 — Induced Erdős--Pósa property for long holes, long thetas, and beyond

Usefulness6/10

Difficulty7/10

Novelty8/10

Architecture Memory Speedup Scalability Attention Transformer Kv cache Inference speedup Graph theory Combinatorics Approximation theory

Source paper: Induced Erdős--Pósa property for long holes, long thetas, and beyond arXiv:2607.07697 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Construct a sparse token-interaction graph from attention affinities and recursively split it by removing the closed neighborhoods of a small set of separator tokens. Separator tokens retain global communication, while the resulting anti-adjacent components perform local attention independently, reducing quadratic attention and KV-cache costs. The induced Erdos-Pósa theorem supplies a structural diagnostic: graphs with few anti-adjacent long-cycle or theta packings should admit small neighborhood separators.

Formulas

$$|X|=O(tk\log k),\qquad N[X]=X\cup\{v\in V(G):\exists x\in X\text{ with }(v,x)\in E(G)\},$$

$$\text{either }\exists\ H_1,\ldots,H_k\text{ pairwise vertex-disjoint and anti-adjacent induced minors of }H,\quad\text{or }G-N[X]\text{ is }H\text{-induced-minor-free},$$

$$k=k_D+k',\qquad \chi=\chi_D\cup\chi',\qquad X=W\cup X_D\cup X',$$

$$\widetilde{A}_{ij}=\mathbf{1}\{j\in C(i)\cup N[X]\}\,A_{ij},\qquad \operatorname{Attn}(Q,K,V)=\operatorname{softmax}(\widetilde{A})V,$$

Mathematical statement

For a graph G and fixed pattern H, such as a long cycle C_t or long theta Theta_t, an induced packing is a collection of vertex-disjoint copies of H as induced minors whose vertex sets are pairwise anti-adjacent, meaning there are no edges between distinct copies. The paper guarantees that for every integer k, either G contains k such copies, or there is X contained in V(G) with |X| = O(t k log k) such that N[X] = X union N(X) intersects every H induced minor. The extracted recursion explicitly removes N[W], chooses a connected component D of G-N[W], and recurses on D and G-N[D]. Because D and the remainder are anti-adjacent, their packings combine additively: k = k_D + k' and X = W union X_D union X'. We adapt this as a learned graph partition rule: approximate the attention graph by G, find a small separator X, remove N[X], and run attention independently on the resulting anti-adjacent components. The graph theorem is used as a structural justification and evaluation criterion, while the implementation uses a bounded-radius greedy approximation rather than claiming exact induced-minor computation.

Implementation notes

Integrate this into a Transformer attention layer after computing a cheap proxy interaction graph from token embeddings. (1) Exact integration point: for every chunk of L tokens, form symmetric edge scores s_ij = (q_i^T k_j + q_j^T k_i)/(2 sqrt(d)), retain the top-r neighbors of each token, and define an undirected graph G=(V,E) from these edges. Do not run the separator routine every layer; run it every B layers or once per decoding segment. (2) Greedy pseudocode: initialize U=V and separator X=empty. While U contains a bounded-length induced cycle or theta-like pattern, choose x in U maximizing pattern participation divided by deg_U(x)+1, append x to X, and delete the closed neighborhood N_U[x] from U. Then compute connected components C_1,...,C_m of the remaining graph. If no pattern detector fires, optionally stop when every component has at most s tokens. Build the attention mask so token i attends to tokens in its own component C_a plus selected separator tokens X and their one-hop neighbors; use full attention among X. This realizes the paper's N[X] removal and recursive anti-adjacent decomposition. (3) What comes from the mathematics: the closed-neighborhood separator object, the packing-versus-hitting interpretation, and the additive recursion k=k_D+k'. What is estimated empirically: the induced-minor packing number, pattern participation, and the constant hidden in O(t k log k). Detect patterns only for small t, such as t=3 or 4, using bounded-depth BFS plus chord checks, or use a surrogate based on counts of length-2 and length-3 paths with forbidden chords. (4) First experiment: train a 6-layer, 8-head Transformer on WikiText-103 or a synthetic long-range-copy task at sequence lengths 1K, 2K, and 4K. Compare dense attention, fixed local-window attention with the same average degree, and separator attention. Measure validation perplexity, training loss versus FLOPs, peak activation and KV memory, and decoding throughput. A successful result is at least 1.5x lower attention FLOPs or 2x smaller KV memory at matched perplexity, with no more than a 3% degradation on long-range-copy accuracy. Ablate separator frequency B, separator visibility, graph degree r, maximum separator size, and pattern length t.

Verification

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 7/10

Built a readable neighborhood-separator attention MVP with symmetric top-r affinity graphs, greedy triangle-based closed-neighborhood separators, anti-adjacent component checks, and masked attention. The structural math check passed exactly: residual components were anti-adjacent and the implemented mask matched the stated component-plus-N[X] formula. On a planted community graph, separator attention reduced allowed attention pairs by 42.6% (1.74x estimated attention speedup) with MSE 0.0194 versus dense, while fixed local attention was much sparser but had MSE 0.3298; on random affinity graphs the separator mask became dense and provided no speedup, so the effect is conditional on graph structure rather than universal.

Agent confidence: 7/10

Baseline: Dense: 16,384 allowed pairs, relative cost 1.000, MSE 0.0. Fixed local radius-2: 634 pairs, relative cost 0.0387, 25.84x estimated pair-count speedup, MSE 0.3286 on random and 0.3298 on planted graphs.
Idea: Random graph: 16,384 pairs, no speedup, MSE 0.0, mean 1 residual component. Planted community graph: 9,402 pairs, relative cost 0.5739, 1.74x estimated speedup, MSE 0.0194, mean 6 residual components, mean separator size 2.

Limitations: This is a single-layer NumPy attention approximation experiment, not a trained Transformer or long-range-copy/WikiText evaluation. It uses a bounded triangle surrogate rather than exact long-cycle/theta induced-minor detection, estimates compute from allowed pair counts rather than measuring wall-clock GPU throughput, and does not directly measure KV-cache memory or separator refresh frequency.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.07697) Sep 4, 2026

No significant difference vs. the tuned baseline (+0.0%, p=0.256, wins 1 / 8 paired seeds).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0.2635
Idea mean: 0
Effect (Δ): 0 (+0.0%; negative = idea better)
Wins: 1 / 8 paired seeds
p-value: 0.256 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Not confirmed ✗
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

Only the built-in sequence forecast track was tested; no long-range-copy task, wall-clock sparse-kernel speed, KV-cache memory, refresh-frequency ablation, or exact induced-minor/theta detector was evaluated.

How to run: python3 bench_experiment.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 4, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented neighborhood-separator attention as a graph-masked modification of transformer_tiny on the structurally matched sequence track. Across 8 paired seeds, baseline test MSE was 0.263520 and idea test MSE was 0.263567, giving delta_mean +0.0000467 and permutation p=0.25605; this is no measurable effect, not a win. The trained-model mechanism signature was not confirmed because observed allowed fraction was 1.0 and no residual components were produced.

Baseline: best lr=0.001; 8-seed test MSE 0.2635204885
Idea: best lr=0.001; 8-seed test MSE 0.2635671869; paired delta +0.0000466984; p=0.25605; 1/8 paired wins

Benchmark result