find … -exec rm {} \; executes the rm command for each file. Even though starting a new process is pretty fast, it's still a lot slower than the mere act of deleting a file.
find … -exec rm {} + would call rm in batches, which is a lot faster: you pay the cost of running rm once per batch, and each batch performs many deletion.
Even faster is to not invoke rm at all. The find command on Linux has an action -delete to delete a matching file.
find ./cache -type f -mtime +0.5 -delete
However, if you're producing files at such a rate that find … -exec rm {} \; can't keep up, there's probably something wrong with your setup. If cache contains millions of files, you should split it into subdirectories for faster access.