Lil: Less is Less When Applying Post-Training Sparse-Attention Algorithms in Long-Decode Stage

Large language models (LLMs) demonstrate strong capabilities across a wide range of complex tasks and are increasingly deployed at scale, placing substantial demands on inference efficiency. Prior work typically decomposes inference into prefill and decode stages, with the decode stage dominating total latency, especially in reasoning-intensive tasks. To reduce time and memory complexity in the decode stage, a line of work introduces sparseattention algorithms. In this paper, we show, both empirically and theoretically, that sparse attention can paradoxically increase end-toend complexity: information loss often induces substantially longer sequences. We term this problem "Less is Less" (Lil). To mitigate the Lil problem, we propose an early-stopping algorithm that detects the threshold where information loss exceeds information gain during sparse decoding. Our early-stopping algorithm reduces token consumption by up to 90% with a marginal accuracy degradation of less than 2% across reasoning-intensive benchmarks.