acceptodds
Under review as a conference paper at ICLR 2027

Graph-Parameterized Capacity for Latent Multi-Hop Recall: Usage, Compression, and Composition

Abstract

When can knowledge stored in model parameters replace bounded knowledge-graph traversal? We price latent multi-hop storage by graph structure rather than raw fact count. We define coverage-conditioned support usage , macro-decomposition credit , and realizable width , and give a geometric construction with dimension quadratic in and logarithmic in code count and inverse slack. For witness-executing position-factorized memories, we prove a restricted entry-count lower bound matching the charge on branch-functional, pair-balanced closures under stated selector and representation assumptions. For modular memories, we prove an expected confabulation-plus-abstention floor on unique-witness crossings for weight-local, frame-nonaligning composition with a latent crossing interface, under receiving-cap overlap and path-separation assumptions. Empirically, 14 theory-matched families share a coarse rung index on an -scaled ladder, while realized prefactors remain family-dependent; the distractor control does not identify the factor. Support diversity best predicts thresholds. Macro credit reduces explicit parameters under slot-elastic allocation, while trained macro gains mainly reflect shorter live retrieval depth. A receiving-gate audit isolates frame mismatch. Pretrained LoRA thresholds remain bottom-censored, while CoT reaches the measured floor at on 9/9 chain and 8/9 segmented cell-seeds.

Primary area:
learning theory
Keywords:
multi-hop reasoning, associative memory, model capacity, knowledge graphs, latent reasoning, parametric memory, memory compression, modular composition, representation alignment

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dsFcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates how graph structure affects the memory resources required for latent multi-hop recall and the composability of modular memories. It introduces measures of support usage, macro-decomposition credit, and realizable width, and derives a constructive capacity upper bound, a restricted entry-count lower bound, and a conditional composition failure bound. Controlled experiments on gated-memory architectures examine support-dependent capacity scaling, show that compression savings depend on allocation, and suggest that trained macro gains primarily reflect shorter retrieval depth rather than cross-query reuse. Additional oracle controls isolate the effect of cross-module representation alignment. The empirical findings primarily concern these controlled substrates; pretrained-model experiments remain capacity-threshold censored.

Critical strengths
  1. A concrete structural account of memory cost. The paper distinguishes support usage, macro decomposition, and realizable width, providing an explicit construction that captures differences obscured by raw fact counts. Its separation of memory parameters from dictionary and parsing resources makes the resulting guarantees more interpretable. This offers a useful foundation for studying how graph structure affects the cost of storing and executing multi-hop knowledge.
  2. Informative controls separating compression from implementation and learning effects. The allocation and private-macro controls show that fewer discrete associations do not necessarily translate into fewer implemented parameters or explain trained gains. The receiving-complete frame controls also separate representation mismatch from missing support. These comparisons provide useful mechanism-level information beyond reporting whether a particular memory system succeeds.
Critical weaknesses
  1. The scientific increment beyond the assumptions is insufficiently established. Theorem 2 requires witness execution and limits each entry to one labeled macro-fact per slot, imposing much of the underlying counting structure. Theorem 3 relies on receiving-cap overlap and path separation, which perform substantial explanatory work in connecting interface incompatibility to failure. These restrictions do not invalidate the results, but the paper needs to establish more clearly what non-obvious understanding remains beyond them and how it advances the closest capacity and associative-memory results. Section 2 provides insufficient comparative analysis, while the dense exposition lacks a worked graph-to-memory example connecting the definitions, guarantees, and experiments. Consequently, the paper’s central conceptual contribution remains difficult to assess.
  2. The quantitative and mechanistic interpretations require stronger evidential support. Appendix D states that the threshold-bracket audit fixes rung-level pass/fail verdicts without re-estimating uncertainty from the underlying learning-rate runs. The sensitivity of the reported scaling slopes and support-predictor comparisons to these decisions therefore remains unclear. Likewise, the private/shared-macro controls establish no detectable reuse advantage at the tested resolution, but do not by themselves uniquely identify reduced retrieval depth as the explanation for trained gains. The paper acknowledges several measurement limitations; however, their consequences for these quantitative and mechanistic interpretations need to be carried through more explicitly. These are fixable concerns about inference, rather than allegations that the reported measurements are incorrect.
