  In this paper, we investigate extensions between graded Verma modules in the
BGG category $\mathcal{O}$. In particular, we determine exactly which
information about extensions between graded Verma modules is given by the
coefficients of the $R$-polynomials. We also give some upper bounds for the
dimensions of graded extensions between Verma modules in terms of
Kazhdan-Lusztig combinatorics. We completely determine all extensions between
Verma module in the regular block of category $\mathcal{O}$ for
$\mathfrak{sl}_4$ and construct various ``unexpected'' higher extensions
between Verma modules.
