CS Paper Radar

When Information Is Not Enough: Accuracy-Constrained Thermodynamic Costs of Binary Classification

Xuening Wu

cs.IT ·submitted 2026-09-25 14:17 UTC · v1
theory

Abstract

How much entropy must a physical classifier produce to achieve a prescribed accuracy? Rate--distortion theory specifies the minimum information required, but does that information threshold suffice to determine the physical cost? We show that it does not, even for a binary task and a two-state memory. For a uniform binary target observed through a finite symmetric experiment, replacing the classification-error constraint with its necessary mutual-information threshold strictly lowers the infimum of entropy production under a common operation time, integrated mobility budget, and sufficiently large finite transition-rate cap. The separation holds whenever the target error lies strictly between the Bayes error of the observations and chance. Two results establish this physical gap. First, ordering observations by posterior confidence gives exact transport--risk and transport--information frontiers. Observations with the same Bayes error can have different cost frontiers. Second, we construct bounded-rate protocols that realize prescribed encoders with write probabilities below one, starting from exact reset, with an explicit excess cost above the transport bound. An achievable information-constrained cost then falls below a lower bound valid for every task-feasible protocol. Examples with repeated noisy observations illustrate the separation. The results identify a limitation of information-only benchmarks for physical classification: task accuracy and kinetic constraints must be retained explicitly. The cost analyzed is total entropy production during memory writing, excluding data acquisition, controller operation, and subsequent reset.

Closest papers

Nearest neighbours by meaning across the whole index.

Mutual Information Constrained Chernoff Bottleneck

cs.IT cs.LGmath.OCmath.ST+1 ·2026-09-29 ·Dier Tang, Guangyue Han
similarity 0.61
Abstract · 35 pages, 4 figures, 3 tables. Feedback and comments are welcome!

The classical information bottleneck (IB) measures the relevance of a representation $U$ of $X$ to a target $Y$ by $I(U;Y)$, which does not directly characterize the error of downstream decisions. For a binary hypothesis $Y$ inferred from many separately encoded observations, the optimal error exponent is the Chernoff information between the two conditional distributions of $U$ given $Y$. We study the mutual information constrained Chernoff bottleneck, which seeks an encoder that maximizes this Chernoff information subject to a rate constraint $I(U;X) \leq R$. We show that its optimal value $C(R)$ increases strictly up to $R = H(V)$, where $V$ merges the symbols of $X$ with equal likelihood ratio, remains at the uncompressed exponent beyond, and, unlike the IB curve, need not be concave. We further show that $k+1$ outputs suffice to attain $C(R)$, where $k$ is the cardinality of $V$. We propose an alternating algorithm that updates the encoder via a generalized Blahut--Arimoto algorithm and the Chernoff parameter $s$ via a nonlinear equation, and prove that its iterates remain feasible, with nondecreasing and convergent Chernoff information. Comparing with the classical IB for $n$ samples, we show that, whenever the two objectives disagree, the IB encoder has the smaller equivocation $H(Y|U^{n})$ at $n = 1$, whereas the Chernoff bottleneck has the smaller error probability and equivocation for all large $n$. Numerical experiments confirm the theory, and on real topic-detection data from the 20 Newsgroups corpus, compressing each word to only $17\%$ of its entropy retains $90\%$ of the error exponent and nearly the accuracy of the uncompressed classifier.

0.40

Evaluating and Recalibrating Probabilistic Classifiers from One-Bit Threshold Queries

cs.LG ·2026-09-04 ·Roman Plaud, Antoine Saillenfest, Matthieu Labeau, Thomas Bonald, Willem Waegeman
similarity 0.60
Abstract · Extended and revised version with additional theory and experiments

Standard calibration evaluation and recalibration methods assume access to predicted probabilities. We study one-bit threshold access, a setting in which probabilities are hidden and the evaluator observes only whether the predicted probability exceeds a single chosen threshold per sample. Under this restriction, we show that classifiers can nevertheless be evaluated and recalibrated without reconstructing their hidden scores. We derive a consistent estimator of True Calibration Error, unbiased estimators of strictly proper scoring rules, and a one-bit objective for Temperature Scaling whose expectation matches the standard log-loss objective. Across these settings, we quantify the statistical cost incurred by replacing standard probability-access procedures by our one-bit estimators. Finally, we instantiate the framework for black-box LLMs, where the logit_bias API parameter allows us to realize the required threshold queries in zero-shot binary question answering.

0.26

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.60
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16

Information-Theoretic Analysis of Next-Token Prediction under Markovian Data

cs.IT stat.MLcs.LG ·2026-09-28 ·Masoud Kavian, Abdellatif Zaidi, Milad Sefidgaran
similarity 0.60
Abstract · 49 Pages, 6 Figures

We develop an information-theoretic framework for generalization in next-token prediction under temporally dependent data. We consider independent trajectories generated by finite-memory Markov processes and distinguish algorithmic dependence, quantified by mutual information, from temporal dependence, characterized by mixing. For cross-entropy loss, we derive an expected generalization bound using the Donsker--Varadhan variational representation and a McDiarmid-type concentration inequality for Markov chains. A refinement captures the joint effect of context length and temporal mixing through the mixing properties of the history-state process. We then extend the bound through a rate--distortion formulation, replacing mutual information with the minimum information rate required to represent the learned model within a prescribed distortion in the generalization gap, yielding informative guarantees for deterministic algorithms over continuous hypothesis spaces. For margin-based prediction, we derive explicit bounds for linear and self-attention next-token predictors via noisy low-dimensional compression, revealing the roles of context length, model complexity, sample size, margin, and temporal mixing. Experiments on TinyStories and ETTh2 show that longer contexts can reduce both training and test losses, but typically reduce training loss more, enlarging the generalization gap. A complementary ETTh2 analysis identifies an effective predictive-memory scale near 24 hours, with no statistically supported improvement beyond this scale, offering a plausible explanation for test-performance saturation at larger contexts.

