acceptodds
Under review as a conference paper at ICLR 2027

Train Short, Reason Long: Compositional Generalization via Frozen Holographic Memory

Abstract

Trained sequence models compose known facts at the depths they trained on but degrade beyond them. We trace the failure to one architectural choice: trained weights both decide which facts to compose and execute the composition, so an approximation in one corrupts the other. Systems that keep execution symbolic avoid the choice, but where their rules compose along one path over a fixed set of facts, a fact off the path is never read and a fact that changes is never replaced. We present Frozen Holographic Memory (FHM), an architecture in which trained weights decide what enters a composition and a fixed algebra executes it. One algebra holds facts, replaces them exactly, composes them, and induces rules from them. Trained on possession chains up to two facts deep, FHM tracks state exactly on chains 40 facts deep. Trained on CLUTRR stories of two or three facts, it composes ten-fact stories at 100.0% on the net generation count and 98.3% on the full kinship label. On NoRA, FHM induces its own rules and constraints and scores above the Edge Transformer on every split scored, 52.8% against 6.0% on the split whose answers need the most facts off the path. We intend FHM as an architectural primitive for any system that requires state tracking, composition at unseen depths, rule induction, or off-path reasoning.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
neuro-symbolic, vector symbolic architectures, holographic reduced representations, rule induction, state tracking, compositional generalization, systematic generalization

Reviews

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

This paper proposes a neural-symbolic architecture, Frozen Holographic Memory (FHM), for compositional reasoning. Building on the holographic representation framework of Plate (1994), FHM uses fixed algebraic operations to store, update, and compose facts, while relying on lightweight neural controllers to learn task-specific decisions. Across three state-tracking and compositional reasoning benchmarks (Possession, CLUTRR, and NoRA), FHM demonstrates strong generalization performance when evaluated on reasoning depths and relation compositions beyond those encountered during training, outperforming the compared transformer-based baselines.

Critical strengths
  • The experimental results are promising. FHM demonstrates strong extrapolation performance on possession chains and CLUTRR relation compositions beyond the training depths, and substantially outperforms the Edge Transformer on the evaluated NoRA splits, particularly on off-path reasoning.
Critical weaknesses
  • Limited baseline comparisons. The compared baselines are limited, making it unclear whether the strong empirical results come from the proposed holographic memory design or primarily from the predefined symbolic reasoning operations. The authors mainly compare FHM against transformer-based models, while prior work has shown that incorporating explicit structural or algebraic inductive biases can substantially improve compositional generalization [1,2,3]. I believe it is important to include comparisons with other symbolic or neuro-symbolic approaches, particularly a symbolic baseline using the same reasoning procedures but without the holographic memory representation.

  • Heavy reliance on task-specific design. The proposed FHM architecture heavily relies on task-specific knowledge and manually designed reasoning procedures, which raises concerns about its applicability to new tasks. For example, the rule templates used for NoRA are selected based on the rule structures provided by the benchmark, while CLUTRR relies on predefined generation-count operations and relation composition procedures. In my view, a major limitation of such approaches is their dependence on domain-specific structural priors, which may not be readily available in realistic applications. The paper lacks a discussion of this limitation and how FHM could be applied to tasks where the underlying reasoning structures are unknown.

  • Presentation needs to be improved. Section 2 is difficult to follow, partly because substantial space is devoted to introducing existing holographic memory operations. I would suggest more clearly separating the established algebra from Plate 1994 from the novel design choices of FHM, and adding an overview figure illustrating the complete reasoning pipeline.

[1] Herzig, J., & Berant, J. (2021, August). Span-based semantic parsing for compositional generalization. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) (pp. 908-921).

[2] Yao, Y., & Koller, A. (2022, December). Structural generalization is hard for sequence-to-sequence models. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (pp. 5048-5062).

[3] Liu, C., An, S., Lin, Z., Liu, Q., Chen, B., Lou, J. G., ... & Zhang, D. (2021, August). Learning algebraic recombination for compositional generalization. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021 (pp. 1129-1144).

Questions for authors

