Greedy Prompt Compression: Diagnosis, Prognosis, and a Cure

Every extractive prompt compressor greedily maximises a next-token fidelity objective, inheriting the 1-1/e guarantee of Nemhauser, Wolsey and Fisher. That theorem has three preconditions: non-negativity, monotonicity, and submodularity. We measure all three and all three are false. A structural theorem shows that any model computing an answer as a non-degenerate join of two context units has a strictly non-submodular fidelity function. On an exact 2^10 retention lattice, submodularity is violated on 47.8% of triples, the objective is non-monotone and can go strictly negative, and the submodularity ratio is negative on every retained prompt — so the weak-submodular rescue does not weaken the guarantee, it inverts it. There is no safe compression regime: across sixteen compression levels the violation holds near-constant from the lightest compression onward, and no per-genre threshold survives multiple-comparison correction. There is no cheap test: an exhaustive interaction census over four models finds a minimal witness in every prompt while predicting nothing about the regret greedy incurs. The violation rate is flat from 160M to 7B parameters. We give a bounded repair, PAIR, which measures pairwise interaction on a sampled probe set and repairs only the coalitions a first-order scorer splits. It beats one-shot scoring in 52 of 143 budget cells and loses in none; at deployment scale on a production compressor it reduces fidelity loss by 77% across 120 contexts with zero regressions. On downstream multi-hop QA the recovered fidelity does not measurably convert into recovered answers — reported as a null, with the floor effect that limits it stated explicitly. All numerals are generated from logged runs into a macros file; none is transcribed by hand.