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

1. Problem Statement

Video diffusion models represent one of the most computationally expensive generative workloads. Test-time search strategies (e.g., Best-of-N), which sample multiple candidates to select the highest-scoring output via a verifier, exacerbate this cost by 2–10×. In standard Best-of-N, every candidate is generated at full computational cost, even though the majority are discarded.

While training-free caching techniques exist to accelerate individual rollouts by reusing features across denoising steps (yielding 2–3× speedups), their application to test-time search has been unexplored. The core obstacle is subtle: caching is lossy. While it may preserve pixel-level fidelity in seed-matched comparisons, it is unclear whether it preserves the relative ordering of candidates under a verifier. If caching reshuffles the rankings, the search process may select the wrong candidate, negating the efficiency gains. This paper addresses whether caching corrupts candidate rankings in video test-time search and proposes a method to leverage caching safely.

2. Methodology: CachedSearch

The authors propose CachedSearch, a training-free, verifier-agnostic protocol that decouples exploration from delivery. The method operates on the principle that while pixel fidelity may degrade slightly under caching, the relative ranking of candidates often remains intact.

Core Workflow

1. Exploration (Cheap): Generate $N$ candidates using aggressive caching. A wrapper intercepts transformer calls and skips computation when the accumulated input drift is below a threshold $\tau$.
2. Scoring: Score all $N$ cached candidates using a verifier (e.g., ImageReward).
3. Selection: Identify the seed corresponding to the highest-scoring cached candidate.
4. Commit (Full): Regenerate only the winning seed at full computational cost (without caching) to produce the final output.

Technical Implementation

• Adaptive Transformation-Vector Caching: The method wraps the Diffusion Transformer (DiT) using a variation of EasyCache. Instead of caching raw outputs, it caches the transformation vector $\Delta = v_\theta(x_{ref}) - x_{ref}$.
• Skip Rule: An accumulated drift indicator $a$ tracks the relative change in latent inputs. If $a \le \tau$, the transformer call is skipped, and the approximation $\hat{v}_\theta(x) = x + \Delta$ is used. Once $a > \tau$, the transformer is evaluated, and the state is refreshed.
• Determinism: The process is deterministic for fixed $(c, s, \tau)$, ensuring that the "commit" phase reproduces the exact full-compute sample for the selected seed.
• Cost Model: The cost of CachedSearch is $N \cdot C_c + C_f$, where $C_c$ is the cached rollout cost and $C_f$ is the full cost. This is significantly cheaper than full Best-of-N ($N \cdot C_f$) when $N > N^* = 1/(1-\gamma)$, where $\gamma = C_c/C_f$.

3. Key Contributions

• First Ranking-Preservation Study: The paper provides the first empirical study on whether caching preserves candidate rankings under test-time search. It establishes a seed-matched protocol evaluated on the gate grid, VBench, and VBench-2.0.
• The "Explore-Cheap, Commit-Full" Protocol: Introduces CachedSearch, which retains 94.7% of the reward gain of full Best-of-8 search at only 63% of the wall-clock cost.
• Analysis of Corruption: Demonstrates that ranking errors are "self-limiting." Corruption concentrates on prompts where candidates are nearly tied (low score spread). In these cases, selecting the "wrong" candidate incurs minimal regret.
• Generalizability: Shows that the method transfers across six models and four architecture families (Wan, LTX, CogVideoX, Hunyuan) spanning 1.3B to 14B parameters, requiring only a single parameter ($\tau$) recalibration per family.
• Composability: Proves that CachedSearch stacks multiplicatively with candidate pruning methods, achieving a 3.11× exploration speedup.

4. Experimental Results

The evaluation was conducted primarily on Wan2.1-T2V-1.3B, with replication on larger models and different suites.

• Ranking Preservation:
  • On the VBench suite (946 prompts), the median per-prompt Spearman rank correlation ($\rho$) between cached and full scores is 0.905.
  • Top-1 agreement (selecting the same best candidate) is 72%.
  • VBench-2.0 (a harder suite) replicates these results with $\rho = 0.881$.
• Efficiency and Gain Capture:
  • At $N=8$, CachedSearch captures 94.7% of the reward gain of full Best-of-8 at 63% of the cost.
  • Under a fixed budget, it allows searching twice as wide (e.g., 8 candidates vs. 4), yielding 38% more reward than full Best-of-4.
  • The method scales with width: at $N=16$, it captures 95.7% of the gain at 57% of the cost.
• Regret Analysis:
  • Mean regret is low (0.056 on VBench), with a median of 0.
  • 72% of prompts incur zero regret.
  • Errors occur primarily in low-spread scenarios where the value of the correct selection is inherently low.
• Model Generality:
  • The method works across the 1.3B–14B scale. Wan2.1-14B achieves the same median $\rho$ (0.905) as the 1.3B model.
  • Off-family models (e.g., CogVideoX-5B) require recalibrating $\tau$ (e.g., from 0.10 to 0.05) to maintain high capture rates (>85%).
• Comparison to Alternatives:
  • Compared to "step truncation" (reducing denoising steps), caching preserves significantly more search value (90.1% capture vs. 72.6% for truncation) because it perturbs the same trajectory rather than sampling a different distribution.
  • It is compatible with various caching engines (PAB, CFG-Cache, TeaCache), forming a unified capture-vs-speedup frontier.

5. Significance and Claims

The paper claims that CachedSearch is a "plug-in multiplier" for test-time scaling in video diffusion. Its significance lies in:

1. Decoupling Fidelity from Ranking: It demonstrates that for search purposes, candidates do not need to be pixel-perfect; they only need to be "honest" about their relative ordering.
2. Cost Reduction without Training: It achieves near-lossless quality retention and significant cost reduction (up to 3.11× when combined with pruning) without fine-tuning or modifying model weights.
3. Scalability: The approach is orthogonal to the search algorithm and verifier, making it applicable to any sample-then-rank loop.
4. Practical Impact: It enables smaller models (e.g., 1.3B) to rival larger ones by allowing wider search spaces within the same computational budget, effectively democratizing high-quality video generation.

The authors conclude that the lesson extends beyond caching: any lossy accelerator can support exploration if it passes a ranking-plus-regret audit, suggesting a new direction for allocating budgets across accelerators in generative AI.