Research map / Large language models / Language, safety and interpretability
Learning to Keep a Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PASTA, a learned asynchronous decoding system where an LLM annotates semantically independent chunks in its own response with a custom tag language, and a two-stage SFT plus BoNBoN preference optimization trains it to trade off quality and decoding speedup.
Problem
Autoregressive LLM decoding is sequential and inefficient; existing parallel asynchronous decoding methods (SoT, APAR) rely on hand-crafted syntactic heuristics (regex over lists/paragraphs), which are rigid and imprecise.
Approach
Teach the LLM to annotate semantic independence in its own output via a learned XML-like annotation language (PASTA-Lang: promise/sync/async tags), with an interpreter that runs asynchronous decoding threads and a KV-cache interleaving layout; preference optimization (BoNBoN) with a score combining theoretical speedup and quality optimizes the latency-quality trade-off.
Key results
- PASTA models achieve geometric mean realized speedups from 1.21x (52.3% LC win rate) to 1.93x (42.9% win rate) on AlpacaEval.
- PASTA-2-2 reaches 1.62x speedup with about 5% win-rate drop, matching APAR's speedup (1.6x) with 4.3% higher win rate.
- SoT applied to Baseline-SFT gives no speedup, while SoT on official Gemma-IT gives 1.61x with a 12% win-rate drop.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use learned Pasta-Lang annotations with preference optimization at λ=2 | Pasta-BoN · AlpacaEval | length-controlled win rate: +4.3% | Helped |
| Use Pasta-BoN (r=2, λ=2) instead of APAR | Asynchronous decoding on Gemma 7B · AlpacaEval | realized speedup: 1.6x vs 1.62x | No clear effect |
| Use Pasta-BoN (r=2, λ=1) instead of APAR | Asynchronous decoding on Gemma 7B · AlpacaEval | realized speedup: 20.6% higher speedup | Helped |
| Apply SoT decoding to Gemma-IT | Gemma-IT · AlpacaEval | length-controlled win rate: 12% | Hurt |
| Decrease the quality weight λ to optimize more aggressively for speedup (ablation) | Pasta-BoN · AlpacaEval | realized speedup: 1.21x to 1.93x | Mixed |
| Increase the number of preference optimization iterations (ablation) | Pasta · AlpacaEval | quality-speedup trade-off | Helped |
| Predict asynchronous block lengths in multiples of ten (Pred-10X) instead of fixed-length assignment (ablation) | Pasta-SFT · AlpacaEval | quality | Helped |
| Predict asynchronous block lengths exactly (Pred-1X) rather than use fixed-length assignment (ablation) | Pasta-SFT · AlpacaEval | quality | Helped |
| Use theoretical speedup alone as the preference efficiency score instead of theoretical parallelism alone (ablation) | Pasta-BoN · AlpacaEval | realized speedup | Helped |
| Optimize the preference score for theoretical parallelism alone rather than theoretical speedup (ablation) | Pasta-BoN · AlpacaEval | realized speedup | Hurt |
| Optimize the preference score using the harmonic mean of theoretical speedup and parallelism instead of theoretical speedup alone (ablation) | Pasta-BoN · AlpacaEval | realized speedup | No clear effect |
| Use arithmetic mean of theoretical speedup and parallelism as the preference efficiency score (ablation) | Pasta-BoN · AlpacaEval | quality-speedup trade-off | Mixed |
Surprising findings
- Pasta-SFT model without preference optimization shows high theoretical parallelism but little realized speedup, because the induced parallelism is redundant content that hurts quality.
- SoT yields no speedup on the Baseline-SFT model, suggesting prompt-based methods depend on strong instruction-following ability.
Limitations
- Relies on a proprietary model (Gemini 1.5 Flash) for annotation and Gemini 1.5 Pro for quality judging during training.
- Evaluated only on AlpacaEval with a single 7B base model and greedy decoding at batch size 1.
- Position ID prediction and fixed-shape KV-cache assumptions add engineering complexity.
Experimental setup
Datasets: SlimOrca AlpacaEval
Benchmarks: AlpacaEval
Metrics: length-controlled win rate realized speedup (geometric mean) theoretical speedup theoretical parallelism
Baselines: Baseline-SFT sequential decoding APAR Skeleton-of-Thought (SoT)
Builds on: BoNBoN IPO Skeleton-of-Thought APAR
Closest papers by meaning
- AdaDecode: Accelerating LLM Decoding with Adaptive Layer Parallelism (ICML 2025 · similarity 0.89)
- ATTS: Asynchronous Test-Time Scaling via Conformal Prediction (ICLR 2026 · similarity 0.89)
- Mean-Field Parallel Decoding for Discrete Diffusion Language Models (NeurIPS 2026 · similarity 0.89)
- Accelerating Diffusion LLMs via Adaptive Parallel Decoding (NeurIPS 2025 · similarity 0.89)
- Gumiho: A Hybrid Architecture to Prioritize Early Tokens in Speculative Decoding (ICML 2025 · similarity 0.88)
- Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.