A sample compression scheme summarizes a finite labeled sample by retaining a bounded number of its examples, possibly with a bounded amount of auxiliary information,
so that a fixed reconstruction rule produces a hypothesis agreeing with every label
in the original sample (Floyd and Warmuth 1995). For a binary concept
class , the realizable version applies to
every finite sample labeled by some member of
.
A labeled scheme of size
retains an unordered subset of at most
labeled examples and at most
auxiliary bits. Its reconstruction need not be a member of
.
Cai et al. (2026, Theorem 1.1) gave such a scheme for every binary concept class of finite Vapnik-Chervonenkis
dimension , with
and , where
denotes big-O notation.
These bounds are independent of the number of examples and hold for finite or infinite
domains. They improve the exponential dependence on
established by Moran and Yehudayoff (2016). The conjecture
that
examples suffice remains open. The result is an existence bound on compression size
and does not assert a polynomial running time.
The scheme can retain only labels: the remaining retained examples need only
be stored without their labels, using the same auxiliary-bit bound (Cai et al.
2026, Remark 1.2). This is a mixture of labeled and unlabeled examples,
rather than a wholly unlabeled scheme. The same bounds also admit reconstruction
with no more errors on an arbitrary labeled sample than the best member of
on that sample.
Cai et al. (2026) report that the proof was obtained autonomously by the Cogentic multi-agent system using Gemini 4 Carbon; the authors subsequently simplified the proof and take responsibility for its correctness.