# ProPD: Dynamic Token Tree Pruning and Generation for LLM Parallel Decoding

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 14 of its 20 references that are in the map.
- First posted on arXiv 21 Feb 2024.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Multi-News: a Large-Scale Multi-Document Summarization Dataset and Abstractive Hierarchical Model](https://mlsanity.com/paper/1906.01749/) (2019)
- [How Good Are GPT Models at Machine Translation? A Comprehensive Evaluation](https://mlsanity.com/paper/2302.09210/) (2023)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023)
- [Accelerating Transformer Inference for Translation via Parallel Decoding](https://mlsanity.com/paper/2305.10427/) (2023)
- [Full Stack Optimization of Transformer Inference: a Survey](https://mlsanity.com/paper/2302.14017/) (2023)
- [Fast and Robust Early-Exiting Framework for Autoregressive Language Models with Synchronized Parallel Decoding](https://mlsanity.com/paper/2310.05424/) (2023)
- [LLMCad: Fast and Scalable On-device Large Language Model Inference](https://mlsanity.com/paper/2309.04255/) (2023)
- [Conversational Question Answering: A Survey](https://mlsanity.com/paper/2106.00874/) (2021)
- [RecycleGPT: An Autoregressive Language Model with Recyclable Module](https://mlsanity.com/paper/2308.03421/) (2023)

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

- [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (2024)
- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Speculative Decoding and Beyond: An In-Depth Survey of Techniques](https://mlsanity.com/paper/2502.19732/) (2025)
- [LP-Spec: Leveraging LPDDR PIM for Efficient LLM Mobile Speculative Inference with Architecture-Dataflow Co-Optimization](https://mlsanity.com/paper/2508.07227/) (2025)
- [Closer Look at Efficient Inference Methods: A Survey of Speculative Decoding](https://mlsanity.com/paper/2411.13157/) (2024)
- [Amphista: Bi-directional Multi-head Decoding for Accelerating LLM Inference](https://mlsanity.com/paper/2406.13170/) (2024)
- [EfficientNav: Towards On-Device Object-Goal Navigation with Navigation Map Caching and Retrieval](https://mlsanity.com/paper/2510.18546/) (2025)
- [SSSD: Simply-Scalable Speculative Decoding](https://mlsanity.com/paper/2411.05894/) (2024)
- [POSS: Position Specialist Generates Better Draft for Speculative Decoding](https://mlsanity.com/paper/2506.03566/) (2025)
- [S2-MoE: Enabling Efficient Self-Speculative Decoding for Mixture-of-Experts on Edge Devices](https://mlsanity.com/paper/2608.15018/) (2026)
- [Speculative Sampling with Reinforcement Learning](https://mlsanity.com/paper/2601.12212/) (2026)
- [Reciprocal Guidance: Orchestrating Draft and Verify Budgets for Advancing the Diffusion-AR Self-Speculation Frontier](https://mlsanity.com/paper/2609.34388/) (2026)

## Abstract (arXiv)

Recent advancements in generative large language models (LLMs) have significantly boosted the performance in natural language processing tasks. However, their efficiency is hampered by the inherent limitations in autoregressive token generation. While parallel decoding with token tree verification, e.g., Medusa, has been proposed to improve decoding parallelism and efficiency, it often struggles with maintaining contextual relationships due to its independent token prediction approach and incurs significant verification overhead, especially with large tree sizes and batch processing. In this paper, we propose ProPD, an efficient LLM parallel decoding framework based on dynamic token tree pruning and generation. ProPD features an advanced early pruning mechanism to efficiently eliminate unpromising token sequences to improve verification efficiency. Additionally, it introduces a dynamic token tree generation algorithm to balance the computation and parallelism of the verification phase in real-time and maximize the overall efficiency across different batch sizes, sequence lengths, and tasks, etc. We verify ProPD across a diverse set of datasets, LLMs, and batch sizes and demonstrate ProPD consistently outperforms existing decoding algorithms by 1.1-3.2x.