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

• URL: http://arxiv.org/abs/2605.09472v1
• Date: Sun, 10 May 2026 10:58:20 GMT
• Title: Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases
• Abstract summary: We study attention with positional bias through the lens of locality-sensitive hashing (LSH)<n>We show that the ALiBi bias matrix is the expectation of contiguous block-diagonal binary masks induced by a positional LSH'' scheme.
• Score: 10.27725229355938
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Positional encoding in transformers is commonly implemented through positional embeddings, attention masks, or bias terms, but formal connections between these mechanisms remain limited. We study attention with positional bias through the lens of locality-sensitive hashing (LSH), focusing on Attention with Linear Biases (ALiBi). We show that the ALiBi bias matrix is the expectation of contiguous block-diagonal binary masks induced by a ``positional LSH'' scheme. The empirical mean of masks sampled from this scheme yields spectral norm and max-norm approximation guarantees with bounded block sizes with high probability. This structural theorem implies a uniform approximation theorem for ALiBi-biased attention: with high probability over the sampled masks, the approximate attention output is accurate simultaneously for all query-key-value inputs and can be computed in near-linear time in the context length, reducing long-context ALiBi to a collection of randomized short-context regular (positionally unbiased) attention operations. Conceptually, this connects positional bias, masks, and positional embeddings in a single formal framework and suggests an approach to efficient ALiBi-biased attention. Experiments on large language models validate our theoretical findings.

Related papers

• Relative Positions Generalize, Absolute Positions Memorize: An Implicit-Bias Account of Length Generalization in Attention [4.422349568747053]
  Transformers with relative positional encodings often extrapolate to sequences longer than those seen during training.<n>We prove that rotary encodings make the attention logit a function of relative offset alone.<n> Learned absolute encodings instead leave out-of-range positions unconstrained, and the trained head pins to a fixed absolute position inside the training range.
  arXiv  Detail & Related papers  (2026-07-21T06:29:10Z)
• Efficient Long-Context Modeling in Diffusion Language Models via Block Approximate Sparse Attention [58.484607892210015]
  Diffusion Language Models (DLMs) enable globally coherent, bidirectional, and controllable text generation.<n>Many existing block-sparse attention methods select blocks by fixed sampling patterns over the high-resolution attention space.<n>We propose the Block Approximate Sparse Attention framework (BA-Att) with block-wise pre-downsampled operation.
  arXiv  Detail & Related papers  (2026-05-19T12:01:13Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Prism: Spectral-Aware Block-Sparse Attention [46.31167787304103]
  Existing methods typically employ coarse-grained attention as a proxy for block importance estimation.<n>Mean pooling acts as a low-pass filter that induces destructive interference in high-frequency dimensions.<n>We introduce Prism, a training-free spectral-aware approach that decomposes block selection into high-frequency and low-frequency branches.
  arXiv  Detail & Related papers  (2026-02-09T09:31:06Z)
• Higher-order Linear Attention [59.92962330635185]
  quadratic cost of scaled dot-product attention is a central obstacle to scaling autoregressive language models to long contexts.<n>We introduce Higher-order Linear Attention (HLA), a causal, streaming mechanism that realizes higher interactions via compact prefix sufficient statistics.
  arXiv  Detail & Related papers  (2025-10-31T07:54:37Z)
• Local Information-Theoretic Security via Euclidean Geometry [0.0]
  This paper introduces a methodology based on Euclidean information theory to investigate local properties of secure communication over memoryless wiretap channels.<n>We analyze both the information leakage to an eavesdropper informational efficiency and the largest generalized cost of a secret message.
  arXiv  Detail & Related papers  (2025-10-15T15:19:59Z)
• On the Emergence of Position Bias in Transformers [59.87743433861665]
  This paper presents a graph-theoretic framework for analyzing position biases in multilayer positions.<n>Our framework offers a principled foundation for understanding positional interplay in transformers.
  arXiv  Detail & Related papers  (2025-02-04T02:53:07Z)
• HyPE: Attention with Hyperbolic Biases for Relative Positional Encoding [0.0]
  In Transformer-based architectures, the attention mechanism is inherently permutation-invariant with respect to the input sequence's tokens. We introduce Hyperbolic Positional Attention (HyPE), a novel method that utilizes hyperbolic functions' properties to encode tokens' relative positions.
  arXiv  Detail & Related papers  (2023-10-30T15:54:32Z)
• SEA: Sparse Linear Attention with Estimated Attention Mask [51.22399593954608]
  Long seqeuences pose a problem due to the quadratic complexity of the attention operation. Previous research has aimed to lower the complexity by sparsifying or linearly approximating the attention matrix. We propose SEA: Sparse linear attention with an Estimated Attention mask.
  arXiv  Detail & Related papers  (2023-10-03T03:56:26Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.