Computing the velocity field is an expensive process for mantle convection codes. This has implications for particle methods used to model the advection of quantities such as temperature or composition. A common choice for the numerical treatment of particle trajectories is classical fourth-order Runge–Kutta (ERK4) integration, which involves a velocity computation at each of its four stages. To reduce the cost per time step, it is possible to evaluate the velocity for a subset of the four time integration stages. We explore two such alternative schemes, in which velocities are only computed for: a) stage 1 on odd-numbered time steps and stages 2–4 for even-numbered time steps, and b) stage 1 for all time steps. A theoretical analysis of stability and accuracy is presented for all schemes. It was found that the alternative schemes are first-order accurate with stability regions different from that of ERK4. The efficiency and accuracy of the alternate schemes were compared against ERK4 in four test problems covering isothermal, thermal, and thermochemical flows. Exact solutions were used as reference solutions when available. In agreement with theory, the alternate schemes were observed to be first-order accurate for all test problems. Accordingly, they may be used to efficiently compute solutions to within modest error tolerances. For small error tolerances, however, ERK4 was the most efficient.