  The coalgebraic $\mu$-calculus provides a generic semantic framework for
fixpoint logics over systems whose branching type goes beyond the standard
relational setup, e.g. probabilistic, weighted, or game-based. Previous work on
the coalgebraic $\mu$-calculus includes an exponential-time upper bound on
satisfiability checking, which however relies on the availability of tableau
rules for the next-step modalities that are sufficiently well-behaved in a
formally defined sense; in particular, rule matches need to be representable by
polynomial-sized codes, and the sequent duals of the rules need to absorb cut.
While such rule sets have been identified for some important cases, they are
not known to exist in all cases of interest, in particular ones involving
either integer weights as in the graded $\mu$-calculus, or real-valued weights
in combination with non-linear arithmetic. In the present work, we prove the
same upper complexity bound under more general assumptions, specifically
regarding the complexity of the (much simpler) satisfiability problem for the
underlying one-step logic, roughly described as the nesting-free next-step
fragment of the logic. The bound is realized by a generic global caching
algorithm that supports on-the-fly satisfiability checking. Notably, our
approach directly accommodates unguarded formulae, and thus avoids use of the
guardedness transformation. Example applications include new exponential-time
upper bounds for satisfiability checking in an extension of the graded
$\mu$-calculus with polynomial inequalities (including positive Presburger
arithmetic), as well as an extension of the (two-valued) probabilistic
$\mu$-calculus with polynomial inequalities.
