# Centroid-Halving Preference Queries

- ID: 2671
- Canonical URL: https://synthcore.org/idea/2671/centroid-halving-preference-queries
- API JSON: https://synthcore.org/api/idea/2671.json
- API Markdown: https://synthcore.org/api/idea/2671.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.21579](https://arxiv.org/abs/2608.21579)
- Category: training
- Solves: sample-efficiency, stability, accuracy
- ML areas: ranking, active-learning, rlhf, fine-tuning
- Math tags: convex-analysis, geometry, combinatorics, optimization
- Ratings: usefulness 7/10; difficulty 6/10; novelty 7/10

## 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.

## 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.

## Key formulas

- $$\bigl\{x\in[0,1]^{n}:x_{j}-x_{i}>0\bigr\}$$
- $$\operatorname{vol}(K_{t})=\frac{|\mathcal{V}_{t}|}{n!}$$
- $$c_t=\frac{1}{\operatorname{vol}(K_t)}\int_{K_t}x\,dx$$
- $$\operatorname{vol}(K\cap H)\geq \frac{1}{e}\operatorname{vol}(K)\quad\text{for every halfspace }H\text{ containing the centroid of }K$$

## 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:
```text
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

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 10/10
- 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.

## Artifacts

- [centroid_halving.py](https://synthcore.org/code/1030/centroid_halving.py)
- [report.md](https://synthcore.org/code/1030/report.md)
- [results.json](https://synthcore.org/code/1030/results.json)
- [verification_results.json](https://synthcore.org/code/1030/verification_results.json)
- [verify_centroid_halving.py](https://synthcore.org/code/1030/verify_centroid_halving.py)
- [Download all files as ZIP](https://synthcore.org/download/1030)

## Disclaimer

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