acceptodds
Under review as a conference paper at ICLR 2027

PCAF: Bounded Exact-Successor Memory for Efficient Language Models

Abstract

Efficient causal models compress long histories, which can erase token-successor associations. We study PCAF-Exact, a bounded per-key memory that retains recent observed successors and mixes their sparse vote with a causal model’s prediction. Capacity-matched experiments show that exact memory improves PG-19 perplexity across three model scales; at 40M/64K, PPL falls from 129.72 to 114.54. A parameter-free reciprocal-recency reader retains much of this benefit. Under equal record storage, continuous retrieval gives lower perplexity, while exact lookup reads about 2.3× faster; measured teacher-forced pipelines show a smaller speed advantage. A compact hybrid improves on a payload-matched continuous reader across 19 PG-19 test books at both evaluated scales. Same-target tests show gains through 128K context. Together, these results position bounded exact-successor memory as an efficient complement to contextual retrieval for repeated transitions.

Primary area:
foundation or frontier models, including LLMs
Keywords:
language modeling, long-context models, bounded memory, exact-successor retrieval, associative memory, recurrent neural networks, state-space models

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_nQWtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Paper Summary

  • Overview: The paper investigates PCAF-Exact, a bounded exact-successor cache that stores up to KK recent completed transitions per unique token key, decoupled from sequence-level token distance. At inference time, the model interpolates this sparse transition distribution with the causal LM's parametric output distribution via a fixed or learned mixture weight.
  • Key Claims:
    1. Access Dominates Weighting: A parameter-free reciprocal-rank reader (1/r1/r) recovers nearly all empirical gains achieved by learned scoring, pruning, and contextual gating.
    2. Coverage vs. Efficiency Trade-off: Under matched byte budgets, continuous hidden-state retrieval yields lower perplexity through broader target support, whereas exact lookup runs roughly 2.3x faster in isolated reader operations.
    3. Hybrid Contextual-Exact Memory: Combining an exact-key cache with a contextual hidden-state reader consistently reduces perplexity over payload-matched continuous baselines.
  • Empirical Scope: Small recurrent and delta-rule backbones (40M–350M parameters) evaluated under low token budgets (~0.5–2.5 tokens per parameter), extended context evaluations up to 128K tokens, a 5B-token pretraining run on a 125M backbone, and post-hoc adaptation on frozen Qwen3-1.7B.
Critical strengths

Critical Strengths

  1. Ablation Discipline and Transparent Negative Reporting: Unlike many architectural proposals that gloss over diminishing returns, the authors candidly document where the method stalls. They explicitly present the rapid decay of exact-memory utility over longer training trajectories (Table 33), the failure modes of Learned PCAF under multi-key transfer seeds (Appendix J), and the near-zero PPL deltas on frozen Qwen3-1.7B.
  2. Rigorous Decomposition of Access vs. Weighting: The paper cleanly separates candidate retention from candidate probability scoring. Demonstrating that an unparameterized reciprocal-rank rule performs within Δ=0.019\Delta = 0.019 NLL of a fully parameterized neural scoring and gating pipeline convincingly demonstrates that the primary utility stems from the index structure rather than learned scoring mechanics.
Critical weaknesses

Critical Weaknesses

  1. Gains Disappear in Well-Trained Regimes (Compensation for Undertraining) & Detached from Realistic Autoregressive Serving and Large Vocabularies
    The reported perplexity improvements are driven almost entirely by severely undertrained models evaluated at ~0.5–2.5 tokens per parameter. Once trained more adequately (125M model evaluated across 5B token presentations), the NLL gain collapses from -0.0311 to -0.0025 (a marginal 0.33% PPL reduction). Similarly, testing on a fully converged pretrained base (Qwen3-1.7B) yields a negligible ~0.5% PPL drop. The mechanism merely compensates for unconverged parametric representations and offers virtually no practical utility for production-scale models trained on modern trillion-token budgets. The advertised 2.3x reader speedup isolates a micro-operator and drops to a trivial 1.09x–1.23x within the complete teacher-forced pipeline, where backbone and vocabulary compute dominate. More critically, the paper lacks batched autoregressive generation benchmarks (TTFT, token decode latency, memory bandwidth contention). Under modern vocabulary sizes (128K–256K), the proposed dense O(BVK)O(BVK) buffer forces unacceptable static memory footprints, whereas sparse hash-based alternatives introduce irregular GPU memory access that will easily eliminate the marginal pipeline throughput gain.

  2. Absence of Intuitive Qualitative Results and Case Studies
    The paper relies almost exclusively on dense aggregate numerical tables and custom statistical strata, completely lacking qualitative text-level examples or concrete case studies. It remains opaque to the reader in what specific natural-language contexts exact single-token successor memory actually succeeds or fails (e.g., rare entities, code syntax, boilerplate text vs. common polysemous words). Providing concrete input-output snippets and prediction-probability shift examples would be essential to substantiate the real-world linguistic utility beyond abstract statistical summaries.

