Systems, methods, and computer storage media for handling failures in generating structured queries from natural language queries. One of the methods includes obtaining, through a natural language front end, a natural language query from a user; converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base, comprising: parsing the natural language query, analyzing the parsed query to determine dependencies, performing lexical resolution, forming a concept tree based on the dependencies and lexical resolution; analyzing the concept tree to generate a hypergraph, generate virtual query based on the hypergraph, and processing the virtual query to generate one or more structured operations; performing the one or more structured operations on the structured APIs of the knowledge base; and returning search results matching the natural language query to the user.