We show that the basic system of modal logic K has a form of monotone interpolation, and hence we give an exponential lower bound on the lengths of proofs in K. The result immediately extends to K4, Godel-Lobs logic, S and S4. However, it is not immediately applicable to S5. Indeed, we show that S5 has an unbounded speed-up over K.