Track the amount of time the player has spent on a given dungeon level. As it increases, random monster spawns gradually get less frequent (unless you have the demigod flag set, which overrules this) and more difficult, starting at one or two thousand turns spent on the level.