Questions for authors
  1. Conceptual contribution: After accounting for the witness-execution, entry-representation, and composition assumptions, what are the principal non-obvious conclusions relative to the closest capacity and associative-memory results? Please identify which explanatory steps are established by the analysis rather than supplied by the assumptions.
  2. Threshold robustness: Using the existing runs, how stable are the reported scaling slopes and support-predictor rankings to threshold-bracket resolution and learning-rate/seed-level pass/fail variation? This would help assess the uncertainty omitted by treating the archived rung-level verdicts as fixed.
  3. Mechanism attribution: Which aspects of the existing macro controls distinguish reduced live retrieval depth from other changes introduced by macro encoding? In particular, what supports the retrieval-depth attribution beyond the absence of a detectable private/shared threshold difference?
1 comment

We thank the reviewer for identifying the need to distinguish assumptions from deductions, quantify threshold uncertainty, and avoid overattributing the trained macro effect. The revised manuscript now separates these claims explicitly.

Critical weakness 1 / Question 1 — theoretical increment

“The scientific increment beyond the assumptions is insufficiently established. Theorem 2 requires witness execution and limits each entry to one labeled macro-fact per slot... Theorem 3 relies on receiving-cap overlap and path separation...”

Response. We agree these are substantive assumptions, not empirical findings. Theorem 2 assumes witness-executing, slot-factorized resolution, but derives the number of distinct entries that must survive on a sufficiently large correctly answered query set. Pair-balancedness bounds the support deleted by omitted query mass; selector optimality is required only to identify the reference-selector H−SH-S; explicit entries are required to convert entry counts into scalar parameters. A direct answer shortcut or superposed representation may lie outside this lower bound.

Theorem 3 assumes receiving-cap overlap, a frame-nonaligning latent interface, and path-separating execution. Its derived step converts a local crossing incompatibility into a workload-level confabulation-plus-abstention floor:

E[errconf+abst]≥(1−pch(d)−δalign) crosskuniq.\mathbb E[\mathrm{err}_{\mathrm{conf}}+\mathrm{abst}] \ge (1-p_{\mathrm{ch}}(d)-\delta_{\mathrm{align}})\,\mathrm{cross}^{\mathrm{uniq}}_k.

It is a conditional mechanism theorem, not a universal impossibility result. We have clarified both theorem scopes and the increments relative to Ravfogel et al. (2026): retained fact–slot support, admissible witness compression, and realizable-width-aware construction. The revised worked example makes the full resource accounting explicit.

Critical weakness 2 / Question 2 — threshold robustness

“Using the existing runs, how stable are the reported scaling slopes and support-predictor rankings to threshold-bracket resolution...?”

Response. The archived thresholds are intervals L<P∗≤UL<P^*\le U, with median bracket width about 2.1×2.1\times. E-T reanalyzes the 11 non-control families using 20,000 independent per-family draws uniform in log⁡P∗\log P^* within these brackets. The slope median is 0.9460.946, the central 95% bracket-sensitivity interval is [0.795,1.098][0.795,1.098], and the sampled range is [0.688,1.196][0.688,1.196]. This is not a seed-level confidence interval or 20,000 independent training replications. It supports a roughly linear trend within the tested gated substrate under that sensitivity model, not a uniquely identified law.

The predictor ranking is unstable: H0H_0 wins just 18.3% of realizations. Raw ∣E∣|E| and H2H_2 never win among the tested predictors under this procedure. We therefore removed the unique-best-predictor claim. The later restricted-adapter Transformer experiment (E-S) also fails to reproduce an HH ordering across structural families, with additional optimization sensitivity; this is reported rather than presented as confirmation.

