CachedSearch: Training-Free Cached Exploration for Test-Time Search in Video Diffusion

Test-time search reliably improves a pretrained video diffusion model, sample N candidates,scorethemwithaverifier,andkeepthebest. Butitiswastefulasevery candidateisfullydenoised,whileallbutonearediscarded. Weobservethatsearch uses only the verifier’s ranking of discarded candidates, not their pixels. A cheap, lossy rollout that preserves this ranking can therefore replace full generation dur- ing search. Training-free feature caching provides such a rollout. On 7,552 seed- matched cached and full-compute Wan2.1-T2V-1.3B videos on VBench, caching that halves candidate cost preserves verifier rankings with a median per-prompt Spearman correlation of 0.905. Its errors occur mostly among nearly tied candi- dates, yielding zero median regret. Under a Gaussian-copula model, the fraction of search gain preserved under ranking noise equals the latent rank correlation for every N, so cheaper candidates can widen search without compounding er- ror. CachedSearch explores all candidates with aggressive caching, then regen- erates only the winner at full compute from its seed, always returning an exact full-compute sample. At N = 8, it retains 94% of best-of-8’s reward gain at 63% of its cost. For under 2% more cost than best-of-4, it searches six candidates and achieves 11% more gain on VBench; with candidate pruning, it explores candi- dates 3.12×more cheaply than best-of-8. CachedSearch requires no training and applies to any sample-and-rank search with a training-free cache and verifier. Asinglethreshold,calibratedon50prompts,retainsatleast85%ofthegainwith 1.8–2.4×cheaper candidates on five of six models across four families, ranging from 1.3B to14B parameters. Code willbereleased.