Block-Attention for Efficient Prefilling

• URL: http://arxiv.org/abs/2409.15355v5
• Date: Sun, 13 Apr 2025 14:02:47 GMT
• Title: Block-Attention for Efficient Prefilling
• Authors: Dongyang Ma, Yan Wang, Lan Tian,
• Abstract summary: We introduce Block-attention, an attention mechanism designed to address the increased inference latency and cost in Retrieval-Augmented Generation (RAG) scenarios.<n>By defining each passage as a block, Block-attention enables us to reuse the KV states of passages that have been seen before.<n>Block-attention significantly reduces the time to first token (TTFT) and floating point operations (FLOPs) to a very low level.
• Score: 6.916657784681611
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce Block-attention, an attention mechanism designed to address the increased inference latency and cost in Retrieval-Augmented Generation (RAG) scenarios. Traditional approaches often encode the entire context in an auto-regressive manner. Instead, Block-attention divides retrieved documents into discrete blocks, with each block independently calculating key-value (KV) states except for the final block. In RAG scenarios, by defining each passage as a block, Block-attention enables us to reuse the KV states of passages that have been seen before, thereby significantly reducing the latency and the computation overhead during inference. The implementation of Block-attention involves block segmentation, position re-encoding, and fine-tuning the LLM to adapt to the Block-attention mechanism. Experiments on 11 diverse benchmarks, including RAG, ICL, and general domains, demonstrate that after block fine-tuning, the Block-attention model not only achieves performance comparable to that of full-attention models, but can also seamlessly switch between the block and full attention modes without any performance loss. Notably, Block-attention significantly reduces the time to first token (TTFT) and floating point operations (FLOPs) to a very low level. It only takes 45 ms to output the first token for an input sequence with a total length of 32K. Compared to the full-attention models, the TTFT and corresponding FLOPs are reduced by 98.7% and 99.8%, respectively. Additionally, in Appendix A, we elaborate on how Block-attention is applied in Game AI scenario and the substantial potential benefits it entails. We strongly suggest researchers in the gaming field not to overlook this section.

Related papers

• MAGE: All-[MASK] Block Already Knows Where to Look in Diffusion LLM [9.69241599043101]
  Block diffusion LLMs are emerging as a promising next paradigm for language generation, but their use of KV caching makes memory access a dominant bottleneck in long-context settings.<n>This work identifies a key opportunity unique to block diffusion: attention at the first All-[MASK] denoising step reliably predicts important KV entries and budget requirements.<n>MAGE achieves near-lossless accuracy with a fraction of the KV budget while delivering up to 3-4x end-to-end speedup.<n>A lightweight fine-tuning strategy further strengthens [MASK]-guided patterns with minimal cost, requiring only a few hours of training on
  arXiv  Detail & Related papers  (2026-02-15T16:07:51Z)
• Advancing Block Diffusion Language Models for Test-Time Scaling [73.54022593833638]
  We propose a unified framework for test-time scaling in BDLMs.<n>We introduce adaptivity in both decoding and block-wise generation.<n>We show that applying BACD and TCCF to TDAR-8B yields significant improvements over strong baselines.
  arXiv  Detail & Related papers  (2026-02-10T09:05:07Z)
• FlashBlock: Attention Caching for Efficient Long-Context Block Diffusion [51.1618564189244]
  FlashBlock is a cached block-external attention mechanism that reuses stable attention output, reducing attention computation and KV cache access without modifying the diffusion process.<n> Experiments on diffusion language models and video generation demonstrate up to 1.44$times$ higher token throughput and up to 1.6$times$ reduction in attention time, with negligible impact on generation quality.
  arXiv  Detail & Related papers  (2026-02-05T04:57:21Z)
• PISA: Piecewise Sparse Attention Is Wiser for Efficient Diffusion Transformers [37.401543107035046]
  Diffusion Transformers are fundamental for video and image generation, but their efficiency is bottlenecked by the quadratic complexity of attention.<n>We propose PISA, a training-free Piecewise Sparse Attention that covers the full attention span with sub-quadratic complexity.
  arXiv  Detail & Related papers  (2026-02-01T07:47:06Z)
• Block Sparse Flash Attention [29.499030734003952]
  Block-Sparse FlashAttention is a drop-in replacement for FlashAttention.<n>It computes exact query-key similarities to select the top-k most important value blocks for each query.<n>It achieves up to 1.10x speedup on real-world reasoning benchmarks and up to 1.24x needle-in-a-haystack retrieval tasks.
  arXiv  Detail & Related papers  (2025-12-07T21:20:12Z)
