State space caching is a state space exploration method that stores all states of just one execution sequence plus as many previously visited states as available memory allows. So far, this technique has been of little practical significance. With a conventional reachability analysis, it allows one to reduce memory usage by only two to three times, before an unacceptable exponential increase of the run-time overhead sets in. The explosion of the run-time requirements is caused by redundant multiple explorations of unstored parts of the state space. Indeed, almost all states in the state space of concurrent systems are typically reached several times during the search. There are two causes for this: firstly, several different partial ordcrings of statement executions can lead to the same state; secondly, all interleavings of a same partial ordering of statement executions lead to the same state.