Abstract: The ability of fine-tuning the performance of Bluetooth Low Energy (BLE) communication is essential to create low-power wireless applications with heavy user interaction, such as smart thermostats or door locks. One of the key challenges when designing such applications is finding the right trade-off between a system's responsiveness and energy-efficiency. Although there exists research works that improve the performance of BLE communication, all these approaches focus on connection-based BLE. Most BLE-based applications, however, spend the majority of their time in connection-less device discovery, waiting for approaching users. The energy-efficiency and timeliness in this state are defined by parameters that are often statically set at compile time. Although supported by the BLE specifications, how to dynamically adapt these parameters to user behavior is still an open question. In this paper, we tackle this challenge and design a strategy to improve the energy-efficiency and responsiveness of BLE device discovery. Towards this goal, we model the device discovery process and identify its key parameters. We further design an adaptive advertising strategy that allows smart objects to adapt their device discovery parameters to the user behavior. We implement this adaptive strategy and measure its performance in a real-world application, the Nuki Smart Door Lock. Our experiments show that a smart lock using our strategy consumes 48% less energy while reducing the device discovery time by up to 63% compared to the use of static parameters. Furthermore, we discuss how nearby BLE devices can be used to inform the lock about approaching user devices and hence to improve its responsiveness in low-power phases even further.