Software that interacts with a physical environment must operate with a partial and imprecise knowledge, due to the inaccuracy of its sensors. Belief programming is a programming methodology that addresses this issue. It provides a framework to reason about the possible states of a system given a set of assumptions—or beliefs—about its variables. This technique is, however, prone to state space explosion, as pointed out by its authors. A straightforward implementation based on exhaustive search will run out of memory when assumptions are not sufficiently tight. In this paper, we present a new model to overcome this issue. By using Map Family Decision Diagrams to maintain a compact representation of the possible states of the system, our approach scales to a large number of variables and is yet able to perform safety checks efficiently. We developed a belief programming framework based on that model, outperforming the original implementation by several orders of magnitude.