AbstractA cache replacement policy is normally suited to a particular class of applications, or limited to a set of fixed criteria for evaluating the cache‐worthiness of an object. We present Universal Caching as a mechanism to capture the generality of the most adaptive algorithms, while depending on a very limited set of basic criteria for cache‐replacement decisions. Our testing was limited to Web workloads, where we tested the Universal Caching policy using real‐world traces from both the server‐side and client‐side proxies. Using a self‐tuning mechanism, combined with a generalization of the criteria employed in GD‐* Web caching, Universal Caching was able to consistently outperform any other fixed choice of algorithm we tested. Copyright © 2006 John Wiley & Sons, Ltd.