The negative sign problem in quantum Monte Carlo (QMC) simulations of cluster impurity problems is the major bottleneck in cluster dynamical mean field calculations. In this paper we systematically investigate the dependence of the sign problem on the single-particle basis. We explore both the hybridization-expansion and the interaction-expansion variants of continuous-time QMC for three-site and four-site impurity models with baths that are diagonal in the orbital degrees of freedom. We find that the sign problem in these models can be substantially reduced by using a non-trivial single-particle basis. Such bases can be generated by diagonalizing a subset of the intracluster hoppings.