For lack of general algorithmic methods that apply to wide classes of logics, establishing a com-
plexity bound for a given modal logic is often a laborious task. The present work is a step towards
a general theory of the complexity of modal logics. Our main result is that all rank-1 logics enjoy
a shallow model property and thus are, under mild assumptions on the format of their axioma-
tisation, in PSPACE. This leads to a unified derivation of tight PSPACE-bounds for a number
of logics including K, KD, coalition logic, graded modal logic, majority logic, and probabilistic
modal logic. Our generic algorithm moreover finds tableau proofs that witness pleasant proof-
theoretic properties including a weak subformula property. This generality is made possible by a
coalgebraic semantics, which conveniently abstracts from the details of a given model class and
thus allows covering a broad range of logics in a uniform way.