Imagen de Portada

Diffusion Language Models are Provably Optimal Parallel Samplers

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Jiang, Haozhe, Haghtalab, Nika, Chen, Lijie
Formato:	Preprint
Publicado:	2025
Materias:	Machine Learning Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

Provably Explaining Neural Additive Models
por: Bassan, Shahaf, et al.
Publicado: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Core Safety Values for Provably Corrigible Agents
por: Nayebi, Aran
Publicado: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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