Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation
Authors: Xuefei Ning
Zinan Lin
Zixuan Zhou
Zifu Wang
Huazhong Yang
Yu Wang
Venue: ICLR 2024 poster (2024)
Keywords: large language model
efficient inference
data-centric optimization
parallel generation
prompt engineering
planning
Primary area: generative models
TL;DR: As a data-centric efficiency technique, SoT decreases the generation latency by guiding the LLM itself to organize the output data and generate multiple segments in parallel.

Abstract: This work aims at decreasing the end-to-end generation latency of large language models (LLMs). One of the major causes of the high generation latency is the sequential decoding approach adopted by almost all state-of-the-art LLMs. In this work, motivated by the thinking and writing process of humans, we propose Skeleton-of-Thought (SoT), which first guides LLMs to generate the skeleton of the answer, and then conducts parallel API calls or batched decoding to complete the contents of each skeleton point in parallel. Not only does SoT provide considerable speed-ups across 12 LLMs, but it can also potentially improve the answer quality on several question categories. SoT is an initial attempt at data-centric optimization for inference efficiency, and showcases the potential of eliciting high-quality answers by explicitly planning the answer structure in language.

Published as a conference paper at ICLR 2024
SKELETON-OF-THOUGHH PROMPTING LLMs FOR EFFICIENT PARALLEL GENERATION
Xuefei Ning! foxdoraame@gmai com
Zinan Lin
linzi nan'1 www.annnnnnnnee 9958gma .com com
Zixuan Zhou 14+
Zifu Wang
chouzx21émailss www.gluussinnuuu...a edu.cn
zifu zifu. wanckkueggelleeeeenn.ooooo
Huazhong Yang!
Yu Wang
yanghzēts/ Brnggh/@tsnnhuua...m nghua. edu. cn
yu-wangets inguua sechh.aaedd....e cn
Department of Electronic Engineering, Tsinghua University, Beijing, China
2 Microsoft Research, Redmond, Washington, USA 3 ESAT-PSI, KU Leuven, Leuven, Belgium Infinigence-Al
Website: http::/sssssttse.llleeeee google wtt.e///ecc//eee///ootllll Code: https://github. com/ /mwgiiatiion--eeeercheeee
ABSTRACT
This work aims at decreasing the end-to-end generation latency of large language models (LLMs). One of the major causes of the high generation latency is the sequential decoding approach adopted by almost all state-of-the-art L.LMs. this work, motivated by the thinking and writing process of humans, propose ofehethn-of-Thoughht (SoT), which first guides LLMs to generate the skeleton the answer, and then conducts parallel API calls or batched decoding to complete the contents each skeleton point in parallel. Not only does SoT provide consid- 12 LLMs, but can also potentially improve the answer quality on several question categories. SoT is an initial attempt at data-centric op- timization for inference efficiency, and showcases the potential of eliciting high- quality answers by explicitly planning the answer structure in language.
erable speed-ups
INTRODUCTION
Large language models (LLMs) (Brown al., 2020; Touvron et al., 2023a; et al., 2022; OpenAl, 2023; Zheng et al., 2023) have shown exceptional performance natural language processing and chatbot systems. However, the inference process of the state-of-the-art LLMs is slow, hindering their interactive use. For example, it takes 22 seconds for Claude (Anthropic, 2023) (accessed through Slack API) and 43 seconds for Vicuna-33B V1.3 (a 33B LLaMA-based model, rumning locally one NVIDIA A 100 GPU) to answer the question in Fig. 1.
We conclude three major causes of LLMs' slow inference: (1) A large model size requires large amount of memory, memory access, and computation. For example, the FP16 weights of 175B GPT- 3 take 350GB memory, which means at least 5x80GB A100 GPUs are needed keep the model in GPU memory. Even with enough GPUs, the heavy memory access and computation slow down the inference. (2) The attention operation the prevailing transformer architecture is I/O bounded and has a quadratic memory and computation complexity in sequence length. (3) The sequential decoding approach in inference generates tokens one by one. This approach introduces significant inference latency since the generation of tokens cannot be parallelized. There is bunch of literature addressing the first two axes: large model size (Xiao al., 2022; Frantar et al., 2022; Lin al., 2023; Sheng et al., 2023; Wang et al., 2021) and attention operation (Kitaev et al., 2020; Wang al., 2020;
"Equal contribution.

---

Published as a conference paper at ICLR 2024
Normal Decoding
Question
Skeleton-of-Thowe
0.4
subiekicura112
Decoding
What are the most effective etrategles conflict
Net win rates
Vicura-1 38 V1.3
resolution the workplace?
(1) Skeleton
stage
0.2
Chargrmas
UttraM
Vicuna-88 V1.3
Answer
istering
Vicun 338 V1.3
1. Active listening involves fully
Idenlly sques
concentrating
Compromse
0.0
LLaMA2-Cha1-78
Identify issues,
root
[2) Point-
LLMAZ Chat-1B
caussss
espanding
stage
Cludde
Openthat-Pam
Compromise. Look for a middio ground
-0.2
Vicuna 78 VI.1
1.0
1.2
1.4
1.6
1.8
Generates answers sequentially Slower
Generates answers
Speed-up
parolie' Faster
(SoT). Instead of producing answers se- quentially, SoT produces different parts of answers in parallel. In more detail, given the question, SoT first prompts the LLM to give out the skeleton, then conducts batched decoding or parallel API calls expand multiple points in parallel, and finally aggregates the outputs get the final answer. Right: The net win rates and speed-ups of SoT with router (SoT-R) compared to normal generation on Vicuna-80. The net win rate is the difference between the fraction of questions that SoT-R has better and worse answers than normal generation. The speed-up is the ratio between the latency of normal and SoT-R generation. (1.0, 0.0) represents normal generation. Higher is better on both axes. For most models, SoT-R not only accelerates the generation but also improves the quality of the answers (evaluated with FastChat metric (Zheng et al., 2023)). See $ 3.2 and for more details.
Figure 1: Left: An illustration of Skeleton-of-Thouge
Dao et al., 2022; Zaheer al., 2020; Chen et al., 2023b). These works either compress/redesign the model (Xiao et al., 2022; Frantar et al., 2022; Lin et al., 2023; Kitaev et al., 2020; Wang et al., 2020; Dao et al., 2022; Zaheer et al., 2020) or redesign the serving system (Sheng et al., 2023; Chen al., 2023b) and hardware (Wang et al., 2021).
In contrast to prior work, we tackle the third axis and question the common assumption that LLMs have to do fully sequential decoding. We show the feasibility of parallel decoding of off-the-shelf LLMs without any changes to their model, system, or hardware. For instance, for the question in Fig. I, we can reduce the latency from 22 seconds to 12 seconds (1.83x speed-up) with Claude, and from 43 seconds to 16 seconds (2.69x speed-up) with Vicuna-33B V1.3 on an NVIDIA A100.
The idea stems from reflecting how humans ourselves think about questions and write answers in a sequential fashion. contrast, for many question types, we first derive the skeleton according some protocols and strategies, and then add evidence and details to explain each point. This is especially the case on occasions like offering consultancy, taking tests, writing papers, and on. This intuition has back question the necessity of fully sequential decoding. In this paper, we propose Skeleton-of ofo-Thhtht (SoT). Specifically, shown in Fig. we guide the LLM derive a skeleton first by itself. Based on the skeleton, the LLMs can complete each point in parallel so that we get speed-up. SoT can be utilized to accelerate both open-source models with batched decoding and API-based models with parallel API calls.
questions. Humans do not always
The current SoT is suitable for questions that require a long answer whose structure can be planned ahead, while not suitable for questions that require step-by-step reasoning or only need a short answer. Therefore, to make the overall solution more practical, we design extension, SoT with router (SoT-R), which employs a router to only trigger SoT for suitable questions.
We test SoT 12 recently released LLMs. Not only does SoT provide considerable speed-ups (up to 2.39 x), but it can also improve the answer quality in many cases (Fig. 1).
Note that in contrast to existing model- and system-level efforts for inference efficiency, SoT takes a novel "data-level" pathway by letting the LLM organize its output content. This novel perspective is becoming feasible and is expected to grow in importance, owing to the evolving capabilities of state-of-tte-art LLMs. We hope this work can stimulate more research in the realm of data-centric optimization (Zha al., 2023; HazyReeearch, 2023) for efficiency.
2

---

Published as a conference paper at ICLR 2024
Prompt 1. Skeleton Prompt Template 7
[User:] You'de re an organizer responsible for only giving the skeleton (not the full content) for answering the question. points (numbered 3.. etc.)
Provide skcleton each skeleton point should be very short with only 3-55 words. Generally, the skeleton should have 3 10 points. New, please provide the skeleton for the following question. [question)
question. Instead writing sentence.
Skeleton:
[Assistant:]
Prompt 2. Point- Expanding Prompt Template T
[Ueer:] You're responsible for continuing the wriling of and only point the overall the following question.
(question)
The skeleton of the answer
[skeleton)
Continue only continue writing point (point index). Write *"very sbortly** I-~2 sentence and do not continue with other points!
[Assistant:] {point index). (point skeleton)
The rest of the paper organized as follows. We first introduce SoT in $ and show its results in $ 3. Then, we expand the SoT-R extension in 4. $ positions SoT in the research ecosystem (expanded in App. D). Finally, we analyze the limitations and share outlooks SoT in $
SKELETON-OF-THOUCGE (SOT)
2.1 METHOD
Overview. Based on the intuition that humans usually think about and answer question in an organized way, the core idea of this work is to guide the LLM itself to give a skeleton first and then write the overall answer parallelly instead of sequentially. Fig. I illustrates how SoT produces the final answer to a user question
(1) Skeleton stage. SoT first assembles skeleton request, TO (guuestion 2), using the skeleton prompt template T (Prompt I, and Prompt in App. B.1) with the question as the parameter. The skeleton prompt template written to guide the LLM output a concise skeleton of the answer. Then, we extract the B points from the skeleton response !t of the LLM.
(2) Point-expanding stage. Based on the skeleton, let the LLM expand on each point in parallel. Specifically, for the point with index and skeleton Ri. SoT uses T (question g. skeleton = R" point index b, point skeleton Ri)) as the point-expanding request for the LLM, where The is the point-expanding prompt template (Prompt 2). Finally, after completing all points, we concatenate the point-expanding responses [R]") )b=1,..., B to get the final answer.
Parallel point expanding. We conduct parallel point-expanding so that SoT is able to achieve speed-up than normal decoding.
(1) For proprietary models with only API access, we can issue multiple parallel API calls to get an end-to-end latency gain at the cost of an increased number of API requests and tokens.
(2) For open-source models that we can run locally, we let them process the point-expanding re- quests as batch (paddings are added to the left the point-expanding requests). We explain below why this could achieve speed-ups. A typical LLM generative process consists of two phases: (a) the prefilling phase in which the prompt is parsed to generate the key-value cache for further use, and (b) the decoding phase in which tokens are generated one by one in sequential manner. The decoding phase accounts for the majority of the end-to-end latency, especially when generating a long response. Note that the decoding phase is bottlenecked by weight loading instead of activation

---

Published as a conference paper at ICLR 2024
loading computation." Consequently, running LLM inference with increased batch sizes does not increase the per-token latency much. Therefore, SoT allows us to decode roughly Bx more to- kens within the same amount of time if we parallelly decode B points. See App. E for the expanded discussions and the supporting experiments. Please refer to App. B for more implementation details.
SOT EVALUATION
Datasets. We evaluate SoT on two recent assistant-style datasets: (1) Vicuna-80 (Chiang et al., 2023), which contains 80 questions spanning nine categories, such as coding, math, writing, role- play, and so on, and (2) WizardLM (Xu et al., 2023), which contains 218 questions spanning more categories and diverse difficulties. Due to space constraints, we only report Vicuna-80 results in the main paper, and defer WizardLM results to the Apps. G and I.
Models. We test SoT on 12 models, including 9 open-source models and 3 API-based models. We obtain the weights of all the open-source models from Hugging Face. See App. A for more details.
3.1 EVALUATION OF EFFICIENCY
We record the latency of every API call with start time. time (); ...; elapsed time time time () start, and add the latency of the skeleton API call and the slowest point-expanding API call as the SoT latency.
API-based models.
Open-source models. All open-source models we currently evaluate based on the LLaMA 7B, 13B, or 33B architectures. Thus, to enable fast analysis, we first make a latency profiling table for each LLaMA architecture on NVIDIA A100. The table contains the architecture's 's (1) latency for prefilling sequences of length I to 700 with different batch sizes (from I to 16), and (2) decoding one token with context of length 1 to 1024 with different batch sizes (from to 16). With these three latency profiling tables, given the number of points B, the token lengths of the requests and responses the skeleton and point-expanding stages, we can quickly estimate the SoT latency by simply looking up entries in the tables and adding them up. See App. F for more detailed description of how we conduct the profiling and estimate the latency.
In addition to the above approach, we also compare the actual latency of SoT and normal sequential generation (abbreviated as "normal" in the following discussion) in App. G.1.4.
The rest of this section shows the speed-ups of SoT on different models ($ 3.1.1) and question categories (8 3.1.2). In addition, we also report the latency breakdown of SoT stages in App. G.1.2 and the SoT speed-ups on an RTX 3090 GPU in App. G.1.3.
3.1.1 SPEED-UP UP BREAKDOWN: MODELS
We investigate how SoT reduces the end-to-end latency on different models. Fig. 2a shows the average upeed-up for each model across all question categories. We can see that SoT obtains >2x speed-up (up to 2.39 x) on 8 out of 12 models.
We report the detailed statistics about token lengths and numbers of points Fig. 11. (1) In terms of the point number B (Fig. 1a)), LLaMA2, Vicuna-7B V1.1, Vicuna-7B V1.3, and ChatGPT-3.5 yield relatively fewer points (<6), while GPT-4 and Stable 13B generates the largest number of points on average (R9).. (2) Regarding the point-expanding response length, Figs. 1lb to 1 show that the API-based models, ChatGPT-3.5, Claude, and GPT-4, follow the point-expanding request better and generate shorter point-expanding responses than the open-source models. One can also notice that Stable Vicuuna-3BB longest expaniix responses for many question cat- egories can be lengthy as the overall normal answer, since it fails adhere to the "Write it **very shortly#** instruction the point-expanding request. Consequently, So'T cannot accelerate Stable Vicuna- 13B well. (3) Regarding the length balance degree between point responses, Fig. le shows that LLaMA2 and the API-based models generate more balanced point-cxpanding responses. (4) As for the overall length of the final aggregated answer (Fig. 11f), employing SoT on most models results in answers that are, on average, 1~2x x longer than the normal answer.
This when the number of concurrent queries small; see & for discussion on other scenarios.
4

---

Published as a conference paper at ICLR 2024
LLAMA2 Cha, 75
T0x
knooledge
2.33x
2.31K
Vituna 78 V1.1
1.20%
common-sense
2.24
Utouu 13
KULK
relepby
coding
1.95x
7.06x
chators3
counter faciud
1.89K
fomm
1.69X
Stabreieuun-
30
11
math
1:30k
1.
12
14
18
20
22
24
26
28
1.
1.4
1.6
2.0
22
244
26
28
(a) Different models.
(b) Different categories.
Figure 2: Average speed-ups of SoT on different models and question categories.
3.1.2 SPEED-UP BREAKDOWN: QUESTION CATEGORIES
Here we investigate how SoT reduces the end-to-end latency for different question categories. Fig. 2b shows the average speed-up for each question category across all models. The question categories for which SoT can provide high-quality answers are marked in green, and other cate- gories are marked in red (see 3.2.3 for the answer quality evaluation). We can see that SoT can obtain speed-ups for all question categories. For the five question categories that SoT can provide high-quality answers (i.c., knowledge, generic, common-senue roleplay. counterfactual), SoT can speed up the overall answer generation process by 1.89x to x in the meantime.
3.2 EVALUATION OF ANSWER QUALITY
In order to compare the answer quality of the normal sequential generation (abbreviated "normal" in the following discussion) and SoT generation, we adopt two LLM-bbase evaluation frameworks: FastChat (Zheng et al., 2023) and LLMZoo (Chen et al., 2023c). The evaluation process is to present a question and a pair of answers (from normal or SoT generation) to an LLM judge (GPT-4 in the main paper, see App. I.4 for the results evaluated using ChatGPT-3.5) and ask for preference.
Here are more details about the evaluation of the answer quality:
(1) Detailed metrics. FastChat provides one metric for the general answer quality. In addition to general metric, LLMZoo provides five detailed metrics on the answers' coherence, diversity, immersion, integrity, and relevance.
(2) Question categories. FastChat provides two special evaluation prompts for coding and math questions for more accurate evaluation, whereas LLMZoo does not. Following the implementation in LLMZoo, we exclude math and coding questions in all LLMZoo evaluation results.
(3) Extentions to avoid evaluation bias. To avoid the potential bias from the order of the two answers presented to the LLM judge, we extend FastChat and LLMZoo evaluation frameworks by running the evaluation twice with either ordering of the two answers. In either evaluation, a score 0, and -1 is assigned when SoT wins, ties, loses. respectively. The final evaluation is that SoT wins/ties/loses when the sum the two scores is positive/zero/negattvee For example, if SoT wins in evaluation and loses in the other evaluation, the result is "tie". If SoT wins (loses) in one evaluation and ties in the other, the result is "win" ("lose").
I,
(4) Net win rates. We further define net win rates give summarized view of the answer quality. Given the number of questions that SoT wins (#win) and loses (tlose), we define net win rates as awin-Alese/ #lose focal number questions. 0% means that SoT performs competitively the normal baseline (wins and loses in the same number of questions). Higher values mean that SoT performs better.
In the following sections, we first present the overall quality of SoT answers ($ 3.2.1), )), and then go into the details across different question categories ($ 3.2.3), models ($ 3.2.2), and metrics ($ 3.2.4).
3.2. OVERALL QUALITY
In Fig. 3, we show the win/tie/lose rates (the percentage of the cases when SoT wins/ties/loses compared to normal generation) across all models and questions using the two metrics from FastChat and LLMZoo that capture the general quality of the answers. We notice discrepancy between the two metrics on when SoT is strictly better than the baseline (45.8% v.s. 29.5%). Despite that, the two metries agree that SoT is not worse than the baseline in around 60% of the cases, and the win
5

---

Published as a conference paper at ICLR 2024
rates close to the lose rates. This result suggests that the answers of SoT maintain good quality of that of the normal generation.
Wir1
Lowm
General quality (FastChat)
29.5%
29.3%
41.2%
General quality (LLMZoo)
14.5%
0%
20%
40%
60%
80%
100%
Figure 3: Win/tie/lose rates of SoT v.s. normal generation using "general" metrics from FastChat and LLMZoo. SoT performs better than or equal normal generation in around 60% cases.
3.2.2 QUALITY BREAKDOWN: MODELS
We compute net win rates on all models in Fig. 4. Again, we see that the two general metrics from FastChat and LLMZoo have different absolute values but similar rankings. particular, both metrics agree that OpenChat- 13B, Vicuna-7B V1.1, Claude, -LaMA2-Chat- rates, whereas Vicuna- 13B V1.3, SiuunaVi and UltraLM- 13B have high net win rates.
have low net win
Vicuna 78 1
Vicuna 78 VL
LaM Chat 138
LLaMAz Chat
Chaicer
Wrina
Dital VL
136
Utral aLM VL
StableVicune
StaoleVicune-
60%
-40%
-20%
0%
20%
-40%
-20%
0%
20%
40%
60%
(a) Metrie: general quality (FastChat).
Metric: general quality (LLMZoo).
Figure 4: Net win rates of SoT on different models.
We investigate the answers in App. I.1.1, and summarize the key takeaways follows. Some models have low SoT net win rates as they cannot understand the skeleton and point-expanding prompts well. Some other models have low SoT net win rates their normal answers already have good quality, making it hard for SoT to beat them (c.g., Claude). For models that are able to understand the SoT prompts and the normal answers answer quality. We expect that further improving SoT prompts or fine-tuning the models can make easier for LLMs to understand the skeleton and point-expanding prompts and ultimately result in better answer quality.
good enough, SoT can improve the
3.2.3 QUALITY BREAKDOWN: QUESTION CATEGORIES
We compute net win rates on all question categories in Fig. 5, Similar to Fig. 3, we see that LLMZoo tends be more optimistic about the quality of SoT than FastChat. Nevertheless, the conclusions are consistent: SoT performs relatively well on generic, common-sense, knowledge, roleplay, and counterfactual, and relatively poorly on writing, fermi, math, and coding.
coding
writing
math
writing
rolepley knowledge common sense generic
knowledge
common sense
genaric
counterfactua
counterfactual
80%
.60%
-40%
.20%
0%
20%
40%
-20%
0%
20%
40%
60%
(a) Metrie; general quality (FastChat).
Metrie: general quality (LLMZoo).
Figure 5: Net win rates of SoT different question categories.
We investigate the answers in App. 1.1.2, and summarize the key takeaways follows. SoT per- forms well when the question can be answered in several points whose details can be expanded independently. This includes wide range of real-world questions. On the other hand, it is fun- damentally challenging to apply SoT on questions that require step-by-step thinking, which the latter steps require the details from the earlier steps, such math questions. To make SoT general

