When a large language model is given worked examples in its prompt (in-context learning), both which examples appear and in what order change the answer. Picking an ordered list of $k$ examples from a pool of $n$ has $n!/(n-k)!$ possibilities. Existing methods cope with this by training a selection policy or by clustering heuristics, and both struggle once $k$ grows past a handful. This proposal starts from an empirical bet. In decoder-only models, order sensitivity is concentrated in a few positions near the start and end of the prompt. The interior behaves almost like an unordered bag, consistent with the widely reported "lost in the middle" effect.
If the bet holds, ordered selection splits into two parts. The first is choosing an unordered interior set, which a randomized greedy algorithm handles cheaply: at each step it scores only a small random sample of candidates instead of the whole pool. The second is assigning items to $p$ position-sensitive slots, where $p$ is small. The total search cost is then exponential only in $p$, never in $k$, and per-step cost does not depend on $n$. The proposal builds this method, measures $p$ for real models, and states plainly when the decomposition fails.
Core Claim
Three bodies of work motivate the bet. Guo and Vosoughi's study of Serial Position Effects of Large Language Models shuffled label lists and source documents across 104 model–task pairs. They found primacy in 73 of them, recency in summarization, and neglect of the middle in long contexts. They also found that these profiles cluster by architecture and resist steering prompts, which suggests a stable, model-specific positional signature rather than prompt-specific noise. Xiang et al. (Addressing Order Sensitivity of In-Context Demonstration Examples in Causal Language Models) trace order sensitivity to the causal attention mask: early examples see little context, late ones see everything. They also show that bidirectional models such as T5 are far more stable.
Neither line of work turns this structure into a selection algorithm. That is the step here. We treat "how many slots are order-sensitive" as a measurable parameter $p$ of a given model and task, and design the search so that only those slots pay a combinatorial price. This borrows the stance of parameterized algorithms, which confine the exponential blow-up to one small structural number. The clustering literature also warns about the regime we must avoid: Improved analysis of D2-sampling based PTAS for k-means and other Clustering problems shows that even well-optimized exponential dependence becomes impractical beyond small parameter values. So $p$ must actually be small for this idea to be useful, and we test that first.
Formally, let $\pi=(e_1,\dots,e_k)$ be an ordered prompt and $F(\pi)$ the model's mean log-likelihood of correct labels on a small validation set. We define the sensitivity of slot $i$ as
$$\sigma_i = \mathbb{E}\big[\,|F(\pi) - F(\pi^{(i\leftrightarrow j)})|\,\big],$$
the expected change in validation score when the item in slot $i$ is swapped with one in a random other slot $j$. The expectation is over random prompts and swap partners. Let $P$ be the set of slots whose $\sigma_i$ exceeds a threshold, with $p=|P|$. The interior slots are the remaining $k-p$. Let $\delta$ be the largest change in $F$ caused by permuting only the interior. The working assumption is that $\delta$ is small and $p$ is two to four, even for $k$ in the tens.
Under that assumption, the method selects the interior set by stochastic greedy. Each step scores $s$ random candidates and keeps the best, so per-step cost is independent of $n$. By the quantile argument in the stochastic greedy literature, the best of $s$ uniform draws lands in the top $\alpha$ fraction of candidates with probability $1-(1-\alpha)^s$. If the interior objective is close to monotone submodular, this inherits the familiar $(1-1/e-\epsilon)$ guarantee. That guarantee holds only up to an additive slack: $\delta$, plus however far the interior objective is from submodular, which we measure rather than assume. The method then fills the $p$ sensitive slots by search over sampled candidates conditioned on the chosen interior. The search costs $O(s^p)$ evaluations, so the total is roughly $O(ks + s^p)$ evaluations instead of $n!/(n-k)!$.
Research Program
The work has three stages. The first is measurement. For each model and task we estimate the full profile $\sigma_1,\dots,\sigma_k$ by swap probes for $k\in\{8,16,32,64,128\}$, together with the interior permutation slack $\delta$. Bidirectional encoder–decoder models serve as a control. Following Xiang et al., we predict a flat, low profile for them, effectively $p=0$. We also measure how stable the profile is across tasks for a fixed model, since Guo and Vosoughi's architecture-clustering result predicts a profile that transfers. A transferable profile would let practitioners estimate $p$ once per model rather than per task.
The second stage is the algorithm, which we call slot-aware stochastic greedy. It proceeds as described above, with two variants for the boundary stage. One enumerates all assignments of sampled candidates to the $p$ slots. The other is greedy over item–slot pairs, treating each sensitive slot as its own category with capacity one. Ohsaka and Yoshida's Monotone k-Submodular Function Maximization with Size Constraints supplies the stochastic version of this greedy and its $1/3$ guarantee under individual size constraints. We use their algorithm as the method, and do not claim the guarantee transfers without checking the required property empirically. Token length enters as a modular cost when the context budget binds, using the distortion idea of Harshaw et al. (Submodular Maximization Beyond Non-negativity) to keep long, high-utility examples from consuming the budget early.
The third stage is analysis. We state the approximation guarantee as an explicit function of $p$, $\delta$, the measured submodularity violation, and $s$. Each of these is estimated from data, so the bound is checkable rather than decorative.
This differs from the closest work in specific ways. Auto-regressive In-context Demonstration Selection (AutoSelect) trains a Vision-Transformer policy that picks examples one at a time. Its training needs many LLM reward calls, it scans the full pool, it is evaluated only up to $k=16$, and it carries no approximation guarantee. Our method is training-free and per-step cost does not grow with $n$. Hierarchical Demonstration Order Optimization for Many-shot In-Context Learning (HIDO) orders a many-shot set by K-means clustering followed by intra- and inter-cluster search. It never asks where order actually matters, and it optimizes order for a set chosen separately. Let The Jury Decide (JUDGE) runs greedy selection on a pruned pool but treats the prompt as unordered. Sequence-submodular methods such as Budgeted Sequence Submodular Maximization and Robust Sequence Submodular Maximization handle order in general but scan the whole ground set every step and ignore the specific shape of LLM positional bias.
Baselines
The do-nothing reference is $k$ uniformly random examples in random order, reported with its spread over permutations. A second naive reference is nearest-neighbour retrieval by sentence embedding, in retrieval order, which is what most deployed systems do. Both use zero optimization calls and anchor how much any search buys.
The strongest existing method for small $k$ is AutoSelect. Its paper reports gains of 11.2% on Winowhy and 5.6% on AQuA over the strongest non-oracle baseline, and an average task rank of 1.1 across its suite. It does not report absolute accuracies we could quote, so we rerun it. For fairness, its policy-training reward calls count against the same budget of LLM forward passes that our method spends on validation scoring. Beating it means matching or exceeding its accuracy on TREC, SST-2, Winowhy and AQuA at $k\le16$ with at most the same total forward passes. Exceeding it at $k=64$ and $k=128$, where it was not evaluated, also counts.
For many-shot ordering the strongest method is HIDO. It reports 51.19% on CommitmentBank with GPT-3.5-Turbo against 46.43% for its best baseline, and 80.47% against 76.69% on TREC with SciPhi. We run HIDO on the same pools and models, with the same probing-call budget. Beating it means higher accuracy on CB and TREC at $k\ge100$ with equal or fewer calls.
JUDGE-style unordered greedy is the third comparison. It isolates the cost of ignoring order.
The ablation that isolates our key ingredient is the same pipeline with the slot split removed, in two forms. One form treats all $k$ slots as sensitive, which forces greedy over item–slot pairs everywhere. The other treats none as sensitive, which is plain stochastic greedy followed by random order. A third variant uses full-pool scans instead of random samples, to show what sampling costs in quality.
Why not just…?
Why not just select an unordered set greedily and then sort it into the best order? This is the real threat. If positional bias acts as a fixed weight per slot that multiplies each item's standalone value, then selecting first and ordering second is optimal, and our joint boundary search is wasted. The experiment that settles it compares select-then-order against slot-aware selection at equal budget. Select-then-order here means stochastic greedy for the set, then the best of $s^p$ arrangements of the chosen items over the sensitive slots. If the two tie across tasks, we report the simpler pipeline as the contribution, with the $p$-measurement as the reason it suffices. The joint method only earns its place if the item that is best in slot one is often not in the best unordered set.
Why not just average predictions over several random orderings? Aggregation in the style of REQUAL-LM multiplies inference cost by the number of orderings $m$ on every query. Our method pays once at selection time and then serves a single prompt. Averaging also mixes good and bad orderings. The Order Effect reports F1 drops of up to 12.24% on MSMARCO under shuffling, so the bad orderings are not harmless. We include an $m$-ordering ensemble on top of the selected set and report accuracy against total inference calls, so readers can see where, if anywhere, the ensemble wins.
Why not just fine-tune the model to be order-invariant? InfoAC (from Xiang et al.) cuts SST-5's permutation-inconsistency measure from 60.5% to 17.1% on a 13B Llama model using LoRA. However, it needs model weights, and it still leaves the question of which examples to choose. We treat it as complementary rather than competing. On an open model we will apply InfoAC and remeasure $\sigma$. We predict that $p$ shrinks, which would make our method cheaper on top of it rather than redundant.
Why not just use uniform random sampling after filtering, as in BiasBusters? BiasBusters reduces tool-selection bias from 0.380 to 0.094 with filter-then-sample. That works because its candidates are functionally equivalent. In-context examples are not equivalent, and the random-examples baseline above measures exactly how much is lost by sampling without scoring.
Proposed Experiments
We use TREC, SST-2, SST-5, CommitmentBank, AGNews and Banking77 for classification, and Winowhy and AQuA for reasoning, with pools of thousands of training examples. Models are two open decoder-only families and one API model, with an encoder–decoder model as the positional control. Metrics are test accuracy; LLM forward passes spent on selection; a permutation-inconsistency ratio in InfoAC's sense, measured over shuffles of the final prompt; and the measured $p$ and $\delta$.
The first decisive check runs before any method comparison. If the sensitivity profile is not concentrated, meaning $p$ grows roughly linearly with $k$ or the interior slack $\delta$ is comparable to the accuracy gaps between methods, the core claim is false and we report that as the finding. The second check is the select-then-order comparison above. The third is scaling: accuracy and cost as $n$ grows tenfold at fixed $k$. Our per-step cost should stay flat while full-scan greedy and AutoSelect costs grow with the pool. The fourth is the encoder–decoder control, where the slot split should give no benefit over plain stochastic greedy because there is little order effect to exploit.
References
- Serial Position Effects of Large Language Models
- Addressing Order Sensitivity of In-Context Demonstration Examples in Causal Language Models
- Improved analysis of D2-sampling based PTAS for k-means and other clustering problems
- Monotone k-Submodular Function Maximization with Size Constraints
- Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
- Auto-regressive In-context Demonstration Selection
- Hierarchical Demonstration Order Optimization for Many-shot In-Context Learning
- Let The Jury Decide: Fair Demonstration Selection for In-Context Learning through Incremental Greedy Evaluation
- Budgeted Sequence Submodular Maximization
- Robust Sequence Submodular Maximization
- REQUAL-LM: Reliability and Equity through Aggregation in Large Language Models
- The Order Effect: Investigating Prompt Sensitivity to Input Order in LLMs
- BiasBusters: Uncovering and Mitigating Tool Selection Bias in Large Language Models