# Learning to Keep a Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding

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

## Key facts

- Cited by 28 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 25 of its 44 references that are in the map.
- First posted on arXiv 17 Feb 2025.

## Placed in

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

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Gemma: Open Models Based on Gemini Research and Technology](https://mlsanity.com/paper/2403.08295/) (2024)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [Length-Controlled AlpacaEval: A Simple Way to Debias Automatic Evaluators](https://mlsanity.com/paper/2404.04475/) (2024)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [Reducing Activation Recomputation in Large Transformer Models](https://mlsanity.com/paper/2205.05198/) (2022)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [TaskMatrix.AI: Completing Tasks by Connecting Foundation Models with Millions of APIs](https://mlsanity.com/paper/2303.16434/) (2023)
- [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [Accelerating Transformer Inference for Translation via Parallel Decoding](https://mlsanity.com/paper/2305.10427/) (2023)
- [BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling](https://mlsanity.com/paper/2406.00832/) (2024)
- [Hydra: Sequentially-Dependent Draft Heads for Medusa Decoding](https://mlsanity.com/paper/2402.05109/) (2024)
- [APAR: LLMs Can Do Auto-Parallel Auto-Regressive Decoding](https://mlsanity.com/paper/2401.06761/) (2024)

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

- [CaP-X: A Framework for Benchmarking and Improving Coding Agents for Robot Manipulation](https://mlsanity.com/paper/2603.22435/) (2026)
- [Parallel-R1: Towards Parallel Thinking via Reinforcement Learning](https://mlsanity.com/paper/2509.07980/) (2025)
- [Learning Adaptive Parallel Reasoning with Language Models](https://mlsanity.com/paper/2504.15466/) (2025)
- [ParaThinker: Native Parallel Thinking as a New Paradigm to Scale LLM Test-time Compute](https://mlsanity.com/paper/2509.04475/) (2025)
- [Hogwild! Inference: Parallel LLM Generation via Concurrent Attention](https://mlsanity.com/paper/2504.06261/) (2025)
- [Multiverse: Your Language Models Secretly Decide How to Parallelize and Merge Generation](https://mlsanity.com/paper/2506.09991/) (2025)
- [Group Think: Multiple Concurrent Reasoning Agents Collaborating at Token Level Granularity](https://mlsanity.com/paper/2505.11107/) (2025)
- [Self-Steering Language Models](https://mlsanity.com/paper/2504.07081/) (2025)
- [ASPD: Unlocking Adaptive Serial-Parallel Decoding by Exploring Intrinsic Parallelism in LLMs](https://mlsanity.com/paper/2508.08895/) (2025)
- [A Survey on Parallel Reasoning](https://mlsanity.com/paper/2510.12164/) (2025)
- [SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models](https://mlsanity.com/paper/2506.05745/) (2025)
- [Planned Diffusion](https://mlsanity.com/paper/2510.18087/) (2025)
- [ThreadWeaver: Adaptive Threading for Efficient Parallel Reasoning in Language Models](https://mlsanity.com/paper/2512.07843/) (2025)
- [The Era of Agentic Organization: Learning to Organize with Language Models](https://mlsanity.com/paper/2510.26658/) (2025)
- [Asynchronous Reasoning: Training-Free Interactive Thinking LLMs](https://mlsanity.com/paper/2512.10931/) (2025)
- [Generalized Parallel Scaling with Interdependent Generations](https://mlsanity.com/paper/2510.01143/) (2025)
- [Accelerating Structured Chain-of-Thought in Autonomous Vehicles](https://mlsanity.com/paper/2602.02864/) (2026)
- [Reasoning Shift: How Context Silently Shortens LLM Reasoning](https://mlsanity.com/paper/2604.01161/) (2026)
- [Sharing State Between Prompts and Programs](https://mlsanity.com/paper/2512.14805/) (2025)
- [Divide-and-Conquer CoT: RL for Reducing Latency via Parallel Reasoning](https://mlsanity.com/paper/2601.23027/) (2026)
- [PaDoc: Layout-Grounded Parallel Decoding for Document Parsing](https://mlsanity.com/paper/2608.06146/) (2026)
- [Parallel Decoder Transformer: Planner-Conditioned Latent Coordination for Model-Intrinsic Parallel Generation](https://mlsanity.com/paper/2512.10054/) (2025)
- [Regulating Branch Parallelism in LLM Serving](https://mlsanity.com/paper/2605.06914/) (2026)
- [Parason: Revealing Subtask and Trial Parallelism in LLM Reasoning](https://mlsanity.com/paper/2608.24658/) (2026)
- [Line-Coupled Language Model](https://mlsanity.com/paper/2609.07129/) (2026)
- [LLMs are General Asynchronous Agents](https://mlsanity.com/paper/2609.35427/) (2026)
- [JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs](https://mlsanity.com/paper/2610.03296/) (2026)
- [SchemaWeaver: Accelerating On-Device Mobile Agentic AI via Schema-Guided Parallel LLM Decoding](https://mlsanity.com/paper/2610.17436/) (2026)

## Abstract (arXiv)

Decoding with autoregressive large language models (LLMs) traditionally occurs sequentially, generating one token after another. An emerging line of work explored parallel decoding by identifying and simultaneously generating semantically independent chunks of LLM responses. However, these techniques rely on hand-crafted heuristics tied to syntactic structures like lists and paragraphs, making them rigid and imprecise. We present PASTA, a learning-based system that teaches LLMs to identify semantic independence and express parallel decoding opportunities in their own responses. At its core are PASTA-LANG and its interpreter: PASTA-LANG is an annotation language that enables LLMs to express semantic independence in their own responses; the language interpreter acts on these annotations to orchestrate parallel decoding on-the-fly at inference time. Through a two-stage finetuning process, we train LLMs to generate PASTA-LANG annotations that optimize both response quality and decoding speed. Evaluation on AlpacaEval, an instruction following benchmark, shows that our approach Pareto-dominates existing methods in terms of decoding speed and response quality; our results demonstrate geometric mean speedups ranging from 1.21x to 1.93x with corresponding quality changes of +2.2% to -7.1%, measured by length-controlled win rates against sequential decoding baseline.