AsyncSpade: Efficient Test-Time Scaling with Asynchronous Sparse Decoding

Test-time scaling (TTS) can boost LLM reasoning through long chain-of-thought (CoT), but the linear KV-cache growth amplifies the memory-bound bottleneck of LLM decoding. Query-aware sparse decoding methods can achieve state-of-the-art performance under constrained FLOP budget, but are mainly constrained by both sequential-dependent page filtering and coarse-grained token selection, hampering the serving efficiency and model performance on TTS tasks under high concurrency and long CoT scenarios, where token selection can even occupy higher runtime than the forward pipeline itself. In this paper, we first find that the query state of the current decoding token can be approximated in a unified manner from a short sliding window of recent queries, enabling training-free query-aware sparsity without sequential dependency in the decoding loop. Based on the findings, we propose $\texttt{\textbf{AsyncSpade}}$, an asynchronous framework for efficient TTS, built on two core components: $\textbf{(1) a novel light-weight temporal-regressive module}$ that predicts the next-token query state, and $\textbf{(2) an asynchronous disaggregated framework}$ that decouples the KV cache selection from the auto-regressive decoding loop, overlapping the token-level KV selection with the forward inference computation through asynchronism, thereby eliminating the sequential dependency without sacrificing model performance. We validate the effectiveness of $\texttt{AsyncSpade}$ on common LLM serving setups with an A100 node, where $\texttt{AsyncSpade}$ can fully overlap KV-cache operations with the inference pipeline within a certain workload range, $\textbf{achieving theoretical optimal time-per-output-token~(TPOT)}$. Specifically, $\texttt{AsyncSpade}$ delivers over 20% reduction on TPOT compared to SoTA baseline ($\textit{i.e.}$ Quest) and at least 50% TPOT reduction compared to full attention on Qwen3-8B and Qwen3-32B models, while matching or surpassing their accuracy on various TTS benchmarks (AIME-24/25, GPQA-Diamond, MATH-500). Our code is available through https://github.com/UNITES-Lab/AsyncSpade.

AI language models solve hard problems in math, coding, and science far better when they are allowed to think at length before answering, working through long step-by-step solutions. But this thinking is slow, because before producing each new word the model must review everything it has written so far, and as the solution grows longer, this reviewing rather than the reasoning becomes the main thing holding it back. The slowdown makes such models costly to run, especially when serving many users at once. A common way to speed this up is to have the model review only the most relevant part of its earlier work. The drawback is that existing methods decide what is relevant only at the last moment, right before each word, so the model waits for this step every single time. We found that the part a model will need next can be reliably predicted in advance from its recent behavior. Our method, $\texttt{AsyncSpade}$, hands this selection to a separate processor that works ahead of time, in parallel with the model's main computation, so the model never pauses. As a result, $\texttt{AsyncSpade}$ cuts response time by over 20% compared with the best existing method and by more than half compared with the standard approach, all without lowering answer quality, making powerful reasoning models cheaper and more practical to deploy.