Do the authors have any insights into how FHM or similar symbolic methods could be applied to more realistic state-tracking or compositional reasoning tasks, where task-specific reasoning structures and operations may not be known in advance?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 599y

Thank you for your time and for highlighting FHM's off-path reasoning on NoRA.

"The compared baselines are limited, making it unclear whether the strong empirical results come from the proposed holographic memory design or primarily from the predefined symbolic reasoning operations."

The symbolic operations produce the scores, while the holographic memory trains the decisions on possession and CLUTRR. Part 2/5 reports the baseline you requested, where Python dictionaries replace FHM's stores and the reasoning procedures stay unchanged. On every benchmark, this baseline executes FHM's trained decisions and scores the same as FHM. With the dictionary replacing the store during training, no gradient path exists, so we use REINFORCE. The controller then learns to write on an observation verb in some possession seeds and does not fit CLUTRR's net generation count in four seeds of five.

"The authors mainly compare FHM against transformer-based models, while prior work has shown that incorporating explicit structural or algebraic inductive biases can substantially improve compositional generalization [1,2,3]."

Besides the symbolic baseline, we added two baselines that are not transformers. DeltaNet fits its training regime on possession and reaches 98.7% at depth 40 but 84.8–89.7% across depths with 100 items. An LSTM does not fit (Part 3/5). We did not run the methods of the three papers you cite, which study semantic parsing. The revised related work discusses them (Part 5/5).

"For example, the rule templates used for NoRA are selected based on the rule structures provided by the benchmark, while CLUTRR relies on predefined generation-count operations and relation composition procedures."

The revised experiments drop NoRA's rule templates and train a controller on CLUTRR's products. In the submission, NoRA's candidate if-parts took their shapes from the benchmark's rules. Now, controllers decide which if-parts of one to three facts to keep as rules. On CLUTRR, a controller learns each pair's product from the answer alone, whereas the submission wrote it into the product store from the training questions. The net generation count still runs on a predefined count store, but its controller chooses among 19 offsets, up from five. Learning these decisions costs accuracy: CLUTRR's full label falls from 98.3% to 69.9% at length 10, while NoRA scores lower on Test-BL, Test-OPEC and Test-W's hard questions (Parts 3/5 and 4/5).

"I would suggest more clearly separating the established algebra from Plate 1994 from the novel design choices of FHM, and adding an overview figure illustrating the complete reasoning pipeline."

The revised Section 2 separates Plate's algebra from what FHM adds and includes an overview figure of the full pipeline (Part 5/5).

"Do the authors have any insights into how FHM or similar symbolic methods could be applied to more realistic state-tracking or compositional reasoning tasks, where task-specific reasoning structures and operations may not be known in advance?"

The revised experiments are a step toward such tasks. Controllers now learn NoRA's rules and CLUTRR's products, whereas before, FHM induced the rules in its rule store and wrote the products from the training questions. The store's operations and each task's procedure are still fixed in advance. Applying FHM where those are unknown is outside this paper's scope, as the new Limitations section states (Part 1/5).

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

This paper proposes an architecture that separates learned decisions from the actual execution of reasoning operations. Instead of learning how to perform every reasoning step, FHM uses a fixed algebraic memory to store, update, and compose facts, while small learned controllers decide which information should be used. The authors evaluate the module on three tasks: possession tracking, CLUTRR kinship reasoning, and NoRA relational reasoning. The results show strong generalization to much longer sequences than those seen during training.

Critical strengths

Interesting architecture with strong length generalization.

I think the separation between learned decisions and fixed algebraic operations is an interesting direction. The experimental results are quite good, particularly on the possession and CLUTRR tasks, where the method maintains high accuracy at much greater depths than those seen during training.

Evaluation across different reasoning problems.

I also appreciate that the authors go beyond simple sequence tracking and evaluate the method on relational reasoning and off-path reasoning. The ablation studies provide useful evidence that exact replacement, memory capacity, and discrete retrieval contribute to the method's performance.

Critical weaknesses

1. The comparison with the Transformer baselines is not fully convincing.

