Bilateral Log-Linear Attention

Kazi Ashik Islam, Guojing CongarXiv 2026 · arXiv

TL;DR

Bilateral Log-Linear Attention improves long-context retrieval in sequence models by pairing a recency-biased memory hierarchy with a new, origin-anchored hierarchy. This "best of both worlds" approach significantly boosts associative recall—raising accuracy from 76% to 96% on key benchmarks—while maintaining efficient logarithmic scaling for memory and computation.

What Problem Does This Paper Address?

Modern Large Language Models (LLMs) face a fundamental tension between performance and efficiency. Standard Softmax Attention (Transformers) provides near-perfect recall but suffers from quadratic complexity ($O(T^2)$), making long contexts prohibitively expensive.

To solve this, researchers developed Linear Attention and State-Space Models (SSMs) like Mamba, which compress context into a fixed-size recurrent state ($O(1)$ memory). While efficient, this compression often leads to "forgetting," especially for specific facts buried deep in the past (associative recall).

Log-linear attention recently emerged as a middle ground, using a Fenwick tree hierarchy to maintain $O(\log T)$ state matrices. However, it has a "recency bias": it provides high resolution for recent tokens but lumps older tokens into increasingly coarse, compressed summaries. If the "needle" you need to find in the "haystack" is near the beginning of the sequence, log-linear attention often misses it.

Methods

The authors introduce Bilateral Log-Linear Attention, which complements the existing recency-focused hierarchy with a second branch anchored at the sequence origin.

The Two Branches:

  1. Forward Branch: Uses the standard Fenwick hierarchy. It provides fine-grained resolution for tokens near the current query.
  2. Reverse Branch: A new hierarchy anchored at $t=0$. Bucket sizes grow geometrically ($1, 2, 4, 8, \dots$) as they move away from the start. This ensures that the very first tokens in a sequence—often containing crucial instructions or context—retain high resolution.

Key Technical Innovations:

  • Shared Features: Both branches share the same Query (Q), Key (K), and Value (V) projections to save parameters.
  • Reverse Write Gating: A data-dependent gate ($\eta_s$) controls how strongly each token is written into the reverse branch's memory, allowing the model to filter out noise.
  • Branch Normalization & Mixing: Because the two branches represent context differently, the authors use affine-free RMS normalization and a learned, input-dependent "router" (softmax mixing) to fuse the outputs of the two hierarchies.
  • Efficient Computation: The authors derived a chunkwise parallel formulation using additive prefix scans. This preserves the $O(T \log T)$ training complexity and $O(\log T)$ decoding complexity of the original log-linear model.

Datasets

The model was evaluated across a rigorous battery of tests:

  • MQAR (Multi-Query Associative Recall): A synthetic "stress test" for memory where models must retrieve multiple KV pairs from a 512-token sequence.
  • RULER: A suite of "needle-in-a-haystack" tasks specifically designed to test long-context retrieval (tested up to 6144 tokens).
  • Standard LM Benchmarks: WikiText-2 (perplexity) and LAMBADA (commonsense reasoning).
  • Downstream Retrieval: Eight tasks including SQuAD, TriviaQA, and Natural Questions (NQ).

Key Insights and Ideas

  • Resolution Allocation Matters: The "aha moment" here is that memory capacity isn't just about the amount of state, but where you allocate resolution. By anchoring at both the start and the current query, the model effectively brackets the context.
  • Stability vs. Dynamics: In the forward branch, buckets are query-dependent and shift as the sequence progresses. In the reverse branch, buckets are stationary relative to the origin. This stability in the reverse branch makes it easier for the model to "index" into early context.
  • The Logarithmic Sweet Spot: $O(\log T)$ storage provides enough "slots" to prevent the catastrophic interference seen in $O(1)$ SSMs, yet remains vastly more scalable than the $O(T)$ KV cache of Transformers.

Key Results

The quantitative gains are substantial, particularly in retrieval-heavy tasks:

  • Associative Recall (MQAR): Bilateral attention achieved 96.12% mean accuracy, compared to 76.37% for standard log-linear attention and 70.53% for Mamba-2.
  • RULER (Long Context): At a context length of 6144 tokens, the bilateral model nearly doubled the performance of the forward-only baseline, raising the mean score from 26.97% to 50.03%.
  • Downstream Retrieval: Bilateral attention outperformed the forward log-linear baseline on 7 out of 8 tasks, narrowing the gap significantly between efficient recurrent models and full Transformers.
  • Language Modeling: It achieved the lowest perplexity on WikiText-2 (30.21) among the non-Transformer models tested.

Limitations and Future Work

  • Parameter Overhead: While the authors used parameter-matching for fair comparison, adding a second hierarchy naturally increases the architectural complexity.
  • Extreme Contexts: The experiments capped at 6144 tokens. While the $O(\log T)$ scaling is theoretically sound for much longer sequences, real-world performance at 100k+ tokens remains to be seen.
  • Delta-Rule Integration: The authors suggest that their bilateral structure could be combined with "DeltaNet" (which uses a delta rule for state updates) to further improve how associations are stored and overwritten.
  • Hardware Kernels: To reach the speed of highly optimized Transformers (like those using FlashAttention), custom CUDA kernels for the bilateral prefix scan will likely be necessary.

Summary updated

Abstract

Sequence models represent past context at different resolutions, using token-level keys and values, fixed-size recurrent states, or hierarchies of compressed summaries. Full attention supports strong associative recall but requires quadratic work during training and prefill and a linearly growing key-value cache during inference. Linear attention and state-space models reduce these costs through fixed-size recurrent memory, but this compression can limit recall. Log-linear attention offers a middle ground by maintaining logarithmically many state matrices. However, its hierarchy favors finer resolution near the current query while compressing earlier context into coarser summaries. To complement this allocation of resolution, we introduce bilateral log-linear attention, which pairs the existing hierarchy with a second hierarchy anchored at the sequence origin. By combining their reads, the two branches provide finer access to both early and recent context while remaining causal. We derive recurrent and chunkwise parallel formulations for the added branch, preserving log-linear training and prefill work, logarithmic decoding work per token, and logarithmic persistent state storage at fixed feature dimensions and chunk size. In multi-query associative recall, this design raises mean overall test accuracy from 76.37% to 96.12% over forward log-linear attention across multiple training seeds. For pretrained language models under approximate parameter matching, it raises the mean score on six selected RULER needle-in-a-haystack tasks from 26.97% to 50.03% at a context length of 6144 tokens. In the same setting, bilateral attention also outperforms forward log-linear attention on seven of eight downstream retrieval tasks, including question answering and information extraction.
BibTeX
@misc{islam2026bilateral,
  author = {Kazi Ashik Islam and Guojing Cong},
  title = {{Bilateral Log-Linear Attention}},
  year = {2026},
  eprint = {2611.18974},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18974},
}
Figure