Learning to Keep a Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding
Authors: Tian Jin
Ellie Y Cheng
Zachary Ankner
Nikunj Saunshi
Blake M Elias
Amir Yazdanbakhsh
Jonathan Ragan-Kelley
Suvinay Subramanian
Michael Carbin
Venue: ICML 2025 poster (2025)
Keywords: parallel decoding
large language model
inference acceleration
Primary area: deep_learning->large_language_models
TL;DR: We make LLM parallel-generate semantically independent chunks of tokens.

Abstract: Decoding with autoregressive language models traditionally occurs sequentially, generating one token after another. Recent attempts to introduce parallelism require a pre-determined structure in the generated content to implement parallel generation, such as by pattern-matching on bullet points. In this work, we present a new technique to automate parallel generation by dynamically exploiting the semantic independence of generation outputs to implement asynchronous decoding. We introduce an annotation language Pasta-Lang for language models to initiate asynchronous decoding at inference time. We also develop an accompanying Pasta-Lang interpreter that performs on-the-fly asynchronous decoding, effectively implementing parallel generation and speeding up inference. We present an instruction-finetuning dataset with Pasta-Lang-annotated responses for teaching LLMs to annotate semantic independence with Pasta-Lang as well as the methodology for creating the dataset. Our evaluation shows using the interpreter with a Pasta-Lang-equipped model achieves significant speedup while maintaining the same generation quality.

Learning to Keep a Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding
Tian Jin 1+ Ellie Y. Cheng") 1
Zachary Ankner' Nikunj Saunshi? Blake M. Elias
Amir Yazdanbakhsh
Jonathan Ragan-Kelley!
Suvinay Subramanian
Michael Carbin'
Abstract
1. Introduction
Autoregressive decoding is a fundamental efficiency bottle- neck in large language model (LLM) inference. Contem- porary LLMs routinely require multiple seconds or even minutes of decoding time to complete user requests (Jiang et al., 2024; Touvron et al., 2023; Jaech et al., 2024; Guo et al., 2025). This latency stems from the sequential nature of autoregressive decoding, which leads inefficient hard- ware utilization during inference. While training achieves 40-60% Model Flops Utilization (MFU) (Korthikanti et al., 2022), inference typically achieves less than 20% MFU (Pope et al., 2022).
Decoding with autoregressive large language models (LLMs) traditionally occurs sequentially, generating one token after another. An emerging line of work explored parallel decoding by identi- fying and simultaneously generating semantically independent chunks of LLM responses. However, they rely on hand-crafted heuristics tied to syn- tactic structures like lists and paragraphs, making them rigid and imprecise. We present PASTA, a learning-bas based system that teaches LLMs to iden- tify semantic independence and express parallel decoding opportunities in their own responses. At its core PASTA-LANG and its interpreter: PASTA-LANG is annotation language that en- ables LLMs to express semantic independence in their own responses; the language interpreter acts on these annotations to orchestrate parallel decod- ing on-the-fly at inference time. Through two- stage finetuning process, we train LLMS to gener- ate PASTA-LANG annotations that optimize both response quality and decoding speed. Evaluation AlpacaEEval, an instruction following bench- mark, shows that our approach Pareto-dominates existing methods in terms of decoding speed and response quality; our results demonstrate geomet- ric mean speedups ranging from 1.21x to 1.93x with corresponding quality changes of +2.2% -7.1%, measured by length-controlled win rates against sequential decoding baseline.
Semantic Independence. Recent works like Skeleton-of- Thought (SoT) and APAR leverage semantic independence in LLM responses as source of parallelism, decoding inde- pendent chunks of tokens in parallel. Namely, these meth- ods decode semantically independent chunks (contiguous sequences of tokens) of tokens in the response in paral- lel. Given request, SoT first produces a bullet-point out- line, then applies eeguular-xpressiion prppesssion-baedd syntactic pattern matching to extract points that are then expanded in parallel. APAR, contrast, applies eegular-expression -baeed syntac- tic pattern matching training data identify structures like lists and paragraphs, and finetunes an LLM to decode in parallel the item descriptions given list items and the paragraph bodies given the first sentences.
While semantic independence broadly exists in LLM re- sponses, relying purely on syntactic heuristics mesifested as hand-crafted regular expressions limitations. First, these heuristics lack scalability, requiring manual engineering to capture more semantic independence, even as more training compute becomes available. Second, they lack robustness, failing to detect semantic indepen- dence when responses deviate from expected patterns, even by a missing punetuation mark. These limitations moti- vate a learning-basee approach optimize LLMs' ability to identify semantic independence, enabling LLMs find parallelization opportunities beyond fixed patterns.
identify them has
Eqqual contribution. Part this work was completed dur- ing an internship at Google. 'MIT CSAIL, Cambridge, USA Google Research, New York, USA 'Google, Mountain View, USA *Google DeepMind, Mountain View, USA. Correspon- dence to: Tian Jin <tianjin @ essii.mmt..cdus........ Michacl Carbin <mcarbin csail.mit.cdux.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Learned Parallel Decoding. We present PASTA, a system that teaches LLMs to identify and annotate parallelization

---

Learning to Keep Promise
User: the endpoints of line segment are (2) and (10, 4), what is the length of the segment?
Assistant (Decoding...):
<promise topii="coordinatees""
2
<promise topic="length formula"/>
3
<sync/>
Assistant: <promise topic= > To find the length of the line segment, we need to use the formula for the
distance between two points in plane. The two points -2) and (10, 4) <promise topic="length formula"/>
5 The
length of line segment be found using the formula: Length v((22 x1)^ [yz y1
<sync/>
6
Let's plug in the
coordinates: Length v((100 2y^2 (4 (-2))2) Length v((8)2 (6)^2) Length v(64 36) Length v1000 Length 10 So, the
length of the line segment is 10.
Figure 1. Example response from a PASTA model executed by the PASTA-LANG interpreter. The interpreter begins with only the main thread. It first decodes ()) and it creates asynchronous decoding thread, which decodes 4 in red. In parallel, the main thread decodes ② It creates another asynchronous decoding thread, which contains both the <promise /> tag on coordinates extraction and the <promi /e/ tag on length formula in its prefix, and decodes ( in green. The main thread continues decoding in parallel to both threads to get 3 It wait at this point until all other threads complete. The interpreter then inserts each asynchronous content after their corresponding ppromise/> tags. Finally, the interpreter decodes 6. with both the asynchronously decoded content in the prefix.
opportunities in their own responses. Our system consists of a set of annotations that extend the model's 's vocabulary for asynchronous decoding, an interpreter that acts on these annotations to orchestrate parallel decoding, and a finetun- ing procedure that optimizes LLMs' ability to identify and express parallelization opportunities. Through this system, L.MM develop and execute their own asynchronous decod- ing strategies. In Figure 1, we show how these components implement asynchronous decoding.
model to create the Pasta-SFT dataset by annotating the SlimOrea
finetuning dataset (Lian et al., 2023b) with PASTA-LANG annotations that identify semantically in- dependent chunks compatible with asynchronous decoding. PASTA then finetunes an LLM on this dataset to produce a model that generates PASTA-LANG annotations.
In the second stage, PASTA creates another dataset by sam- pling the finetuned LLM and scoring each output based on its quality and latency. Unlike traditional uses of prefer- ence optimization improve response quality (Gui et al., 2024; Rafailov et al., 2023), we adapt one such algorithm for PASTA to optimize for both output quality and latency. PASTA applies preference optimization to the finetuned LLM on this dataset to produce a model with improved output quality and latency. This second stage of finetuning features a quality weight hyperparameter that controls the trade-off between quality and speedup. Through repeated iterations of the second stage, PASTA creates models that respond with increasingly better quality and lower latency.
Annotations. Our annotation language, PASTA-LANG (PArallel STructure Annotation LANGuage), enables LLMs to express semantic independence in their responses. In Fig- ure 1, we show a PASTA- LGG-annottte response. The <promise/> > tags serve as placeholders for content chunks that are semantically independent to each other, such as ex- tracting coordinates (Tag ! and recalling the line segment length formula (Tag 2) Each <promi se/> tag includes topic attribute that concisely describes the chunk. When further decoding steps require conditioning on tokens that are still being asynchronously decoded, the LLM issues an <syne/> tag to indicate so, as shown at 3 in Figure 1.
Results. Varying the quality weight hyperparameter, PASTA produces a suite of models with different quality-latency trade-offs. We evaluate these models on 805 representative instruction-followin prompts from AlpacaEval (Li et al., 2023; Dubois et al., 2024). After one iteration of prefer- ence optimization, these models Pareto-dominate all exist- ing asynchronous decoding methods. Additional iterations of preference optimization further improve the speedup- quality Pareto frontier, showing no signs of saturation even after two iterations. Our results demonstrate geometric mean speedups ranging from 1.21x to 1.93x' with corre- sponding quality changes of +2.2% -7.1 % respectively, measured as in length-controlle win rates
Interpreter. We develop the PASTA-LANG interpreter, which acts on PASTA-LANG annotations to orchestrate asyn- chronous decoding during inference. It launches parallel decoding threads for semantically independent contents marked with <promise/ tags and synchronizes them at <sync/> tags. The interpreter simultaneously decodes mul- tiple non-contiguous token chunks from the LLM, improv- ing overall decoding latency.
Finetuning. Training LLM to generate PASTA-LANG annotations starts with two manual inputs: seven human- crafted demonstrations and a description of the PASTA- LANG annotation language. Prompting the Gemini 1.5 Flash model (Anil et al., 2024) with these manual inputs, the PASTA system initiates an automated two-stage finetuning process. In the first stage, PASTA uses the prompted Gemini
'Geometric mean should be used to compute normalized val- ues (Fleming & Wallace, 1986). However, the prevailing practice in parallel decoding literature uses arithmetic averaging when re- porting speedup, which would show this result as 1.57-2.6x.
2

---

Learning to Keep Promise
Contribution. We present a collection of contributions:
human-defined heuristics. By training an LLM identify and exploit parallelization opportunities, PASTA achieves Pareto-optimal trade-off between speedup and quality as compared to previous asynchronous decoding techniques.
We design PASTA-LANG to be annotation language that enables LLMs to annotate semantically independent chunks of tokens in their own responses.
We implement a PASTA- interpreter that efficiently orchestrates asynchronous decoding based on PASTA-
3. Language and Interpreter Design
LANG annotations at inference time.
PASTA-LANG is an XML-like annotation language designed for a language model to annotate semantic independence in its own response. We present the syntax of the language and the operations of the interpreter in this section.
We develop a two-stage finetuning technique that trains LLMs to identify diverse patterns of semantic indepen- dence in their output and express them through PASTA- LANG annotations, while directly optimizing for both response quality and inference speedup.
Syntax. PASTA-LANG defines three tags: <async> tags which appear in pairs to wrap around blocks of content, and two standalone tags <promise/s and <sync/>. <pr ser// > tag requires two attributes: a string attribute topic and an integer attribute tokens, and must appear before the content block it refers to.
We evaluate our method on AlpacaEval (Li et al., 2023; Dubois et al., 2024), a suite of 805 representa- tive instruction-following prompts, and find our method Pareto-dominate all existing asynchronous decoding meth- ods in terms of quality and speedup.
Interpreter. A PASTA- Leuu--puppppp language model initiates asynchronous decoding by generating the PASTA- LANG tags that the PASTA-LANS interpreter executes to implement asynchronous decoding. We describe here the functionality of each tag and how they are used by the interpreter. Figure 2a shows how the interpreter orchestrates asynchronous decoding.
Implication. PASTA demonstrates the utility of incorporat- ing latency objectives into the standard preference optimiza- tion step during LLM post-training. The effectiveness and scalability of this approach makes it a practical prescription for reducing LLM decoding latency.
2. Asynchronous Decoding
With the user query A as the prefix, the interpreter decodes sequentially until encountering a <prom i se/> tag at tag B.. The topic attribute indicates the topic of the chunk that will be decoded asynchronously, and the takens at- tribute estimates the number of tokens in multiples of 10 in the <asyno> tag. These attributes provide context for decoding future tokens. The interpreter then initiates new asynchronous decoding thread named "Fork#1". The main thread continues decoding in parallel, while the new thread first appends an <asyne> tag to its prefix at C and then de- codes content matching the specified topi until reaching a < /aaync>> tag at (D. The main thread proceeds without con- ditioning on any asynchronously decoded content. When encountering a <sync/> tag at ①.) the interpreter pauses to wait for all asynchronous decoding threads to complete, and enables the language model to condition on asynchronously decoded content for decoding subsequent tokens in (F)
To provide context for how PASTA-LANG relates to other parallel decoding techniques for accelerating LLM decod- ing, we present a dichotomy of parallel decoding techniques. Specifically, a given parallel decoding strategy can be cate- gorized as either performing synchronous or asynchronous decoding. In synchronous decoding, only single chunk is decoded in parallel while the rest of the generation is halted. In contrast, during asynchronous decoding, multi- ple chunks of of the language model's output are decoded independently in parallel.
We consider speculative decoding (Leviathan et al., 2023; Chen et al., 2024; Stem et al., 2018; Cai al., 2024; Ankner al., 2024; He al., 2024; Fu et al., 2024; Spector & Re, 2023; Santilli et al., 2023) as a prototypical example of synchronous decoding. It decodes multiple tokens within single chunk in parallel, but must complete that chunk before moving on to any subsequent tokens.
Efficiency. Our interpreter implementation addresses sev- eral key challenges in efficient asynchronous decoding, with KV-cache management being the core issue. Since ML compilers often requires static tensor shapes for effective compilation (Sabne, 2020; Paszke et al., 2019), we assume fixed batch size and sequence length 2 Implementing asyn- chronous decoding naively as batched decoding faces two suboptimal options: 1) allocate differently sized KV-ccche
In contrast, works such as SoT (Ning et al., 2024) and APAR (Liu et al., 2024) implement asynchronous decoding techniques. Both methods enable decoding to jump ahead in the output sequence and generate tokens before previ- ous positions are filled, resulting in multiple chunks of the output being decoded in paraliel. While our PASTA system also implements asynchronous decoding, we improve upon previous works by employing a surning-based system to identify parallelization opportunities, instead of relying on
We use a batch size of I and max sequence length of 2048 as
in Liang et al. (2025).
3

---

Learning to Keep Promise
User:
If the endpoints of segment are (2, 2) and (10, what the length the segment?
Assistant (Decoding...):
<promise topic="coordinatee" tokens=2 />
<promise topic="length formula" tokens=2 />
<sync/>
Fork#1
Fork#2
Assistant:
<promise topic= "poria"coordinates" tokens 2 />
Assistant:
<promise ppicc"coordinate"" tokens-2 />
<async>
D
To find the length of the line segment, we
<promise
topic="length
formula"
tokens=2
need to use the formula for the distance between two points in a plane. The two points are (2, -2) and (10, 4) </async>
<async>
The length of line segment can be found using
the formula: Length v((x2 x1) + (y2 y1)^2) </async>
Assistant:
<promise "coricccooddiates" tokens=2 />
<async> To find the length of the line segment, we need to use the formula
for the distance between two points in plane. The two points are (2, -2) and (10, 4) </async> <promise topic="length formula" tokens-2 />
<async> The length of line segment can be found using the formula: Length v((x2 x1 (22 y1)²2 </async>
<sync/>
Let's plug in the coordinates: Length v(110 2)^2 (4 (2)) <(8)2 (6)2) v(64 + 36) - v100 10. So, the length
of the line segment
(a) PASTA-LANG interpreter orchestrates parallel decoding. A shows the user prompt. shows the <promi tag which initiates the first asynchronous decoding thread named "Fork#1". C indicates where the interpreter appends <asyne> tag to the prefix of 1ork#1, signaling 1 should complete the promised content with topic "coordinates". D denotes the asynchronous generation by Fork#1. L shows <sync/> tag where the interpreter pauses to wait for asynchronous generations. (F) shows the main thread decodes the remaining content with both asynchronous generations in its prefix.
B
segment?
spromise..
<promise...>
<sync/s
Kasync*
find
<lasynce
Fork#2:
The
length
<tasync>
1-0
I+1
TH2 1+5
1+4
1-22
1=23
T-33
TH54
TwOb
(b) Decoding parallelism and attention patterns at each timestamp. At each timestamp, we show the tokens decoded in parallel in that timestamp. The directed edges between tokens show the attention relationships: each edge connects token the very token that may attend to it. A token can then attend to any tokens that can be reached by following these edges back through the graph. A shows the last few tokens of the user query. B shows when the interpreter decodes <promise semmise// token, after which immediately appends an <async> token for Fork#1 at C Subsequently at DD, Fork#1 begins asynchronous decoding, while in paraliel, the interpreter creates another decoding thread (Fork#2), At E when encountering the <sync/> >, the interpreter pauses the main thread until all asynchronous threads complete. Finally at (F) the main thread resumes decoding with both asynchronously decoded content in its prefix.
the
AogmenE
coromsee
spromise.
TO
cosyncc
Aid
The
the
lengeh
pians
KASSYTER
<SyToc
Let's
HIZT
HZZZ
23
HQS
PGB
HOb
HX27
H28
1400
HTS
HE1
T1O
T10
T-22
T-32
Tr32
(c) KV-cache layout throughout parallel decoding. At A the last few tokens of the user prompt, the KV-cache is laid out in typical contiguous manner. Starting at B, the KV-cachu begins to interleave between threads, while inserting the corresponding <async> token for the new thread at D shows parallel decoding in progress, with tokens from Fork#1 being generated while the main thread continues decoding. At (F) the <syne/>>>> token (decoded by the main thread at T=3) is inserted into the KV-cache, After synchronization. the K KV-cache returns to contiguous layout at P
Figure 2. Details for efficient PASTA- LANG interpreter implementation. Color shows the identity of the decoding thread (purple=main. red=Fork#1, green=orktt2); orange denotes interpreter -nseereer-inserredd tokens.

---

Learning to Keep Promise
pools and switch between them upon thread creation and termination, which wastes precious accelerator memory, or 2) pre-allocating fixed number of decoding threads, leading to wasted memory and computation due to inac- tive threads. We further discuss the drawbacks of naive option 2) in Appendix B. Instead, we store KV-cache from all asynchronous decoding threads in a single contiguous pre-allocated memory pool with an interleaved layout.
Instruction- Finetuning Dataset
Annotate training responses with PASTA-LANG using LLM
PASTA SFT Dataset
Base Model
Finetune
Finetune
Figures 2b and 2c illustrates our approach. We denote de- coding timestamp with T and index in the KV-cache pool with i. When only one thread is active at T=0 (A), it ap- pends new V-cachhe sequentially to the pool at i=19-20. When the main thread (purple) decodes a <promise/> to- ken T=1 B,, the interpreter immediately appends an <asyne> token to signal the start of a new thread Fork#1 (O). T=2 (). Fork#1 begins asynchronous decoding, while the interpreter initiates another asynchronous decod- ing thread Fork#2 At T=3, (D), the interpreter decodes 3 tokens in parallel from 3 active threads, where the <syne/> token signals pausing to wait for other threads to complete and therefore this token does not enter into the KV-ccche pool until later. Where as the other two tokens do enter the K KV-cache pool in neighboring positions (i=26-27). The two threads (green/red) continue to decode in parallel, alternat- ing as they append tokens to the KV-cache pool (T=3-22).
PASTA SFT Model
Rejection sample responses based on quality and theoretical speedup
PASTA Model
Rejection Sampled Dataset
Figure 3. PASTA-LANG dataset creation and model training.
4. Training PASTA-LANG Capable Models
We present a two-stage finetuning process that trains an LLM to annotate semantic independence in their own re- sponses using PASTA-LANG, Figure illustraaees the PASTA system pipeline for dataset construction and model training to produce a PASTA-LANG-equipped model.
Building a Pasta-SFT Dataset. The PASTA system pipeline begins by constructing an initial finetuming dataset, which we refer to as the Pasta-SFT dataset. It prompts the Gemini 1.5 Flash (Anil et al., 2024) to add PASTA-LANG anno- tations to responses from an codtruction-oolloviin dataset We provide Gemini 1.5 Flash with 7 human annotated ex- amples and description of the syntax and semantics of PASTA-LANG and have it label a 100K response subset of the SlimOrea dataset (Lian et al., 2023a)². We provide the annotation prompt used in Appendix A.
To prevent cross-thread interference with this interleaved KV-cache layout, we use attention masks to ensure threads cannot attend each other's tokens before synchronization. In Figure 2b, each directed edge connects token to the very next token that may attend to it. A token can attend to any ancestor token reachable by following these edges backward through the graph. A token in an asynchronous thread can only attend to tokens within its own thread and tokens from the main thread that existed before the thread was spawned. For example, the token find (at T=3, red) attends to To (at T=2, red) and segment? ? (at T=0, purple), but cannot attend to the second <async> token (at T=2, orange), the second <promise token (at T=2, purple), or the <syne/> token (at T=3, purple).
Training a Pasta-SFT Model. PASTA then finetunes the base LLM on the Pasta-SFT dataset, producing what we call the Pasta-SFT model. Since the model must decode content after <promise/> >> tags without access to the corresponding <async> content, we implement three key modifications to the standard next-token prediction finetuning algorithm.
First, the attention mask prevents the tokens after a <promise/> from attending to content within its <asyne> tags until <sync/> tag is reached. This enforces the semantic independence constraint between asynchronous blocks. Second, during inference, the position IDs of tokens after <premise/> /> cannot be known until fully decoding the corresponding <async> block. To handle this, we train the model to predict the length of each <async> block in the tokens attribute of its <promise/> tag. This predic- tion enables us to assign estimated position IDs to tokens that follow the <promi se/> >> tag, even before fully decoding the <async> block. Finally, to enable the model to continue
Once the interpreter decodes the <syne/> token in the main thread at T=3 (E) it pauses the main thread to synchro- nize, waiting for both forks to complete: 1ork#1 and Fork#2 decode their </asyne> tokens at T=34 and T=22 respec- tively. After the wait is over at T=34, the interpreter inserts the <sync/> token into the K VV-ccche pool at i=80, and the main thread resumes decoding (F) while conditioning on both forks' asynchronous generations.
While prior works like radix attention (Zheng et al., 2023) enables multiple decoding threads to share attention to a common prefix, our design has to additionally address the challenge of enabling a single decoding thread to attend to multiple asynchronously decoded threads.
Due API limitations, we only successfully annotated 87K/100K instmaction-response pairs as the Pasta-SFT dataset.
5

---

Learning to Keep Promise
decoding past <pronise/ tags, we set the next-token pre- diction target at each <promi se/> to be the first token after its corresponding <asyne> block. This enables the model to skip past placeholder <promise/> tags.
where 0 are the model weights being trained, mii the initial model weights, x is a prompt, y², y are the best and worst-of-N PASTA-LANG-ammotatel responses respec- tively. and a is a hyperparameter to weight the SFT and IPO loss contributions. We set Oinit to be the Pasta-SFT model. We use a learning rate of 5E-7 and set a to 0.005 as recommended by (Gui et al., 2024).
PASTA-LANG Preference Optimization. PASTA further improves the Pasta-SFT model with a second stage of train- ing that directly optimizes for quality and speedup achieved by the PASTA-LANG annotations.
5. Experiment
First, PASTA trains baseline sequential model Baseline- SFT by fine-tuning the same base model on Pasta-SFT dataset without the annotations. Then, for each prompt in the Pasta-SFT dataset, PASTA samples N different PASTA- LANG annotated responses from the Pusta-SFT model using a temperature T. It then scores each of the N sampled re- sponses. We set N- 10 and temperature T = 1. The score for ranking the sampled responses is a combination of:
We evaluated the performance of our PASTA-LANG- equipped model in terms of speedup, parallelism, and re- sponse quality and show that is Pareto-optimal compared to other asynchronous decoding techniques.
5.1. Experimental Setup
Baselines. We present the following baselines: standard autoregressive decoding from Baseline-SFT. APAR de- coding (L.iu et al., 2024) and SoT decoding (Ning et al., 2024). APAR and SoT are examples of asynchronous de- coding techniques relying hand-crafted syntactic heuris- tics. We evaluate sequential autoregressive decoding using the Baseline-SFT model finetuned on the the Pasta-SFT dataset without PASTA-LANG annotations. To evaluate APAR decoding, we train an APAR model again on the same Pasta-SFT dataset, except preprocessed following the official APAR methodology. Using regex and filters, we recreated the APAR heuristics for extracting structured data as described in their work (Liu et al., 2024).
1. Response theoretical speedup - the ratio between (1) the total number of tokens in Baseline-SFTTs response, and (2) the length of the longest sequence that must be decoded sequentially for Pasta-SFT's response. This measures the maximum achievable speedup of Pasta- SFT over Baseline-SFT.
2. Response quality for each sampled response, PASTA computes weniidence-weighted win-loss ratio by com- paring it against the Baseline-SFTTs response and the original SlimOrca response. Each comparison appears in both orders and is judged by Gemini 1.5 Pro, which pro- vides a preference and a probability for that preference between 0 and 1, interpreted as confidence. The final ratio is the confidence--eightee sum of wins divided by the mmffidence-weighee sum of losses.
Models and Hyperparameters. For all experiments, we use Gemma 7B (Mesnard et al., 2024) as the base model. We finetune all models using a batch size of 8, a learning rate that decays linearly from le-5 to O, and train for a total of 4 epochs. We chose these hyperparameters as they maximized the quality of the baseline model." 4 We provide further details on hyperparamter selection in Appendix C.
Each sampled response receives a score: speedup + À x quality, where is the quality weight. For each prompt, PASTA selects the highest and lowest-scoring response as the preferred and un un-preferred example, respectively. We explore alternative scoring methods in Appendix
There are two PASTA specific hyperparamters: X, the quality weight used for building preference pairs (Section 4); and r, the number of BoNBoN preference optimization iterations. We train multiple PASTA models, with À 1, 4, 8 and set 2. We refer to each model as NoNta- We also train PASTA models while optimizing exclusively for quality, denoted as Pasta-BoN-co.
While our methodology is compatible with any LLM prefer- ence optimization algorithm, in this work we use BoNBoN optimization (Gui et al., 2024) for it was the state-of-the-arr algorithm at the time of writing this paper. The BonBon algorithm trains a model to approximate the best-of-N re- sponse distribution by combining an SFT loss on the pre- ferred example with an IPO preference loss (Azar et al., 2024) between the best and worst response. Specifically, the BoNBoN objective is:
Hardware and Software. We evaluate decoding perfor- mance using PyTorch with norch.compile optimization set to maximum auto auto-tuning mode (Paszke et al., 2019). All experiments run on H100 GPUs using greedy decoding. We
LBONBoN (0; 0m)) = Eg,y y --- l log po (v (x)
+ (1 a1-a) po (y (y
|x)
*For reference, our bascline model achieves a 38% length con- trolled win rate against Gemma-7B-in Google's officially released instruction-tuned Gemma-7b model. This comparison demonstrate that despite our smaller-scale experimental setup, our baseline model performs competitively against state-of trt model.
po (y) (z)
-log Par. (u+ + xx)
po (y) (z) 8 )2
6

---

Learning to Keep Promise
Pasta -BoN Quality Weight (A)
Pasta BoN Quality Weight (A)
Pasta Pasta-BoNi/ Quality Weight (A)
GPT-4 LC Win Rate 196)
GPT-4 LC Win Rate (%)
GPT-4 LC Win Rate 196)
40
40
40
30
30
30
20
Baseline-SFT
20
Baseline-SFT
20-
Baseline-SFF
Pasta-SF SFT
Pasta-SFT
Pasta-SFT
Pasta-BoN-A
Pasta-BoNa -oN-
Pasta-Bou Pasta-BoN-A
APAR
10
APAR
10
APAR
SoT
SoT
SoT
0
0
0
1.0
2.0
1.0
2.0
1.0
1.5
2.0
2.5
(Geomean) Realized Speedup
(Geomean) Theoretical Speedup
(Geomean) Theoretical Parailelism
Figure Left (Realized Speedup). PASTA models achieved Pareto-optimal quality-speedul trade-off than asynchronous decoding strategies with hand-crafted heuristics. Middle (Theoretical Speedup). The realized speedup using PASTA-LANG interpreter is close to the theoretical speedup. Right (Theoretical Parallelism). PASTA responses show high degree of parallelism.
use a batch size of as common with parallel decoding literature (Leviathan et al., 2023). To avoid measuring com- pilation overhead, we decode each request twice and only take the timing of the second of two decoding runs.
5.2. Results
The left, middle and right plots in Figure 4 show how re- sponse quality trades off against realized speedup, theoreti- cal speedup, and parallelism respectively across PASTA and baseline models. We mark the baseline (50% win rate with speedups) with an X. An ideal asynchronous decoding strategy should match this baseline in quality while surpass- ing it in speedup; the closer to the top right corner of the plot, the better the technique.
Evaluation. We evaluate all models on the AlpacaEval benchmark (Dubois et al.. 2024; Li et al., 2023), an open ended suite of 805 representative prompts. For each decod- ing method we evaluate, we compute the following metrics:
We measure the realized speedup against the baseline as the ratio between the wall-clock decoding times: baseline model time divided by test model time, both using the PASTA-LANG interpreter.
Pareto-Optimality. The left plot in Figure shows that PASTA models achieve Pareto-optimal trade-off between quality and realized speedup. The best-quality model -oost--BoNooo) achieved 52.3% win rate 1.21x speedup, whereas the best-speedup model (Pasia-BoN-I) achieved 42.9% win rate at 1.93x speedup. The Pasta-Bod -Bott model Pareto-dominate all prior asynchronous decoding tech- niques, achieving superior quality-speedup trade-off.
2.
We calculate the theoretical speedup against the baseline as the ratio between (I) the total number of tokens in the baseline response and (2) the length of the longest sequence that must be decoded sequentially in the test model's response, as described in Section 4.
The APAR model and Pasta-BoN-2 achieved similar speedups (1.6x vs 1.62x), but Pasta- BoN-2 obtained 4.3% higher win rate. This result stems from APAR's 's reliance on syntactic heuristics for identifying semantic independence, which can lead to false positives. Similarly, while APAR and Pasta-BoNy showed comparable win rates (41.2% vs 12.9)) Pasta-BoN-I delivered 20.6% higher speedup. This superior speedup stems from the flexibility of PASTA- LANG'S annotation, which enables asynchronous decoding at any position in the output.
3. We measure the theoretical parallelism in the model output: the ratio of (1) the total number of non-control tokens to (2) the length of the longest sequence of tokens that must be decoded sequentially.
We measure the quality as the onggh-controlled, LLM-as- a-judge win-rate using AlpacaEval benchmark (Li et al., 2023; Dubois al., 2024) when compared the baseline model. We use Gemini 1.5 Pro (Anil al., 2024) as the judge model for development and GPT4 as the judge for evaluation, to prevent reward hacking.
Notably, we do not observe any speedup by SoT (Ning et al., 2024), when applied to Baseline-SFT: We believe that SoT, as a prompt- method, requires the base model to have strong instruction-followee
We aggregate the speedup and parallelism over each prompt in the dataset using the geometric mean".
ability to perform well, and
'The arithmetic mean of ratios can lead to inconsistent results depending on the baseline used to compute the ratio and is there- fore appropriate for our (Fleming Wallace, 1986). How- ever, the prevailing practice parallel decoding literature uses
arithmetic mean when reporting speedup. We provide the speedup computed with arithmetic mean for reference in Appendix

---

Learning to Keep Promise
validated this hypothesis by applying SoT to the stronger of- ficial cnaructtoo-finttunee Gemma-IT model from Google. With this generous implementation, SoT achieves a 1.61x speedup while dropping its win rate by 12%. In contrast, our Pasta-BoN-2 achieves 1.62x speedup with only a 5% drop to win rate.
8
50
Gemini Pro LC WWnn Rate (%)
10th
45
Quality Weight (A)
800% B2....
40
Role of A. We observe that the quality weight serves as an effective control knob for the trade-off' between quality and speedup. A lower weight results in more aggressive optimization for speedup at the cost of reduced quality.
10% R1
35
Pasta-SFT
30
*
Theoretical speedup. Comparing the left (realized speedup) and middle (theoretical speedup) plot in Figure 4 shows that the combination of PASTA-LANG interpreter and PAsTa models deliver realized speedup close to theoretical optimal.
1.5
2.0
2.5
Geomean Theoretical Speedup
Figure 5. Increasing the numher of preference-opimmizatinn rounds steadily improves the quality-latency trade-off.
The right plot in Figure 4 shows that PASTA models achieve high degree of theoretical parallelism. No- tably, while the Pasta-SF7 model starts with high theoretical parallelism, this does not translate into significant decod- ing speedup. This disconnect occurs because the induced parallelism is not effective - the model learns to generate redundant content, which hurts both quality and speedup. Preference optimization effectively mitigates this pathology, as the Pasta-BoN BBN models deliver speedups commensurate with their theoretical parallelism.
Parallelism.
8. We visualize each stage's ' data using distinct colors in Figure 5. To illustrate the difference in quality-speedup trade-off between stages, we computed linear fits for each stage after Pasta-SFT and plotted the linear fit using the same color as each stage.
Results. Figure 5 demonstrates the scalability of preference optimization, increased training compute continuously improves the Pareto frontier toward better trade-offs (i.e., top right corner). As is common when scal- ing LLMs with more training compute (Kaplan et al., 2020), we observe diminishing returns, though we do not observe saturation after two rounds of preference optimization.
Conclusion. PASTA is an effective technique for enabling asynchronous decoding, producing Pareto-dominant per- formance. PASTA also enables flexible trade-off between speedup improvements and response quality.
Observing the linear fits of quality-speedup trade-off within each stage reveals distinct optimization dynamics. The ini- tial 10% of Round preference optimization aggressively optimizes for speedup, moving the group to the right of the plot. However, from 10% Round 2 to 60% Round 2, we observe an emphasis on quality improvements, shifting the group upward. Overall, preference optimization effec- tively navigates the trade-off space by exploring both quality improvement and speedup improvement.
6. Sensitivity Analysis.
In this section, we investigate how three key design choices of the PASTA system impact model quality and latency: a) the number of preference optimization iterations, b) the configurations of positional embeddings, and c) the scoring method for PASTA-LANG annotated responses.
6.1. Number of Iterations
Conclusion. Preference optimization is a scalable technique that improves the speedup qualiity trade-off with increased training compute. Unlike prior asynchronous decoding tech- niques that require hand-crafted syntactic heuristics, our technique directly converts computational resources into better quality and speedup trade-off, offering more scal- able path to improving decoding speed.
We examine how the number of preference optimization iterations affects the quality-speedue trade-off in PASTA models; we observe continuous improvements as training compute increases and find distinct optimization dynamics at different preference optimization iterations.
Methodology. We analyzed the impact of preference opti- mization on the speedup-qualics trade-off by PASTA mod- els at 5 different stages: initial (aka Pasta-SFT), 10% into Round 1, and 100% into Round 1, 10% into Round 2, and 60% into Round 26. The initial stage represented by a sin- gle star, while results from later stages contain four points each, corresponding to quality weights (A) of 1, 2, 4, and
6.2. Positional Embedding
Asynchronous decoding methods introduce uncertainty over the true position of tokens as they are being generated as the output is generated in non-sequential manner. Namely, the main decoding thread is unaware of the true length of of any previously occurring <async> blocks that have not been synchronized. Thus, the main thread must estimate
'We stopped at 60% of Round 2 due to time constraints.
8

---

Learning to Keep Promise
30
Pred-10x
speedup for models finetuned on the Pasta-SFT dataset using each of the different position ID estimation techniques. Length prediction performs the best, achieving quality and speedup metrics matching (or even slightly exceeding) the Oracle. The Pred- 10X variant offers a flexible solution to the position ID assignment problem that is admissible to preference optimization. Based on these results, we adopted Pred-10X our position ID assignment strategy.
Gemini Pro LC Win Rate (%)
29
28
Pred-1x
27
Oracl
Oracle-10x
26
7. Related Work
Const-40
Oracle-1x
After discussing parallel decoding approaches in Section 2, we now turn to other relevant research areas.
25
1.5
1.6
1.7
1.8
1.9
2.0
Geomean Theoretical Speedup
Agent Planning/Tool Use. Our work is related to the idea of agent planning and tool use (Yao et al., 2023; Schick et al., 2023; Shen et al., 2023; Liang et al., 2024; Lu et al., 2023). Prior studies show that L.LM- agents can solve complex tasks by planning and using tools such as web search and external APIs. Our work extends the suite of tools available to LLMs with the PASTA-LANG language and interpreter for improving their own decoding efficiency.
Figure 6. Predicting position IDs multiples of ten (Pred-10x) gives the best quality with minimal speed-up loss.
the number of tokens an <asyne> block before contin- uing generation. If the predicted number of tokens for the <async> block does not match the true number of tokens generated, this can lead to errors the position IDs af- ter synchronization will either not increase monotonically (predicted too few) or contain a gap (predicted too many).
A Approximate Parallelization. Our work extends the idea of approximate parallclization (Udupa et al., 201 I; Misailovic et al., 2012). Udupa et al. (2011) proposed a framework that enables programmers annotate breakable data dependen- cies in program and developed compiler and runtime that exploits these annotations to automatically parallelize oth- erwise sequential regions of code. Misailovic et al. (2012) opportunistically relaxes synchronization primitives in par- allel program to improve parallelism, to program outputs that are acceptably close to the original one. Similarly, we break the sequential decoding process of LLMs into ap- proximately parallelizable and independent components and exploit the parallelism improve decoding efficiency. Our work differs in that instead of relying on end-user annota- tion or compiler analysis, we teach L.MSs to autonomously express parallelism in their own decoding process using the PASTA-LANG annotation language.
Methodology. To minimize the error between the true and predicted position IDs, we compare three different ap- proaches for position ID assignment:
Fixed-length: We make the assumption that each <asyne> block has fixed length. In our experiments, we chose this length to be forty tokens as this is slightly larger than the median <asyne> block length in our training data.
Length Prediction: We train the model to predict the length of each <async> block, and then use the model's predic- tions during decoding. We evaluate two variants that pre- dict <asyne> block lengths at diffferent granularities: 1) Pred-1X: Predict the <asyne> token length exactly; and 2) Pred-10X: Predict the <async> token length as a multiple of ten for coarser granularity.
Oracle: We use the ground truth length of each <asyne> block (i.e. the position IDs of the tokens in the block if the chunk was decoded sequentially) assign position IDs. While the oracle position IDs are infeasible to obtain dur- ing deployment, we evaluate the performance of oracle ID decoding to serve as a reference point for the performance of decoding with no error in the position ID calculations. We evaluate two different granularity for the oracle position IDs: 1) Oracle- 1X: Using the true <asyne> block length: and 2) Oracle-10X 10X: Using the true <async> block length rounded to the nearest multiple of ten. We consider one final oracle baseline, which we refer to as Oracle, where the exact <async> block lengths are used to offset the position IDs but the length is not included in the <promise// tag.
8. Conclusion
We present PASTA, a system that teaches LLMs identify semantically independent chunks in their responses and annotate them for parallel decoding opportunities. Through set of annotations, an interpreter and a finetuning proce- dure, our method enables learned asynchronous decoding.
PASTA is an effective and scalable system which enables learned asynchronous decoding. Evaluation on AlpacaFval demonstrates that our approach Pareto-dominates existing asynchronous decoding methods in terms of quality and speedup. The improvements continue with additional train- ing compute, showing no signs of saturation during our experimental evaluation.
Results. Figure presents both the response quality and

