Large-mammal surveys often rely on indirect signs such as dung or nests. Sign density is usually translated into animal density using sign production and decay rates. In principle, such auxiliary variable estimates should be made in a spatially unbiased manner. However, traditional decay rate estimation methods entail following many signs from production to disappearance, which, in large study areas, requires extensive travel effort. Consequently, decay rate estimates have tended to be made instead at some convenient but unrepresentative location. In this study we evaluated how much bias might be induced by extrapolating decay rates from unrepresentative locations, how much effort would be required to implement current methods in a spatially unbiased manner, and what alternate approaches might be used to improve precision. To evaluate the extent of bias induced by unrepresentative sampling, we collected data on gorilla dung at several central African sites. Variation in gorilla dung decay rate was enormous, varying by up to an order of magnitude within and between survey zones. We then estimated what the effort-precision relationship would be for a previously suggested "retrospective" decay rate (RDR) method, if it were implemented in a spatially unbiased manner. We also evaluated precision for a marked sign count (MSC) approach that does not use a decay rate. Because they require repeat visits to remote locations, both RDR and MSC require enormous effort levels in order to gain precise density estimates. Finally, we examined an objective criterion for decay (i.e., dung height). This showed great potential for improving RDR efficiency because choosing a high threshold height for decay reduces decay time and, consequently, the number of visits that need to be made to remote areas. The ability to adjust decay time using an objective decay criterion also opens up the potential for a "prospective" decay rate (PDR) approach. Further research is necessary to evaluate whether the temporal bias inherent in such an approach is small enough to ignore, given the 10-20-fold increases in precision promised by a PDR approach.