---

Published as a conference paper at ICLR 2024
across broader question categories, one promising pathway is to enable SoT to adaptively fall back to normal generation, which we explore in $ 4. Interestingly, our results suggest that some LLMs already able to do that occasionally without special prompting tuning (see A.p.).1.)..
3.2.4 QUALITY BREAKDOWN: METRICS
In Fig. 6, we show more detailed metrics from LLMZoo to reveal in which aspects SoT can improve or hurt the answer quality. On average, we can see that SoT improves the diversity and relevance while hurting the immersion and coherence.
Diversity
27.3%
Relevance
40.3%
25.7%
Immersion
20
30.6%
39.0%
Coherence
21.7%
31.2%
42 15%1%
Integrity
0%
20%
40%
60%
80%
100%
Figure 6: Win/tie/lose rates of SoT v.s. normal generations using metrics from LLMZoo. SoT performs well on diversity and relevance, and relatively worse on coherence and immersion.
Through answer investigation (App. I.13),, we summarize the key takeaways as follows. The skele- stage of SoT explicitly require L.MSs to discuss the answers from multiple aspects without filler words. This improves the diversity and relevance of the answers. As for coherence and immersion, SoT is not worse than the normal generation around 60% of the time. One future direction is to improve the SoT prompts or pipeline so that the answers can be better in more metrics.
4 SOT WITH ROUTER (SoT-R): ADAPATIVELY TRIGGERING SOT
In $ 3, we see that SoT provides considerable speed-ups while maintaining (or even improving) answer quality for many question types. However, the biggest limitation is that SoT not suitable for questions that require step-by-step reasoning ($ 3.2.3). Towards pushing the practical adoption of SoT, we explore the possibility adaptively triggering SoT only when it suitable. To achieve that, we propose router module that decides if SoT should be applied for the then call either SoT or normal decoding accordingly. This paradigm aligns with the recent trends of composing multiple models solve complicated tasks (Chase, 2022; Shen et al., 2023). To implement the router, we explore two options: L.M prompting as the router (no model training is needed) ($ 4.1), and trained RoBERTa as the router ($ 4.2). The evaluation is provided in 4.3.
request, and
4.1 PROMPTING ROUTER
We directly ask LLM if the question is suitable for SoT. More specifically, we ask the LLM if the desired answer list of independent points (see App. C. for the prompt). If the answer yes, will use SoT; otherwise, will use normal generation (i.e., directly feeding the question to the LLM). We employ GPT-4 as the LLM router given its strong capability.
4.2 TRAINED ROUTER
While leveraging GPT-4 as the router obviates the need for model training, its performance remains sensitive to prompt design. Therefore, we approach the problem as sequence classification task by fine-tuning a small language model as the router. Specifically, we annotate the LIMA dataset (Zhou et al., 2023) as the training set to train RoBERTa model (Liu et al., 2019), which has only 120M parameters. Details about the annotation and training can be found in Apps. C.2.1 and C.2.2.
4.3 SoT-R EVALUATION
We compare SoT and SoT-R under the same evaluation setup in & 3. Besides the prompting and trained routers, we also consider a "human router" where we manually judge whether SoT should be applied for each question. This serves as a benchmark for comparison.
7

---

Published as a conference paper at ICLR 2024
4.3.1 EVALUATION OF EFFICIENCY
Fig. 7 shows the speed-ups of SoT and SoT-R for different models on Vicuna-80 (see App. G.2 for results the WizardLM dataset). We can see that: (I) As expected, SoT-R obtains lower speed- ups than SoT, since SoT is not triggered for some questions and the router induces a small latency overhead. Nevertheless, SoT-R can still benefit most models with > 1 x speed-ups. (2) SoT-R with the trained router obtains slightly higher speed-ups for 7 out of 12 models on Vicuna-80, while SoT-R with the prompting router obtains higher speed-ups for all models on WizardLM (Fig. 17).
LLMM6aChhat-7
coding
LaMA22Chat-1338
math
Vicuna-338
OpenChat- 130
writing
fermi
Ultral 138
ralepaay
StableVicune-113
Vicuna
Mcuns-78
ChorGPt 3.5
Cluude
GPT
SoT trained router
SoT twle router)
SoT-R mi prompting ng router
counterfactual
common-serse
knowledge
generic
SoT we human router
Se1th an prompingg rourw
1.0
155
200
25
300
4.0
-80%
.60%%
-0%%
-20%
0%
20%
40%
Figure 7: Speed-ups of SoT and SoT-R on dif- ferent models across all question categories of the Vicuna-80 dataset.
Figure 8: Net win rates of SoT and SoT-R on different question categories of the Vicuna-80 dataset (evaluated with the FastChat metrics).
4.3.2 EVALUATION OF ANSWER QUALITY
Fig. 8 shows the net win rates (averaged across all models) SoT and SoT-R on Vicuna-80 with the FastChat metrics (see App. 1.2 for results of the Wiz dataset and LLMZoo metrics). We can see that: (1) SoT-R significantly improves the answer quality on questions where SoT is not suitable (e.g., coding, math, writing, fermi) by falling back to normal decoding. At the same time, SoT-R maintains answer quality improvements on questions where SoT is good at. (2) The trained router performs similar to (on Vicuna-80) or better than (on WizardLM; see App. 1.2) the prompting router. This accords with our intuition in $ 4.2. (3) The prompting and trained routers could even surpass human router (e.g., on roleplay questions; see more examples on WizardLM in App. I.2).
We discuss the consistency across three routers in App. C.3. The primary takeaways include: (1) on Vicuna-80, there is notable consistency among all three routers, and (2) on WizardL M,, greater discrepancies emerge, with the trained router showing higher alignment with human annotations.
5 SOT IN THE CONTEXT OF LITERATURE
This section positions SoT in related work to reveal how SoT (1) is connected to, (2) is different from, and (3) can harness the power of other methods. See App. D for the expanded discussion.
Efficient LLM methods at model and system levels. At the model level, prior work proposes ef- ficient architectures, including dynamic mixture-of-experts (Lepikhin et al., 2021), low-complexity attention (Kitaev et al., 2020), and multi-query attention (Shazeer, 2019). However, they usually require significant re-training cost. In contrast, compression methods require smaller amount of fine-tuning cost by reducing the complexity of pre-trained LLMs such as quantization (Frantar al., 2022) and weight or activation sparsification (Mishra et al., 2021; Zaheer al., 2020).
At the system level, prior work (1) optimizes the computational graph (Dao et al., 2022), (2) op- timizes the assignment and scheduling of computational graph on devices (Sheng et al., 2023), or (3) designs batching or caching mechanisms for serving multiple users (Fang et al., 2021). These techniques address the large memory access and footprint posed by the vast model scale and atten- tion mechanism, and mainly aim at enhancing the throughput rather than the end-to-end latency. As SoT trades off throughput for end-to-end latency, SoT can make these throughpu-orrenteed tech- niques help with end-to-end latency. This interesting synergy offers opportunities for achieving better trade-offs between latency and throughput in future serving systems.
In contrast to model- and system-level techniques, SoT is data-level technique in new "content co-organization for efficiency" " paradigm. See ğ 6 for more discussions.
Efficient LLM methods through parallel generation. Some prior work also addresses the sequen- tial decoding issues. Speculative decoding (SD) methods (Stern et al., 2018) employ smaller models to generate some consecutive tokens sequentially and apply the target LLMs to verify them paral- lelly. Non-autoregressive generation (NAG) methods (Gu et al., 2018; Xiao et al., 2023) sample and refine consecutive tokens parallelly, often with the support of modified and tuned model.
8

---

Published as a conference paper at ICLR 2024
Relying on either assisting models or special models and sampling schemes, SD and NAG methods conduct parallel verification or sampling and refinement of consecutive tokens. In contrast, SoT prompts the LLM itself to plan the contents in way that permits the parallel generation of tokens in different segments, by exploiting the emerging instruction-folloiing and planning ability of L.Ms..
Prompting methods for LLMs. Recent years have witnessed the emergence of the "pre-train, prompt, and predict" paradigm, which has shown promise in enhancing LLMs' quality in math and commonsense reasoning (Wei et al., 2022; Kojima et al., 2022; Wang et al., 2022; Chen et al., 2022) and planning for multi-modality tasks (Shen et al., 2023; Zhu et al., 2023). Instead of focusing on answer quality, SoT is a first attempt at exploiting the power of prompting to improve efficiency.
6 LIMITATIONS, FUTURE WORK, AND OPEN QUESTIONS
Answer quality evaluation. Our answer quality evaluation is far from perfect due to the limited prompt set, the potential bias of GPT-4 judges, and the inherent difficulty of evaluating LLM gener- ations. Currently, we did not conduct human evaluation since it easy for human to tell whether an answer is generated with SoT due to its distinctive pattern, which might cause evaluation bias.
Eliciting or improving LLMSs ability. $ 3.2.4 demonstrates SoT's potential of enhancing answer quality. is part of broader trend in recent research, exemplified by work including CoT (Kojima al., 2022; Wei et al., 2022). ToT (Yao ct al., 2023), and ReAct (Yao et al., 2022). which collectively affirm the notion that explicitly articulating the thought process in language can elicit high-quality answers from LLMs. These findings resemble human thinking: rather than relying solely on the first intuition or purely sequential thinking, we often document step-by-step reasoning or thought organization to attain high-quality answers. This intriguing parallel prompts us to explore further how we can draw from the human thinking process facilitate more effective and efficient AI.
For instance, SoT currently ignores the dependencies between points. A conceptually better way is to organize the points as Graph-offThougghe point is decoded conditioned on the contents of its ancestor points. In addition, instead of complying with a static graph, we expect the need of having dynamic Traph-of-Thoughee thought structure is adjusted dynamically by LLMs themselves. This could potentially combine the efficiency and global thinking advantages of SoT with the logical reasoning and impromptu think- ing strengths of methods like CoT (Kojima et al., 2022; Wei et al., 2022). Notably, a contemporary to elicit reasoning. Further- more, it is interesting to explore how the SoT answers can be used to fine-tune LLMs to generate more structured answers in a coll-improving way (Zelikman ct al., 2022; Huang et al., 2022).
where the edges represent the dependencies, and each
where the high-level
work (Besta et al., 2023) has attempted to design traph-off-Thuughe
Efficiency and overhead of SoT in different scenarios. Serving systems commonly adopt batch processing to handle concurrent queries. This raises a concern of whether SoT may hurt serving throughput due to parallel requests. (1) When there is unsaturated number of concurrent queries, SoT can effectively reduce latency and enhance GPU utilization. Example scenarios include (a) Edge-side applications with a single user; (b) Centralized services during periods with unsaturated user requests and underutilized computing capacity. It is interesting to study the appropriate SoT triggering conditions based on system workloads. (2) When there a saturated number of concur- rent queries, SoT is still useful for improving answer quality. However, in this case, it is important to consider the computation overhead from SoT. We delve into this concern in App. H.
For API-based models, a notable concern arises regarding the increased number of prefilling tokens (App. H). Given that many APIs charge token usage, SoT may lead to higher costs. To address this, one can use prompt tuning to design shorter SoT prompts (Jiang et al., 2023).
Data-centric efficiency optimization. While data-centric engineering for improving answer qual- ity (Zha et al., 2023; HazyResearch, 2023) is gaining popularity, its potential for inference efficiency is not explored yet. SoT is the first attempt. As LLM capabilities and the amount of LLM-generated data are growing rapidly, data-centric techniques could become more useful in the future. To pave the way towards that, there are a lot to explore. For example, the acceleration ratio of SoT depends on the SoT prompt. the model, and the question, and thus not predictable and controllable as model- or system-level techniques, which might hinder the practical adoption. We look forward to future work unlock the full potential of data-centric efficiency optimization.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We thank Sergey Yekhanin (Microsoft Research), and Tianji Wu (Infinigence AI) for their support and suggestions. This work is also supported by National Natural Science Foundation of China (No. 62325405, 62104128, U19B2019, U21B2031, 61832007, 62204164), Tsinghua EE Xilinx Al Research Fund, and Beijing National Research Center for Information Science and Technology (BNRist). We thank Tianyu Fu for initial discussions on the idea. We thank Ke Hong and Genghan Zhang for discussions about profiling. We thank Yue Wu for the help on the Claude scripts. We thank Da Yu. Chulin Xie, and Saiqian Zhang for their suggestions on revising the first version of the paper. We thank Rui Hu, Cheng Cheng, Jack Jin, Zhoutong Ye, Mingze Sun, Jun Yan, Zhi Zhang, Yuxuan Tong, Nianhui Guo, and Andrea Santilli for their suggestions on revising the second version of the paper. We thank Chris Stetkiewicz, Amanda Melfi, and Amber Tingle from Microsoft for their suggestions and help on writing. We acknowledee support from the Research Foundation Flanders (FWO) through project numbers GOA13199 and S001421N, and funding from the Flemish Government under the Onderzoeksprogrambbn We thank the anonymous reviewers for their insightful questions and suggestions.
Artificiële Intelligentie (AI) Vlaanderen programme.
REFERENCES
Anthropic. Introducing claude, May 2023. URL https::/www..atatriicc.c///////
introducing-cladde.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. arXiv preprint arXiv:2308. 09687, 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. arXiv preprint 17X1v 2019.
Harrison Chase. LangChain, October 2022. URL https:://githabb.cmm//hheessss
langchain.
Charlic Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013/8, 2023a.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211.12588, 2022.
Zhaodong Chen, Zheng Qu, Yuying Quan, Liu Liu, Yufei Ding, and Yuan Xie. Dynamic M fine-grained structured sparse attention mechanism. Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, pp. 369-379, 2023b.
Zhihong Chen, Junying Chen, Hongbo Zhang, Feng Jiang, Guiming Chen, Fei Yu, Tiannan Wang, Juhao Liang, Chen Zhang, Zhiyi Zhang, Jianquan Li, Xiang Wan, Haizhou Li, and Benyou Wang. Lim zoo: democratizing chatgpt. https:/ / //g//ttttt /ggitub....//./ com/ wtt.:ccw///eeeeeee wwtm://eeeemmmneelleeeeee wiiteeeee/eee///// LIMZoo, 2023c.
Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, lon Stoica, and Eric P. Xing. Vicuma: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023. URL https:
//mmys..oos org /bl og/ 2023-03----32 100--30-viiunae
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling instruction finetounddd language mod- els. arXiv preprint arXiv:2210. 11416, 2022.
10

---

Published as a conference paper at ICLR 2024
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 15.16344-16359, 2022.
Emily L Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. Advances in neural information processing systems, 27, 2014.
Ning Ding, Yulin Chen, Bokai Xu, Yujia Qin, Zhi Zheng, Shengding Hu, Zhiyuan Liu, Maosong Sun, and Bowen Zhou. Enhancing chat language models by scaling high-quality instructional conversations. arXiv preprint arXiv:2305.144 14233,, 2023.
Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang. Glm: General language model pretraining with autoregressive blank infilling. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 320-335, 2022.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1):1997-2017, 2019.
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. arXiv preprint a8Xiv: 04833, 2018.
Jiarui Fang, Yang Yu. Chengduo Zhao, and Jie Zhou. Turbotransformers: an efficient gpu serv- ing system for transformer models. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 389-4022 2021.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. The Journal of Machine Learning Research, 23(1):
5232-5270, 2022.
Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Gptq: Accurate post-training quantization for generative pre-trained transformers. arXiv preprint arXiv:2210.17322 2022.
Prakhar Ganesh, Yao Chen, Xin Lou, Mohammad Ali Khan, Yin Yang, Hassan Sajjad, Preslav Nakov, Deming Chen, and Marianne Winslett. Compressing large-scale wranformer-basee mod- els: A case study on bert. Transactions of the Association for Computational Linguistics, 9: 1061-1080, 2021.
Joao Gante.
Assisted generation: //wuggiinfacc..... co/blog
direction toward low-latency text generation. https: 2023. Accessed: 2023-06-23.
Google. Tensorflow serving, 2021. URL Utt.ttts:://gittieee http://tww.com/cccssoooo///////e http://ww/..///////////////////a
Jiatao Gu, James Bradbury, Caiming Xiong, Victor O.K. Li, and Richard Socher. Non-autorrgreesivv neural machine translation. In International Conference on Learning Representations, 2018. URL
https:/ / wpwnrevieeeeeeeeeeeeeeeeee .nt// forum? Bdd
Song Han, Huizi Mao, and William Dally, Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv: 110.0445 2015.
HazyResearch.
Data-centric ai. data-centric-ate 2023. Accessed: 2023-07-04.
https:
Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models can self-improve. arXiv preprint 1xXi::2210.11611 2022.
Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems, 32, 2019.
Andrei Ivanov, Nikoli Dryden, Tal Ben-Nun, Shigang Li, and Torsten Hoefler. Data movement is all you need: A case study on optimizing transformers. Proceedings of Machine Learning and Systems, 1-732, 2021.
11

---

Published as a conference paper at ICLR 2024
Huiqiang Jiang, Qianhui Wu, Chin- Lin, Yuqing Yang, and Lili Qiu. Limlingua: Compressing prompts for accelerated inference of large language models. In Proceedings of the 2023 Con- ference Empirical Methods in Natural Language Processing. Association for Computational Linguisties, December 2023. URL
org/ aaaabb//221/ /201//21000 0...//111.000 05736.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.044 2020.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199-2223 2022.
Raghuraman Krishnamoorthi. Quantizing deep convolutional networks for efficient inference: A whitepaper. arXiv preprint urXiv:1806.08342 2018.
Alex Krizhevsky, One weird trick for parallelizing convolutional neural networks. arXiv preprint arXiv:1404.5997 2014.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. arXiv preprint urXiv:2309.06/88 2023.
Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang. Maxim Krikun, Noam Shazeer, and Zhifeng Chen. {GS hhard: Scaling giant models with condi- tional computation and automatic sharding. In International Conference on Learning Represen- /oppreeveneeeeeeeeeeeeee net http://wwwwe//eeeddeeeeeeoo
tations, 2021. URL /
Brian Lester, Rami AI-Rfou, and Noah Constant, The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104.0869) 2021.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. arXiv preprint arXiv:2211.17/92 2022.
Guohao Li, Hasan Abed Al Kader Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. Camel: Communicative agents for "mind" exploration of large scale language model society, 2023a.
Jiwei Li, Minh-Thang Thang Luong, and Dan Jurafsky. A hierarchical neural autoencoder for paragraphs and documents. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1106-1115, 2015.
Xiang Lisa Li and Percy Liang. Prefix-tuning! Optimizing continuous prompts for generation. arXiv preprint arXiv:2 10..0/01110000000000 00000,000000000 2021.
Xuechen Li, Tianyi Zhang. Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Alpacaeval: An automatic evaluator of instruction-followin models. https::// thub wtt.bb..c//tttttuuttoaaa http://tttttaaaaaaaaaaaaaaaaaaae 1, 2023b.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5315- 5333, 2023c.
Zhuohan Li. Siyuan Zhuang. Shiyuan Guo, Danyang Zhuo, Hao Zhang, Dawn Song, and Ion Stoica. Terapipe: Token-level pipeline parallelism for training large-scale language models. In Interna- tional Conference on Machine Learning, pp. 6543-6552, PMLR, 2021.
Ji Lin. Jiaming Tang, Haotian Tang, Shang Yang, Xingyu Dang, and Song Han. Awq: Activation-aware weight quantization for Ilm compression and acceleration. arXiv preprint 000998 2023.
12

---

