Lune

ICML2026Top-tier venue

Cache Coherent Resampling for Efficient Test Time Scaling in LLM Reasoning via Adaptive Sequential Monte Carlo

Ke Wang, ZEHAO Yu, Luwei Wang, Yongchao Huang

Abstract

Recent work shows that chain based sampling for power shaped trajectory distributions can deliver large test time gains from a fixed base LLM and can approach RL trained reasoners such as GRPO. Deployment is the bottleneck. Autoregressive Metropolis Hastings is inherently serial, limits GPU utilization, and exhibits extreme tail latency at high budgets, reaching p95 =1318=1318s on MATH500 at 128×128\times. We propose Adaptive Sequential Monte Carlo (ASMC), a parallel particle inference method that targets power shaped trajectory distributions while adapting particle populations to problem hardness. To make resampling practical for Transformers, we introduce cache coherent resampling, which realizes ancestry updates by reordering KV caches and other particle bound tensors, avoiding prefix recomputation. On MATH500 at the same budget, ASMC attains 80.6% exact-match accuracy with p95 = 73.7s, substantially reducing the tail latency of sequential MCMC and providing additional high-accuracy operating points beyond the saturation of best-of-n. We further analyze particle degeneracy and find that collapse severity, measured by low ESSmin⁡/N\mathrm{ESS}_{\min}/N, strongly predicts failures, while sensitivity to the resampling scheme is limited.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Reasoning with Sampling: Your Base Model is Smarter Than You Think cites QUEST: Quality-Aware Metropolis-Hastings Sampling for Machine Translation
  • Reasoning with Sampling: Your Base Model is Smarter Than You Think cites Proteina: Scaling Flow-based Protein Structure Generative Models
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on4

  1. The Curious Case of Neural Text DegenerationAri Holtzman, Jan Buys, Li Du, Maxwell Forbes et al.ICLR 2020 · 4,112 citations
  2. Reasoning with Sampling: Your Base Model is Smarter Than You ThinkAayush Karan, Yilun DuICLR 2026 · 87 citations
  3. QUEST: Quality-Aware Metropolis-Hastings Sampling for Machine TranslationGonçalo Rui Alves Faria, Sweta Agrawal, António Farinhas, Ricardo Rei et al.NeurIPS 2024 · 23 citations
  4. Proteina: Scaling Flow-based Protein Structure Generative ModelsTomas Geffner, Kieran Didi, Zuobai Zhang, Danny Reidenbach et al.ICLR 2025

Related papers

  1. ThreadWeaver: Adaptive Threading for Efficient Parallel Reasoning in Language ModelsLong (Tony) Lian, Sida Wang, Felix Juefei-Xu, Tsu-Jui Fu et al.ICML 2026
  2. Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution SharpeningXiaotong Ji, Rasul Tutunov, Matthieu Zimmer, Haitham Bou AmmarICML 2026 · 17 citations
  3. Adaptive Draft Sequence Length: Enhancing Speculative Decoding Throughput on PIM-Enabled SystemsRunze Wang, Qinggang Wang, Haifeng Liu, Long Zheng et al.HPCA 2026 · 1 citation
  4. ATTS: Asynchronous Test-Time Scaling via Conformal PredictionJing Xiong, Qiujiang Chen, Fanghua Ye, Zhongwei Wan et al.ICLR 2026 · 8 citations
  5. Parallel Test-Time Scaling for Latent Reasoning ModelsRunyang You, Yongqi Li, Meng Liu, Wenjie Wang et al.ACL 2026 · 10 citations
Dusk over the sea between two cliffs drawn in fine vertical lines