mlsanityData to 14 Oct 2026

DeFT: Decoding with Flash Tree-attention for Efficient Tree-structured LLM Inference

arXiv 2404.00242 ↗First posted 30 Mar 2024cs.CL cs.AIcited by 19

On the map: Efficient LLM inference and serving → KV cache optimization

Abstract (arXiv)

Large language models (LLMs) are increasingly employed for complex tasks that process multiple generation calls in a tree structure with shared prefixes of tokens, including few-shot prompting, multi-step reasoning, speculative decoding, etc. However, existing inference systems for tree-based applications are inefficient due to improper partitioning of queries and KV cache during attention calculation. This leads to two main issues: (1) a lack of memory access (IO) reuse for KV cache of shared prefixes, and (2) poor load balancing.As a result, there is redundant KV cache IO between GPU global memory and shared memory, along with low GPU utilization. To address these challenges, we propose DeFT(Decoding with Flash Tree-Attention), a hardware-efficient attention algorithm with prefix-aware and load-balanced KV cache partitions. DeFT reduces the number of read/write operations of KV cache during attention calculation through KV-Guided Grouping, a method that avoids repeatedly loading KV cache of shared prefixes in attention computation. Additionally, we propose Flattened Tree KV Splitting, a mechanism that ensures even distribution of the KV cache across partitions with little computation redundancy, enhancing GPU utilization during attention computations. By reducing 73-99% KV cache IO and nearly 100% IO for partial results during attention calculation, DeFT achieves up to 2.23/3.59x speedup in the end-to-end/attention latency across three practical tree-based workloads compared to state-of-the-art attention algorithms. Our code is available at https://github.com/LINs-lab/DeFT.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 36 of its 48 references that are in the map. First posted on arXiv 30 Mar 2024.

Builds on

36 of 48 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Bifurcated Attention: Accelerating Massively Parallel Decoding with Shared Prefixes in LLMs13 Mar
  2. 2024ChunkAttention: Efficient Self-Attention with Prefix-Aware KV Cache and Two-Phase Partition23 Feb
  3. 2023Efficient Memory Management for Large Language Model Serving with PagedAttention12 Sep

Other references · 33

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  4. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  6. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  7. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
  8. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  9. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,218
  10. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,141
  11. 2021Measuring Coding Challenge Competence With APPScited by 902
  12. 2022Solving math word problems with process- and outcome-based feedbackcited by 901
21 more
  1. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 886
  2. 2023Reasoning with Language Model is Planning with World Modelcited by 861
  3. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Headscited by 843
  4. 2019Plug and Play Language Models: A Simple Approach to Controlled Text Generationcited by 799
  5. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 717
  6. 2020Recipes for building an open-domain chatbotcited by 593
  7. 2023SqueezeLLM: Dense-and-Sparse Quantizationcited by 294
  8. 2023Prompt Cache: Modular Attention Reuse for Low-Latency Inferencecited by 268
  9. 2017Lexically Constrained Decoding for Sequence Generation Using Grid Beam Searchcited by 237
  10. 2023Self-Evaluation Guided Beam Search for Reasoningcited by 196
  11. 2018Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translationcited by 182
  12. 2021NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristicscited by 154
  13. 2020NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraintscited by 149
  14. 2018Learning to Write with Cooperative Discriminatorscited by 119
  15. 2016Guided Open Vocabulary Image Captioning with Constrained Beam Searchcited by 105
  16. 2024Hydragen: High-Throughput LLM Inference with Shared Prefixescited by 73
  17. 2022NaturalProver: Grounded Mathematical Proof Generation with Language Modelscited by 72
  18. 2023FlashDecoding++: Faster Large Language Model Inference on GPUscited by 71
  19. 2023Lookahead: An Inference Acceleration Framework for Large Language Model with Lossless Generation Accuracycited by 37
  20. 2024APAR: LLMs Can Do Auto-Parallel Auto-Regressive Decodingcited by 24
  21. 2024RelayAttention for Efficient Large Language Model Serving with Long System Promptscited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 6; 2026: 12.

19 papers.

Sort:

By area:

  1. 2024A Survey on Large Language Model Acceleration based on KV Cache Managementcited by 131
  2. 2025A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworkscited by 21
  3. 2025FR-Spec: Accelerating Large-Vocabulary Language Models via Frequency-Ranked Speculative Samplingcited by 20
  4. 2025Generative AI Act II: Test Time Scaling Drives Cognition Engineeringcited by 15
  5. 2026TALON: Confidence-Aware Speculative Decoding with Adaptive Token Treescited by 13
  6. 2025CoDec: Prefix-Shared Decoding Kernel for LLMscited by 4
  7. 2026Bole: Efficient Tree Speculation for Hybrid-Attention Language Modelscited by 3
  8. 2026D^2SD: Accelerating Speculative Decoding with Dual Diffusion Draft Modelscited by 2
  9. 2025Saffron-1: Safety Inference Scalingcited by 1
  10. 2026Even GPT-5.2 Can't Count to Five: The Case for Zero-Error Horizons in Trustworthy LLMscited by 1
  11. 2026AREAL-DTA: Dynamic Tree Attention for Efficient Reinforcement Learning of Large Language Modelscited by 1
  12. 2026MAC-Attention: a Match-Amend-Complete Scheme for Fast and Accurate Attention Computationcited by 1
7 more
  1. 2026PaDoc: Layout-Grounded Parallel Decoding for Document Parsingcited by 1
  2. 2026Intra-Prompt Parallel Decoding for Common-Context Question Answeringcited by 1
  3. 2025TyphoonMLA: A Mixed Naive-Absorb MLA Kernel For Shared Prefixcited by 0
  4. 2026RadixMLP -- Intra-batch Deduplication for Causal Transformerscited by 0
  5. 2026Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inferencecited by 0
  6. 2026Mahalanobis-Based Multi-Head Attention for Complex State Propagationcited by 0
  7. 2026LumoTree: Path-Parallel Speculative Verification for Hybrid Language Modelscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026OasisKV: Scaling In-Decode KV Cache Beyond HBM with Lookahead Sparse Prefetching
  2. 2025Inference-Cost-Aware Dynamic Tree Construction for Efficient Inference in Large Language Models
  3. 2026PackInfer: Compute- and I/O-Efficient Attention for Batched LLM Inference
  4. 2026CATS: Cascaded Adaptive Tree Speculation for Memory-Limited LLM Inference Acceleration
  5. 2025FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving
  6. 2024ShadowKV: KV Cache in Shadows for High-Throughput Long-Context LLM Inference
  7. 2025PAT: Accelerating LLM Decoding via Prefix-Aware Attention with Resource Efficient Multi-Tile Kernel
  8. 2026Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache