In-Context Learning as Approximate Belief Propagation
Abstract
Few-shot in-context learning (ICL) cannot revise its belief about an early demonstration once a later, contradicting one arrives, so a single misleading example can derail the prediction. Existing remedies are split: retrieval methods choose which examples to include but weight them uniformly; calibration methods adjust the output without identifying which demonstration to distrust; mechanistic interpretability reveals the latent inter-example structure but offers no way to act on it. We introduce ICL-BP, an inference-time augmentation that addresses all three. ICL-BP constructs a sparse pairwise factor graph from the model's own late-layer attention maps, runs a small fixed number of loopy belief propagation iterations to obtain per-example relevance beliefs, and uses those beliefs to additively edit the residual-stream context at the query token before decoding. Conditional on a linear-representation hypothesis, an attention--similarity alignment proxy, and a belief-collapse condition that we verify empirically rather than rate-prove, the bias of the implicit concept estimator falls quadratically in the fraction of misleading demonstrations; when no demonstration is misleading, ICL-BP reduces exactly to Standard ICL under uniform beliefs, with at most a 1/N2 noise inflation in the empirically-observed near-uniform case. On Llama-3.1-8B-Instruct with 16 demonstrations, ICL-BP improves over Standard ICL by a median +7.4 pp across eight benchmarks (+5.2 to +12.0) and over the strongest reweighting baseline BatchICL by +1.8~pp median (+1.2 to +2.4). Composed with SC-CoT on Llama-3.1-70B, it reaches 90.4% exact match on GSM8K and 80.5% on MMLU at under 10% wall-clock overhead.