The methods used to establish PSPACE-bounds for modal logics can roughly be grouped
into two classes: syntax driven methods establish that exhaustive proof search can be
performed in polynomial space whereas semantic approaches directly construct shallow
models. In this paper, we follow the latter approach and establish generic PSPACE-
bounds for a large and heterogeneous class of modal logics in a coalgebraic framework.
In particular, no complete axiomatisation of the logic under scrutiny is needed. This
does not only complement our earlier, syntactic, approach conceptually, but also covers
a wide variety of new examples which are di cult to harness by purely syntactic means.
Apart from re-proving known complexity bounds for a large variety of structurally di erent
logics, we apply our method to obtain previously unknown PSPACE-bounds for Elgesem's
logic of agency and for graded modal logic over re
exive frames.