{"id":"a9143c7d-67c2-443a-be57-a1641f33ad59","arxiv_id":"2501.07905","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"Logarithmic Memory Networks are a new hierarchical-memory architecture claiming O(log n) attention, but the complexity math is internally inconsistent and the empirical evidence is a single small run.","lead":"This paper introduces Logarithmic Memory Networks, a sequence model that stores past tokens in a hierarchical tree and attends only to one summary vector per level. It claims O(log n) complexity and competitive loss versus GPT-2, which would matter for running long-context models on phones, but the paper's own equations undermine that claim.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's central O(log n) complexity claim is contradicted by its own architecture: the memory tensor [B, L, log L, E] and score tensor [B, L, log L] imply O(n log n) storage and attention cost, not O(log n).","rationale":"The reader's strongest_claim already identifies the O(n log n) contradiction, but the reader's weakest_assumption focuses on information loss in the linear summarizer. I see the complexity mismatch as the more fundamental problem: even a lossless summarizer cannot make the memory or score tensors O(log n) because their shapes are fixed by the construction. I therefore partially agree with the reader. I also flag §5.2's own admission that the complexity 'should ideally be O(log(n)^2)' as in-scope evidence; it directly weakens the subsequent O(log n) claim. The concrete test would verify actual resource scaling in the released code, although the analytical shapes make the result clear. Because the central advertised contribution—logarithmic memory and time—is not established, I would leave the REJECT verdict unchanged.","tokens_in":10120,"tokens_out":6746,"duration_ms":62237,"concrete_test":"Run the memory and inference-time benchmark in the released GitHub repository (or instrument the forward pass) for a fixed embedding size, batch size 1, and sequence lengths n = 2^10, 2^11, ..., 2^15 in parallel mode. Record peak allocated memory and per-layer FLOPs or wall time. If peak memory scales like n log n (roughly doubling plus a small factor when n doubles) rather than like log n (nearly flat on a log-log plot), the central O(log n) claim is refuted. The paper's own tensor shapes in §3.3.1 and §3.4 already predict this outcome.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and §5.2 promise a reduction from O(n^2) to O(log n) in memory and attention complexity. The architecture defined in §3 does not deliver that. Parallel memory construction (§3.3.1) returns a tensor of shape [B, L, log(L), E], so storing the memory is O(n log n). The single-vector attention (§3.4) computes scores of shape [B, L, log(L)] by multiplying Q with the first K vector and then sums V over the log(L) levels; per layer this is O(n log n) scalar operations, not O(log n). §3.7 gives the expander variant as O(k/2 · log^2 n), and §5.2 itself concedes 'the complexity should ideally be O(log(n)^2)' before asserting that focusing on the original token makes it O(log n). That assertion is a non sequitur: removing one log factor from a per-position cost does not remove the L factor from processing every position. Over a full sequence the total is O(n log n) (or O(n log^2 n) with the expander), regardless of whether the O(log n) claim is meant per token or total. The paper's advertised logarithmic scalability is therefore not supported by its own definitions; the correct headline would be subquadratic, not logarithmic. This is the load-bearing claim because the architecture's entire motivation is resource efficiency, and the experiments do not repair the complexity analysis.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Logarithmic Memory Networks (LMNs), a sequence model that stores past context in a hierarchical tree built by repeatedly summarizing pairs of adjacent node embeddings with a linear projection. It introduces a single-vector attention mechanism that scores the log L memory levels of each position, plus parallel (training) and sequential (inference) construction modes, optional multi-bank memory, and an expander variant. The advertised contribution is reducing attention memory and computation from O(n²) to O(log n) while remaining competitive with GPT-2; the experiments compare loss on Tiny Shakespeare and benchmark inference time and memory against standard attention.","tokens_in":10471,"tokens_out":8937,"duration_ms":84171,"significance":"The central promise—a logarithmic-complexity attention mechanism with competitive accuracy—would be practically significant for resource-constrained long-sequence modeling, and the accompanying MIT-licensed code is a concrete asset. However, the paper's own architectural definitions imply O(n log n) storage and attention cost rather than O(log n), so the headline result is not established. The empirical evaluation is a single run on one small dataset with no error bars, and the quality claims on retrieval and compression rest on unverified assumptions. The architecture is simple and falsifiable, but the paper as written does not substantiate scalable logarithmic behavior.","major_comments":[{"comment":"The advertised O(log n) complexity is contradicted by the paper's own definitions. Parallel memory construction returns a memory tensor of shape [B, L, log(L), E], so storing the memory is Θ(n log n) entries, not Θ(log n). Single-vector attention computes scores of shape [B, L, log(L)] and then a weighted sum over the log(L) levels, so the attention cost per layer is Θ(n log n) operations. The expander variant in §3.7 is stated as O(k/2 · log² n), and §5.2 itself concedes 'the complexity should ideally be O(log(n)^2).' The argument that focusing on the original token removes one log factor does not remove the L factor from processing every sequence position. The correct characterization is subquadratic (n log n, or n log² n with the expander), not logarithmic, and this affects the validity of the compression ratios reported in §5.2.","section":"§3.3.1, §3.4, §5.2"},{"comment":"The retrieval mechanism depends on two unexamined assumptions: that a single linear projection of two concatenated E-dimensional nodes is a sufficiently lossless summary for all future retrievals, and that the first vector of K at each position is an adequate query for all log(L) memory levels. The first assumption is load-bearing because every higher tree level is a further compression of an already lossy summary; the paper offers no information-theoretic bound, no ablation varying the summarizer, and no experiment that isolates compression loss. The second assumption is load-bearing for the 'single-vector attention' claim; without an ablation or analysis, the model's capacity to retrieve long-range dependencies is not established. Section 3.4 also does not specify how the single-vector attention performs cross-position retrieval, since the score tensor has shape [B, L, log(L)] rather than [B, L, L].","section":"§3.3, §3.4, §6"},{"comment":"The empirical support is too thin for the paper's conclusions. Table 1 reports one training run per configuration, with no seeds, no error bars, and a single dataset (Tiny Shakespeare) trained for only 5,000 steps; statements such as 'LMNs ... outperform it' in §5.1 are not justified at this scale, especially since parameter counts are not closely matched (LogMem has 1,072,193 parameters versus GPT-2's 841,281 at embedding size 128). The inference-time and memory benchmarks in §5.3 do not report error bars, the number of repetitions, or the exact attention implementation being compared. The 'compression factor' arithmetic in §5.2 is a restatement of the claimed asymptotic complexity, not a measured overhead reduction, so it cannot compensate for the missing benchmarking details.","section":"§5.1, §5.3"}],"minor_comments":[{"comment":"Equations (1) and (2) are dimensionally confusing: the values are ratios, not percentages, and for n=1024 the ratio is 104,857.6, not 1,048,576%; please state the exact formula and use percentage notation correctly.","section":"§5.2"},{"comment":"The notation log2(n) in §3.7 and log(n)^2 in §5.2 is ambiguous: specify whether this means (log n)² or log to base 2, and state whether the expansion factor k and bank count are treated as constants or as terms in the asymptotic expression.","section":"§3.7, §5.2"},{"comment":"The bullet 'Reduce Parameters' is not part of the attention mechanism and interrupts the description; it should be moved to the experimental or architecture-parameter sections. The claim that it 'outperforms GPT-2' with half the parameters is not supported by Table 1 as presented.","section":"§3.4"},{"comment":"Several references are misattributed or appear unverifiable. For example, [20] is listed as 'Mamba: A memory-augmented model for sequence-to-sequence learning,' but the known Mamba paper is titled 'Mamba: Linear-Time Sequence Modeling with Selective State Spaces'; [3], [4], [21], [22], and [24]–[28] also need verification against actual published venues.","section":"References"},{"comment":"The paper states the tree depth as log(L) without specifying the base or the handling of non-power-of-two sequence lengths, and the phrase 'the first vector of K which is the current token' is ambiguous in parallel mode where all positions are processed simultaneously; please clarify the indexing and the causal masking applied to the scores.","section":"§3.3.1, §3.4"},{"comment":"There is a grammatical slip in the phrase 'A Logarithmic Memory Networks is proposed'; it should be 'Logarithmic Memory Networks are proposed.'","section":"§1"}],"recommendation":"reject","confidential_remarks":"The central complexity claim is contradicted by the architecture's own tensor shapes, and the experiments are far too limited to establish the performance claims. Even with a corrected O(n log n) analysis and expanded experiments, the paper would need substantial restructuring of its abstract, title, and motivation; I do not see a path to acceptance within the current scope. The reference list also contains several entries that do not match known publications, which warrants editorial checking."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline claim in the abstract—attention reduced from O(n²) to O(log n)—does not survive contact with the paper's own definitions. The memory tensor is [B, L, log L, E], the score tensor is [B, L, log L], so storage and per-layer attention cost are O(n log n), not O(log n). The expander variant is O(log² n), and §5.2 concedes as much before hand-waving that focusing on the original token removes a factor. That is a non sequitur: dropping one log factor from a per-position cost leaves the L factor across positions untouched.\n\nWhat is genuinely here: a concrete, code-backed architecture that puts together hierarchical pooling, single-vector attention over one key per level, and parallel-training/sequential-inference modes. That combination is not in the cited references, and the sequential mode is a sensible way to reuse memory at inference. The idea that tree paths encode relative position is worth a closer look. The author releases code on GitHub and runs small-scale comparisons on Tiny Shakespeare; that is real effort.\n\nThe soft spots are serious. The complexity error is load-bearing; the entire motivation is resource efficiency, and the advertised logarithmic scaling is false. The experiments are a single run on one tiny dataset with no error bars, so they cannot support the 'competitive with GPT-2' framing. The Mamba citation is wrong: reference [20] is a 2020 paper with a different title, not the Mamba SSM. Related work misses earlier hierarchical and memory-compressed transformers, which weakens the novelty case. And the assumption that a linear map from 2E to E can faithfully summarize a pair is untested; there is no ablation isolating compression loss.\n\nWho is this for? Someone looking for subquadratic attention variants for edge deployment might skim the architecture and the code. But the paper as written would mislead a casual reader: the central claim is internally contradicted. I would not send this to peer review in its current form. A rewrite that claims O(n log n) or O(n log² n), adds error bars and real baselines, and fixes the citations could make it a legitimate submission. As is, it is a good idea in need of an honest complexity analysis and a lot more evidence.","headline":"The O(log n) claim is false on the paper's own tensor shapes; the architecture is a plausible subquadratic hybrid, but the headline doesn't hold and the evidence is too thin.","tokens_in":10939,"tokens_out":3224,"would_cite":false,"duration_ms":27928,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Log-tree memory cuts attention cost from O(n^2) to O(log n)","keywords":["logarithmic memory networks","hierarchical tree memory","single-vector attention","long-range sequence modeling","resource-constrained environments","computational complexity","positional encoding"],"falsifier":"Train LMNs on a task that requires exact recall of a specific earlier token (e.g., a copy task on a sequence of length 2^k), then probe the memory tree at the highest level with a linear classifier; if the classifier cannot recover which token occupied a given position, the linear summarizer has destroyed information the attention mechanism cannot restore. Alternatively, benchmark memory growth as sequence length doubles: if the tensor is [B, L, log(L), E], measured peak memory will grow faster than O(log L), contradicting the headline claim.","tokens_in":9898,"feed_emoji":"🌳","tokens_out":5318,"duration_ms":50151,"temperature":0.7,"pith_summary":"This paper proposes Logarithmic Memory Networks (LMNs), a sequence model that replaces the quadratic self-attention of Transformers with attention over a hierarchical tree of memory summaries. The claim is that storing past context in a logarithmic tree and reading it with a single-vector attention operation reduces computational complexity and memory footprint from O($n^{2}$) to O(log n), while staying competitive with GPT-2 on language modeling. The significance, if the claim holds, is that long-range sequence modeling could run on mobile and edge devices where quadratic attention is infeasible. The model also removes explicit positional encodings by letting tree paths carry position information.","feed_headline":"Log-tree memory cuts attention cost from O(n^2) to O(log n)","feed_subtitle":"A hierarchical tree of summaries plus single-vector attention could bring long-range models to phones.","key_machinery":"The central machinery is the logarithmic tree memory plus single-vector attention. The summarizer layer defines the tree: for each pair of nodes at level i, it concatenates the two vectors of dimension E and applies a linear projection back to dimension E, so every parent node is a trained compression of its two children. Single-vector attention reads only the first vector of K (the current token) against every level of the memory, yielding log(L) scores per token, and then weights the value vectors by those scores. A path-through positional encoding emerges because a token's route up the tree—or its binary position in sequential construction—is implicitly stored in the summaries. The expander summarizer optionally adds slots at deeper levels via a 1D transposed convolution to mitigate information loss at high compression.","core_discovery":"Logarithmic Memory Networks are a hierarchical memory architecture. The lowest level of the tree is the token sequence; each higher level is produced by a summarizer layer that takes two adjacent nodes and linearly projects their concatenation into a single node. The resulting memory tensor has shape [B, L, log(L), E]. Attention is then computed only against the first vector of the key tensor—the current token—producing scores of shape [B, L, log(L)], which the paper argues gives O(log n) attention cost. The memory construction runs in parallel during training and sequentially during inference, where the sequential mode acts as a recurrent memory with a small footprint. The paper reports that on the Tiny Shakespeare benchmark, LMNs with roughly GPT-2's parameter count yield lower training and validation loss than GPT-2, and that inference time and memory usage stay flat as sequence length grows, whereas standard attention degrades.","pith_inferences":["The paper's O(log n) complexity claim does not follow from its own definitions: the memory tensor is [B, L, log(L), E], so storage is O(n log n), and computing scores requires O(n log n) operations; an honest accounting would compare O(n log n) attention against quadratic attention, which is still a large improvement but not the claimed complexity.","The summarizer's linear projection from 2E to E is the capacity bottleneck: if two distinct pairs of nodes can map to the same vector, then the memory cannot distinguish certain histories, and attention has no way to recover the lost distinction. A copy-recall probe would reveal how many bits of an original token survive after k levels of summarization.","The dual-mode equivalence between parallel and sequential construction is asserted but not proven; checking that both modes produce identical memories for the same input would test whether inference really matches training behavior."],"forward_implications":["Sequences of tens of thousands of tokens become processable on memory-limited hardware, since the per-token memory and compute grow only with log(L) in the paper's accounting.","Positional encodings become unnecessary, simplifying the architecture and removing an extra hyperparameter.","The dual-mode execution allows GPU-parallel training while keeping inference as a lightweight recurrent-style memory update.","At matched parameter counts, LMNs report better training and validation loss than GPT-2 on the tested small-scale language modeling task."],"supporting_citations":[{"why":"GPT-2 is the baseline the paper compares losses and parameters against.","marker":"[11]"},{"why":"Defines the quadratic self-attention whose complexity LMNs claim to reduce from O(n^2) to O(log n).","marker":"[9]"},{"why":"Transformer-XL is the recurrence-based long-range variant LMNs position themselves against.","marker":"[12]"},{"why":"Longformer is a sparse-attention baseline serving as a point of comparison for long-sequence efficiency.","marker":"[13]"},{"why":"Linformer is the linear-complexity attention baseline that LMNs aim to improve upon for resource-constrained settings.","marker":"[14]"}],"fun_headline_variants":["Log-tree memory shrinks attention cost from O(n^2) to O(log n)","Hierarchical summary tree gives O(log n) attention for long sequences","LMNs: Parallel training, sequential inference, logarithmic memory","Single-vector attention on a log-tree: long-range without heavy memory","O(log n) attention via hierarchical tree — ideal for phones and IoT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The architecture's usefulness rests on the premise that a single linear projection of two concatenated node vectors can preserve enough task-relevant information at every tree level, so that the hierarchical memory is a faithful summary rather than an uncontrolled compression; the paper offers no bound, ablation, or experiment that directly tests this compression fidelity.","fun_headline_variants_meta":{"raw":{"variants":["Log-tree memory shrinks attention cost from O(n^2) to O(log n)","Hierarchical summary tree gives O(log n) attention for long sequences","LMNs: Parallel training, sequential inference, logarithmic memory","Single-vector attention on a log-tree: long-range without heavy memory","O(log n) attention via hierarchical tree — ideal for phones and IoT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000383,"raw_usage":{"total_tokens":2029,"prompt_tokens":944,"completion_tokens":1085,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":990}},"tokens_in":560,"tokens_out":1085,"duration_ms":10090,"temperature":1.0,"reasoning_tokens":990,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:29:46.780444+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train LMNs on a task that requires exact recall of a specific earlier token (e.g., a copy task on a sequence of length 2^k), then probe the memory tree at the highest level with a linear classifier; if the classifier cannot recover which token occupied a given position, the linear summarizer has destroyed information the attention mechanism cannot restore. Alternatively, benchmark memory growth as sequence length doubles: if the tensor is [B, L, log(L), E], measured peak memory will grow faster than O(log L), contradicting the headline claim.","supporting_citations":[{"cited_title":"Improving language under- standing by generative pre-training,","cited_arxiv_id":null,"evidence_quote":"GPT-2 is the baseline the paper compares losses and parameters against."}],"review_version":1}