We present an \(O^*(|\mathbb {F}|^{\min \left\lbrace R,\ \sum _{d\ge 2} n_d\right\rbrace + (R-n_0)(\sum _{d\ne 0} n_d)})\)-time algorithm for determining whether the rank of a concise tensor \(T\in \mathbb {F}^{n_0\times \dots \times n_{D-1}}\) is ≤ R, assuming n0 ≥ … ≥ nD − 1 and R ≥ n0. For 3-dimensional tensors, we have a second algorithm running in \(O^*(|\mathbb {F}|^{n_0+n_2 + (R-n_0+1-r_*)(n_1+n_2)+r_*^2})\) time, where \(r_*:= \left \lfloor \frac{R}{n_0} \right \rfloor +1\). Both algorithms use polynomial space and improve on our previous work, which achieved running time \(O^*(|\mathbb {F}|^{n_0+(R-n_0)(\sum _d n_d)})\).