Questions for authors

Questions for Authors

  1. Clarification on Representation Saturation vs. Memory Utility: In Table 33, the exact-reader NLL advantage decays by an order of magnitude (from -0.0311 to -0.0025) as the 125M model is trained to 5B presentations. Does qualitative or token-class analysis reveal what specific transitions the cache is still winning on at 5B tokens (e.g., verbatim repetitive boilerplate, rare proper nouns, numerical constants)? If the parametric recurrent backbone naturally internalizes these transitions with sufficient training, what is the justification for maintaining an external exact cache in models trained on multi-trillion tokens?

  2. Clarification on Large Vocabulary Scalability: All from-scratch models fix the vocabulary size to V=20,000V = 20,000. Modern LLM tokenizers routinely employ vocabularies between 128,000 and 256,000 tokens. In the dense configuration, reserving O(BVK)O(BVK) slots under realistic serving conditions (B=32,K=8B = 32, K = 8) demands hundreds of megabytes in static GPU allocation per instance purely for integer index arrays. If falling back to dynamic sparse hash maps or dictionary allocations, what measured kernel launch overhead and memory divergence latency are incurred during single-token step decoding on GPU?

  3. Clarification on End-to-End Autoregressive Generation: The reported runtime benefits focus heavily on an isolated reader microbenchmark (around 2.3x speedup) and a teacher-forced full-window evaluation pipeline (~1.09x–1.23x speedup). Can you provide end-to-end wall-clock serving metrics for batched autoregressive generation (e.g., Time-To-First-Token and per-step token generation latency at batch sizes 8 or 32)? In an actual generation loop with variable-length sequences, does exact lookup retain a meaningful throughput advantage over fused sliding-window attention?

  4. Request for Qualitative Case Studies: The empirical validation relies almost exclusively on aggregate perplexity numbers and statistical breakdowns. Could you provide concrete qualitative examples or case studies demonstrating how the exact successor vote shifts prediction probabilities on actual text spans (comparing instances where the exact cache successfully overrides a confused backbone versus where it introduces harmful unigram bias)?

4 comments

Thanks for the revisions and the additional experiments. The longer-training analysis and the stronger storage-matched comparison make the contribution clearer. I also appreciate the 128K continuation timings in Section 6, which show the cost of adding exact memory in that setting.

My main remaining question is about the separate batched autoregressive benchmark mentioned in the response. I couldn’t find the TTFT and per-step decode latency numbers for batch sizes 8 and 32 in the revised paper. Could you share those results alongside the baseline under the same prompt and generation settings? That would help me understand whether the lower reader latency translates into a meaningful speed advantage in batched decoding.

Overall, I found the distinction between access and weighting useful, and the rebuttal strengthened the paper. But I’m still not quite convinced that the contribution meets the bar for acceptance at ICLR. The gains in the longer-trained and frozen-model settings are small, and the stronger storage-matched comparison shows a modest improvement in perplexity without establishing a practical efficiency advantage. I see value in the paper as a careful study of when exact successor memory helps, but the current evidence leaves me uncertain about how broadly that finding matters. On balance, I’m keeping my rating at 2. I hope the authors build on this work and make a stronger case in a future submission, with more convincing evidence of when exact successor memory offers meaningful gains in prediction quality or decoding efficiency.

I also think the paper could tell a more compelling story: the main insight gets buried in the tables, and a clearer thread from the motivating question to the key results would make it easier to see why the findings matter.

AuthorsOpenReview ↗

Official Comment by Author

Thank you for the careful follow-up. You are correct that the batched-decoding table was omitted when we condensed the manuscript. We provide the complete requested comparison below and clarify how it relates to the paper’s contribution.

Batched autoregressive generation. Both arms use the same frozen 40M backbone, identical prompt batches, and 32 greedily generated tokens per sequence. The exact arm adds a K=8 reciprocal-rank reader with a fixed coefficient of 0.025, without retraining. Measurements use one RTX 5090, FP32, static equal-length batches, and three paired repetitions after warmup.

