Copertina

Diffusion Language Models are Provably Optimal Parallel Samplers

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Jiang, Haozhe, Haghtalab, Nika, Chen, Lijie
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Machine Learning Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

Provably Explaining Neural Additive Models
di: Bassan, Shahaf, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Core Safety Values for Provably Corrigible Agents
di: Nayebi, Aran
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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