Circuits, methods, and apparatus that store a large number of texture states in an efficient manner. A level-one texture cache includes cache lines that are distributed throughout a texture pipeline, where each cache line stores a texture state. The cache lines can be updated by retrieving data from a second-level texture state cache, which in turn is updated from a frame buffer or graphics memory. The second-level texture state cache can prefetch texture states using a list of textures that are needed for a shader program or program portion.