acceptodds
Under review as a conference paper at ICLR 2027

ONE VOCABULARY PASS, MANY REQUESTS: A STREAM-ONCE OUTPUT-HEAD KERNEL FOR CONCURRENT LLM DECODING

Abstract

The output head of a large-vocabulary language model is a maximum-inner-product search. Existing exact CPU implementations batch queries or reuse blocked products but do not make a single compact vocabulary-row stream the shared screening unit across concurrent decoder states. FuseHead performs one affine-u8 row traversal, screens each row–query pair, and completes the survivor union in FP32. A public 24-query panel and two held-out groupings verify all canonical FP32 row scores and final token decisions, with additional cancellation, one-ULP, extreme-scale, random, and tie-breaking controls. On an eight-core CPU and a Qwen2.5-0.5B-derived WikiText-2 trace, FuseHead matches all 288 FP32 decisions and reduces median output-head time from 2.542 seconds to 0.591 seconds. Its paired headline speedup over an exact per-panel oracle is 2.03× [1.18,4.10]. When measured no-cache prefix replay is included, end-to-end throughput is 1.09× that of the strongest same-information dense comparator.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
LLM inference, output head, maximum inner-product search, concurrent decoding, vocabulary streaming, CPU serving, quantization, kernel optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_jKo1OpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

FuseHead accelerates CPU-based greedy decoding by combining HNSW initialization, a batch-shared scan of 8-bit vocabulary representations with conservative score bounds, and exact FP32 rescoring of surviving candidates. It preserves the outputs of a specified FP32 reference while reducing full-precision output-head computation. However, the evaluation is restricted to one modified Qwen2.5-0.5B checkpoint, one CPU platform, and a small set of batch sizes and decoding traces. Practical end-to-end gains, applicability to other models and hardware, and support for stochastic decoding remain unverified.

Critical strengths
  1. The idea behind this paper is clearly presented: find cheap threshold through HNSW, use 8 bit computation to compare with this threshold in order to get the candidates and finally use exact FP32 computation to determine the final chosen.
  2. Under the experimental settings FuseHead gets the best performance.
Critical weaknesses
  1. The method/kernel is applied to a narrow scope: cpu, top-1 greedy sampling. It remains unclear whether the method can benefit from other senarios like gpu and topk/topp sampling.
  2. The experiment scope is also limited to Qwen2.5-0.5B checkpoint, one CPU platform, and a small set of batch sizes and decoding traces.
  3. More discussion and ablation study about UNSW and 8-bit computation is needed. The paper acknowledges that the stored error radius is not guaranteed to upper-bound the exact reconstruction error. Consequently, the current implementation does not establish output equivalence for every input.
  4. Lack of practical end-to-end accelration results under different workloads.
Questions for authors
  1. Demonstrate the results on gpu and topk/topp sampling.
  2. Implement on different model sizes among different model families: such as llama-3.2-3b, qwen2.5-7b, llama-3.1-8b.
  3. Please analyze the trade-off between HNSW initialization quality and pruning efficiency by varying ef and the number of initial candidates.
  4. A bit-width sensitivity study, together with a breakdown of quantization and rounding margins would clarify why 8-bit is chosen.
  5. Provide practical end-to-end accelaration results under different workloads on at least a model.
Reviewer_XEohOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents FuseHead, which performs a shared 8-bit vocabulary scan for concurrent greedy decoding on CPU. It leverages per-request score upper bounds to prune most vocabulary entries, and only scores a small set of candidates using the original FP32 weights. The design aims to accelerate the output head while preserving token selections from the reference FP32 implementation.

Critical strengths

The problem is well-defined and the approach is clever. It combines shared vocabulary reads across requests with precise scoring only for entries that could potentially be selected, rather than simply quantizing the entire output head.

The implementation is carefully considered. The paper addresses floating-point rounding, overflow, tie-breaking rules, and thread state restoration, and validates upper bounds line-by-line on test inputs. This is more convincing than merely reporting “288/288 identical tokens”.

The authors are transparent about limitations. They clearly present slowdown cases, tail latency, performance degradation under memory pressure, as well as the limits of their proofs and end-to-end evaluations.

