A set-associative cache memory having incremental access latencies among sets is disclosed. The cache memory has multiple congruence classes of cache lines. Each congruence class includes a number of sets organized in a set-associative manner. In accordance with a preferred embodiment of the present invention, the cache memory further includes a means for accessing each of the sets with an access time dependent on a relative location of each of the sets such that access latency varies incrementally among sets.