TL;DR
This paper introduces "Parallel Decoding in One Sequence" (PDOS), a novel method to speed up Large Language Model (LLM) reasoning on parallelizable tasks. By identifying parallel steps and decoding them concurrently within a single sequence using a modified attention mask, PDOS achieves significant speedups (up to nearly 100%) without increasing memory usage or compromising answer quality.
What Problem Does This Paper Address?
Large Language Models (LLMs) are increasingly capable of complex reasoning. However, their autoregressive nature means they generate text token by token, which is inherently sequential. This becomes a bottleneck for "parallelizable reasoning tasks" – tasks where multiple steps can be executed independently and concurrently. While existing methods like "skeleton-of-thoughts" and "Medusa" attempt to accelerate this, they often suffer from increased memory usage, API costs, or require retraining models. This paper aims to accelerate parallelizable reasoning in LLMs efficiently, without these drawbacks.
Methods
The core innovation is the "Parallel Decoding in One Sequence" (PDOS) method, which operates in three stages:
- Identifying Parallelizable Steps: The LLM is prompted to generate a "skeleton" of the reasoning process. Special tokens (
####) are used to mark the beginning of parallelizable steps, and only their titles are generated, followed by an ellipsis (......). A terminator token (####%%%%) signals the end of a parallel block. This stage leverages the LLM's ability to identify parallelism without explicit pre-definition. - Parallel Decoding: For identified parallelizable steps, the method reuses the KV cache from non-parallelizable parts. Crucially, it employs a novel "tree-like attention mask" to decode multiple tokens per forward pass, treating each parallel step as a branch. This allows concurrent generation of tokens for different branches while sharing common prefixes.
- Concatenation and Continuation: The decoded content from the parallel steps is concatenated with the non-parallelizable parts, and the model resumes normal decoding. If new parallel blocks are detected, the process loops back to Stage 1.
The "tree-like attention mask" is a modification of the standard attention mechanism, specifically designed to handle multiple parallel branches within a single sequence.
Datasets
The paper evaluates its method on three types of parallelizable tasks:
- Retrieval Task: A student resume retrieval dataset (difficult-retrieval) with 100 samples, requiring parallel GPA analysis.
- Multi-Document QA Task: 2-Wiki MultihopQA from LongBench, with 200 samples, requiring parallel document analysis.
- Planning Task: A custom dataset designed to analyze multiple aspects (e.g., economy, politics, culture) and propose solutions, with 100 samples.
The models used for evaluation include Qwen2.5-7B-Instruct, Qwen2.5-14B-Instruct, phi-4-mini-instruct, and QwQ-32B.
Key Insights and Ideas
- Leveraging LLM's Implicit Parallelism Detection: Instead of hardcoding parallelism, the method relies on prompting the LLM to identify parallelizable steps, making it more flexible.
- Efficient Parallelism within a Single Sequence: The key breakthrough is achieving parallel decoding within one sequence using a custom attention mask, avoiding the memory overhead of creating multiple sequences or batches.
- No Retraining or Extra Data: The method works by modifying the decoding process and prompting, requiring no model retraining or additional training data, which enhances its adaptability.
- Trade-off Management: While aiming for speed, the method carefully balances acceleration with maintaining answer quality, showing minimal degradation in most cases.
Key Results
The PDOS method demonstrated significant improvements across the evaluated tasks:
- Retrieval Task: Nearly doubled decoding speed with no decrease in answer quality.
- Multi-Document QA Task: Improved decoding speed by nearly 60%, with a slight increase in answer quality.
- Planning Task: Increased decoding speed by over 50%, with answer quality largely maintained.
Compared to baselines like Skeleton-of-Thoughts (SoT), PDOS achieved comparable or better speedups while avoiding the significant memory increases SoT experienced on long-context tasks. It also outperformed Chain-of-Draft (CoD) in answer quality, especially when CoD was used alone.
Limitations and Future Work
- Small/Large Models: For very small or very large models, Stage 1 (skeleton generation) might fail to produce the required format, hindering subsequent stages.
- Synthetic Datasets: The current evaluation is primarily on synthetic datasets. More complex, real-world tasks might present new challenges.
- Model Architecture Dependence: The method's effectiveness might vary across different model architectures.
Future work could explore extending PDOS to more complex task types, investigating its applicability across a wider range of model architectures and sizes, and addressing the limitations observed with extremely large or small models.
Summary updated