Test-Time Compute

Notes

Test-time compute is the deliberate expansion of the inference-time computation budget, usually by generating hidden or visible “thinking” tokens, sampling multiple candidate solutions, or running verifier-guided search, instead of increasing parameter count or doing another training run. For an autoregressive decoder, the dominant per-request work is approximately $C\approx 2N_{\text{params}}{T}_{\text{gen}}+C_{\text{attn}}(T_{\text{prompt}},T_{\text{gen}})$ FLOPs, while the dominant decode memory traffic for weights is approximately $B\approx S_{\text{weights}}{T}_{\text{gen}}$ when batch size is too small to reuse weights efficiently. The product trade is therefore explicit: if a reasoning policy raises output length from $T$ to $kT$, it buys accuracy by multiplying decode cost and latency by roughly $k$, plus extra KV-cache traffic. This is the shift behind chain-of-thought, self-consistency, verifier reranking, tree search, and systems such as EAGLE speculative decoding: quality is no longer purchased only by a larger checkpoint, but by spending more tokens on every customer request.

For a concrete decode-bound example, take a 70B FP16 model on one 80GB H100 with $3.35$ TB/s HBM bandwidth. The weights occupy about $70\times 10^9\times 2=140$ GB, so a single-token, batch-1 decode pass must stream about $140$ GB of weights, ignoring tensor-parallel sharding details. The bandwidth lower bound is $140/3350=0.0418$ s, or about $24$ tokens/s, before attention, kernels, synchronization, and sampling. If “thinking” changes a request from $300$ output tokens to $1800$, the lower-bound weight traffic changes from $42$ TB to $252$ TB, and the lower-bound time changes from $12.5$ s to $75.2$ s on that single-GPU mental model. On a real tensor-parallel deployment the weights are split and batch reuse improves throughput, but the billable fact remains: six times as many generated tokens means roughly six times as many decode steps unless speculative or parallel search accepts enough tokens to compensate.

The KV-cache term is the part that makes long thinking qualitatively different from simply printing a longer answer. With grouped-query attention using $8$ KV heads, head dimension $128$, FP16 KV, and $80$ layers, one token’s KV footprint is $2\times 8\times 128\times 2\times 80=327,680$ bytes, about $320$ KiB/token/request. A $10,000$-token scratchpad therefore consumes about $3.28$ GB of KV cache for one sequence; $16$ concurrent such sequences consume about $52.4$ GB before allocator fragmentation and metadata. This is why vLLM’s PagedAttention paper, “Efficient Memory Management for Large Language Model Serving with PagedAttention,” mattered: it made fragmented KV allocation look more like virtual memory pages, raising usable batch size for long prompts and long generations. FlashAttention, from Dao et al., attacks the attention IO pattern inside the kernel, but it does not make the KV cache free; it reduces SRAM/HBM movement for attention computation, while every extra reasoning token still creates another KV entry that future tokens must read.

The field’s economic bargain is that training is a capital expense amortized over many calls, while test-time compute is an operating expense proportional to live demand. A 70B model trained once may cost millions, but after release the marginal cost of a product feature such as “think harder” is incurred on every API request, in GPU seconds, KV residency, queueing delay, and failed speculative drafts. Self-consistency is the cleanest illustration: sampling $n$ chains and voting can raise math accuracy, but its cost is $C_{\text{sc}}\approx n{C}_{\text{single}}+C_{\text{vote}}$, so $8$ samples of $1000$ tokens behave like an $8000$-token decode workload unless batched perfectly. OpenAI’s o1-style public framing, DeepSeek-R1-style visible reasoning, and verifier/search recipes all lean on this same exchange: spend inference tokens where a smaller direct answer would be wrong. The engineering consequence is that capacity planning moves from “can we train the model?” to “can we afford tomorrow morning’s reasoning traffic at the latency SLO?”

The serving stack has adapted by trying to make extra tokens less painful rather than pretending they are free. vLLM combines PagedAttention with continuous batching so long and short requests can share decode iterations without reserving worst-case KV blocks. SGLang, introduced with its RadixAttention/runtime work, targets structured multi-call and agent workloads where prefixes, tool traces, and branches can be cached and reused instead of recomputed. TensorRT-LLM added in-flight batching, paged KV cache, quantized KV options, and speculative decoding plugins for NVIDIA deployments. NVIDIA Dynamo, announced as a disaggregated inference serving stack, and llm-d, the Kubernetes-native distributed inference project, both reflect the same pressure: prefill, decode, KV transfer, and routing become separate scheduling objects once test-time compute dominates. EAGLE, from “Speculative Decoding with Extrapolation Algorithm for Greater Language-model Efficiency,” drafts future tokens using features from the target model so that several decode positions may be accepted per expensive target step.

The technique stops working, or becomes actively bad, when additional tokens do not buy enough marginal accuracy per dollar or when they push the request into the wrong serving regime. If a task is retrieval-bound, policy-bound, or missing information, a $4000$-token scratchpad may only elaborate a false premise while multiplying latency. If the context is already near the model’s effective attention limit, more reasoning can dilute salient evidence and increase lost-in-the-middle failures. If KV memory is the bottleneck, long thoughts reduce concurrency: with the $320$ KiB/token 70B example, adding $5000$ hidden tokens costs another $1.64$ GB per live sequence, so a node that was throughput-efficient at batch $32$ may fall to batch $8$ and lose weight-streaming amortization. Speculative decoding also has a failure regime: when the draft model’s acceptance rate is low on hard reasoning branches, EAGLE-style or TensorRT-LLM speculative paths add draft computation and verification overhead without enough accepted tokens. In production, the right question is not whether more thinking can improve a benchmark, but whether the accuracy lift survives its daily token bill, tail latency, and capacity loss.