From Logical to Computational Sparsity: Structure-Aware Block-Sparse Attention for Long-Code Completion

Code Large Language Models face critical Time-To-First-Token (TTFT) latency challenges when handling long code completion due to the quadratic complexity (O(n 2 )) of attention mechanisms. While existing sparse attention methods attempt to address this issue, they suffer from three key limitations: (1) general sparse patterns cause excessive accuracy degradation without considering code structure, (2) code-specific methods achieve only logical sparsity without actual computational speedup, and (3) limited adaptation to complex scenarios such as repository-level completion. We propose SabreCoder, a training-free Structure-aware block-sparse attention mechanism that bridges the gap between logical and computational sparsity. SabreCoder parses code into semantic chunks, constructs chunklevel sparse patterns through dependency analysis and similarity matching, and maps them to GPU-friendly block-sparse formats. Extensive experiments on LCC and CrossCodeEval benchmarks demonstrate that SabreCoder reduces TTFT by 45-55% while maintaining accuracy within 3% of dense attention. Global Attn Intra-Chunk Attn Dependency Attn Similarity Attn Block-Level Attn Code Chunks GPU Blocks Mapping Code File Code Chunks Dependency Graph Code Analysis 2 X 2 Kernel Size Apply Sparse Chunk-Level Sparse Block-Level Sparse Mapping from flextls.protocol import Protocol from flextls.field import VectorUInt16Field from flextls.field import ServerNameListField class Extension(Protocol): def init(self, **kwargs): Protocol.init(self, **kwargs) ...