• Sparser Block-Sparse Attention via Token Permutation [46.22204775916057]
  We propose Permuted Block-Sparse Attention (textbfPBS-Attn), a plug-and-play method that leverages the permutation properties of attention to increase block-level sparsity.<n>Powered by our custom permuted-FlashAttention kernels, PBS-Attn achieves an end-to-end speedup of up to $2.75times$ in long-context prefilling.
  arXiv  Detail & Related papers  (2025-10-24T09:11:50Z)
• AdaBlock-dLLM: Semantic-Aware Diffusion LLM Inference via Adaptive Block Size [7.442463267121892]
  Diffusion-based large language models (dLLMs) are gaining attention for their inherent capacity for parallel decoding.<n>This paper presents the first systematic investigation challenging the fixed block size assumption in semi-AR decoding.<n>We introduce AdaBlock-dLLM, a training-free, plug-and-play scheduler that adaptively aligns block boundaries with semantic steps by adjusting block size during runtime.
  arXiv  Detail & Related papers  (2025-09-30T15:53:56Z)
• Blockwise SFT for Diffusion Language Models: Reconciling Bidirectional Attention and Autoregressive Decoding [60.06816407728172]
  Discrete diffusion language models have shown strong potential for text generation.<n>Standard supervised fine-tuning misaligns with semi-autoregressive inference.<n>We propose Blockwise SFT, which partitions responses into fixed-size blocks.
  arXiv  Detail & Related papers  (2025-08-27T02:49:33Z)
• BlockFFN: Towards End-Side Acceleration-Friendly Mixture-of-Experts with Chunk-Level Activation Sparsity [66.94629945519125]
  We introduce a novel MoE architecture, BlockFFN, as well as its efficient training and deployment techniques.<n>Specifically, we use a router integrating ReLU activation and RMSNorm for differentiable and flexible routing.<n>Next, to promote both token-level sparsity (TLS) and chunk-level sparsity ( CLS), CLS-aware training objectives are designed, making BlockFFN more acceleration-friendly.
  arXiv  Detail & Related papers  (2025-07-11T17:28:56Z)
• XAttention: Block Sparse Attention with Antidiagonal Scoring [10.517760961650279]
  Long-context Transformer Models (LCTMs) are vital for real-world applications but suffer high computational costs due to attention's quadratic complexity. We introduce XAttention, a plug-and-play framework that dramatically accelerates long-context inference in Transformers models using sparse attention.
  arXiv  Detail & Related papers  (2025-03-20T17:59:58Z)
• ParallelComp: Parallel Long-Context Compressor for Length Extrapolation [51.68913021512016]
  Extrapolating ultra-long contexts (text length >128K) remains a major challenge for large language models (LLMs)<n>In this work, we propose ParallelComp, a parallel long-context compression method that effectively overcomes the memory bottleneck.<n>We achieve a 1.76x improvement in chunk throughput, thereby achieving a 23.50x acceleration in the prefill stage with negligible performance loss.
  arXiv  Detail & Related papers  (2025-02-20T07:10:43Z)
• Next Block Prediction: Video Generation via Semi-Autoregressive Modeling [92.60177942930946]
  Next-Block Prediction (NBP) is a semi-autoregressive (semi-AR) framework for video generation. NBP employs bidirectional attention within each block, enabling tokens to capture more robust spatial dependencies. Our model achieves FVD scores of 103.3 on UCF101 and 25.5 on K600, outperforming the vanilla NTP model by an average of 4.4.
  arXiv  Detail & Related papers  (2025-02-11T17:57:53Z)
• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  We propose a tile-based strategy that partitions the contrastive loss calculation into arbitrary small blocks. We also introduce a multi-level tiling strategy to leverage the hierarchical structure of distributed systems. Compared to SOTA memory-efficient solutions, it achieves a two-order-of-magnitude reduction in memory while maintaining comparable speed.
  arXiv  Detail & Related papers  (2024-10-22T17:59:30Z)
• SeerAttention: Learning Intrinsic Sparse Attention in Your LLMs [10.702409298302547]
  SeerAttention learns the block-level attention sparsity from the Large Language Models itself. Inspired by the gating mechanism in Mixture of Experts (MoE), SeerAttention augments the conventional attention with a learnable gate. Our evaluation results demonstrate that SeerAttention achieves better model accuracy and lower latency for long-context pre-filling.
  arXiv  Detail & Related papers  (2024-10-17T07:07:09Z)
• Realizing Unaligned Block-wise Pruning for DNN Acceleration on Mobile Devices [1.6114012813668932]
  Block-wise pruning is promising due to its low accuracy drop tradeoff for speedup gains. Unaligned block pruning (UBP) addresses this by allowing blocks to be selected at arbitrary positions. We propose a pseudo-optimal yet fast block selection algorithm called Block Expansion and Division.
  arXiv  Detail & Related papers  (2024-07-29T01:59:06Z)
