  We study the statistics of increments in record values in a time series
$\{x_0=0,x_1, x_2, \ldots, x_n\}$ generated by the positions of a random walk
(discrete time, continuous space) of duration $n$ steps. For arbitrary jump
length distribution, including L\'evy flights, we show that the distribution of
the record increment becomes stationary, i.e., independent of $n$ for large
$n$, and compute it explicitly for a wide class of jump distributions. In
addition, we compute exactly the probability $Q(n)$ that the record increments
decrease monotonically up to step $n$. Remarkably, $Q(n)$ is universal (i..e.,
independent of the jump distribution) for each $n$, decaying as $Q(n) \sim
{\cal A}/\sqrt{n}$ for large $n$, with a universal amplitude ${\cal A} =
e/\sqrt{\pi} = 1.53362\ldots$.
