# Uniform PEP selective decoding

- ID: 2329
- Canonical URL: https://synthcore.org/idea/2329/uniform-pep-selective-decoding
- API JSON: https://synthcore.org/api/idea/2329.json
- API Markdown: https://synthcore.org/api/idea/2329.md
- Verification status: unverified
- Source: [arXiv:2608.15169](https://arxiv.org/abs/2608.15169)
- Category: theory
- Solves: stability, sample-efficiency, inference-speedup
- ML areas: retrieval, inference-speedup, rlhf
- Math tags: probability, statistics, information-theory
- Ratings: usefulness 5/10; difficulty 4/10; novelty 5/10

## Idea description

Replace raw neural scores with randomized pairwise-error probabilities relative to a reference candidate distribution. Use a fixed PEP threshold to accept, abstain, or form a variable-size candidate list; exact uniformity under the reference law makes the threshold interpretable independently of the model's score scale and robust to ties.

## Mathematical statement

For a candidate space \(\mathcal X\), context \(y\), model score \(m_\theta(x,y)\), and independent tie-breaker \(u\sim\mathcal U([0,1])\), define the lexicographic order \((a,u)\succ(b,v)\) by higher score first and then larger tie-breaker. The pairwise error probability is \(p_e(x\mid y;u)=\mathbb P_{X,U}\{(m_\theta(X,y),U)\succ(m_\theta(x,y),u)\}\), where \(X\sim Q_X\) is a reference candidate and \(U\sim\mathcal U([0,1])\). The lexicographic identity states \(\mathbb P_{X,U}\{(m(X,y),U)\succ(m(x,y),u)\}=\mathbb P_{X,U}\{p_e(X\mid y)<p_e(x\mid y;u)\}=p_e(x\mid y;u)\). If \(X\sim Q_X\), then \(p_e(X\mid y)\sim\mathcal U([0,1])\); under \((X,Y)\sim Q_X\times Q_Y\), also \(p_e(X\mid Y)\sim\mathcal U([0,1])\). The measurable tail-quantile inverse \(\tilde m\) satisfies \(\tilde m(p_e(X\mid y),y)=m(X,y)\) almost surely. In the neural adaptation, \(Q_X\) is an empirical or proposal distribution over labels, documents, actions, or tokens, and acceptance \(p_e(x\mid y;u)\le\alpha\) is a rank-calibrated rule.

## Key formulas

- $$p_e(x\mid y;u)=\mathbb P_{X,U}\{(m_\theta(X,y),U)\succ(m_\theta(x,y),u)\},\qquad X\sim Q_X,\ U\sim\mathcal U([0,1]).$$
- $$\mathbb P_{X,U}\{(m(X,y),U)\succ(m(x,y),u)\}=\mathbb P_{X,U}\{p_e(X\mid y)<p_e(x\mid y;u)\}=p_e(x\mid y;u).$$
- $$p_e(X\mid y)\sim\mathcal U([0,1]),\qquad (X,Y)\sim Q_X\times Q_Y\ \Longrightarrow\ p_e(X\mid Y)\sim\mathcal U([0,1]).$$
- $$\widehat p_e(x_i\mid y;u_i)=\frac{1}{N}\sum_{j=1}^{N}\mathbf 1\!\left[(m_\theta(x_j,y),u_j)\succ(m_\theta(x_i,y),u_i)\right],\qquad \text{accept }x_i\text{ iff }\widehat p_e(x_i\mid y;u_i)\le\alpha.$$

## Implementation notes

Integrate this at the final scoring stage of a retrieval system, classifier, policy, or language-model decoder, before top-k selection or selective prediction. For each context tensor \(y\), construct a reference candidate batch \(x_1,\ldots,x_N\sim Q_X\). The reference can be a minibatch of documents, a label-prior sample, an action-proposal set, or sampled token candidates. Compute scalar scores \(s_i=m_\theta(x_i,y)\), draw independent \(u_i\sim\mathcal U([0,1])\), and rank pairs \((s_i,u_i)\) lexicographically. For candidate \(x_i\), compute \(\widehat p_i=N^{-1}\sum_j1[(s_j,u_j)\succ(s_i,u_i)]\). Accept when \(\widehat p_i\le\alpha\); otherwise abstain, retrieve more documents, invoke a larger model, or expand the beam. Compact pseudocode is: `x=sample_reference(QX,N); u=uniform(N); s=model_score(x,y); rank=lexicographic_rank_descending(s,u); p=(rank-1)/N; if p[i]<=alpha: return x[i] else fallback()`. The theorem applies to the population probability under \(Q_X\), while the code estimates it with an empirical rank, so evaluate sampling variability as a function of \(N\). First run CIFAR-10 selective classification with a small ResNet, using the training label prior as \(Q_X\) and a held-out calibration split; compare raw-softmax thresholding and conformal rank baselines at matched coverage. Then test retrieval on BEIR with a fixed candidate pool. Success means empirical null acceptance close to \(\alpha\), stable behavior under score rescaling and ties, and fewer fallback or large-model calls at matched error or recall.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.