The embodiments disclosed herein relate to predictive rate limiting. A workload for completing a request is predicted based on, for example, characteristics of a ruleset to be applied and characteristics of a target set upon which the ruleset is to be applied. The workload is mapped to a set of tokens or credits. If a requestor has sufficient tokens to cover the workload for the request, the request is processed. The request may be processed in accordance with a set of processing queues. Each processing queue is associated with a maximum per-tenant workload. A request may be added to a processing queue as long as adding the request does not result in exceeding the maximum per-tenant workload. Requests within a processing queue may be processed in a First In First Out (FIFO) order.