Efficient Ranking of Mathematical Reasoning Chains via Calibrated Interpolation Sort

Ranking mathematical reasoning chains by quality (for best-of-$n$ decoding, reward model training, or verification) requires expensive pairwise oracle queries. Standard noisy sort needs $\Theta(n \log n)$ such queries per batch. We show that mathematical reasoning chains have a property we call score commensurability: when chains are clustered by embedding similarity, quality becomes approximately linear in the latent space, and a small calibration set of $k$ preference pairs suffices to learn a quality direction $\widehat{w}$. Feeding projected scores to interpolation sort then ranks $n$ chains in $O(n \log \log n)$ key comparisons with zero additional oracle queries. On PRM800K (37k human-graded reasoning chains across 900 MATH problems), embedding-based clustering reduces pairwise noise from $\hat{p} \approx 0.31$ to $0.11$, enabling calibrated methods to achieve $\tau_b < 0.12$ with $k = 5000$ pairs. A key structural finding: mathematical topic labels do not ensure commensurability. PRM800K's "intermediate algebra" category spans polynomial factoring, functional equations, and inequalities with no shared quality direction, but k-means clustering on embeddings does. The calibrated direction $\widehat{w}$ amortizes: once learned, each new batch is ranked with zero additional oracle queries.