How Many Orderings Does It Take? Permutation Designs for Order-Invariant LLM Answers

Language models change their answers when the same options, labels, or retrieved passages are listed in a different order. The standard fixes sit at two extremes. One is to try every ordering, which grows as $k!$ for $k$ items. The other is to shuffle at random a few dozen times and vote. A third, cheap deterministic fix is to rotate the list cyclically $k$ times, so every item visits every position once. This note asks a question from derandomization, the part of algorithm theory that studies when coin flips can be replaced by a fixed, structured set of choices. The question is which fixed families of orderings cancel the order effects a model actually has, and how many queries they need compared with random shuffling.

The core idea is to treat the model's score, as a function of the ordering, like a signal and split it into parts. The "degree-1" part depends only on which slot each single item lands in. The "degree-2" part depends on where pairs of items land relative to each other, and so on up to degree $k$. A fixed family of orderings that is t-wise uniform places every $t$-tuple of items in every $t$-tuple of slots equally often. Averaging over such a family removes all order effects up to degree $t$ exactly, while random shuffling leaves noise at every degree. If most of a model's order sensitivity lives at low degree, a small fixed design should beat random shuffling at equal cost. If it does not, random shuffling is the honest answer. We propose to measure which of these holds, across tasks and models.

Core Claim

Let $f(\sigma)$ be a model's score for an item set presented in ordering $\sigma$, for example the log-probability of the correct option. The quantity we want is the order-free value $\bar f$, the average of $f$ over all $k!$ orderings. Write $f = f_{\le t} + f_{>t}$, where $f_{\le t}$ is the part of $f$ that depends on at most $t$ item positions jointly and $f_{>t}$ is the rest. The two estimators then compare as follows. Averaging over a t-wise uniform design $D$ gives error exactly equal to the average of $f_{>t}$ over $D$. Averaging over $m$ random orderings gives mean squared error

$$\mathrm{MSE}_{\text{random}} = \frac{\mathrm{Var}(f_{\le t}) + \mathrm{Var}(f_{>t})}{m},$$

which is the usual Monte Carlo rate from independent draws. The deterministic design pays nothing for low-degree structure. The random estimator pays for all of it.

Our claim has two parts. First, for current models on multiple-choice, label-list classification, and retrieval-augmented question answering, the order-sensitive variance is concentrated in degrees 1 and 2. Second, t-wise uniform designs with $t \le 2$ therefore reach the full-permutation answer with several times fewer model calls than random shuffling. The size cost of such designs is known and unavoidable. A design that is exactly t-wise uniform needs at least $k!/(k-t)!$ orderings, because every $t$-tuple of slots must appear. That means $k$ orderings for degree 1 and $k(k-1)$ for degree 2, the latter achievable with sharply 2-transitive groups when $k$ is a prime power.

We also give a concrete reinterpretation of a known failure. Do RAG Systems Suffer From Positional Bias? found that moving the relevant passage to a favored edge pushes a hard distractor to the other favored edge, so clever reordering does no better than shuffling. In our language this "cancellation effect" is a degree-2 interaction between the positions of two specific passages. A degree-1 design such as cyclic rotation cannot remove it. A pair-uniform design can, and it needs no knowledge of which passage is the distractor.

Relation to Prior Work

Three lines of work motivate the project by showing that order effects are large and structured. Serial Position Effects of Large Language Models finds that the first positions are favored in 73 of 104 model-task settings. It also finds that prompting does not remove the effect, which suggests the effect lives in the architecture. Positional Biases Shift as Inputs Approach Context Window Limits shows that the shape of the bias changes with how full the context window is: middle-neglect dominates at low fill and distance-to-end at high fill. Under our decomposition, the balance between low-degree and higher-degree parts should therefore depend on prompt length. The multiple-choice studies, CMMU and Choosing 'Right' from Wrong, document letter and slot preferences that look first-order.

The closest existing methods fall into two camps: random-shuffle aggregation and fixed orderings. QMOS votes over 20 random option shuffles. REQUAL-LM averages embeddings over $m$ random candidate orders. Both choose the number of shuffles by hand and offer no guarantee against unlucky draws. CMMU's CircularEval uses $k$ cyclic rotations. That is a degree-1 design, although it is not described that way, and it keeps the relative adjacency of items fixed. We keep CircularEval's determinism but ask which degree of balance is needed. We keep QMOS's aggregation but replace its random draws with designs matched to the measured spectrum.

OTTER corrects label bias deterministically in a single pass, using optimal transport over a batch. It fixes a fixed prior over output labels, which is a degree-1 effect, but it cannot see interactions between positions. Beyond Majority Voting improves on voting when errors are correlated. It treats random shuffling as an outside fix, and we use its weighted aggregator as a downstream combiner.

