Bitrate adaptation is critical in ensuring good users’ quality-of-experience (QoE) in Internet video delivery system. Several efforts have argued that accurate throughput prediction can dramatically improve (1) initial bitrate selection for low startup delay and high initial resolution; (2) midstream bitrate adaptation for high QoE. However, prior ef- forts did not systematically quantify real-world throughput predictability or develop good prediction algorithms. To bridge this gap, this paper makes three key technical contributions: First, we analyze the throughput characteristics in a dataset with 20M+ sessions. We find: (a) Sessions sharing similar key features (e.g., ISP, region) present similar initial values and dynamical patterns; (b) There is a natural “stateful” dynamical behavior within a given session. Second, building on these insights, we develop CS2P, a better throughput prediction system. CS2P leverages data-driven approach to learn (a) clusters of similar sessions, (b) an initial throughput predictor, and (c) a Hidden-Markov-Model based midstream predictor modeling the stateful evolution of throughput. Third, we develop a prototype system and show by trace-driven simulation and real-world experiments that CS2P outperforms state-of-art by 40% and 50% median pre- diction error respectively for initial and midstream through- put and improves QoE by 14% over buffer-based adaptation algorithm.