Published as a conference paper at ICLR 2024
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre- train, prompt, and predict: A systematic survey of prompting methods in natural language pro- cessing. ACM Computing Surveys, 55(9):1-35, 2023.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, 2019.
Iyya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Confer- ence on Learning Reprexentations, 2019.
Wenyan Lu, Guihai Yan, Jiajun Li, Shijun Gong, Yinhe Han, and Xiaowei Li. Flexflow: A flexible dataflow accelerator architecture for convolutional neural networks. In 2017 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 553-564. IEEE, 2017.
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang. Xinhao Cheng. Zeyu Wang, Rae Ying Yee Wong, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jía. Specinfer: Accelerating generative I1m serving with speculative inference and token tree verification. arXiv preprint arXiv:2305.09971, 2023.
Asit Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius. Accelerating sparse deep neural networks. arXiv preprint arXiv:2/04.08376 2021.
Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R Devanur, Gre- gory R Ganger, Phillip B Gibbons, and Matei Zaharia. Pipedream: Generalized pipeline par- allelism for dnn training. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pp. 1-15, 2019.
Deepak Narayanan, Amar Phanishayee, Kaiyu Shi, Xie Chen, and Matei Zaharia. Memory-efficieed appeline-paralll dnn training. In International Conference on Machine Learning, pp. 7937-7947. PMLR, 2021.
NVIDIA.
Fastertransformer, 2019.
URL https://gtttuub.com///DDDD
RasterTransforme
NVIDIA. Triton inference server, 2021. Criton-inference server.
URL http:://devellperr..vdddd
OpenAl. Gpt-4 technical report. arXiv preprint arXiv:2303.0874,,22 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Duy Phung. Stablevicuna-13b, May 2023. URL
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. Mcasuring and narrowing the compositionality gap in language models. arXiv preprint arXiv:2210.03350, 2022.
Ratish Puduppully, Li Dong, and Mirella Lapata. Data-to-text generation with content selection and planning. Proceedings of the AAAI conference on artificial intelligence, volume 33, pp- 5008-6915 2019.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase and Yuxiong He. Zero: Memory optimizations toward training trillion parameter models. SC20: International Conference for High Perfor- mance Computing, Networking, Storage and Analysis, pp. 1-16. IEEE, 2020.
Jie Ren, Samyam Rajbhandari, Reza Yazdami Aminabadi, Olatunji Ruwase, Shuangyan Yang, Min- jia Zhang, Dong Li, and Yuxiong He. (ZeRO-Offload) Democratizing (Biliion-Scale model training. In 202/ USENIX Annual Technical Conference (USENIX ATC 2/), pp. 551-564, 2021.
13

---

Published as a conference paper at ICLR 2024
Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorca, Michele Mancusi, Ric- cardo Marin, and Emanuele Rodolà. Accelerating transformer inference for translation via paral- lel decoding. In acl, 2023.
Timo Schick, Jane Dwivedi-Yuu Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. arXiv preprint arXiv:2302.04761, 2023.
SenseTime, Lightllm. 2023-09-26.
http:://tthtaaaccccooooooe//o//t 2023a. Accessed:
SenseTime. Openppl. cessed: 2023-09-26.
httpsss/gghhaa.cccm///mppppppppp nn, 2023b. Ac-
Zhihong Shao, Minlie Huang, Jiangtao Wen, Wenfei Xu, and Xiaoyan Zhu. Long and diverse text generation with planning- hicrarchical variational model. arXiv preprint arXiv: 1000:0090000605, 2019.
Noam Shazeer. Fast transformer decoding: One write-head is all you need. arXiv preprint arXiv:1911.02150, 2019.
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hugginggpt: Solving ai tasks with chatgpt and its friends in huggingface. arXiv preprint arXiv:2303. 17580, 2023.
Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Daniel Y Fu, Zhiqiang Xie, Beidi Chen, Clark Barrett, Joseph E Gonzalez, et al. High-throughput generative inference of large language models with a single gpu. arXiv preprinl arXiv:2300 2300200633.66 2023.
Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp- 4222 4235, 2020.
Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autore- gressive models. Advances Neural Information Processing Systems, 31, 2018.
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, Felix Yu, Michael Riley, and Sanjiv Kumar. Spectr: Fast speculative decoding via optimal transport. In Workshop on Efficient Systems for Foundation Models @ ICML2023, 2023. URL https: // //openzeview net/ westtt/frummidddde dorummiddddmmsaahuut.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori Hashimoto. Alpaca: A strong, replicable instruction-followinn model. html, 2023. Accessed: 2023-
06-23.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13977, 2023a
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshom, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev. Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuming Mao, Xavier Martinet. Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi,
14

---

Published as a conference paper at ICLR 2024
Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023b.
Guan Wang, Sijie Cheng, Qiying Yu, and Changling Liu. Openlims: Less more for open-source models, July 2023a. URL https://tt thub. com/ imoneci//penccher
Hanrui Wang, Zhekai Zhang, and Song Han. Spatten: Efficient sparse attention architecture with cascade token and head pruning. In 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pp. 97-110. IEEE, 2021.
Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768, 2020.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou, Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2033.1177,, 2022.
Zifu Wang, Teodora Popordanoska, Jeroen Bertels, Robin Lemmens, and Matthew B Blaschko. Dice semimetric losses: Optimizing the dice score with soft labels. In Medical Image Computing and Computer Assisted Intervention, 2023b.
Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc Le. Finetuned language models are zero-shot learners. arXiv preprint 109.012/, 2021.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of- prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 01244844-48377 2022.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances neural information processing systems, 29, 2016.
Guangxuan Xiao, Ji Lin, Mickael Seznec, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models. arXiv preprint arXiv:2211.10433. 2022.
Yisheng Xiao, Lijun Wu, Junliang Guo, Juntao Li, Min Zhang, Tao Qin, and Tic-yan Liu, A survey non-autoregressive generation for neural machine translation and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng. Chongyang Tao, and Daxin Jiang. Wizardlm: Empowering large language models to follow complex instructions. arXiv preprint MXXi:2334.12244 2023.
Yuanzhong Xu, HyoukJoong Lee, Dehao Chen, Blake Hechtman, Yanping Huang, Rahul Joshi, Maxim Krikun, Dmitry Lepikhin, Andy Ly, Marcello Maggioni, et al. Gspmd: general and scalable parallelization for ml computation graphs. arXiv preprint arXiv:2 105.0463,, 2021.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 10601, 2023.
Gyeong-In In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung- Gon Chun. Orca: A distributed serving system for (Transformer ) generative models. In 16th USENIX Sympo- sium on Operating Systems Design and Implementation (OSDI 22), pp. 521-538. 2022.
15

---

Published as a conference paper at ICLR 2024
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:17283-17297, 2020.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476-15488, 2022.
Daochen Zha, Zaid Pervaiz Bhat, Kwei-Herng Lai, Fan Yang. Zhimeng Jiang, Shaochen Zhong, and Xia Hu. Data-centric artificial intelligence: survey. arXiv preprint vrXiv:2303.10/33 2023.
Yujia Zhai, Chengquan Jiang, Leyuan Wang, Xiaoying Jia, Shang Zhang. Zizhong Chen, Xin Liu, and Yibo Zhu. Bytetransformer: A nigh-eerformance transformer boosted for variable-length inputs. arXiv preprint arXiv:2210.03052, 2022.
Yifan Zhang, Jingqin Yang, Yang Yuan, and Andrew Chi-Chih Yao. Cumulative reasoning with large language models. arXiv preprint arXiv:2308 04371, 2023.
Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Eric P Xing, et al. Alpa: Automating inter-and (Intra- Operator) parallelism for distributed deep learning. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pp. 559-578, 2022.
Lianmin Zheng. Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt-hench and chatbot arena, 2023.
Chunting Zhou, Pengfei Liu, Puxin Xu, Srini Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, Lili Yu, et al. Lima: Less is more for alignment, 2023.
Zhe Zhou, Xuechao Wei, Jiejing Zhang, and Guangyu Sun. {PetS]: A unified framework for Efrfiiete--fffcienttt transformers serving. In 2022 USENIX Annual Technical Conference (USENIX ATC 22), pp. 489-504, 2022.
Xizhou Zhu, Yuntao Chen, Hao Tian, Chenxin Tao, Weijie Su, Chenyu Yang. Gao Huang, Bin Li, Lewei Lu, Xiaogang Wang, et al. Ghost in the minecraft: Generally capable agents for open-world enviroments via large language models with text-based knowledge and memory. arXiv preprint 17.14 2023.
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. In Interna- tional Conference on Learning Representations (ICLR), 2017.
16

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Model Details
18
B Implementation Details of Skeleton-of-Thonggle
18
B.1 Prompt
18
B.2 Supporting Multi-Roun Round Conversation
20
Implementation Details Skeleton-of-Thougeee with Router
20
C.I Prompting Router
20
C.2 Trained Router
20
C,3 Router Consistency
21
C.4 Concurrent exccution for SoT-R
21
SoT the Context of Literature (Expanded)
22
Efficient LLMs
22
D.2
Prompting Methods for L.MSs
................................
23
D.3 Hierarchical Text Generation
24
E Efficiency Analysis
24
F Efficiency Profiling
26
Efficiency Evaluation
27
G.1 Skeleton-of-Thone
27
G.2 Skeleton-of- Thoouhhhtt with Router
29
H Overhead of SoT in Different Scenarios
31
Answer Quality Evaluation
32
L.1
Skeleton-of-Thoughh
32
1.2
Skeleton-of ofear-----TThhhhh with Router
................................
44
I.3
Quality Comparison with Longer Normal Answer ................................
46
1.4
ChatGPT-3.5 as the Judge
46
J Combining SoT-R with Model Quantization
48
J.1
Speed-ups of SoT Quantization on Quantized Models
49
J.2
Speed-ups of SoT Quantization on Unquantized Models
49
K Additional SoT-R statistics
50
K.1 Number of Suitable Questions
50
K.2 Peak Memory Overhead
50
K.3 Speed-ups with Different Number of Points
51
L Notes on Application Scenarios
51
17

---

Published as a conference paper at ICLR 2024
A
MODEL DETAILS
Table summarizes the models on which we evaluate SoT. We use GPT-4 in the main paper and ChatGPT-3.5 in App. 1.4 the judge in FastChat and LLMZoo evaluation.
Table Models evaluated with SoT. All the open-source models are fine-tuned from LLaMA mod-
els.
Access
Model Name
Institution
Released Date
LLaMA2-Chat-7B (Touvron et al., 2023b)
Meta & Microsoft
2023/07
LLaMA2-Chat-I5 (Touvron et al., 2023b)
Meta Microsoft
2023/07
OpenChat- 13B (Wang et al., 2023a)
Tsinghua
2023/07
Vicuma-7B V1.3 (Chiang et al., 2023)
LMSYS
2023/06
Open-Souree
Vicuna-138 V1.3 (Chiang et al., 2023)
LMSYS
2023/06
Vicuna-33B V1.3 1.3 (Chiang et al., 2023)
LMSYS
2023/06
StablaVicuna113 (Phung, 2023)
CarperAI
2023/05
UltraLM-133 M-B (Ding et al., 2023)
OpenBMB & Tsinghua
2023/05
Vicuna-7B V1.1 (Chiang al., 2023)
LMSYS
2023/03
Claude (Anthropic, 2023)
Anthropic
2023/05
API-Based
ChatGPT-3.5
OpenAl
2022/11
GPT-4
OpenAl
2023/03
Table 2 shows sources of the models we use in the paper.
Table 2: The Hugging Face or API endpoints of the models.
Access
Model Name
Hugging Face or API Endpoints
LLaMA2-Chat-77 (Touvron et al., 2023b)
meta-llaama/Llana222--bhhhhee
LLaMA2-Chat-ID 13B
(Touvron et al., 2023b)
meca-llmmllLamma22--3chhhh--
OpenChat- C3 (Wang et al., 2023a)
openchat/opennchat
Vicuna-7B V1.3 (Chiang al., 2023)
Imsys/vicuna-77-v11.3
Open-Source
Vicuna-133 13B V1.3 (Chiang et al., 2023)
Imsys/vicuna-113-v11.3
Vicuna-33B V1.3 (Chiang et al., 2023)
Imsys/vicuna-333--11..
StableVicuna- (Phung, 2023)
CurperAl/saalleviinnn---BB----
UltraLM- 13B (Ding al., 2023)
openbmb/UltraLL--1135 Innys/vicuma-7l--elaaa.111..
Vicuna-7B V1.1 (Chiang et al., 2023)
Claude (Anthropic, 2023)
Claude extension on Slack
API-Based
ChatGPT-3.5
Azure OpenAl, gpt-35-turbo 0301 version'
GPT-4
OpenAI, gpt-4-0613 version
B IMPLEMENTATION DETAILS OF SKELETON-OF-THOUGGH
B.
PROMPT
The skeleton prompt is shown in Prompts and 3 and the point-expanding prompt is shown in Prompt 2.
Skeleton prompt template. In order make the output skeleton short and in consistent format for the good of efficiency and ease of point extraction, the skeleton prompt template (1) describes the
the non-official endpoint TheBBokkkktahlevviemme1111 and TheBBlok/UUmmaLLM-1BB----p to get merged weights.
Foor convenience,
hhttps://wwe anth httppppp..ccoocccceeee----------
mi htttss///onreemnooooff.c..oo/// http:////rrrrrrroeeeeoeeerrre/er
18

---

Published as a conference paper at ICLR 2024
Prompt 3. Skeleton Prompt Template 7 (with Two-Shot Demonstrations)
[User:] You'de an organizer responsible for only giving the skeleton (nor the full content) for answering the question. etc.)
Provide the skeleton sentence, each skeleton point should be very short with only 30-5 words. Generully, the skeleton should have 3>~10 points.
points (numbereed
question. Instead of writing full
Question:
What the typical types of Chinese dishes?
Skeleton:
Dumplings.
2. Noodles.
Dim Sum.
Hot Pot.
Wonton
Ma Po Tofu.
7. Char Siu.
Question:
What practical lips for individuals reduce their carbon emissioos?
Skeleton:
Energy conservation.
2. Efficient tramportation.
Home energy elliciency.
4. Reduce water consumption.
Sustainable diet.
Sustainahle travel.
Now, please provide the skelcton following question. [question)
Skeleton:
[Assistant:]
task precisely, and (2) provides a partial answer "1." for the LLM to continue writing. The skeleton responses in the desired format in most cases. Therefore, ( (\d+) \. \s? (I's sSS)+++ +?) (?=An| \n* to extract point indexes and point skeletons from the skeleton response.
simple regular expression
We find that GPT-4 can work well without the two demonstrations in the skeleton prompt. Therefore, do not include the two demonstrations for GPT-4 (Prompt 1). For all other models, the two demonstrations are included, as shown in Prompt 3.
Point-expanding prompt template. It describes the point-expanding task and provides partial answer. We also provide instructions "Write it **very s in 1~22 sentence" so that the LLMs keep the answers concise. Unlike the skeleton prompt template, we find that demonstrations are not necessary to get reasonable results.
We find that Claude and GPT-4 follows the instruction "Write it **very shortly** in 1~2 sentence and do not continue with other points!" in Prompt 2 very well, so that the answers are very short. Therefore, we delete "** "**very shortly**" from the prompt template in Claude and GPT-4.
Partial answer. In the Prompts 1 and 2, we provide partial answers so that LLMs can follow the desired response format better.
We can put the partial answer at the end of the prompt for the open-source models to continue writing. An implementation detail is that different open-source models have different conversa- tion templates (i.e., different ways to combine user and assistant messages into one string). For example, Vicuna (Chiang al., 2023) uses the string "USER:" and " ASSISTANT." for the place- holder "[User:]" and "[Role]" in the Prompts and 2, respectively, while UltraLM (Ding et al., 2023) uses "User:" and "(/s) Assistantt. We build our open-source model experiments with the help of the FastChat codebase (Zheng al., 2023), in which the conversation templates of many models are already handled correctly. We implement the conversation templates of OpenChat- ViebenV 13B, and UltraLM- 13B according their official guides and codes.
For CharGPT-3.5, we provide partial answers as a last message in the chat history from the assistant. Note that it is not documented approach. We find works well in most cases, in that ChatGPT-3.5
19

---

Published as a conference paper at ICLR 2024
Prompt 4. LLM Prompting as the Router
[User:] Question:
{quertion)
How would like answer the question?
A. Organize answer list of points or perspectives (in the format of 2., 3., etc.), the points or perspeetives unswered independentll without referring the contents of the previous points.
B. Organize the answer as list of points or perspectives (in the format of I,, 2., 3., etc.), and the contents of later points perspectives cannot answered independently without referring C. Do not organize the answer list of points perspectives.
of previous
Just B, C. Do not explain. Do not provide answer to the question. [Assistant:]
continues the texts from the provided partial answer. However, in some rare cases, ChatGPT-3.5 repeats the provided partial answers.
For Claude over Slack, there is obvious way to give the API partial answer. We resort to modifying the prompt template slightly by adding
Please start your answer from "[partial answer)" and do not output other things before that at the end. We find that Claude understands and obeys well. For GPT-4, we also take this approach.
System Message. We do not include the system message in the prompts for open-source models except LLaMA2.
The partial answer, very shortly***, and the 2-shot demonstrations discussed above are the only differences between the prompts we used across all models and all evaluations.
B.2 SUPPORTING MULTI-ROUM. CONVERSATION
To use SoT in multi-round conversation, we can just put the question and the final aggregated answer in the history, removing all the SoT prompts. In this way, using SoT in one conversation round will not introduce additional prefill cost in future rounds.
C IMPLEMENTATION DETAILS OF SKELETON-OF-THOUGHH WITH ROUTER
C.I PROMPTING ROUTER
We use Prompt 4 for querying GPT-4 as the router. the answer "A" (i.e., the question can be answered in list of independent points), will use SoT. Otherwise, if the answer is "B" (i.e., the answer in list of points but they depend on each other) or "C" (i.e., the answer should not be in list of points), SoT not suitable and we will fall back normal decoding.
C.2 TRAINED ROUTER
We tackle the routing problem as a sequence classification task. We first annotate the LIMA training (Zhou et al., 2023), and then fine-tune RoBERTa model (Liu al., 2019) using the labeled data. Finally, we apply the tuned RoBERTa as the router on Vicuna-80 and WizardLM. We detail the steps in the following.
C.2.1 ANNOTATION PROCESS
In the classification task, label of (positive) indicates that this question can be answered with SoT, while a label of 0 (negative) suggests that using the normal generation mode is more suitable. We annotate the LIMA training set, which consists of 1,030 Q&As sourced from three community webpages: Stack Exchange, wikiHow, and the Pushshift Reddit. We also annotate the Vicuna-80 and WizardI M datasets for evaluation.
20

---

Published as a conference paper at ICLR 2024
Table 3: Router confusion matrices on the Vicuna-80 dataset. Left: Rows are human annotations
(H) and columns are the GPT-4 router (G). Middle: Rows are human annotations (H) and columns are the RoBERTa router (R). Right: Rows are the GPT-4 router (G) and columns are the RoBERTa router (R).
GO
G1
RO
RI
RO
RI
HO
38
5
HO
37
GO
34
4
HI
37
H1
32
GI
8
34
Table 4: Router confusion matrices on the WizardLM dataset. Left: Rows are human annotations
(H) and columns are the GPT-4 router (G). Middle: Rows human annotations (H) and columns
are the RoBERTa router (R). Right: Rows are the GPT-4 router (G) and columns are the RoBERTa router (R).
GO
G1
RO
R1
RO
RI
HO
94
HO
135
25
GO
93
H1
3
55
H1
31
27
G1
73
48
We use GPT-4 to assist the annotation process. Specifically, we present each question to GPT-4 and analyze its answer to determine whether SoT can be triggered for this question. We assign a positive label to question if GPT-4's response meets two criteria: (1) it contains a list of points that can be expanded in parallel, (2) each point provides sufficient details (i.e., the point-expanding response is not too short), which will enable SoT to achieve speed-up. Two of the paper's 'ss authors conduct the annotation process independently, and discuss the inconsistent annotations to decide the final label.
C.2.2 TRAINING DETAILS
We use scberta-base with 120M parameters as the router model. The finetuning is conducted using the AdamW optimizer (Loshchilov & Hutter, 2019) with weight decay of 0.01. The learning rate undergoes a warm-up phase during the first 1% of iterations to 5e-5 and then decays linearly. We train the model for 2 epochs using batch size of 32. Input sequences are either padded or truncated to achieve consistent length of 512 tokens.
In the application of SoT, false positives (SoT is incorrectly triggered when it should not be, resulting in degraded answer quality) are of more significant concern than false negatives (the router misses potential SoT trigger, resulting in a reduced speed-up). Thus, to mitigate false positives, we employ the Tversky loss (Wang et al., 2023b) with parameters positives more heavily than false negatives. We also incorporate label smoothing (Szegedy et al., 2016) with factor of 0.2. Overall, the entire fine-tuning process is efficient, completing in minutes on an NVIDIA A100 GPU.
0.7 and 3 0.3, which penalizes false
C.3 ROUTER CONSISTENCY
We present the confusion matrices for the three routers to illustrate their consistency. The results on Vicuna-80 and WizardLM are shown in Tables 3 and 4, respectively.
On Vicuna-80,, we can observe a notable level of agreement among the three routers. Compared with the GPT-4-prompting router, the trained router exhibits slightly higher number of false negatives w.r.t. the human annotations. Conversely, on WizardLM, given the intricate answer structure and the presence of many ambiguous cases, the routers show significant discrepancies. Specifically, the GPT-4 router produces many false positives, which pose adverse affects on the answer quality (see App. 1.2). The RoBERTa router aligns more closely with the human annotations.
C.4 CONCURRENT EXECUTION FOR SoT-R
In SoT-R, the router serves additional stage that extends the two-stage SoT pipeline, illus- trated in Fig. 9. To push the limit of latency optimization, we can rum the router, normal generation, and SoT generation concurrentyy. Once the router makes a decision, generation processes can be aborted. However, this approach will increase the token overhead. Therefore, did not employ this approach in this work and leave it future work.
of the normal and SoT
21

---

Published as a conference paper at ICLR 2024
Skeleton
Expand
Answer
positive
Skeleton
Expand
Auswer
posilise
Question
Router
Question
Router
Answer
negotive
Regutive
Answer
Figure 9: Left: The SoT-R pipeline. Right: possible approach to further reduce latency at the cost of token overhead.
D SOT IN THE CONTEXT OF LITERATURE (EXPANDED)
D.1 EFFICIENT LLMs
Extensive research has been dedicated enhancing the throughput and latency of LLM infer- ence. We first discuss model-level architecture design or compression techniques. These techniques change the model and can benefit both the latency and throughput but require finetuning retain the model quality. Then, we discuss system-level efforts that optimize the computational graph or the assignment and scheduling of the computational graph on computation and storage devices. Most system-level efforts accelerate the prefilling phase or focus on improving the throughput. Finally, we discuss some research efforts that share a similar motivation to ours, namely, addressing the efficiency issue of sequential decoding.
Model-Ievel optimization. Considerable architectural design efforts have emerged to (1) improve the scalability w.r.t model size by introducing mixture-of-ewe -f-eeert inference (Lepikhin et al., 2021; Fedus et al., 2022), (2) address the quadratic complexity w.r.t. input size of attention by designing new attention mechanisms (Kitaev al., 2020; Wang al., 2020), (3) reduce the memory access and footprint of attention by using multi-query attention (Shazeer, 2019), and so on. However, these methods usually require a substantial re-training cost. The model compression techniques require smaller amount of fine-tuning by reducing the model complexity of pre-trained LLM from certain aspects (Ganesh et al., 2021). Representative techniques include quantization (Xiao et al., 2022; Frantar et al., 2022; Lin et al., 2023), the static or dynamic pruning of weights, activation, and attention (Mishra al., 2021; Zaheer al., 2020; Wang al., 2021; Chen et al., 2023b), and so on.
Zooming out from LLM compression to the whole field of model compression, we can see that model co-design or compression for efficiency has received tremendous attention in the past few years and has grown into large research fields, such as pruning (Han et al., 2015; Wen et al., 2016), quantization (Krishnamoorthi, 2018), factorization (Denton et al., 2014), and neural architecture search (Zoph & Le, 2017; Elsken et al., 2019; Cai et al., 2019). Different from the model co-design paradigm, SoT is in a "content co-organization for efficiency" paradigm for improving the LLM efficiency. Along with the growth in the LLM capabilities and amount of LLM- data, data-level techniques could become important tools in the efficient LLM toolbox.
System-level optimization. In the realm of lossless acceleration, considerable efforts have been devoted to addressing the I/O-bound nature of LLMs on modern hardware platforms (Dao et al., 2022). Numerous studies (Dao et al., 2022; Zhai al., 2022; Ivanov al., 2021; NVIDIA, 2019) have focused on adjusting the computational graph by fusing and implementing operations in an VO-friendly way. As a representative method, FlashAttention (Dao al., 2022) fuses all operations of one attention into one GPU kernel with spatially tiled computation to reduce the off-chip I/O of the attention map. While FlashAttention can effectively accelerate training and the prefilling phase of inference, it cannot accelerate the decoding phase much (when the batch size is small), as it is the 1/O of weights rather than activation or attention map that bottlenecks the decoding phase. For example, when the context length is 64, decoding of the 7B parameters from the off-chip HBM onto the GPU chip at least once, but only transferring about 20M (0.02B) activation values between the off-chip HBM and GPU chip.
token using LLaMA-7B needs to load each
In order to satisfy Service Level Objectives, serving systems focus on improving the serving throughput under latency constraints. To this end, serving systems (Fang et al., 2021; NVIDIA,
22

---

Published as a conference paper at ICLR 2024
2021: Google, 2021) pack multiple queries together into batch to improve the hardware utiliza- tion. The batching technique has proven highly effective in enhancing throughput, leading to the development of various variants. For example, some work designs methods to decide which queries to batch together (Fang et al., 2021; Zhou et al., 2022), while others selectively batch parts of the model to enable fine-grained iteration-level batching (Yu et al., 2022) multi-task batching (Zhou et al., 2022). Various model parallelism (Lu et al., 2017; Huang et al., 2019; Narayanan et al., 2019; Rajbhandari et al., 2020; Narayanan al., 2021; Li et al., 2021; Zheng al., 2022) and offloading (Ren et al., 2021; Sheng et al., 2023) techniques have been proposed to maximize the throughput of LLM training or inference. In a nutshell, given the computational graph and device configurations, these techniques optimize the split, assignment, and scheduling of computations, storage, and communications on devices. In addition to the model parallelism and batching tech- niques, an efficient memory management mechanism for LLM workloads is also an essential feature in the serving systems (Kwon ct al., 2023; CenseTime, 2023a;b).
To sum up, these system-level techniques mainly help with the throughput in training and batched inference. They can be used by SoT to improve the throughput of the batched decoding of multiple segments. This means that SoT can hamness the power of these throughput-oriest -orientd techniques and make them help with the end-to-end latency, offering a new dimension for better trading off latency and throughput in future serving systems.
Another parallelism perspective to position SoT is that So' guides the L.M to adjust the sequen- tial workload become "inter-content" parallelizable, which differs from the parallelism levels in existing serving systems, including inter-instance (Krizhevsky, 2014; Rajbhandari et al., 2020), inter-operation (Huang et al., 2019; Narayanan al., 2019; 2021), intra-operation (Xu et al., 2021), and inter-token (Li et al., 2021). It may be worthwhile to explore the integration of SoT into serving systems to maximize the hardware utilization.
Decoding optimization. One bottleneck for the end-to-end latency lies in the autoregressive de- coding phase, where tokens must be generated one by one. Due to the dependency between tokens, the computation of different tokens cannot be parallelized, causing severe ander-utilization of GPU. In order to improve the end-to-end decoding latency of given LLM, speculative decoding meth- ods (Stern et al., 2018; Leviathan et al., 2022; Chen et al., 2023a; Gante, 2023; Sun et al., 2023; Miao al., 2023) propose to use cheaper approaches to generate short candidate token sequences, for example, by sequentially decoding with an assisting model much smaller than the given LLM. Then, they use the LLM to parallelly verify the candidates and keep the prefix sequence that matches the LLM's 's verification results.
Another line of work that shares the motivation of addressing the autoregressive efficiency issue is non-autoregressive generation (NAG) methods (Gu et al., 2018; Xiao et al., 2023). NAG methods sample consecutive tokens parallelly, often with the aid of a modified and tuned model. To maintain the answer quality, instead of sampling for one iteration, many NAG methods refine the output parallelly for multiple iterations (Xiao et al., 2023; Santilli et al., 2023).
To summarize, the speculative decoding methods use assisting models for letting the LLM conduct parallel verification of consecutive tokens, and the NAG methods rely on specially designed models, training schemes, sampling schemes for the parallel sampling and refinement of consecutive to- kens. In contrast, SoT prompts the LLM itself to plan the contents in a way that permits the parallel generation of multiple tokens in different segments. SoT exploits the emerging followinn and planning ability of SoTA LLMS rather than relying on specially designed modeling, sampling, and training schemes. This is different from all existing work that targets the autoregressive effi- ciency issue.
D.2 PROMPTING METHODS FOR LLMS
In recent years, the "pre-train, prompt, and predict" paradigm has emerged (Liu et al., 2023), which designs prompts comprising task descriptions and (optionally) a few demonstrations to guide pre- trained LLMs in generating answers for wide range of downstream tasks. Researchers found that Instruction-tuned LLMs (Brown et al., 2020; Wei et al., 2021; Ouyang et al., 2022; Chung et al., 2022; Taori et al., 2023) possess strong ability (1) generalize new tasks thanks to the diverse
23

---

Published as a conference paper at ICLR 2024
natural language descriptions encountered during instruction tuning, and (2) learn in-context using a few demonstrations without weight tuning.
In virtue of these abilities, the field has been manually engineering (Brown et al., 2020; Kojima ct al., 2022; Shen ct al., 2023; Li et al., 2023a), automatic searching (Shin ct al., 2020), or continu- ously tuning (Li & Liang, 2021; Lester et al., 2021) the prompts for uncovering the capabilities of LLMs on downstream tasks. There are a bunch of prompting methods that improves the reasoning performance of LLMs by designing thinking flows mimicking human reasoning: (1) mimicking the step-by-step or compositional thinking structure (Wei et al., 2022; Kojima et al., 2022; Press et al., 2022: Yao al., 2023; Besta et al., 2023; Zhang et al., 2023). (2) designing multiple reasoning paths and their aggregation (Wang et al., 2022; Yao et al., 2023; Li et al., 2023c), and (3) using tools for calculation and information retrieval (Chen et al., 2022; Yao et al., 2022; Schick et al., 2023). As prompts largely improve the performance
representative example, the Chain-of-Thouge that require logical reasoning by simply providing "Let's think step by step" (Kojima et al., 2022) instruction few demonstrations (Wei et al., 2022). Another topic that arises quite a surge of in- terests is to prompt LLMs to help finish complex multi-modality task (Shen et al., 2023; Zhu et al., 2023). For example, HuggingGPT (Shen et al., 2023) design prompts to guide the LLM generate structural JSON for the orchestration of multi model execution to finish complex tasks.
tasks
To summarize, the large literature prompting methods has been aiming at uncovering different capabilities LLM and improving the answer quality on different downstream tasks. In contrast, So' is a first attempt at exploiting the power of prompting to improve efficiency.
D.3 HIERARCHICAL TEXT GENERATION
SoT can be regarded as being "hierarchical" since it has high-level answer structure planning. Prior studies in hierarchical text generation (Li et al., 2015; Shao et al., 2019; Puduppully et al., 2019; Fan et al., 2018) all focus on enhancing the answer quality, including improving the long-range coherence, relevance to the topic, or reducing redundancy. These methods craft hierarchical neural architectures that contain different modules to model high-level (sentence-level or document-level) and low-level (word-level) dependencies (Li et al., 2015; Shao et al., 2019; Fan et al., 2018). They still employ sequential word-by-wond generation without parallelization between sentences.
Note that the sentence-level representations in previous work (Li et al., 2015; Shao et al., 2019) are "implicit" latent variables instead of "explieit" language descriptions. Some previous studies (Shao et al., 2019; Puduppully et al., 2019) train a dedicated planning module to execute explicit content planning in advance. Nevertheless, these methods all conduct "closed-form" planning that only reorders and groups the input keywords, rather than producing "free-form" " plans on "what to say" and "how to say". All the hierarchical architectures and planning modules require training or even special data processing (Puduppully et al., 2019).
To summarize, in terms of the objective, the primary focus of SoT efficient generation dif- ferent from previous hierarchical text generation literature. In terms of the methodology, instead of designing new hierarchical architectures or planning modules, SoT exploits the emerging planning and custruction-followee abilities of LLMs to do explicit (which means the plan is described by in- terpretable language) and free-form planning. This allows SoT to be applied to off-the-shelf LLMs for producing structured answers.
As the hierarchical text generation literature focuses on enhancing answer quality, they could pro- vide inspiration for future expansions of SoT to generate high-quality answers for broader types of questions.
E EFFICIENCY ANALYSIS
This section gives a detailed explanation on why SoT can reduce the overall decoding latency with the same computational resource for local models.
The vanilla approach processes only one question and decodes the answers sequentially, whereas SoT processes multiple point-expanding requests and the answers in a batch. We focus the p following question: "Compared to processing only one sequence, how much peak memory overhead and latency increase will be brought by processing batch of sequences?"
24

---

Published as a conference paper at ICLR 2024
Table 5: The latency and average GPU performance of the prefilling and decoding phases when inferencing LLMs. The prefilling token length is 128, the decoding token length is 64, and the batch size is The test is run on one NVIDIA A100 GPU.
Model
Prefill/Decode Latency (ms)
Prefill/Decode GPU Perf. (TFLOPS)
LLaMA-7B
40/ 2735
43 / 0.31
LLaMA-13B
54 / 3725
62/ / 0.44
LLaMA-33B
100 5506
85 / 0.75
100
180
11MMA-78
HaMMM-7
HaM4-78
LLONA-138 138
LL29A-138
LLaMA-138
090
LLONA 338
LL 320
LLaM 338
200
(a) Latency (ms)
(b) Actual GPU Perf. (TFLOPS)
(c) Pcak Memory (GB)
Figure 10: The trends of latency, average GPU performance of decoding one token, and peak mem- ory with respect to the batch size of sequences. The prefilling token length is 128, and the decoding token length is 64. The test is run on one NVIDIA A100 GPU.
A typical LLM generative process consists of two phases: (1) the prefilling phase in which the prompt is parsed to generate the key-value cache for further use, and (2) the decoding phase in which tokens are generated one by one in a sequential manner. The decoding phase accounts for the majority of the end-to-end latency, especially when generating long response. As shown in Table 5, when running Vicuna-7B on NVIDIA A100-80G, the actual computing performance is only 0.31 TFLOPS (0.1% utilization) in the decoding phase, compared to 43 TFLOPS (13.8% uti- lization) during prefilling. The utilization is calculated with respect to the FP16 tensor core peak performance 312 TFLOPS for NVIDIA-A100. As result, the latency of decoding only one token is comparable to that of prefilling 128 tokens (40ms). This huge gap in actual computing perfor- mance and thereby the latency arises from the fact that all LLM weights need to be loaded onto the GPU chip at least once only for decoding one token, so the decoding is heavily bottlenecked by the 1/O of weights and the GPU computation units cannot be well utilized.
When conducting batched decoding, as the sequence batch size B increases, the latency of decoding one token for each sequence stays roughly the same (Fig. 10a), as the amount of LLM weights that needs to be loaded onto the chip does not change. As result, the GPU computation utilization (Actual GPU Performance
Peak GPU Performance ) increases almost linearly as B increases (Fig. 10b). In other words, for gener- ating final answer of length N, if we cut the answer into segments of length N/B and decode them batch, we get Bx decoding speed-up compared sequential decoding. Never- theless, in practice, as prefilligg longer requests brings some overhead, and the lengths of the B segments could be imbalanced, the actual speed-up of the batched point-expanding stage compared with the original prefilling and sequential decoding process is smaller than B.
As for the peak memory overhead, the amount of LLM weights can be one to two orders of mag- nitude larger than that of all the intermediate activations as long as the prefilling token length is not too large, not mention that most activations do not need to be saved for nack-propagation during inference. Therefore, the LLM weights account for the majority of the memory footprint in our test cases. Consequently, as shown in Fig. 10c, the peak memory overhead due to the increasing size of the KV cache and activation grows at a slow pace as the batch size B increases. Thanks to the small peak memory overhead, in all of our experiments, we managed to use one GPU run SoT without seeking help from other peak memory optimization techniques (e.g., quantization (Frantar et al., 2022; Lin et al., 2023), offloading (Sheng et al., 2023)).
'All of our experiments run with FP16 inference.
25

---

Published as a conference paper at ICLR 2024
F EFFICIENCY PROFILING
We run the profiling on the target GPU (NVIDIA A100-80G and NVIDIA RTX 3090) with CUDA 11.7, using the Hugging Face transformer library 4.28. and PyTorch 2.0.1. The host of A A100-80G has an Intel Xeon Platinum 8358P CPU and IT memory. The host of RTX 3090 has an Intel Xeon Gold 6246R CPU and 512G memory.
Latency profiling and estimation. For the decoding phase, denote (k) as the latency of batched decoding the k + 1-th token with batch size B, where the superscript D stands for "decode". For each batch size use torch. cuda Event to record the latency of decoding one token. We run each decod- ing three times continuously and take their geometric mean as {t)(())) (k))==1,... 102.:000..1.... ( ,6-- For the prefilling phase, profile the latency of batched prefilling the inputs with token length k in range(1, 700, 10) and batch size stands for "prefill". We run each test seven times continuously, regard the first two times as the warmup tests, and take the geometric mean the last five times as {
1..... 16 and each context length k 1, 1024, we
1, 16, and denote as (k)), where the superscript
691::==-... .16- Once we get the latency profiling table, given request with 4 tokens and the decoding batch size B, the latency of generating to tokens can be estimated as:
4 Σ
T(,, B) = (L.) +
(A))
(1)
where the subscripts and o stand for "input" and "output". Note that we only test the prefill- ing latency every token lengths (i.e., 1,
for fast profiling and estimate & (4. by
( 1).
The SoT decoding process consists of two stages: the skeleton stage and the point-expanding stage. Denoting the token length of the skeleton request and skeleton response I and 15, the token length of the longest point-expanding request and the longest point-expanding response as 1.th and Ige the number of the points as B, we can compute the latency of the skeleton and point-expanding stages as:
(L 12) = T(,,, 1), L pe (1T ,1" B) = T(4 ,ee B).
(2)
(3)
Using the latency profiling table, further estimate the average GPU computing performance in FLOPS (i.c., FLOPs per second) of decoding l, tokens with prefilling length 4, as
Σ + (k) k=h
pd (1. B)
(4)
2km (k)
where (k) denotes the FLOPs of decoding one token with context length k, which is calculated by DeepSpeed's FLOPs profiler Fig. 10b reports the average GPU computing performance during the process of decoding 64 tokens (prefilling length=128), i.., pD (128, 64, B).
Memory profiling and evaluation. To evaluate the peak memory, we use torch. cuda fex___mmrr___aa_
record the memory consumption of prefill- ing sequences of different lengths and decoding with different context lengths and a batch size ranging from 1 to 16. Then, we calculate the peak memory of each stage as the maximum value of the prefilling and decoding phases, and calculate the overall peak memory of SoT as the maximum value of the skeleton and point-expanding stages.
/tttps:///epsppedd readth
26

---

Published as a conference paper at ICLR 2024
G EFFICIENCY EVALUATION
G.1 SKELETONNOF-THHUUGH
G.1.1 DETAILED STATISTICS OF TOKEN LENGTHS AND POINT NUMBERS
10.0
000kg
92
math
500
8.
Turns
1appay
releplay
400
w1thg
-.0
-00
trondedge
2000
genere-
generic
counterfactul
-50
couttorfacuaa
200
Avaruge
Average
1000
v1.
170
4i
(a) The number of points B.
(b) The normal answer length.
2.5
math
formi
Tumn
375.0
2.0
250.0
wrlling
Inowdedge
trentesge
generic
Counter Sccuul
15.0
Average
(d) The ratio of the maximum expndexx sponse length the normal answer length.
(c) The maximum poinn-expanding response length.
codling
60.0
-.0
114
femm
60
rolspla
withig
40.0
wittig
Inowidgge
Imoxdedge
genoic
50
conteraatuu
20.0
countertacual
3.0
common-ss7ee
341
130
Goudd
A
(e) The imbalance degree of poiin--xp response lengths (standard deviation of point token lengths).
(I) The ratio of the final SoT answer length the nor- mal answer length.
Figure 11:
The statistics of the token lengths and point numbers the Vicuna-80 dataset. Each row corresponds to one question category, and each column corresponds to one model.
1.1.2 LATENCY BREAKDOWN: SOT STAGES AND PHASES
Fig. 12 presents the absolute latencies of normal and SoT generations on Vicuna-80. Again, the speed-ups of SoT compared with normal generation is evident. We can see that the decoding phases predominantly account for the end-to-er latency. Consequently, although SoT has higher prefilling latency in the skeleton stage than the normal generation and introduces additional point-expanding
27

---

Published as a conference paper at ICLR 2024
prefilling latency which is expected - this has negligible impact the overall latency and thereby the overall speed-up.
oniting
CP7-
knowledge
136
generic
Wiaan 138 31.3
femi
LLM44 Chat-78 78
Veune-78 31.3
counterfactual
$tabawtcum-11100
releplay
5
poinhespanding
math
5000
10000
1500b
70000
25000
30000
35000
40000
5000
10000
15000
70003
Latinncy ins)
Latenic icy (ms)
(a) Average latency across all question categories except (b) Average latency across all models different math and code different models.
question categories.
Figure 12:
The latency breakdown of SoT and normal generations on the Vicuna-80 dataset. For open-source models, the latency breakdown of the prefilling and decoding phases is shown in dif- ferent colors. For API-based models, we do not record such latency breakdown information; the bar labeled as "(decode)" indicates the overall latency of prefilling and decoding phases.
G. G.1.3 EFFICIENCY EVALUATION ON NVIDIA RTX 3090
We present the SoT speed-ups and latency breakdown on RTX 3090 in Fig. 13. We test the three 7B models, as their FP16 FP16-precision version can be run on an RTX 3090 GPU without further peak memory optimization techniques such as weight quantization (Frantar et al., 2022; Lin et al., 2023) or offloading (Sheng et al., 2023). On these three models, SoT can obtain 1.94x to 2.40x speed-up on average on Vicuna-80.
For the five question categories that SoT can provide high-quality answers (i.e., knowledge, common- sense, generic, roleplay, counterfactual), SoT can speed-up the overall answer generation process by 1.96x to 2.52x in the meantime. Note that for the math category, despite the average speed-up being 1.20x by calculating the speed-up across the three math questions, SoT does not reduce the absolute latency of processing the three questions.
Nomal (prchil)
Nomal (decoda)
writing
2.43x
skeleton (preñto
common
2.39x
SoT point-axparce expanding (prefit)
knowledde
2.37x
SoT point expanding (decode)
coding
2.10x
LLMMA2Chaa-78
2.40x
counterfactual
Vicuna78 V1.
3,26x
formi
1.70x
Viuua-78 V1.3
1.00
2000
4000
6000
12000 Latency (ms)
8000
10000
14000
16000
2000
4000
6000
8000
10000
12000
14000
16000
Latency tme)
The latency breakdown of SoT and normal decoding on the Vicuna-80 dataset. The average speed-up across questions also marked on the figure.
Figure 13:
G.1.4 ACTUAL LATENCY TESTING
This section reports the actual SoT speed-up on the Vicuna-80 with batch testing (instead of analyz- ing with pre-made profiling tables), using single NVIDIA A100 GPU. We test the actual end-to-end latency of the SoT and normal decoding with the open-source models. For each model, we run the speed-up test for five times and plot the box in Fig. 14.
28

---

Published as a conference paper at ICLR 2024
As shown in Fig. 14a, the current SoT solution obtains 2x speed-up 6 out of the 9 open- source models (i.e.. Vicuna-7E 7B V1.1, Vicuna-7B V1.3, UltrLLM-13B, LLaMA2-Chate Chaththt-B Vicuna- 13B V1.3, and LLaMA2-Chat 13B), and 1.7 speed-up OpenChat-13B and Vicuna-33B V1.3. SoT achieves no speed-up on StableVicuna- Vicuna- 13B. As shown in Fig. 14b, for the five question cate- gories that SoT can provide high-quality answers (i.e., knowledge, common-sense. generic, roleplay, counterfuctual) SoT can speed-up the overall answer generation process by 2.15x X to 2 in the meantime.
2.50x
Mcuna-78
knowledge
220
coding
2.50
counterfactua
H
LLLMAZ Choc-158
2.34
wrkking
OpenChar-138 138
197x
roteplay
Viuuna133 130 V1.3
1.75x
mwrh
StatraWeure--30-
0.974
10ml
1.8x
3.0
2.5
(a) Average speed-up on different models.
(b) Average speed-up on different question categories.
Figure 14: Speed-ups open-source models the Vicuna-80 dataset with actual batch testing.
G.2 SKRLATON-OF-THOUGHH WITH ROUTER
The overhead brought by the router inference is relatively small: On the Vicuna-80 dataset, the prompting and trained router have an average latency of 0.65s (0.39s~1..7s)) and 0.04s 0..00s~~1.555) respectively. On the WizardLM dataset, the average latency of the prompting and trained router is 0.80s (0.368~~2.22s) and 0.03s (0.509)~2.52ss, respectively.
G.2.1 SPEED-UP BREAKDOWN: MODELS
Fig. 15 shows the speed-ups of SoT-R on different models on the Vicuna-80 dataset. Fig. 16 and Fig. 17 show the speed-ups of SoT-R on different models on the WizardLM dataset. We can ob- serve that on Vicuna-80, the two methods yield similar speed-ups, whereas on WizardLM, GPT-4 prompting router usually obtains higher speed-ups than the trained router, especially on GPT-4 itself.
LLMAA2-hats Chat-1 38
1,70x
OpenChat-138 38
1.02X
OpenChat-1 38
78
3.63X
Vicune700 v1.3
Vieuna-18
M-1 30
50x
Vicuna-3300
U 30
S1x
GP
-40
Vicuma v1.1
Vicuna 78
130
1:34
3.a
ChatGPT-33
StableVicune
Stablevicuna- 136
0.90%
1.0
1.2
1.4
1.6
1.8
2.0
2.2
1.0
1.2
1.4
1.6
1.8
2.0
2.2
(a) Average speed-up across question categories with prompting router.
(b) Average speed-up across all question categories with trained router.
Figure 15: Speed-ups of SoT-R different models Vicuna-80 dataset.
29

---

Published as a conference paper at ICLR 2024
Vicuna333B V1.3
1,00K
BeenChar-139
1,42x
Viduna
Mouna-133 13B 31
LaKAA Crst 76
Micun-78 W1.1
LakAz Chat 139
35x
LaNAZ Cast 78
131K
33B V1.
333
Vicune
EhaxGPT-335
1.40%
Vicuna: 138 V1.3
1.31%
StableVicuna 130
Claude
1,25
1,30
1.75
2,00
2.25
2.50
2.75
1.30
1.75
2.00
2.25
2.50
2.75
(a) Average speed-up across question categories with prompting router.
(b) Average speed-up across all question categorics with trained router.
Figure 16: Speed-ups of SoT-R on different models WizardLM dataset.
GPT44
UltratM-1331
Openthat-11300
Mcuna-338 V1.3
ChatGP7:15 1-5
Sol Iwlo router)
ULMM Chat-70
Vicuna-78 V1.3
prompting
StableVicune-113
Cladde
1.5
2.0
2.5
3.0
3.5
4.0
Figure 17: Speed-ups of SoT and SoT-R on different models on the WizardLM dataset.
G.2.2 SPEED-UP BREAKDOWN: CATEGORIES
Fig. 18 and Fig. 19 show the speed-ups of SoT-R on different question categories of Vicuna-80 dataset. The trained router achieves slightly higher speed-up on most of the categories (except for knowledge, writing, and fermi). Fig. 20 and Fig. 21 show the speed-ups of SoT-R different question categories of WizardLM dataset. We can observe that on 19 out of 29 categories, using the prompting router achieves higher speed-ups than using the trained router.
generic
2.76x
common-sense
2.05x
2.10x
knowladge
1.95x
knowledge counterfactuull
1.87x
counterfactual
1.75%
1.79x
roleplay
1.17x
roloplay
1.23x
writing
1.10x
termi
1.00k
ferm
1.01x
coding
7.00x
coding
0.90%
math
1.00
125
150
1.75
2.00
2.25
2.50
2.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
2.75
(a) Speed-ups of SoT-R with prompting router dif- ferent question categories.
(b) Speed-ups of SoT-R with trained router different question categories.
Figure 18: Speed-ups of SoT-R on different question categories of Vicuna-80 80 dataset
knowledge
generic writing
roleplay
SoT (wlo router)
counterfactual
w/ prompting router
ferii
S-T.R trained router
math
2.0
2.5
Figure 19: Speed-ups of SoT and SoT-R different question categories of the Vicuna-80 dataset.
30

---

Published as a conference paper at ICLR 2024
Counterisctual
2.23x
Counteriactul
12 2
Economy
2.26x
2.18x
History
2.10x
Sport
Medicine
1,93X
Chemistry
1.73x
Law
Economy
1,00x
LKerature
85
TruthfuQQA
1.61%
Writing
Common Sende
Academic
Wrtting
1.09
Toxlcty
1.22
Chemistry
Mubllinuull
1.7%%
Roledlay
L58x
Computer Science
1.117
Rusic
54x
Physis
1.14%
Reasoning
1.05%
Code Debug
1.25 225
Philssphy
.000%
Comman- Sense
Academic Willing
1.00%
Mutilingual
Complex Format
144
Code Debug
-00%
Toxccty
Literature
intertimment
103%
Math
1.0xx
Code Gencration .002%
Complex Format
1 0000
Physics 80,94x
Entertainment
1. 1.00x
Moth 8.85X
Code Generation
10.9 0.99
2,00 2.25
(a) Speed-ups of SoT-R with prompting router on dif- ferent question categories.
(b) Speed-ups of SoT-R with trained router on different question categories.
Figure 20: Speed-ups SoT-R on different question categories WizardL.N M dataset
Counterfactual
Fconomy
Technology
Medicine
Writing
Sport
Code Generation
Roleplay
Philosophy
Academic Willing
Chemistry
Code Debuq
Computer
Ethics
Toxicity
Music
Bioloey
Common-Senie
Multlingual
Reasoning
SeT (W/ router)
Physics
SoT-R w/ prompting router
Entertainment
trained
1.75
Figure 21: Speed-ups of SoT and SoT-R different question categories of the WizardLM dataset.
H OVERHEAD OF SOT IN DIFFERENT SCENARIOS
Despite the optimizations made to the decoding phase, SoT brings overhead to the prefilling phase as the model needs to handle additional SoT prompts. Table reports SoT's prefilling overhead for the API-based models. These statistics are averaged across the Vicuna-80 questions that are suitable for SoT (according to our manual annotation). We can see that SoT significantly increases the number of prefilling tokens. This is because that SoT issues independent point-expanding request for each point, with the average number of points being 6.8 on Vicuna-80 dataset across all evaluated models. Consequently, the APIS need to prefill the point-expanding request multiple times.
31

---

Published as a conference paper at ICLR 2024
Table SoT's prefilling token overhead for API-based models.
Prefill Phase
Model
Normal
SoT Stage
SoT Stage
Ratio (SoT / Normal)
Claude
10.33
155.33
730.91
85.79
ChatGPT-3.5
10.21
136.33
480.95
60.46
GPT-4
10.21
72.44
838.26
89.20
When using SoT to serve the open-source models, simple and small trick is to prefill the common prefix of point-expanding requests with batch size during Stage 2 (i.e., the point-expanding stage). Table 7 shows the prefilling overhead after applying the trick. Although the ratio is consid- erably smaller compared to that of the API-based models, this computational overhead remains a concern, especially during periods of high system workload.
There are some possibilities to further reduce the token and computational overhead that are worth exploring in future work. To name few: (I) When using SoT in serving systems, can simply reuse the key-value cache containing the question and skeleton from Stage during Stage 2, rather than re-prefilling them as multi-round conversation. (2) Generally, as LLM capabilities continue to evolve and prompt tuning techniques advance (Shin et al., 2020; Li & Liang, 2021; Lester et al., 2021; ;; Jiang al., 2023), the possibility of using much shorter prompts to activate the SoT mode in the future holds promise, which would significantly mitigate the token or computational overhead.
Table SoT's computational overhead (in terms of the number prefilling tokens) for open-source models.
Prefill Phase
Model
Naive
SoT Stage
SoT Stage 2
Ratio (SoT) Normal)
LLMA22-Chtt77
12.52
171.41
216.49
30.98
LLaMA2-Char 133
12.52
171.41
216.41
30.98
OpenChat-132
12.52
171.41
234.38
32.41
Vicuna-7B V1.3
12.52
171.41
211.61
30.59
Vicuna- 13B V1.3
12.52
171.41
273.39
35.53
Vicuna-33B V1.3
12.52
171.41
258.88
34.37
Stable Vicuna- 13B
12.52
171.41
312.03
38.61
UltraLM-13BB
12.52
171.41
290.88
36.92
Vicuna-7B V1.1
12.52
171.41
196.64
29.40
T ANSWER QUALITY EVALUATION
1.1 SKELETON-OF-THOURE
I.1.1 ANSWER ANALYSIS: DIFFERENT MODELS
Models on which SoT has low net win rates. We observe two types reasons for the low net win rates.
(1) OpenChat-13B. Vicuna-7B VI.1, and LLaMA2-Chat-133 For the weak models such as OpenChat-13B and Vieuna-7B V1.1, they not able to follow the SoT prompts precisely. For OpenChat-13B and LLaMA2-Chate 13B, sometimes the skeleton contains undesired contents (c.g., completing the skeleton points shown below).
32

