Decision problem such that any algorithm admits an exponentially faster algorithm
It seems to be a simple case of Blum's Speedup Theorem:


  Given a Blum complexity measure $(\varphi, \Phi)$ and a total computable function $f$ with two parameters, then there exists a total computable predicate $g$ (a Boolean valued computable function) so that for every program $i$ for $g$, there exists a program $j$ for $g$ so that for almost all $x$
  $$f(x,\Phi_j(x)) \leq \Phi_i(x)$$


Just let the the complexity measure be the time complexity measure (i.e. $\Phi_e(x)$ is the time complexity of the Turing machine with code $e$) and let $f(x,y) = 2^y$.