Dongqing Li et al. Introduce Differentiable Bayesian Relaxation for Partial Order Inference

Many real-world datasets—such as workflow logs, agent traces, and social dominance records—are recorded as linear orders even though their underlying structure is only partially ordered. This arbitrary linearization obscures true prerequisites and causal relationships. Existing methods rely on hard, discontinuous constraints that are computationally expensive and difficult to scale.

To address this, Dongqing Li, Geoff K. Nicholls, Shiyi Sun, and You Luo propose a differentiable Bayesian relaxation that replaces the hard product-order precedence and binary frontier feasibility with smooth surrogates. The resulting continuous posterior preserves partial-order semantics while unlocking gradient-based inference techniques like MCMC and variational inference. The authors prove soft transitivity, sharp-limit frontier recovery, and convergence to the original hard likelihood. Experiments on synthetic data, social dominance relations, and cloud-agent traces demonstrate that the method achieves close posterior fidelity to hard MCMC on small instances and significantly improved runtime–accuracy trade-offs on larger problems. This work opens the door to scalable, gradient-based Bayesian inference for latent partial-order structures in sequential data.