---

Learning to Keep Promise
Impact Statement
Fu, Y., Bailis, P., Stoica, I., and Zhang, H. Break the se- quential dependency of LLM inference using lookahead decoding. In International Conference Machine Learn- ing. 2024.
This work improve the efficiency of LLM inference, which could lead to reduced computational resource requirements and improved accessibility to LLMs.
Gui, L.,, Gârbacea, C.,, and Veitch, V. Bonbon alignment for large language models and the sweetness of best-of-n sampling. In Advances in Neural Information Processing Systems, 2024.
Acknowledgement
This work was supported in-part by the Sloan Foundation and SRC JUMP 2.0 (CoCoSys). We are deeply grateful to William Brandon, Michael Brenner, Gintare Karolina Dziugaite, Xin Dong, Han Guo, Zhun Liu, Jesse Michel, Aniruddha 'Ani' Nrusimha, Ankit Singh Rawat, Narges Shahidi, Ananda Theertha Suresh, Xin Wang, Logan We- ber, Cambridge Yang, and Xiaofan Zhang for their thought- ful feedback and detailed review of this manuscript. This work benefited significantly from the support of the Google CoreML Performance Team. We also thank the extended team at Google Research and Google DeepMind for their valuable contributions to this research.
Guo, D., Yang, D., Zhang, H., et al. Deepseek-rl: Incen- tivizing reasoning capability in Ilms via reinforcement learning. arXiv preprint arXiv:2501.12945. 2025.
He, Z.,, Zhong, Z.,, Cai, T., Lee, J., and He, D. Rest: Retrieval-based speculative decoding. In Conference of the North American Chapter of the Association for Computational Linguistics, 2024.
Jaech, A., Kalai, A., Lerer, A., at. Openai ol system card. arXiv preprint arXiv:2412.16720 2024.
References
Jiang, A. Q., Sablayrolles, A., Roux. A., Mensch, A., Savary, B., Bamford, C., Chaplot, D. S., de las Casas, D., Bou Hanna, E., Bressand, F., Lengyel, G., Bour, G., Lample, G., Renard Lavaud, L.,, Saulnier, L., Lachaux, M.-A., Stock, P., Subramanian, S., Yang, S., Antoniak, S., Le Scao, T., Gervet, T., Lavril, T., Wang. T., Lacroix, T. and El Sayed, W. Mixtral of experts, arXiv preprint wwXhv:241.040888 2024.
Anil, R., Borgeaud, S., Alayrac, J.-B., al. Gemini: A fam- ily of highly capable multimodal models. arXiv preprint arXiv:2312. 11805 2024.
Ankner, Z., Parthasarathy, R., Nrusimha, A., Rinard, C.,, Ragan-Kelley, J., and Brandon, W. Hydra: Sequentially- dependent draft heads for medusa decoding. In Confer- ence on Language Modeling, 2024.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint 17XXi:2001.08366 2020.
Azar, M. G., Guo, Z. D., Piot, B., Munos, R., Rowland, M., Valko, M., and Calandriello, D. A general theoretical paradigm understand learning from human preferences. In International Conference Artificial Intelligence and Statistics, 2024.
Korthikanti, V., Casper, J., Lym, S., McAfee, L.,, Andersch, M.. Shoeybi, M., and Catanzaro, B. Reducing activa- tion recomputation in large transformer models. arXiv preprint arXiv:2205.05719, 2022.
Cai, T., Li, Y., Geng, Z., Peng. H., Lee, J. D., Chen, D., and Dao, T. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads. In Interna- tional Conference on Machine Learning, 2024.
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In Interna- tional Conference on Machine Learning, 2023.
Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifre, L., and Jumper, Accelerating large language model decoding with speculative sampling. In International Conference Learning Representations, 2024.
Li, X., Zhang, T., Dubois, Y., Taori, R., Gulrajani, I. Guestrin, C., Liang, P., and Hashimoto. T. B. Alpacaeval: An automatic evaluator of instruction-followinng models, 2023. URL https: /ttt::///gttut www.//ttootttooee/eeeeeo a aipaca_evaa
Dubois, Y., Galambosi, B., Liang, P., and Hashimoto, T. B. Length-controlled alpacaeval: A simple way to debias automatic evaluators. arXiv preprint arXiv:2404.0447 2024.
Lian, W., Goodson, B., Wang, G., Pentland, E.,, Cook, A., Vong, C., and Teknium. Mistralslimorca: Mistral-7b model instruct-tuned on filtered, corrected, openorcavl gpt-4 dataset, 2023a. URL ht http://hggggg......././// co/Open-Orca /Mi Mistrall -aarrrll-B--e imrrca.
Fleming, P. J. and Wallace, J. J. How not to lie with statis- tics: The correct way to summarize benchmark results. Communications of the ACM, 29(3), 1986.
10

