Embodiments of the invention provide methods and apparatus to defer the optimization an acceleration data structure (e.g., a kd-tree) in response to movements of objects within a three-dimensional scene. According to one embodiment of the invention, an image processing system may determine portions of an acceleration data structure affected by the movement of an object within a three-dimensional scene. The image processing system may store the affected portion of the ADS in an optimization queue. If the image processing system does not have sufficient processing bandwidth available to optimize the ADS, the image processing system may defer the ADS optimization until sufficient processing bandwidth becomes available. Once sufficient processing bandwidth becomes available, the image processing system may optimize the ADS according to the information stored in the optimization queue.