This disclosure describes techniques for reducing or eliminating estimator inconsistency in vision-aided inertial navigation systems (VINS). For example, an observability-constrained VINS (OC-VINS) is described which enforce the unobservable directions of the system to prevent spurious information gain and reduce inconsistency.