If the hemisphere is tesselated into sufficiently many cells, a small amount of error in the calculation of a few cells does not significantly affect the resulting average. We can optimize the calculation of the hemisphere's average by caching intersection points of previously traced paths along with the paths' color. For each first-generation ray, I find the orientation of the hemisphere of the closest intersecting surface and project all the points in the cache onto the hemisphere, storing the cache entry's color in the appropriate cell. If several cache points fall into the same cell, the points that are closest to the surface point are kept and the rest are not used for this hemisphere. If any cell on the hemisphere has no cache points projected onto it, a new ray is shot through it and its result is added to the cache.
One problem with this approach is that much potentially useful information is lost when several cache points project onto the same cell. This can be solved by tesselating the hemisphere more finely, but many more cells will have no cache points at all, greatly increasing the computation for the hemisphere. A good compromise is to have the hemisphere be tesselated into super-cells, with each super-cell composed of, say, 2x2 cells. A new ray is only shot through a super-cell if the entire super-cell is empty. This approach allows the hemisphere to be tesselated more finely without incuring the cost of more traced rays. The cells in each super-cell are averaged together before averaging all the super-cells so as to not bias super-cells with more samples.