In this case, celeritate should be used with cum.
The general rule for the ablative of manner is that it should be used with cum if the ablative isn't modified by an adjective. Dale A. Grote explains this rule:
When the noun in this kind of construction is modified by an
adjective, Latin has the option of dropping the preposition cum. This
sentence could also be written: Id magna celeritate fecerunt. But
if the noun governed by cum is not qualified by an adjective, the
cum must be used. This is incorrect: Id celeritate fecerunt; but this is correct: Id cum celeritate fecit. And so is this: Id
magna cum celeritate fecit; this is fine, too: Id magni celeritate
fecit.
However, as is often the case, there are exceptions to the rule (but none that affect celeritate). According to Bradley's Arnold Latin Prose Composition, the use of cum is optional (even without an adjective) with the following:
casu "by chance" consilio "by design" consulto "deliberately"
forte "by chance" fraude "deceitfully" iure "rightly"
iniuria "unjustly" silentio "in silence" vi "by force"
There are also some common phrases with which cum is never used:
hoc consilio "with this intention"
hoc modo, hac ratione "in this way"
summo opere "ernestly, energetically"
aequo animo "calmly"
iussu tuo "at your command"
iniussu Caesaris "without Caesar's permission"
bona tua venia "with your kind permission"
nullo negotio "without trouble"
nescio quo pacto "in some way or other"