LeMiCa: Lexicographic Minimax Path Caching for Efficient Diffusion-Based Video Generation

AI summary

Overview

Research area: Efficient inference for diffusion-based generative models, specifically text-to-video (and text-to-image) synthesis.

Technical level: Intermediate. The paper assumes familiarity with diffusion sampling loops and caching-based acceleration, but the core idea (graph path planning over denoising timesteps) is explained clearly enough for readers with general deep learning background.

Scope: The paper proposes a training-free caching scheduler that reformulates which diffusion timesteps to skip as a worst-case-bounded graph path problem, delivering faster video generation with less content drift than prior heuristic caching methods.

What This Paper Is About

Diffusion video models generate high-quality clips but are slow because they run dozens of denoising steps. A popular shortcut is caching: skip some steps and reuse earlier model outputs. Existing methods decide what to skip using local, step-to-step differences and fixed thresholds. The problem is that small local errors accumulate over the trajectory, so accelerated videos drift in content and lose detail compared with the originals. This paper's goal is to choose which steps to skip using a global, worst-case-aware criterion so that the accelerated video stays faithful to the unaccelerated one, without retraining the model.

Key Contributions

1. A training-free, model-agnostic cache scheduler. LeMiCa reformulates step skipping as traversal of a directed acyclic graph (DAG) whose edges are candidate cache segments, rather than a set of locally greedy threshold decisions. It works on top of any diffusion video backbone without architectural changes or retraining.

2. A Global Outcome-Aware error metric. Instead of measuring the difference between adjacent timestep outputs, the authors weight each candidate cache segment by the error it actually induces in the final denoised video, averaged across many prompts and random seeds. This captures the non-uniform, time-dependent way errors propagate.

3. Lexicographic minimax path optimization. Given a fixed budget of full forward passes B, the method selects the path that lexicographically minimizes the sorted vector of segment errors—shrinking the worst error first, then the second worst, and so on. This explicitly bounds worst-case degradation, which additive shortest-path methods do not.

4. Broad empirical validation. Experiments on Open-Sora 1.2, Latte, and CogVideoX (plus an extension to the Qwen-Image text-to-image model) show simultaneous gains in speed and fidelity over Δ-DiT, T-GATE, PAB, and TeaCache, including under out-of-distribution prompts and altered denoising trajectories.

Main Findings

• Speed and quality improve together, not as a trade-off. On Open-Sora 1.2, LeMiCa-slow reaches a 1.52× speedup with LPIPS 0.050, versus TeaCache-slow's 1.50× with LPIPS 0.134—roughly a 2.7× reduction in perceptual error at comparable latency.
• On Latte, speedup reaches 2.93×. LeMiCa-fast runs at 2.93× with LPIPS 0.273, versus TeaCache-fast at 2.60× with LPIPS 0.318, while preserving VBench quality (76.75% vs. 76.09%).
• CogVideoX gains the largest fidelity margin. LeMiCa-slow achieves LPIPS 0.023 / SSIM 0.958 / PSNR 35.93 at a 1.72× speedup, compared with TeaCache-slow at LPIPS 0.053 / SSIM 0.928 / PSNR 31.07.
• Cache position matters more than cache length. Segment-wise error analysis shows early-trajectory caches amplify downstream error far more than late ones, invalidating fixed-threshold heuristics that treat all timesteps as equally sensitive.
• Lexicographic minimax beats shortest-path. Under matched budgets, the minimax path scores VBench 79.27, LPIPS 0.143, and PSNR 24.67, versus 76.04, 0.203, and 22.90 for a shortest-path baseline—evidence that cache errors are non-additive and cannot simply be summed.
• Very few prompts are needed to build the graph. A single prompt for DAG construction already yields PSNR 24.51, and performance saturates around 10–20 prompts against the 350-prompt upper bound of 24.67. DAG construction and evaluation deliberately use disjoint datasets.
• Robust to trajectory shifts. When the sampling trajectory scale is varied across 0.5–1.5, LeMiCa consistently outperforms TeaCache on LPIPS, despite the cache being precomputed on the default path.
• Robust under distribution shift. On the out-of-distribution IP-VBench (Physical, Biological, Social, Geographical prompts), LeMiCa reaches an overall LPIPS of 0.042 and PSNR 33.5, versus 0.120 and 26.4 for TeaCache.
• Negligible offline cost. Edge-weight estimation takes about 3.18 minutes per prompt and is parallelizable across GPUs; graph construction and path search each finish in under one second. All of this happens once per model configuration, before inference.
• Generalizes to image generation. On the commercial Qwen-Image model, LeMiCa (B=17) achieves 2.45× speedup with LPIPS 0.100, and LeMiCa (B=10) reaches 3.37× with LPIPS 0.253, comparing favorably with Cache-DiT at similar speedups.

Methodology in Plain English

The core observation: During denoising, some steps matter far more than others, and a shortcut taken early in the process causes much larger damage than the same shortcut taken late. Because of this, judging a skip by how similar two adjacent outputs look is misleading—a locally "safe" skip early on can ruin the final video.

