Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity

• URL: http://arxiv.org/abs/2605.22476v1
• Date: Thu, 21 May 2026 13:35:48 GMT
• Title: Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity
• Abstract summary: We show that most mass concentrates in local block-diagonal neighborhoods with a light cross-block residue.<n>We derive a blockwise evaluation of a resolvent-style operator that keeps within-block interactions exact and routes cross-block interactions through a reduced system.<n>Our method matches the dense operator's accuracy while reducing wall-clock time by $12-29%$ under a standardized measurement protocol.
• Score: 45.829192030010006
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Entity tracking requires maintaining and updating latent states for entities and attributes over long sequences. Recent task-specific attention operators can compress deep Transformer stacks into a few layers by performing multi-hop state propagation within a single layer, but their dense evaluation remains expensive. We show that in this setting, learned attention is strongly structured: most mass concentrates in local block-diagonal neighborhoods with a light cross-block residue. Exploiting this, we derive a blockwise evaluation of a resolvent-style operator that keeps within-block interactions exact and routes cross-block interactions through a reduced system. The resulting evaluation is subquadratic in sequence length $O(n^{4/3}d)$ (and $O(n^{7/3})$ when $d\approx n$). On controlled tracking benchmarks, our method matches the dense operator's accuracy while reducing wall-clock time by $12-29\%$ under a standardized measurement protocol, and is up to $2.4 \times$ faster than a compact dense Transformer at comparable exact-match accuracy. We further provide ablations over block size and model capacity, and identify a limitation: performance collapses when the number of simultaneously evolving properties exceeds the number of attention heads.

Related papers

• A*-Thought-V2: Efficient Latent Reasoning via Geometric Dynamics of LLM [40.07171947823021]
  Chain-of-Thought (CoT) improves the reasoning ability of Large Language Models (LLMs) but incurs substantial computation and context costs.<n>We present A*-Thought-V2, a geometric dynamics of LLM guided framework that models CoT as a hidden-state trajectory and replaces hard deletion with an explicit-implicit interleaved latent architecture.
  arXiv  Detail & Related papers  (2026-09-07T17:56:20Z)
• CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration [67.17709877327232]
  Cate KV is a hybrid KV cache method that retains only critical token information for consistent heads.<n>Cate KV reduces memory usage by up to $2.72times$ and accelerates decoding by $2.18times$ in single-sample inputs.
  arXiv  Detail & Related papers  (2026-08-31T06:02:37Z)
• A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking [0.5076419064097734]
  We introduce a held-out transition-pair falsifier for finite non-Abelian group tracking.<n>In a controlled $S_3 times S_3$ benchmark, a projected recurrent state model trained only on length-8 sequences produces error-free final-state predictions.
  arXiv  Detail & Related papers  (2026-06-05T13:26:41Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• CAWN: Continuous Acoustic Wave Networks for Autoregressive Language Modeling [46.16066322190728]
  We introduce the Continuous Acoustic Wave Network (CAWN), a fully continuous sequence-mixing architecture.<n>Instead of discrete matrix-based attention, CAWN projects hidden states into multi-headed complex-domain phasors.<n>To prevent signal degradation over ultra-long contexts, we introduce a dual-gated Selective Phase Resonance mechanism.
  arXiv  Detail & Related papers  (2026-04-05T20:13:22Z)
• Topology-Aware Block Coordinate Descent for Qubit Frequency Calibration of Superconducting Quantum Processors [9.256953420444077]
  Pre-execution calibration is a major bottleneck for operating quantum processors.<n>We show that the widely-used Snake Sequence is equivalent to Block Coordinate Descent (BCD)<n>These results provide a scalable, implementation-ready workflow for frequency calibration on NISQ-era processors.
  arXiv  Detail & Related papers  (2026-01-15T09:09:36Z)
• Adaptive t Design Dummy-Gate Obfuscation for Cryogenic Scale Enforcement [0.0]
  Cloud quantum services can reveal circuit structure and timing through scheduler metadata, latency patterns, and co-tenant interference.<n>We introduce NADGO, a scheduling and obfuscation stack that enforces operational privacy for gate-model workloads.<n>We prototype the approach on a 4-qubit superconducting tile with cryo-CMOS control and evaluate both depth-varied local-random circuits and small QAOA instances.
  arXiv  Detail & Related papers  (2025-08-31T12:12:48Z)
• AnchorAttention: Difference-Aware Sparse Attention with Stripe Granularity [9.63873831179673]
  Large Language Models (LLMs) with extended context lengths face significant computational challenges during the pre-filling phase.<n>We propose textbfAnchorAttention, a difference-aware, dynamic sparse attention mechanism that efficiently identifies critical attention regions.<n>With its finer-grained sparsity strategy, textbfAnchorAttention achieves higher sparsity rates at the same recall level, significantly reducing computation time.
  arXiv  Detail & Related papers  (2025-05-29T14:59:06Z)
• Treeformer: Dense Gradient Trees for Efficient Attention Computation [24.045251327736814]
  We show how to speed up attention computation by enforcing different attention structures such as sparsity, low-rank, approximating attention using kernels. Based on such hierarchical navigation, we design Treeformer which can use one of two efficient attention layers -- TF-Attention and TC-Attention. We demonstrate that our Treeformer architecture can be almost as accurate as baseline Transformer while using 30x lesser FLOPs in the attention layer.
  arXiv  Detail & Related papers  (2022-08-18T18:31:40Z)
• CloudAttention: Efficient Multi-Scale Attention Scheme For 3D Point Cloud Learning [81.85951026033787]
  We set transformers in this work and incorporate them into a hierarchical framework for shape classification and part and scene segmentation. We also compute efficient and dynamic global cross attentions by leveraging sampling and grouping at each iteration. The proposed hierarchical model achieves state-of-the-art shape classification in mean accuracy and yields results on par with the previous segmentation methods.
  arXiv  Detail & Related papers  (2022-07-31T21:39:15Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)
• Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
  We propose Combiner, which provides full attention capability in each attention head while maintaining low computation complexity. We show that most sparse attention patterns used in existing sparse transformers are able to inspire the design of such factorization for full attention. An experimental evaluation on both autoregressive and bidirectional sequence tasks demonstrates the effectiveness of this approach.
  arXiv  Detail & Related papers  (2021-07-12T22:43:11Z)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  We formulate novel fast NonLocal blocks, capable of reducing complexity from quadratic to linear with no loss in performance. The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks.
  arXiv  Detail & Related papers  (2021-07-06T19:51:37Z)
• LoCo: Local Contrastive Representation Learning [93.98029899866866]
  We show that by overlapping local blocks stacking on top of each other, we effectively increase the decoder depth and allow upper blocks to implicitly send feedbacks to lower blocks. This simple design closes the performance gap between local learning and end-to-end contrastive learning algorithms for the first time.
  arXiv  Detail & Related papers  (2020-08-04T05:41:29Z)

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.