My main concern is that the Transformer baselines do not successfully fit the training regime on the possession task. As reported in Section 4.1, their validation accuracy remains below the authors' 95% criterion, even before evaluating longer sequences. This makes it difficult to determine whether the large performance gap mainly reflects better compositional generalization or simply that the baselines have not learned the original task sufficiently well.

2. The generality of the proposed reasoning framework remains unclear.

Although the results are strong, much of FHM's reasoning ability seems to come from predefined operations and task-specific structure. For example, the architecture uses explicit fact representations, fixed binding and unbinding operations, predefined rule templates, and task-specific memory organization. On NoRA, the system does not train any neural controller, but instead induces rules using a predefined set of candidate patterns. This makes me question how much of the reported generalization comes from learning a reusable reasoning mechanism, rather than applying carefully designed symbolic operations to tasks that already have a compatible structure.

I also wonder how the approach would scale to less structured inputs, where facts and relations must be extracted from natural language and may be ambiguous or noisy. Given the paper's broader claims about compositional reasoning, I think this is an important limitation.

Questions for authors
  1. Could the authors clarify why the Transformer baselines do not achieve higher accuracy on the training-regime validation tasks? Would this affect the conclusions about generalization?

  2. How much does the proposed method rely on predefined symbolic structures and task-specific rules? Could the authors discuss how it might generalize to less structured tasks?

  3. It would be helpful to include a discussion of the limitations of FHM, particularly when dealing with noisy or ambiguous information.

1 comment
AuthorsOpenReview ↗

Response to Reviewer oaGm

Thank you for your time and for your interest in FHM's architecture.

"Could the authors clarify why the Transformer baselines do not achieve higher accuracy on the training-regime validation tasks? Would this affect the conclusions about generalization?"

They had stopped training once their validation accuracy had not improved for 2,000 steps, whether they had fit or not. Without early stopping and with 2-3x the training steps, every transformer we report fits, at 95% or more on 1,000 validation stories. Once fit, they still score 22–35% at depth 40, so the conclusions about generalization do not change (Part 3/5).

"How much does the proposed method rely on predefined symbolic structures and task-specific rules?"

Less than in our original submission. You noted that on NoRA, FHM "does not train any neural controller". Controllers now decide which rules and constraints to keep. Their candidates no longer take their shapes from the benchmark. On CLUTRR, a controller now learns each pair's product, which the submission wrote into the product store from the training questions. Learning these decisions costs accuracy. CLUTRR's full label falls from 98.3% to 69.9% at length 10, while NoRA scores lower on Test-BL, Test-OPEC and Test-W's hard questions (Parts 3/5 and 4/5). Each task's parsed input, the store's operations and each task's procedure remain predefined (Part 4/5).

"This makes me question how much of the reported generalization comes from learning a reusable reasoning mechanism, rather than applying carefully designed symbolic operations to tasks that already have a compatible structure."

We design the operations but train the decisions. Part 2/5 tests each. The operations execute a decision exactly: a Python dictionary executing FHM's trained decisions scores the same on possession and CLUTRR, as a Python set does on NoRA. On possession and CLUTRR, the gradient path through the store is what trains the decisions. With a dictionary in the store's place during training, the same controller learns to write on an observation verb in some possession seeds and does not fit CLUTRR's net generation count in four seeds of five.

"I also wonder how the approach would scale to less structured inputs, where facts and relations must be extracted from natural language and may be ambiguous or noisy."

We have not tested FHM on unparsed input. The new Limitations section scopes the claims to parsed inputs (Part 1/5).

"It would be helpful to include a discussion of the limitations of FHM, particularly when dealing with noisy or ambiguous information."

The Limitations section covers both. The NoRA splits we score contain ambiguous facts, which FHM resolves by enumerating their refinements. On Test-W's hard questions, which rest on an ambiguous fact, FHM answers 323–343 of 389 over five seeds (Part 4/5). We have no result on noisy input.

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

