Can't you solve it using hash trees (or Merkle trees) ?

You tag each computation nodes with a hash of its dependencies and some constant salt, that gives you an ID which identifies the results that the computation node would produce; before running it.

You can then use those IDs to index the computations results in a cache; whenever you query a computation results, as long as you update the IDs of each leaf of the computation graph, you will only re-compute the nodes that need to be updated