8. The apparatus of claim 6 , wherein the WFST decoder further executes instructions to: look up in the single lookup arc cache the arc identifier and accumulated weight for an input label and a source state, wherein the single lookup arc cache does not include an entry corresponding to the input label and the source state; and in response to the look up, generate a cache miss in the single lookup arc cache, to cause a cache controller to search the second WFST for an arc with the input label in the source state, and to cause the cache controller to recursively search all states in the second WFST that are reachable via epsilon arcs, in order to populate the single lookup arc cache with the missed entry.
6. The apparatus of claim 5 , wherein each entry in the single lookup arc cache includes a source state identifier, an input label identifier, an arc identifier, and an accumulated weight value, wherein the accumulated weight value corresponds to the weight of the arcs along the path from the state identified by the source state identifier to the arc identified by the arc identifier.