The use of approximation is fundamental in computational science. Almost all computational methods adopt approximations in some form in order to obtain a favourable cost/accuracy trade-off and there are usually many approximations that could be used. As a result, when a researcher wishes to measure a property of a system with a computational technique they are faced with an array of options. Current computational workflow frameworks focus on helping researchers automate a sequence of steps on a particular platform. The aim is often to obtain a computational measurement of a property. However these frameworks are unaware there may be a large number of ways to do so, and cannot support researchers in making these choices during development or at execution-time. We argue that computational workflow frameworks should be designed to be approximation-aware - that is, support the fact a given workflow description represents a task that could be per- formed in different ways. This is key to unlocking the potential of computational workflows to accelerate discovery tasks, particularly those involving searches of large entity spaces. It will enable effi- ciently obtaining measurements of entity properties, given a set of constraints, by directly leveraging the space of choices available. In this paper we describe the basic functions an approximation-aware workflow framework should provide, how those functions can be realized in practice, and illustrate some of the powerful capabilities it would enable, including approximate memoization, surrogate model support, and automated workflow composition.