---

Published as a conference paper at ICLR 2024
Question: How many lightning strikes occur Earth each day? Try explain your answer. Your explanation should take the reader through your reasoning step-by-step.
SoT's answer (OpenChat-Il (Orange texts the skeleton.)
(Onyy showing the skeleton)
Introduction.
The Earth's atmosphere.
Lightnng formation.
Electrical discharge.
5. Lightnng strikes per second.
Calculating the total.
Skeleton:
Introduction.
Lightning is heautiful and wie-iinpiiing natural phenomenon, hut also dangerous, It occurs when positively charged partieles chundercloud discharge to the negatively charged Earth. The process still not fully understood, but scientists have boen ablo estimate bow many lightning strikes Skeleton:
Earth each day.
The Earth's is atmosphere.
The Earth's stmossphere plays crucial role the formation of lightning. It consists of different layers, with the tropo- sphere being the lowest and most active. The troposphere is where most the weather occurs, and where lightning primarily forms. The stmosphere's temperature, humidity, and wind patterns all contribute the likelihood of lightning strike.
Skeleton:
2. Lightning Formation.
warm, moist rises, cools forms water <imore texts are omitted...
For both OpenChat- 133 and Vicuna-7B V1.1, sometimes they do not write anything in the point- expanding stage when details are needed.
Question: As superhero, how would you explain your origin story curious child?
SoT's answer (Vicuna-7B V1.1) (Orange texts are the skeleton.)
Born with extraoriinary abilities. Trained
for the greater good.
Protecting the innocent and fighting villains. use my powers to defend the defenseless and bring justice to those who
wronged.
4. Inspired by courage. justice, and selflessness.
These two issues result in bad net win rates.
(2) Claude. For strong models such Claude, we do see major issues with SoT's answers except the common issues across all models discussed in 3.2.3. We hypothesize that the low net win rates are majorly due to the fact that their normal sequential generation already very good.
Models on which SoT has high net win rates. The models with high net win rates (Vicuna- 13BB V1.3, StableVicuna 13B, and UlrraLM-13BB are between the above two extremes. On one hand, they are good enough to understand SoT prompts. While we observe that they sometimes have the same issues as OpenChat- 13B and Vicuna-7B V1.1 discussed before, these issues happen much less frequently. On the other hand, their normal sequential generation performance has larger room for improvement than Claude and ChatGPT-3.5 so that the benefits from SoT are more visible on these models.
1.1.2 ANSWER ANALYSIS: DIFFERENT QUESTION CATEGORIES
Categories on which SoT has low net win rates.
(1) Math. Math questions require step-by-step thinking. Without knowing the previous steps, is hard to derive the following steps. Chain of Thoughts (Kojima et al., 2022; Wei et al., 2022) empha- size the importance of expanding the sequential thinking steps solve these problems successfully. In contrast, SoT requires the models to (a) come up with the skeleton of the solution first and (b) deduce each individual step independently without referring to previous results. Both of these are challenging tasks. Strong models are able to get (a) correct but fail at (b). In the following example, ChatGPT-3.5 gets the skeleton steps correct. However, without knowing the results from the first step, the model starts making mistakes in the second step.?
One additional (minor) issue of the API-hased ChatGPT-3.5 is that the skeleton point "1." is repeated in the answer.
33

---

Published as a conference paper at ICLR 2024
Question: (Math) Solve for in the equation 3x 10 5(x
X SoT's answer (ChatGPTT33.5) (Orange texts are the skeleton.)
1. Move all terms one stiee. 1. Move all terms to one side by subtracting Sx from both sides, giving 2x =0 -10. by subtracting
Move
both sides, leaving 5x
-10- 10.
Simplify the equatioo. Comhine like terms on hoth sides of the equation to get + 10 5x 10.
get Check the solution by plugeing back into the original equation Substitute the value of obtained in step back into equal.
Divide both sides coefficient Divide both sides
original equation verify
Normal answer (ChatGPT-3355)
3x 10 Six 2) he simplified follows:
3x + 10 5x (distribute the on the right side)
10 5x (subtract
both sides)
20 = 2x (combine like terms on the right side)
(divide both sides by
Therefore, the solution for the equation 3x 10 Six 2) is 10.
For weaker models, it is hard to even get step (a) correct. For example, shown below, the third step "Apply FOIL." in Vicuna-13B V1.3's SoT solution comes out of nowhere. This makes SoT's solution incorrect (though the solution from the normal generation is also incorrect).
Question: (Math) Solve in equation
5(x
SoT's answer (Vicuna-133B V1.3) (Orange texts the skeleton.)
Simplify equation.
can simplify the equation by combining like temss
3x 10 5(x 2))
Ft 3x 10=
10
==
=
*; =3
Factor -).
5xx-)==5x 5
Apply FOIL.
Mulltiply the hinomials in the equation, using the first term of each hinomial for the first term the product, the cutside product, the second each binomial for the third term the product, and the
for the second remaining terms for the fourth tern of the product. 5(-2)
3(x +)
3x 5x
3x
"x= 5x 10/3
*x= 5/3x 10/3
2/3x
4. Solve for
After applying
method simplifying the equation, we get Therefore,
Normal answer (Vicuna-13B V1.3)
To solve for
equation 3x 2), need first distribute the multiply both sides
3x + 2)
5(x 10) 5(
15x + 50 3x 10
20x 50 5x
Subtract 5x from both sides:
15x 0
Divide both sides by 15: ==0
Therefore, the solution to the equation O.
(2) Fermi. Similar to math questions, questions the fermi category require solvers to make as- sumptions and caleulate the answer step-by-step. For example, to answer the question in the figure below, the solver is required to make an assumption about when life began on Earth. In step 4, ChatGPT-3.5 does not know that it has already assumed 3.5 billion years in step 3 and uses the wrong number 4.54 billion in the calculation. In step 5, ChatGPT-3.5 does not know that it has already made the above assumptions and refuses to answer "due to the uncertainties estimating the age of the Earth". In contrast, normal generation is able to create a consistent solution.
34

---

Published as a conference paper at ICLR 2024
Question: (Fermi) How many times has the Earth orbited the Sun since the beginning of life? Try to explain your answer. Your explanation should take the reader through your reasoning step-by-step.
SoT's answer (ChatGPT-3.5) (Orange texts are the skeleton.)
Estimate the age of the Earth. The age the Earth estimated to around 4.54 billion years, based radiometric dating of rocks and meteorites.
Determine when life began Earth. Life on Earth estimated to have begun around 3.5 billion years ago, based on the discovery of ancient microfosils..
known fossils suggest that life on Earth began around hillion years ago. Therefore, the number of years since life began on Earth is approximately 3.5 hillion years.
Calculate the number years since life began.
Divide the number of years by the length of one orbil. Assuming an orbital period of 365, 25 days, the Earth has orbited the Sun approximately 4.54 billion / 365.25 12,425,000 times since the beginning life.
The Earth has orbited the Sun approximately X times since the beginning of life. Unfortumately. is impossible to give specific number for amount times the Earth has orbited the Sun since the boginning life due the uncertainties in estimating the age of the Earth and when life first emerged.
Normal answer (ChatGPTT3355
beginning life Earth estimated to have occurred around billion years ago. Since time, the Earth has been othiting the Sun continuously.
length of one ochit, or one year, approximately 365.25 days. This means that Earth completes one orhit
around the Sun every 365 25 days.
To calculate the number of times the Earth has orbited the Sun since the beginning of life, we can divide the total number of days by the longth of one orbit:
Total number of days since the beginning of life = (3.5 billion years) (365 days per year) = 1.2775 trillion days Number uebits (1.2775 trillion days) / (365.25 days per orbit) 3.5 billion orbits
Therefore, the Earth has arbited the Sun upproximately 3.5 billion times since the beginning of life.
As the following example shows, there are also cases when SoT solves the question (with minor computation errors) by embedding the computation steps in the skeleton directly in the skeleton stage. The point-expanding stage will then add little content (except some undesired repetition of the following skeletons occasionally). This happens both on small/weak models and large/powerful models. Although this behavior is not what we originally expect, it sheds light promising direc- tion for making SoT a general framework: the problem where step-by-step thinking is needed, the SoT model automatically falls back to the sequential generation mode by outputting the complete stage. Future work needs to be done
answer in the skeleton stage and skipping the to control and encourage this behavior better.
Question: (Fermi) How many times does the average human blink in a lifetime? Try to explain your answer. Your explanation should take the reader through your reasoning step-by-step.
SoT's answer (Vicuna-7B V1.1) (Orange texts are the skeleton.)
The average human blinks 12-15 times per minute.
2. There are 60 minutes in an hour.
Therefore, average human blinks 60 x 12-15 720-900 times per hour:
4. There are 24 hours in Therefore, the average human blinks 720-900 24 = 17,520-22,400 times per day.
Therefore. average haman blinks 720-900
= 17,520-22,40X times per day This trassattes to blinking approxi-
mately 50-65 times per hour, which is significant portion of the day. There are 365 days in a year Therefore, the average human blinks 17,520-22,400 x 365 5,857,6060 337,66008, 124,000 times per year.
7. Therefore, the average human blinks 17,520-22,44 x 365 = 5.857.6000 1016000-81122 1,1,000 times per year. The hurnan lifespan is typically 70.80 years. Therefore, the average human blinks 80,000- 10,000-112,000 122,00 times in their liferime.
9. Therefore, the average human blinks 5887.600-8.1240000 70-80 80,000-112,000 times in their lifetime.
Normal answer (Vicuna-7B VI.1)
The average buman blinks about 12-15 times per minute, which translates to sbout 18,200 20,400 blinks per day. Over the course of lifetime, the number of blinks is estimated to be around 7,500,000 to 8,000.000. Blinking is a reflexive action that helps keep cyes and other foreign particles. The frequency of blinking can vary depending on a variety of factors, including age. health, example, people who work dusty or dry enviromments may
and confortable, well to protect the eyes from dust
and envirommental conditions. than those who work in a clean, moist enviromentt
more frequenily
Over the course of a lifetime, the average person will spend approximately 27,375 days or 700,000 hours awake. This means that the majority of the time spent blinking will occur the first few decades life, with the frequency of blinking gradually decreusing as people age.
individual variation in the frequency of blinking. Some people may blink more or less than the average, depending on a variety of factors such as age, health, and environmental condi- tions. Additionally, blinking patters can affected by factors such stress, fatigue, certain medical conditions.
It important note that there significant
35

---

Published as a conference paper at ICLR 2024
(3) Coding. While in most cases, the models are able to decompose the coding problem into smaller tasks in the skeleton stage, the generation quality during the pxint-expanding stage is bad, potentially due to the fact that we did not carefully craft special point-expanding prompt for coding. The failure cases can be grouped into two cases. (a) In some cases, the model only generates a description of how implementation
be done without giving the code.
Question: (Coding) Develop a C++ program that reads a text file line by line and counts the number of occurrences of a specific word in the file.
SoT's answer (Claude) (Orange texts are the skeleton.)
Open file stream by doclaring ifstream object and using the open() method open the file read mode.
2. Read line hy line from the file stream into string using gerline().
Find word by scarching each for the target word using string:rfind koeping track matches.
Increment counter by each time the specifled word is encountered the current line.
Close lile
The file stream should be closed alter linishing reading the lile free resources. This can be dome calling
close() method on the file stream object.
This might be due to the fact that the powerful models (e.g., Claude) follow the point-expanding prompt "Write it #* **very shortly** in 1~2 sentence" precisely. Better prompts tailed to coding could help. (b) In some other cases, the model tends to generate the complete code repeatedly in several points.
Question: (Coding) Develop a C++ program that reads a text file line by line and counts the number of occurrences of a specific word in the file.
SoT's answer (OpenChat-133) Chat--3B) (Orange texts are the skeleton.)
by
2. Store lines in a container.
oocurrences specific word.
"cpp
<more texts are onitted....>
This codo uses the C++ standard library to read text file line by line, store each line in container, and count the occureences specific word. The results are printed.
4. Print results. Here's 's C++ program that text line by line and counts the number occurrences specific word file:
"epp
omitted...>>
note that this a very implementation. You may adjust depending your specific requirements.
This problem might also be alleviated by prompts that explicitly tell the model to only generate "code snippet" in each skeleton point.
Although better prompt engineering could lead better results, we expect that SoT is not suitable for the coding questions in Vicuna-80. The reason is that the solutions to the problems in Vicuna- 80 are usually in few lines with strong dependencies between each other. Without knowing the previously defined variable names or imported libraries, it is hard (or even impossible) to implement the subsequent code correctly. As consequence, generating different parts of the answers in parallel is not suitable here. Similar to the math questions, automatically falling back to outputting all the code in the skeleton stage and not triggering the point-expanding stage might more suitable for answering this question type.
However, we expect that SoT could be helpful for larger coding tasks that involve multiple modules (e.g., functions, classes). The skeleton stage could be in charge of defining the interfaces between different modules (e.g., functionalities, names, parameters, return types). The point-expen pointeexpanding stage could be in charge of implementing these modules using these modules to complete the final task, which can be done in parallel. This mimics the common practice in software engineering.
(4) Writing. The writing questions usually ask for email, blog post, review in given scenario. In the detailed evaluation output from FastChat and L..MZoo metrics, the major and common complaint is that SoT's answers are (slightly) less detailed. This could potentially be improved by popadinx prompts that request more details.
36

---

Published as a conference paper at ICLR 2024
While inspecting SoT's answers manually, observe one additional issue. Writing problems ally require a coherent passage without embedded skeleton points, whereas our current SoT pipeline ($ 2) concatenates skeleton points as part of the answer. One example is shown below.
Question: (Writing) Can you help me write a formal email to a potential business partner proposing a joint venture?
SoT's answer (ChatGPTT-355 (Orange texts are the skeleton.)
Introduce yourself and your company. Dear [Rocipicut].
1 hope this email linds you well. My name is YYour Name] and am the Your Position] at Your Company Name
The purpose of this 3. Explain the potential henefits of the joint venture. By combining our resources and expertise, we increase market
purpose the
propose joint venture between our companies.
share profitability for both companies.
proposed collaboration. Our proposed collaboration would involve combining expertise in marketing with your strong manufacturing capubilities to create a new line of products.
Provide details
Suggest follow-up meeting call. Please know your availability for follow-up next this opportunity Turther.
Thank the recipient
consideration you considering this proposal we look forward to
bearing back from soon.
Normal answer (ChatGPT-3.5)
course, help you with Here's sample email you can use as a guide:
Subject: Proposal for Joint Venture
Dear [Business Partner's Name].
between companies, [Your Company Name] and [Potential Partoer Company Name). We believe that our respective expertise can crcate a successull partnership that benelit of our businesses.
hope this email finds you well. writing propose
We have conducted thonuug research on your company and admire your innovative appronch to [insert industry or niche]. think [insert expertise or specialty] could complement your [insen potential partner's specialty expertise] By collaborating on this joint venture, we believe can create new and innovative product that will appeal to respective markets.
We confident that companies would work well together and that joint like to set a meeting to discuss the specilics of our proposal and explore how we can move forward with the joint venture.
would be suceessful. would
Thank you for considering this pmopssa. We look forward to hearing from you soon.
Best regards.
Youur Namel
In such cases, simply removing the skeleton points would greatly improve the answer quality. To make SoT more general, one future direction is to let the LLLM itself decide whether the point index and point skeleton should be included to make the final answer more natural and fluent.
Categories on which SoT has high net win rates.
(1) Counterfactual, knowledge, common sense, generic. All these four categories have the same characteristic: the ideal answer should cover several relatively independent points. Having the LLM generate a skeleton before expanding the details can result in more comprehensive discussions for the question. Besides, organizing the answers as list points makes the answers easier to read, whereas the answers from normal generation are sometimes less structured and less readable. Below, we give one example for each question category to illustrate these points.
37

---

Published as a conference paper at ICLR 2024
Question: (Countcrfactual) What if the Internet had been invented during the Renaissance period?
S answer (ChatGPPT-355 (Orange texts are the skeleton.)
1. Advansements in communicaiion The inveation of the Interett during the Renaissance period would have revolution- communication, allowing for faster and more ellicient exchange of ideas information across vast distances. Increased access to knowledge The invention of the prining press during the Renaissance period already allowed for greater access to knowledge,
internet would have revolutionized this even further by providing instantaneous to information from all over the world.
Improved dissemination of idens.I If the internet had heen invented during the Renaissance period, the spread of ideas the time. This could have led faster
and knowledge would have been much faster and widespread than progression of scicatific and artistic innovations.
Impact on art literature: The invention of internet during the Renaisance period would have revolutionized art and literature are created, shared, and consumed, leading to more diverse and globally -nnilly--feeeeedd artistic and literary scene.
Potential for global trade.The invention of the internet during the Renaissance period would have greatly expanded global trade opporunities, allowing for casier commanication and collaboration between merchants and traders across continents.
6. Inffuence on political and social structures. The invention of the internet during the Renaissance period could have led significant changes political and social structures, allowing greater democratization and communication among people from different regions and classes.
Normal answer (ChatGPT-3.5)
the Internet had invented during the Renaissance period, would communicated. shared ideas, and gained knowledge. The Renaissance was time of great intellectual and artistic growth, and the Internet would have Escilitated the spread these ideas and innovations. Scholars and artists would have been able share their work would have been able tn connect and collahorate more easily. The Internet would have also made it easier to access information, which could have accelerated tbe pace scientitic and technological advancements.
a significant impact on the way people
easily, peuple from different parts of the world
However, it's important to note that the infrastructure required for the Internet to exist did not exist during the Remuissance period. There were telccommunications networks electricity grids, so idea Internet would have been impossible to realize. Nonetheless, it's interesting to think about how the Renaissance might have been different if the Internet had existed that
38

---

Published as a conference paper at ICLR 2024
Question: (Knowledge) What are some potential implications of using a single-use plastic bottle versus a reusable bottle on both the environment and human health?
SoTss answer (ChatGPPT3355) (Orange texts are the skeleton.)
Single-ase plastic waste Single-uxe plastic bottles contribute to the massive amount plastic waste that ends up in landfills and occans, harning wildlife and coosystems.
Pollution of waterways Single-use plastic bottles contribute to the pollution of waterways, as they otten end up in lakes, and oceams, causing harm to aquatic life and the overall evosystem.
Harmful chemicals leaching Single- use plastic bottles may release harmful chemicals such as bisphenol A (BPA) and phthalates into the water liquid they contain, posing a risk human health.
4. Groenhouse gas emissions The production and disposal of single-use plastic bottles contribute to greeahouse gas emissions, which contribute to elimate change. Using a reusable bottle reduces the need for constant production and disposal, therefore reducing greeahouse Microplastic ingestion.iingl-ut Single-use use plastic bottles contribute to the accumulation of microplastics in the environment, leading potential bealth risks.
emissions.
which can ingested by humans thruug food and
Increased risk of disease Single use plastic bottles can harbor harmful bucteria, leading to an increased risk of diseave not disposed properly. Reusable bottles, when eleaned regularly, pose lower risk.
Normal answer (ChatGPT-3.5)
Using a single-use plastic bottle has significant implications on the environment and human health.
Enviroumental implications:
1. Plastic pollution: Single-use plastic bottles are one of the major contributors to plastic pollution in oceans and landfills,
They take hundreds of years to docompose, and during that time, they release toxic chemicals and microplasties into environment.
Carbon emissions:: Manufacturing and transporting single-use plastic bottles require Nignificant amount of energy and resources, which contribute to greenhouse gus emissions and climate change.
3. Natural resource depletion: The production of single-use plastic bottls requires large amounts of water and oil, which are finite resources.
Health implications:
1. Chemical exposure: Single-use plastic bottles contain chemicals such as Bisphenol A (BPA) and phthalates, which
leach the water and pose risk human bealth.
2. Microplasties ingestion; When plastic bottles break down, they release microplastics, which can enter the food chain and he ingested humans.
Using a reusable bottle, on the other hand, has positive imguct on the environment and human health.
Envirommental henefits:
Reduced plastic waste: Reusable bottles significantly reduce the amount of plastic waste generated.
Lower carbon emissions: Reusable bottles have a lower carbon footprint as they can used multiple times.
Reduced resource depletion: The production of reusable bottles requires fewer resources than single use plastic bottles.
Health henefits:
Chemical-free: Reusable bottles are typically made from materials that are free from harmful chemicals, reducing the
risk of chemical exposure.
Reduced microplastics: Reusable bottles do not break down easily, reducing the release microplastics into cavironment.
Overall, using reusable bottle is a more sustainable and healthicr option than using a single-use plastic bottle.
(Common sense) How can you determine if a person is genuinely interested in a conver- sation or simply being polite?
Question:
SoT's answer (ChatGPTT-.55 (Orange texts are the skeleton.)
Pay atlention body language Notice if their posture open or closed, if they are facing lowards you or away, and they are fidgeting or relaxed. These can all indicate their level of interest in the conversation.
Listen ongaged responses. the person is genuinely interested the conversation, they will respond with thoughtful
and relevant comments or questions rather than short, generic responses.
3. Observe eye contact If the person maintains steady eye contact and their gaze is focused on you, they are likely conversation. On the other hand, they froquently look away seem distracted, they may
gemuinely interested
just be being polite.
Look for follow-up up questions person asks follow up questions and seems genuinely interested what you're 're saying, then they are likely interested in the conversation and not just heing polite.
5. Notice tone v person who is genuinely interested in a conversation will often have a more enthusiastic and animated tone of voice, compared someone who is simply being polite and giving short, monotone responses.
Normal answer (ChatGPT-3.5)
As an Al assistant, 1 cannot determine a person's 's true intentions or foelings, However, there are some social cues that indicate whether person genuinely interested conversation
For example, if they maintain eye contact, lean in, nod their head and ask follow-up questions, can he a sign that they are engaged in the conversation. On the other hand, they avoid eye contact, give short or vague responses, seem distracted, may indicate that they not as interested. Ultimatoly, it's important to remember that everyonc has different communication styles, and it can be difficult accurately interpeet somcone's intentions withour directly asking them.
39

---

Published as a conference paper at ICLR 2024
Question: (Generic) How can I improve my time management skills?
Ss answer (ChatGPPT-355 (Orange texts are the skeleton.)
1. Set clear goals. Sctting clear goals is important in improving time managoment skills as belps you to focus on what needs be done and what can be accomplisted within certain timeframe.
2. Prioritize tasks. Make list of tusks and prioritize them based on their importance and deadline. This will help you focus on most critical tasks avoid wasting time less important ones.
Create schedule. Creating schedule helps you allocate time for each task and ensures that you complete them
within the allotted time.
Minimize distractions, Distractions such social media, emails, and phone notifications waste a lot of time. Try to limit them by turning off notifications or setting specific times to check them.
Take breaks. TTkiing breaks can actually amprove productivity and help prevent burnout. It's imporiant schedule short breaks throughout the day to recharge and refozus.
Learn to say no It's important to prioritize your own tasks and not take too much at once, Saying no to requests that don't align with your goals schedule can help you manage your time effectively.
7. Delegate tasks. If you have too many tasks to handle, consider delegating some of them to others who can help you. This will allow you focus more important tasks manage your time more effectively.
8. Use time management tools. There are a variety of time management tools available, such as calendars, to-do lists, and productivity apps, that can help you stay organized and on track with your lasks.
Normal answer (ChatGPT-3.5)
Improving time management skills can be a challenge, but there are several strategies that can help. Here are few:
1. Set clear goals and priorities: Identify your most important tasks and make sure to complete them first.
Make schedule: Create schedule that includes your most important tasks and set aside time for them.
3. Use timer: Set a timer for a specilic amount of time help you stay locused and avoid distractions.
Take breaks: Take short breaks throughout the day to help you rechurge and avoid burnent.
5. Eliminate distractions: Try to limit distractions as much as possible, such as by tuming off your phone or closing your
email.
6. Delegate tusks: If possible, delegate lusks to otbers to free up time for more important activities.
Remember, improving time management skills takes practice and perseverance. Be patient with yourself and keep trying
until you find strutegies that work well for you.
(2) Roleplay. Roleplay questions require LLMs to assume character and present an introduction or speech to other people. LLMZoo and FastChat metrics usually favor the level of details of SoT when assigning it a better score. Similar to the writing category discussed before, SoT's answers could be even better if the skeleton points are removed from the answer.
Question: (Roleplay) How would you introduce yourself as medieval knight at royal banquet?
So answer (Claude) (Orange texts are the skeleton.)
Name and house My name is Sir Percival of Camelot, knight of the Round Table and protector King Anthur's realm.
Lands and titles. hold fiefdom over the lands of Westmarch and Ravenshire, and bear the titles Baron the Western Marches and Knight the Raven.
3. Military feats. I have led my men to great victories against the kingdom's enemies, winning many battles thruugh strength arms tactical cunning.
4. Allegiance to king. pledge my sword, my loyalty, and my life to serve and protect my noble king and this great kingdom.
5. Request to join table. Your Highness, it would he the greatest honor to join your exalted table and share in this
magnifieent feast with my fellow knights and loyal subjects.
Normal answer (Claude)
Greetings, your majesty and honored guests. am Sir Claude, knight in service of the king. hail from the province of Assistantia, where was trained in the knightly virtues of chivalry, courage and courtesy. Though am but a humble knight, I shall endeavor
you and this kingdom with all the strength and valar possess. thank you for allowing me to join you at this royal feast, and hope only that my conduct brings further honor to my liege and this noble court. Please let know I be any service during the celebrations, as would be my honor assist you any way.
1.1.3 ANSWER ANALYSIS: DIFFERENT METRICS
Metrics which SoT has low net win rates.
(1) Coherence. In the prompt of LLMZoo evaluation, coherence is defined as "The response should be coherent and flow logically from one point to the next that is easy to read and understand without major gaps or inconsistencies. The more coherent they are, the better." SoT's answer is structured in a list of points. It is suitable for some questions but not all. For example, in the questions that require
40

---

Published as a conference paper at ICLR 2024
LLMs to write passage, email, script, the introduction and conclusion paragraphs are usually missing, and the answers usually lack transition sentences between consecutive points. These make the answers less coherent. Below is one example from Claude.
Question: Write script for a YouTube video exploring the history and cultural significance of jazz.
So answer (Claude) (Orange texts are the skeleton.)
Origins. Jazz originated in the late 19th and carly 20th centuries among African Americans in New Orleans, emerging from a combination of African thy thytiii traditions, blues, ragtime, and other intluences.
Early juzz styles. The early styles of juzz that emerged the late 19th and early 20th centuries included rigtime, Dixieland, and the blues,
Jazz age. The Jazz Age the period during the 1920s when jazz music and dance styles like the Charleston became popular cultural phenomena in American and Faropean snciety.
Bebop cra. Behop emerged in the early 1940s with artists like Dizzy Gillespie and Charlic Parker experimenting with faster tempos, complex chord changes, and unpredictable melodic phrasing.
5. Cool juzz. Emerging in the late 1940s and early 1950s, cool juzz was more subdued, mellow style that broke from the high-energy virtuosic improvisation of behop.
6. Free jazz emerged in the late 1950s and 1960s as musicians explored free improvisation and atonality, moving away
from traditional jazz structures.
7. Fusion jazz. Major jazz artists such as Miles Davis and Herbie Hancock began experimenting with combining elements of rock, funk, and electronic music in the 1970s, resulting in the emergence of the subgcare known as fusion jazz.
Jazz festivals. Jazz lestivals emerged the 1950s and 1960s as way celebrate jazz music. with lamous early
festivals like the Newport Jazz, Festival bringing thousands of fans logether to hear top performets. Jazz instruments. The trumper, saxophone, piano, double hass, and drum
some of the key instrmments
monly used in jazz.
Influential musicians include Louis Armstrong. Duke Ellington. Charlie Parker, Miles Davis, John Coltrane. and many others who pioncered new styles and techniques.
11. Legacy and impact. Jazz left an indelible mark on music and culture over the past century, influencing countless artists and genres while spreading the spirit of improvisation and freedom across the globe.
Normal answer (Claude)
Here is a draft script for YouTube video exploring the history and cultural significance of jazz: Introduction
Hey everyone! Welcome to my channel. In today's is video, we're 'r going to he exploring the history and cultural impact of one America's original forms- -aaz music.
Jazz Origins
Jazz grew out of the African American communiries the southern United States the late 19th and carly 20th centuries. It was influcnced by combination of African and European musical traditions. Some key elements that fod into carty jazz included blues. ragtime, spirituals, work songs, field hollers, and bruss band music. New Orleans is considered the birthplace jazz, emerging around the turn of the 20th century. The city pot of cultures and musical styles. Musicians mixed improvisation, syncopated rhythms, hent notes and a loose ensemble playing style create new genre that became known jazz.
melting
Farly jazz greats like Buddy Bolden, Jelly Roll Morton and Sidney Bechet began fusing these various influences into the distinct jazz sound. As the music spread via travel and recordings in the 1910s, jazz captivated listeners and began to evolve into different styles.
Jazz Styles Emerge
In the 1920s, juzz expanded from New Orleans and Chicago emerged as hotspot. Louis Armstrong's 's innovative solos and expressive phrasing bocame influential. The swing style also developed during the 1930s and 40s, propelled
hy star big hands and dancers.
Rehop arose in the 1940s with soloists like Charlie Parker and Dizzy Gillespic exploring new levels of harmonic and thythmic complexity. In the 50s and 60s, jazz expanded into new fusions like cool jazz, hard bop. free jazz, modal jazz and soul jazz. Artists used jazz to express their unique regional, social and political identities
Cultural Significance
Over the decades, jazz has become like individualism, freedom, spontancity, innovation and social harmony.
into the fabric American society. equated with many values and ideals
Jazz was associated with hreaking down harriers between races, classes and genres. It represented modernism culture. Musicians like Louis Armstrong and Duke Ellington became some of the first widely popular African American artists.
Jace also spread American culture and values abroad through performances, radio and film. influenced music around the world and became a truly global art form.
Today jazz continues to thrive and evolve both in the U.S. and internationally. history and sounds reflect the diversity of both American and global cultures. From its folk roots, jazz has become a sophisticated art music that retains its spirit freedom and improvisation.
Conclusion
That covers some of the key points the history and cultural impact of jazz music. Lot me know in the comments about
your favorite jazz styles and musicians! Be sure like and subscribe. See you next time.
While the content of SoT's answer is good, it reads less fluent for the purpose of a YouTube script. (2) Immersion. In the prompt of LLMZoo evaluation, immersion is defined as "the response should act like the assigned role using the tone, manner, and vocabulary the role would use. The more assistant-like tones, the worse. The more in-character, the better." The way that SoT breaks the
41

---

Published as a conference paper at ICLR 2024
answers into list makes its answer less in-character. Therefore, SoT receives lower immersion score. Here is one example.
Question: Pretend to be a world-famous chef. How would you describe your signature dish to panel of judges?
So answer (Claude) (Orange texts are the skeleton.)
1. Main ingredient; The incredibly fresh and tender salmon caught just this morning from the crystal clear waters of the
Pacific Northwest.
2. Cooking method
I slowly braise main ingredient in a rich broth to bring out its natural flavors before searing to perfect golden crust.
3. Special seasoning
The dish is semsoned wilh blend of fresh herbs like thyme, resemary, and oregano which provides an aromatic backbone
that pairs nicely with the natural flavors of the main ingredients. add touch of smaked paprika provide subtle
smokiness without overpowering the other flavors.
outside tender inside, with each bite yiclding delightful mix of crunchy and smooth textures that dance across your tongue.
Texture: The dish has a perfect balance crispy
Plating presentation
1 purposefully create beight and dimension the plate with the carefully arranged components of the disht, that the
dish appears vibrant and alive. The interplay of colors, textures and shapes is intended to delight the eye before the first hite.
Inspiration:
This dish was inspired by my dear grandmather, who lught me the secret family recipe when was just
child.
Normal answer (Claude)
"clears throat and speaks fancy accent
Ronjour honored judges. Today I present tn signature dish- In crème de ln crème of French haute cuisine. Behold, le poulet Claude!
This succulent chicken firstly marinated overnight bath of line herbes thyme, rosemary, and sage cultivased from my private garden. The young spring chicken is then masted to perfection, its skin crisping to beautiful caramel brown. Nestled beside the chicken is tower of pommes dauphine- light and airy potato puffs alongside decadent mound of crème fraiche infused with trufflc essence.
enriched with cream butter, hrightened dash of lemon, and studded with morsels of morel mushrooms foraged at dawn.
the pièce résistance
sauce. luxurious paol
One bite of this ensemble will transport you to food heaven. The tender chicken, the creaminess of the pocato puffs, and the rich decadence of the
meld together in blissful harmony.
So tell me honored judges, will my poulet à la Claude earn your coveted approval? await your discerning verdict as swirl vintage Rordeaux into your glasses. Santé!
Again, while the answer from SoT covers sufficient aspects and details, it reads rather stiffly. The normal answer, in contrast, has the opening sentence "Bonjour honored judges. Today present to you my signature dish..." and the conclusion statement "So tell me honored judges, will my poulet à la Claude earn your coveted approval? ..." which reads more like a casual talk from a chef.
Metrics which SoT has high net win rates.
(1) Diversity. In the prompt of LLMZoo evaluation, diversity is defined as "The response should be comprehensive and provide range of information that is limited to single perspective. More perspectives are better." The skeleton stage in SoT encourages LLMs to think from multiple perspectives. Therefore, SoT's answers tend to have better diversity. Below is one example showing that SoT's s answer has better diversity.
42

---

Published as a conference paper at ICLR 2024
Question: How can you determine a person is genuincly interested in a conversation or simply being polite?
So answer (ChatGPT-3355) (Orange texts are the skeleton.)
Pay attention to body language. Notice if their posture open or closed, if they are facing towards you away, and if they are fidgeting or relaxed. These can all indicate their level of interest the conversation.
Listen for engaged responses. If the person is genuinely interested the conversation, they will respand with thoughtful and relevant comments or questions rather than short, generic responses.
Observe eye contact.f If the person maintains steady eye contact and their gaze is focused on you, they likely gemuinely interested in the conversation. On the other hand, if they frequently look away or seem distracted, they may just being polite.
Look for follow-up questions If the person asks follow-up questions and seems genuinely interested what you re saying, then they are likely interested in the conversation and not just being pulite.
Notice tone V person who genuinely interested in conversation will often have enthusiastic and animated tone of voice, compared to someone who is simply being polite and giving short, monotone responses.
Normal answer (ChatGPT-3.5)
As an AT assistans, cannot determine person's true intentions feelings, However, there some social that can indicate whether person is genuinely interested in conversation or not, For example, if they maintain eye contact, in, nod their head other hand, if they avoid eye contact, give short or vague respenses, or seem distracted, it may indicate that they are not as interested. Ultimately. important to semember that everyone has different communication styles, and it be difficult to accurately interpeet someone's intentions without directly asking them.
follow-up questions,
a sign they engaged
conversation. On
SoT answers the question from five aspects, whereas the normal answer only mentions one aspect.
(2) Relevance. In the prompt of LLMZoo evaluation, relevance is defined as "The response should be closely related to the question and answer the question accurately with sufficient details without repetition or redundancy. The more relevant they are, the better." In the skeleton stage, LLMs are forced to propose several points around the question; and in the point-expanding stage, LLMs are required to only discuss these points. Therefore, answers from SoT tend to have better relevance. One typical example is shown below.
Question:
Why do some people enjoy the sensation of being scared, such as by watching horror movies or going on roller coasters, while others avoid these experiences?
SoT's answer (ChatGPT-3.5) (Orange texts are the skeleton.)
Neurological differences Some people enjoy the sensation of being scared due to the release of adrenaline and
dopamine in the brain, while others may have a lower threshold for fear due to differences in their amygdala and pre-
frontal cartex.
2. Psychological factors, Some people may enjoy the sensation of being scared because it can provide sense of excite- ment, thrill, and temporary escupe from the mundane aspects of everyday life. the other hand, others may avoid these experiences due to past trauma or anxicty.
Sonee
Developmental experiences Individuals who had negative experiences with fear during childhood, such as trauma
abuse, may avoid scary situations adults, while those who had posilive experiences with fear may seek out these experiences.
Cultural influences Some cultures place greater emphasis seeking excitement and thrill, while others may priori- tize safety and sccurity, which can impact whether individuals eajoy scary expericnces or avoid them.
Genetics Revearch has suggested that some individuls may have a genetic predispunition lowards seeking out thrillng or risky experiences, which may include enjoying the sensation of being scared.
Normal answer (ChatGPT-3.5)
enjoyment of being scared complex psychological phenomenon. Some people may enjoy the adrenaline rush that comes with being seared, while others may enjoy the feeling of being ablc to conquer their fears. Additionally, some people may be more naturally inclined to seek out new experiences sensations, including those that are scary thiiling. On the other hand,
people may more risk-averse may have had negative experiences with fear or anxiety in the past, which could make them more likely to avoid seary experiences. Ultimately, the reasons why some people enjoy heing scared while others do not likely to influenced by mage of factors, including personality, past experiences, and individual preferences.
In the answer from the normal generation, the first two sentences provide little information in an- swering the question, and the last sentence only gives keywords such as "personality, past expe- riences, and individual preferences" without providing concrete explanations to each. In contrast,
43

---

Published as a conference paper at ICLR 2024
SoT's answer is well structurdd into five reasons with sufficient explanations and does not waste space in irrelevant contents.
1.1.4 QUALITY BREAKDOWN: QUESTION CATEGORIES AND MODELS
In the main text, we analyze how question categories and models affect SoT's answer quality. Here, Fig. 22 show the per-model and per-category results.
100%
coding
199
2096
31%
6%
100%)
X1%
2012
69%
XT%
-99%
160%)
75%
math
48%
47%
41%
4.mh
122h
4.7%
-.th
-80
0377%
50%
roleplay
45%
30%
-3%
30%
10%
50%
42%
10%
EN
-0%
10%
385
25%
writing
0%
knowledge
66/6
38%
05%
-25%
generic
14%
.00%
43%
.10%
0011
-106
50%
40%
38%
50%
40%
50%
counterfactual
common-sense
2096
4.9
77%
70h
975
70%
Average
-2%%
-26
-006
-25%
-235
11%%
48%
-100%
Avgerage LLRAAA Gat-
LLAMAZ Chat 138
Gat-78
Ogenn 238 Stabie
138
Claude Chatoi
3.5
GPT.4
Vicung
Vicunn
Vicuna
Vicunar
Ultral
Figure 22: Net win rates different models and question categories. Each row corresponds one question category, and one column corresponds one model. (Evaluated using metric defined by the FastChat prompt, and GPT-4 as the judge.)
1.2 SKELETON-OF-
WITH ROUTER
Fig. 23 shows net win rates of SoT on Vicuma-80 dataset with LLMZoo metrics, and Fig. 24 shows net win rates of SoT on WizardLM dataset with FastChat metrics. The key takeaways are: (1) In both cases, SoT-R achieves similar better quality than SoT, and the net win rates of SoT-R usually non-negative. This indicates that SoT--R falls back to normal decoding on the right question categories. (2) On the WizardLM dataset,
that the trained router has better performance than the prompting router in most cases. This is reasonable, as the prompting router is limited by the capability of GPT-4, whereas the trained router is dedicated this task. (3) Sometimes, routers can even achieve better performance than humans.
Fig. 1(b) in the main text has showed SoT's quality and speed-up plot evaluated with the FastChat quality metric, here, Fig. 25 shows the results evaluated with the LLMZoo quality metric.
writing
SoT router)
ferm
Sel & wi prompting router
roleplay
SoT wi human router
krowledge
comminn
generic-
counterfactual
.20%
20%
Figure 23: Net win rates of SoT and SoT-R different question categories of Vicuna-80 dataset using the general quality metric from LLMZoo. Blue dots are from Fig. 5b. SoT-R correctly falls back normal decoding questions where SoT is not suitable.
44

---

Published as a conference paper at ICLR 2024
Code Debug
Complex Format
Mukilingusl
Entertainment
Medicine
Wriling
Math
Chemistry
Computer
TruthfuiGA
Lay
Blolody
Physics
Roleplay
Sport
Music
router)
Ethics
SoT-R wi prompting router
Counterfactual
SOT.R wi trained router
human router
-60%
40%
-20%
20%
40%
Figure 24: Net win rates of SoT and SoT-R on different question categories of WizardI.M dataset using the general quality metric from FastChat. SoT-R correctly falls back to normal decoding on questions where SoT not suitable.
sqbovicuns-13 138
Vicuna-138 V1.3
0.4
GPT-4
Net win rates
U33
0.2
ChatGPT-3.5
Vicuna:78 V1.3
Vicuna-338 v1.3"
Baseline
LaaMA2-Chst-7
0.0
OpenChat-138
Claude
LLaNk2-Cha
0.2
Vicuna-78 v1.1
1.0
1.2
1.4
1.6
1.8
Speed-up
Figure 25: The net win rates and speed-ups of SoT with router (SoT-R) compared to normal gener- ation on Vicuna-80. The net win rate is the difference between the fraction of questions that SoT-R has better and worse answers than normal generation. The speed-up is the ratio between the latency of normal and SoT-R generation. (1.0, 0.0) represents normal generation. Higher better on both axes. For most models, SoT-R not only accelerates the generation but also improves the quality of the answers (evaluated with LLMZoo metric (Chen et al., 2023c)).
45

---

Published as a conference paper at ICLR 2024
SoT vs. Normal Long
vs. Normal
19-55%
1%
0%
20%
40%
60%
100%
(a) ChaiGPT-3.5.
SoT Normal Long 2m
SoT Normal
21.6%
75.7%
0%
20%
40%
60%
80%
100%
(b) L.LaMA2-Chat-7B
Figure 26: Win/tic/lose rates of SoT v.s. longer normal generation. Evaluated only on the questions that we manually label as being suitable for SoT. Evaluated using "general" metrics from FastChat and LLMZoo.
2.0
response length ratio
resgonse length ralio
2.0
1.5
1.0
0.5
SoT/Noomal
SOT/Nommal Long
SoT/Normal
So SoT/Mommal Long
(a) ChaiGPT-3.5.
(b) LLaMA2-Chat
Figure 27: Length ratios of SoT generated answer normal generated answer. "Normal" refers to the normal generation using solely the request as the prompt: "Normal Long" refers to the normal generation using the additional "... give long answer..." instruction in the prompt.
1.3 QUALITY COMPARISON LONGER NORMAL ANSWER
When assessing the answer quality, the GPT-4 judge might exhibit bias towards longer responses. To take this factor into consideration, we add comparison between longer sequentially generated answer and the SoT generated answer. Specifically, we add a instruction prefix to the prompt for normal generation. The prefix is "Please give slightly long answer for the following question." and "Please give a long answer for the following question." for ChatGPT-3.5 and LLaMA2-Chat 7B, respectively. Fig. 27 shows the ratios of the length of SoT answers normal answers, and Fig. 26 shows the quality comparison. We can see that for both models, when the overall answer lengths similar, the quality of the SoT answer comparable that of the long normal answer.
1.4 CHATGPT-3.5 AS THE JUDGE
In this section, we provide quality evaluation results with ChatGPT-3.5 as the judge in FastChat and LLMZoo metrics. Note that as prior work (e.g.. (Li et al., 2023b)) shows, GPT-4-based evaluation usually aligns with human better than ChatGPT-3.5. Therefore, readers should refer to the results in the main paper (with GPT-4 as the judge) for a more accurate view of the performance of SOT. However, the takeaway messages from ChatGPT:3.5 are similar the ones from GPT-4.
46

