LLM & VLM courseBlog
91Track 5: LLM inference and serving · session 14 of 65

Output organization: Skeleton-of-Thought, APAR, SGLang; model cascades

A decode step for one sequence costs almost the same as a step for five, so a single answer leaves most of the GPU unused. This session shows how to change the shape of the output so independent parts are written at the same time: Skeleton-of-Thought, graph decoding and APAR. It then shows how SGLang shares the KV cache of common prompt prefixes across all these calls, and how a cascade of a small and a big model cuts the average cost of a request.

Time: 2.5 to 3.5 hours (reading 2 hours, exercises 1 hour)Level: IntermediateBefore this: Sessions 80, 82 and 84 (the KV cache, why inference is slow, batching basics)

What you will learn

  • Why a decode step at small batch costs about the same for 1 or 5 sequences, and how to turn that into lower latency for one answer
  • Skeleton-of-Thought: the two prompts, the latency formula, and why the longest point and the skeleton limit the speed-up
  • When SoT hurts (math, code) and how a router, a dependency graph (SGD) or a trained fork token (APAR) fixes it
  • How APAR forks threads that share the parent’s KV prefix, and how to count its decode steps
  • SGLang programs and RadixAttention: prefix matching, hit rate, memory saved by sharing, LRU eviction and prefix-aware scheduling
  • Model cascades (FrugalGPT): cost and accuracy as a function of one threshold, and why a cascade can beat the big model

Why this matters

A chat model that writes a 500-token answer runs the whole network 500 times, one step after the other. Each step makes one token. On a GPU, one step for one user costs almost the same time as one step for five users, because the time goes into reading the weights, not into arithmetic. So when only one user is waiting, most of the GPU’s power sits unused.

Session 82 showed this: decoding is memory-bound (its speed is set by how fast the GPU reads memory, not by how fast it computes). Session 84 used the free compute to serve more users at the same time. This session asks a different question: can we use the free compute to finish one answer sooner? The idea is to change the shape of the output. If an answer is a list of independent points, the points do not need to wait for each other. We can write them at the same time, as a batch, inside one request.

The efficient-inference survey calls this output organization (its Section 4.2, part of “data-level” optimization: the model is not changed, only the way we ask for and arrange its output). [Certain] We cover four ideas:

  • Skeleton-of-Thought (SoT): ask for a short outline first, then expand all points in parallel. Reported speed-ups reach 2.39× across 12 models. [Certain, SoT paper]
  • Graph and fork decoding: SGD puts dependent points in a graph; APAR teaches the model to emit a [Fork] token that starts a new parallel thread by itself.
  • SGLang: a small programming language for LLM calls whose runtime keeps a tree of all cached prefixes (RadixAttention), so the many requests that SoT-style programs create share their common prompt automatically.
  • Model cascades (FrugalGPT): a different way to organize work. Try a cheap model first, and call the expensive one only when the cheap answer looks unreliable.

These ideas are in real systems today. SGLang is a widely used open-source serving engine, and prefix caching in the style of RadixAttention exists in most major engines. [Likely] Routing between small and large models (the cascade idea) is a standard way to control the cost of LLM products. [Likely] The previous session, session 90, made the input shorter. This session makes the output faster to produce and the average request cheaper.

The cost model: why parallel points are almost free

We need one formula for the time of one decode step. In session 82 we saw that, at small batch sizes, a decode step must read all weights once and read the KV cache of every sequence in the batch. The arithmetic is too small to matter. So the step time is about the bytes moved divided by the memory bandwidth:

\[ t_{\text{step}}(B, c) \;\approx\; \frac{M_W + B \cdot c \cdot m_{kv}}{\text{BW}} \tag{91.1} \]
Read the symbols
\(B\)
batch size: how many sequences make one token each in this step
\(c\)
how many tokens each sequence already has in the KV cache (its context length)
\(M_W\)
bytes of all model weights (read once per step, shared by the whole batch)
\(m_{kv}\)
bytes of KV cache per token (keys and values of all layers)
\(\text{BW}\)
GPU memory bandwidth in bytes per second

The key fact is in the numerator: \(M_W\) is paid once per step, whatever \(B\) is. For Llama 2 7B in 16-bit, \(M_W \approx 13.5\) GB, while one token of KV cache is \(2 \cdot 32 \text{ layers} \cdot 32 \text{ heads} \cdot 128 \cdot 2 \text{ bytes} = 0.5\) MiB (session 80). With 300 tokens of context, five sequences add only about 0.8 GB of cache reads to the 13.5 GB of weights. So a step with \(B = 5\) costs only a few percent more than a step with \(B = 1\), but makes five tokens instead of one. This holds until \(B\) is large enough that compute becomes the limit; that point is often at a batch of 100 or more for a 7B model. [Likely]

Normal decoding writes the \(N\) tokens of an answer one after the other, always with \(B = 1\). After the prompt of \(n_q\) tokens is processed (the prefill, time \(T_{\text{pre}}\)), the time is:

\[ T_{\text{normal}} = T_{\text{pre}}(n_q) + \sum_{t=0}^{N-1} t_{\text{step}}(1,\, n_q + t) \;\approx\; N \cdot t_{\text{step}}(1) \tag{91.2} \]

The sum has \(N\) terms, and nothing can make it shorter as long as each token waits for the one before it. This is the sequential dependency of autoregressive decoding. Speculative decoding (session 128) attacks it by guessing several future tokens and checking them together. Output organization attacks it at a higher level: it finds parts of the answer that do not depend on each other at all.

Skeleton-of-Thought: outline first, then expand in parallel

