Can hypergraphs capture multi-hop reasoning better than graphs?

Most retrieval memory designs store retrieved chunks as flat lists or, at best, as graphs of binary relations. HGMem proposes hypergraph memory for multi-step RAG, where each hyperedge can connect arbitrarily many facts at once. This matters because multi-hop reasoning frequently needs to bind three or more entities into a single propositional relation — "A caused B in context C under condition D" — and binary edges have to factor such relations into pairwise approximations that lose the joint constraint.

The implication is structural rather than incremental. A hypergraph memory accumulates retrieved evidence not as a growing pile but as a growing combinatorial space where new facts can attach to existing groupings without first decomposing them. This is what "build structured knowledge over time" means in practice: each new retrieval step extends the hypergraph rather than appending to a list, so the model can see which previously retrieved facts were already cohering around a common relation before deciding what to retrieve next. This is the multi-step analogue of Can knowledge graphs enable multi-hop reasoning in one retrieval step? — both move away from flat retrieval but HippoRAG operates within a single retrieval pass while HGMem accumulates across many.

The trade-off is representational complexity. Hypergraphs are harder to construct, harder to traverse, and harder to embed than ordinary graphs. The bet HGMem makes is that for genuinely multi-step reasoning the constraint expressiveness pays back the complexity, because the alternative — re-retrieving from a flat memory at each step — loses the coherence the agent has already established.