Building the map offline: The authors first run full, unaccelerated generation on a handful of prompts. For every possible cache segment—meaning "do a full forward pass at step i, skip from i+1 to j-1, then do a full forward pass at step j"—they replay the trajectory with only that segment cached and measure how much the final video differs from the original. Averaging this across prompts and seeds gives a stable error weight per segment. To keep the graph small, they forbid very long skips, since those are known to be damaging. The result is a directed acyclic graph where nodes are timesteps and edge weights encode real, end-of-pipeline damage.

Choosing a path: Given a target budget of B full forward passes, the problem becomes: find a path from the first timestep to the last that uses exactly B full steps, mixing computed steps and cached segments, while minimizing damage. Rather than minimizing total summed error—which can hide one catastrophic segment behind many good ones—they sort a path's edge errors from largest to smallest and compare paths like dictionary entries: pick the path with the smallest largest error; if tied, compare the second largest; and so on. A dynamic program over (node, steps used) solves this efficiently, storing for each state the best lexicographic error profile and the path that produced it.

At inference: The chosen path is fixed and precomputed. The model simply follows it, computing at B steps and reusing cache elsewhere. There is no runtime overhead, no online threshold tuning, and no additional training.

Why This Matters

For research: The paper reframes cache scheduling from a sequence of online heuristic decisions into a global, offline optimization with an explicit worst-case guarantee. This shifts the framing of a long-standing problem—how to reuse computation in generative sampling—and shows that classical robust control techniques (lexicographic minimax) transfer usefully to diffusion acceleration. It also provides a diagnostic insight, namely that cache errors are non-additive and position-dependent, which other caching work will likely need to confront.

Real-world applications:

• Content creation and social media production, where creators iterate rapidly on text-to-video prompts and need fast turnaround without quality loss.
• Advertising and marketing, where brand-sensitive visuals require content fidelity to the original render and cannot tolerate the object drift or detail loss common in greedy caching.
• Film previsualization and storyboarding, where directors need quick rough renders that still match the intended scene structure for shot planning.
• Cloud and edge deployment, where a 2–3× reduction in forward passes translates directly into lower GPU rental cost per generated clip and makes video synthesis feasible on more constrained hardware.

Industry relevance: Efficiency of video generation is a competitive bottleneck for any company running diffusion models at scale. LeMiCa's training-free, architecture-agnostic nature means it can be layered on top of existing deployed models without retraining budgets, and it composes naturally with orthogonal techniques like distillation, quantization, and sequence parallelism (which the authors already combine with Dynamic Sequence Parallelism for high-resolution, long-video generation across multiple GPUs). The responsible-AI angle is also relevant: fewer forward passes means less energy consumed per generated clip, which the authors explicitly cite as a sustainability benefit. The work comes from China Unicom's AI research institute, suggesting direct interest from a major telecom/cloud operator in serving video generation at scale.

Future Directions

• Handling complex motion and weak base models. The authors acknowledge that when the underlying model struggles—particularly with intricate motion dynamics—the scheduler's advantage shrinks. Whether better error estimation or model-aware weighting can close this gap is open.
• From static to adaptive graphs. The current graph is precomputed once and reused across all prompts. Building per-prompt or per-category graphs, or adapting paths online while preserving the worst-case guarantee, could push both fidelity and speed further.
• Beyond 3× acceleration. The fidelity-focused and speed-focused variants chart a trade-off curve, but high-ratio settings still degrade quality. Tighter worst-case bounds, or combining caching with distillation and quantization into a single joint optimization, may raise the ceiling.
• Transfer to other generative domains. The authors propose extending the framework to 3D, multi-view, and multi-modal generation, where controllable, structure-aware acceleration remains an open problem. Verifying that the non-additive error structure they observe in video also holds in those settings would be a natural next step.

Target Audience

This paper is most useful to researchers and engineers working on efficient generative modeling—particularly those deploying diffusion-based video or image systems where inference latency is a product constraint. It is also valuable to graduate students studying diffusion acceleration, since it offers a clear and well-motivated counterexample to local greedy caching, and to practitioners who need a drop-in, training-free speedup that does not require access to the original training data or model internals. Readers without prior exposure to diffusion sampling loops will need to consult the background material in Section 3.1 first, but the graph-planning idea itself is self-contained and approachable.

Authors’ abstract

We present LeMiCa, a training-free and efficient acceleration framework for diffusion-based video generation. While existing caching strategies primarily focus on reducing local heuristic errors, they often overlook the accumulation of global errors, leading to noticeable content degradation between accelerated and original videos. To address this issue, we formulate cache scheduling as a directed graph with error-weighted edges and introduce a Lexicographic Minimax Path Optimization strategy that explicitly bounds the worst-case path error. This approach substantially improves the consistency of global content and style across generated frames. Extensive experiments on multiple text-to-video benchmarks demonstrate that LeMiCa delivers dual improvements in both inference speed and generation quality. Notably, our method achieves a 2.9x speedup on the Latte model and reaches an LPIPS score of 0.05 on Open-Sora, outperforming prior caching techniques. Importantly, these gains come with minimal perceptual quality degradation, making LeMiCa a robust and generalizable paradigm for accelerating diffusion-based video generation. We believe this approach can serve as a strong foundation for future research on efficient and reliable video synthesis. Our code is available at :https://github.com/UnicomAI/LeMiCa