• Improved Block Merging for 3D Point Cloud Instance Segmentation [6.632158868486343]
  The proposed work improves over the state-of-the-art by allowing wrongly labelled points of already processed blocks to be corrected through label propagation. Our experiments show that the proposed block merging algorithm significantly and consistently improves the obtained accuracy for all evaluation metrics employed in literature.
  arXiv  Detail & Related papers  (2024-07-09T16:06:34Z)
• Towards Effective and Efficient Non-autoregressive Decoding Using Block-based Attention Mask [74.64216073678617]
  AMD performs parallel NAR inference within contiguous blocks of output labels concealed using attention masks. A beam search algorithm is designed to leverage a dynamic fusion of CTC, AR Decoder, and AMD probabilities. Experiments on the LibriSpeech-100hr corpus suggest the tripartite Decoder incorporating the AMD module produces a maximum decoding speed-up ratio of 1.73x.
  arXiv  Detail & Related papers  (2024-06-14T13:42:38Z)
• Towards Universal Dense Blocking for Entity Resolution [49.06313308481536]
  We propose UniBlocker, a dense blocker that is pre-trained on a domain-independent, easily-obtainable corpus. By conducting domain-independent pre-training, UniBlocker can be adapted to various downstream blocking scenarios without requiring domain-specific fine-tuning. Our experiments show that the proposed UniBlocker, without any domain-specific learning, significantly outperforms previous self- and unsupervised dense blocking methods.
  arXiv  Detail & Related papers  (2024-04-23T08:39:29Z)
• Accurate Block Quantization in LLMs with Outliers [0.6138671548064355]
  The demand for inference on extremely large scale LLMs has seen enormous growth in recent months. The problem is aggravated by the exploding raise in the lengths of the sequences being processed. Various quantization techniques have been proposed that allow accurate quantization for both weights and activations.
  arXiv  Detail & Related papers  (2024-03-29T12:15:06Z)
• CBQ: Cross-Block Quantization for Large Language Models [66.82132832702895]
  Post-training quantization (PTQ) has played a key role in compressing large language models (LLMs) with ultra-low costs. We propose CBQ, a cross-block reconstruction-based PTQ method for LLMs. CBQ employs a cross-block dependency using a reconstruction scheme, establishing long-range dependencies across multiple blocks to minimize error accumulation.
  arXiv  Detail & Related papers  (2023-12-13T07:56:27Z)
• Constant Memory Attention Block [74.38724530521277]
  Constant Memory Attention Block (CMAB) is a novel general-purpose attention block that computes its output in constant memory and performs updates in constant computation. We show our proposed methods achieve results competitive with state-of-the-art while being significantly more memory efficient.
  arXiv  Detail & Related papers  (2023-06-21T22:41:58Z)
• Blockchain Large Language Models [65.7726590159576]
  This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, BlockGPT, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System.
  arXiv  Detail & Related papers  (2023-04-25T11:56:18Z)
• SC-Block: Supervised Contrastive Blocking within Entity Resolution Pipelines [75.5113002732746]
  This paper presents SC-Block, a blocking method that utilizes supervised contrastive learning for positioning records in the embedding space. We benchmark SC-Block against eight state-of-the-art blocking methods. For measuring the overall runtime, we determine candidate sets with 99.5% pair completeness and pass them to the matcher.
  arXiv  Detail & Related papers  (2023-03-06T13:49:41Z)
• Self-Supervised Learning of Perceptually Optimized Block Motion Estimates for Video Compression [50.48504867843605]
  We propose a search-free block motion estimation framework using a multi-stage convolutional neural network. We deploy the multi-scale structural similarity (MS-SSIM) loss function to optimize the perceptual quality of the motion compensated predicted frames.
  arXiv  Detail & Related papers  (2021-10-05T03:38:43Z)
• Streaming End-to-End ASR based on Blockwise Non-Autoregressive Models [57.20432226304683]
  Non-autoregressive (NAR) modeling has gained more and more attention in speech processing. We propose a novel end-to-end streaming NAR speech recognition system. We show that the proposed method improves online ASR recognition in low latency conditions.
  arXiv  Detail & Related papers  (2021-07-20T11:42:26Z)
• Algorithm to Compilation Co-design: An Integrated View of Neural Network Sparsity [0.8566457170664925]
  We apply structured and unstructured pruning to attention weights of transformer blocks of the BERT language model. We study relationships between modeling decisions and their direct impact on sparsity-enhanced execution.
  arXiv  Detail & Related papers  (2021-06-16T15:13:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.