Video-on-Demand (VoD) is a compelling application, but costly due to the load it places on servers. Peer-to-peer (P2P) techniques hold the potential to reduce centralized costs by sharing data between peers. There are many difficult design issues associated with P2P for VoD. Viewing the problem as designing a large distributed cache, many of the issues can be expressed in terms of caching algorithms.In an earlier paper [6], we studied the performance of Grid-Cast, a P2P VoD system deployed on CERNET. From system traces, we found that departure misses are the major cause of server load. Motivated by this finding, this paper examines how to use replication to decrease departure misses and thereby further reduce server load.This paper proposes and evaluates a framework for lazy replication. Lazy replication postpones replication, trying to make efficient use of bandwidth. In our framework, two predictors are plugged in to create the working replication algorithm. Lazy replication with several predictors is compared with a naive eager replication algorithm. We find that lazy replication is more efficient than eager replication, even when using two simple predictors. With these two simple predictors, lazy replication can decrease server load by 15% from multivideo caching with only a minor increase in network traffic.