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

We appreciate the encouraging feedback from the reviewer!

However, with only specifying that the work is evaluated on one dataset, the contributions may be limited.

We 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].

References: [1] Wang, Yizhong, et al. Self-Instruct: Aligning Language Models with Self-Generated Instructions. ACL. 2023. https://arxiv.org/abs/2212.10560

[2] Köpf, Andreas. OpenAssistant Conversations -- Democratizing Large Language Model Alignment. NeurIPS. 2023. https://arxiv.org/abs/2304.07327

[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/

[4] Geng, Xinyang, et al. Koala: A Dialogue Model for Academic Research. 2023. https://bair.berkeley.edu/blog/2023/04/03/koala/

[5] Bai, Yuntao, et al. Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback. 2022. https://arxiv.org/abs/2204.05862

We appreciate the reviewer for the helpful comments!

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.

Our 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. Further, 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.

experimental testbed uses public benchmarks for performance, which is good, but "theoretical speedup" on decoding side is a bit less convincing.

We 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.

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.

Could the reviewer please clarify why async chunks might help reduce hallucinations and specify what "hypotheses suggested" refers to?

We 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.

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.

We will add this clarification in the paper.

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?

We 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.

We appreciate the reviewers careful reading and insightful comments!

The authors mention SoT, another relevant baseline, in L234 as a comparison point but I did not find any results with it.

We have included here the updated Figure 3 with the SoT results (please see rebuttal doc 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 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.

comparing models on benchmarks with objective metrics would be appreciated to remove bias.

We thank the reviewer for this suggestion. We will include an objective evaluation benchmark in the final paper.

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.

Our 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.

the decision to have it output a multiple of 10 seems arbitrary and to be selected because it turned out to work best.

We considered the following candidates of position ID adjustment techniques:

• Const: assume a fixed async chunk length,
• Pred-1: have the LLM predict async chunk length in multiples of 1,
• Pred-10: have the LLM predict async chunk length in multiples of 10.

In 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.

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.

We 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 Figure 2).

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.

The 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.

We 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.

Do you find that the estimated token counts in the promises are accurate?

Inspecting 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).

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.

We will include results with 3 rounds of training and update our analysis accordingly in the final paper.

[1] DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.

We thank the reviewer for the encouraging feedback and thoughtful comments! Here're our responses.

How generalizable is this method? Does finetuning on SlimOrca in PastaLang produce generalization capabilities that would help for other unrelated tasks/domains?

We 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: “[AlpacaEval] operates on a fixed set of 805 instructions chosen to be representative of user interactions on the Alpaca web demo.” Therefore, our results demonstrate generalizations across a considerable range of tasks/domains already.

How does PASTA compare to speculative decoding? Could they be used in parallel, with speculative decoding active within each asynchronous chunk?

Even though it's synchronous, shouldn't standard speculative decoding be a suitable baseline as well?

We 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.

Why doesn't Figure 3 compare directly to skeleton-of-thought?

We include here the updated Figure 3 with skeleton-of-thought results (please see rebuttal doc 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.

References:

[1] Dubois, Y., et al. Length-controlled alpacaeval: A simple way to debias automatic evaluators. arXiv preprint arXiv:2404.04475, 2024

[2] Longpre, S., et al. The Flan Collection: Designing Data and Methods for Effective Instruction Tuning. arXiv preprint arXiv:2301.13688, 2023.