  Minimum-entropy coupling (MEC) -- the process of finding a joint distribution
with minimum entropy for given marginals -- has applications in areas such as
causality and steganography. However, existing algorithms are either
computationally intractable for large-support distributions or limited to
specific distribution types and sensitive to hyperparameter choices. This work
addresses these limitations by unifying a prior family of iterative MEC (IMEC)
approaches into a generalized partition-based formalism. From this framework,
we derive a novel IMEC algorithm called ARIMEC, capable of handling arbitrary
discrete distributions, and introduce a method to make IMEC robust to
suboptimal hyperparameter settings. These innovations facilitate the
application of IMEC to high-throughput steganography with language models,
among other settings. Our codebase is available at
https://github.com/ssokota/mec .