---

Published as a conference paper at ICLR 2024
1.4.1 OVERALL QUALITY
Fig. 28, we show win/tie/lose rates (the percentage the cases when SoT wins/ties/loses compared to normal generation) across all models and questions using the two metrics from FastChat and LLMZoo that capture the general quality of the answers. We notice a discrepancy between the two metrics when SoT is strictly better than the baseline (50.2% v.s. 12.4%). Despite that, the two metrics agree that SoT' is not worse than the baseline in more than 76% of the cases. For FastChat metric, we also show the rates excluding math and coding questions that SoT is not suitable for (see $ 3.2.3); SoT is not worse than the baseline in more than 89% of the cases. This result suggests that the answers of SoT maintain good quality.
General quality (FastChat)
General quality (FastChat)
(excluding math coding)
General quality (LLMZoo)
0%
20%
100%
Figure 28: Win/tie/lose rates of SoT v.s. normal generation using "general" metrics from FastChat and LLMZoo. SoT performs better than or equal to normal generation around 80% of cases. (Evaluated using ChatGPT-3.5 as the judge.)
1.4.2 QUALITY BREAKDOWN: QUESTION CATEGORIES
Next, we investigate how SoT performs on different question categories. We compute net win rates (win rates minus lose rates) across all question categories in Fig. 29. Similar Fig. 28, that ILMZoo tends to be more optimistic about the quality SoT than FastChat. Nevertheless, the conclusions consistent: SoTT performs relatively well generic, common-sense, knowledge, roleplay, and counterfactual. SoT performs relatively badly on writing, fermi, math, and coding.
coding
writing
math
femi
witing
ferm
co comman-sanse
knowledge
knowledge
roleplay
counterfactual
counterfactuel
60% 50%% .40%
-30%
-20%
-10%
0%
105
20%
10%
20%
30%
40%
(a) Metric: general quality (FastChat).
(b) Metric: general quality (LLMZoo).
Figure 29: Net win rates of SoT different question categories. (Evaluated using ChatGPT-3.5 as the judge.)
I.4.3 QUALITY BREAKDOWN: MODELS
Next, investigate how SoT performs on different models. We compute win rates across all models in Fig. 30. Again, we see that the two general metrics from FastChat and LLMZoo have different absolute values but similar rankings. In particular, both metrics agree that OpenChat- 13B, Vicuna-7B V1.1, Claude, ChatGPT-3.5 have low net win rates, whereas Vicuna-13B V1.3, StableVicuna-1391 13B, and U-133I have high net win rates.
1.4.4 QUALITY BREAKDOWN: QUESTION CATEGORIES AND MODELS
In the main text, analyze how question categories and models affect SoT's answer quality. Here, we show the per-model and per-category results. For each model and question category, we compute the net win rates. The results in Fig. 31.
47

