We propose ACE (Acquisitional Context Engine), a middleware that supports continuous context-aware applications while mitigating sensing costs for inferring contexts. ACE provides user’s current context to applications running on it. In addition, it dynamically learns relationships among various context attributes (e.g., whenever the user is Driving, he is not AtHome). ACE exploits these automatically learned relationships for two powerful optimizations. The rest is inference caching that allows ACE to opportunistically infer one context attribute (AtHome) from another already-known attribute (Driving), without acquiring any sensor data. The second optimization is speculative sensing that enables ACE to occasionally infer the value of an expensive attribute (e.g., AtHome) by sensing cheaper attributes (e.g., Driving). Our experiments with two real context traces of 105 people and a Windows Phone prototype show that ACE can reduce sensing costs of three context-aware applications by about 4:2, compared to a raw sensor data cache shared across applications, with a very small memory and processing overhead.