We present a variance-reduced method for efficiently solving the Boltzmann equation in all rarefaction regimes. The proposed method is based on the VRDSMC method of Al-Mohssen and Hadjiconstantinou (2010) [50], which exploits the correlation between two DSMC simulations using the same random numbers to significantly reduce the statistical uncertainty associated with moment estimation. This variance-reduction formulation is preferred here because it requires minimal change to the underlying DSMC method and code base. The instability reported in the collision-dominated regime in this previous work is removed via a combination of Kernel Density Estimation, a hierarchy of moment conservation constraints and a Maximum Entropy formulation for minimizing the bias introduced by the stabilization process. The resulting method is referred to as maximum-entropy variance-reduced direct simulation Monte Carlo (ME-VRDSMC). Computational experiments show that the proposed algorithm provides an efficient and accurate method for solving the Boltzmann equation in the low-signal limit. We also show that, similar to VRDSMC, the relative statistical noise of the proposed method is decoupled from the signal magnitude, leading to a substantial speedup compared to DSMC in the small-signal limit.