An apparatus and method of using a cache to improve a learn rate for a content-addressable memory (“CAM”) are disclosed. A network device such as a router or a switch, in one embodiment, includes a key generator, a searching circuit, and a key cache, wherein the key generator is capable of generating a first lookup key in response to a first packet. The searching circuit is configured to search the content of the CAM to match the first lookup key. If the first lookup key is not found in the CAM, the key cache stores the first lookup key in response to a first miss.