Contextual Plackett–Luce: An Efficient Neural Model for Probabilistic Sequence Selection under Ambiguity

Noam Mizrachi, Nadav Har-Tuv, Shai Shalev-Shwartz · 2026

Read Contextual Plackett–Luce: An Efficient Neural Model for Probabilistic Sequence Selection under Ambiguity by Noam Mizrachi, Nadav Har-Tuv, Shai Shalev-Shwartz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-09112.txt.

Introduction

Noam Mizrachi, Nadav Har-Tuv, and Shai Shalev-Shwartz address tasks where a system must pick a coherent sequence or subset, such as forecasting a path or choosing representative items. The catch is ambiguity: many answers can be valid, but training data shows only one sampled answer for each input.

Their model, Contextual Plackett-Luce, extends a classic ranking model so its scores depend on context, with terms for single items and pairs. Scoring runs in parallel for speed, then a light step-by-step selection keeps the output coherent. On path prediction and subset selection tasks, the model gave more consistent and robust results than strong parallel rivals when supervision was ambiguous.

Catalog record

CREATORNoam Mizrachi, Nadav Har-Tuv, Shai Shalev-Shwartz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.09112

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Contextual Plackett–Luce: An Efficient Neural Model for Probabilistic Sequence Selection under Ambiguity Noam Mizrachi, Nadav Har-Tuv, Shai Shalev-Shwartz Abstract Selecting a coherent sequence or subset of elements is a fundamental problem in structured prediction, arising in tasks such as detection, trajectory forecasting, and representative subset selection. In many such settings, the target is inherently ambiguous: each input admits multiple valid outputs, while supervision provides only a single sampled instance. This induces a mismatch between the underlying multi-modal target distribution and the observed training signal. We propose Contextual Plackett–Luce (CPL), a structured probabilistic model for sequence selection that extends the classical Plackett–Luce model to a context-dependent setting following an Ising-style parameterization with unary and pairwise interaction terms. CPL can be viewed as a hybrid between fully autoregressive prediction and parallel sequence selection: autoregressive models effectively capture uncertainty but are computationally expensive on modern parallel hardware such as GPUs, while parallel methods are efficient but struggle to represent multi-modal dependencies. CPL combines the strengths of both by constructing the parameters of a probabilistic selection model in a fully parallel manner, followed by a lightweight autoregressive selection process in which each step applies incremental updates to contextual logits. This decoupling of parallel scoring and sequential selection enables efficient computation without sacrificing expressivity. We evaluate CPL on two structured selection tasks: multi-modal path prediction and representative subset selection. CPL achieves improved structural consistency and robustness under ambiguous supervision compared to strong parallel baselines. Source code: https://github.com/cplPaper2026/CPL_NeurIPS_2026 . 1 Introduction Structured prediction problems often require selecting a coherent subset or sequence of elements from a large candidate space ( 7 ; 36 ; 21 ) . In such settings, the correctness of one decision depends on the configuration of the others: a useful output is not merely a collection of high-scoring elements, but a structured object whose parts must be mutually consistent. A central difficulty arises when the target is inherently ambiguous. The same input may admit several valid structured outputs, while training supervision provides only a single observed instance. This creates a mismatch between the multi-modal structure of the task and the single realization seen during learning ( 31 ; 8 ) . Running example: path prediction. Consider predicting a future driving path from road geometry. This problem is central in autonomous driving, where the goal is to plan the ego trajectory and to predict the future behavior of other agents in the scene ( 6 ; 29 ; 8 ) . In practice, supervision for this task is typically constructed from recorded trajectories, using the future path that an agent actually followed. However, this reflects only a single realized outcome, even though multiple valid alternatives may have been available at that moment. This mismatch between multiple possible futures and a single observed trajectory introduces inherent ambiguity into the learning problem. As illustrated in Figure 1 , junctions and splits may admit multiple valid continuations. A training set can therefore contain different valid choices for similar inputs, for example a left continuation in one instance and a right continuation in another. This exposes the model to multiple plausible but mutually exclusive outcomes, while never observing the full set of possibilities for any given scene. (a) (b) Figure 1 : Path prediction under ambiguity. (a) Ground-truth trajectories in a scene with multiple valid continuations. (b) CPL prediction selecting a single consistent branch. At inference time, the desired output is a single coherent path: the model should commit to one branch and continue along it, rather than merging incompatible alternatives. This example exposes the core challenge studied in this paper. Independent scoring methods are efficient, but they do not model the interactions needed to suppress redundant or incompatible choices, and can therefore produce fragmented outputs. Matching-based set predictors introduce global alignment, but under single-sample supervision they may favor intermediate or hybrid configurations that partially match multiple valid modes without corresponding to any valid output ( 4 ; 32 ) . Appendix E provides a minimal illustrative example of this failure mode. Fully autoregressive models naturally resolve ambiguity by committing one decision at a time, but their sequential computation can be expensive for dense candidate spaces. Our approach. We introduce Contextual Plackett–Luce (CPL), a structured probabilistic framework for subset and sequence selection under ambiguous supervision. CPL builds on the normalized sequential-choice structure of Plackett–Luce models ( 26 ; 30 ; 27 ) while extending it with context-dependent utilities: each selected element updates the logits of the remaining candidates through learned pairwise interactions. This enables history-dependent decision making without recomputing representations at each step, as the underlying features are computed once and reused throughout the selection process. CPL supports both ordered sequences and unordered subsets under a common formulation. We evaluate CPL in two complementary regimes: ordered path prediction and unordered representative subset selection. Multi-modal path prediction requires selecting a single coherent trajectory despite multiple valid continuations. Representative subset selection requires choosing a subset of representative elements that captures the underlying structure of the data while avoiding redundant or conflicting selections under ambiguous supervision. Our main contributions are: • a contextual Plackett–Luce model that augments unary scores with learned pairwise interactions, enabling history-dependent selection and explicit modeling of compatibility between elements; • a permutation-invariant training objective for learning from unordered and ambiguous supervision, allowing the model to recover consistent structures from single sampled targets; • an efficient decoding procedure in which each selection step reduces to a lightweight logit update using precomputed interactions, avoiding full autoregressive recomputation; • empirical results on path prediction and representative subset selection demonstrating improved structural consistency and robustness under ambiguous supervision. 2 Analysis of modeling trade-offs and constraints To motivate our design, we first examine three standard paradigms for subset selection, highlighting their modeling limitations under ambiguous supervision and their computational properties. 2.1 Preliminaries and notation We define the candidate set as \mathcal{X}=[k] , where each index i\in\mathcal{X} corresponds to an embedding vector q_{i}\in\mathbb{R}^{d} . The goal is to select a subset S\subseteq\mathcal{X} that forms a valid structured output. We denote by k the number of candidate elements, by d the embedding dimension, and by L the number of layers in the backbone network used to compute representations. The quantity |S| denotes the size of the selected subset. We distinguish between sequential and parallel computation, where A\times B denotes a process with A sequential steps and B parallel operations per step. 2.2 Existing paradigms and limitations Independent scoring Independent scoring evaluates each candidate element in isolation, assigning a scalar utility that reflects its individual suitability. Formally, each candidate q_{i} is assigned a score \theta_{i} and selected via thresholding: \theta_{i}=f_{\theta}(q_{i}),\quad S=\{i\mid\theta_{i}>\tau\}. This formulation lacks a mechanism to coordinate selections, which can lead to over- or under-selection. In the running path prediction example, multiple branches at a junction may exceed the threshold, resulting in incompatible continuations being selected together, while in other cases valid segments may be suppressed. We refer to this failure mode as fragmentation : the output decomposes into disconnected components that are locally plausible but do not form a coherent solution. The computation is fully parallel over candidates, requiring a single forward pass with complexity: O(L\times d^{2}k) . Matching-based set prediction Matching-based methods shift supervision from individual elements to sets, training the

Read the complete text