The paper introduces Frozen Holographic Memory (FHM), which separates learned decisions about which facts enter a composition from the fixed algebraic operations that execute it. It combines frozen complex-valued representations, memory cleanup, and explicit procedures for storing, updating, and composing structured facts to generalize from short training examples to longer reasoning chains. Experiments on different reasoning tasks report strong generalization and improvements over the evaluated transformer baselines.

Critical strengths

Clear architectural principle: FHM separates learned decisions from fixed execution procedures for memory updates and composition. This provides an mechanism for repeatedly applying learned local decisions at greater depths, while explicit updates and memory cleanup help control interference.

Strong length generalization on structured reasoning tasks: the CLUTRR results are particularly convincing. After training on stories containing two or three facts, FHM achieves 100% generation-count accuracy and 98.3% full kinship-label accuracy on ten-fact stories. Here, the transformer baselines fit the training regime but deteriorate on longer problems.

Critical weaknesses

Broader applicability remains untested: the authors position FHM as a broadly applicable architectural primitive, but its usefulness as a component of a larger learned system remains untested. The experiments demonstrate strong performance within task-specific pipelines using structured facts and predefined reasoning procedures, without showing how an existing model could learn to use FHM or whether integrating it would improve reasoning.

Questions for authors

How could FHM be integrated into a larger learned model, and what evidence supports its usefulness beyond the current task-specific pipelines?

1 comment
AuthorsOpenReview ↗

Response to Reviewer g4cG

Thank you for your time and for highlighting FHM's separation of learned decisions from fixed execution.

"Broader applicability remains untested: the authors position FHM as a broadly applicable architectural primitive, but its usefulness as a component of a larger learned system remains untested."

We have not tested FHM inside a larger model. The revisions remove the sentence that positioned FHM as a primitive for any system from the abstract and the conclusion (Part 5/5).

"The experiments demonstrate strong performance within task-specific pipelines using structured facts and predefined reasoning procedures, without showing how an existing model could learn to use FHM or whether integrating it would improve reasoning."

Controllers now learn NoRA's rules and CLUTRR's products, whereas before, FHM induced the rules in its rule store and wrote the products from the training questions (Part 4/5). However, the full label you cited fell from 98.3% to 69.9% on ten-fact stories, while the net generation count stayed at 100% (Part 3/5). Each task still receives parsed facts and runs a procedure fixed in advance.

"How could FHM be integrated into a larger learned model, and what evidence supports its usefulness beyond the current task-specific pipelines?"

We have no such evidence. Integrating FHM into a larger learned model is a direction we want to pursue, which the Limitations section places outside this paper's scope.

Comments on the paper

7 comments
AuthorsOpenReview ↗

General Response (Part 1/5)

We thank all reviewers for their time and feedback! All three reviews highlighted FHM's length generalization beyond training depths. Reviewers g4cG and oaGm also highlighted its separation of learned decisions from fixed algebraic operations, and Reviewers oaGm and 599y highlighted its off-path reasoning on NoRA. The main concerns are whether the results come from the holographic memory or from predefined operations (Reviewers 599y and oaGm), how much of FHM we tailored to each task and whether it extends to tasks with unknown structure (all), and whether we trained the transformer baselines until they fit (Reviewer oaGm).

FHM is one way to separate learned decisions from exact execution. Its controllers make decisions while its store executes them exactly. A gradient path from the answer back to the controllers trains each decision. An exact data structure with no differentiable path, such as a Python dictionary, executes the same decisions exactly but carries no gradient back to them, so another method has to train the decisions. Learned state trackers train end to end, but in our comparisons, their accuracy falls with depth or story size. We build FHM's store on holographic reduced representations because binding alone builds the facts and keys of every store across tasks. Binding powers of one code adds their exponents, enabling arithmetic within the same representation. A data structure with no binding operation needs its keys and its arithmetic defined separately for each task.

