По идее мне нужен какой-то кеш, из которого я буду удалять старые текстуры и загружать новые, но они ведь могут быть разные по размеру, т.е. удаление текстуры 32x32 не позволит мне залить в память текстуру 256x128
Удалять много небольших или немного больших можно. Процентов 80 от видеопамяти используй, если у тебя, так сказать, тайтл, то есть, тяжёлое приложение типа игры, при работе с которым пользователь вряд ли будет переключаться на что-то другое. У тебя какой API? Ты можешь запрашивать объём доступной и используемой памяти через DXGI или через расширения OpenGL. В D3D12 и в Вулкане ты можешь прямо точно узнать, сколько ресурс будет занимать места (потому что там есть ручное выделение памяти), только без учёта фрагментации, конечно, если у тебя dedicated allocations