In alloys cluster expansions (CE) are increasingly used to combine first-principles electronic-structure calculations and Monte Carlo methods to predict thermodynamic properties. As a basis-set expansion in terms of lattice geometrical clusters and effective cluster interactions, the CE is exact if infinite, but is tractable only if truncated. Yet until now a truncation procedure was not well defined and did not guarantee a reliable truncated CE. We present an optimal truncation procedure for CE basis sets that provides reliable thermodynamics. We then exemplify its importance in Ni3V, where the CE has failed unpredictably, and now show agreement to a range of measured values, predict new low-energy structures, and explain the cause of previous failures.