Question 3 — macro mechanism attribution

“Which aspects of the existing macro controls distinguish reduced live retrieval depth from other changes introduced by macro encoding?”

Response. Shared and query-private macro arms keep segmentation and active execution depth matched while removing cross-query identity reuse in the private arm. Thresholds agree exactly in 27/30 family–seed–budget cells and within one rung in 29/30. In reuse_hi3, the private arm can store more associations than the free arm yet require fewer table parameters. Thus cross-query reuse is not necessary for the observed trained gain at the tested resolution. Because macro encoding and optimization also change, we now say the result is consistent with fewer live lookups, not that it uniquely proves retrieval-depth causation.

We hope the narrower claims and explicit sensitivity and negative findings address your concerns. We respectfully ask you to reconsider your score in light of these revisions.

Reviewer_1wvhOpenReview ↗
Rating
2(−1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper shows how knowledge graph structure affects the memory needed for multi-hop reasoning. The authors show that memory usage depends not just on the number of facts, but also on how they are used and compressed. They also explain why separately trained memories may fail when combined.

Critical strengths
  1. The paper offers an interesting way to study memory capacity by considering graph structure, support usage, and compression, rather than just counting facts. I think this is a useful extension of existing work on multi-hop memory capacity.

  2. I found the composition theorem particularly interesting. It helps explain why independently trained memories may fail when combined, and the receiving-gate experiments provide useful evidence for the representation alignment issue.

Critical weaknesses
  1. The novelty of the H−S bound is not entirely clear compared with Ravfogel et al. (2026). The graph-dependent formulation is interesting, but I would like to see a clearer explanation of what new theoretical insights it provides.

  2. The lower bound relies on fairly strong assumptions about the memory architecture, so it is unclear how well it applies to general Transformers. The experiments on pretrained models are also limited, as the LoRA results do not show clear capacity thresholds.

Questions for authors
  1. How is the proposed H−S bound different from Ravfogel et al. (2026)? Besides adding graph structure, what new insights does it provide?

  2. Is the H−S lower bound a general limitation of latent multi-hop reasoning, or does it mainly come from the position-factorized memory assumptions?

3 comments

After reading other reviewer’s comments, I agree with Reviewer dsFc’s concern about the strong assumption and novelty. My concern is about the H−S lower bound relying on specific memory architecture and unsure it can be applied to general transformer. The experiment on pretrained model is also limited. Thus, I decide to change my ratings to 2.

We thank the reviewer for revisiting the submission and for the explicit November 17 assessment. We agree that novelty beyond architectural assumptions and applicability to pretrained Transformers are central concerns.

Official comment — November 17, 2026

“After reading other reviewer’s comments, I agree with Reviewer dsFc’s concern about the strong assumption and novelty. My concern is about the H−SH-S lower bound relying on specific memory architecture and unsure it can be applied to general transformer. The experiment on pretrained model is also limited. Thus, I decide to change my ratings to 2.”

Response. We agree that Theorem 2 does not prove a general Transformer lower bound. It applies to witness-executing, position-factorized memories Fpf\mathcal F_{\mathrm{pf}}. Correctness in that class must resolve a witness through slot-specific entries; the proof then lower-bounds the entries needed after allowing witness selection, error, and abstention. Pair-balancedness limits the support lost when low-mass queries are omitted; selector optimality connects the minimized charge to reference-selector H−SH-S; explicit-entry accounting converts entries to scalar parameters. Direct answer shortcuts and superposed or shared representations can escape this class. The unrestricted extension remains Conjecture 1.

We have also updated the pretrained-model evidence. The original all-linear LoRA experiments remain bottom-censored at rank 1. A subsequent restricted-adapter study (E-S; last-two-block q,vq,v projections of Qwen2.5-0.5B) exposes finite-training transitions, but the confirmatory results do not support transfer of the proposed HH ordering. With two completed confirmatory seeds, hubs and reuse_hi have H=1310H=1310 and 13141314, yet observed 18k-step adapter thresholds of 90,11290{,}112 and 22,52822{,}528 parameters. Three of six thresholds decrease at 54k steps, so these are not established architectural capacity lower bounds. We now report this negative transfer and optimization sensitivity explicitly.

Weakness 1 / Question 1 — novelty beyond Ravfogel et al. (2026)

“How is the proposed H−SH-S bound different from Ravfogel et al. (2026)? Besides adding graph structure, what new insights does it provide?”

Response. Our claim is a conditional graph/workload refinement, not a new universal associative-capacity law. The construction charges distinct retained (fact, hop-position) associations HH, allows graph-witness macro decompositions with charge HDH_D and credit S=H−min⁡DHDS=H-\min_D H_D, and accounts for realizable simultaneous branching through WDW_D. For every admissible decomposition, Theorem 1 gives

dD=O ⁣(WD2log⁡(ND/η)),PD=O ⁣(dD2+(HD+code/dictionary terms)dD).d_D=O\!\left(W_D^2\log(N_D/\eta)\right),\qquad P_D=O\!\left(d_D^2+(H_D+\text{code/dictionary terms})d_D\right).

Only in the branch-functional, workload-dominant specialization does this simplify to an H−SH-S charge. Theorem 2 provides a class-specific necessity statement; it does not claim equivalence for unrestricted Transformers. The revision now contrasts the exact scope of these results with the closest geometric account and works through an explicit graph-to-bound example.

Weakness 2 / Question 2 — restrictive lower-bound assumptions

“Is the H−SH-S lower bound a general limitation of latent multi-hop reasoning, or does it mainly come from the position-factorized memory assumptions?”

Response. It is a lower bound within the stated restricted class. Witness execution and per-entry expressivity are substantive restrictions; the nontrivial derivation is the quantitative retained-entry requirement under coverage/error slack and the additional hypotheses. We do not claim a general Transformer limitation. In the revised manuscript, the theoretical result, the controlled Fpf\mathcal F_{\mathrm{pf}} experiments, and the negative E-S transfer findings are explicitly separated.

We hope these clarifications and the additional negative evidence address the concerns underlying your updated assessment. We would be grateful if you would reconsider your score in light of the revised manuscript and responses.

Thank you for your effort in the rebuttal, including the examples and the clearer scope of Theorem 2. I appreciate it. However, the new experiments do not resolve my concerns but rather reinforce them. The lower bound only applies to a restricted memory class, and the new results do not show that it can be generalized to Transformers. Therefore, I intend to keep my rating of 2.

Reviewer_i6ksOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies when a model can answer multi-step questions using knowledge stored in its parameters instead of searching a knowledge graph step by step. It examines how the connections between facts affect the amount of storage needed. The authors give theoretical bounds for specific memory designs and test their predictions on controlled graphs.

Critical strengths
  1. The paper asks a useful question about when models can answer multi-step queries from stored parametric knowledge.
  2. Looking at how facts connect, rather than just counting them, gives a more detailed picture of what makes knowledge hard to store.
Critical weaknesses
  1. The paper is is very hard to follow. For example in abstract: terms such as “coverage-conditioned support usage” and “frame-nonaligning composition” need a simple explanation of what they mean and why they matter.

  2. The lower bound applies to memories that store explicit key–value entries, while the extension to general Transformers remains a conjecture. Could the authors explain what the current theory tells us about trained Transformers?

  3. The distractor control does not establish the log₂ |V| factor. Is there another experiment that tests this dependence on graph size? Which parts of the theoretical prediction are supported by the results, and which remain untested?

  4. The theory is difficult to follow because many definitions and assumptions are introduced together. A worked example showing how the storage measures are calculated and used in the bounds would help.

A note on my assessment: I am less familiar with the theoretical tools used here and could not verify the proofs. My comments focus mainly on the experiments, clarity, and relevance to practical models.

Questions for authors

Check the Weaknesses

1 comment

We thank the reviewer for highlighting presentation, theory scope, and the unverified vocabulary-size factor. We have revised the introduction, the worked example, and the separation between guarantees and trained-model observations.

Weakness 1 — presentation and terminology

“The paper is very hard to follow. For example in abstract: terms such as ‘coverage-conditioned support usage’ and ‘frame-nonaligning composition’ need a simple explanation of what they mean and why they matter.”

Response. We now explain the three structural quantities before formalizing them: HH counts distinct (fact, hop-position) pairs in the retained workload; SS is the reduction achievable by admissible path/macro decomposition; and WDW_D counts simultaneously realizable branches that the construction must represent. Frame-nonaligning composition means combining memories without estimating or undoing their relative latent-coordinate mismatch. An overview figure and expanded graph-to-bound example precede the main theorems.

Weakness 2 / Question — restricted lower bound and Transformers

“The lower bound applies to memories that store explicit key–value entries, while the extension to general Transformers remains a conjecture. Could the authors explain what the current theory tells us about trained Transformers?”

Response. Theorem 2 is an entry-count lower bound for witness-executing, position-factorized memories Fpf\mathcal F_{\mathrm{pf}}. It becomes a scalar-parameter statement only under explicit-entry assumptions; Transformers with direct shortcuts, weight sharing, or superposition need not satisfy these conditions. The unrestricted extension remains Conjecture 1.

The original all-linear pretrained LoRA arms were bottom-censored at rank 1. We now also report E-S, a later restricted-adapter study that exposes finite-training thresholds. Its two-seed confirmatory comparison does not show reliable ordering by HH across graph families: hubs (H=1310H=1310) and reuse_hi (H=1314H=1314) have 18k-step thresholds 90,11290{,}112 and 22,52822{,}528 trainable adapter parameters, respectively. Extending training to 54k steps lowers three of six family thresholds, indicating optimization effects. These results do not validate a general Transformer capacity law; the revised paper reports them as a negative transfer and measurement-limit finding.

Weakness 3 / Question — the log⁡2∣V∣\log_2|V| factor

“The distractor control does not establish the log⁡2∣V∣\log_2|V| factor. Is there another experiment that tests this dependence on graph size? Which parts of the theoretical prediction are supported by the results, and which remain untested?”

Response. We agree. Increasing unused graph size from 2k to 32k while holding the retained support fixed does not resolve a threshold shift. Crucially, the capacity ladder was itself scaled with Hlog⁡2∣V∣H\log_2|V|, so this control cannot separately identify the vocabulary factor. We do not claim that it does. Controlled gated-memory measurements are compatible with approximately support-linear scaling but cannot uniquely distinguish correlated support predictors; E-S does not establish transfer to pretrained Transformers. The precise vocabulary dependence and general Transformer lower bound remain open.

Weakness 4 / Question — worked example

“A worked example showing how the storage measures are calculated and used in the bounds would help.”

Response. We expanded the k=2k=2 chain, hub, shared-macro, and diamond examples beyond the earlier summary table. The chain has H2=4H_2=4, greedy decomposed charge H2D=2H_2^D=2, credit S2=2S_2=2, and WD=1W_D=1; the diamond has H2=8H_2=8, S2=0S_2=0, and WD=2W_D=2. The revision traces the charged fact/slot pairs and substitutes the resulting terms into the full upper bound:

dD=O(WD2log⁡(ND/η)),PD=O ⁣(dD2+(HD+other code terms)dD).d_D=O(W_D^2\log(N_D/\eta)),\qquad P_D=O\!\bigl(d_D^2+(H_D+\text{other code terms})d_D\bigr).

The simplified H−SH-S expression is presented only under branch-functional and workload-dominance conditions, not as a general identity.

We hope the clearer presentation, worked example, and updated empirical scope address your questions. We would be grateful if you would reconsider your score based on these revisions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.