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 s on MATH500 at . 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 , 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.
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 on4
- The Curious Case of Neural Text DegenerationAri Holtzman, Jan Buys, Li Du, Maxwell Forbes et al.ICLR 2020 · 4,112 citations
- Reasoning with Sampling: Your Base Model is Smarter Than You ThinkAayush Karan, Yilun DuICLR 2026 · 87 citations
- 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
- Proteina: Scaling Flow-based Protein Structure Generative ModelsTomas Geffner, Kieran Didi, Zuobai Zhang, Danny Reidenbach et al.ICLR 2025
Related papers
- ThreadWeaver: Adaptive Threading for Efficient Parallel Reasoning in Language ModelsLong (Tony) Lian, Sida Wang, Felix Juefei-Xu, Tsu-Jui Fu et al.ICML 2026
- Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution SharpeningXiaotong Ji, Rasul Tutunov, Matthieu Zimmer, Haitham Bou AmmarICML 2026 · 17 citations
- 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
- ATTS: Asynchronous Test-Time Scaling via Conformal PredictionJing Xiong, Qiujiang Chen, Fanghua Ye, Zhongwei Wan et al.ICLR 2026 · 8 citations
- Parallel Test-Time Scaling for Latent Reasoning ModelsRunyang You, Yongqi Li, Meng Liu, Wenjie Wang et al.ACL 2026 · 10 citations
