Research map / Learning theory and algorithms / Matrix and tensor methods

Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models

ICML 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Structured low-rank learning · 3 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.

Defines a dynamic (online) version of exact attention computation D^{-1}AV under entry updates to K and V, gives a lazy-update data structure with sub-linear-amortized update and n^a query time, and a conditional lower bound under the Hinted MV conjecture.

Problem

Maintaining the exact softmax-style attention output D^{-1} exp(QK^T) V under single-entry updates to K and V while answering entry queries fast; static attention is known to be hard to speed up, and LLM parameters change during training.

Approach

Applies lazy-update techniques from dynamic algorithms (rank-1 update lists recomputed every n^a steps) to the exp-based attention matrix, with a fine-grained lower bound reduction from the Hinted MV conjecture showing the trade-off is conditionally near-optimal.

Key results

• Data structure with O(n^{omega(1,1,tau)-tau}) amortized update time and O(n^{1+tau}) query time for the (Q-free) update case, using O(n^2) space.
• Under the Hinted MV conjecture, no algorithm achieves amortized update O(n^{omega(1,1,tau)-tau-Omega(1)}) together with query time O(n^{1+tau-Omega(1)}), so the upper bound is conditionally optimal.
• The lower bound extends to the normalized ODAMV problem via a reduction constructing instances with padded zero blocks.

Limitations

• Purely theoretical; no experiments on actual LLMs.
• Lower bound relies on the Hinted MV conjecture, which is unproven.
• Analysis assumes d = O(n) and the exact (not approximate) attention computation.

Experimental setup

Metrics: amortized update time worst-case query time

Builds on: Hinted MV conjecture OMV conjecture lazy update (Cohen, Lee, Song 2019) Alman and Song 2023 static attention hardness

Closest papers by meaning

• HyperAttention: Long-context Attention in Near-Linear Time (ICLR 2024 · similarity 0.89)
• SEA: Sparse Linear Attention with Estimated Attention Mask (ICLR 2024 · similarity 0.86)
• Scaling Stick-Breaking Attention: An Efficient Implementation and In-depth Study (ICLR 2025 · similarity 0.86)
• Various Lengths, Constant Speed: Efficient Language Modeling with Lightning Attention (ICML 2024 · similarity 0.86)
• Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix (ICLR 2025 · similarity 0.86)
• A Training-Free Sub-quadratic Cost Transformer Model Serving Framework with Hierarchically Pruned Attention (ICLR 2025 · similarity 0.85)