In various embodiments, a hindsight application computes a total download size for a sequence of encoded chunks associated with a media title for evaluation of at least one aspect of a video streaming service. The hindsight application computes a feasible download end time associated with a source chunk of the media title based on a network throughput trace and a subsequent feasible download end time associated with a subsequent source chunk of the media title. The hindsight application then selects an encoded chunk associated with the source chunk based on the network throughput trace, the feasible download end time, and a preceding download end time associated with a preceding source chunk of the media title. Subsequently, the hindsight application computes the total download size based on the number of encoded bits included in the first encoded chunk. The total download size correlates to an upper bound on visual quality.