Circuits and methods are disclosed for decomposition of a content addressable memory into a plurality of CAMs having a lower cost. In an example implementation, a set of CAM rules are grouped into a plurality of subsets. For each of the subsets, CAM rules in the subset are reformatted for storage in a respective CAM configured to store fewer ternary bits or configured for prefix match. Each reformatted subset of CAM rules are stored in the respective CAM. A search key formatting circuit is configured to reformat an input search key for each of the respective CAMs is used to store the reformatted subsets to produce a respective reformatted search key and input the respective reformatted search key to the respective CAM.