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

arXiv: https://arxiv.org/abs/2601.03043 · HTML: https://mlsanity.com/paper/2601.03043/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 6 Jan 2026.

## Builds on (most cited first, 21 of 21)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025)
- [DeepSeekMoE: Towards Ultimate Expert Specialization in Mixture-of-Experts Language Models](https://mlsanity.com/paper/2401.06066/) (2024)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://mlsanity.com/paper/2410.10819/) (2024)
- [Marco-o1: Towards Open Reasoning Models for Open-Ended Solutions](https://mlsanity.com/paper/2411.14405/) (2024)
- [ReSum: Unlocking Long-Horizon Search Intelligence via Context Summarization](https://mlsanity.com/paper/2509.13313/) (2025)
- [SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference](https://mlsanity.com/paper/2502.18137/) (2025)
- [LoongServe: Efficiently Serving Long-Context Large Language Models with Elastic Sequence Parallelism](https://mlsanity.com/paper/2404.09526/) (2024)
- [PQCache: Product Quantization-based KVCache for Long Context LLM Inference](https://mlsanity.com/paper/2407.12820/) (2024)
- [MemServe: Context Caching for Disaggregated LLM Serving with Elastic Memory Pool](https://mlsanity.com/paper/2406.17565/) (2024)
- [ClusterKV: Manipulating LLM KV Cache in Semantic Space for Recallable Compression](https://mlsanity.com/paper/2412.03213/) (2024)
- [MiMo-Audio: Audio Language Models are Few-Shot Learners](https://mlsanity.com/paper/2512.23808/) (2025)
- [Answer Convergence as a Signal for Early Stopping in Reasoning](https://mlsanity.com/paper/2506.02536/) (2025)
- [Uncertainty-Guided Chain-of-Thought for Code Generation with LLMs](https://mlsanity.com/paper/2503.15341/) (2025)
- [DeepServe: Serverless Large Language Model Serving at Scale](https://mlsanity.com/paper/2501.14417/) (2025)
- [Directional Diffusion-Style Code Editing Pre-training](https://mlsanity.com/paper/2501.12079/) (2025)

## Built on by (most cited first, 3 of 3)

- [IndexCache: Accelerating Sparse Attention via Cross-Layer Index Reuse](https://mlsanity.com/paper/2603.12201/) (2026)
- [HySparse: A Hybrid Sparse Attention Architecture with Oracle Token Selection and KV Cache Sharing](https://mlsanity.com/paper/2602.03560/) (2026)
- [On the Trade-off Between Information Loss and Generalization in Sparse Attention](https://mlsanity.com/paper/2610.04424/) (2026)

## Abstract (arXiv)

Large language models (LLMs) demonstrate strong capabilities across a wide range of complex tasks and are increasingly deployed at scale, placing significant demands on inference efficiency. Prior work typically decomposes inference into prefill and decode stages, with the decode stage dominating total latency. To reduce time and memory complexity in the decode stage, a line of work introduces sparse-attention algorithms. In this paper, we show, both empirically and theoretically, that sparse attention can paradoxically increase end-to-end complexity: information loss often induces significantly longer sequences, a phenomenon we term ``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.