A system and method is provided for mipmap texturing in which texture tiles are mapped into sets of a set-associative texture cache for use in displaying a graphic primitive. When a miss occurs, a new texture tile is called from main memory to replace a texture tile which is not shared between the segment being traversed and the next segment to be traversed and which is the “least recently used”. This is accomplished by maintaining a record for each cache line describing the texture tile it contains and replacing the texture tile which is the “least likely to be reused”.