0.31

Communication Complexity of Universal Features

cs.DS stat.MLcs.LG ·2026-10-19 ·Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor, Abhishek Shetty
theory similarity 0.60
Abstract

Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes $X\sim D$ and produces a finite encoding before a task $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ is specified. For each task, a decoder must predict $f(X)$ with error at most $\varepsilon$ under $D$. We construct an encoder that outputs a representation with $O(d^{*}\log(1/\varepsilon))$ bits, where $d^{*}$ is the dual VC dimension of $\mathcal{F}$. Our encoder greedily selects $O((d^{*}/\varepsilon)\log(1/\varepsilon))$ functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every $d^* \ge 1$ and $\varepsilon < 1/4$ up to a universal constant factor, and instance-wise optimal for every family $\mathcal{F}$ up to an $O(\log(1/\varepsilon))$ factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.

0.21

What Should an Information Bottleneck Encoder Learn? Separating Representation Learning from Rate Control

cs.LG cs.IT ·2026-10-26 ·Hassan Tavakoli, Bella Bose
similarity 0.59
Abstract

The information bottleneck (IB) trades compression of an input $X$ against prediction of a target $Y$ through a multiplier $β=1/λ$, yet each operating point is usually served by training, or fully conditioning, a new encoder. For jointly Gaussian data, we show that the IB solution factorizes as $A(β)=D(β)W$: the information-bearing directions $W$ do not depend on $β$, and $β$ acts only through scalar gains. We ask whether this separation of \emph{representation} from \emph{rate control} survives beyond Gaussian models, treating the budget as a given operating parameter rather than a quantity to be optimized. For a budget-free representation \(F(X)\), the \emph{separation gap} is controlled by the \emph{sufficiency deficit} $ε_F=I(X;Y\mid F(X))$: We show there is at least $ε_F$ in the worst case for finite inputs, and it is bounded uniformly in $λ$ by a function of $ε_F$ for finite label alphabets. The same certificate extends to a new target distribution and to pooled multi-domain data, where a conditional-alignment term appears. On MNIST, SVHN, CIFAR-10 and STL-10 (10 seeds, eight prespecified budgets), a frozen CNN representation with one compressor--decoder pair per budget reduces estimated training multiply--accumulate operations (MACs) by $7.7\times$ and wall-clock time by about $2\times$ relative to end-to-end VIBs, and attains higher budget-averaged accuracy ($65.6\%$ versus $57.3\%$ per domain; $67.1\%$ versus $57.1\%$ pooled), with the advantage concentrated at strong compression, where the VIBs collapse. At weak compression ($λ\le0.036$), VIB has higher cross-entropy and ECE; its surrogate Lagrangian is higher per domain, indistinguishable from the pooled VIB in the macro average, and lower on the pooled test set.

0.10

Thermodynamic characterization of message-passing: Framework and initial study

cs.IT cond-mat.stat-mech ·2026-10-26 ·Kalana G. Abeywardena, Stark C. Draper
publishedtheory similarity 0.59
Abstract · Published in IEEE Journal on Selected Areas in Information Theory (JSAIT), August 2026. 36 pages, 10 figures

We study the thermodynamic efficiency of message-passing decoders using the mismatch cost framework. This framework quantifies the excess entropy generated when a system operates away from the thermodynamically optimal initial distribution. It provides a computable lower bound on irrecoverable energy loss. The decoder is modeled as a main decoding program with local message updates implemented as subroutines. Memory is treated as an external copying subsystem whose thermodynamic cost is excluded. Studying the $[7,4]$ Hamming code transmitted over a binary erasure channel, we show how the channel-induced initialization statistics and the step-wise evolution of the algorithmic state distribution during decoding determine the total mismatch cost. We further show that different thermodynamically optimal state distributions, representing different underlying physical implementations of the decoder, can produce different thermodynamic costs for identical decoding dynamics. Conditioning the input distribution on correctable and non-correctable erasure patterns further reveals distinct thermodynamic signatures. These results demonstrate that thermodynamic cost is jointly governed by decoding dynamics, input statistics, and hardware characteristics. This points to opportunities for thermodynamically-informed decoder design to realize energy-efficient physical implementations.

0.59

Physics of Information Geometry - Part I: Principle of Least Action on the Probability Simplex

cs.IT cond-mat.stat-mech ·2026-09-08 ·C. Emre Koksal, Deniz Sargun
similarity 0.58
Abstract

We develop a least-action framework for describing how a probability distribution can evolve from an equilibrium state to a prescribed nonequilibrium state under constrained incremental changes. Taking a Gibbs distribution as the equilibrium reference, the framework gives a direct physical meaning to the geometry of the probability simplex: distance from equilibrium corresponds to nonequilibrium free energy, while changes between successive distributions carry an informational kinetic cost. The Pythagorean structure of relative entropy then provides the central insight of the work. It shows that intermediate distributions chosen via sequential information projections can reduce the kinetic cost of large transitions and establishes an energy-conservation-like relation between the kinetic expenditure along a path and the free energy accumulated in reaching the target distribution. Motivated by this geometry, we construct a greedy least-action path through successive information projections, obtain a closed-form characterization of each projection through the Lambert W function, and establish a finite-step performance guarantee. We further show that state-dependent costs can be incorporated naturally by reshaping the underlying Gibbs reference, providing a thermodynamic interpretation of path penalties as modifications of the effective energy landscape. Together, these results provide a unified view of distributional evolution through least action, information geometry, and nonequilibrium thermodynamics.

0.41