{"id":"95cf0645-67ca-4bc5-b86f-159e1c7a76c7","arxiv_id":"1908.08961","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For binary classification, the optimal tradeoff curve between stored bits and class information is achieved by binning the posterior class probability into contiguous intervals.","lead":"The authors show how to compress images into a few discrete groups while keeping as much information as possible about a binary label, and they map the full tradeoff curve between storage size and label information. The method works by first reducing each image to its estimated class probability, then optimally binning that probability into intervals; the authors prove these interval binnings achieve the optimal tradeoff for the discrete information bottleneck problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof establishes optimality among deterministic encoders of W, but the paper's headline claim is about deterministic encoders of X; the missing equivalence between sup over g(W) and sup over g(X) is asserted, not proved.","rationale":"I read the paper as claiming to compute the Pareto frontier of equation (1) over all deterministic maps X -> Z. The only theorem restricting the search to contiguous binnings is Theorem II.2, whose supremum is over deterministic functions of W. The data-processing inequality gives I(Z,Y) <= I(W,Y), but it does not imply that every feasible (H,I) point from an X-encoder can be matched or beaten by a W-only encoder. This is exactly the reader's weakest assumption, and I agree with it. The gap is not merely cosmetic: functions of X can randomize the bin assignment within level sets of W, producing stochastic channels W -> Z that the proof never analyzes. For binary Y, a concavity or extreme-point argument may close the gap, and the proposed brute-force test would check it. Until then, the correctness risk is real, and the paper's experimental claims about compressing X inherit the same caveat. I do not see grounds to reject: the analytic warmup, the exact comparison with Blahut-Arimoto, and the interval-binning theorem are correct for the narrower W-frontier problem, and the missing lemma may be true. The conditional verdict is therefore appropriate, and my read does not change it.","tokens_in":22050,"tokens_out":16380,"duration_ms":178733,"concrete_test":"Using the analytic toy model of Section III.A, extend X to (W, U) with U ~ Unif[0,1] independent of (W, Y), discretize both axes on a fine grid (e.g., 128 x 128), and for M = 2 and M = 3 brute-force the upper envelope of (H(Z), I(Z,Y)) over all deterministic maps X -> Z by enumerating grid partitions. Compare this envelope with the interval-binning frontier obtained from Theorem II.2 applied to W alone. If any brute-force point lies strictly above the interval-binning frontier, the asserted equivalence in Section II.C fails; if none does, the missing lemma is not contradicted and the proof gap is patchable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem II.2 proves that the Pareto frontier of equation (21) is spanned by contiguous interval binnings of W, where the supremum is over deterministic functions g: R -> {1,...,M}. The abstract and Section II.C then identify this with the original problem (1), where the supremum is over all deterministic encoders g: X -> Z. Because W is a deterministic function of X, every W-only encoder is an X-encoder, so the theorem gives achievability. But the converse is not established: an X-encoder may depend on the within-level-set variation of X given W, inducing a stochastic map W -> Z that is not representable as a deterministic function of W. The paper never proves that such stochastic channels cannot achieve a better (H,I) tradeoff than any deterministic interval binning of W. The data-processing inequality only bounds I(Z,Y) by I(W,Y); it does not guarantee that for every feasible (H(Z), I(Z,Y)) from an X-encoder there exists a W-only interval binning with the same or better pair. This missing equivalence is load-bearing because the central claim that the full Pareto frontier for compressing X is obtained by binning W rests on it. The theorem's proof itself treats only deterministic g(W), so the gap is not a small omitted detail in the proof but an unproven premise linking the abstract's claim to the theorem. A concavity or extreme-point argument might close the gap, since for binary Y the objective depends on averages of the monotone posterior p(w), but no such argument appears in the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses lossy compression of a data variable X into a discrete code Z=f(X) for binary classification, with the goal of mapping the Pareto frontier of (H(Z), I(Z,Y)). It first proves a lossless distillation theorem: for Y in {1,...,n}, the posterior vector W=P(Y|X) satisfies I(W,Y)=I(X,Y), so W is a sufficient statistic. For binary Y, the paper then claims that after uniformizing W and making the conditional probability P(Y=1|W) monotone, the entire Pareto frontier of the original compression problem is obtained by binning W into contiguous intervals. This reduces the frontier computation to a one-dimensional search over bin boundaries. The method is demonstrated on an analytic toy model, MNIST, Fashion-MNIST, and CIFAR-10, and is compared with the Blahut-Arimoto method for the DIB objective. The paper also interprets DIB phase transitions as transitions between 'corner' points of the Pareto frontier.","tokens_in":22346,"tokens_out":10061,"duration_ms":115822,"significance":"If the main theorem is fully established for the original X-compression problem, this is a valuable result: it gives an exact, finite-dimensional characterization of the DIB Pareto frontier under a monotone-likelihood condition, replacing iterative approximations with a direct search and clarifying the non-concave structure of the frontier. The lossless distillation theorem (Theorem II.1) is clean and correct, and Appendix A provides a quantitative bound on the information lost by fine binning. The release of code and the comparison with Blahut-Arimoto are also strengths. The principal weakness is a scope gap: the proof of Theorem II.2 is carried out for deterministic functions of W, whereas the paper's headline claims are about deterministic functions of X. The result is likely repairable, but the missing reduction is load-bearing.","major_comments":[{"comment":"The original problem in Eq. (1) optimizes over deterministic encoders g: X -> Z, but Theorem II.2 and Eq. (21) optimize over deterministic encoders g: W -> Z. The proof of Theorem II.2 even begins by writing 'Z≡g(X)' and then immediately defines μ_i = {w ∈ [0,1] : g(w)=i}, so the argument is entirely about functions of W. Because W is a deterministic function of X, every W-encoder is an admissible X-encoder, which gives achievability of the frontier by binning W. The converse, however, is not established: an X-encoder may split individual level sets {x : w(x)=w} and thereby induce a genuinely stochastic map from W to Z, and the data-processing inequality I(Z,Y) ≤ I(W,Y) does not imply that every such X-encoder is dominated by a deterministic W-encoder. This missing equivalence is load-bearing because the abstract and Section II.C claim that the full Pareto frontier for compressing X is obtained by binning W. The authors should either prove the reduction (for example, by showing that any stochastic channel W -> Z is dominated by a deterministic W -> Z for the (H,I) tradeoff, or by a direct extreme-point argument), or restate Theorem II.2 as a result about the W-compression problem and weaken the claims about X accordingly.","section":"§II.B.4, Eq. (21); §II.C"},{"comment":"The proof's swap argument assumes that the non-contiguous binning has a bin k whose support has two separated components with some other bin l occupying the interval between them. The text handles the case p_k = p_l by saying it 'swap[s] to entirely eliminate the discontiguity, and repeat[s] our swapping procedure between other bins until we increase the entropy (again obtaining a contradiction) or end up with a fully contiguous binning.' This case is not proved in detail: it is not shown that the required swaps can always be performed without changing the marginal bin probabilities, nor that the process terminates with a definite contradiction when a non-contiguous optimal binning exists. Since the theorem is the central result, this gap should be closed with a precise argument or by citing a standard result.","section":"§II.B.4, proof of Theorem II.2"}],"minor_comments":[{"comment":"In Theorem II.2, the notation 'bin boundaries b1 < ... < bn−1' reuses n, which already denotes the number of classes; use a different symbol such as M or N for the number of bins.","section":"§II.B.4"},{"comment":"In the definition of f(w,a), the variable x appears inside the sum and in the polynomial term, but the function is written as a function of w; replace x with w for consistency.","section":"§II.B.2, Eq. (31)"},{"comment":"The first sentence of the proof says 'Z≡g(X)' even though the theorem concerns g(W); this wording obscures the fact that the proof does not address general functions of X and should be corrected.","section":"§II.B.4, proof of Theorem II.2"},{"comment":"The CIFAR-10 entries for cat and dog appear as two-line rows, which makes it unclear which coefficient vector corresponds to which class and how the two lines relate to equations (34)–(38); please format this more clearly.","section":"Table II"},{"comment":"There are a few typos: 'can be conveniently be found' in the abstract and 'traveoff' in Section III.D should read 'can conveniently be found' and 'tradeoff', respectively.","section":"Abstract and §III.D"}],"recommendation":"major_revision","confidential_remarks":"The main technical gap is the X-to-W reduction in Theorem II.2. The rest of the paper is sound; if the authors can supply the missing proof or appropriately restrict the claims, the paper would be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuinely useful paper for the DIB crowd. The Contiguous Binning Theorem is a real extension of Kurkoski-Yagi's fixed-bin-count optimality result to the full entropy-information frontier, and the experimental demonstration on real images is engaging. But the paper's own headline claim—that this solves the Pareto frontier for compressing X—is not quite what the proof shows. The theorem proves optimality among deterministic functions of the distilled posterior W. Every W-only encoder is an X-encoder, so that direction is fine. The other direction is missing: an arbitrary deterministic g(X) induces a stochastic channel from W to Z, and the proof never shows that some deterministic binning of W can match or beat that channel. A concavity/extreme-point argument could likely close this, and the classical likelihood-ratio quantizer results suggest it is true, but it is not in the paper. That is a load-bearing omission, not a footnote.\n\nThe lossless distillation theorem is correct (it is the sufficiency of the posterior, well known), and the uniformization/sorting steps are sensible. The proof of Theorem II.2 itself is solid; the swapping argument is clean. I also credit the authors for explicitly noting that the DIB linear objective cannot find convex parts of the frontier, which is a real insight, and for the comparison against Blahut-Arimoto on the toy example.\n\nSofter issues: the monotonicity assumption is handled by binning and sorting, which is only approximate for continuous W; fine in practice, but the theorem is stated for the continuous case. The experiments report '99% of class information' for CIFAR-10 with five bins, but that figure is relative to a lower bound on I(X,Y) derived from the classifier's cross-entropy, and there are no error bars or repeated runs. The GitHub link is given but without a commit hash, so reproducibility is slightly weaker than ideal. None of these are fatal, but a referee should ask for the X-to-W step to be proven or stated as an assumption, and for the information numbers to be qualified as lower-bound estimates.\n\nPaper is for readers working on information bottleneck, likelihood-ratio quantization, or interpretable clustering. It deserves a serious referee, even though my own verdict would be conditional on the gap being patched.","headline":"A clean theorem about binning the posterior, but the headline claim about compressing X is one reduction step ahead of the proof.","tokens_in":22879,"tokens_out":13735,"would_cite":true,"duration_ms":139633,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A17","62B10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For binary classification, the Pareto-optimal lossy compressions are exactly contiguous binnings of the class-probability score.","keywords":["Pareto frontier","lossy compression","mutual information","Discrete Information Bottleneck","binary classification","posterior probability binning","sufficient statistic","image clustering"],"falsifier":"Enumerate every two-group partition of a small uniform score W with increasing P(W|Y=1) and check whether any non-contiguous grouping gives more label information at the same entropy than the best contiguous binning; one such point would refute the theorem.","tokens_in":21807,"feed_emoji":"🎯","tokens_out":10418,"duration_ms":100433,"temperature":0.7,"pith_summary":"This paper is about the trade-off between how many bits you keep from a data set and how much label information those bits retain. Its thesis is that for binary classification this trade-off has a simple exact solution: the only compressions that need to be considered are groupings of the classifier's probability score P(Y=1|X) into contiguous intervals. It first proves the score itself is a lossless distillation, so replacing each image by one real number W=P(Y=1|X) loses no mutual information with the label. Then it proves that binning W into adjacent intervals spans the full Pareto frontier of entropy versus mutual information, turning a hard multiobjective search into a one-dimensional scan of bin boundaries. The payoff is that optimal image clustering, as demonstrated on cats-versus-dogs and digits, becomes an information-theoretically principled procedure rather than a heuristic.","feed_headline":"Best compressed label is a bin of the class-probability score","feed_subtitle":"Grouping that score into contiguous intervals provably maximizes label information per stored bit.","key_machinery":"The load-bearing object is W, the distilled posterior P(Y|X), normalized to a uniform random variable and sorted so the conditional probability P(W|Y=1) increases. The compression is the contiguous binning function B(W,b), which sends W to the integer label of the interval containing it. The Contiguous Binning Theorem (Theorem II.2) is the mechanism: it reduces the original infinite search over encodings of X to a finite-dimensional search over bin-boundary vectors, using a swap operation that moves small measure between bins to push conditional probabilities apart, thereby increasing I(Z,Y) at fixed H(Z).","core_discovery":"The central claim is the Contiguous Binning Theorem: if the distilled score W is uniformly distributed and P(W|Y=1) is monotonically increasing, then every Pareto-optimal point (H(Z), I(Z,Y)) is realized by binning W into contiguous intervals. Consequently the points that maximize I(Z,Y) for a fixed number of bins m, the corners of the frontier, can be found by ordinary single-objective optimization over bin boundaries instead of multiobjective or iterative schemes. The proof works by swapping tiny pieces of measure between bins with different conditional probabilities; because such swaps spread the conditional probabilities further apart, they strictly raise mutual information while keeping both marginals fixed. Repeating the swap eliminates any non-contiguous support. Since uniformization and sorting by conditional probability are lossless, the theorem applies to any binary classification task once W is estimated, and the paper verifies the resulting frontiers on MNIST, Fashion-MNIST, and CIFAR-10. Those frontiers turn out to be non-concave, which explains why the linear DIB objective jumps between corners: the phase transitions reported in DIB learning are transitions between different cluster counts.","pith_inferences":["Editorial inference: the contiguous-binning theorem suggests a calibration test: when the trained score W is well calibrated (P(Y=1|W)=W), the exact frontier can be computed from the empirical distribution of W alone, so the method should transfer to any probabilistic classifier, not just neural networks.","Editorial inference: for multi-class tasks the lossless distillation produces an (n-1)-dimensional posterior vector, and the likely generalization is that optimal frontiers live on contiguous regions of the probability simplex ordered by likelihood ratio; a direct extension would make the bin-boundary scan exponential in classes.","Editorial inference: because the frontiers are non-concave, any downstream system that pays a linear cost per stored bit will prefer the corners; this predicts that practical soft-classifier designs with a storage penalty should use a few well-chosen bins rather than interpolating along the frontier.","Editorial inference: the vertical-binning reformulation suggests a practical shortcut that the paper notes but does not develop: bin the conditional probability P(Y=1|W) itself into equal-width slices, which can be implemented without fitting the distribution f(W|Y)."],"forward_implications":["For binary classification, the full trade-off curve can be mapped exactly by scanning bin boundaries, without multiobjective optimization or iterative Information Bottleneck alternation.","The DIB phase transitions observed in prior work are transitions between frontier corners, i.e., changes in the number of clusters, because the frontier is non-concave.","Grouping images into a handful of clusters by probability score retains nearly all useful label information: the paper reports five clusters capture 99% of the available information in the cat/dog example.","High classification accuracy does not imply high information retention; 99% binary accuracy corresponds to roughly 0.92 bits, and simply rounding the probability score to fixed decimals is suboptimal.","The resulting clusters are deterministic and information-theoretically optimal soft classifiers, with the usual generalization benefits of compression."],"supporting_citations":[{"why":"defines the Information Bottleneck objective I(Z,Y)-βI(Z,X), the problem family the paper generalizes and compares against.","marker":"[10]"},{"why":"introduces the Deterministic Information Bottleneck objective I(Z,Y)-βH(Z), whose linear form misses convex stretches and whose phase transitions the paper explains.","marker":"[12]"},{"why":"argues the interesting DIB-frontier points are corners, motivating the paper's focus on fixed bin-count optima.","marker":"[23]"},{"why":"supplies the Blahut-Arimoto iterative relaxation used as the baseline in the paper's frontier comparison.","marker":"[27]"},{"why":"together with the preceding marker, gives the alternating-minimization algorithm the paper compares against.","marker":"[28]"},{"why":"addresses maximizing I(Z,Y) for a fixed number of bins, which corresponds to the corner points derived from the frontier.","marker":"[9]"},{"why":"provides the multiobjective optimization algorithm used to locate bin boundaries in the numerical scans.","marker":"[17]"}],"fun_headline_variants":["Contiguous binning of class scores is Pareto-optimal for binary labels","Optimal binary compression bins the class-probability score contiguously","Contiguous bins of score are provably optimal for binary label info","Pareto-optimal label compression is just contiguous binning of W","Contiguous binning theorem settles binary compression frontier"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method compresses the distilled score W rather than the raw data X, and the whole claim rests on W carrying everything X knows about Y; the paper states this but does not separately prove that an optimal encoder for X can always be replaced by one reading only W.","fun_headline_variants_meta":{"raw":{"variants":["Contiguous binning of class scores is Pareto-optimal for binary labels","Optimal binary compression bins the class-probability score contiguously","Contiguous bins of score are provably optimal for binary label info","Pareto-optimal label compression is just contiguous binning of W","Contiguous binning theorem settles binary compression frontier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000918,"raw_usage":{"total_tokens":4038,"prompt_tokens":1142,"completion_tokens":2896,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":758,"completion_tokens_details":{"reasoning_tokens":2820}},"tokens_in":758,"tokens_out":2896,"duration_ms":19128,"temperature":1.0,"reasoning_tokens":2820,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:26:38.881824+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate every two-group partition of a small uniform score W with increasing P(W|Y=1) and check whether any non-contiguous grouping gives more label information at the same entropy than the best contiguous binning; one such point would refute the theorem.","supporting_citations":[{"cited_title":"Goodfellow, J","cited_arxiv_id":null,"evidence_quote":"introduces the Deterministic Information Bottleneck objective I(Z,Y)-βH(Z), whose linear form misses convex stretches and whose phase transitions the paper explains."},{"cited_title":"Chalk, O","cited_arxiv_id":null,"evidence_quote":"argues the interesting DIB-frontier points are corners, motivating the paper's focus on fixed bin-count optima."},{"cited_title":"Krizhevsky, V","cited_arxiv_id":null,"evidence_quote":"supplies the Blahut-Arimoto iterative relaxation used as the baseline in the paper's frontier comparison."},{"cited_title":"LeCun, C","cited_arxiv_id":null,"evidence_quote":"together with the preceding marker, gives the alternating-minimization algorithm the paper compares against."},{"cited_title":"cat” and “dog","cited_arxiv_id":null,"evidence_quote":"addresses maximizing I(Z,Y) for a fixed number of bins, which corresponds to the corner points derived from the frontier."},{"cited_title":"Latent Representations of Dynamical Systems: When Two is Better Than One","cited_arxiv_id":"1902.03364","evidence_quote":"provides the multiobjective optimization algorithm used to locate bin boundaries in the numerical scans."}],"review_version":1}