We build two-server private information retrieval (PIR) that achieves information-theoretic security and strong double-efficiency guarantees. On a database of \(n > 10^6\) bits, the servers store a preprocessed data structure of size \(1.5 \sqrt{\log _2 n} \cdot n\) bits and then answer each PIR query by probing \(12 \cdot n^{0.82}\) bits in this data structure. To our knowledge, this is the first information-theoretic PIR with any constant number of servers that has quasilinear server storage \(n^{1+o(1)}\) and polynomially sublinear server time \(n^{1-\varOmega (1)}\) . Our work builds on the PIR-with-preprocessing protocol of Beimel, Ishai, and Malkin (CRYPTO 2000). The insight driving our improvement is a compact data structure for evaluating a multivariate polynomial and its derivatives. Our data structure and PIR protocol leverage the fact that Hasse derivatives can be efficiently computed on-the-fly by taking finite differences between the polynomial’s evaluations. We further extend our techniques to improve the state-of-the-art in PIR with three or more servers, building on recent work by Ghoshal, Li, Ma, Dai, and Shi (TCC 2025). On an 11 GB database with 1-byte records, our two-server PIR encodes the database into a 1 TB data structure—which is 4,500,000 \(\times \) smaller than that of prior two-server PIR-with-preprocessing schemes, while maintaining the same communication and time per query. To answer a PIR query, the servers fetch and send back 4.4 MB from this data structure, requiring 2,560 \(\times \) fewer memory accesses than linear-time PIR. The main limitation of our protocol is its large communication complexity, which we show how to shrink to \(n^{0.31} \cdot \textsf{poly}(\lambda )\) using compact linearly homomorphic encryption.