In various embodiments, a graph streaming application computes a first distance along a first potential playback path between a first playback position and a first media content block. The graph streaming application then computes a first score for the first media content block based on the first distance and a first probability associated with the first potential playback path. Similarly, the graph streaming application computes a second score for a second media content block based on a second playback position, a second potential playback path, and a second probability associated with the second potential playback path. The graph streaming application compares the first score and the second score to determine that the first media content block should be buffered by a client device. The graph streaming application then causes the first media content block to be stored in a playback buffer for subsequent playback on the client device.