Caching cookies in a server includes observing cookies in document requests generated from a client and in responses from web hosts and storing them in a data structure based on certain conditions to maintain a path invariance condition. The cookies may be stored in a trie data structure. Upon certain conditions, cookies in the trie may be coalesced if they are equivalent and nodes of the trie may be collapsed. A server may retrieve cookies from the cache for use in a prefetch operation.