The derandomization literature supplies the key lesson and one constraint. A Deterministic Partition Tree and Applications shows that removing randomness often costs structure; there, nodes need logarithmic rather than constant degree. We expect the analogous cost here to be the $k(k-1)$ size of pair-uniform designs. For long passage lists this cost may favor a hybrid: randomly choose one of several degree-1 designs. That keeps an unbiased estimate and removes the degree-1 variance.

Two papers constrain what we can claim. ARC 'Challenge' Is Not That Challenging shows that scoring options in isolation loses a great deal of accuracy, so the order-free target must be computed with options shown together. LLMs May Perform MCQA by Selecting the Least Incorrect Option warns that order invariance is not the same as knowing the answer. We therefore claim only to recover the full-permutation answer cheaply, not to make the model correct.

Research Program

The first component is measurement. For 4-option multiple choice we enumerate all 24 orderings per question on MMLU, ARC-Challenge, and MedMCQA. This lets us compute the exact split of the order-sensitive variance by degree, per model and per question. For larger $k$ the full split cannot be computed. For label-list classification (Banking77 with 77 labels, GoEmotions) and for retrieval QA with 10 passages (Natural Questions, TriviaQA, PopQA), we estimate the degree-1 and degree-2 energy by regression on slot indicators and slot-pair indicators, using a large random sample of orderings. We report energy by degree as a function of model family, task, and context fill.

The second component is construction. For degree 1 we use Latin squares and Williams squares; a Williams square also balances which item immediately precedes which. For degree 2 we use sharply 2-transitive groups when $k$ is a prime power, and we search for small near-pair-uniform families otherwise. We also include randomized Latin-square hybrids. The third component is analysis. We will turn measured energy into predicted crossover budgets, meaning the number of model calls $m$ below which a design beats random shuffling. We will then check these predictions against observed error.

Baselines

The naive reference is a single pass in the benchmark's canonical order, which is what most leaderboards report.

The main competitor is random shuffling with aggregation at an equal number of model calls, as in QMOS. QMOS reports that Phi-2 on TeleQnA rises from 42.07% to 84.65% accuracy. That gain comes from 20 shuffles combined with fine-tuning and retrieval, so the shuffling contribution is not isolated. We therefore re-run shuffling alone at $m \in \{k, 2k, k(k-1)\}$, with the same model and prompts and 20 seeds.

The retrieval competitor is shuffle versus MaxRel from Do RAG Systems Suffer From Positional Bias?. With Qwen 2.5 7B and BGE plus reranking, it reports 71.00% accuracy for shuffle and 71.73% for MaxRel. We reproduce this pipeline and compare pair-uniform designs at equal call counts. Beating it means a significant accuracy gain over both 71.00% and 71.73% at matched cost.

CircularEval from CMMU serves as the degree-1 ablation. CMMU reports GPT-4V at 30.91% under its protocol. Comparing Williams squares and pair-uniform designs against plain rotation isolates the value of balancing pairs.

For single-pass correction we compare against slot-prior subtraction estimated on held-out data, and against OTTER. No reported result was found on Lacuna for OTTER's MMLU accuracy number, so we run it ourselves.

The comparison criterion is the same throughout. Beating a baseline means lower error with respect to the full-permutation value, and matching or higher accuracy, at an equal or smaller number of model calls, with paired bootstrap tests.

Why not just…?

Why not just shuffle randomly more times? This is the real threat. If most of a model's order sensitivity sits at degree 3 or higher, random shuffling is as good as any design, and our proposal reduces to a measurement paper. The spectrum measurement settles this directly. We commit to reporting the crossover budget even where it is unfavorable. In the regime where designs are too large, the randomized Latin-square hybrid keeps the benefits of randomness.

Why not just rotate cyclically, as CircularEval does? Rotation is exactly a degree-1 design and costs only $k$ calls. It is the right tool if pair effects are negligible. It fails if they are not: the RAG cancellation effect is a pair interaction, and rotation never changes which item follows which. The Williams-square and pair-uniform ablations measure how much accuracy rotation leaves unrecovered.

Why not just subtract a learned slot prior in one pass? For purely first-order bias, this could match a $k$-call design at $1/k$ of the cost. That would be a genuine win for the simpler method, and we will report it as such. It cannot remove interactions that depend on content, such as which specific passage sits next to which. The degree-2 energy estimate predicts where this approach should fail, and the retrieval experiment tests that prediction.

Decisive Checks

The first check concerns spectra on 4-option multiple choice, where exact computation is possible. If degree-1 energy exceeds about 80% of order variance, CircularEval-style designs should match 24-ordering enumeration within noise. If they do not, the decomposition itself is the wrong lens.

The second check concerns retrieval with 10 passages, including hard distractors. A 90-ordering pair-uniform design, with $k=10$ handled by near-uniform search, should recover more of the full-permutation accuracy than 90 random shuffles and more than 10 rotations. Failure here would falsify the claim that the cancellation effect is a pair interaction.

The third check concerns Banking77. Here even degree-1 designs cost 77 calls, so we test whether the predicted crossover budget from measured energy matches observed error curves across model families and context-fill levels.