New and revised experiments plus a new Limitations section address each concern:

  • Revised experiments on CLUTRR and NoRA (Reviewers 599y, oaGm, g4cG). On CLUTRR, a controller now picks each pair's product, where before the submission wrote each product into the product store from the training questions. We train it through the store by the answer alone and give it no path between the question's two people. The full label falls from 98.5% to 84.2% over the test split and from 98.3% to 69.9% at length 10, while the net generation count, trained the same way, stays at 100% at every length. On NoRA, controllers now decide which rules and constraints to keep without any shapes taken from the benchmark. Over five seeds, Test-D scores 1,087 of 1,123 in every seed, Test-W 6,316–6,333 of 6,452, Test-BL 11,427–11,599 of 12,000 and Test-OPEC 105–110 of 216.
  • A symbolic baseline (Reviewers 599y, oaGm). We kept FHM's procedures and its trained controllers but swapped each store on possession and CLUTRR for a Python dictionary. On NoRA, a Python set replaces the store that holds a story's facts. All possession grid cells, CLUTRR lengths and NoRA splits score the same as the holographic memory.
  • Controllers trained without the gradient path (Reviewers 599y, oaGm). Trained by REINFORCE through a Python dictionary, the possession controller fits in every seed. One seed in five at a learning rate of 1e-3 and three in five at 5e-3 then score 71–80% on the grid. On CLUTRR's net generation count, REINFORCE fits one seed in five.
  • Retrained transformer baselines (Reviewer oaGm). On possession, trained without early stopping and for 2-3x as many steps, each fits its training regime and then scores 22–35% at depth 40.
  • A new DeltaNet baseline (Reviewer 599y). Trained and scored on possession, it reaches 98.7% at depth 40 and 84.8–89.7% across depths with 100 items, at the best of its three learning rates. An LSTM, also added on possession, does not fit its training regime (best validation 67.5%).
  • A Limitations section (all three reviewers). The section scopes the claims to parsed inputs and operations fixed in advance.
AuthorsOpenReview ↗

General Response (Part 2/5)

1. What the holographic memory contributes (Reviewers 599y, oaGm)

Reviewer 599y asked whether the results come from the holographic memory or primarily from the predefined symbolic reasoning operations. Reviewer oaGm asked how much of the generalization comes from learning a reusable reasoning mechanism rather than from carefully designed symbolic operations. We prepared two demonstrations that swap FHM's stores for Python dictionaries.

Our first isolates execution by replacing each store with a dictionary only after training. The dictionary receives the same writes as the store it replaces and executes the trained controllers' decisions. On NoRA, a Python set replaces the store that holds a story's facts, with the learned rules and constraints kept.

BenchmarkScores comparedEqual to FHM's
Possession grid40 cells (20 held-out, the same 20 drawn with training names) in 5 seeds200 of 200
CLUTRR, net generation count9 lengths in 5 seeds45 of 45
CLUTRR, full label9 lengths in 5 seeds45 of 45
NoRA4 splits in 5 seeds20 of 20

Our second keeps the dictionary in place during training as well. In the first, FHM trained the controllers but the dictionary executes their decisions. Here, the dictionary has no gradient path back to the controller, so REINFORCE [1] on the answer trains it instead. On possession, FHM and REINFORCE use the same controller and the same corrected stories (Part 3/5). REINFORCE runs at the two learning rates that tied on validation in our selection on seed 0.

ArmValidationPossession grid, 40 cells
FHM100% in every seed100% in every cell, 5 of 5 seeds
Dictionary, REINFORCE, 1e-397.2–100%100% in 4 seeds, 71–80% in 1
Dictionary, REINFORCE, 5e-395.4–100%100% in 2 seeds, 71–80% in 3

Every seed that scores 71–80% on the grid learns to write on the observation verb "wants", although an observation does not change who holds an item.

We ran the same comparison on CLUTRR's net generation count. REINFORCE runs at 5e-3, the only of three learning rates that fit on seed 0.

ArmValidationLength 10
FHM100% in every seed100% in every seed
Dictionary, REINFORCE, 5e-3100% in 1 seed, 13.0–49.5% in 4100% in 1 seed, 2.5–32.8% in 4

References

