Centroid-Halving Preference Queries
Implementation & benchmark of arXiv:2608.21579 — Sorting from Counterexamples
Source paper: Sorting from Counterexamples arXiv:2608.21579 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use a convex uncertainty region over latent item scores to select the next ranked-list query, rather than training separate pairwise preference predictors. Sort the centroid of the current region to obtain a proper ranking; every returned pairwise counterexample intersects the region with a halfspace and removes a constant fraction of its volume under the centroid-cut guarantee. This provides an active-learning procedure for preference models, reward models, or ranking heads that remains globally consistent and can be stress-tested under adversarial feedback.
Formulas
Mathematical statement
Represent a candidate ranking by a score vector x=(x_1,...,x_n) in the cube [0,1]^n, where items i and j are ordered by their coordinates. A counterexample stating that item j should precede item i contributes the halfspace {x in [0,1]^n : x_j-x_i>0}; after all feedback, K_t is the intersection of the cube with these halfspaces and is therefore convex. If V_t is the set of feasible rankings, then every permutation cell has volume 1/n!, so vol(K_t)=|V_t|/n!. Let c_t=(1/vol(K_t)) integral over K_t of x dx be the centroid. Query the ranking obtained by sorting c_t. Grünbaum's theorem states that for any convex body K and any halfspace H containing its centroid c, vol(K intersect H)>=vol(K)/e; the opposite halfspace also has volume at least vol(K)/e. Consequently, a truthful response leaves at most a (1-1/e) fraction of feasible volume and gives O(n log n) noiseless queries. For adversarial feedback, introduce outlier variables z_r in {0,1} for feedback constraint r, enforce x_{j_r}-x_{i_r}>=epsilon-M z_r with sum_r z_r<=k_hat, and run geometrically increasing guesses k_hat when the true corruption budget k is unknown.
Implementation notes
1. Integration point: add this as an active-query controller around a neural ranking or reward model. Given a batch of n candidate items and a neural encoder f_theta, use the controller to select the next complete ranking to request from a human, preference model, or environment. Do not replace the neural scorer initially; use the controller to determine which listwise labels are collected, then fine-tune f_theta on those labels.
2. Pseudocode:
initialize particles x[1:M] ~ Uniform([0,1]^n)
for t = 1,...,T:
retain or reweight particles satisfying all feedback constraints
c = mean(x[1:M])
q = argsort_descending(c)
receive success or counterexample (i,j)
if j must precede i:
weight_m *= 1[x_m[j] - x_m[i] >= epsilon]
resample particles and apply hit-and-run moves inside the surviving halfspaces
train theta on collected complete rankings with a listwise loss
For dimensions below roughly 20, replace particles with a halfspace-intersection sampler or linear-programming oracle. For noisy feedback, attach z_r to each constraint and retain particles satisfying all but at most k_hat constraints; alternatively use soft weights exp(-lambda max(0, epsilon-(x_j-x_i))). Run k_hat=1,2,4,... in parallel or increase it when the effective particle count collapses. The theorem supplies the target constant-factor volume reduction; Monte Carlo centroid error, particle count M, epsilon, and lambda are empirical settings. First test a 2-layer MLP reward model on synthetic rankings of n=16 items generated from hidden linear scores. Compare random complete-ranking queries, pairwise uncertainty sampling, and centroid-halving queries at 0%, 5%, and 10% adversarial counterexamples. Measure Kendall tau versus query count, labels needed to reach tau=0.9, invalid-cycle rate, and reward-model loss at equal labeling budget. Success means fewer labels than pairwise active learning, zero invalid rankings, and approximately geometric decay in surviving particle mass on truthful rounds.
Verification
Stage 1 · Toy mechanism gate: Failed ✗
Stage 2 · Mechanism transferred to benchmark: Not tested
Stage 2 · Practical benchmark result: Not run
Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works
Stage 1 — Mechanism check agent confidence 10/10
Built a numerical centroid-cut and ranking-query simulator in centroid_halving.py, plus focused verification in verify_centroid_halving.py. The valid centroid-passing halfspace check matched Grünbaum’s prediction: observed minimum retention 0.443 versus predicted lower bound 1/e = 0.368. However, the proposed zero-threshold preference cut is not generally a centroid cut: for K = [0,1]^2 intersect {x >= y}, the centroid is approximately (0.667, 0.333), while the opposite preference halfspace has zero volume; query experiments consequently showed centroid querying stalling rather than geometric progress. The claimed mechanism therefore did not manifest as stated.
- Agent confidence
- 10/10
- Baseline
- Exact/sampled comparison was unstable and capped at 100 queries; random querying averaged 3.0, 10.6, 58.1, and 100.0 queries for n=3,4,5,6 respectively.
- Idea
- Valid centroid-cut retention: predicted >=0.3679, observed minimum 0.4431 and mean 0.5000. Proposed ranking controller averaged 50.1, 87.9, 100.0, and 87.9 queries for n=3,4,5,6, often hitting the cap rather than showing geometric decay.
Limitations: The neural reward-model integration, adversarial 5%/10% corruption experiments, hit-and-run sampling, Kendall tau, and listwise loss were not tested. The continuous sampler uses finite Monte Carlo particles and the exact query comparison is limited to small n and a query cap.
How to run: python3 verify_centroid_halving.py && /home/maxwelhelp/main/bin/python3 centroid_halving.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Artifacts
- centroid_halving.py 4.2 KB View Raw
- report.md 1.8 KB View
- results.json 1.8 KB View Raw
- verification_results.json 1.0 KB View Raw
- verify_centroid_halving.py 2.8 KB View Raw