---

Published as a conference paper at ICLR 2024
VI
Calde
ChatcP1
Veuneera VI
Veucie Vi
LaMkz hat/
Vinun-338 336
stablevicuss
uitroLM 138
Stablevicush Vicuna-138
uitaLk
Vicuna-13B
-10%
10%
(a) Metric: general quality (FastChat).
(b) Metric: general quality (LLMZoo).
Figure Net win rates of SoT on different models. (Evaluated using ChatGPT-3.5 as the judge.)
1074
100%
75%
fem
50%
term
50%
25%
Ar0le
wrlbln
0%
trowldiee
krondolge
generic
-3%
generic
ountefacttal
-0%%
counterfactuu
50%
-2%
Average
Avarage
100%
100%
(a) FastChat metric.
(b) The "general" metric from LLMZoo.
Figure 31: Net win rates of different models and question categories. Each row corresponds to one question category, and one column corresponds one model. (Evaluated using ChatGPT-3.5 as the judge.)
I.4.5 QUALITY BREAKDOWN: METRICS
All previous evaluations metrics about the general quality of the answer. In Fig. 32, show more detailed metrics from LLMZoo to reveal in which aspects SoT can improve or hurt the answer quality. On average, immersion and coherence.
that SoT improves the diversity and relevance while hurting the
Win
Tie
Lose
Diversity
49.4%
29.0%
21.5%
Relevance
50
21.0%
28.2%
Integrity
Immersion 7%.7%
Coherence 28.3%
31.4%
40.2%
0%
20%
40%
60%
80%
100%
Figure 32: Win/tie/lose rates of SoT normal generations using metrics from LLMZoo. SoT per- forms well on diversity and relevance, and relatively worse on coherence and immersion. (Evaluated using ChatGPT-3.5 the judge.)
J COMBINING SOT-R WITH MODEL QUANTIZATION
Model quantization a widely-used model-level optimization to accelerate LLM inference, which orthogonal to SoT. In this section, evaluate the speed-ups of open-source models with both
48

---

