Research map / Architectures and efficiency / Attention and transformers

Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases

NeurIPS 2026 · Architectures and efficiency › Attention and transformers · approach: Linear attention approximations · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows ALiBi's bias matrix is the expectation of random contiguous block-diagonal binary masks from a positional LSH (Random Binning Features) scheme, giving norm-based guarantees and a near-linear-time approximation of ALiBi-biased attention.

Problem

Computing attention with ALiBi positional bias over long contexts is costly because the bias prevents direct use of efficient regular attention kernels; the formal link between positional bias, masks, and embeddings is also limited.

Approach

Reinterpret the ALiBi Laplacian positional kernel as an LSH collision probability over positions (Random Binning Features), so the bias matrix is the mean of random contiguous block-diagonal all-ones masks; sample-averaging these masks gives spectral and max-norm guarantees and reduces biased attention to many short regular attention computations.

Key results

• On Qwen3-0.6B trained from scratch at 8k, Positional LSH with s=20 reaches PPL 19.05 vs. ALiBi 18.92 and original model 20.21, and beats fixed blocks (19.79).
• On Mistral-7B fine-tuned with LoRA at 4k, Positional LSH s=10 gets PPL 6.698 vs. ALiBi 6.498 and original 6.347; performance improves with more samples but does not beat the original model.
• Matrix-norm errors on Llama-4-Scout and Mistral-7B attention decay toward zero as sample size s grows.

Surprising findings

• On Qwen3-0.6B, Positional LSH outperforms the original model without positional bias even with a small sample size.
• On Mistral-7B, neither positional bias method outperforms the original model in length extrapolation.

Limitations

• No wall-clock speedups over optimized exact ALiBi implementations; prototype not engineering-optimized.
• Spectral-norm and block-size guarantees are specific to ALiBi/RBF; other positional biases need separate proofs.
• Experiments are small-scale (0.6B and 7B models, Wikitext-103) and mainly validate theory; Positional LSH does not match ALiBi performance.

Experimental setup

Datasets: Wikitext-103

Benchmarks: Wikitext-103

Metrics: perplexity next-token accuracy spectral norm error max-norm error

Baselines: ALiBi original model without positional bias fixed blocks

Builds on: ALiBi Random Binning Features FlashAttention-2 LoRA

Closest papers by meaning

• Positional Attention: Expressivity and Learnability of Algorithmic Computation (ICML 2025 · similarity 0.87)
• SEA: Sparse Linear Attention with Estimated Attention Mask (ICLR 2024 · similarity 0.87)
• Customizing the Inductive Biases of Softmax Attention using Structured Matrices (ICML 2025 · similarity 0.86)
• HyperAttention: Long-context Attention in Near-Linear Time (ICLR 2024 · similarity 0.86)
• Token Statistics Transformer: Linear-Time Attention via Variational Rate Reduction (ICLR 2025 · similarity 0.86)
• StableMask: Refining Causal Masking in Decoder-only Transformer (ICML 2024 · similarity 0.86)