If absolute velocity does not exist, how can we say a rocket accelerates in empty space?

Within the context of Newtonian mechanics, there's a simple answer: velocities are not absolute, but differences in velocities are. So you can state that acceleration occurs unambiguously.

In special relativity, this is a bit more complicated because of relativistic velocity addition, but all observers can unambiguously compute a "proper" acceleration for every object, which is the acceleration in that object's momentary rest frame.

In fact, the same logic still works in general relativity; acceleration is unambiguous even in a universe without matter. However, in certain philosophical stances inspired by general relativity, the question is trickier because one might take a hardline Machian position, where motion should only be defined in relation to other matter. But in this case you can still answer the question because there is motion relative to the exhaust.

A rocket's thrusters function by ejecting reaction mass (exhaust). You can measure the movement of the rocket by its distance from its reaction mass. The rocket moves relative to its reactant.

You can say the rocket didn't move, but not because it can't be measured. The center of mass of a rocket-reactant system* never goes anywhere—not even in our universe**—because the force of the rocket on its reactant is equal and opposite to the force of the reactant on the rocket. In this sense, the rocket-reactant system's center of mass is unaffected by the thrusters because the thrusters are internal to the system in question.

* Edited for clarity.

** Unless acted upon by an outside force.

how can we say a rocket accelerates in empty space ?

According to third Newton law, body in a rocket will experience pseudo-force with direction opposite to that of rocket acceleration. That is - rocket acceleration will induce body weight which can be observed / measured :

It's much like water "feels" centrifugal force. What you actually will not be able to distinguish is that if rocket flies with acceleration OR if it has already landed at some planet given that astronauts were sleeping in a journey and no windows to see planet surface and rocket's dashboard is broken showing false acceleration. It is a direct conclusion of Equivalence principle.