# A Differentiable Bayesian Relaxation for Latent Partial-Order Inference

arXiv: https://arxiv.org/abs/2605.06976 · HTML: https://mlsanity.com/paper/2605.06976/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 16 of 16)

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Automatic Differentiation Variational Inference](https://mlsanity.com/paper/1603.00788/) (2016)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [Probabilistic Embedding of Knowledge Graphs with Box Lattice Measures](https://mlsanity.com/paper/1805.06627/) (2018)
- [Understanding predictive information criteria for Bayesian models](https://mlsanity.com/paper/1307.5928/) (2013)
- [BayesDAG: Gradient-Based Posterior Inference for Causal Discovery](https://mlsanity.com/paper/2307.13917/) (2023)
- [Hierarchical Density Order Embeddings](https://mlsanity.com/paper/1804.09843/) (2018)
- [Learning Rich Rankings](https://mlsanity.com/paper/2312.15081/) (2023)
- [Bayesian mixture of Plackett-Luce models for partially ranked data](https://mlsanity.com/paper/1501.03519/) (2015)
- [Statistical Models of Top-k Partial Orders](https://mlsanity.com/paper/2406.15893/) (2024)
- [Bayesian inference for partial orders from random linear extensions: power relations from 12th Century Royal Acta](https://mlsanity.com/paper/2212.05524/) (2022)
- [Pseudo-Mallows for Efficient Probabilistic Preference Learning](https://mlsanity.com/paper/2205.13911/) (2022)
- [Bayesian Inference for Vertex-Series-Parallel Partial Orders](https://mlsanity.com/paper/2306.15827/) (2023)

## Abstract (arXiv)

Many ranking and agent trace datasets are recorded as linear orders even though their latent structure is only partially ordered. This is especially common in agent and workflow traces, where observed order may reflect arbitrary linearization rather than true prerequisites. We introduce a differentiable relaxation for latent partial-order inference from such traces. Starting from a hard frontier-constrained model of noisy linear extensions, we replace discontinuous product-order precedence and binary frontier feasibility with smooth surrogates, yielding a continuous posterior that preserves closure-level partial-order semantics and supports gradient-based MCMC and variational inference. We prove soft transitivity, sharp-limit frontier recovery, and convergence to the hard likelihood. Experiments on synthetic data, records of social dominance relations, and cloud-agent traces show close posterior fidelity to hard MCMC on small instances and improved runtime--accuracy trade-offs on larger problems.