Skeleton-of-Thought (Ning et al., 2023) copies how people write: first a plan, then the details. It needs no training and no change to the model. It is only a change in how we prompt. [Certain]

  1. Skeleton stage. A skeleton prompt asks the model for a short numbered outline only, with each point in about 3 to 5 words, and usually 3 to 10 points. [Certain, SoT paper] Example: “1. Keep a fixed schedule 2. Limit screens at night 3. Watch caffeine 4. Make the room dark”.
  2. Point-expanding stage. For each point \(i\), a point-expanding prompt contains the question, the whole skeleton, and the instruction “continue only point \(i\), in 1 to 2 sentences”. All these prompts are sent at the same time: as parallel API calls for a closed model, or as one batch for an open model on your own GPU.
  3. Join. The expansions are put together in order. The user sees one normal-looking answer.
Algorithm 1: Skeleton-of-Thought
  1. input: question \(q\), model \(f\), skeleton template \(P_s\), expansion template \(P_e\)
  2. \(\text{sk} \leftarrow f(P_s(q))\) // short outline, decoded normally with \(B = 1\)
  3. \(\text{points} \leftarrow \text{parse\_numbered\_list}(\text{sk})\) // e.g. 5 short lines
  4. if parsing fails or \(|\text{points}| \le 1\): return \(f(q)\) // fall back to a normal answer
  5. in parallel for \(i = 1 \dots K\): \(e_i \leftarrow f(P_e(q, \text{sk}, i))\) // one batch of \(K\) sequences
  6. return \(\text{points}_1 + e_1 + \dots + \text{points}_K + e_K\)

Now the time. The skeleton has \(L_s\) tokens and is decoded with \(B = 1\). Then all \(K\) expansion prompts are prefilled together, and the expansions are decoded together. Point \(i\) has \(L_i\) tokens. The batch shrinks as short points finish: at step \(s\) of the expansion, the batch holds the \(B_s\) points that are still longer than \(s\):