Prompt lengthBatchTTFT: baseline / exact (ms)Decode: baseline / exact (ms per batch step)
1,024820.77 / 37.617.77 / 8.92
1,0243282.46 / 142.2115.27 / 16.36
8,1928162.22 / 227.088.08 / 9.92
8,19232668.27 / 920.609.05 / 8.47

TTFT includes prefill, exact-memory construction and transfer, mixing, and first-token selection. Decode includes the backbone, memory updates and reads, mixing, and token selection; each step produces one token per sequence.

These results answer the efficiency question directly: the lower isolated-reader latency does not establish a consistent batched generation speedup in this prototype. At 8K/batch 32, the decode ranges overlap—7.93–9.82 ms for the baseline and 8.39–8.49 ms with exact memory—so we do not interpret the lower exact median as acceleration. The prototype also does not evaluate variable-length scheduling or a fused-attention comparator.

We nevertheless believe the paper’s contribution is broader than a serving-speed claim. Its central question is: which benefits come from retaining and accessing observed transitions, rather than learning a more elaborate reader? Three connected findings answer this:

  1. Access capacity is a more consistent lever than scoring complexity. In the controlled component cohort, increasing K from 8 to 16 lowers NLL by 0.02526, with paired interval [−0.03992, −0.01061]. By contrast, the fixed-versus-learned scoring difference is unresolved. This provides actionable evidence about where reader complexity is useful.

  2. Coverage explains where exact and contextual retrieval differ. The support decomposition, followed by the fixed-score candidate-mask intervention, connects the observed quality gap to accessible evidence rather than attributing it solely to mixture calibration.

  3. Exact evidence remains complementary to a stronger contextual reader. Against the storage-matched confidence-based control, hybrid-minus-control NLL is −0.003217 at 40M and −0.000823 at 350M, with two-scale-adjusted book intervals below zero. These effects are small and conditional on the evaluated checkpoints and books, but they demonstrate incremental predictive information beyond the stronger comparator.

The longer-training attenuation is therefore part of the characterization, not something the paper needs to explain away. The contribution is a controlled account of what bounded exact access preserves, when simple weighting suffices, and when broader contextual retrieval is needed. We appreciate your suggestion to make this thread more prominent: it is the scientific connection among the experiments, rather than the number of tables or a claim of universal decoding acceleration.

Thanks for sharing the batched decoding numbers. That answers my question. TTFT goes up in all four settings, and there isn’t a consistent speedup during decoding. I appreciate that you’ve been clear about what the results show.

Your reply also helped me see how the experiments fit together. I found it interesting that exact memory still adds some predictive value on top of a stronger contextual reader. My main hesitation is that the gains are small, both in that comparison and in the longer-trained and frozen-model settings. I came away with a better understanding of what exact memory can do, but I’m still not quite convinced that the results make a strong enough case for acceptance. I’ll keep my rating at 2.

AuthorsOpenReview ↗

Official Comment from Author

Thanks for coming back to this. We agree on what the timings show. Where we’d push back a little is on what the small gains tell us.

There are two different questions here: Is the gain big enough to justify adding exact memory to a production system? We haven’t shown that. Does a strong contextual reader make explicit transition records redundant? In our tests, it didn’t. Even when the continuous reader had the same declared memory budget and the same exact-history summaries for its gate, letting the model use the stored successor votes still improved prediction at both scales.

That matters for a concrete design choice: when a memory misses, should we improve how it scores the records it already sees, or change which records it can see? Our experiments show why those aren’t interchangeable. A better scorer can’t recover a successor it was never given.

That’s the result we’d put at the center of the paper. The small gains after longer training and the higher time to first token tell us where not to overstate it; they don’t erase what the comparison teaches us about memory design.

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

This paper investigates PCAF-Exact, a bounded exact-successor memory for language modeling. The proposed mechanism maintains the latest K observed successor tokens for each token identity and interpolates a cache-derived distribution with the backbone language model. The authors study parameter-free and learned readouts, analyze retrieval coverage, and evaluate the quality–cost trade-off against continuous neural caches. The experiments demonstrate improvements over matched reader-free backbones, particularly under limited training budgets.

Critical strengths
  1. The proposed mechanism is simple and shows lower PPL compared with controlled baselines.
  2. The target-support decomposition provides useful insights into when exact matching helps and when broader contextual retrieval is necessary.