Critical weaknesses
  • The core claim of general exactness is not fully established. The error radius may underestimate the true error, so the guarantee that the upper bound holds for arbitrary inputs remains incomplete. exhaustive checks over a limited set of inputs cannot substitute for a general proof.

  • Speedup is not robust. The main experiments show notable slowdown cases, where FuseHead’s 95th-percentile latency exceeds that of the exact oracle. at batch size 24, the speedup range even includes 1×. For serving kernels, tail latency matters just as much as average performance.

  • Baselines could be further optimized. The authors acknowledge that some baselines are not fully tuned: for example, LEMP-LI prunes zero entries under the current setup, and the top-1 selection of the exact oracle runs substantially faster in standalone tests. This complicates interpretation of the reported speedups.

  • The evaluation scope is narrow. Experiments are limited to one specially trained Qwen2.5-0.5B checkpoint, a single CPU machine, a maximum batch size of 24, and greedy decoding. The held-out set contains only 36 hidden states. The paper has not evaluated realistic request arrival patterns, full serving stacks with KV caching, or other models and hardware.

Questions for authors
  1. Can you compute an error radius offline with directed rounding that is provably guaranteed to cover the true error, and re-report both speed and correctness results?
  2. After re-tuning the exact oracle and LEMP-LI, what are the corresponding speedups and tail latency numbers?
  3. Does the 8-bit shared scan still yield benefits under larger batches, alternative models, and realistic serving workloads? How much of the gain comes from low-cost upper-bound filtering versus shared cross-request reads, respectively?

I would be open to raising my score if the authors adequately address my concerns

Reviewer_NkGuOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents FUSEHEAD, a CPU kernel designed to accelerate exact greedy token selection (maximum inner product search, MIPS: arg⁡max⁡i∈{0,…,V−1}wi⊤h\arg\max_{i \in \{0,\dots,V-1\}} w_i^\top h) during concurrent LLM decoding. For models featuring large vocabulary-to-hidden dimension ratios (e.g., Qwen2.5-0.5B with d=896d = 896 and V=151,936V = 151,936, where the FP32 output head takes 544.5 MB and represents 27.6% of per-token parameters), the output layer forms a significant computational bottleneck.

FUSEHEAD operates in three stages:

  1. Warm start: Proposes candidate tokens per request using an HNSW index (ef=16ef = 16, 8 candidates) augmented with special/frequent tokens, scoring them in FP32 to establish a baseline threshold ℓb\ell_b.
  2. Single-pass 8-bit pruning: Quantizes the vocabulary offline into affine 8-bit integers (cik=round((wik−ai)/si)c_{ik} = \text{round}((w_{ik} - a_i)/s_i)). The kernel streams the 8-bit vocabulary exactly once across all BB concurrent requests in CPU registers (AVX2), computing a strict upper bound UibU_{ib} that accounts for quantization error and floating-point directed upward rounding (including γd(32),γd(64)\gamma_d^{(32)}, \gamma_d^{(64)}, and subnormal η32\eta_{32}).
  3. Exact FP32 re-scoring: Gathers the union of surviving candidates across the batch S=⋃bSb\mathcal{S} = \bigcup_b \mathcal{S}_b, reads them once from the original FP32 matrix, and scores them with reference tie-breaking.

Evaluated on an 8-core AMD EPYC 7742 with batch sizes B∈{8,12,24}B \in \{8, 12, 24\} on a 24-prompt WikiText-2 trace (288 token decisions) and two held-out groupings, FUSEHEAD prunes down to a median of 2 rows per request (scoring only 0.066% of the vocabulary in FP32). It achieves a 2.03$\times$ [1.18, 4.10] paired speedup over an exact oracle baseline while guaranteeing 100% exact numerical agreement with the full FP32 reference.

Critical strengths
  1. Mathematically Sound and Rigorously Certified Exact Bounding: Unlike approximate nearest neighbor methods (e.g., HNSW, FastScan) that alter output token sequences, FUSEHEAD constructs a provable upper bound that rigorously covers both 8-bit quantization error and IEEE-754 directed rounding (controlling the MXCSR register for upward rounding and subnormals). Across all 288 main-trace decisions and held-out traces, it achieves 100% exact token agreement with canonical FP32 greedy decoding without triggering dense fallback.

  2. Commendable Scientific Honesty and Transparency: The authors deserve significant credit for their uncommonly transparent reporting in Section 6 and Appendix A. Rather than concealing edge-case regressions, the paper explicitly documents that speedups at B=24B = 24 cross 1.0 (95% CI: [0.73, 2.36]), details tail-latency regressions (p95p95 latency is 1.57$\times$ higher than the oracle), and shows that performance drops to 0.873$\times$ under memory bus pressure. This level of empirical candor is exemplary.

