We introduce a class of probabilistic models on graphs motivated by coding and combinatorial optimization problems (e.g., LDPC codes, k-SAT, clustering). We show that for a large class of models, the conditional entropy between the information at the nodes and at the edges concentrates around a determnistic threshold. Joint work with A. Montanari.