Critical weaknesses
  1. Limited methodological novelty. The mechanism is simple yet appears closely related to the conditional bigram cache studied in classical adaptive language modeling. In particular, Rosenfeld (1994), A Hybrid Approach to Adaptive Statistical Language Modeling, already considers a conditional bigram cache that retrieves successor statistics based on the preceding word and contributes to prediction only when the corresponding context has been observed. The associated thesis further describes conditional bigram/trigram caching and interpolation in detail. PCAF-Exact differs in its per-key latest-K retention policy, reciprocal occurrence-rank weighting, and implementation for modern neural language models. Nevertheless, these distinctions do not appear sufficient, without further empirical evidence, to establish the proposed mechanism as a substantially new modeling approach. The paper should explicitly discuss this prior work and isolate the contributions of the retention policy and weighting scheme.
  2. Unclear practical significance. The primary from-scratch experiments use relatively limited training budgets, corresponding to approximately 0.57–2.5 training tokens per model parameter. Importantly, the paper's own longer-training experiment shows that the exact-cache NLL advantage decreases from approximately 0.0311 to 0.0025 as training increases from 0.1B to 5B token presentations. Similarly, improvements on frozen Qwen3-1.7B are modest, and continuous retrieval consistently achieves lower perplexity. Also, for Qwen3-1.7B, there's no end-to-end comparison (like accuracies for reasoning tasks) to show the practical use. These observations raise concerns about whether the method addresses an intrinsic limitation of compressed-state language models or primarily compensates for insufficient backbone training.
Questions for authors
  1. How does PCAF-Exact differ fundamentally from the conditional bigram cache described by Rosenfeld (1994), beyond its bounded per-key storage policy and recency weighting?
  2. Were identical tokenizers and target token sequences used for the cross-architecture perplexity comparisons in Appendix K? Note that when vocabularies mismatch, the PPLs are not directly comparable.
  3. Given the substantial reduction in gains after longer training, what evidence supports the claim that exact-successor memory addresses a persistent architectural limitation rather than primarily improving undertrained models?
Reviewer_j2VxOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes PCAF-Exact, a bounded exact-successor memory for language models. For each token key, it retains the latest K completed successor records and predicts by mixing the backbone distribution with a reciprocal-rank successor vote. The main results are that exact token-identity access provides useful transition evidence beyond capacity-matched controls, that much of the benefit survives without learned scoring/gating, and that exact access is an efficient complement to broader continuous retrieval rather than a replacement.

Critical strengths
  1. The paper separates reader-off, independently trained no-reader, capacity-matched no-reader, and separately attached fixed caches on reader-free backbones.

  2. At matched storage, continuous retrieval has lower PPL but higher read cost; the paper shows that much of the continuous-minus-exact NLL gap comes from target positions where exact candidates exist but lack the correct successor, and continuous retrieval supplies target support on many of them.

Critical weaknesses
  1. The empirical evidence is too limited and the gains too small to support the paper’s broader framing.
  2. The compact and projected hybrids use different readers, banks, payload accounting, and timing scopes, and the paper explicitly says they are never combined into one quality-latency result. The projected 350M primary endpoint has a 97.5% interval [−0.00146,+0.00005] that includes zero; the compact study is payload-matched quality only and reports no latency. An earlier consensus-gated hybrid is actually worse than continuous on its separate bank (PPL 58.60 vs. 57.90). At matched storage, continuous retrieval also has better PPL, with exact access’s advantage being lower measured read cost on one GPU under teacher-forced evaluation. This is material because “exact access is a useful complement” is the paper’s main integrative claim, yet the combined-reader evidence is mixed, configuration-specific, and sometimes statistically unresolved.
Questions for authors
  1. For the projected hybrid, the 350M primary interval includes zero, and the compact hybrid has no latency measurement. Can you provide a single predeclared comparison with matched payload, matched evaluation bank, and measured reader/pipeline cost for hybrid vs. the strongest continuous control? Without this, the complementarity claim remains difficult to assess.
  2. The target-support decomposition is explanatory, and the exact and continuous policies use different gates. Can you provide an access-only intervention with fixed gates or fixed mixture weights to isolate how much of the gap is due to missing target support versus gate calibration? This would materially strengthen the causal interpretation of Section 5.
  3. The main from-scratch comparisons use three seeds and descriptive intervals, with several intervals containing zero. A preregistered primary endpoint with multiple-comparison control across settings would make the strength of the exact-access claim much easier to judge.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.