We propose a principled and effective framework for one-step generative modeling. We introduce the notion of average velocity to characterize flow fields, in contrast to instantaneous velocity modeled by Flow Matching methods. A well-defined identity between average and instantaneous velocities is derived and used to guide neural network training. Our method, termed the \textit{MeanFlow} model, is self-contained and requires no pre-training, distillation, or curriculum learning. MeanFlow demonstrates strong empirical performance: it achieves an FID of 3.43 with a single function evaluation (1-NFE) on ImageNet 256$\times$256 trained from scratch, significantly outperforming previous state-of-the-art one-step diffusion/flow models. Our study substantially narrows the gap between one-step diffusion/flow models and their multi-step predecessors, and we hope it will motivate future research to revisit the foundations of these powerful models.

Conventional wisdom holds that autoregressive models for image generation are typically accompanied by vector-quantized tokens. We observe that while a discrete-valued space can facilitate representing a categorical distribution, it is not a necessity for autoregressive modeling. In this work, we propose to model the per-token probability distribution using a diffusion procedure, which allows us to apply autoregressive models in a continuous-valued space. Rather than using categorical cross-entropy loss, we define a Diffusion Loss function to model the per-token probability. This approach eliminates the need for discrete-valued tokenizers. We evaluate its effectiveness across a wide range of cases, including standard autoregressive models and generalized masked autoregressive (MAR) variants. By removing vector quantization, our image generator achieves strong results while enjoying the speed advantage of sequence modeling. We hope this work will motivate the use of autoregressive generation in other continuous-valued domains and applications. Code is available at [https://github.com/LTH14/mar](https://github.com/LTH14/mar).

Generative processes that involve solving differential equations, such as diffusion models, frequently necessitate balancing speed and quality. ODE-based samplers are fast but plateau in performance while SDE-based samplers deliver higher sample quality at the cost of increased sampling time. We attribute this difference to sampling errors: ODE-samplers involve smaller discretization errors while stochasticity in SDE contracts accumulated errors. Based on these findings, we propose a novel sampling algorithm called \textit{Restart} in order to better balance discretization errors and contraction. The sampling method alternates between adding substantial noise in additional forward steps and strictly following a backward ODE. Empirically, Restart sampler surpasses previous SDE and ODE samplers in both speed and accuracy. Restart not only outperforms the previous best SDE results, but also accelerates the sampling speed by 10-fold / 2-fold on CIFAR-10 / ImageNet $64{\times} 64$. In addition, it attains significantly better sample quality than ODE samplers within comparable sampling times. Moreover, Restart better balances text-image alignment/visual quality versus diversity than previous samplers in the large-scale text-to-image Stable Diffusion model pre-trained on LAION $512{\times} 512$. Code is available at https://github.com/Newbeeer/diffusion_restart_sampling

Knapsack and Partition are two important additive problems whose fine-grained complexities in the (1 — ε)-approximation setting are not yet settled. In this work, we make progress on both problems by giving improved algorithms.

Unbounded SubsetSum is a classical textbook problem: given integers w1,w2, …, wn∈[1,u], c,u, we need to find if there exists m1,m2, …, mn ∈ ℕ satisfying c =Σni=1 wimi. In its all-target version, t ∈ ℤ+ is given and the answers for all integers c ∈ [0, t] are required. In this paper, we study three generalizations of this simple problem: All-Target Unbounded Knapsack, All-Target CoinChange and Residue Table. With new combinatorial insights into the structures of solutions, we present a novel two-phase approach. As a result, we show that: • All-Target CoinChange can be solved in Õ(u +t) time deterministically, improving the previous Õ(t4/3) time algorithm [Chan and He, ESA 2020]. • Residue Table can be solved in Õ(u) time deterministically, improving the previous Õ(u3/2) time algorithm [Klein, 2021]. •All-Target Unbounded Knapsack can be solved in Õ(T(u) + t) time, where is the running time for (min, +) convolution for length-n arrays, improving the previous O(u2 log u + t) time algorithm [Chan and He, ESA 2020].

A simplicial vertex of a graph is a vertex whose neighborhood is a clique. It is known that listing all simplicial vertices can be done in $O(nm)$ time or $O(n^ω)$ time, where $O(n^ω)$ is the time needed to perform a fast matrix multiplication. The notion of avoidable vertices generalizes the concept of simplicial vertices in the following way: a vertex $u$ is avoidable if every induced path on three vertices with middle vertex $u$ is contained in an induced cycle. We present algorithms for listing all avoidable vertices of a graph through the notion of minimal triangulations and common neighborhood detection. In particular we give algorithms with running times $O(n^{2}m)$ and $O(n^{1+ω})$, respectively. Additionally, based on a simplified graph traversal we propose a fast algorithm that runs in time $O(n^2 + m^2)$ and matches the corresponding running time of listing all simplicial vertices on sparse graphs with $m=O(n)$. Moreover, we show that our algorithms cannot be improved significantly, as we prove that under plausible complexity assumptions there is no truly subquadratic algorithm for recognizing an avoidable vertex. To complement our results, we consider their natural generalizations of avoidable edges and avoidable paths. We propose an $O(nm)$-time algorithm that recognizes whether a given induced path is avoidable.