Techniques include receiving a search query from a user device, receiving an indication of a current application (app) state of a native app executing on the device from the device, and identifying app state records based on the query and the indication. Each app state record includes an app access mechanism (AAM) and app state information (ASI). The AAM references the native app executing on the user device and indicates operations for the app to perform. The ASI describes an app state of the app after performing the operations. Identifying each app state record based on the indication includes determining that the current app state is a parent app state of the app state described by the ASI included in the identified record. The techniques further include selecting the AAMs from the identified app state records and transmitting the selected AAMs to the user device.