A Differentiable Bayesian Relaxation for Latent Partial-Order Inference
This work provides a new method for inferring partial orders from linear traces, benefiting researchers analyzing ranking or agent trace data where latent structure is partially ordered.
The authors introduce a differentiable relaxation for inferring latent partial orders from linear-order traces, enabling gradient-based inference. Experiments show close posterior fidelity to hard MCMC on small instances and improved runtime-accuracy trade-offs on larger problems.
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.