---

Learning to Keep Promise
Lian, W., Wang, G., Goodson, B., Pentland, E., Cook, A., Vong, C., and Teknium. Slimorca: An open dataset of gpt-4 augmented flan reasoning traces, with verifi- cation, 2023b. URL Open-Orca/ (erca//1ue imrrca.
Sabne, A. Xla: Compiling machine learning for peak per- formance, 2020.
Santilli, A., Severino, S., Postolache, E., Maiorca, V., Man- cusi, M., Marin, R., and Rodolå, E. Accelerating trans- former inference for translation via parallel decoding. In Annual Meeting of the Association for Computational Linguistics, 2023.
Liang, Y., Wu, C., Song, T., Wu, W,, Xia, Y., Liu, Y., Ou, Y.,
Lu, S., Ji, L., Mao, S., Wang, Y., Shou, L.,, Gong, M., and Duan, N. Taskmatrix.ai: Completing tasks by connect- ing foundation models with millions of apis. Intelligent Computing, 3, 2024.
Schick, T., Dwivedi- Yu, J., Dessi, R., Raileanu, R., Lomeli, M., Hambro, E., Zeutleoyer, L., Cancedda, N., and Scialom, T. Toolformer: Language models can teach themselves to tools. In Advances in Neural Informa- tion Processing Systems, 2023.
Liang Y., Feng, B., He, H., et al. gpt-fast: High- performance gpt decoding, 2025, URL https:// git github. wow.ppytocch-las//. fast.
Shen, Y. Song, K., Tan, X., Li, D., Lu, W., and Zhuang, Y. Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face. In Advances in Neural Information Processing Systems, 2023.
Liu, M., Zeng, A., Wang, B., Zhang, P., Tang, J., and Dong, Y. Apar: Lims can do auto-parke auto-parallel ruto-regressive de- coding. arXiv preprint orXiv22401006700 2024.
Spector, B. and Re, C. Accelerating LLM inference with staged speculative decoding. arXiv preprint arXiv:2308 2r845:3308.04623, 2023.
Lu, P., Peng, B., Cheng, H., Galley, M., Chang, K.-W., Wu, Y. N., Zhu, S.-C., and Gao, Chameleon: Plug-and- play compositional reasoning with large language models. In Advances in Neural Information Processing Systems, 2023.
Stern, M., Shazeer, N., and Uszkoreit, Blockwise parallel decoding for deep autoregressive models. In Advances in Neural Information Processing Systems, 2018.
Mesnard, T., Hardin, C., Dadashi, R., et al. Gemma: Open models based on gemini research and technology. arXiv preprint KKV::2403.08299 2024.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lam- ple, G. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Misailovic, S., Sidiroglou, S., and Rinard, M. C. Danc- ing with uncertainty. In ACM Workshop Relaxing Synchronization for Multicore and Manycore Scalability, 2012.
Udupa, A., Rajan, K., and Thics, W. Alter: Exploiting breakable dependences for parallelization. In ACM SIG- PLAN Conference on Programming Language Design and Implementation, 2011.
Ning, X., Lin, Z., Zhou, Z., Wang, Z., Yang. H., and Wang, Y. oofitton-of-thugghe Large language models do parallel decoding. In International Conference Learn- ing Representations, 2024.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. React: Synergizing reasoning and act- ing in language models. International Conference on Learning Representations, 2023.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Köpf. A., Yang. E., Vito,o Z., Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv:1912.01703. 2019.
Zheng, L., Yin, L., Xie, Z., Huang, J., Sun, C., Yu, C. H., Cao, S., Kozyrakis, C., Stoica, I., Gonzalez, J. E., et al. Efficiently programming large language models using sglang. arXiv preprint arXiv:3112.07104, 2023.
Pope, R., Douglas, S., Chowdhery, A., Devlin, J., Bradbury, J.. Levskaya, A., Heek, J., Xiao, K., Agrawal, S., and Dean, J. Efficiently scaling transformer inference. arXiv preprint arXiv:2211.05102. 2022.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. In Ad- vances Neural Information Processing Systems, 2023.

---

Learning to Keep Promise
A. Dataset Annotation Prompt
Japanese business joint venture. with sony being one of the developers behind the compact disc digital music media, a compact disc production plant was constructed in Japan under the joint venture, allowing CBS to begin supplying some of the first compact disc releases for the American market in 1983. AnAnNOw answer this question In what year did CDs come to the American market?"
Below is the prompt used to annotate our PASTA-LANG seed dataset. Additional in-context examples are omitted for presentation.
As highly-paid expert annotator, you will be given chatbet response, your job is to decide whether and how this response may be generated asynchronously in parallel by a large Language model. Parallel text generation allows the model to generate segments of text simultaneously rather than sequentially, significantly improving efficiency and response times.
h
"from": "chatbot",
"value": "CDs (Compact Discs)
the American market in 1983. This was made possible through a joint venture between CBS and Sony, named CBS/Sony Records, which was formed in March 1968. As Sony of the developers behind the compact disc digital music media, they built a compact disc production plant in Japan under this joint collaboration. This plant enabled CBS supply some of the first compact disc releases for the American market in 1983. The introduction of CDs revolutionized the music industry as they provided new and improved way to store and listen to music, providing higher sound quality and durability compared to the earlier vinyl records and cassette tapes."
You will first identify whether the given chatbot respense may generated in parallel. You are to then annotate the chatbot response using specific tags that highlight scgments suitable for parallel generation.
one
Use <async> tags to denote segments of text that may be generated asynchronously in parallel with respect to the text that follows. Thus apply <asyne> tags only to sentences that do not serve as necessary context for subsequent sentences. Sentences that are crucial for understanding or generating follewing text are not suitable for parallel asynchronous generaticn, For each <async> tag, include very cencise topic description of the text surrounded within the <async> tags. The topic description will be accessible to text generation after the closing async tag to ensure continuity and coherence.
...
Annotated chatbot response: syjjsnn
"from": "chatbot",
"value": "CDs (Compact Discs) came to the American market in 1983. <asyne topic=' joint maauure'>hhi was made possible through joint venture between CBS and sony, named CBS/Sony Records, which was formed in March 1968. </88yc/ssyc>>> <asyne topic =' japan production plant' >As Sony was one of the developers behind the compact disc digital music media, they built compact disc production plant in Japan under this joint collaboration, This plant enabled CBS to supply some of the first compact disc rel releases for the American market in 1983.</ The the
Use the singleton <sync/> tag for synchronization,
content generated before <syne/>, including text marked by asyne> is accessible to subsequent text generation after the <syne/> tag, ensuring continuity and ccherence.
Detailed Instructions:
Tagging Rules:
Use <async> tag in pairs.
Ensure that each <asyne> tag encerpasses at least five words.
async> <asyne popic="impact" introuction of CDs revolutioni music industry as they provided new and improved way to store and listen to music, providing higher sound quality and durability compared to the earlier vinyl records and cassette
Refrain from altering the content of the response during annotation.
Use maximum of 3 words in the topic description.
Use <sync/> sparingly as it introduces significant slowdown.
Input conversation:
11 jsson
{
"from": "human",
"value": "Article: In March 1968, CBS
and Sony formed CBS/Sony Records,
12

---

Learning to Keep Promise
B. Naive Interpreter Implementation.
In this section, we illustrate the KV-cache layout for naive implementation before and after synchronization in Fig- ure 7b and Figure 7c. We repeat the full model output in Figure 7a. Here we illustrate the inefficiencies associated with implementing asynchronous decoding as batched de- coding, where we pre-allocate the VV-cache pool assuming a fixed number of decoding threads of 4.
In Figure 7b, we show the K V-cache content before synchro- nization at ④.. The naive batched implementation requires duplicating the prefix for each asynchronous thread, which runs independent batch item. Since the KV-cache pool is sized for the maximum possible number of paral- lel threads, many rows often remain unused. This wastes both accelerator memory and computation, as the K V-cccche pool's shape determines the shape of attention computation.
In Figure 7c, we show the KV-cache content after synchro- nization, two decoding steps into (.) The naive interpreter must copy and insert Fork#1 and Fork#2's ' asynchronous generations after their corresponding spromise/> > tags in the main thread's KV-cache row, then mark the rows of terminated threads as uninitialized. This naive batched im- plementation thus suffers from wasted accelerator memory during memory allocation, wasted computation from the oversized attention operations, and additional overhead from KV-cache movement during synchronization.
13

---

Learning to Keep Promise
User: A
If the endpoints of a line segment are (2, and (10, what the length of the segment?
Assistant (Decoding...)
<promise topic="coordinates" tokens=2
/>
<promise copic="lenge" formula" tokens=2
<sync/>
Fork#1
Fork#2
Assistant: <promise topic=" "ooii="coordinates tokens=2
Assistant:
Spromise topic=" ccooddiaats" tokens=2 />
<async>
D
To find the length of the line segment,
<promise
topic="length formula" tokens-2
need to use the formula for the distance between two points
<asynce
The length of line segment can be found using
plane. The points (2, and (10, 4). </async>
formula: Length v((x2 x1)>2 (y2 -1)²2)
</async>
Assistant:
<promise topic= "coordinates" tokens=2 />
<async>
To find the length of the line segment, we need to use the formula
for the distance between points plane. The points (2, and (10, 4). </async> <promise topic= lenchh formula"
tokens=2 />
<async*
The length of line segment can be found using the formula: Length (((2 x1 (y2 y1)22 </async>
<sync/>
Let's plug the coordinates: Length v((10 2)^2 (4 (2)) v( (6)^ v(64 36) v100 10. So, length
of the line segment is 10.
(a) PASTA LANG interpreter orchestrates parallel decoding. A shows the query. B shows the <promise/> tag which initiates the first asynchronous decoding thread named "Fork#1" 1" CC) indicates where the interpreter appends an <async> tag to the prefix of Fork#1. signaling 1ork#1 should complete the promised content with topic "coordinates" (D) denotes the asynchronous generation by 1 F shows the < <sync/> tag where the interpreter pauses to wait for all asynchronous generations, remaining content with both asynchronous generations its prefix.
(F) shows the main thread decodes the
Main p=0
segment
#promiie
Foromice
[pad]
[pad]
[owa)]
[pad]
[pad]
[pad]
Staaynic
Fork 0m/
Seament
+g Spromise.>
Sor Saforiss..
The
wnggth
[pad]
[pod]
[pad]
Untiiialieed
[pad]
[owd]
[pad]
1.94
(b) Naive KV-cache layout before synchronization. The naive approach implements asynchronous decoding through batched decoding, with a pre-allocated fixed-size K KV-cache pool supporting a maximum number of parallel threads, which is set of 4 in this figure. Each decoding thread operates as an independent batch item, with shared prefix duplicated for each thread. The KV-cache pool is stored in row-major layout with shape (max batch size sequence length), shown here before synchronization. The figure show KV-cache pool contents immediately after decoding <syne/> E
Mare
Unint allldoddd pe1t
gudd]
[PA4)
18+4
[PA5]
244)
[194]
[844
[244]
(244)
[24]]
[04)
(44)
(844)
18+4)
[p+4)
(44)
[194]
1948
(000
[440
(444
(44)
[20]]
(a4)
1640
1844
[p04)
[240)
(04)
1848
B440
904)
[04)
[04)
(c) Naive KV-eache layout after synchronization. For asynchronous content to available subsequent decoding steps, naive interpreter must copy and insert each thread's KV-cache (shown in red and green) after their corresponding <promi se/> tokens in the main thread's is KV-eache row. After insertion. the <sync/ token is added and subsequent decoding can attend to the asynchronous content. The interpreter must then mark rows corresponding terminated threads (Fork #1, Fork #2) uninitialized to free memory. The figure shows KV-cache pool contents two steps into
Figure Example Naive Interpreter Implementation.
14

---

Learning to Keep Promise
C. Hyperparamater Selection
monic mean be the most effective since it encourages balanced optimization by inducing larger weight the weaker metric. However, we find that optimizing for har- monic mean performs similarly to optimizing directly for speedup. We hypothesize this is because our LLLM-based quality evaluation naturally favors longer, more detailed responses, preventing the model from artificially increasing speedup through response truncation. As expected, optimiz- ing solely for theoretical parallelism leads to poor speedup, demonstrating the importance of including speedup in the objective. Based on these results, we adopted theoretical speedup only as our efficiency metric.
We selected the learning rate and epochs that we used to train all models based on which combination of hyperparam- eters led the highest quality Baseline-SFT-SFT model as measured by length-controlles win-rate on AlpacaEval. We performed grid search over all combinations of learning rates in [le 4, 1e - 5, le- - 6] and epochs in [1, 4, 8]. We found that training with a learning rate of le-5 5 for 4 epochs resulting in the highest win-rate model.
D. PASTA-LANG Preference Score
45
E. Evaluation
Gemini Pro LC Win Rate (36)
40
The prevailing practice in parallel decoding literature uses arithmetic mean to compute average speedup. However, geometric mean should when averaging normalized values such as speedup against a baseline (Fleming & Wallace, 1986). As such, we report geometric mean in Section but include here in Figures 9a to 9c the results computed using arithmetic mean as reference. Notably, by definition, arithmetic mean is larger than or equal to geometric mean, therefore Figures 9a 9c show notably higher speedup and parallelism than Section 5. Furthermore, PASTA models still Pareto-dominate using arithmetic mean.
35
30
25
Aritmmean
Harnonic
20
Theoreti Speedup
Theoreti Parallel im
15
1.4
1.6
1.
2.0
2.2
Goomean Theoretical Speedup
Figure& 8. Optimization objective. Comparing alternative objec- tives for preference optimization shows our choice yields the best quality-speedup balance.
When performing PASTA-LANG preference optimization, we compute a preference score for each PASTA-LANT anno- tated response as a weighted combination of a quality term and a decoding efficiency term, which is meant reflect the improvement in decoding speed for response. While ultimate goal is to increase decoding speed, it is not ob- vious a priori that directly optimizing for the speedup will produce the desired behavior. Such an objective could lead to degenerate solutions such as producing short responses.
Methodology. To determine the most performant decoding efficiency term, we investigate four separate metrics for (a) the theoretical speedup of the response only (b) the harmonic mean of the theoretical speedup and theoretical parallelism of the response (c) the arithmetic mean of the theoretical speedup and theoretical parallelism of the response (d) the theoretical parallelism of the response only.
the decoding efficiency of a response:
We re-compute the preference score for each training re- sponse using each of the efficiency metrics we present above. We then perform single round of BoNBoN training on each of the different preference labeled datasets.
Results. Figure& 8 presents the response quality and speedup for each model trained to optimize a different decoding efficiency metric. Intuitively, one might expect the har-
15

---

Learning to Keep Promise
50
50
50
x
Pasta BoN Quality Weight (h)
Pasta-BoN Quality Weight (A)
GPT-4 WWn Rate (%)
Pasta-Sof quality Weight
GPT-4 LC Win Rate (%)
40
40
4D
30
Win
20
Bosta-BoN-A
Pasta-BoN-X
10-
APAR
10
APAR
10
APAR
SoT
SoT
SoT
1.0
2.0
1.0
1.5
2.0
2.5
(Arithmetic Mean) Realized Speedup
(Arithmetic Mean) Thearetical Speedup
(Arithmetic Mean) Theoretical Parallelism
(a) Realized speedup. PASTA models achieve Pareto-optimal quality-speedup trade-off.
(b) Theoretical speedup. Realized speedup
(c) Theoretical parallefism. PASTA outputs exhibit high degree of parallelism.
with the PASTA-LANG interpreter is close thcoretical limit.
16


Reviews:
[{"review_id": "pOlYd518Su", "reviewer": "Reviewer_dvEG", "summary": "This paper proposes PASTA, a method for accelerating LLM inference via promises. It's based on PASTA-lang, a markup-based language that expresses which parts of a prompt might be semantically independent. They write a specification for PASTA-lang, use Gemini-Flash to annotate an instruction-tuning dataset with asynchronous tags in PASTA-lang, and finally finetune a model on PASTA data. The finetuned model achieves significant inference-time speedups on tasks that can be decomposed into semantically independent chunks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging feedback and thoughtful comments! Here're our responses.\n\n> How generalizable is this method? Does finetuning on SlimOrca in PastaLang produce generalization capabilities that would help for other unrelated tasks/domains?\n\nWe designed our method and evaluation to accommodate a wide variety of tasks/domains. Specifically, SlimOrca was derived from the FLAN collection of instruction-following dataset, covering 1800+ tasks[2]. Furthermore, our evaluation also covers a wide range of representative real world interaction with LLM including translation/summarization/explanation/creative writing/mathematical problem solving/coding. As [1] notes:\n“[AlpacaEval] operates on a fixed set of 805 instructions chosen to be representative of user interactions on the Alpaca web demo.”\nTherefore, our results demonstrate generalizations across a considerable range of tasks/domains already.\n\n> How does PASTA compare to speculative decoding? Could they be used in parallel, with speculative decoding active within each asynchronous chunk? \n\n> Even though it's synchronous, shouldn't standard speculative decoding be a suitable baseline as well?\n\nWe indeed believe PASTA and speculative decoding are complementary techniques that compose well. As you mentioned, speculative decoding can accelerate each asynchronous chunk in PASTA, creating a multiplicative speedup effect. We will include the results of using speculative decoding in the final paper.\n\n> Why doesn't Figure 3 compare directly to skeleton-of-thought?\n\nWe include here the updated Figure 3 with skeleton-of-thought results (please see [rebuttal doc](https://anonymous.4open.science/r/icml-rebuttal-2025-8A52/ICML_Rebuttal.pdf) Figure 1). As described in Section 5, we do not observe speedup by SoT, when applied to Baseline-SFT. We believe that SoT, as a prompt-based method, requires the base model to have strong instruction-following ability to perform well, and validated this hypothesis by applying SoT to the stronger official instruction-finetuned Gemma-IT model from Google. With this generous implementation, SoT achieves a 1.61x speedup while dropping its win rate by 12%. In contrast, our round 2 Pasta-BoN model with quality weight 2 achieves 1.62x speedup with only a 5% drop to win rate.\n\nReferences:\n\n[1] Dubois, Y., et al. Length-controlled alpacaeval: A simple way to debias automatic evaluators. arXiv preprint arXiv:2404.04475, 2024\n\n[2] Longpre, S., et al. The Flan Collection: Designing Data and Methods for Effective Instruction Tuning. arXiv preprint arXiv:2301.13688, 2023.", "claims_and_evidence": "Yes, the benchmarking results are very compelling, as well as the training and inference time measurements.", "methods_and_evaluation_criteria": "Yes, the method makes a lot of sense, and the evaluation is thorough and includes Pareto curves for various tradeoffs.", "theoretical_claims": "n/a", "experimental_designs_or_analyses": "The experimental design was thorough including various ablations, speed analyses, and description of the finetuning process.", "relation_to_broader_scientific_literature": "This paper is a nice contribution to the LLM inference literature, specifically under the umbrella of asynchronous decoding. It does require special tuning on a specific dataset, so it is not adaptable to the general case, but it's a nice proof-of-concept.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths:\n- Method is simple and works well\n- Configuring attention mechanisms in this setup is tricky and important, and has been done well in this case (\"Training\") in Section 4\n- Although they only use the SlimOrca dataset, the finetuning setup seems general enough that it might be reusable in other domains\n- Experimental analysis is thorough and interesting\n\nWeaknesses:\n- How generalizable is this method? Does finetuning on SlimOrca in PastaLang produce generalization capabilities that would help for other unrelated tasks/domains?\n- How does PASTA compare to speculative decoding? Could they be used in parallel, with speculative decoding active within each asynchronous chunk?", "other_comments_or_suggestions": "n/a", "questions_for_authors": "- Why doesn't Figure 3 compare directly to skeleton-of-thought? \n- Even though it's synchronous, shouldn't standard speculative decoding be a suitable baseline as well?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ig9HgEQLrO", "reviewer": "Reviewer_RqHB", "summary": "The paper addresses LLM inference speed and proposes a method to enable asynchronous, parallel decoding of partial LLM responses. The main idea is to fine-tune the model to output special tags for partial answers that are independent of each other and that can then be decoded in parallel. The critical ingredients of the method are:\n- Obtaining a dataset which contains markup identifying independent parts of answers; this is achieved by distillation from a powerful LLM (Gemini)\n- Training the model to actually produce the independent parts in an independent manner, where the important detail is adjusting position encodings\n- Implementing a decoder that can realize the new parallel decoding ability into lower wall-clock time during inference.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewers careful reading and insightful comments!\n\n> The authors mention SoT, another relevant baseline, in L234 as a comparison point but I did not find any results with it.\n\nWe have included here the updated Figure 3 with the SoT results (please see [rebuttal doc](https://anonymous.4open.science/r/icml-rebuttal-2025-8A52/ICML_Rebuttal.pdf) Figure 1). Notably, we do not observe any speedup by SoT, when applied to Baseline-SFT. We believe that SoT, as a prompt-based method requires the base model to have strong instruction-following ability to perform well, and\nvalidated this hypothesis by applying SoT to the stronger official instruction-finetuned Gemma-IT model from Google. With this generous implementation, SoT achieves a 1.61x\nspeedup while dropping its win rate by 12%. In contrast, our round 2 Pasta-BoN model with quality weight 2 achieves 1.62x speedup with only a 5% drop to win rate.\n\n> comparing models on benchmarks with objective metrics would be appreciated to remove bias.\n\nWe thank the reviewer for this suggestion. We will include an objective evaluation benchmark in the final paper.\n\n> Regard the overall method, I like the idea of a model-driven parallelization strategy, and I can indeed see how for many questions, in particular in combination CoT, answers contain some independent and some dependent parts. What's unfortunate is that the method requires a dedicated training strategy that appears to be pervasive, requiring not only SFT data but also further dedicated fine-tuning stages. It's not clear whether existing fine-tuned models can be easily adapted to follow the format.\n\nOur post-training process mirrors RLHF (SFT + preference optimization). PASTA extends RLHF to improve not just quality but also latency. As RL methods take an increasingly central role in LLM training [1], PASTA is well-positioned for integration with these training algorithms.\n\n> the decision to have it output a multiple of 10 seems arbitrary and to be selected because it turned out to work best.\n\nWe considered the following candidates of position ID adjustment techniques:\n- Const: assume a fixed async chunk length, \n- Pred-1: have the LLM predict async chunk length in multiples of 1,\n- Pred-10: have the LLM predict async chunk length in multiples of 10.\n\nIn addition to our empirical analysis, we have clear rationales for selecting Pred-10. Having the LLM predict async chunk length (rather than using a fixed constant) makes position ID adjustment learnable. We chose multiples of 10 over exact token count prediction (Pred-1) because Pred-1 creates an unrealistic training condition—it predicts length perfectly during training, so the model never encounters position ID collisions. During inference, however, prediction errors inevitably cause such collisions. Pred-10 predicts async chunk length with error due to rounding, intentionally creating imperfect but realistic training conditions that better prepare the model for inference-time position ID collisions.\n\n> It's unclear to me what the impact of this choice would be if, for example, decoding would be performed with top-p sampling instead of greedy.\n\nWe swept the following sampling parameters {T=0.5, T=1} x {TopP=0.2, TopP=0.4, TopP=0.8} for each of our 5 round 2 models. Results show similar quality/speedup trade-off as greedy sampling. Please see [rebuttal doc](https://anonymous.4open.science/r/icml-rebuttal-2025-8A52/ICML_Rebuttal.pdf) Figure 2).\n\n> I am a bit surprised by the noise in Figure 4 and would have expected oracle positions to perform best; here, they perform badly in terms of quality. I would appreciate a general comment regarding noise in the paper's evaluations.\n\nThe SFT stage shows slightly higher noise (std over 3 runs is 0.6% win rate) while the BoN stage exhibits much less noise. In Figure 3, we report performance across 10 BoN models, providing clear evidence of stability and consistency.\n\nWe hypothesize this difference is because we do not optimize for a specific quality/speedup trade-off during SFT, which means the resulting model may land at different points on the same Pareto frontier. Whereas for the BoN stage, we do explicitly optimize for a specific quality/speedup trade-off, making the optimization problem more constrained and the solution more stable.\n\n> Do you find that the estimated token counts in the promises are accurate?\n\nInspecting the outputs from 5 round 2 models, we find the average relative error to be 14.5%, computed as average(abs(prediction - ground_truth)/ground_truth).\n\n> I did not like that the analysis promises future improvements from further rounds of BonBon (5.3, \"Continuous Improvements\") but stops at 2 rounds, while this style of training has trouble achieving benefits after more than 2 iterations.\n \nWe will include results with 3 rounds of training and update our analysis accordingly in the final paper.\n\n[1] DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.", "claims_and_evidence": "The paper claims superior results in both quality and speed compared to existing asynchronous decoding methods; the one considered for comparison is APAR. The authors mention SoT, another relevant baseline, in L234 as a comparison point but I did not find any results with it. After the SFT stage with annotated examples, the model performs worse than APAR in both speedup and quality; after rejection sampling training, the authors achieve higher output quality and higher speed-up compared to APAR, validating the pareto-dominant claim of the abstract.\n\nIt should be noted that here, \"quality\" is measured by win-rates according to LLM-as-a-judge. The authors took some precaution and selected the hyper-parameters of their algorithm with Gemini (Fig. 4, Fig. 5) while performing final evaluations with GPT-4, but comparing models on benchmarks with objective metrics would be appreciated to remove bias.", "methods_and_evaluation_criteria": "Yes, quality and speed are indeed the main criteria to evaluate methods that improve decoding speed.\n\nRegard the overall method, I like the idea of a model-driven parallelization strategy, and I can indeed see how for many questions, in particular in combination CoT, answers contain some independent and some dependent parts. What's unfortunate is that the method requires a dedicated training strategy that appears to be pervasive, requiring not only SFT data but also further dedicated fine-tuning stages. It's not clear whether existing fine-tuned models can be easily adapted to follow the format.\n\nThe method also relies on specifics regarding the handling of position encodings during parallel decoding. While, in the end, the model does predict the expected length of the response itself, the decision to have it output a multiple of 10 seems arbitrary and to be selected because it turned out to work best. It's unclear to me what the impact of this choice would be if, for example, decoding would be performed with top-p sampling instead of greedy. I am a bit surprised by the noise in Figure 4 and would have expected oracle positions to perform best; here, they perform badly in terms of quality. I would appreciate a general comment regarding noise in the paper's evaluations.", "theoretical_claims": "No theoretical claims.", "experimental_designs_or_analyses": "Experimental setup looks good to me; the criteria for the preference tuning stage with BonBon are sensible (finding a trade-off between speed and quality).\n\nI did not like that the analysis promises future improvements from further rounds of BonBon (5.3, \"Continuous Improvements\") but stops at 2 rounds, while this style of training has trouble achieving benefits after more than 2 iterations (e.g., https://arxiv.org/abs/2308.08998).", "relation_to_broader_scientific_literature": "APAR, the main point of comparison, uses a similar technique to achieve decoding speed-ups but relies on hand-crafted heuristics to identify independent sub-sequences in the LLM output. Instead, this paper asks Gemini to produce an annotated dataset to bootstrap the model's ability to announce parallel sections The method presented here offers more flexibility in structuring the output, and via sampling and preference optimization, the model can be further tuned towards higher speed and quality.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "While the writing is mostly clear, I found it a bit confusing that the related work is spread throughout the paper. There is an initial discussion in the introduction, then section 2, and finally there is a dedicated related work section which discusses work that, in my opinion, are not very related to this paper. I would prefer a joint discussion in a single section; for example, I don't think the postulated dichotomy is very relevant to the method overall apart from describing related work.\n\nFor the \"tokens\" parameter of the <promise> tag, it took a while to find out what it actually means. It first appears in Fig 1, the main figure presenting the method, without explanation, then in section 3 where is referred to an integer attribute (which makes it appear from Fig. 1 as the model would get them wildly wrong), then finally on page 7 in the discussion of the ablations we learn that it represents 10x the expected token count. Maybe I missed an earlier explanation, but it would be good to clarify this early, e.g., in the figure caption or in the \"Annotations.\" paragraph of the intro.\n\nI would suggest the authors refrain from labeling their method as \"pareto-optimal\" without adding the qualifier \"among the methods that were compared\" (e.g., L128 right).", "other_comments_or_suggestions": "- Fig. 1 caption, \"It wait\"\n- L135 right, \"Pasta-Lang is XML-like\"\n- L254 left, \"BonBon training\" (iterations?)", "questions_for_authors": "- Do you find that the estimated token counts in the promises are accurate?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nva6aEAss4", "reviewer": "Reviewer_gQzb", "summary": "This work presents a novel framework that allows the model to learn semantic boundaries in the sequence space, so that semantically independent chunks could be decoded in parallel, or async manner. First, they proposed an XML-based markup to be able to structure a flat sequence into structured chunks that can be used by the decoding controller. Specifically, decoding could switch from usual decoding into async mode, and then synchronize chunks back and use previous chunks as context to decode the final part of the sequence.\nAuthors design training pipeline so that the model can learn when to generate control tokens to switch into async mode and back. Training pipeline involves both supervised and preference finetuning. Their experimental results show that they method is able to maintain or improve the quality of model responses while making decoding faster due to ability to process async chunks in parallel.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the helpful comments!\n\n> the benefits of splitting decoding chunks into parallel executions that can synchronize later is an interesting idea, however, the practical utility of such method is questionable especially on the efficiency side. Efficient and optimal async inference of such blocks (while keeping consistent kv cache of the sequential prefix) might be overly complicated usecase unless all major foundational language models would use that.\n\nOur results directly address efficiency. Our implementation achieves practically significant speedups up to 1.9x and on average reaches 78.6% of the theoretical speedup (an optimistic estimate of maximum possible speedup). These results clearly demonstrate real efficiency gains.\nFurther, our interpreter design is model-agnostic. Any foundation model can reuse our implementation as long as it adopts the same control tokens to orchestrate asynchronous decoding.\n\n> experimental testbed uses public benchmarks for performance, which is good, but \"theoretical speedup\" on decoding side is a bit less convincing.\n\nWe emphasize that: 1) The left plot in Fig. 3 presents measured wallclock speedup. 2) Theoretical speedup is helpful because end-to-end evaluation entangles the quality of our training algorithm's with the quality of our interpreter implementation. Theoretical speedup lets us examine how effectively our training algorithm promotes speedup, independent of our interpreter implementation.\n\n> presented speed-ups (geomean theoretical speedup) usually comes with quality degradation, which is a bit concerning given that in theory such async chunks might help to improve reasoning abilities by reducing hallucinations. hypotheses suggested by authors do not hold very strong in the experimental part, unless I misunderstood something.\n\nCould the reviewer please clarify why async chunks might help reduce hallucinations and specify what \"hypotheses suggested\" refers to? \n\nWe acknowledge the quality-speedup tradeoff and have been transparent about it throughout our paper, including in the abstract. Our contribution is achieving the best quality-speedup tradeoffs among existing asynchronous decoding methods.\n\n> it would help to emphasize that LC winrates in alpaca eval shall be interpreted as \"higher-better\" , same for all other metrics in the experiments.\n\nWe will add this clarification in the paper.\n\n> Do you think such approach could bring improvements in model's ability in long chain of thought reasoning? If yes, what would be an essential experiment to do in context of this work to showcase that?\n\nWe believe mathematical reasoning benchmarks are promising application scenarios for PASTA. However, we also emphasize that DeepSeek R1 (first open source long CoT model) was released only ~8 days prior to ICML deadline. We will include the results of using Pasta with long chain of thought reasoning models in the final paper.", "claims_and_evidence": "* the overall idea of allowing the model to split the chain of thought into a set of semantically independent chunks is sound and has clear motivation given recent advances in reasoning with long chain of thoughts.\n* the benefits of splitting decoding chunks into parallel executions that can synchronize later is an interesting idea, however, the practical utility of such method is questionable especially on the efficiency side. Efficient and optimal async inference of such blocks (while keeping consistent kv cache of the sequential prefix) might be overly complicated usecase unless all major foundational language models would use that.", "methods_and_evaluation_criteria": "* experimental testbed uses public benchmarks for performance, which is good, but \"theoretical speedup\" on decoding side is a bit less convincing.", "theoretical_claims": "* presented speed-ups (geomean theoretical speedup) usually comes with quality degradation, which is a bit concerning given that in theory such async chunks might help to improve reasoning abilities by reducing hallucinations. In that sense the hypotheses suggested by authors do not hold very strong in the experimental part, unless I misunderstood something.", "experimental_designs_or_analyses": "Experimental design is described clearly. The presented method shows robust improvements in quality and speed compared to other async decoding methods.", "relation_to_broader_scientific_literature": "I'm not very familiar with async decoding literature, but related work section looks like it well represents related work, and goes even further into decoding efficiency discussion about methods such as speculative decoding.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Overall the biggest concern i have is the potential impact of such approach in the community, I don't see such approach being used widely, but I could be biased. However, I think the proposed method makes sense, and I don't see any flaws in the experimental design!", "other_comments_or_suggestions": "* it would help to emphasize that LC winrates in alpaca eval shall be interpreted as \"higher-better\" , same for all other metrics in the experiments.", "questions_for_authors": "Do you think such approach could bring improvements in model's ability in long chain of thought reasoning? If yes, what would be an essential experiment to do in context of this work to showcase that?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CMIcSKKsAw", "reviewer": "Reviewer_9kSW", "summary": "The authors propose a mechanism, Pasta to train large language models (LLMs) to identify and express semantic independence and directly optimizes for both response quality and decoding latency. This framework has two key components, the Pasta-Lang, an annotation language that allows LLMs to express semantic independence, and it also has an interpreter orchestrate parallel decoding on the fly. This two-stage framework achieved state-of-the-art on a benchmark, AlpacaEval, speeding up and improving the quality of generation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the encouraging feedback from the reviewer!\n\n> However, with only specifying that the work is evaluated on one dataset, the contributions may be limited.\n\nWe would like to clarify that AlpacaEval actually is a suite of 5 different benchmarking datasets: Self-Instruct [1], Open-Assistant [2], Vicuna [3], Koala [4], and hh-rlhf [5]. \n\n\nReferences:\n[1] Wang, Yizhong, et al. Self-Instruct: Aligning Language Models with Self-Generated Instructions. ACL. 2023. https://arxiv.org/abs/2212.10560\n\n[2] Köpf, Andreas. OpenAssistant Conversations -- Democratizing Large Language Model Alignment. NeurIPS. 2023. https://arxiv.org/abs/2304.07327\n\n[3] Chiang, Wei-Lin, et al. Vicuna: An Open-Source Chatbot Impressing GPT-4 with 90%* ChatGPT Quality. 2023. https://lmsys.org/blog/2023-03-30-vicuna/\n\n[4] Geng, Xinyang, et al. Koala: A Dialogue Model for Academic Research. 2023. https://bair.berkeley.edu/blog/2023/04/03/koala/\n\n[5] Bai, Yuntao, et al. Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback. 2022. https://arxiv.org/abs/2204.05862", "claims_and_evidence": "The experiments generally support the claims of the work. However, with only specifying that the work is evaluated on one dataset, the contributions may be limited.", "methods_and_evaluation_criteria": "The work only used a benchmark dataset, which may present generalization risks for the proposed method.", "theoretical_claims": "The theoretical claims make sense. There’s not much theoretical proofs provided, but more empirical settings.", "experimental_designs_or_analyses": "The experiments are adequate. Evaluations on the speed and quality are both provided with enough details.", "relation_to_broader_scientific_literature": "There’s a generally thorough literature review provided in the paper, and the authors discussed how their research is built on prior work.", "essential_references_not_discussed": "I am not aware of any other essential references not discussed.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes PASTA, a method for accelerating LLM inference via parallel autoregressive generation, when it is possible to do so. The proposed method appears to be simple and works well. All reviewers praised the significance of the method. It is however, a bit complex as it requires specialized fine-tuning and engineering, which can limit it being widely adopted. Nonetheless, I recommend acceptance
Decision: Accept (poster)