As deep neural networks are increasingly being deployed in practice, their efficiency has become an important issue. While there are compression techniques for reducing the network’s size, energy consumption and computational requirement, they only demonstrate empirically that there is no loss of accuracy, but lack formal guarantees of the compressed network, e.g., in the presence of adversarial examples. Existing verification techniques such as ReluVal and DeepPoly provide formal guarantees but they are designed for analyzing a single network instead of the relationship between two networks. To fill the gap, we develop a new method for differential verification of two closely related networks. Our method consists of a fast but approximate forward interval analysis pass and a backward pass that iteratively refines the approximation. There are two main innovations. During the forward pass, we exploit structural and behavioral similarities of the two networks to more accurately compute the symbolic ranges of all neurons. In the backward pass, we leverage the gradient differences to more accurately compute the refinement. Our experiments show that, compared to state-of-theart verification tools, our method can achieve orders-of-magnitude speedup and prove many more properties than existing tools.