Critical weaknesses
  1. Highly Constrained Setting and Vanishing Speedup at Practical Serving Scales:
  • Greedy-Only Restriction: FUSEHEAD is strictly limited to arg⁡max⁡\arg\max decoding. Modern LLM serving systems overwhelmingly rely on stochastic sampling (temperature, top-pp, min-pp), which fundamentally requires computing logits across the vocabulary or broad subsets, rendering this kernel inapplicable to most production workloads.
  • Vanishing Gains as Batch Size Grows: The per-request latency advantage of FUSEHEAD diminishes rapidly as batch size increases (Figure 2b). At B=24B = 24, the paired speedup over the exact oracle drops to 1.31$\times$ with a 95% confidence interval of [0.73, 2.36] (statistically indistinguishable from parity). Because batched matrix multiplication amortizes vocabulary weight streaming across requests, standard BMM will inevitably outperform FUSEHEAD at higher concurrent batch sizes (B≥32B \ge 32).
  • Negligible End-to-End Speedup: When evaluated in an end-to-end setting (Section 4.4), the throughput improvement is merely 8.8% (1.088$\times$). Crucially, this was benchmarked without a KV-cache (recomputing prefixes from scratch). In a realistic serving engine equipped with an optimized KV-cache, the relative end-to-end speedup would be further diluted.
  1. Tail Latency and Memory Saturation Regressions:
  • Tail Latency Degradation: FUSEHEAD's 95th-percentile per-token latency is 229.0 ms, which is significantly worse than the exact oracle (145.4 ms) and FP32 SGEMM (130.8 ms). The multi-phase pipeline (HNSW search + streaming 8-bit pass + dynamic exact gather) introduces substantial latency variance.
  • Memory Bus Sensitivity: Under background memory traffic (Appendix A, four threads streaming 66.2 GB/s), FUSEHEAD's speedup over the exact oracle drops to 0.873$\times$ [0.521, 1.652]. Because modern CPU LLM inference is severely memory-bandwidth bound during attention decoding, this sensitivity undermines its deployment viability in real multi-tenant serving nodes.
  1. Extremely Narrow Empirical Benchmark:
  • The empirical validation relies on only 24 WikiText prompts generating 12 tokens each (288 total token decisions).
  • The evaluation is confined to a single, non-standard checkpoint (Qwen2.5-0.5B subjected to 120 additional fine-tuning steps, rather than the clean public release) on a single 8-core CPU. Moreover, Qwen2.5-0.5B has an unusually skewed head-to-backbone parameter ratio (d=896,V=151,936d = 896, V = 151,936, where the head is ~28% of weights). On standard models (e.g., Llama-3-8B where the head represents <7%<7\% of weights), the potential benefit is drastically lower.
Questions for authors
  1. Checkpoint Rationale: Why was the public Qwen2.5-0.5B model fine-tuned for an additional 120 steps rather than evaluated directly out of the box? Does the original public checkpoint exhibit different activation norms or logit margins that affect row pruning efficiency?
  2. Generalization across Hidden Dimensions: For standard architectures where the output head forms a much smaller percentage of model weights (e.g., Llama-3 with d=4096,V=128,256d = 4096, V = 128,256), how does the tradeoff between the single 8-bit streaming pass and dense SGEMM evolve?
  3. Realistic KV-Cache Serving Benchmark: Section 4.4 evaluated the full model by recomputing prefixes without a KV-cache. What is the measured wall-clock speedup when FUSEHEAD is integrated into a modern CPU inference engine (such as llama.cpp or OpenVINO) with standard KV-cache management?
  4. Directed Rounding for Error Radius: Section 6 acknowledges that ρ~i\tilde{\rho}_i is computed via standard FP64 subtraction and is not strictly proven to be an upper bound of ρi∗\rho_i^*. If an interval enclosure with directed rounding is computed offline to guarantee mathematical closure, does it noticeably widen the bound and degrade pruning ratios?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.