A method is implemented by a network device to dynamically optimize lookup speed in a packet processing table maintained at the network device while the network device is in operation. The method includes determining one or more runtime metrics of the packet processing table, selecting a lookup algorithm for the packet processing table from a set of lookup algorithms supported by the network device based on the one or more runtime metrics of the packet processing table, and configuring the network device to match incoming packets against rules in the packet processing table using the selected lookup algorithm for the packet processing table.