A technique classifies packets in a manner that is both deterministic and efficient. A hierarchical arrangement of lookup tables is organized into levels to classify the packets. Entries contained in the lookup tables are incrementally built and added to the lookup tables as packets are classified. A packet is divided into a series of fields and a first-level lookup table is built for each of these fields. Successive-level-lookup tables are then allocated and initialized to contain "missing" entries. When a packet is classified, it is applied to the first-level lookup tables to produce a series of indices. These indices are then applied to the second-level lookup tables to select indices that are the applied to a next-level table and so on until an outcome index is selected from a final-level lookup table. If the entry selected in the second-level lookup table is empty the successive-level entries are built and the classification is retried.