\[ T_{\text{SoT}} = \underbrace{T_{\text{pre}}(n_s) + L_s\, t_{\text{step}}(1)}_{\text{skeleton}} + \underbrace{T_{\text{pre}}(K n_e)}_{\text{expansion prefill}} + \underbrace{\sum_{s=0}^{\max_i L_i - 1} t_{\text{step}}(B_s)}_{\text{parallel expansion}}, \qquad B_s = \#\{i : L_i \gt s\} \tag{91.3} \]
Read the symbols
\(n_s, n_e\)
prompt lengths of the skeleton request and of one expansion request (question + template, plus the skeleton for \(n_e\))
\(L_s\)
skeleton length in tokens
\(L_i\)
length of the expansion of point \(i\); the answer has \(N = \sum_i L_i\) tokens in total
\(B_s\)
how many points are still being written at expansion step \(s\)

If the step time is flat in \(B\) (formula 91.1 at small batch) and prefill is short, the speed-up has a simple form:

\[ S = \frac{T_{\text{normal}}}{T_{\text{SoT}}} \;\approx\; \frac{\sum_{i=1}^{K} L_i}{L_s + \max_i L_i} \;\le\; K \tag{91.4} \]

Three lessons are in this one line. (1) The best case is \(K\) points of equal length and a tiny skeleton: speed-up close to \(K\). (2) The longest point sets the time; one long point ruins the gain. (3) The skeleton is pure extra work done sequentially; a long skeleton eats the gain.

Worked example: SoT for Llama 2 7B on one GPU

Assume a GPU with 2 TB/s of memory bandwidth and 312 TFLOP/s of 16-bit compute (about an A100), the Llama 2 7B numbers above (\(6.74 \times 10^9\) parameters, 13.5 GB of weights, 0.5 MiB of cache per token), and ideal kernels. One decode step with \(B = 1\) then takes \(13.48 \text{ GB} / 2 \text{ TB/s} = 6.74\) ms. Prefill is computed as \(\max(M_W/\text{BW},\ 2 \cdot 6.74\times10^9 \cdot n / 312\times10^{12})\).

The question has 50 tokens and the full answer has 500. The skeleton and expansion templates add 150 tokens each, and the skeleton has \(L_s = 30\) tokens.

  • Normal: 500 steps at \(B = 1\): 3,416 ms.
  • SoT, 5 equal points of 100 tokens: skeleton 212.5 ms, expansion prefill of \(5 \times 230\) tokens 49.7 ms, 100 parallel steps 710.6 ms. Total 972.8 ms, speed-up 3.51×. Formula (91.4) gives \(500/(30 + 100) = 3.85\); the gap is prefill and the growing KV cache.
  • SoT, 5 uneven points (60, 80, 100, 120, 140 tokens): the parallel phase now lasts 140 steps: total 1,243.0 ms, speed-up 2.75×.
  • SoT with one point of 500 tokens: 3,655.3 ms, a slow-down (0.93×): the skeleton was wasted work.

These are ideal lower-bound times from formula (91.1), not measurements. Real kernels are slower, and real SoT answers differ from normal answers in length. The SoT paper measured up to 2.39× on 12 models, above 2× on 8 of them. [Certain, SoT paper]

normal decoding (\(B = 1\))skeleton (\(B = 1\))prefillparallel expansion
Figure 1. The time of one answer with normal decoding (top bar) and with Skeleton-of-Thought (bars below), from formulas (91.1) to (91.3) for Llama 2 7B on a 2 TB/s GPU. Point \(i\) gets length \(\text{mean} \cdot (1 + u(2i/(K-1) - 1))\), so the unevenness \(u\) spreads the lengths around the mean. The total answer length is the same in both cases.
How to read Figure 1

Each blue bar is one point being written. All blue bars start at the same moment and run in one batch; the expansion is finished when the longest bar ends. Move the unevenness to 0 and the speed-up comes close to \(K\) times \(\text{mean}/(\text{mean} + L_s)\). Move it to 0.8 and the longest point decides everything. Set \(K = 1\) to see that SoT then only adds the cost of the skeleton. Increase \(L_s\) to see the sequential skeleton grow. The readout also shows the number of input tokens: SoT sends the question \(K + 1\) times, which costs money with a paid API.

When SoT helps and when it hurts

SoT assumes the points are independent: point 3 can be written without seeing the text of point 2. That is true for many “list” questions and false for others. The SoT paper found that SoT works well on knowledge, generic, common-sense, role-play and counterfactual questions, and works badly on math, Fermi estimates, coding and writing. [Certain, SoT paper] In math, step 3 needs the result of step 2, so the steps cannot be written at the same time.

The fix is a router: a small classifier that decides, per question, whether to use SoT or a normal answer. The paper calls this SoT-R and tries two routers: a prompt to GPT-4, and a fine-tuned RoBERTa model of about 120M parameters. [Certain] The router is cheap compared with the LLM, so it costs almost nothing per request.

Graph decoding: points that depend on each other

Pure SoT has two options: all points in parallel, or a normal answer. Many answers are in between. Point 3 may depend on point 1, while point 2 is independent. SGD (Jin et al., first called “Adaptive Skeleton Graph Decoding”, later renamed Plato) asks the model to write the skeleton as a dependency graph: a directed graph without cycles (a DAG), where an edge \(u \to v\) means “\(v\) needs the text of \(u\)”. [Certain] A node is decoded as soon as all of its parents are finished, and its prompt includes the parents’ text. The finish time of each node is:

\[ F(v) = \max_{u \in \text{pa}(v)} F(u) \;+\; L_v, \qquad T_{\text{graph}} = \max_v F(v) \tag{91.5} \]

Here \(\text{pa}(v)\) is the set of parents of \(v\) (the max over an empty set is 0), and \(L_v\) is the number of tokens of node \(v\). \(T_{\text{graph}}\) is the length of the critical path: the longest chain of dependent nodes. It lies between pure SoT (no edges: \(\max_v L_v\)) and normal decoding (a single chain: \(\sum_v L_v\)). The first version of the SGD paper reported a 1.69× speed-up over normal decoding and up to 51% better quality than SoT; the later version reports 68% higher throughput. [Certain, arXiv 2402.12280 v1 and v2] The survey adds that SGD also picks a model size per node, from an estimate of how hard the node is. [Certain, survey Section 4.2]

Figure 2. Four parts of an answer: P1 (60 tokens), P2 (80), P3 (50, needs P1) and P4 (40, needs P1 and P2). Left: the dependency graph. Right: when each part is decoded under each schedule. One column of the timeline is one decode step for all active parts together.
How to read Figure 2

“Normal” writes everything in one chain: 230 steps. “SoT” starts all four at once: 80 steps, but P3 and P4 are written without the text they need, which is where SoT loses quality. “Level by level” waits until the whole first level (P1 and P2) is done: 130 steps. “As soon as ready” starts P3 the moment P1 ends: 120 steps, the critical path of formula (91.5). Red marks show parts that started before their parents were done.

APAR: let the model fork itself

SoT and SGD use prompts and need at least two rounds of calls: one for the skeleton, one for the expansion. APAR (Auto-Parallel Auto-Regressive decoding, Liu et al., 2024) moves the planning into the model. The model is fine-tuned to emit a special control token, [Fork], at points where the text that follows can be written in parallel. The paper compares it to the fork() system call of an operating system. [Certain]

How it works:

  • Training data. Answers with structure (numbered lists, several paragraphs) are turned into a tree of paragraph nodes. Each node has a short root (the first phrase or sentence) and the detail (the rest). The authors built about 16k structured samples from ShareGPT conversations, plus about 9k unstructured ones (code, math) kept as single nodes so the model learns not to fork there. They fine-tuned Vicuna v1.3 7B and 13B. [Certain, APAR paper]
  • Attention during training. Each node attends only to its ancestors and itself, not to its siblings. So the model learns to write a detail without seeing the other details, which is exactly the situation at inference time.
  • Inference. When the model samples [Fork] after a root, the engine creates a new sequence that shares the parent’s prefix, appends a forced [Child] token to it, and decodes it in the same batch. The child writes the detail; the parent goes on with the next root. When a thread ends, its KV cache can be freed, because no other thread attends to it. At the end, the tree is read in order to give the final text. [Certain]
Algorithm 2: APAR fork decoding (one request)
  1. input: prompt \(p\); state: active threads \(\mathcal{A} \leftarrow \{\text{main}\}\), tree with one node
  2. while \(\mathcal{A}\) is not empty:
  3.   run one decode step for all threads in \(\mathcal{A}\) as one batch // each attends only to its path to the root
  4.   for each thread \(s \in \mathcal{A}\) with new token \(x\):
  5.     if \(x = \texttt{[Fork]}\): create \(s'\) that shares the KV blocks of \(s\); append \(\texttt{[Child]}\) to \(s'\); add \(s'\) to \(\mathcal{A}\) // copy at most one block
  6.     else if \(x = \texttt{[EOS]}\): remove \(s\) from \(\mathcal{A}\); free its own KV blocks
  7.     else: append \(x\) to the current node of \(s\)
  8. return the tree read in order (root, first child, next sibling)

The number of decode steps is the time at which the last thread ends. If child \(j\) is forked at step \(f_j\) and writes \(L_j\) tokens, and the main thread ends at step \(T_0\):

\[ T_{\text{APAR}} = \max\Big( T_0,\ \max_j \big( f_j + L_j \big) \Big) \tag{91.6} \]

APAR avoids three costs of SoT: no second round of prompts, no repeated question in the input, and no wasted skeleton (the roots are the skeleton, and they stay in the final text). With paged attention (vLLM), a fork copies at most one KV block and shares the rest. [Certain] The reported results: about 2× average speed-up on Vicuna Bench and 1.4× on MT-Bench at batch size 1, up to about 4× and 2.9× when combined with Medusa speculative decoding, and 20–70% higher throughput in a vLLM serving setting, with answer quality within about ±2% of the original model by GPT-4 judgment. [Certain, APAR paper]

root text (main thread)[Fork] tokendetail (child thread)intro and conclusion
Figure 3. One APAR answer with a 20-token question, an intro of 10 tokens, three list items (root of 6 tokens, then [Fork]), and a 12-token conclusion. The three details have 30, 22 and 36 tokens and are written by child threads. Written in one chain, the same 128 tokens need 128 steps.
How to read Figure 3

Each row is one thread; the horizontal axis is the decode step. Move the slider: the main thread writes a root, emits [Fork], and a child row starts on the next step. During the overlap, several tokens are made per step. The readout counts the KV cache in tokens. With sharing, the cache holds the question, the main thread, and the details of the threads still running. Without sharing (the paper’s plain Transformers version), each child holds its own copy of the parent’s prefix.

Worked example: the steps of Figure 3

The main thread writes \(10 + 3 \times (6 + 1) + 12 = 43\) tokens (the 3 are the [Fork] tokens), so \(T_0 = 43\). The forks happen at steps 17, 24 and 31. The children end at \(17 + 30 = 47\), \(24 + 22 = 46\) and \(31 + 36 = 67\). By formula (91.6), \(T_{\text{APAR}} = \max(43, 47, 46, 67) = 67\) steps for 128 text tokens: a 1.91× reduction in steps. The last child decides the time, just like the longest point in SoT.

SGLang: programs of LLM calls, and sharing their prefixes

SoT, SGD and agent pipelines all turn one user request into a program of many LLM calls, and these calls share long beginnings: the same system prompt, the same question, the same skeleton. If the engine treats every call as a fresh request, it computes the KV cache of the shared part again and again. SGLang (Zheng et al., 2023) fixes this from both sides. [Certain]

  • The front end is a small language embedded in Python. A program builds a prompt state with +=, and uses primitives: gen (generate into a named variable, optionally with a regex constraint), select (pick the most likely option from a list), fork and join (make parallel copies of the state, and merge them), and image / video for multimodal input. [Certain, SGLang paper] SoT is a few lines: one gen for the skeleton, a fork into \(K\) copies, one gen per copy.
  • The runtime keeps every computed KV cache in a radix tree (RadixAttention). A radix tree is a prefix tree in which one edge can hold a whole run of tokens. Every path from the root is a token sequence whose KV cache is in GPU memory. A new request walks down the tree, reuses the KV cache of the longest matching prefix, and only computes the rest.

How much does sharing save? Let request \(r\) have prompt \(p_r\). Without sharing, prefill computes \(\sum_r |p_r|\) tokens. With a perfect prefix cache, it computes only the tokens that are new to the tree: the size of the union of all prefixes. The cache hit rate is the share of prompt tokens that were reused:

\[ h = 1 - \frac{\big|\bigcup_r \text{prefixes}(p_r)\big|}{\sum_r |p_r|} \tag{91.7} \]

Sharing also saves memory, not only compute. For a fork of \(K\) branches after a shared prefix of \(n_p\) tokens, where branch \(i\) adds \(L_i\) tokens:

\[ M_{\text{shared}} = \Big(n_p + \sum_{i=1}^{K} L_i\Big)\, m_{kv}, \qquad M_{\text{copied}} = \Big(K n_p + \sum_{i=1}^{K} L_i\Big)\, m_{kv} \tag{91.8} \]
Algorithm 3: RadixAttention for one new request
  1. input: token sequence \(p\); radix tree \(\mathcal{T}\) whose nodes hold KV blocks, a reference count and a last-used time
  2. \(v, m \leftarrow \text{match\_prefix}(\mathcal{T}, p)\) // deepest node \(v\); \(m\) = number of matched tokens (an edge may be split)
  3. increase the reference count of every node on the path to \(v\) // in use: cannot be evicted
  4. while free memory \(\lt\) memory for \(|p| - m\) new tokens: evict the least recently used leaf with reference count 0
  5. prefill only \(p[m:]\), attending to the cached KV of \(p[:m]\); then decode
  6. insert the new prompt tokens and the generated tokens below \(v\); when the request ends, decrease the reference counts

Evicting leaves first keeps shared ancestors (like a system prompt) alive as long as possible. A node can only be evicted when no running request uses it. [Certain] The scheduler also helps: it orders waiting requests by the length of their matched prefix (longest first), so requests that share a prefix run close together while that prefix is still in the cache. For a batch known in advance and a cache at least as large as the longest request, the paper proves that a depth-first visit of the tree gives the best possible hit rate, and longest-prefix-first matches that order. Online it is only an approximation, and it can starve requests with no match, so real schedulers mix in fairness. [Certain, SGLang paper]

reused from the cacheprompt tokens computed nowtokens generated nowcached earlier, not used now
Figure 4. A radix tree of cached KV, built by eight requests to one engine: two few-shot questions with the same 300-token system prompt and 500 tokens of examples, a two-turn chat, and one SoT program (a skeleton, then three point expansions created by fork). Numbers in the boxes are token counts. For clarity, each box is one prompt part; the real tree splits edges at any token.
How to read Figure 4

Press Next to send the next request. Green boxes are the matched prefix: their KV is read from the cache, not computed. Orange boxes are new prompt tokens that prefill must compute. Blue boxes are the answer, which is also added to the tree; that is why the second chat turn reuses the first answer. The readout gives the hit rate of formula (91.7), for this request and for all requests so far.

Worked example: what the tree in Figure 4 saves

The eight requests have \(4{,}084\) prompt tokens in total. With the radix tree, \(3{,}060\) of them are found in the cache, so prefill computes only \(1{,}024\) tokens: a hit rate of \(3{,}060 / 4{,}084 = 74.9\%\). The three SoT point requests each have a 408-token prompt and reuse 400 of those tokens.

Memory, by formula (91.8), for the three SoT branches of Llama 2 7B: the shared prefix is \(n_p = 300 + 60 + 40 = 400\) tokens, and each branch adds \(8 + 100 = 108\). Shared: \((400 + 324) \times 0.5 \text{ MiB} = 362\) MiB. Copied: \((1{,}200 + 324) \times 0.5 \text{ MiB} = 762\) MiB, more than twice as much.

The SGLang paper reports up to 6.4× higher throughput and up to 3.7× lower latency than other systems (Guidance, vLLM, LMQL) on agent, reasoning, few-shot, JSON, RAG and multi-turn chat workloads, with cache hit rates between 50% and 99%. [Certain, SGLang paper] Two other runtime tricks are worth knowing. A compressed finite-state machine speeds up constrained output such as JSON: when the regex allows only one continuation (like {"name": "), several tokens are added in one step instead of one per step. And API speculative execution lets the first gen call to a closed API run past its stop point, so later fields of a template may already be filled, saving a call. [Certain] The serving side of prefix caching is covered in session 134.

Model cascades: try the small model first

The methods above make one answer faster. A cascade makes the average answer cheaper. Most requests are easy. A small model answers them correctly; only some need the largest model. FrugalGPT (Chen et al., 2023) studied paid LLM APIs whose prices differed by two orders of magnitude, and proposed the LLM cascade: send the query to a list of models, cheapest first, and stop as soon as an answer is judged reliable. [Certain]

The judge is a scoring function \(g(q, a) \in [0, 1]\) that estimates how likely answer \(a\) to query \(q\) is correct. In FrugalGPT it is a small DistilBERT regression model, trained on examples of correct and wrong answers, and far cheaper than any of the LLMs. [Certain] Each model \(i\) in the list has a threshold \(\tau_i\). For two models, small (s) and big (b), with prices \(c_s\) and \(c_b\), and the share of queries the small model keeps \(a(\tau) = P(g \ge \tau)\):

\[ \E[C](\tau) = c_s + \big(1 - a(\tau)\big)\, c_b \tag{91.9} \]
\[ \text{Acc}(\tau) = P\big(g \ge \tau,\ \text{small correct}\big) + P\big(g \lt \tau,\ \text{big correct}\big) \tag{91.10} \]
Read the symbols
\(\tau\)
the threshold: keep the small answer when its score is at least \(\tau\); raising it sends more queries to the big model
\(a(\tau)\)
acceptance rate: share of queries answered by the small model alone
\(c_s, c_b\)
cost of one call to the small and the big model (the small one is always paid, even when its answer is rejected)

With more models, FrugalGPT picks the ordered list \(L\) of APIs and all thresholds to maximize expected answer quality under a budget \(b\):

\[ \max_{L,\ \tau}\ \E\big[r(a,\, f_{L_z}(q))\big] \quad \text{s.t.} \quad \E\Big[\sum_{i=1}^{z} c_{L_i}(q)\Big] \le b \tag{91.11} \]

Here \(z\) is the position in the list where the cascade stops for query \(q\), \(f_{L_z}\) is the model at that position, and \(r\) is the reward (for example 1 if the answer is right). This is a hard mixed-integer problem; the paper prunes candidate lists and uses a fast approximate search. In the experiments the lists have length 3. [Certain]

Algorithm 4: an LLM cascade at inference time
  1. input: query \(q\); models \(f_{L_1}, \dots, f_{L_m}\) from cheap to expensive; thresholds \(\tau_1, \dots, \tau_{m-1}\); scorer \(g\)
  2. for \(i = 1 \dots m - 1\):
  3.   \(a \leftarrow f_{L_i}(q)\); pay \(c_{L_i}\)
  4.   if \(g(q, a) \ge \tau_i\): return \(a\) // reliable enough: stop here
  5. return \(f_{L_m}(q)\) // the last model always answers

The real example from the paper, on the HEADLINES dataset with a budget one fifth of GPT-4’s cost: ask GPT-J; accept if the score is above 0.96; otherwise ask J1-L; accept if above 0.37; otherwise ask GPT-4. Across datasets, FrugalGPT matched the best single model at 98.3%, 73.3% and 59.2% lower cost (HEADLINES, OVERRULING, COQA), and could also beat GPT-4’s accuracy by up to 4% at the same cost. [Certain, FrugalGPT paper] How can a cascade beat the big model? The small model is sometimes right where the big one is wrong, and a good scorer keeps exactly those answers.

cascade, all thresholdsyour thresholdsmall only / big onlyperfect scorer
Figure 5. A simulated two-model cascade on 2,000 synthetic queries (seeded, not a benchmark). Each query has a hidden difficulty; the small model is right on about 69% of queries, the big one on about 93%. The scorer sees whether the small answer is right only through noise; “scorer quality” sets how strong that signal is. Cost is shown as a share of always calling the big model.
How to read Figure 5

The blue curve shows every threshold from 0 (always keep the small answer, bottom left) to 1 (always escalate, top right, a bit more expensive than the big model alone because the small call is still paid). Good cascades lie toward the top left. Set scorer quality to 0: the scorer is random, and the curve becomes a straight line between the two models, so the cascade buys nothing. At high quality the curve bends up toward the green point of a perfect scorer, which beats the big model alone. Lower the price ratio: when the big model is only 2× more expensive, paying for the small call first is rarely worth it.

Worked example: the default point of Figure 5

With \(\tau = 0.5\) and scorer quality 2.5, the small answer is rejected for 689 of the 2,000 queries (34.45%). With \(c_s = 1\) and \(c_b = 20\), formula (91.9) gives \(\E[C] = 1 + 0.3445 \times 20 = 7.89\), which is \(7.89/20 = 39.4\%\) of the cost of the big model alone. Accuracy is 92.45%, against 93.35% for the big model alone and 68.8% for the small one. Raise \(\tau\) to 0.7: 40.9% of queries escalate, cost 45.9%, accuracy 93.4%, the same as the big model at less than half the price.

The survey places cascades in its model-level section rather than in output organization. [Certain] We put them here because they answer the same engineering question: how to organize the work of one request so that the expensive part is done only where it is needed. The same idea appears in early exit (session 121) and in speculative decoding, where a small model drafts and a big one checks.

Code: shared-prefix parallel expansion and a cascade in PyTorch

The code builds a tiny decoder with a KV cache. It prefills a shared prefix once, gives three “point” branches a view of that cache (no copy), decodes them as one batch, and checks that the result is exactly the same as three separate full runs. Then it evaluates a two-model cascade on the same synthetic setting as Figure 5. It runs on a CPU in about a second, with fixed seeds.

import torch, torch.nn.functional as F
torch.manual_seed(0)
V, D, H = 50, 32, 4                      # vocab, width, heads

class TinyLM(torch.nn.Module):
    def __init__(s):
        super().__init__()
        s.emb = torch.nn.Embedding(V, D); s.pos = torch.nn.Embedding(256, D)
        s.qkv = torch.nn.Linear(D, 3 * D); s.out = torch.nn.Linear(D, D)
        s.mlp = torch.nn.Sequential(torch.nn.Linear(D, 4 * D), torch.nn.GELU(), torch.nn.Linear(4 * D, D))
        s.head = torch.nn.Linear(D, V)
    def forward(s, ids, cache=None):      # ids (B, T); cache = (K, V), each (B, H, T_old, D/H)
        B, T = ids.shape
        t0 = 0 if cache is None else cache[0].shape[2]
        x = s.emb(ids) + s.pos(torch.arange(t0, t0 + T))
        q, k, v = s.qkv(x).view(B, T, 3, H, D // H).permute(2, 0, 3, 1, 4)
        if cache is not None:
            k = torch.cat([cache[0], k], 2); v = torch.cat([cache[1], v], 2)
        mask = torch.ones(T, t0 + T, dtype=torch.bool).tril(t0)   # causal, shifted by the cache
        a = F.scaled_dot_product_attention(q, k, v, attn_mask=mask)
        x = x + s.out(a.transpose(1, 2).reshape(B, T, D))
        x = x + s.mlp(x)
        return s.head(x), (k, v)

@torch.no_grad()
def greedy(model, logits, cache, steps):  # decode `steps` tokens for every row of the batch
    out = []
    for _ in range(steps):
        nxt = logits[:, -1].argmax(-1, keepdim=True); out.append(nxt)
        logits, cache = model(nxt, cache)
    return torch.cat(out, 1)

model = TinyLM().eval()
prefix = torch.randint(0, V, (1, 40))     # system prompt + question + skeleton (shared)
points = torch.randint(0, V, (3, 4))      # "expand point i" tokens, one row per point

with torch.no_grad():
    # 1) SoT expansion with a shared prefix: prefill the prefix ONCE, then share its KV cache
    _, (k, v) = model(prefix)
    shared = (k.expand(3, -1, -1, -1), v.expand(3, -1, -1, -1))   # a view, formula (91.8): no copy
    logits, cache = model(points, shared)
    batched = greedy(model, logits, cache, 12)   # all 3 points decoded together as one batch

    # 2) the same three expansions, one by one, each with its own full prefill
    alone = torch.cat([greedy(model, *model(torch.cat([prefix, points[i:i+1]], 1)), 12)
                       for i in range(3)])

print("same tokens:", torch.equal(batched, alone))                       # True
print("prefill tokens, shared vs not:", 40 + 3 * 4, "vs", 3 * (40 + 4))  # 52 vs 132

# 3) a two-model cascade, formulas (91.9) and (91.10)
def cascade(score, small_ok, big_ok, tau, c_small=1.0, c_big=20.0):
    accept = score >= tau
    acc = torch.where(accept, small_ok, big_ok).float().mean().item()
    cost = (c_small + (~accept).float().mean().item() * c_big) / c_big
    return acc, cost

g = torch.Generator().manual_seed(0)
d = torch.rand(2000, generator=g)                                      # hidden difficulty
small_ok = torch.rand(2000, generator=g) < torch.sigmoid((0.7 - d) * 10)
big_ok   = torch.rand(2000, generator=g) < torch.sigmoid((1.0 - d) * 10)
noise = torch.logit(torch.rand(2000, generator=g))
score = torch.sigmoid(2.5 * (small_ok.float() * 2 - 1) + noise)           # a noisy judge
for tau in (0.3, 0.5, 0.7):
    acc, cost = cascade(score, small_ok, big_ok, tau)
    print(f"tau={tau}: accuracy {acc:.3f}, cost {cost:.3f} of big-only")
# tau=0.3: accuracy 0.901, cost 0.321 | tau=0.5: 0.920, 0.372 | tau=0.7: 0.933, 0.441
print(f"small only {small_ok.float().mean():.3f}, big only {big_ok.float().mean():.3f}")  # 0.698, 0.934

Two details matter. expand makes a view with stride 0 along the batch, so the prefix KV exists once in memory; the new tokens of each branch are concatenated per row, as a paged engine does with its own blocks. And the output is exactly equal: sharing a prefix changes the cost, never the math. (The synthetic cascade numbers differ slightly from Figure 5 because the random generator is different.)

Where this is used

SettingTechniqueWhy it fits
Chat assistant answering “list” questions (tips, pros and cons, comparisons)SoT with a router (SoT-R), or an APAR-tuned modelPoints are independent; latency at batch 1 is set by the number of sequential steps
Agents and tool pipelines with a long system promptSGLang programs; prefix caching (RadixAttention)Every call repeats the same thousands of tokens of instructions and tool descriptions
Few-shot classification of many itemsShared few-shot prefix in the radix tree; select over the label setHit rates near the top of the 50–99% range; one forward pass scores the options
Video summarization by chaptersSkeleton of chapter titles (from shot boundaries), then parallel expansion per chapterChapters can be described independently; the video tokens are the shared prefix
Video-RAG and video question answering (several questions on one clip)Prefix sharing of the encoded video tokens; fork per questionA clip can be thousands of visual tokens; prefill them once, not once per question [Likely]
Key-moment detection and captioning of a long broadcastCascade: a small vision-language model screens every segment; a large model only describes the candidatesMost segments are uneventful; the big model runs on a small share of them
Content moderation, video classification, and fingerprint-match reviewCascade with a calibrated scorer and a budget (formula 91.11)Cheap decisions for clear cases; expensive review only near the decision boundary
High-load serving (big batches)APAR in vLLM; prefix cachingBatch is already large, so the gain comes from fewer cached and attended tokens, not from free compute

Common mistakes

  • Using SoT for every question. On math, code and step-by-step reasoning, points depend on each other and quality drops. Use a router, or a graph method.
  • Expecting a K-times speed-up. Formula (91.4) is limited by the longest point and by the skeleton. Uneven points and a long skeleton can turn the gain into a loss (Figure 1 with \(K = 1\)).
  • Forgetting that SoT needs free compute. On a server that already runs a big batch, decoding is closer to compute-bound and the extra branches compete with other users. The latency gain shrinks and throughput does not grow.
  • Copying the prefix KV for every branch. Without prefix sharing, memory grows with \(K n_p\) (formula 91.8), and the batch of other users that fits shrinks.
  • Breaking prefix reuse by accident. A timestamp or user name at the start of the system prompt makes every request different from token 1, so the hit rate is 0. Put the fixed parts first and the changing parts last.
  • Using the LLM’s own confidence as the cascade score without checking calibration. Token probabilities are often over-confident; FrugalGPT trains a separate scorer on labeled answers. Measure accuracy and cost on held-out data at each threshold.
  • Ignoring the cost of the first call. In a cascade the cheap model is always paid. If most queries escalate, or the price ratio is small, the cascade costs more than the big model alone.

Interview questions

Skeleton-of-Thought generates about as many tokens as a normal answer. Why can it be faster?basic
At small batch, a decode step is memory-bound: its time is mostly reading the weights once (formula 91.1). A step with 5 sequences costs almost the same as a step with 1 but makes 5 tokens. SoT turns a chain of \(N\) dependent tokens into a short skeleton plus \(K\) chains that run side by side, so the number of sequential steps falls from \(N\) to about \(L_s + \max_i L_i\).
When does SoT hurt, and what do you do about it?core
When points depend on each other (math, coding, Fermi estimates, stories), each expansion is written without the text it needs, and quality drops. Also when the answer is short or has one dominant point, since the skeleton is wasted sequential work. Fixes: a router (SoT-R) that sends only suitable questions to SoT; a dependency graph (SGD) so dependent parts wait for their parents; or a model trained to fork only where it is safe (APAR).
Estimate the SoT speed-up for 4 points of 50, 50, 50 and 150 tokens with a 20-token skeleton.core
By formula (91.4): \(N = 300\), and the sequential steps are \(20 + 150 = 170\), so \(S \approx 300/170 = 1.76\). If the same 300 tokens were split evenly (75 each), \(S \approx 300/95 = 3.16\). The longest point decides; prompts that ask for balanced, short points help.
How do SoT and speculative decoding differ? Can you combine them?core
Speculative decoding keeps the exact output distribution: a draft proposes tokens and the target model verifies them in one pass, so it speeds up each chain. SoT changes the output itself (a different prompt, so a different answer) and runs several chains in parallel. They are independent and can be combined: APAR with Medusa heads reached about 4× on Vicuna Bench versus about 2× for APAR alone.
What does APAR change compared with SoT?core
APAR fine-tunes the model to emit [Fork] where the following text can be parallel; the engine starts a child thread that shares the parent’s KV prefix. There is no separate skeleton call, no re-sent question, and the roots stay in the final text. Training uses a tree attention mask so a node sees only its ancestors, matching inference. The cost is fine-tuning, and it needs engine support for forking.
Explain RadixAttention: data structure, matching and eviction.core
All cached KV is stored as paths in a radix tree over token sequences; edges can hold many tokens. A new request finds its longest matching prefix, reuses that KV, and computes only the rest; its prompt and output are inserted into the tree. Nodes in use by running requests have a reference count above 0 and cannot be evicted. When memory is needed, the least recently used leaf with count 0 is evicted, so shared ancestors live longest. Cached and running tokens share one memory pool.
Why does SGLang schedule by longest shared prefix first, and what is the risk?advanced
Requests that share a prefix should run while that prefix is still cached; ordering by match length approximates a depth-first walk of the tree, which the paper proves gives the best hit rate for an offline batch when the cache holds at least one full request. The risk is starvation: requests with no match keep waiting. Real schedulers add fairness, priorities or aging, and must also respect latency goals.
Design a two-model cascade for a classification API. How do you set the threshold?core
Collect a labeled set; run both models; train a cheap scorer \(g(q, a)\) to predict whether the small answer is right. On held-out data, sweep \(\tau\), computing cost with (91.9) and accuracy with (91.10). Pick the cheapest \(\tau\) that meets the accuracy target (or the most accurate within budget, 91.11). Monitor the escalation rate in production, since a shift in traffic changes both cost and accuracy.
How can a cascade be more accurate than the big model alone?advanced
The two models make different errors. On some queries the small model is right and the big one is wrong. If the scorer keeps the small answer exactly on those, and escalates when the small one is wrong, accuracy is that of “either model right”, above either alone (the green point in Figure 5). FrugalGPT reported up to 4% better accuracy than GPT-4 at the same cost. This needs a scorer that is good, not just confident.
Your server already runs batches of 128. Will SoT still lower latency?advanced
Much less. At large batch, the step is closer to compute-bound and every extra branch takes compute from other users; per-step time rises with \(B\), so formula (91.4) no longer has a flat denominator. SoT also adds prefill and tokens. Overall throughput does not improve and may fall. APAR’s gains at high load come from a different source: fewer cached and attended tokens per thread (children see only their path), which let more requests fit (20–70% higher throughput in its vLLM tests).
A team reports a 10% prefix-cache hit rate on a chat product with a 2,000-token system prompt. What do you check?advanced
Whether the prompt really is identical at the token level: dynamic content (date, user name, request id) placed early breaks every match; different chat templates or tool lists per user also break it. Then whether the cache is evicted before reuse (too little memory, or a load balancer that spreads one user’s turns across many replicas; use cache-aware routing). Also check that turn \(n+1\) re-sends turn \(n\) exactly as it was generated.

Exercises

  1. With formula (91.4), compute the ideal SoT speed-up for 6 equal points of 80 tokens and a 40-token skeleton. What happens if one of the points grows to 200 tokens (the others stay at 80)?
  2. In Figure 2, add an edge P2 \(\to\) P3. What is the new critical path for “as soon as ready”?
  3. An APAR answer has a main thread of 30 tokens with forks at steps 8, 15 and 22; the children have 25, 40 and 10 tokens. How many decode steps does it take? How many text tokens are written in total, if the main thread includes 3 fork tokens?
  4. Ten requests share a 1,500-token prefix and each adds 100 new tokens. Compute the prefill tokens with and without prefix sharing, and the hit rate (91.7).
  5. A small model costs \$0.2 and a big one \$3 per 1,000 queries’ worth of tokens. The cascade escalates 25% of queries. What is the cost per 1,000 queries and the saving against always using the big model? At what escalation rate does the cascade stop saving money?
  6. Write an SGLang-style program (pseudo-code) for SoT that uses gen, fork and join. Which part of the KV cache is shared, and which is not?
Answerscheck
1. \(N = 480\); \(S \approx 480/(40 + 80) = 4.0\). With one point at 200: \(N = 600\), \(S \approx 600/(40 + 200) = 2.5\). 2. P3 now starts at \(\max(60, 80) = 80\) and ends at 130; P4 still ends at 120, so the critical path is 130 steps. 3. Children end at \(8 + 25 = 33\), \(15 + 40 = 55\), \(22 + 10 = 32\); the main thread ends at 30, so 55 steps. Text tokens: \(30 - 3 + 25 + 40 + 10 = 102\), so 102 sequential steps without APAR: 1.85× fewer steps. 4. Without sharing: \(10 \times 1{,}600 = 16{,}000\). With sharing: \(1{,}500 + 10 \times 100 = 2{,}500\). Hit rate \(1 - 2{,}500/16{,}000 = 84.4\%\). 5. \(0.2 + 0.25 \times 3 = \$0.95\) against \$3: a saving of 68.3%. Break-even: \(0.2 + e \cdot 3 = 3\), so \(e = 93.3\%\). 6. s += question; s += "Skeleton:" + gen("sk", stop="\n\n"); fs = s.fork(K); for i, f in enumerate(fs): f += f"Expand point {i+1}:" + gen("e", max_tokens=128); s.join(fs). The KV of the question and the skeleton (the state before fork) is shared by all branches through the radix tree; each branch’s instruction and expansion tokens are its own.

Key takeaways

  • At small batch, a decode step costs about the same for 1 or 5 sequences (91.1). Output organization uses this to cut the number of sequential steps of one answer (91.2, 91.3).
  • Skeleton-of-Thought: outline, then parallel expansion. Speed-up \(\approx \sum L_i / (L_s + \max L_i)\) (91.4); up to 2.39× reported on 12 models. Use a router; it hurts on math and code.
  • Graph decoding (SGD) runs parts as soon as their parents end; time is the critical path (91.5). APAR trains the model to emit [Fork] and runs children with a shared prefix; time is the last thread’s end (91.6).
  • SGLang programs plus RadixAttention reuse KV for every shared prefix: hit rate (91.7), memory saving (91.8), LRU eviction of unused leaves, longest-prefix-first scheduling.
  • Cascades (FrugalGPT) send queries to the cheap model first and escalate by a learned score; cost (91.9) and accuracy (91.10) are traded with one threshold, or optimized under a budget (91.11).

Key formulas

\[ t_{\text{step}}(B) \approx \frac{M_W + B c\, m_{kv}}{\text{BW}}, \qquad S_{\text{SoT}} \approx \frac{\sum_i L_i}{L_s + \max_i L_i}, \qquad F(v) = \max_{u \in \text{pa}(v)} F(u) + L_v \]
\[ h = 1 - \frac{|\bigcup_r \text{prefixes}(p_r)|}{\sum_r |p_r|}, \qquad \E[C] = c_s + (1 - a(\tau))\, c_b \]

References for this session

  1. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  2. Ning et al. (2023). Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation
  3. Liu et al. (2024). APAR: LLMs Can Do Auto-Parallel Auto-Regressive Decoding
  4. Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
  5. Chen et al. (2023). FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance
  6. Jin et al. (2024). Adaptive Skeleton Graph Decoding (later version: Plato: Plan to Efficiently Decode for Large Language Model Inference)
  7. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  8. Cai et al. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads