Skeleton-of-Thought: How Parallel Prompting Cuts LLM Latency Up to 2.39x

Every token a language model outputs depends on every token that came before it. This sequential dependency is not a design flaw; it is the fundamental mechanism by which autoregressive transformers work. But it creates a practical problem: no matter how many GPUs you have or how fast your network is, generating a 500-token answer requires 500 serial decoding steps. Each step loads the full model weights from memory, computes one token, and appends it to the context before the next step can begin. For long responses, the wall-clock latency of this process becomes a genuine bottleneck in user-facing products. Skeleton-of-Thought (SoT), published at ICLR 2024, attacks this bottleneck from an unusual angle: instead of changing the model or the hardware, it changes the structure of the output.

The paper and its authors

Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation was submitted to arXiv on July 28, 2023 (arXiv:2307.15337) and accepted at ICLR 2024. The authors are Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang, and Yu Wang. Ning, Zhou, Yang, and Yu Wang are affiliated with the Department of Electronic Engineering at Tsinghua University. Lin was at Microsoft Research in Redmond at the time of publication, and Zifu Wang was at KU Leuven in Belgium. The paper frames SoT as a data-centric optimization: the technique works through prompting and output structure rather than through model architecture or serving infrastructure changes.

Why sequential decoding is the bottleneck

The paper identifies two phases in a typical LLM inference pass. The prefilling phase takes the input prompt and produces the key-value cache and the first output token. The decoding phase then generates each subsequent token one at a time, updating the KV cache at each step. The core inefficiency is in decoding: generating a single token requires loading every model weight from GPU memory to produce just one output value, which means the memory bandwidth of the GPU is almost fully consumed by weight loading rather than by actual compute. The authors measured this directly on LLaMA models on an NVIDIA A100 GPU at batch size 1. For LLaMA-7B, prefilling 128 tokens took about 40 milliseconds while decoding a single token took about 43 milliseconds. For LLaMA-13B the corresponding figures were 54 and 58 milliseconds. The decode latency is nearly equal to the prefill latency for a single token, which means that a 200-token response requires roughly 200 individual weight-loading passes, each almost as expensive as reading the entire prompt.

Approaches to this problem typically fall into three categories: model compression (quantization, pruning), speculative decoding, and serving-side batching. SoT introduces a fourth category: restructuring the output so that multiple independent segments can be generated in separate parallel calls rather than in a single sequential stream.

The two-phase SoT pipeline

SoT works in two stages. In the skeleton stage, the model receives a prompt instructing it to produce a brief, structured outline of its answer. The skeleton prompt asks the model to generate a numbered list of the main points it will cover, without expanding on any of them. The output is a short list of concise point labels, typically a few words each. In the point-expansion stage, the model is called once per skeleton point (or multiple points can be batched together) with a prompt asking it to elaborate on that specific point. Because the skeleton points are largely independent of each other at the content level, these expansion calls can be issued in parallel. With a multi-threaded API client, all expansion calls go out simultaneously, and the final response is assembled by concatenating the expanded points in the order they appeared in the skeleton.

• Skeleton stage: one short call produces a numbered outline of the answer. The skeleton itself is typically 20 to 60 tokens.
• Expansion stage: one API call per skeleton point, all issued in parallel. Each call generates the full content for that point independently.
• Assembly: the expanded points are joined in order. The total wall-clock time is the skeleton call plus the longest single expansion call, not the sum of all expansion calls.
• No model changes required: SoT is entirely prompt-driven and works with any instruction-following LLM accessible through an API or a batched inference backend.
• The technique is most effective when the answer has a natural list or section structure, such as comparisons, how-to guides, or explanations of multi-part concepts.

Measured speedups across 12 LLMs

The paper evaluated SoT on 12 language models spanning a wide range of scales and providers, including GPT-4, Claude v1, Llama, Vicuna, and Falcon variants. The headline result is a speedup of up to 2.39 times in end-to-end generation latency. The speedup varies by task and model. Questions with a clear multi-point structure benefit the most, because the skeleton naturally decomposes into independent segments that expand without reference to each other. Questions requiring a narrative or continuous reasoning chain benefit less, because the expansion points cannot be independently generated without losing coherence across point boundaries.

The paper also reports quality results, and this is where SoT is noteworthy relative to most latency-reduction techniques. For several question categories, the parallel structure of SoT answers was rated higher than the sequential baseline on diversity and relevance. The authors attribute this to the explicit planning step: forcing the model to commit to an outline before expanding each point may produce more organized and complete answers than unconstrained sequential generation, where the model can drift or repeat itself as the context grows. The quality improvement is not universal; tasks that require a flowing narrative rather than a structured list may produce less natural output when forced through the skeleton format.

SoT-R: the router extension

The ICLR 2024 version of the paper introduces SoT-R, a routing extension that addresses the key limitation of the base method. Not every question has a natural skeleton structure. Questions asking for a single-paragraph explanation, a yes-or-no answer with brief justification, or a continuous reasoning chain do not decompose cleanly into independent expansion points. For these questions, applying SoT produces fragmented output that scores worse than a standard sequential response. SoT-R addresses this by adding a lightweight routing step at the start: the model is asked to classify whether the incoming question is suitable for SoT parallelization. If the classifier returns a positive signal, SoT is applied. If not, the system falls back to standard sequential generation. The routing step itself is a short call that adds minimal latency, and the paper shows that SoT-R preserves the quality of sequential generation on unsuitable question types while still capturing the latency gains on compatible ones.

When to use SoT and when to skip it

SoT is a strong fit for applications where the primary metric is time-to-full-response and where users are asking structured questions with multiple independent sub-answers. Technical documentation generators, comparison tools, FAQ systems, and how-to guides are natural candidates. The technique is especially valuable when operating through a provider API where each call is billed separately but can be issued in parallel, because the total cost in tokens is roughly the same as a single sequential call while the wall-clock time drops to the duration of the longest parallel call plus the skeleton call. For applications requiring narrative continuity, such as story generation, legal reasoning chains, or multi-step mathematical proofs, SoT is less suitable without significant prompt engineering to keep the expansion steps coherent with each other. The SoT-R router is the practical solution for mixed workloads where the question type is not known in advance.

PromptingIndex covers SoT alongside other inference-time optimization techniques including speculative decoding, which targets the same latency problem from the model-serving side, and chain-of-thought prompting, which deliberately adds sequential steps to improve reasoning at the cost of latency. SoT occupies a distinct position: it reduces latency while maintaining or improving answer quality on structured tasks, making it one of the few prompting techniques where the speed and quality trade-off moves in the same direction.