# Neighborhood-separator attention

- ID: 555
- Canonical URL: https://synthcore.org/idea/555/neighborhood-separator-attention
- API JSON: https://synthcore.org/api/idea/555.json
- API Markdown: https://synthcore.org/api/idea/555.md
- Verification status: failed_benchmark
- Source: [arXiv:2607.07697](https://arxiv.org/abs/2607.07697)
- Category: architecture
- Solves: memory, speedup, scalability
- ML areas: attention, transformer, kv-cache, inference-speedup
- Math tags: graph-theory, combinatorics, approximation-theory
- Ratings: usefulness 6/10; difficulty 7/10; novelty 8/10

## 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.

## 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.

## Key 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,$$

## 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

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: no_effect
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 7/10
- 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.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.25605
- Paired wins: 1/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/1384/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/1384/bench_report.json)
- [experiment.py](https://synthcore.org/code/1384/experiment.py)
- [report.md](https://synthcore.org/code/1384/report.md)
- [report_bench_2026-09-04T180814.md](https://synthcore.org/code/1384/report_bench_2026-09-04T180814.md)
- [results.json](https://synthcore.org/code/1384/results.json)
- [Download all files as ZIP](https://synthcore.org/download/1384)

## Disclaimer

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