Rate–Distortion Dictionaries for Reconstruction and Generation

Deploying a family of $\beta$-VAE codecs at multiple rate–distortion operating points is straightforward; deciding which of them to keep is not. We study the problem of selecting a small dictionary of $k$ frozen codecs from a larger candidate frontier so that every future request is served by its single nearest deployed atom. We show that this constrained $k$-medoids problem is not solvable by the classical one-dimensional clustering dynamic program, because nearest-atom assignment is provably non-monotone once matching is judged against points external to the frontier. We restore tractability by freezing, independently of $k$, which frontier atom each request would use on the full unreduced frontier, which makes the resulting surrogate objective exactly solvable by an $O(M^2(N+k))$ dynamic program. We then certify this surrogate: an exact identity for its gap to the true deployed loss, a geometric bound computable before optimization, and a finite-sample guarantee that extends the certificate to the underlying population objective. Experiments across three datasets show the certificate is non-vacuous and that the resulting dictionary matches or exceeds standard selection heuristics.