Published as a conference paper at ICLR 2024
quantization and SoT the Vicuna-80 dataset. Specifically, adopt GPTQ (Frantar et al., 2022) to apply 4-bit weight-only quantization and use SoT-R instead plain SoT.
J.1 SPEED-UPS OF SOT + QUANTIZATION ON QUANTIZED MODELS
We first compare the latency of the quantized models in the normal and SoT modes to evaluate how much SoT can speed up quantized models. Fig. 33 shows the speed-ups of SoT-R different quantized models. SoT-R obtain 1.08x to 1.99x speed-ups on all the models. Fig. 34 shows the speed-ups of SoT-R on different categories. We can that on the five question categories for which SoT can provide high-quality answers (i.e., knowledge, generic, common-sense,, roleplay, counterfactual) SoT-R can speed up the overall answer generation process by 1.07 2.38x.
LLMMA2-Chat-138
1.95k
LLMMA2-Chat-18
1.99x
Vicum-3338 v1.3
1.91x
Vicune-330 v1.3
1.80x
LLaM62-Chat-78
1.68x
ILaMA2-Chat-78
OpenChat-138
1.40%
OpenChat-130
1.51x
Vicuna 13B V1.3
1.24x
Vicuna 78 v1.3
1.30x
Vicuna v1.3
Vicuna 78
Vccua-78
1.20x
Vicuna-138
1.25x
Ultral M-138
1.08x
Ultral M-1 38
1.09
1.4
1.6
2.0
2.2
1.2
1.8
2.0
(a) SoT-R with the prompting router.
(b) SoT-R with the trained router.
Figure 33: Speed-ups of the quantized model with SoT-R generation w.r.t. the quantized model with normal generation on different models, on the Vicuna-80 dataset.
generic
2.18x
generic
2.38x
knowledge
2.06x
counterfactual
counterfactual
knowledge
2.05x
femi
1.00x
coding
0.87x
1.00
1.25
1.50
175 2.00 2.5
2.50
2.75
3.00
1.00 1.50 175 2.00
2.25
2.50
2.5
3.00
(a) SoT-R with the prompting router.
SoT-R with the trained router.
Figure 34: Speed-ups of the quantized model with SoT-R generation w.r.t. the quantized model with normal generation, on different question categories of the Vicuna-80 dataset.
J.2 SPEED-UPS OF SOT QUANTIZATION ON UNQUANTIZED MODELS
Here, report the overall speed-ups of the quantization model with SoT-R generation w.r.t. the unquantized model with normal generation. Fig. 35 shows the speed-ups of SoT-R on different models. SoT-R can obtain 1.54x to 2.07x speed-ups. Fig. 36 shows the speed-ups of SoT-R on different categories. On the five question categories for which SoT can provide high-quality answers (i.e., knowledge, generic, common-sense, roleplay, counterfuctual), SoT-R can speed up the generation by 1.33 x to 3.41 x with the prompting and trained routers.
49

---

Published as a conference paper at ICLR 2024
Vicuna788 v1.3
1.95
OpenChat-1 38
2.07x
LaNA2-Chat-138
Vicuna-78 v1.3
1.98x
OpenChat-130
1.90k
192
LhatA2-Chat
884
LLaMA2 Chat
1.91x
UltraLM 138
1.8 1,82x
LLaMt2- Chan2-Chat-P2 78
1.91x
Vicuna 78
Vicuna 78 V1.1
Weuna-1 VI.3
1.63%
Vicuna11 v1.3
1.64x
Mcuna-338 V1.3
59H
Micua-338 V1.3
1.54x
(a) SoT-R with the prompting router.
(b) SoT-R with the trained router.
Figure 35: Speed-ups of the quantized model with SoT-R generation w.r.t. the unquantized model with normal generation, on different models, on the Vicuna-80 dataset.
generic
3,07
genetc
3.41x
common-sense
2.76x
common- sense
2.82x
knovledge
2,533x
knovledge
2.45x
counterfactual
2.36%
counterfactual
2.42x
rolepla
1..33x
ralepla
1.49k
writing
1. 1.18x
coding
1 1,00x
fermi
1.05x
fermi
1 1,00x
coding
0 0.96x
wrtting
1000x
math
math
1.00x
1.5
(a) SoT-R with the prompting router.
(b) SoT-R with the trained router.
Figure 36: Speed-ups of the quantized model with SoT-R generation w.r.. the unquantized model with normal generation, different question categories of the Vicuna-80 dataset.
K ADDITIONAL SOT-R STATISTICS
K.1 NUMBER OF SUITABLE QUESTIONS
Overall, there are 37/80, 58/218, 371/1030 questions that are suitable for SoT the Vicuna-80, WizardLM, and LIMA datasets (according human assessment), respectively.
Fig. 37 shows the number questions that are suitable for SoT on Vicuna-80. On counterfactual, commen- sense, knowledge, generic categories, most questions suitable for SoT based the human assessment. The trained router and prompting router give out similar judgments.
Trained Prompting muter Human
writing
counterfactual
teml
commmon-sense
roleplay
knowledge
generic
Figure 37: Number of questions suitable for SoT on the Vicuna-80 dataset.
K.2 PEAK MEMORY OVERHEAD
Fig. 38 and Fig. 39 show the peak memory overhead of SoT-R (with prompting router) on different models and different categories, respectively, on the Vicuna-80 dataset. We can see that, on all models and categories, the overhead of peak memory is quite small (<1.11x).
50

---

Published as a conference paper at ICLR 2024
StableVicuna 138
Vouna-73 v1.
UttraM6-138
11.03x
108KK
Normal (orefill)
SaT (profill)
Stabiekicuna-13B
Vicune-72
UttraMM-138 138
-1.04x
.107
106
Normal (decoce)
SoT (decode)
Viture-338 V1.1
11,0Xx
Vicuna-S38 V1
1.04
Vicune 123 V1.3
11 11.03x
Vicuna V1.
11 1.06x
Vcuun-7a V1.3
1. 02x
Vicuna788 73 V1.
+1.05x
OpanChat-138
11, x2X
OpenChat-138
044
UaMAz-Chat-132
1.002x
LLaMAZ Chat-138
11.04X
LLaMA2-Chat-70
20
40
80
20
40
60
Peak memory
memory (GIB)
(a) Peak memory in the prefilling phase.
(b) Peak memory in the decoding phase.
Figure 38: Peak memory overhead of SoT-R on different models on the Vicuna-80 dataset.
writing
coding
math
1.00x
1.00x
1.01x
Normal (prefilli
wittnn
cocing
math
1.00x
1.01
1.00x
Normal (decode)
(decode)
counterfactual
41. 11.04X
counterfactual
-1. -1,10x
fermi
1.01x
fermi
1.02*
common--sense
*1 x
common-sense
-1 1.10x
releplay
1. 001x
roleplay
.003x
knowledge
#1. 044
knowledge
1. 1.09%
generic
1.055
generii
1.11x
10
20
30
40
50
70
80
10
20
30
50
60
70
Peak memory (G10)
Peak memory (GID)
(a) Peak memory in the prefilling phase.
(b) Peak memory in the decoding phase.
Figure 39: Peak memory overhead of SoT-R on different question categories of Vicuna-80.
K.3 SPEED-UPS WITH DIFFERENT NUMBER OF POINTS
Fig. 40 shows the speed-ups with different numbers of points Vicuna-80. To maintain clarity in the figure, we've chosen to display statistics for only three models. Note that as SoT cannot control the overall length to be the same as that of normal generation, it is not the case that a higher number of points leads to higher speed-ups.
3.5
LLaMAR Chat-78
M-1
GPT-4
2.5-
2.0
1.5-
0.5
8.0
10
11
Number of Paints
Figure 40: The speed-ups with different number of points on the Vicuna-80 dataset.
L NOTES ON APPLICATION SCENARIOS
In a chatbot application, one might wonder why a reduced end-to-end latency can enhance the user experience. While human reading speeds are limited, there are many situations where we do not read responses sequentially. Rather than reading the entire answer, one might prefer to (1) swiftly check the response's 's structure to confirm if the chatbot comprehended the question or (2) extract specific information rapidly without waiting for the generation of prologue or preceding points. Besides, from the quality aspect, even if we would like to check the entire answer, well-defined structure in responses assists us in quickly parsing all the information.
Moreover, beyond enhancing user experience, reduced end-to-end latency significantly benefit emerging application scenarios like agent-agent interaction.
51


Reviews:
[{"review_id": "G2ECf92RPV", "reviewer": "Reviewer_vbj6", "summary": "This paper presents a very simple method for reducing the inference latency of LLM. Given a query, the LLM first generates a list of key points, referred to as the \"skeleton\" in this study. Subsequently, each point is elaborated in parallel via separate LLM executions. The simultaneous execution of these runs reduces the overall inference latency.", "questions": "n/a", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- This paper is extremely well-written.", "weaknesses": "- The core idea is quite straightforward: first list the key points, then elaborate each point. I am afraid that similar ideas have been extensively studied in the literature of NLP (if the authors search hierarchical text generation or planning for text generation or long text generation). Yet this paper gives no discussion. Below I list several references [1][2] (but clearly not sufficient).\n- The proposed method only makes sense when the answer is long, decomposable into several key points, and the interdependence of these key points is low (because the writing of each point only sees the skeleton). \n- As a result, the proposed method inevitably hurts the overall coherence of the answer. The experiments in this paper also confirm that the proposed method hurts the immersion and coherence judged by GPT4 (Section 3.2.4).\n-  All evaluation is conducted by GPT4 or ChatGPT-3.5. The results could be biased or misleading, human evaluation is required.\n\n[1] A Hierarchical Neural Autoencoder for Paragraphs and Documents (ACL15)\n\n[2] Long and Diverse Text Generation with Planning-based Hierarchical Variational Model (EMNLP19)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "H09RWS1v82", "reviewer": "Reviewer_KKRk", "summary": "This paper focuses on the high generation latency of LLM and explores utilizing COT to generate a skeleton of the answer, and then continue to generate the remaining answer parallelly for inference efficiency.", "questions": "1. In a particular training dataset, how many examples can be used with SoT?\n2. How does SoT perform in other general datasets?\n3. Is there anything wrong with the content generated this way? Such as repeating generation or generating blank.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Speed up the process of generation", "weaknesses": "1. There are requirements for tasks, and multiple points of tasks must be able to be generated at ordinary times without affecting each other.\n2. This method of generation may compromise the quality of the results generated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "FsIZHo2R6j", "reviewer": "Reviewer_ieuZ", "summary": "This paper proposes a parallelization for answering questions with large language models. The core idea is to formulate the answer as a list of points (the skeleton), and then elaborate each of them independently with parallel model calls. This is limited to answering a type of questions for which such independent elaborations of a list of points are suitable. The decision whether a question is suitable can be passed to a router, which is an extension that the paper proposes. The parallelization brings about a speedup compared to sequential decoding, and the authors argue that this also mimics the way that humans think.\nThe method is evaluated for 12 different LLMs on FastChat and LLMZoo, and the results are discussed under various perspectives.\n\nScore was raised after author response.", "questions": "- How would Figure 1b look like for the LLMZoo evaluation? This kind of plot is answering the question for the speed-quality trade-off at one glance, so it would be great to have as well for LLMZoo. It looks like the model with the largest wins (StableVicuna-13B) also has the lowest speed-up for LLMZoo (3.2.2), so it would be nice to see if this is a trend more than for FastChat.\n- I do not think that Figure 3 is very expressive, as it is an accumulated result across all models, which in turn (3.2.2) vary largely. Perhaps this could be replaced with a deeper analysis of the loss cases? This would allow the reader to get a better idea of the potential risks.\n- The method reminds me of the map-reduce paradigm, but the reduce step is a simple concatenation rather than a joint processing of the whole list of answers. How much would a final “summarize” decoding step add to the quality and remove from the efficiency? I could imagine this increasing the coherence of the answers.\n- For 4.3.1 the most relevant question seems to be which ratio of questions the router decides to process with skeleton-of-thought. This directly affects efficiency, since speedups can only possibly be obtained if the skeleton-of-thought route is chosen. Quality and efficiency both seem to be a predictable combination of normal decoding and skeleton-of-thought decoding quality and efficiency once the ratio is known. It would be interesting to report this ratio by category in order to evaluate if it agrees with the categories that were identified to work well for skeleton-of-thought in 3.1.2.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- It’s a good idea and well executed. It will probably inspire future works, as there are a few ideas that could easily extend the proposed method, e.g. for improving coherence of the elaborated points.\n- For some models there are efficiency AND quality improvements, which is very attractive for practical adoption in the cases where questions fall into the categories that are suitable for the method.\n- The proposed methods are widely evaluated, covering multiple LLMs and benchmarks. Especially having a large number of LLMs tested is helpful for gaining insights into variability and sensitivity of the models and setting expectations for applying the method to other models. There’s also a large number of analyses and more results in the appendices, which overall give the impression that the authors have profoundly studied the effectiveness of their method.", "weaknesses": "- The comparison with human thinking is merely intuitive and not founded by any references, hence speculation. I do not think this makes the method any more attractive, and would prefer to see a discussion with scientific evidence, if this should be a benefit of this method. It is clear that the inspiration comes from how humans draft a text or the like - but this does not result in humans and LLMs functioning in the same way. The phrasing that LLMs are made “thinking in the same way” just adds fuel to the pseudoscientific discussions around whether LLMs are “thinking” or not (especially the phrase “pushing LLMs to think more like a human”). In addition, there is no connection between the argument of efficiency and human thinking - is it for efficiency that humans derive a skeleton first?\nMissing comparison to previous orthogonal methods proposed for speedups: Where on Figure 1b would they be located? This is necessary to understand the impact of this work in context of the previously proposed and adopted solutions.\n- The title is misleading and alludes to a new ability of LLMs (“LLMs can do”): The actual LLM decoding process is technically still sequential and there is no modification to the LLMs decoding loop (not to be confused with non-autoregressive methods), it’s just that the model is prompted to provide a decomposable answer to be elaborated in parallel. A more concise (but probably not great for selling the paper) reformulation of the title would be “LLMs can be prompted to provide decomposable answers”.\n- The limitations of the method are not clearly articulated in the introduction: until Section 3 it is not clear that this method is limited to specific types of questions and that there is prompt-specific sensitivity. It might be obvious to the authors, but for positioning the paper in the right scope, this should be mentioned in the introduction.\n- An analysis of the effect of added length is missing: Since skeleton-of-thought prompting produces longer answers than the usual prompting (3.1.1), there might be a bias of certain evaluations to prefer more wordy answers even if they have the same contents. Similarly, it remains an open question how the length part (“3-5 words”/”3-10 points”/… see prompt examples) of the prompt should be optimally configured.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "SRyjgRWvt0", "reviewer": "Reviewer_JQY3", "summary": "This paper is about a prompt-based approach to speeding up inference of LLMs.\nThe work tries to address the problem by generating \"skeleton,\" which is a set of simple answer sketches, and then based on the skeleton, a model generates answers in parallel.\nThe main motivation of this generation procedure is that, even if the resulting answer is the same (i.e. the same answer with the naive sequential generation), since applying attention over all previously generated tokens takes a lot of time and accelerator memory (quadratic to the context length), it may be beneficial to split answers into multiple pieces each of which can be generated in parallel.\nEach skeleton point is generated via an LLM, and the actual generation process from each skeleton point is done by calling generation queries in parallel (in the case of models that can only be accessed via API) or by batching multiple prompts.\nFrom evaluation, it is empirically proven that the suggested algorithm speeds up generation speed of various models, from 1.13x to 2.39x, across multiple question domains.\nTo address the issue that the suggested SoT algorithm cannot perform step-by-step generation e.g. chain-of-thought, the authors add LLM or trained model called router to determine whether or not to use SoT, namely SoT-R. Nonetheless of its simple architecture, the router module reduced failure cases where SoT underperforms normal sequential generation, in exchange of reduced speedup.", "questions": "- As mentioned in above, as far as I understood this algorithm may use more resource than normal sequential generation. Do you have numbers about overall resource time used for a single generation? i.e. for API-based experiments it would be (skeleton generation time + sum of all parallel execution times) and for batch-based experiments it would be (skeleton generation time + (batch generation time * sequences per minibtach * number of minibatches) ).\n- For router experiments, do you have numbers about the ratio of each instance being classified as \"capable of being generated via SoT\"? For example in Figure 7, StableVicuna-13B with SoT-R experiments achieved ~1.0x speedup, which means that most of them would be generated via normal sequential generation.\n- Is naturalness of generated text included in metrics of automatic quality evaluation? The prompt used feels not very natural for me; since as far as I understood each sentence should be always start the \"skeleton point,\" according to Prompt 2 (\"... do not continue with other points! [Assistant:] {point index}. {point skeleton}\")", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Good empirical motivation: sentences of generated text may be independent to each other and thus the generation can be done in parallel.\n- Good use of LLM prompts: generating skeletons, (some) routing models, and actually generate text from skeleton with small disruption", "weaknesses": "- The content relies too much on supplementary materials. The manuscript is preferred to be self-contained.\n- Overall, throughput given a fixed amount of compute resource may decrease, due to additional overheads due to skeleton generation and repeated prompts in each parallel generation prompt, since each of which will consume resource even if they are done in parallel.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "PFGFO2c0lU", "reviewer": "Reviewer_4Trv", "summary": "In this work, the authors propose a two-stage generation framework, utilizing an abstraction-generation paradigm for parallel generation, aiming to enhance the generation speed and efficiency of large-scale models. The SoT method demonstrates significant speed-ups across 12 Large Language Models, however, it appears to underperform in tasks such as code generation.", "questions": "see weakness 3", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written and easy to follow.\n2. The idea is simple and neat, and it is effective at some specific tasks, e.g., knowledge and role play.\n3. The authors conducted extensive and detailed comparative experiments on different models, datasets, and tasks. Moreover, they did not conceal tasks where the performance was poor, such as coding. I think this is highly commendable.", "weaknesses": "1. The main contribution of this paper is on the experiments part rather than the idea. In other words, the idea of this article is not insightful because it is very straightforward. Although I believe that skeleton can be generated in different ways, such as through a tree, rather than directly prompting the LLM.\n2. If the purpose of this paper is acceleration, then SoT is not universally applicable. The experiments in the article demonstrate it can lead to a decline in the quality of tasks such as code generation. More importantly, because the length (autoregressive steps) of each point the LLM needs to generate varies, the actual acceleration ratio in online-serving may differ from the test scenarios presented in the article, e.g., batch size=1 or batch size > 1\n3. I  personally doubt how much parallel generation of n points (i.e., SoT) actually enhances the user experience. \nConsidering that people read from left to right, generating n points in parallel may not significantly improve the reading experience for users. Instead, we should consider how to accelerate the generation speed of each point. As long as this speed is slightly faster than human reading speed, users might not perceive generation speed as a significant issue, because they also need time to understand the information from the LLM.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Y7L505shZe", "reviewer": "Reviewer_N4tW", "summary": "This paper proposes a method for speeding up LLM decoding that is typically performed sequentially using a two-step procedure: a) generating the skeleton of the reply (e.g. bullet points) b) expanding the bullet points in parallel through batching or parallel API calls using separate prompts.  Experiments show that this approach can speed up decoding by up to 2.39x and improve the quality of answers in about half the prompt categories & models that they considered based on Fastchat and LLM zoo evaluation. In addition, they propose a backoff strategy that allows to combine the best of sequential decoding and the proposed procedure which leads to better quality overall albeit at the expense of lower decoding speed of up to about 1.8x.", "questions": "- From 3.1.1, it is not entirely clear what is the overhead in terms of memory and or latency introduced by the additional prompting required especially for replies that require expansion of many bullet points with and without preflls. Can the authors quantify this? It would show a more clear picture of the tradeoffs involved. \n- What is the speed up of the proposed method for different prompt sizes, especially the large ones? It would be useful to show the  improvement for replies that require an increasing number of bullet points to answer. \n- In hybrid model case, do you take into account the time required to query the LLM on whether to employ SoT or not? It would be useful to show if it introduces overhead and to what extent. \n- Have you tried prompting the model to generate arbitrary partial answer segments other than bullet points to perform continuations on them in parallel? That could potentially make the method applicable beyond answers that require specific bullet point structure.\n-  For the quality results in section 3.2.1, what is the average absolute scores achieved per category and across all categories overall when showing quality per model?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The problem of decoding in parallel is important and worth pursuing with the widespread use of LLMs. In terms of originality, the idea of sketching the reply before generating continuations in parallel is simple and intuitive and a good implementation could have a significant positive impact in the community.\n- In terms of exposition and execution, the method is described clearly and the experimentation is thorough as it covers a large number of models & settings. \n- Results show that the proposed hybrid method with the backoff strategy to sequential decoding can increase decoding speed by up to 1.80x and improve the quality of the continuations for certain categories (common-sense, generic, counterfactual).", "weaknesses": "1. One key weakness of the proposed decoding method is that the generations happen for different bullet points of a reply are independent from each other, limiting its use to answers that require chain-of-thoughts. Hence, it is applicable to specific type of replies and is sensitive to the instruction following abilities of the model that is being applied to, which limits its generality. \n2. The proposed method requires prompting the model with a large number of additional tokens to generate continuations for each different bullet point per reply; the number of tokens increases linearly with the number of bullet points. This has both memory/inference cost and latency implications that are not clearly exposed when discussing the main results.\n3. When the method is applied without the backoff strategy its quality benefit is not very clear as the improvement is observed in about half the models and categories according to FastChat and LLMZoo evaluations combined.\n4. There is no direct comparison to alternative methods that have been proposed for speeding up decoding in autoregressive models such as quantization, batch inference, and speculative decoding. For instance, a simple baseline would be to perform quantization and then apply multi-stage prompting to improve quality for certain categories.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (poster)