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

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$s on MATH500 at $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 $\mathrm{ESS}_{\min}/N$, strongly predicts failures, while sensitivity to the resampling scheme is limited.

Large language models can solve harder problems when they are allowed to spend more time exploring possible answers, but many existing methods do this one attempt at a time, making them slow for difficult questions. This paper introduces Adaptive Sequential Monte Carlo, a method that keeps many candidate solutions active in parallel so modern GPUs can process them more efficiently. It also reuses the model’s internal memory when candidates are copied or replaced, avoiding costly recomputation. On math and coding benchmarks, the method improves worst-case response time while maintaining strong accuracy. The current evidence is strongest for tasks with clear correct answers, such as math and code.