[1] Williams (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning.

AuthorsOpenReview ↗

General Response (Part 3/5)

2. What the baselines score once they fit (Reviewers oaGm, 599y)

Reviewer oaGm asked whether the gap on possession reflects generalization or transformer baselines that "have not learned the original task sufficiently well". Reviewer 599y noted that we compare FHM mainly against transformer-based models. We retrained the transformers until each fit and added DeltaNet [2] and an LSTM [3].

A shortcut in the possession task. In the training stories, every decoy came before a transfer. No observation followed the focal item's last transfer, so the guess by recency of Section 4.1 (the person in the last event that mentions the item) was always right for the focal item. We changed the generator so that half of the decoys come after the transfer and mention the focal item. On the grid, every question now asks about the focal item and a decoy always follows its last transfer, so a guess by recency scores 0% in every cell.

The transformer protocol. On the possession task, the transformer arms had stopped training once their validation accuracy had not improved for 2,000 steps, whether they had fit or not. We removed early stopping and trained each arm on seed 0 for 20,000 steps at learning rates of 1e-4, 3e-4 and 1e-3, leaving out 3e-3, the worst rate on both arms in our earlier selection. Since no rate fit, we trained each arm's best rate for 40,000 steps (text) or 60,000 steps (event). Both event transformers kept a constant learning rate after the warmup, since at 1e-4 it reached higher validation than a cosine decay. The event transformer with randomized positions reused the event transformer's rate, 1e-4, where it fit within 40,000 steps. Every transformer in the table below now fits, at 95% or more on 1,000 validation stories.

The table gives accuracy under the restricted readout, as a mean over seeds, at 5 items for depths 2–40 and at depth 2 for 100 items. Chance is 25%. We score every row on held-out names except the text transformer's, which we score on the same grid cells drawn with training names. The text transformer never answers with a name it did not see in training, so on held-out names it scores 0% under the unrestricted readout. The event transformer now draws fresh tokens for each story's people and items, in training and at evaluation, so a story with held-out names reads like one with training names.

ModelValidation of the final runsDepth 2Depth 5Depth 10Depth 20Depth 40Depth 2, 100 items
FHM, 1,026 trained parameters, 5 seeds100 in every seed100100100100100100
Text transformer, 19.0M parameters, 3 seeds, training names99.9 / 100 / 99.7997648433028
Event transformer, 19.1M parameters, 3 seeds95.8 / 99.4 / 99.61005863443525
Event transformer with randomized positions [4], 3 seeds98.9 / 98.1 / 97.61003630272226
DeltaNet [2], 20.7M parameters, 1e-3, 3 seeds100 in every seed1001001001009990
DeltaNet, 3e-4, 3 seeds100 in every seed100100100979077
Guess by recency78.3 (94.0 before)000000

DeltaNet fits at all three of its learning rates, with 100% validation. At 1e-4 it scores 76% at depth 40 and 75% at depth 2 with 100 items. At 1e-3 it scores 84.8–89.7% across depths with 100 items. The LSTM [3] does not fit its training regime at any rate, although our LSTM solves Delétang et al.'s parity task at every length from 41 to 500.

The CLUTRR transformers also train without early stopping. Each of four learning rates fits within 3,000 steps on seed 0, at 99.7% or more on all 2,020 of the benchmark's validation stories. We report 1e-4 on the net generation count (5 seeds) and 3e-4 on the full label (3 seeds), the smallest of the rates with the best mean validation, after final runs of 10,000 steps. The table gives accuracy by story length. FHM's rows are the revised runs, as means of 5 seeds. Training stories have lengths 2 and 3.

Length2345678910
Net generation count, transformer10010092805952424346
Net generation count, FHM100100100100100100100100100
Full label, transformer1009576544135333127
Full label, FHM1007893928785787770

At length 10, the paper's transformers scored 39.3% on the net generation count and 19.5% on the full label. A dictionary scores the same full label as FHM at every length in every seed (Part 2/5).

References

[2] Grazzi et al. (2025). Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues. ICLR.

[3] Delétang et al. (2023). Neural Networks and the Chomsky Hierarchy. ICLR.

[4] Ruoss et al. (2023). Randomized Positional Encodings Boost Length Generalization of Transformers. ACL.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.