Example Selection for In-Context Learning via Conditional Mutual Information

In-context learning (ICL) is highly sensitive to which demonstrations are chosen, yet existing methods rely on embedding similarity as a proxy for example value. We argue that similarity is flawed: a similar example may repeat what the model already knows, and selecting similar examples independently ignores inter-example redundancy. We reformulate example selection as conditional mutual information (MI) maximisation and propose MI-Greedy, which greedily selects demonstrations to maximise I(Y; S | x) between the selected set S and the answer Y given test input x. We prove this objective is monotone submodular, guaranteeing a (1 − 1/e) greedy approximation and deriving diversity as a formal consequence. Experiments on SST-2, TREC, RTE, and GSM8K with Qwen2.5-3B show MI-Greedy beats SBERT-kNN at small k (+1.0–+2.7 pp. on TREC at k = 2, 4; +1.4–+1.8 pp. on RTE), but the advantage reverses at k = 8 as similarity-based coverage dominates. A two-stage pipeline (SBERT pre-filter → MI-Greedy) cuts forward passes by up to 83% with no accuracy loss. Under 30% label-noisy candidate pools, MI-Greedy degrades up to 9× less than SBERT-kNN. On GSM8K the token-entropy estimator is ineffective (49% at k = 2, below random 72.3%; Pearson r ≈ − 0.06 to correctness); a pilot answer-consistency estimator recovers 75%, confirming the MI objective is sound but the estimator is the bottleneck for generative tasks.