On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck
Why binary data needs simpler shortcuts than other sources
When compressing information to predict a target outcome, mathematicians have a rule for how complex the compressed version needs to be—but it turns out the rule is stricter for binary (two-option) data than for anything else. This work proves that for binary sources, you never need more than two symbols in your compressed representation, tightening what was previously thought to be a universal limit.
The information bottleneck is used in machine learning and data compression to extract only the relevant parts of data for making predictions. Knowing that binary data can always be compressed into simpler representations without loss of quality makes these algorithms faster and more efficient. This sharpens the theoretical guarantees engineers rely on when building systems that learn from binary signals—like yes/no decisions or on/off states in sensors and diagnostics.