The applicability of model checking is often limited by the size of the industrial system. This is known as state space explosion problem. Compositional verification has been particularly successful in this regard. This paper presents an approach based on a refinement of search space partition for reducing the complexity in verification of models with non-deterministic choices and open environment. The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get better reduction. As reported in the case studies, search space partition improves the efficiency of verification with respect to the requirement of memory and obtains significant advantage over the use of the original one.