提出新型稀疏注意力机制，高效追踪实体属性变化。
Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity
- 利用注意力结构化特性，分块计算并保留块内精确交互
- 序列复杂度降至O(n^4/3 d)，比传统方法快12%-29%
- 适合长序列实体追踪，尤其对属性数不超过注意力头数的场景
实体追踪需在长序列中持续维护与更新实体及其属性的隐状态。现有特定任务注意力算子可通过单层多跳状态传播压缩深层Transformer，但其密集计算仍耗时。我们发现该场景下学习到的注意力高度结构化：大部分权重集中于局部块对角邻域，跨块残差较弱。基于此，我们推导出一种分块评估的松弛型算子，保持块内交互精确，通过降维系统处理跨块交互。计算复杂度为O(n^{4/3}d)（当d≈n时为O(n^{7/3})）。在可控追踪基准上，该方法在精度上匹配密集算子，标准化测试下壁钟时间减少12%-29%，且在相近准确率下比紧凑密集Transformer快达2.4倍。进一步分析了块大小与模型容量的影响，并指出局限性：当同时演化的属性数超过注意力头数时性能急剧下降。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。