A network lookup engine in a network switch is configured to generate multiple lookup queries for each incoming packet in parallel to a remote search engine. The number and type of the lookup queries depend on the protocols supported by the network switch. The responses from the search engine arriving at the lookup engine are not in the same order as the order of the packets. The network lookup engine is configured to collect the responses for the parallel lookup queries in two modes: 1) in-order mode in which the first packet having its lookup queries sent to the search engine has its responses collected first regardless of the order of the responses received from the search engine; 2) out-of-order mode in which the first packet having complete responses to its lookup queries from the search engine has its responses collected first regardless of the order of incoming packets.