Golomb-Rice with base M is prefix code optimal for approximately geometric probability distribution Pr(x) ~ sqrt(2)^(-Mx). Arithmetic coding or FSE/tANS would allow to use the actual probability distribution. The question is how large the gain could be - how far from Shannon is Golomb-Rice for this specific type of data? If this probability distribution varies, maybe it's worth thinking about adaptive rANS, like in Oodle LZNA and BitKnit: https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/ ps. Is M fixed or adapting?