Cover Image

Diffusion Language Models are Provably Optimal Parallel Samplers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jiang, Haozhe, Haghtalab, Nika, Chen, Lijie
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Surjectivity of Neural Networks: Can you elicit any behavior from your model?
by: Jiang, Haozhe, et al.
Published: (2025)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
by: Chen, Bo, et al.
Published: (2025)

Provably Explaining Neural Additive Models
by: Bassan, Shahaf, et al.
Published: (2026)

Provably Overwhelming Transformer Models with Designed Inputs
by: Stambler, Lev, et al.
Published: (2025)

SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
by: Marzouk, Reda, et al.
Published: (2025)

On-Demand Sampling: Learning Optimally from Multiple Distributions
by: Haghtalab, Nika, et al.
Published: (2022)

A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention
by: Ye, Xiaowei, et al.
Published: (2026)

Active Learning for Decision Trees with Provable Guarantees
by: Moakhar, Arshia Soltani, et al.
Published: (2026)

When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?
by: Chen, Yuansi, et al.
Published: (2023)

Large Language Models on Small Resource-Constrained Systems: Performance Characterization, Analysis and Trade-offs
by: Seymour, Liam, et al.
Published: (2024)

From Style to Facts: Mapping the Boundaries of Knowledge Injection with Finetuning
by: Zhao, Eric, et al.
Published: (2025)

Learning With Multi-Group Guarantees For Clusterable Subpopulations
by: Dai, Jessica, et al.
Published: (2024)

Theoretical limitations of multi-layer Transformer
by: Chen, Lijie, et al.
Published: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
by: Hertrich, Christoph, et al.
Published: (2020)

Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?
by: Gölz, Paul, et al.
Published: (2025)

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
by: AbdElhameed, Marwan, et al.
Published: (2024)

On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
by: Ke, Yekun, et al.
Published: (2025)

Additive Models Explained: A Computational Complexity Approach
by: Bassan, Shahaf, et al.
Published: (2025)

Polyhedral Instability Governs Regret in Online Learning
by: Li, Yuetai, et al.
Published: (2026)

Data Debugging is NP-hard for Classifiers Trained with SGD
by: Guo, Zizheng, et al.
Published: (2024)

On Efficiently Representing Regular Languages as RNNs
by: Svete, Anej, et al.
Published: (2024)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
by: Sato, Atsuki, et al.
Published: (2025)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
by: Thornton, Mitchell A.
Published: (2026)

Efficient Parallel Samplers for Recurrent-Depth Models and Their Connection to Diffusion Language Models
by: Geiping, Jonas, et al.
Published: (2025)

Core Safety Values for Provably Corrigible Agents
by: Nayebi, Aran
Published: (2025)

Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
by: Hazra, Rishi, et al.
Published: (2025)

The Optimal Approximation Factor in Density Estimation
by: Bousquet, Olivier, et al.
Published: (2019)

Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm
by: Yao, Jiaqi, et al.
Published: (2026)

AdaBoost is not an Optimal Weak to Strong Learner
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

Near-Optimal Learning and Planning in Separated Latent MDPs
by: Chen, Fan, et al.
Published: (2024)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
by: Merrill, William, et al.
Published: (2025)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
by: Cao, Yang, et al.
Published: (2025)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
by: Huang, Jizhou, et al.
Published: (2025)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
by: Rohatgi, Dhruv, et al.
Published: (2025)

How Global Calibration Strengthens Multiaccuracy
by: Casacuberta, Sílvia, et al.
Published: (2025)

Constant Bit-size Transformers Are Turing Complete
by: Li, Qian, et al.
Published: (2025)