A contragredient view of conformal placement and Steinitz balancing

Less tersely ...

Start with what split conformal actually does. You have \(n\) calibration scores and one test score, \(N=n+1\) numbers in all, and the interval is built from the \(k\)-th smallest of them. The guarantee rests on a counting fact: go through the \(N\) values one at a time, pretend each in turn is the test point, and ask whether that placement would be covered. Exactly \(k\) of the \(N\) placements are, whatever the scores were (ties are assumed away; the note takes the scores distinct). No probability has been used yet. Probability enters once, at the end: if the data are exchangeable, the real test point is equally likely to be any of the \(N\) placements, so its chance of coverage is exactly \(k/N\). The set of all placements is what the note calls the orbit, and the counting fact says the average over the orbit is \(k/N\) exactly.

The word “contragredient” describes two ways of computing that same average. You can hold the question fixed and shuffle the coverage verdicts past it, or hold the verdicts fixed and shuffle the question past them, the way a clock reads the same whether you turn the hands one way or the dial the other. (The thing being shuffled is the vector of 0/1 coverage decisions, not the raw scores; averaging the scores themselves would erase the ranks that decide coverage.) The displayed identity \(\langle P^{\vee}f, v\rangle = \langle f, Pv\rangle\) says nothing more than that the two computations agree. The payoff is that statements proved on one side transfer to the other for free.

Now the other side. Steinitz proved in 1913 that if you have a collection of vectors that sum to zero, none of them large, you can always order them so that every partial sum along the way stays inside a fixed ball, no matter how many vectors there are. Walk through them in a random order and the partial sums drift like \(\sqrt t\); walk in the right order and they never drift at all (demo). Divide by \(t\) and the running average is within a constant over \(t\) of its target at every single step.

The bridge: take each conformal placement, write 1 if it is covered and 0 if not, and subtract \(k/N\). Those \(N\) residuals sum to exactly zero, by the counting fact. They are a Steinitz population. So there must be an ordering of the placements whose running acceptance average stays close to \(k/N\) at every prefix, and in this one-dimensional case the note writes the ordering down explicitly: that average is within \(1/(2t)\) of \(k/N\) after every step \(t\), deterministically (demo).

It helps to see the actual numbers. The population contains only two values: the \(k\) covered placements each contribute \(1-k/N\), and the \(N-k\) uncovered ones each contribute \(-k/N\). Every value has absolute size below 1, and the total is \(k(1-k/N)+(N-k)(-k/N)=0\) exactly. Take \(N=10\) and \(k=8\): eight residuals of \(+0.2\) and two of \(-0.8\). A bad order spends the two \(-0.8\)s early and the running sum lurches; the balanced word \(b_t=\lfloor 0.8t+\tfrac12\rfloor-\lfloor 0.8(t-1)+\tfrac12\rfloor\) spends them at steps 3 and 8, giving the order \(+.2,\,+.2,\,-.8,\,+.2,\,+.2,\,+.2,\,+.2,\,-.8,\,+.2,\,+.2\), whose running sum goes \(.2,\,.4,\,-.4,\,-.2,\,0,\,.2,\,.4,\,-.4,\,-.2,\,0\): never further than \(0.4\) from zero, and back to zero exactly at the end. That bounded ledger, divided by \(t\), is the \(1/(2t)\) coverage statement. The word itself is classical: it solves the two-party case of Tijdeman’s chairman assignment problem (1980), which asks for a schedule keeping every party’s share of the chair within a fixed distance of its quota at every prefix. The scalar, sharp-constant corner of the Steinitz world was mapped before conformal prediction existed; the observation here is that conformal placements live in it.

Herding, where this whole thread started (demo), is Welling’s greedy algorithm for picking points one at a time so that their running averages balance a target. Harvey and Samadi posed a stricter cousin, each point used once, which is exactly the Steinitz ordering problem, and showed that solving it solves herding over the finite population. Ordinary herding, which may reuse points, is the relaxed version. That is why the note treats Steinitz balancing as the exact finite-population construction and herding as a remark.

None of this removes exchangeability from real prediction. In actual use only one placement is the test point, and only exchangeability makes that placement an even draw on the orbit. The balancing results are about computations and audits over the whole orbit, where no randomness is needed at all.

Both halves of the name are jargon from combinatorics on words, the branch of mathematics that studies sequences of symbols. A word is nothing more than a string: a finite or infinite sequence of letters drawn from some alphabet. Here the alphabet is \(\{0,1\}\) and the word is the sequence \(b_1,b_2,\dots,b_N\) saying “covered” or “uncovered” at each step of the traversal. A binary word is balanced if its letters are spread as evenly as possible: any two windows of the same length contain counts of 1s differing by at most one, so every prefix of length \(t\) holds either \(\lfloor t\theta\rfloor\) or \(\lceil t\theta\rceil\) ones, where \(\theta\) is the density. The floor construction \(b_t=\lfloor t\theta+\tfrac12\rfloor-\lfloor (t-1)\theta+\tfrac12\rfloor\), ours with \(\theta=k/N\), is the canonical way to build one; words of this form are also called mechanical or Sturmian-type, the same objects that describe evenly spaced points on a circle and, in the periodic case, leap-year rules. “Balanced” is the standing term for the evenness the corollary needs; the sharp \(\tfrac12\) prefix bound comes from the centered (\(+\tfrac12\) phase) word in particular.

Whether greedy is enough depends on the dimension, and the split is clean. In the scalar two-valued case, our case, yes: the rule “emit whichever symbol keeps the running count closest to its quota” reproduces the balanced word and achieves the sharp \(\tfrac12\). This is Tijdeman’s territory, and with more than two parties the quota-tracking rule is still optimal, the constant degrading gracefully toward 1. In demo 24 the explicit word and greedy achieve the same thing; the word is just nicer to state.

In the vector-valued case, no, not as far as anyone has proved. The dimension-only constant in Steinitz’s theorem does not come from a greedy argument: the proofs that give a clean bound, Steinitz’s original and the Grinberg–Sevastyanov algorithm that achieves a bound linear in the dimension in polynomial time, maintain a fractional certificate over the remaining vectors and round it, a look-ahead structure a myopic rule lacks. Plain greedy, append the remaining vector that minimizes the new prefix norm, has no known \(N\)-independent guarantee and can paint itself into a corner where every remaining vector points the wrong way; demo 23 labels its greedy ordering a heuristic for this reason.

Herding is the greedy algorithm, in the with-replacement setting: pick the next point to best balance the running average. Its \(O(1/n)\) rate is conditional, the Frank–Wolfe interiority conditions of Bach et al.; when those fail, greedy herding falls back to the \(O(1/\sqrt n)\) a random order already gives. Greedy is exactly enough in the scalar conformal corner, and exactly what is not enough in the general one.