- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The authors consider the problem of answering directed reachability queries given node removals, from a compressed representation: e.g., given a graph , how much of it do we need to store so that given and , we can answer reachability queries in ? They also consider variants of this problem in graphs with edge-failure probabilities, causal graphs, and "AND networks." They also provide error probability results under a random graph model. The authors provide an analogy between these graph reachability queries and the memories stored by an agent that must reason over external information that may become unavailable at a later time. In experiments, the authors test whether LLMs can select good edge sets to answer robust reachability queries and find they perform no better than random edge sets, and significantly worse than a greedy baseline.
Critical strengths
There are some interesting theoretical questions studied about how much of a graph needs to be stored to answer robust reachability queries under node removal. A clear presentation of these results on random graphs and causal graphs could make for an interesting algorithms paper.
Critical weaknesses
- The paper is difficult to read as the writing quality and clarity are low. The motivation and takeaways for the results are also not clear. This is severe enough that it is hard to evaluate the paper and needs to be improved dramatically before publication.
- The connection between DAG reachability results and agent memory is very tenuous. Calling these graphs "memories" or "workflows" is a confusing layer of interpretation over the core graph results. It would be much clearer if presented as an algorithms paper at a different venue, without the agent memory dressing. This particular setting of memory in agents (workflows with external information sources that may become unavailable) seems rather niche, and it's not clear how much of the theory is useful for thinking about agent memory systems in practice.
Questions for authors
- Is there a figure that compares the LLMs, the LLMs with advice, and the baselines? Table 2 seems to be missing greedy.
- Is Greedy "the best memory we can compute" (line 320)? Is there no better algorithm? Is it really an upper bound on ? Couldn't some clever combination of edges answer more training request with lower budget?
Comments
- The k-core of a graph is a different existing concept, so renaming would be helpful for disambiguation
- We don't learn much from the experiments: it's not surprising that LLMs do a bad job of choosing a good edge set.
- The paragraph break formatting is very strange. on page 1, there seem to be a number of paragraph breaks but no spacing between them. Later in the paper, some (but not all) paragraphs have space between them. Is there some \vspace compression being used?
- some examples of clarity issues:
- "one route may suffice, every prerequisite may be required, or contributions may add up" is extremely vague; what is a "route"? what does it mean for "contributions" to "add up"?
- Example 4 is very confusing for a non-genetics audience. What is a latent gene program and what does it mean to weaken a program?
- in general, these examples don't do a good job of introducing the key idea (OR, AND, ...), which is buried under extraneous details like "the public index, a company mirror, or a vendored copy" necessary. A clearer approach would be to explicitly define each workflow type, and then provide minimal examples that show how those occur in practice (without distracting extra details)
- what does "OR memory is transitive reduction" mean?
- "AND workflows need only the transitive reduction" is also unclear.
- Theorem 3.1 uses undefined notation and undefined jargon "compatible graph"
- "To leading order in the weight scale" does not parse
- Prop 3.5 is just the corollary of theorem 3.1 stated below ("Hence is the exact...")
- In Figure 4B, where is the dashed line? It's not visible.
2 comments
Thanks for the clarifications! I think these changes will improve the paper in a future revision.
For the current submission, the clarity and writing issues were too significant to be addressed in post-review revisions (the examples that I shared were a small selection). A fresh re-review would be needed to make sure the paper is in a better state, so I'm keeping my original score
We thank the reviewer for the comments on presentation and scope.
Q1: “The paper is difficult to read … The motivation and takeaways for the results are also not clear.”
We thank the reviewer for pointing out the flaws in writing, and will revise it to make things clearer.
Q2: “The connection between DAG reachability results and agent memory is very tenuous.”
The connection is one specific memory function: keeping the dependencies that let an agent recover information when some resources become unavailable. The stored edges are the memory, and the reader answers from them after failures. Conceptually, these can be thought of as world knowledge and the agent wants to keep the necessary logical links, Learning the dependencies and writing free-form summaries, for instance, are outside our scope, and we will clarify the framing accordingly.
Q3: “We don’t learn much from the experiments: it’s not surprising that LLMs do a bad job of choosing a good edge set.”
It is worth pointing out that choosing a good edge set on small graphs is not apriori a task too difficult for modern LLMs, which reportedly have achieved superior reasoning capabilities. Moreover, experiments show why the models fail, proving further insights. On citation graphs, 80%–97% of model errors come from query endpoints whose stored neighbors all fail; one GLM memory spends 117 of its 128 edges on links from three papers. A prompt telling GLM to spread its budget raised the share of covered vertices from 0.35 to $0.80, yet its loss only fell to that of random edges, which reveals a second requirement: links between nearby vertices. In a new experiment, GLM 5.3 still lost 0.8761 when shown the vertex order and given feedback, against 0.813 for random edges.
Q4: “Is there a figure that compares the LLMs, the LLMs with advice, and the baselines? Table 2 seems to be missing greedy.”
We will add Greedy and Balanced to the guidance table, so that all conditions appear together.
Q5: “Is Greedy ‘the best memory we can compute’ … Is there no better algorithm?” “Is it really an upper bound on Dμ?”
Greedy is our strongest tested algorithm rather than an established optimum, and we will drop that phrase to avoid confusion. Greedy's loss still bounds the optimum from above because Greedy's memory is one of the allowed memories: Dμ∗(B,G)≤Dμ(Hgreedy;G) by definition. The reported test loss estimates Greedy's loss over the full request distribution.
Q6: “The k-core of a graph is a different existing concept, so renaming would be helpful for disambiguation.”
We agree with this point and will use alternative names such as “fault-tolerant reachability core”.
Q7: “‘One route may suffice, every prerequisite may be required, or contributions may add up’ is extremely vague.” “Example 4 is very confusing for a non-genetics audience.”
In an OR workflow, one surviving directed path suffices. In an AND workflow, a target needs all of its ancestors. In a linear model, each path contributes the product of its coefficients, and the total effect is their sum. We will revise Example 4 to make it more direct: observed variables mix latent variables, and the data cannot separate direct from indirect effects.
Q8: “What does ‘OR memory is transitive reduction’ mean?” “‘AND workflows need only the transitive reduction’ is also unclear.”
Without failures, an OR answer is whether a directed path exists, and the transitive reduction is the smallest subgraph that preserves all such answers. An AND target can be produced exactly when none of its ancestors fails, and the transitive reduction is the smallest subgraph that preserves every vertex's ancestors, so it suffices for any number of failures. We will revise both statements.
Q9: “Theorem 3.1 uses undefined notation ≡k and undefined jargon ‘compatible graph’.” “‘To leading order in the weight scale’ does not parse.”
G≡kJ means that the two graphs give the same answer to every request with at most k failures. We will restate this in the theorem and replace “compatible graph” with “graph with the same answers.” “To leading order in the weight scale” means that all coefficients are multiplied by a small s, and the result describes the s2 term of the loss as s→0.
Q10: “Prop 3.5 is just the corollary of theorem 3.1 stated below.”
We agree and will label it as a corollary.
Q11: “The paragraph break formatting is very strange … Is there some \ vspace compression being used?”
Yes. The main text reduces paragraph spacing due to page limit. We will make it more consistent.
Q12: “In Figure 4B, where is the dashed line? It’s not visible.”
In the middle panel (k=20), the gray dash-dot Balanced curve almost coincides with the black Greedy curve, which hides it. We will add distinct markers and labels.