Source-linked AI summary
Chain-of-Trajectories: Unlocking the Intrinsic Generative Optimality of Diffusion Models via Graph-Theoretic Planning
Ping Chen, Xiang Liu, Xingpeng Zhang, Fei Shen, Xun Gong, Zhaoxiang Liu, Zezhou Chen, Huan Hu, Kai Wang, Shiguo Lian
TL;DR
Fixed, content-agnostic diffusion schedules cannot efficiently support adaptive trajectory search in high-dimensional noise manifolds, motivating more deliberate resource allocation. CoTj introduces train-free graph planning based on Diffusion DNA and a Predict-Plan-Execute procedure. Across image and video generation, it reports improved quality, fidelity, and motion coherence with less redundant computation, while identifying future challenges in complex video dynamics.
Problem
High-dimensional diffusion state spaces make explicit sample-specific trajectory search intractable, while fixed schedules can misallocate computation across denoising stages.
Method
CoTj predicts a low-dimensional Diffusion DNA difficulty signature and uses it to compute minimum-cost sampling paths on a directed acyclic graph without retraining.
Results
CoTj discovers context-aware trajectories that improve quality, structural fidelity, and motion coherence while reducing redundant computation across image and video generation.
Takeaways & Limitations
Inference-time planning can allocate computation adaptively in high-dimensional continuous generative spaces and provide diagnostic insight into structural instabilities.
Takeaways & Limitations
Future extensions are needed to model complex video dynamics, including temporal entropy or motion resistance, while preserving coherent motion.
Abstract
from arXiv · showhide
Diffusion models operate in a reflexive System 1 mode, constrained by a fixed, content-agnostic sampling schedule. This rigidity arises from the curse of state dimensionality, where the combinatorial explosion of possible states in the high-dimensional noise manifold renders explicit trajectory planning intractable and leads to systematic computational misallocation. To address this, we introduce Chain-of-Trajectories (CoTj), a train-free framework enabling System 2 deliberative planning. Central to CoTj is Diffusion DNA, a low-dimensional signature that quantifies per-stage denoising difficulty and serves as a proxy for the high-dimensional state space, allowing us to reformulate sampling as graph planning on a directed acyclic graph. Through a Predict-Plan-Execute paradigm, CoTj dynamically allocates computational effort to the most challenging generative phases. Experiments across multiple generative models demonstrate that CoTj discovers context-aware trajectories, improving output quality and stability while reducing redundant computation. This work establishes a new foundation for resource-aware, planning-based diffusion modeling. The code is available at https://github.com/UnicomAI/CoTj.
1. Introduction
Diffusion models commonly use fixed, content-agnostic schedules because explicit adaptive trajectory search is infeasible in high-dimensional noise manifolds. CoTj addresses this by using Diffusion DNA and graph planning to allocate computation adaptively across denoising stages.
- Motivation: Fixed schedules treat diffusion sampling as a System 1 process and distribute computation without adapting to content.Existing efficiency methods reduce function evaluations but generally retain predefined scheduling strategies.
- Motivation: The state dimension curse makes explicit trajectory planning infeasible because diffusion states combine continuous noise, multimodality, and semantic variation.The resulting state-space growth makes traditional search-based planning impractical and prone to local optima.
- Motivation: Local adaptive-step methods remain greedy, motivating a low-dimensional and interpretable representation for globally planning generation paths.The introduction identifies mapping generation into such a latent space as the bottleneck for advanced planning.
- CoTj: CoTj introduces Diffusion DNA, a low-dimensional signature of denoising difficulty that proxies the stochastic state space for deterministic DAG planning.Nodes represent intermediate states, edges represent temporal jumps, and edge costs derive from Diffusion DNA.
- CoTj: Its Predict-Plan-Execute procedure estimates input-conditioned difficulty, computes an optimal path before generation, and requires no base-model retraining with negligible overhead.Different inputs produce distinct Diffusion DNA profiles and adaptive, context-aware trajectories.
- Results: Experiments across image and video generation report improved output stability and quality under equivalent computational budgets while reducing redundant steps.The reported gains accompany a shift from reactive execution toward structured, resource-aware planning.
2. Related Work
Prior diffusion acceleration methods reduce sampling cost through solvers or distillation but largely preserve fixed or baked-in trajectories. CoTj instead performs inference-time planning over a graph, introducing dynamic waypoint selection without retraining the generative model.
- Acceleration: Higher-order solvers reduce function evaluations by lowering discretization error, while distillation compresses trajectories into one or a few steps.These approaches improve sampling latency through solver design or trajectory compression.
- Blind Execution: Distillation fixes a trajectory in model weights, and advanced solvers optimize transitions between predetermined time steps rather than selecting optimal waypoints.Both approaches limit inference-time flexibility in trading computation for quality.
- Reactive versus proactive inference: Reactive methods use local feedback or dataset-level statistics and therefore lack foresight over the global difficulty landscape.The related-work discussion characterizes this behavior as greedy optimization.
- Inference-time planning: CoTj adds a pre-computation planning phase that reasons about an optimal latent path before committing to pixel updates.This separates path estimation from execution in a manner aligned with predict-then-plan control.
- Inference-time planning: CoTj addresses inference-time discretization control by mapping continuous flow onto a discrete graph whose costs derive from reconstruction-error bounds.The resulting minimum-cost path is presented as a discrete counterpart to least-action formulations of generative dynamics.
3. Method: Chain-of-Trajectories
CoTj replaces intractable stochastic trajectory search with deterministic planning over a low-dimensional Diffusion DNA surrogate and a Super-Node DAG. Its Predict-Plan-Execute process selects fixed-budget or adaptive-length denoising paths according to input-conditioned difficulty.
- Diffusion DNA: The canonical state provides a reconstruction-error reference, while transition cost W(t, k) combines the temporal jump factor s(t, k) with Diffusion DNA C(t).The temporal lever increases with jump interval; for linear flow matching, s(t, k) = ((t − k)/t)^2.
- Diffusion DNA: CoTj encodes expected reconstruction difficulty across generative stages as a low-dimensional Diffusion DNA that proxies the high-dimensional diffusion state space.The DNA is defined from timestep-wise reconstruction error along a canonical trajectory.
- Graph-Theoretic Planning: Once Diffusion DNA is computed with T evaluations, transition costs are determined algebraically, collapsing stochastic trajectory optimization into deterministic planning over timestep indices.This avoids stochastic rollouts over the high-dimensional state space.
- Graph-Theoretic Planning: CoTj embeds feasible reverse-time transitions in a dense Super-Node DAG and finds paths by shortest-path search that balances correction cost against global error reduction.The graph includes terminal-risk, information-credit, and transition edges, while the shortest path preserves fidelity relative to the canonical manifold.
- Fixed-Step and Adaptive Planning: The planner supports fixed-step optimization and adaptive-length termination when the explained denoising gain reaches a threshold such as ρth = 0.99.Adaptive planning uses the normalized gain ratio ρ(n) to avoid redundant steps, with longer paths for complex conditions and shorter paths for simpler ones.
- Predict-then-Plan: A lightweight regressor predicts Diffusion DNA from the condition embedding, after which deterministic graph planning produces a trajectory executed by the unchanged diffusion model.Inference follows a predict, plan, and execute loop with minimal overhead.
4. Results
Results show that Diffusion DNA captures structured, input-dependent denoising difficulty, enabling CoTj to concentrate computation along efficient trajectories. Across image and video settings, planned trajectories improve quality, stability, and reachability under constrained or matched budgets while reducing redundant computation.
- Intrinsic Diffusion DNA: Diffusion DNA profiles show structured generative difficulty that is weakly coupled to surface-level prompt semantics.Pairwise DNA similarity concentrates in a high-similarity regime, while semantic-embedding similarity correlates with DNA similarity at r = 0.046.
- Systematic Trajectory Planning: CoTj allocates steps to high-cost transitions and critical texture-forming intervals instead of following rigid schedules.Low-entropy prompts use shortcut-heavy paths, while high-entropy prompts receive denser sampling in difficult intervals.
- Adaptive-Length Planning: As explained gain approaches 0.99, required evaluations rise sharply, exposing diminishing returns in the final fraction of trajectory gain.The transition beyond ρ ≈ 0.99 is consistent across diverse prompts and motivates adaptive termination.
- Compositional Reasoning: At Steps=5, CoTj restores global geometry and semantic alignment where standard linear schedules produce blurred, oversmoothed outputs.CoTj with a 1st-order solver reaches GenEval 0.626 versus 0.528 for Baseline + UCGM, while CoTj + UCGM reaches 0.775.
- Trajectory Reachability: At identical step budgets, CoTj reduces reconstruction error and tracks long high-fidelity reference trajectories more closely than Euler and heuristic baselines.At 10 steps, CoTj reduces MSE by more than 60% and improves PSNR by over 6 dB versus Euler; its planned paths also closely follow the 50-step reference.
5. Conclusion
CoTj equips diffusion models with train-free, System 2-style planning through Diffusion DNA and graph-based trajectory optimization. Experiments across image and video generation report improved quality and structural fidelity with less redundant computation.
- CoTj replaces fixed sampling schedules with Diffusion DNA-guided graph planning that allocates computation to difficult denoising phases.Diffusion DNA is a low-dimensional signature of per-step denoising difficulty.
- Experiments across image and video generation show context-aware trajectories that improve quality, structural fidelity, and motion coherence while reducing redundant computation.
- Diffusion DNA also exposes structural instabilities in distilled or few-step models and guides adaptive planning.
A.1. Proof of Postulate 1: The Upper Bound of Correctability
The proof defines single-step reconstruction error as an upper bound for admissible denoising trajectories. Multi-step paths can reduce truncation error by refining the integration grid under stability conditions.
- C(t) represents the intrinsic reconstruction-error upper bound for an optimal denoising trajectory originating at timestep t.The planning objective is to reduce remaining error below this initial bound.
- A single maximum-step projection from t to 0 ignores probability-flow curvature and accumulates global truncation error.
- The optimal multi-step path has reconstruction error no greater than the trivial single-step path, establishing C(t) as its upper bound.
- Refining the integration grid with intermediate denoising steps provides a piecewise approximation that better follows the true probability flow.The argument assumes locally Lipschitz learned drift or score functions and admissible paths within the region of absolute stability.
A.2. Proof of Postulate 2: The Minimum Error Bound of the Canonical Ideal State
The proof argues that canonical ideal states minimize reconstruction error relative to practical off-manifold states. Numerical integration introduces drift, producing a nonnegative out-of-distribution penalty in the denoiser’s error.
- The canonical ideal state x_t^* has reconstruction error no greater than an off-manifold state x_t produced by practical numerical integration.The proof relies on training over the true forward marginal distribution and locally Lipschitz denoising behavior.
- Practical solver steps create cumulative drift δ_t, so x_t becomes an out-of-distribution perturbation of x_t^*.
- A first-order Taylor expansion decomposes off-manifold reconstruction error into intrinsic error, a Jacobian-weighted drift penalty, and a cross-term.
- Under the conditional-expectation training assumption, the cross-term vanishes in expectation, leaving intrinsic error plus a nonnegative OOD penalty.
- The resulting inequality C(t) ≤ C(x_t,t) provides the theoretical basis for paying trajectory-correction cost to return sampling toward the canonical manifold.
A.3. Ideal Trajectories and the Correction Cost
The appendix models practical solver transitions as deviations from ideal noise trajectories. Their difference defines trajectory correction cost, which is used to approximate transition costs for planning.
- Practical sampling advances x_t to x_k with a solver, whereas ideal states x_t^* and x_k^* lie directly on the forward noise trajectory.
- A solver step from x_t^* to k deviates from the ideal path because numerical integration introduces geometric drift.The first-order approximation covers Euler-type ODE steps and Euler–Maruyama-type SDE steps.
- Analyzing first-order solver behavior yields a temporal scaling factor for approximating general transition costs.
- The difference between the realized and ideal states defines the Trajectory Correction Cost W(t, k).
A.4. Recursive Optimization and Corollary
The section replaces intractable optimization over drifting off-manifold states with correction planning over ideal trajectory states. Under Lipschitz continuity and error amplification, an ideal correction step is guaranteed to achieve no worse a bound, enabling one-dimensional dynamic programming.
- The recursive error bound compares continuing along an uncorrected path with paying a correction cost to return to an ideal trajectory.
- Evaluating off-manifold penalties across all drifting states and timesteps is computationally intractable because of the curse of dimensionality.
- Under intrinsic reverse-time error amplification and Lipschitz continuity, there exists an ideal correction step k whose cost plus correction penalty does not exceed the best off-manifold bound.
- Because the denoiser’s local Lipschitz constant satisfies L ≥1, selecting k = j∗ yields a correction bound no larger than the corresponding off-manifold bound.
- The global minimum therefore lies within the ideal correction set, reducing the outer optimization to tractable one-dimensional dynamic programming over ideal states.
A.5. Global Error Reduction Gain
The dynamic program is expressed as a timestep-sequence optimization that maximizes error reduction gain. Since the initial cost is fixed, this is equivalent to shortest-path minimization on the Super-DAG.
- Dynamic programming searches a decreasing timestep sequence from tj to ti to maximize the error reduction gain.
- Maximizing error reduction gain is algebraically equivalent to minimizing total transition cost plus terminal risk minus the initial risk.
- For a full trajectory, the fixed initial term C(T) reduces optimization to transition costs plus terminal risk C(ti).
- The resulting objective matches Super-DAG shortest-path planning, with transition edges encoding W(tm+1, tm) and terminal edges encoding C(ti).
B. Derivation of the Temporal Lever s(t, k) under Linear Flow
Under linear flow matching, intermediate trajectory deviation is reduced to a time-scaled reconstruction error at the current timestep. This defines the temporal lever s(t, k), with an analogous estimate extending to SDE-based diffusion models.
- Replacing the true velocity with the model prediction makes the intermediate deviation proportional to the reconstruction error of x0 estimated at time t.
- The canonical state x_t^* is formed by linearly interpolating between clean data x0 and Gaussian noise z, while x_k^* is the corresponding earlier ideal state.
- At inference, locally constant predicted velocity enables backward propagation from x_t^* to an estimated intermediate state x_k.
- The intermediate deviation equals (t-k)(v^* - v_t), linking trajectory error to the difference between ground-truth and predicted velocities.
- Squared norms yield the temporal lever s(t, k) = ((t-k)/t)^2, unifying deviations across timesteps through ||x̂0 − x0||^2.
- The predict-then-plan argument is stated to extend to SDE-based diffusion models through an analogous temporal scaling estimated from local reconstruction error.