Why Your Prompt Compressor Is Deleting the Wrong Tokens: An Information-Theoretic Diagnosis

Token-level compression of in-context learning (ICL) demonstrations reduces inference cost but degrades classification accuracy past a task-dependent threshold, irrespective of the selection criterion. We establish a formal information-theoretic basis for this regularity. Modeling ICL as Bayesian posterior inference over a latent label mapping $\Theta$ and applying Fano's inequality, we derive a lower bound on $K$-class error under arbitrary token excision that decomposes into a *task-intrinsic* term invariant to any compression operator and a *mapping-dependent* term the data-processing inequality forces to decrease with the excision fraction, delimiting an *incompressible information core*. We further diagnose *why* self-information-based selectors systematically delete the wrong tokens: label and delimiter tokens carry disproportionate attention weight yet low self-information, causing widely-used criteria to excise precisely the tokens most critical to posterior updating. A complementary sensitivity analysis yields a strict severity ordering (flipped $\geq$ arbitrary $\geq$ semantic) across label regimes, governed by the prior-to-posterior Kullback--Leibler divergence each regime must surmount. All theoretical predictions are corroborated across 195 experimental configurations (four model families, four benchmarks, five compression strategies, three label regimes).