아임계 시퀀스 복잡도를 가진 엔티티 추적을 위한 구조적 희소 어텐션 (Structured-Sparse Attention)

엔티티 추적 (Entity tracking)은 긴 시퀀스에 걸쳐 엔티티와 속성에 대한 잠재 상태 (latent states)를 유지하고 업데이트하는 것을 요구합니다. 최근의 태스크 특화 어텐션 연산자 (task-specific attention operators)들은 단일 레이어 내에서 멀티 홉 상태 전파 (multi-hop state propagation)를 수행함으로써 깊은 Transformer 스택을 몇 개의 레이어로 압축할 수 있지만, 이들의 밀집 평가 (dense evaluation)는 여전히 비용이 많이 듭니다. 본 연구에서는 이러한 설정에서 학습된 어텐션 (learned attention)이 강력하게 구조화되어 있음을 보여줍니다: 대부분의 질량 (mass)은 가벼운 블록 간 잔차 (cross-block residue)를 가진 국소적 블록 대각 근방 (local block-diagonal neighborhoods)에 집중됩니다. 이를 활용하여, 우리는 블록 내 상호작용은 정확하게 유지하고 블록 간 상호작용은 축소된 시스템을 통해 라우팅하는 resolvent 스타일 연산자의 블록 단위 평가 (blockwise evaluation) 방식을 도출합니다. 결과적인 평가는 시퀀스 길이 $O(n^{4/3}d)$에 대해 아임계 (subquadratic)이며 ($d ext extapprox } n$일 때는 $O(n^{7/3})$), 표준화된 측정 프로토콜 하에서 통제된 추적 벤치마크를 통해 우리 방법이 밀집 연산자 (dense operator)의 정확도와 일치하면서도 실제 실행 시간 (wall-clock time)을 $12-29%$ 단축함을 보여주었습니다. 또한, 유사한 완전 일치 (exact-match) 정확도에서 컴팩트한 밀집 Transformer (compact dense Transformer)보다 최대 $2.4\times$ 더 빠릅니다. 우리는 더 나아가 블록 크기와 모델 용량에 대한 절제 연구 (ablations)를 제공하며, 한계점을 식별합니다: 동시에 진화하는 속성 (properties)의 수가 어텐션 헤드 (attention heads)의 수를 초과할 때 성능이 붕괴됩니다.