Diffusion dynamics on graphs arise across many fields including information spreading and rumor cascades in online platforms, propagation of cascading outages in power and transportation infrastructures, diffusion of behaviors and product adoption in social networks, and transmission of shocks in financial and supply-chain systems. Graph diffusion provides a compact representation of how states propagate through interacting entities, yet in many applications the diffusion history is not fully observed. Typically, only a small set of snapshots are available while all other states are missing. Diffusion history reconstruction is challenging due to explosive search space, complex combinatorial constraints, and scarcity of training data. To address these challenges, we propose a new method called HERMES. HERMES has two main stages: (i) diffusion parameter estimation and (ii) diffusion history reconstruction. The first stage is to estimate the unknown diffusion parameters from the observed snapshots. To bypass the intractable maximum likelihood estimation of diffusion parameters, we instead propose a tractable mean-field approximation to estimate diffusion parameters. Second, based on the estimated diffusion parameters, we theoretically reduce history reconstruction to expected hitting time estimation through a bias--variance decomposition and estimate the expected hitting times via Metropolis--Hastings Markov chain Monte Carlo (M--H MCMC). The core component of M--H MCMC is the proposal distribution, and our proposal distribution handles the complex combinatorial constraints via a dynamic reachability mechanism that ensures compatibility with all observed snapshots. Moreover, to further enhance M--H MCMC, we parameterize the proposal using a graph neural network (GNN) and train the GNN to match the posterior distribution. Extensive experiments demonstrate that HERMES consistently outperforms existing methods on 12 synthetic and real-world datasets. Due to the page limit, please find the theoretical proofs at https://q-rz.github.io/static/kdd26/kdd26-hermes-extended.pdf.
Yijing Zuo, Ruizhong Qiu, Ling-Jie Chen et al.· Proceedings of the 32nd ACM...· 1 citation· ⚡1
Large Language Models (LLMs) owe much of their success to next-token prediction (NTP), but their autoregressive (AR) structure requires slow, sequential token generation. To overcome this bottleneck, we introduce diffusion-augmented LLMs, a new class of models that defines an AR model distribution while using diffusion to draw multiple tokens in parallel from that distribution. We decouple the parameters of these models into two sets: AR weights, trained using the standard NTP objective, and lightweight diffusion weights, trained to generate multiple tokens simultaneously. The diffusion weights are learned through a simple Diffusion Distillation phase that adds negligible overhead to existing LLM training pipelines. We also introduce $\Psi$-Spec, a family of samplers that enables lossless acceleration and inference-time scaling at a fixed context length. Unlike speculative decoding, our method requires no separate draft model. Unlike diffusion LLMs (d-LLMs), it accelerates generation without sacrificing the quality of the underlying AR model. The resulting models, called Uno, can be trained from scratch or built by augmenting existing open-weight AR LLMs. Uno achieves higher throughput than leading speculative-decoding methods at every evaluated batch size and delivers up to $3\times$ speedups over the base AR model, including at the largest batch size supported by the device. Notably, our 8B Uno model outperforms the leading open d-LLM, the 26B DiffusionGemma, and the proprietary Mercury 2 across all evaluated benchmarks in agentic tool use, coding, and long-context reasoning. We release code and checkpoints at: https://s-sahoo.github.io/uno/
S. Sahoo, Ling-Jie Chen, Khiem Pham et al.· 0 citations
Diffusion language models (DLMs) have emerged as a promising alternative to the auto-regressive paradigm. With bidirectional attention and any-order generation, DLMs naturally fit infilling tasks, which require generating a middle span conditioned on both the prefix and the suffix. However, infilling is sensitive to the length of the span, while DLMs require the length to be fixed before generation. Although prior studies extend DLMs to dynamic lengths, they still suffer from two limitations. (i) Sensitivity to initial length. These methods require a preset length to initialize the search and are highly sensitive to this initial length, often yielding suboptimal results. (ii) Inference inefficiency. They either insert length-changing operations during generation or repeatedly search for an appropriate length using multi-step denoising confidence, both of which introduce substantial extra forward passes and computational cost. Therefore, we propose PILL (Probing-based InfiLling with preset-Length-free decoding), an efficient infilling method for DLMs that requires no preset initial length and adds far fewer extra forward passes than baselines, substantially reducing inference time. Experiments show that, across five DLMs spanning different families, architectures, and training recipes on eight infilling benchmarks, PILL improves over the strongest baseline by +4.8 average pass rate on code and +6.0 BLEU-2 on text, while running 1.82x faster than that baseline. The code is available at https://github.com/Hsu1023/PILL.
Hao-Bo Xu, Si-Rui Chen, Yuanchen Bei et al.· 0 citations
This work proposes method that unifies textual reasoning and graph message passing within a masked diffusion language model, a language model with bidirectional attention and generative decoding that outperforms graph neural networks, graph transformers, and LLM-based baselines on all three TAG benchmarks across two tasks.
This work proposes a principled VLM TTA method called \algname, and theoretically reveals that the InfoNCE loss can be neatly reformulated as a Wasserstein OT formulation, thereby unifying the objectives of the inference and adaptation of VLMs to achieve their mutual benefits.
Qi Yu, Zhichen Zeng, Katherine Tieu et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
