Markov chain Monte Carlo algorithms for Dirichlet process-based models typically rely on either marginalization or truncation, with the latter yielding approximate inference and introducing non-vanishing bias in the resulting partition structure. Slice sampling provides a notable exception: by introducing auxiliary slice variables, it avoids marginalization and enables exact posterior inference. However, standard slice samplers require an unbounded number of operations per iteration, making it difficult to control the computational cost and practical scalability. To formally quantify this cost, we derive high-probability asymptotic bounds on the complexity of slice sampling in Dirichlet process mixture models, showing that, under general cluster-growth regimes, the overhead introduced by slice variables is at most an additive Op(ln n). Building on this result, we propose a novel, exact ""hybrid'' slice-sampling algorithm for posterior inference in hierarchical Dirichlet process (HDP) mixture models that combines the strengths of conditional slice samplers with marginal Chinese Restaurant Franchise representations. We also provide a theoretical analysis of the algorithm’s scalability, alongside that of competing methods. The proposed sampler dynamically instantiates only the minimal number of global atoms and tables required for exact updates, thereby enabling finite-dimensional updates without introducing systematic truncation bias. In numerical experiments, the hybrid sampler achieves substantial per-iteration cost reductions relative to existing exact HDP algorithms, and moderate reductions relative to approximate HDP procedures, while simultaneously improving mixing and inferential performance. [This is joint work with F. Gaffi.]