A method comprises receiving input reference attributes from a data reference interface and selecting a replacement data location of a cache to store data. The replacement data location is selected based on the input reference attributes and reference states associated with cached-data stored in data locations of the cache and an order of state locations of a replacement stack storing the reference states. The reference states are based on reference attributes associated with the cached-data and can include a probability count. The order of state locations is based on the reference states and the reference attributes. In response to receiving some input reference attributes, reference states stored in the state locations can be modified and a second order of the state locations can be determined. A reference state can be stored in the replacement stack based on the second order. A cache can comprise a data reference interface, reference attributes, reference states, cached-data locations, a replacement stack, and a cache manager. The cache manager can perform the method.