Forming Pairwise Coherent Event Probabilities from Language Models

Large language models (LLMs) are increasingly asked for numerical probabilities of uncertain events. Individually, these estimates are often reasonable; collectively, they are frequently incoherent: no joint distribution realizes all of the reported marginal and pairwise-intersection probabilities at once. Existing remedies (prompting, calibration, fine-tuning, learned representations) reduce incoherence but do not eliminate it, while trivially coherent substitutes such as assuming independence discard the information in the judgments. We present, to our knowledge, the first model-agnostic post-processing method for LLM probabilities that guarantees exact pairwise coherence while certifiably staying closest to the original judgments. Starting from the classical fact that a co-occurrence matrix is pairwise coherent if and only if it is a probability mixture of binary outer products (i.e., lies in the full correlation polytope), we cast coherence enforcement as a projection onto this polytope up to a global rescaling, and solve it by column generation: an exactly solved 0-1 quadratic program selects new “possible worlds” and an active-set nonnegative least squares solver refits their weights. For every input and every stopping tolerance, the output is coherent by construction and comes with an explicit joint distribution certifying it; the stopping rule also certifies global optimality of the projection up to that tolerance. Deciding coherence is NP-complete, but hardness affects only worst-case running time, never correctness. On event families with known ground truth, four LLMs are substantially incoherent. Local Fr\'echet repairs and calibration-style rescaling (even when fit to the ground truth) reduce but never eliminate this incoherence, whereas our projection eliminates it, lowers root mean squared error in 35 of 40 model–premise settings, and attains the lowest error of all compared methods in 29.