Bounded-Memory

Follow this topic Ask about this topic

Momentum

10 papers in the last four weeks, up 100% on the four weeks before. 0.1% of all new papers.

Jul 6Week of Sep 21

Latest papers 47

Sep 30, 2026cs.DS

Component-Weighted Centroid Search for Exact Incremental BPE

Exact incremental BPE maintains the canonical tokenization state after every appended byte. The recent algorithm of Jiang and Gong (2026) does this in

O(\log^2 t)

worst-case time, where

t

is the maximum canonical token length. Its centroid search visits

O(\log t)

components and can pay another

O(\log t)

for ordered point location at each one. Within Jiang and Gong's normalized/proper merge-stage model, we change only that local search. Each interval is weighted by the size of the recursive component it selects, so a move from size

m

to size

m'

costs

O(1+\log(m/m'))

. These charges telescope, giving

O(\log t)

time per append and

O(n\log t)

over an

n

-byte stream, with the same BPE semantics and asymptotic space. We also construct a normalized proper BPE family over a fixed alphabet where count-balanced search uses

Θ(\log^2 t)

probes on a reachable update, while the weighted search uses

Θ(\log t)

. A Rust implementation matches the predicted probe counts on every tested instance. On ordinary vocabularies the queried degrees are small, however, and the improvement is a worst-case guarantee rather than an average-speed result.

Harshit Verma, Rex Ying

Yale University

Byte-Pair Encoding Bounded-Memory O(\Bar{K}\Log N)$

Sep 30, 2026cs.LG

Low-Discrepancy Dither for Quantized Recurrent State Caches

Mamba-style and hybrid language models compress their past into a fixed-size recurrent state that is rewritten at every generated token. Storing this state in low precision saves memory bandwidth, but every rounding error is fed back into the next update and can accumulate over long generations. Production systems round the state stochastically; we ask which rounding rule such caches should use. We find that a deterministic golden-ratio Weyl dither, which needs no random numbers, consistently brings the quantized model closer to the full-precision one than stochastic rounding, across pure and hybrid models, storage formats, and long decoding horizons, at no extra cost. Round-to-nearest behaves differently: because it discards small updates, its error keeps growing, so it can look best in short evaluations yet falls far behind over long generations. A discrepancy analysis explains this ordering, and we document implementation pitfalls that silently remove the benefit.

Snigdha Chandan Khilar

Independent Researcher

Recurrent State Bounded-Memory Cache

Sep 30, 2026cs.AI

What Should an Agent Remember? Disentangling Retention from Retrieval in Bounded-Memory Evaluation

A persistent agent must decide both what to retain as information arrives and what to surface once a query appears, yet memory evaluations can confound these decisions by comparing methods that differ in both retention and selection. We build a streaming-recall benchmark crossing retention and selection rules and evaluate every condition on the same 300 seeded episodes. Holding access fixed, query-aware selection improves required-fact recall by 15.5 percentage points (95% CI: 12.8 to 18.2), whereas a mixed comparison that also changes history access reports a 68.7-point advantage, of which 53.2 points are attributable to access. Under bounded retention, query-aware, dense, and oracle selection reach the retention ceiling, and all 319 observed failures in the bounded recency condition are caused by eviction rather than ranking errors. Recall falls to 0% as targets recede sufficiently far into the past. Repeating the evaluation on SQuAD preserves the retention ceiling while showing that dense retrieval can outperform lexical retrieval on natural text. These results show that bounded-memory evaluations should hold access fixed and report retention and selection separately.

Juli Huang

Stanford University

Retention Bounded-Memory Alignment-Aware Selection Persistence Streaming

Sep 29, 2026cs.AI

MemEvo: Automatic Discovery of Streaming Video Memory Mechanisms

Query-agnostic streaming video understanding requires vision-language models to continuously compress an indefinitely growing visual stream into a bounded memory before future queries are known. The performance depends critically on the memory mechanism--what observations to preserve, how to represent and consolidate them, and what information to retrieve when a query eventually arrives. Rather than designing a single memory architecture by hand, we formulate memory design as a search problem over executable memory programs. We introduce a lightweight domain-specific language that expresses memory mechanisms through structured primitives for representation, admission, retention, consolidation, budgeting, and retrieval, while enforcing causal and bounded-memory constraints. Although structured, the derived program space remains large and contains heterogeneous, conditionally dependent design choices whose effects can only be assessed via downstream execution. We therefore propose MemEvo, an LLM-driven auto-research framework that uses pretrained LLM as a semantics-aware proposal model to iteratively generate and refine candidate memory programs based on accumulated experimental feedback. At runtime, a deterministic evaluation pipeline validates and evaluates each candidate, while the underlying vision-language model remains frozen throughout discovery. We finally produce a training-free, bounded-memory mechanism. Extensive experiments on StreamingBench and OVO-Bench demonstrate strong streaming video understanding performance together with substantial context and inference efficiency.

Guohong Liu, Jialei Ye, Shanhui Zhao +2

Institute for AI Industry Research, Tsinghua University · Peking University

Streaming Video Understanding Bounded-Memory Visual Memory Peak Memory Memes

Sep 29, 2026cs.AI

BRIDGE: Bilevel Retrieval-Credit-Aware Agentic Reinforcement Learning

Agentic reinforcement learning (ARL) with verifiable rewards improves the ability of large language models (LLMs) to tackle knowledge-intensive tasks by learning to interleave search and reasoning. However, most existing ARL methods optimize only LLM-generated tokens and treat retrieved evidence as environment observations. This creates an information-credit gap: failures caused by missing or misleading evidence are attributed to the LLM policy rather than to the retriever, which motivates training the LLM and the retriever jointly. In this paper, we show that retrieval and LLM policy learning are order-sensitive: adapting the retriever before optimizing the policy yields a larger reward gain than the reverse order. To preserve this hierarchy while allowing both components to co-adapt, we formulate retrieval-augmented agentic RL as a bilevel optimization problem. To solve it efficiently, we introduce BRIDGE, a memory-efficient first-order bilevel method motivated by a loss-landscape analysis of the RL and retrieval objectives. Across seven open-domain QA benchmarks, BRIDGE achieves the highest average accuracy with both 3B and 7B backbones, improving the multi-hop average over the strongest baseline by 9.6 and 3.4 EM points, respectively. It also achieves the best averaged answer accuracy and reasoning quality across medical QA benchmarks.

Quan Xiao, Mingda Liu, Gaowen Liu +2

Department of Electrical and Computer Engineering, Cornell University · Institute of Integrated Research, Institute of Science Tokyo · Cisco Research

Agentic Reinforcement Learning Large Language Model Policy Optimization Bounded-Memory Bridge

Sep 28, 2026cs.LG

SANTA++: Sampling Attention through Representative Keys

Attention often concentrates on a small subset of tokens in the context, but which subset matters changes from one query to the next. To exploit this changing structure, we introduce SANTA++, a training-free stochastic attention method that uses representative keys for memory-efficient selection without scanning the entire key-value (KV) cache. Cached keys are organized into teams, and the query scores one representative from each team to decide which teams to sample. We compute exact attention scores within the sampled teams and reweight each team's contribution by the inverse of its inclusion probability. This importance sampling correction estimates attention over the full cache, with a sampling budget that lets us trade memory reads for accuracy. Remarkably, with 32 or 64 sampled teams, SANTA++ uses 16% to 22% of dense attention's KV reads and retains 94% to 99% of the dense-attention baseline's scores on LongBench v2 and HELMET's retrieval-augmented generation subset, and 85% to 91% on RULER, with Qwen2.5-7B-Instruct at 32K context. With 31 sampled teams, our GPU implementation delivers a

1.69\times

attention speedup over the dense FlashAttention baseline at 32K context. By reducing the number of cache entries read, SANTA++ in principle complements architectures with compressed KV representations, such as multi-head latent attention. Our kernels are available at: https://github.com/OPUSLab/santapp-kernel-demo.git.

Kyle Lee, Christian Z. Pratt, Ruoyu Fang +4

Department of Electrical and Computer Engineering University of California, Santa Barbara, CA, USA · Flucta, San Francisco, CA, USA

Dynamic Sparse Attention Bounded-Memory Decode Speedup

Sep 28, 2026cs.AI

ReplayLens: Auditing Agents' Use of Outcomes

When an agent reuses logged experience, a changed decision may reflect the recorded score, the action's name, or the record's position in storage. Standard memory evaluations do not reveal which relationship drives that change. We introduce ReplayLens, a black-box audit that changes one relationship in the stored history at a time, holds the remaining interface fixed, and measures the resulting decision. Four interventions target four relationships. Outcome reassignment swaps which scores belong to which actions. Pair transport moves intact action-score pairs to new record slots. Consistent renaming relabels actions in both history and menu. Key-slot reassignment changes both score attachment and position. A constructive separation shows why the audit is needed: two memory writers with identical endpoint accuracy respond differently to the same replay, so conventional evaluation cannot resolve the underlying dependence. On black-box LLM interfaces, swapping scores changes decisions while moving intact pairs does not, separating score attachment from record order. A bounded-memory study exposes ingestion-order sensitivity that endpoint comparison misses. In sequential experiment planning, altered historical scores redirect exploration and reduce final utility despite fresh measurements. A code-debugging agent with sealed hidden tests shows the same pattern outside model selection. ReplayLens provides a relationship-level audit for deciding whether logged experience can be merged, reordered, or reindexed safely.

Dong Xu, Zhangfan Yang, Jiantao Wu +5

School of Artificial Intelligence, Shenzhen University · EasternDawn · School of Computer Science, University of Nottingham Ningbo

Replay Interaction History Model Auditing Bounded-Memory Conceptual Reorganization

Sep 27, 2026cs.LG

When to Evict, Not What to Keep: Draft-Guided Eviction for Training-Free KV-Cache Compression

Training-free KV-cache compression methods such as SnapKV, H2O, and PyramidKV evict tokens at the end of prefill, aiming to preserve the attention mass that future queries are expected to use -optimizing what to keep. We show that this objective fails in two distinct ways. (1) Compensation: restoring the evicted attention mass can recover the attention-level target without recovering task quality. (2) Selection: covering more of the true decode-query mass can hurt quality when the recovered mass is fragmented rather than concentrated in coherent spans. These failures share a common cause: eviction occurs before the queries that determine the answer trajectory exist. We propose Draft-Guided Eviction (DGE), which defers eviction until after drafting the first k=2 answer tokens using the full cache - just one decode step beyond prefill. Because the draft is generated from the answer's own prefix, no cache entries are discarded before this trajectory signal becomes available. The per-head cache budget remains unchanged, and DGE can be applied directly to SnapKV, PyramidKV, H2O, and StreamingLLM without modifying their eviction scores. Unlike extra-pass methods, DGE changes when eviction occurs rather than what cache entries are selected. Extensive experiments demonstrate that DGE outperforms prior methods at every evaluated budget on five of six instruct-tuned backbones, achieving 44.2 on LongBench, nearly matching FullKV at 44.3. The timing-only control DGE-W achieves the same score, demonstrating that the gain comes from when eviction occurs rather than what is selected - an effect we term trajectory anchoring.

Haeyong Kang, Chang D. Yoo

Duksung Women’s University · KAIST

Eviction Key-Value Cache Compression Bounded-Memory Data Compression Methods

Sep 23, 2026cs.CV

DeltaS: Reading the Gated Linear Attention State for KV Cache Eviction in Streaming Video

Recent video-language models increasingly adopt hybrid architectures that interleave linear and full attention layers for efficient long-context processing. While the recurrent state of linear attention remains fixed in size, the KV cache of full attention continues to grow with the video stream, making eviction necessary under a bounded memory budget. The key challenge in streaming is that eviction must occur before the question arrives, so what to retain has to be decided without the question. Existing eviction methods derive token scores from the KV cache itself, using position, attention, or key-value representations, and attention-based scores further require proxy queries or extra computation. Hybrid backbones offer another source of signal. In gated-delta linear attention, the recurrent state is updated by the residual between each input and what can already be retrieved from the state, so its change over a chunk of frames reflects how much new information the chunk brings. We propose DeltaS, a query-agnostic, training-free method that retains video chunks inducing larger normalized state change, or state drift. In a controlled comparison with the budget and retention policy held fixed, state drift outperforms position-, attention-, and key-value-based signals. With a signal costing only 1.9% of the forward pass, DeltaS surpasses the strongest query-agnostic bounded-memory baseline by 2.1 points on average across six long-video benchmarks and by 5.6 points on the longest benchmark. These results suggest that the two memories of hybrid architectures can work cooperatively. Code is available at https://github.com/MaumAI-Company/DeltaS.

Taeyoun Kwon, Seungjin Kim, Hyeonyu Kim +1

Maum AI Inc. · Seoul National University · Yonsei University

Kimi Delta Attention Linear Attention Streaming Video Key-Value Cache Eviction Bounded-Memory Long-Video Benchmarks+2

Sep 23, 2026cs.CL

MORSE: Multi-Context Ordering via Reverse Scoring for Evidence-Preserving Compression

Retrieval-augmented generation often relies on multiple retrieved contexts that contain substantial redundancy, motivating context compression to preserve useful information under limited input budgets. Likelihood-based compressors can account for cross-context redundancy through sequential scoring, but this makes evidence scores dependent on context order. We show that permuting the same contexts under an unchanged compressor can substantially change which supporting evidence survives compression. We attribute this sensitivity to information preemption: earlier, partially relevant contexts can absorb credit for shared information, reducing the incremental scores of later, stronger evidence and increasing its risk of removal. Controlled pair-swap interventions provide direct empirical support for this mechanism by showing that placing stronger evidence before overlapping, partially relevant contexts can improve its survival. Based on this insight, we introduce MORSE, a compression-aware method for evidence-preserving context ordering. MORSE uses reverse query likelihood to construct an evidence-first anchor and to evaluate compressed candidate outputs, enabling compression-aware selection among alternative permutations. Across multi-hop Question Answering (QA) benchmarks, compression procedures, budgets, and scoring models, MORSE improves evidence retention over reverse ordering and generally outperforms matched random search, with downstream QA gains. Our code is available at https://github.com/tbn5pj/MORSE_code

Ke Wan, Yifan Wang, Liheng Lai +1

Department of Computer Science University of Virginia Charlottesville, VA, USA · AfterQuery

Data Compression Methods Bounded-Memory Scoring

Sep 22, 2026cs.AI

CliffCompaction: Cost-Efficient Compaction for Long-Horizon Coding Agents

Agents often work on complex problems that require millions of tokens of context, which necessitates compacting across sessions due to limited context windows. We develop CliffCompaction, an autocompaction technique that reduces cost by up to 50% under a bounded context while maintaining or improving performance on Terminal-Bench and achieving new levels of efficiency for test-time scaling and state-of-the-art results on KernelBench. The per-rollout savings of CliffCompaction make the performance--cost trade-off of test-time scaling more efficient, adding over 10 percentage points on Terminal-Bench for less than the cost of two full-context runs. Under parallel test-time scaling, CliffCompaction lets Kimi K2.6 match Opus 4.7, and exceed Opus 4.6 and GPT-5.3 Codex at lower cost. The key to CliffCompaction's effectiveness is that it keeps compacted information faithful by only truncating or dropping content, never rephrasing or rewriting it. We never compact a compaction---each pass operates only on original content, and prior compacted output is discarded, preventing context drift from accumulating. These properties sustain continual learning over sessions exceeding a million tokens: on KernelBench, CliffCompaction reaches CUDA kernel speedups of

2.23\times

after 200 steps and

3.58\times

after 400 steps, surpassing specialized search algorithms and trained agents despite being a general-purpose compaction technique. We open-source a scaffold-agnostic API-proxy implementation of CliffCompaction usable with Claude Code, Codex and other harnesses.

Trang Nguyen, Eulrang Cho, Bingqing Chen +1

Carnegie Mellon University · Bosch Center for AI

Compaction Bounded-Memory Test-Time Scaling Continual Learning

Sep 22, 2026cs.LG

Beyond Class Marginals: Bounding Rehearsal Gaps without Freezing Class Co-occurrence

Class-balanced replay controls class frequency but does not determine the interval between successive replay appearances of a class. We study this interval, the rehearsal gap, separately from the class marginal and class co-occurrence, and introduce randomised-pass replay (RPR), which visits each resident class once per shuffled pass. For a fixed set of C resident classes and replay batch size b less than or equal to C, RPR preserves the balanced time-averaged class marginal and bounds every gap by 2*ceil(C/b)-1; a churn-conditional bound applies while the resident set changes. The scheduler uses no future class information and adds no replay examples or forward passes. In a linear-head ER-ACE diagnostic, joint absence from the incoming and replay batches produces a one-sided classifier-bias gradient. Longer absence episodes are associated with larger negative bias displacement, and removing the incoming-loss mask attenuates the scheduling effect. In the primary ER-ACE experiments, RPR improves final average accuracy by 0.72-1.67 percentage points relative to independent class-balanced retrieval under reservoir storage, with positive effects also observed under balanced storage. Pretrained ViTs show positive effects on the tested LT10 streams with small replay batches, while matched larger-batch controls show no material effect. Fixed-cycle and reused-pass controls change more than one temporal statistic, so the experiments do not isolate rehearsal-gap length from all other forms of temporal dependence. The accuracy effects depend on the learner and operating regime.

Congren Dai, Nat Roongjirarat, Fei Ye

Imperial College London · King’s College London · University of Electronic Science and Technology of China

Layer-Selective Rehearsal Strategy Deterministic Replay Precision Recall Bounded-Memory Scale Gap Token Co-Occurrence Graphs

Sep 14, 2026cs.LG

Temporal Recurrence Favors Fewer Layers

In streaming tasks, recurrent models can carry latent computation across time, allowing each update to build on representations produced earlier. This raises a basic question: once temporal recurrence provides sequential computation across steps, how much depth is still needed within each step? Prior work has shown that recurrence can make shallow models competitive. We instead study this question as a compute-allocation problem, varying within-step depth, expert width, and the number of parallel experts per layer across several compute budgets. For each budget, we compare the best observed recurrent and non-recurrent allocations and the performance they achieve under approximately matched per-step computation. Across Sokoban and autoregressive FineWeb language modeling, we find that temporal recurrence shifts the best observed compute allocation toward substantially fewer layers, with comparable or better performance.

Ivan Anokhin, Johan Obando-Ceron, Irina Rish +1

Mila – Qu´ebec AI Institute · Universit´e de Montr´eal · Sakana AI

Recurrent Model Recurrence Circuit Depth Layer-Wise Bounded-Memory

Sep 11, 2026cs.SD

Sparse Weight and Edge Circuit Discovery in Transformer-based Acoustic Models

Transformer-based foundation models are powerful but opaque, motivating Mechanistic Interpretation methods to uncover the black-box by identifying small computation subgraphs responsible for a task. DiscoGP is a joint weight-and-edge circuit discovery framework originally developed for text decoders. We extend DiscoGP to speech encoders and present, to our knowledge, the first circuit discovery study for modern speech foundation models. Across HuBERT and Wav2Vec 2.0 on several speech classification tasks, we find that the discovered circuits are extremely compact, yet often match or even exceed the performance of the full pretrained encoder with the same downstream head. Through ablations, we show that these circuits reflect pretrained computation rather than random structure or task-head artifacts. We also introduce a memory-efficient DiscoGP variant that reduces the GPU memory cost of edge-circuit discovery at runtime from quartic to cubic. Overall, our results broaden Mechanistic Interpretation beyond text decoders and show that circuit-level analysis can reveal both explanatory structure and unexpected functional behavior in speech encoders.

Jiankun Wei, Ewan Dunbar, Gerald Penn

Department of Computer Science University of Toronto Toronto, Canada

Transformer Encoder Neural Audio Encoders Circuits Bounded-Memory

Sep 1, 2026cs.LG

Superposed Latent Autoencoder

Autoencoders typically meet tight latent-memory budgets by making each latent representation smaller, sacrificing representational capacity. We ask a different question: can multiple wider latents be stored together instead? We introduce the Superposed Latent Autoencoder (SLAE), which preserves high-capacity latent representations while sharing storage through learned superposition. SLAE transforms latents into storage-friendly codes, binds them with randomized keys, superposes multiple codes into a single memory tensor, and learns to recover each latent before decoding. Under the same storage budget, SLAE replaces irreversible dimensional bottlenecks with structured interference that can be suppressed. Across CIFAR-10/100, SVHN, STL-10, Tiny ImageNet, and a wide range of memory budgets, SLAE substantially improves the reconstruction--memory tradeoff, reducing reconstruction error by up to 56% over conventional autoencoders at matched storage. Further analysis shows that SLAE's advantage comes from making wider representations usable under the same storage budget. These gains also extend beyond reconstruction: the information preserved by SLAE improves downstream classification by up to 16.79 percentage points under the same memory budget. Our results suggest a new principle for representation compression: instead of making every latent smaller, keep representations wide and let them share memory.

Quanling Zhao, Jiaying Yang, Tianqi Zhang +4

University of California San Diego · Georgia Institute of Technology · University of California Riverside +1

Autoencoder Architectures Future Latent Representations Conditional Variational Autoencoder Bounded-Memory

Aug 31, 2026cs.CV

StreamScout: Learning When to Look Deeper for Streaming Video Understanding

Streaming video understanding requires answering questions that arrive at arbitrary moments over an unbounded video stream. Existing systems primarily focus on what to retain in a bounded memory, yet access that memory using the same fixed-cost procedure for every query, despite substantial variation in the evidence required. We argue that deciding how deeply to access memory for each query is as important as deciding what the memory should store. To this end, we introduce StreamScout, an adaptive inference framework that maintains only a lightweight textual timeline in context as the stream unfolds. At query time, StreamScout progressively augments the timeline with up to three increasingly informative visual views: a glance at recent frames, a uniform look-back over the past stream, and query-salient retrieval. At each stage, the model answers immediately if the available evidence is sufficient; otherwise, it escalates to the next view. To improve this stop-or-escalate policy, we probe the cascade on an auxiliary set and distill the model's empirical competence boundary into supervision for a lightweight LoRA adaptation, yielding StreamScout-S. We further refine the policy through reinforcement learning, allowing the model to explore stopping behaviors beyond imitation of the distilled decisions, yielding StreamScout-R. Across three backbones and three streaming benchmarks, StreamScout and its variants consistently outperform prior streaming methods while substantially reducing inference cost and token consumption; on OVO-Bench, for instance, StreamScout-S improves Qwen3-VL-8B by 14.65 points while using 59% fewer tokens than uniform sampling and answering in 1.04 s on average.

Ce Zhang, Jing Bi, Jinxi He +9

Carnegie Mellon University · TikTok · University of Rochester +2

Streaming Video Understanding Bounded-Memory

Aug 31, 2026cs.LG

DASC: Decay-Aware State Compression for Hybrid Linear-Attention Serving

Hybrid linear-attention architectures have recently scaled to large open-weight models, offering quality competitive with full attention while substantially reducing key/value (KV) cache growth. However, their in-place recurrent-state updates complicate cache management: prefix reuse requires state checkpoints alongside full-attention KV, while storing state checkpoints in full increases memory pressure, leading to more evictions and repeated prefill. By analyzing the decay structure of Gated DeltaNet (GDN) and Kimi Delta Attention (KDA), we find that different heads and channels retain prefix information over markedly different timescales, which we term \emph{retention horizons}. This variation suggests substantial compression potential in persistent state checkpoints. Building on this observation, we introduce \emph{Decay-Aware State Compression} (DASC), which derives retention horizons from model weights, selects long-horizon state units, and packs them into a ragged state checkpoint layout. To integrate efficiently with tensor-parallel inference engines, DASC furtherly balances compressed state checkpoints across TP ranks. On reuse, DASC either zero-fills omitted units or refreshes them from a bounded suffix with additional compute cost. Across retrieval and end-to-end reasoning benchmarks on Kimi-Linear, conservative DASC configurations remain close to full caching while compressing KDA recurrent state checkpoints by

2.63\times

. Under fixed state checkpoint memory budgets, the resulting capacity gains reduce mean Time to First Token (TTFT) by 42.6% and improve input throughput by 68.4%. At larger compression ratio, suffix refresh recovers much of the accuracy lost to more aggressive omission, at the cost of additional replay computation. Qwen with GDN exhibits a similar quality--efficiency trend, showing that DASC extends from channel-wise KDA to head-wise GDN.

Yanqi Yu, Pingwei Sun, Jianchao Tan +4

East China Normal University · Meituan · South China University of Technology

Kimi Delta Attention Recurrent State Gated Deltanet Bounded-Memory

Aug 16, 2026cs.LG

SubZero+: Memory-Efficient Adaptive Zeroth-Order LLM Fine-Tuning in Random Subspaces

Zeroth-order (ZO) optimization with SGD in random subspaces enables memory-efficient fine-tuning of large language models without backpropagation. However, high gradient estimation noise fundamentally undermines adaptive optimizers like Adam. We propose SubZero+, which achieves practical adaptive ZO optimization through a carefully designed dual low-dimensionality strategy: (i) multi-query forward-difference gradient estimation in periodically refreshed random subspaces to mitigate noise amplification in moment buffers, and (ii) Adam updates with periodic restarts performed directly in low-dimensional space rather than full-parameter space. In experiments, this dual design retains memory overhead comparable to momentum-free ZO methods while achieving stronger optimization performance than the evaluated ZO baselines. Theoretically, in the exact-directional limit,

K

-query averaging preserves conditional unbiasedness, while the coefficient estimator's covariance and mean-squared error, as well as query-induced second-moment inflation, scale exactly as

1/K

. Extensive experiments across SuperGLUE with models from 1.3B to 32B parameters under both full fine-tuning and LoRA schemes demonstrate consistent improvements over competing ZO methods. SubZero+ significantly narrows the performance gap with first-order optimization while preserving ZO's inference-time memory efficiency.

Ziming Yu, Shuyao Xiao, Xingyu Zhao +6

Beijing Normal University · Singapore Management University · Xiaomi Inc. +2

Zeroth-Order Large Language Model Fine-Tuning Subspace Bounded-Memory

Aug 11, 2026quant-ph

Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory

We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication

B

, persistent instance-dependent memory

M

, and local work

D

; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between

O(\log N)

qubits and

Ω(\sqrt{N})

classical boundary bits. Continual requirements auditing inherits a Max-

k

SAT streaming separation: a recurrent solver uses

O(\log^5 n\log(1/δ))

qubits and polylogarithmic classical workspace to obtain a

0.7172

-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires

Ω(\sqrt{n})

coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses

n

qubits, while every exact finite-state classical causal online realization satisfies

B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)

. The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

Ming Yang

State-Tracking Tractability Bounded-Memory Boundaries

Aug 11, 2026cs.LG

Batch Size or Negatives? A Selection Rule for Memory-Constrained Recommender Training

Large-scale neural recommender systems are typically trained with a softmax cross-entropy objective over the full item vocabulary. For a typical large number of possible items

K

, the final classification layer dominates memory, requiring

O(nK)

logits and gradients to materialize for a batch of

n

examples. Sampled softmax reduces this cost by restricting the objective to only

k \ll K

candidate negative items, resulting in an

O(nk)

memory. However, for a fixed budget

B = n k

, it remains unclear whether one should prioritize larger batches or the inclusion of more negative items. We address this question by analyzing sampled-softmax training under a fixed memory constraint. Under standard smoothness and variance assumptions, our theoretical evidence suggests that the fastest convergence arises from an

n \sim B, k \sim 1

allocation. So, an actionable rule is to include as many objects as possible given computational constraints. Our theory is supported by controlled synthetic and synthetic and four real sequential recommendation benchmarks, including MovieLens-20M. The suggested configuration achieve faster convergence and better final recommendation quality than imbalanced alternatives within the same memory constraint. These findings provide a theoretical and empirical foundation for configuring memory during the training of recommender systems. Code, reproducibility materials, and all scripts for generating figures are available at https://anonymous.4open.science/r/LimitedMemoryRule-BBFB

Artyom Sabitov, Daniil Volkov, Alexey Zaytsev

Applied AI Institute, Moscow, Russia Risk department

Real-World Content Recommendation Problem Bounded-Memory Batch Gumbel-Softmax Relaxation Negative Results Convergence

Aug 9, 2026cs.LG

Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch

Activation checkpointing minimizes the runtime of neural networks under a given memory budget, by selecting which intermediate tensors to store and which to recompute. PyTorch solves this as a 0/1 knapsack problem, where operations from a joint forward-backward computation graph are items with a memory cost (weight) and a runtime saving (value). The default solver, dp_knapsack, allocates a full dynamic programming (DP) table of shape

(n+1) \times (W+1)

, where

n

is the number of operations and

W

is the quantized memory budget. This method is resource-hungry and crashes at

n = 100

items on a machine with 64 GB RAM. In this paper, we introduce dp_knapsack_sliding_hirschberg, which combines the sliding window trick and Hirschberg's algorithm to reduce peak memory from

O(nW)

to

O(W)

while preserving the exact optimal solution. Our experiments show successful knapsack execution at

n = 2000

, where dp_knapsack fails at

n = 100

, a 20

\times

increase in computable problem size. In addition, our benchmarks show a consistent 25-28% runtime speedup over dp_knapsack. The implementation is merged into PyTorch and released in version 2.10.

Jędrzej Maczan

Cohere Labs Community Poland

Knapsack Constraint Pytorch Model Checkpoints Bounded-Memory Peak Memory Bidirectional Long Short-Term Memory+1

Aug 5, 2026cs.LG

MESH: Memory-Efficient Sinkhorn Optimization for Mixture-of-Experts Training

Memory-efficient matrix optimizers such as Sinkhorn gradient descent remove most AdamW optimizer state for dense Transformer matrices, but direct application to Mixture-of-Experts (MoE) training is unreliable. We study this failure in a controlled 110M-parameter nanowhale DeepSeek-style MoE pretraining setting. A SAGE/Sinkhorn hybrid reduces optimizer state from 0.883GB to 0.331GB but degrades evaluation loss to 3.8265, far above the AdamW baselines observed in the same setup (3.58--3.64 across the seeds we study). We show that routed MoE expert matrices are the dominant failure point: their gradients are conditional, temporally varying, and poorly served by stateless Sinkhorn normalization. We propose MESH, a hidden-momentum Sinkhorn update for MoE experts. MESH restores a temporal first-moment signal through the gradient-buffer lifecycle, without storing the expert first moment as optimizer state. MESH is an optional block-preconditioned variant that adds a coarse neuron/block inverse-RMS multiplier. Across ablations, temporal smoothing before matrix normalization is the primary causal ingredient; block/neuron preconditioning can improve the memory-quality frontier, but is not established as universally necessary. In two additional seeds, MESH and MESH-B reduce optimizer-state memory by 62.5% and peak PyTorch CUDA allocation by about 12.6% relative to AdamW, with a modest evaluation-loss gap. Full-state diagnostic variants recover AdamW-like performance in ablations, supporting the conclusion that MoE experts need temporal smoothing, but not necessarily full coordinate-wise AdamW state.

Masato Fujitake

FA Research, Fast Accounting Co., Ltd.

Mixture-Of-Experts Adam Fused Sinkhorn-Localized Similarity Bounded-Memory Spectral Preconditioning Deepseek

Jul 10, 2026cs.LG

FlashTrie: A GPU-Accelerated Constrained Beam Search for Generative Retrieval

Constrained decoding is essential in generative retrieval, where document identifiers generated directly from a query must exactly match a predefined library of valid IDs. At scale, decoding is often constrained using a trie with beam search but most implementations run on CPU. Limited parallelism then makes trie traversal and candidate validation a serving bottleneck as beam width grows. We present FlashTrie, which addresses this limitation by optimizing constrained beam search on GPUs. It introduces an integer-aware succinct trie layout that uses bit compression to reduce memory footprint while keeping the full index in GPU high-bandwidth memory reducing memory stalls, and a cooperative CUDA kernel that performs beam expansion, validation, and pruning entirely on-device without per-step host orchestration. It further replaces CPU-style irregular lookup and heap maintenance with GPU-aware parallel primitives, improving warp utilization and reducing divergence. Together, these designs significantly reduce decoding latency and increase throughput while preserving retrieval quality. On a library of 800M keywords with beam widths up to 1000, FlashTrie reduces trie-search latency to under 3 ms, achieving up to 24x speedup over a highly optimized multi-threaded CPU baseline. These improvements enable FlashTrie to scale beam sizes by up to 5x in latency-critical applications such as sponsored search. In a large-scale online A/B experiment on a popular commercial search engine, it delivers a statistically significant +0.71% revenue lift, enabling real-time constrained decoding at a scale previously feasible only offline. The FlashTrie code will be publicly released after the review process.

Dakshitha Anandakumar, Anurag Mukkara, Wenxiang Hu +5

Microsoft, Redmond, WA, USA · Nvidia, Santa Clara, CA, USA

Beam Search Constrained Decoding Cpu-Gpu Hybrid Designs Bounded-Memory

Jul 6, 2026cs.LG

KVpop -- Key-Value Cache Compression with Predictive Online Pruning

Key-value (KV) cache growth is a major bottleneck in autoregressive decoding, as memory and bandwidth scale linearly with context length. Existing KV eviction methods often rely on static heuristics or proxy scores, which poorly track future token utility and cause brittle eviction as relevance shifts. To address this, we introduce KVpop, which learns a fixed-budget KV eviction policy by directly supervising the keep-or-drop decision. The scorer is trained against a novel future-attention target, computed efficiently without materializing dense attention maps. We further introduce a delayed memory-based scorer that, uniquely among learned eviction methods, defers scoring for a fixed number of steps to exploit near-future context. On AIME and HMMT mathematical reasoning, KVpop retains 98% of full-attention performance on Qwen3-4B at 75% KV cache compression and 97% at 88% compression, consistently outperforming established eviction baselines. Qwen3-8B shows even stronger results, reaching near-full teacher performance. These results show that supervising eviction with future-attention signals cuts memory costs while maintaining quality.

Lukas Hauzenberger, Niklas Schmidinger, Anamaria-Roberta Hartl +5

1NXAI · 2Johannes Kepler University Linz, Austria

Key-Value Cache Eviction Key-Value Cache Compression Bounded-Memory Autoregressive Decoding Destination-Only Scoring Growth

Jul 2, 2026cs.AI

AgenticSTS: A Bounded-Memory Testbed for Long-Horizon LLM Agents

Memory for a long-horizon LLM agent is a contract about what each future decision is allowed to see. The simplest contract appends past observations, tool calls, and reflections to every prompt, which makes prior context easy to access but also turns it into a jumbled mixture in which the effect of any single memory component is hard to isolate. We introduce and instrument an alternative bounded contract: every decision is made from a fresh user message assembled by typed retrieval, with no raw cross-decision transcript appended. The prompt thus stays bounded across runs of any length, and any single layer can be ablated in isolation. We instantiate the contract in Slay the Spire 2, a closed-rule stochastic deck-building game whose runs require hundreds of tactical and strategic decisions. A public online benchmark of frontier LLMs on the same game reports zero wins at the lowest difficulty across five configurations, and the developer-reported human win rate at the same difficulty is 16%; the task is hard but not saturated. Within our harness, a fixed-A0 ablation shows the largest observed difference when triggered strategic skills are enabled: the no-store baseline wins 3/10 games and adding the skill layer 6/10. At this sample size the comparison is directional rather than statistically decisive (Fisher exact p\approx0.37); a cross-backbone probe and public accumulating-context baselines are reported as operational comparisons rather than controlled tests of the contract variable itself. We release a reproducible testbed: 298 completed trajectories with condition tags, frozen memory/skill snapshots, prompt records, and analysis scripts -- an agent design and a validated, reusable methodology for studying how explicit memory layers shape long-horizon LLM-agent decisions.

Xiangchen Cheng, Yunwei Jiang, Jianwen Sun +7

Alaya Lab · Shanghai Jiao Tong University · Shanghai Innovation Institute +2

Long-Term Agent Memory Strategic Reasoning Agentic Bounded-Memory Transcript

Jun 25, 2026cs.CL

CARVE: Content-Aware Recurrent with Value Efficiency for Chunk-Parallel Linear Attention

Recurrent delta-rule models keep a fixed-size state matrix S (d_v x d_k) that compresses all past context. The state of the art (GDN-2) gates this update with element-wise matrix erase/write masks. This is powerful but has two defects. First, both gates are computed from the incoming token alone, making the model memory-blind: it decides what to erase without seeing what it has stored. Second, value-axis coupling in the erase gate blocks the WY-form triangular chunk solver that drives efficient training -- the intra-chunk system splits into d_v independent solves, collapsing throughput to serial-recurrence cost. We introduce CARVE (Content-Aware Recurrent with Value Efficiency), which fixes both and, via a single-launch "megakernel" scheduling of the same WY-form math, trains faster than the matrix-gated baseline it replaces. The key idea is architectural: restricting all gating to the key axis makes the intra-chunk coupling independent of the value index, restoring one unmodified WY-form solve. Within this constraint, CARVE conditions both gates on a content signal read once per chunk from the chunk-boundary state and folded algebraically into each gate's low-rank projection (by associativity, U(Sq)=(US)q), giving memory-aware gating at negligible extra traffic. At init the content projections are zero, so CARVE is bit-identical to the baseline; we prove the one-chunk staleness perturbs gates by only O(1/sqrt(L)), matching a measured 0.18% deviation flat up to L=128. At 1.3B parameters / 100B FineWeb-Edu tokens on H100 (three seeds), CARVE improves every axis: WikiText perplexity 15.72 vs 15.90 (hybrid 15.41 vs 15.62), +0.63 pp average common-sense accuracy, and state-of-the-art RULER and real-world recall -- while training +1.4% faster at matched depth and +19.3% at iso-quality depth, at +13% peak memory. Backed by six formal guarantees.

Sayak Dutta

Recurrent Model Kimi Delta Attention Bounded-Memory Factual Recall Gradient Staleness Efficiency

Jun 24, 2026cs.DS

Space-Efficient Language Generation in the Limit

We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language

K

and must eventually output a hallucination-free hypothesis language

L \subseteq K

while omitting at most

Δ

strings of

K

. We focus on

\mathcal{C}_{s,k}

, the collection of languages recognized by DFAs with at most

s

states over an alphabet of size

k

, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target

K

. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using

\mathrm{poly}(s,k)

space that converges to a hypothesis with generation gap

Δ= O(k^{2s-2})

. Moreover, the learned hypothesis captures every string in

K

of length at least

2s-1

. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap

Δ\le k^{(1-\varepsilon)s}

requires

k^{Ω(\varepsilon s)}

memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.

Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2

EPFL, Switzerland · Stanford University, USA

Bounded-Memory Optimal Sample Complexity

Jun 9, 2026cs.LG

Unifying Data, Memory, and Compute Efficiency in LLM training: A Survey

Resource constraints increasingly determine what can be trained, fine-tuned, and deployed in large language models (LLMs), yet efficiency is often studied through isolated techniques rather than as an interacting system of limits. This survey adopts a constraint-centric perspective and organizes recent progress around three coupled bottlenecks: data efficiency (what to train on), memory efficiency (how to fit training), and compute budget awareness (when and where to spend FLOPs). On the data axis, we review selection and pruning methods that maximize learning per token, ranging from scalable proxy signals based on learning dynamics to gradient- and influence-based scoring, as well as difficulty-aware and curriculum-style strategies. We highlight emerging evidence that different notions of good data dominate in different regimes, implying that optimal subsets depend on the task objective and resource budget rather than being universal. On the systems side, we show that GPU memory, not raw compute, is often the dominant bottleneck in fine-tuning, and that effective scaling requires jointly reducing weight storage, optimizer states, and activation memory rather than optimizing any single component in isolation. Beyond memory, we frame training and inference as compute-governed processes in which optimization, data selection, and decoding must explicitly account for finite FLOP budgets. We review evidence for compute-optimal allocation and stopping rules, where computation should be halted or reallocated once marginal performance gains fall below a budget-dependent threshold. Together, these results unify compute-aware data selection, scaling laws, and adaptive inference under a common principle of resource-conditioned decision-making.

Vanessa Schmidt, Huy Hoang Nguyen, Cédric Jung +2

Chair of Information Theory and Data Analytics (INDA), RWTH Aachen University, 52074 Aachen, Germany · AIT Austrian Institute of Technology GmbH, 1210 Vienna, Austria · Automation and Control Institute, Technische Universität Wien (TUW), 1040 Vienna, Austria

Alignment-Aware Selection Large Language Model Training Bounded-Memory Peak Memory Efficiency

May 28, 2026cs.DS

On Language Generation in the Limit with Bounded Memory

We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples. Prior work assumes access to the entire history, a strong assumption since realistic algorithms retain limited past information. Classical work in learning theory shows memory constraints dramatically alter learnability; we extend this to language generation. First, we study memoryless generators. Under a mild enumeration restriction, every countable collection of infinite languages remains generable without memory. Without this restriction, we exactly characterize when memoryless generation is possible. For finite collections, we characterize the optimal minimax density achievable by memoryless generators -- the best density guaranteed against any collection of a given size. This combinatorial bound relies on Sperner's theorem and symmetric chain decompositions. We further show that a sliding window of the last

W

examples does not improve this worst-case density, whereas allowing it to store

b

adaptively chosen past examples improves the achievable density for every

b \geq 1

. Finally, we revisit identification in the limit, where the learner must converge to a single correct hypothesis for the target language. We focus on its incremental variant, where the learner remembers only its previous guess. Here, although exact identification fails on a collection of just three languages, a mild relaxation requiring convergence to an ``approximate'' version of the target is achievable for every finite collection. These results show bounded memory affects these tasks differently: generation remains achievable for every countable collection, while density and identification are confined to finite collections, with guarantees weakening as the collection grows.

Jon Kleinberg, Anay Mehrotra, Amin Saberi +1

Cornell University · Stanford University · Google Research

Bounded-Memory Learnability Infinities Worst-Case

May 22, 2026cs.LG

Approaching I/O-optimality for Approximate Attention

We revisit the I/O complexity of attention in large language models. Given query-key-value matrices

Q,K,V\in\mathbb{R}^{n\times d}

, and a machine with fast memory size

M

, the goal is to compute the "attention matrix"

A=\text{softmax}(Q K ^{\top}/\sqrt{d}) V

with the minimal number of data transfers between fast and slow memory. Existing methods in the literature, most notably FlashAttention and its variants, incur an I/O cost that depends quadratically on

n

, while a trivial lower bound only requires

Ω(nd)

I/O's to read the inputs and write the output. In this work, we present a technique for computing attention where the I/O cost only depends almost-linearly on

n

in most parameter regimes. This is achieved by developing I/O-efficient algorithms inspired by the recent approximate attention framework of Alman and Song. We also prove corresponding lower bounds in each parameter regime to show that our algorithms are indeed close to I/O-optimal.

Pál András Papp, Aleksandros Sobczyk, Anastasios Zouzias

Computing Systems Lab, Huawei Technologies, Zurich, Switzerland

Kimi Delta Attention Matrix Multiplication Dynamic Attention Bounded-Memory Fast-Slow Optimality

May 20, 2026cs.LG

Memory-Efficient Partitioned DNN Inference on Resource-Constrained Android Crowds

Deploying large deep neural networks on memory-constrained mobile devices is a central challenge in edge ML. While compression, pruning, and quantization reduce per-parameter cost, transformer-based models remain too large for the 3.3-7.4 GB RAM envelope of commodity Android handsets. We present the DNN pipeline scheduling subsystem of CROWDio, which achieves practical ONNX inference across resource-constrained Android workers without model modification, by distributing memory pressure across devices via five mechanisms: JIT deferred partition loading, a single-partition-resident constraint, a 4-tier affinity scheduler, a zlib-compressed tensor transport, and a streaming 1:1 dependency model. Evaluated on DistilBERT (Sanh et al., 2019) (approximately 67 M parameters, SST-2) across five Android handsets over ten runs, our system holds peak per-device RSS to 43+-2 MB and limits battery draw to 50+-3 mAh per run, while streaming concurrency cuts batch latency 34% below barrier synchronisation.

Lakshani Manamperi, Disumi Pathirana, Thiwanka Pathirana +2

Department of Computer Science and Engineering, University of Moratuwa, Moratuwa, Sri Lanka.

Resource-Constrained Edge Devices Neural Network Inference Bounded-Memory Python

May 14, 2026cs.LG

Minimal-Intervention KV Retention via Set-Conditioned Diversity

KV-cache compression at small budgets is a crowded design space spanning cache representation, head-wise routing, compression cadence, decoding behavior, and within-budget scoring. We study seven mechanisms across these five families under matched mean cache on long-form mathematical reasoning (MATH-500~\cite{hendrycks2021math}) with two distilled-reasoning models (Qwen-7B and Llama-8B variants of DeepSeek-R1-Distill~\cite{deepseek2025r1}) at budgets

b \in \{64, 128\}

. All seven were rejected. We then propose

α

, a one-function modification to the TriAttention~\cite{mao2026triattention} retention scorer that replaces argmax-top-

k

with greedy facility-location-inspired selection under a V-space redundancy penalty controlled by a single weight

λ

. A pre-registered protocol tunes

λ

on a frozen development split and confirms on a disjoint held-out split; with

λ= 0.5

,

α

clears Bonferroni on two of the four (model, budget) cells (Qwen

b{=}128

and Llama

b{=}64

), no cell is significantly negative, and the pre-registered Branch~A triggers. The finding is asymmetric: a minimal scoring modification beat heavier structural redesigns in this regime, and the combined matched-memory, sympy-graded, held-out confirmation protocol is the evidence standard that made the asymmetry visible.

Libo Sun, Po-wei Harn, Peixiong He +1

Department of Computer Science and Software Engineering Auburn University, Auburn, AL, USA · Department of Information Management National Central University, Taoyuan, Taiwan

Key-Value Cache Compression Cache Bounded-Memory Retention Token Budget Allocation Diversity

May 12, 2026cs.LG

KV-Fold: One-Step KV-Cache Recurrence for Long-Context Inference

We introduce KV-Fold, a simple, training-free long-context inference protocol that treats the key-value (KV) cache as the accumulator in a left fold over sequence chunks. At each step, the model processes the next chunk conditioned on the accumulated cache, appends the newly produced keys and values, and passes the enlarged cache forward; the same one-step update is applied repeatedly, analogous to foldl in functional programming. Building on the KV cache concatenation primitive introduced for latent multi-agent communication, we repurpose it as a chunk-to-chunk recurrence for long-context inference. When processing chunk t, the model attends to the KV cache carried from earlier chunks as a prefix, reusing its internal state across segments without modifying or retraining the model. Despite its simplicity, the induced recurrence is stable: per-step drift rises briefly and then saturates into a flat plateau that persists across deep chains. This plateau is insensitive to a 10,000x change in numerical precision, robust across chunk sizes, and consistent across model families. At the task level, KV-Fold preserves exact information over long distances. On a needle-in-a-haystack benchmark, it achieves 100% exact-match retrieval across 152 trials spanning contexts from 16K to 128K tokens and chain depths up to 511 on Llama-3.1-8B, while remaining within the memory limits of a single 40GB GPU. Compared to streaming methods, which trade fidelity for bounded memory, KV-Fold maintains long-range retrieval while operating as a sequence of tractable forward passes. Overall, our results show that frozen pretrained transformers already support a stable form of KV-cache recurrence, providing a practical route to long-context inference without architectural changes or training.

Alireza Nadali, Patrick Cooper, Ashutosh Trivedi +1

Department of Computer Science University of Colorado Boulder Boulder, Colorado, 80301

Efficient Long-Context Inference Kv-Cache Management Key-Value Cache LLM Inference Optimization Bounded-Memory Chunk+2

May 9, 2026cs.LG

Navigating LLM Valley: From AdamW to Memory-Efficient and Matrix-Based Optimizers

Training large language models requires optimization algorithms that are not only statistically effective, but also computationally and memory efficient at extreme scale. Although Adam remains the dominant optimizer for large-scale language-model pretraining and fine-tuning, recent work has revisited nearly every component of the optimization stack: adaptive moment estimation, decoupled weight decay, memory footprint, curvature approximation, sign-based updates, large-batch stability, low-rank gradient structure, and matrix-wise orthogonalized updates. This survey reviews optimizer design for large language models through a systems-and-optimization lens. We organize the literature into classical first-order optimizers, adaptive optimizers, memory-efficient variants, second-order and curvature-aware methods, sign-based and discovered optimizers, low-rank and projection-based methods, and matrix-based optimizers such as Muon. We also discuss benchmarking methodology, including hyperparameter fairness, scale dependence, wall-clock efficiency, token efficiency, memory overhead, and downstream evaluation. We argue that optimizer research for LLMs is entering a new phase: moving from single-algorithm speedup claims toward rigorous, scale-aware comparisons that jointly evaluate convergence, stability, memory, and implementation complexity.

Aditya Ranganath

Center for Applied Scientific Computing Lawrence Livermore National Laboratory Livermore, CA, USA

Optimizer Design Large Language Model Training Large Language Model Pretraining Bounded-Memory Low-Rank Structure

May 8, 2026cs.AR

Effective and Memory-Efficient Alternatives to ECC for Reliable Large-Scale DNNs

Modern Deep Learning (DL) workloads are increasingly deployed in safety-critical domains, such as automotive systems and hyperscale data centers, where transient hardware faults pose a serious threat to system reliability. These workloads are highly memory-intensive, and their correct functionality strongly depends on model parameters stored in memory, which are typically protected using Error Correction Codes (ECCs). In this work, we study ECC's impact on such models and propose two lightweight alternatives to ECCs that achieve superior reliability. The first approach, MSET, selectively hardens the most vulnerable bits in CNN and ViT parameters, while the second approach, CEP, provides fine-grained protection for all parameter bits. Experimental results demonstrate that both methods significantly enhance the reliability of large CNNs and ViTs, mostly outperforming conventional Single Error Detection Double Error Correction (SECDED) ECC schemes, with no memory overhead and, in fact, with considerably lower area and delay characteristics when compared to SECDEC. Experimental results indicate that ViTs can be effectively protected by merely protecting their highest exponent bits in FP16 and FP32 representations. Furthermore, applying the CEP technique can guarantee the resilience of DNNs by up to one order of magnitude higher BERs, with a 3.5x lower area overhead and 7x faster decoder compared to SECDED ECC.

Mohammad Hasan Ahmadilivani, Marten Roots, Marco Restifo +3

Tallinn University of Technology, Tallinn, Estonia · ARM Ltd., Cambridge, United Kingdom

Error Correction Neural Network Inference Capability-Speed Trade-Offs Bounded-Memory Reliable

May 7, 2026cs.DS

Nearly Optimal Attention Coresets

We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values

(K,V)

in

\mathbb{R}^d

, there exists a subset

(K',V')

of size at most

O({\sqrt{d} e^{ρ+o(ρ)}/\varepsilon})

such that

\left\| \operatorname{Attn}(q,K,V)- \operatorname{Attn}(q,K',V') \right\| \le \varepsilon

simultaneously for all queries whose norm is bounded by

ρ

. This outperforms the best known results for this problem. We also offer an improved lower bound showing that

\varepsilon

-coresets must have size

Ω({\sqrt{d} e^ρ/ε})

.

Edo Liberty, Alexandr Andoni, Eldar Kleiner

Geometry-Aware Uncertainty Coresets Bounded-Memory Small Models Queries

May 6, 2026cs.CL

The Impossibility Triangle of Long-Context Modeling

We identify and prove a fundamental trade-off governing long-sequence models: no model can simultaneously achieve (i) per-step computation independent of sequence length (Efficiency), (ii) state size independent of sequence length (Compactness), and (iii) the ability to recall a number of historical facts proportional to sequence length (Recall). We formalize this trade-off within an Online Sequence Processor abstraction that unifies Transformers, state space models, linear recurrent networks, and their hybrids. Using the Data Processing Inequality and Fano's Inequality, we prove that any model satisfying Efficiency and Compactness can recall at most O(poly(d)/log V) key-value pairs from a sequence of arbitrary length, where d is the model dimension and V is the vocabulary size. We classify 52 architectures published before March 2026 into the triangle, showing that each achieves at most two of the three properties and that hybrid architectures trace continuous trajectories in the interior. Experiments on synthetic associative recall tasks with five representative architectures validate the theoretical bound: empirical recall capacity lies strictly below the information-theoretic limit, and no architecture escapes the triangle.

Yan Zhou

School of Mathematics and Statistics Changsha University of Science and Technology Changsha, Hunan 410114, China

Sequence Modeling Bounded-Memory Precision Recall Impossibility Trade-Off

May 6, 2026cs.AI

Budget-aware Auto Optimizer Configurator

Optimizer states occupy massive GPU memory in large-scale model training. However, gradients in different network blocks exhibit distinct behaviors, such as varying directional stability and scale anisotropy, implying that expensive optimizer states are not universally necessary and using a global optimizer is often memory-inefficient. We propose the Budget-Aware Optimizer Configurator (BAOC) to reduce memory cost by assigning suitable optimizer configurations to individual blocks under given budgets. Specifically, BAOC samples gradient streams to derive statistical metrics that quantify the potential performance risk of applying cheaper configurations (e.g., low precision or removing momentum). It then solves a constrained allocation problem to minimize total risk under memory and time budgets, selecting a budget-feasible configuration for each block. Experiments across vision, language, and diffusion workloads demonstrate that BAOC maintains training quality while significantly reducing the memory usage of optimizer states. The code is available at https://anonymous.4open.science/r/BAOC-45C6.

Kang Liu, Wei Peng, Jianchen Hu

School of Future Technology Xi’an Jiaotong University Xi’an, China · School of Automation Science and Engineering Xi’an Jiaotong University Xi’an, China

Optimizer Design Graphics Processing Unit Memory Bounded-Memory Gradient Component

May 5, 2026cs.LG

Memory-Efficient Continual Learning with CLIP Models

Contrastive Language-Image Pretraining (CLIP) models excel at understanding image-text relationships but struggle with adapting to new data without forgetting prior knowledge. To address this, models are typically fine-tuned using both new task data and a memory buffer of past tasks. However, CLIP's contrastive loss suffers when the memory buffer is small, leading to performance degradation on previous tasks. We propose a memory-efficient, distributionally robust method that dynamically reweights losses per class during training. Our approach, tested on class incremental settings (CIFAR-100, ImageNet1K) and a domain incremental setting (DomainNet) adapts CLIP models quickly while minimizing catastrophic forgetting, even with minimal memory usage.

Ryan King, Gang Li, Bobak Mortazavi +1

Department of Computer Science Texas A&M University College Station, TX 77843 · Texas A&M University College Station, TX 77843

Contrastive Language-Image Pre-Training Model Replay-Based Continual Learning Contrastive Loss Bounded-Memory

May 2, 2026cs.LG

Activation Compression in LLMs: Theoretical Analysis and Efficient Algorithm

Training large language models (LLMs) is highly memory-intensive, as training must store not only weights and optimizer states but also intermediate activations for backpropagation. While existing memory-efficient methods largely focus on gradients and optimizer states, activation compression is less well established due to the lack of LLM-tailored theory and guarantees. In this work, we develop a theoretical framework showing that activation compression is safe for linear operators when activation compression is unbiased, but problematic for nonlinear ones. We further derive gradient variance bound and establish convergence guarantees for applying activation compression to all linear operators under the standard

L

-smoothness assumption, showing that it does not change the convergence rate. Guided by the theory, we propose an activation-gradient co-compression method that reuses low-rank activation factors to compress linear-layer gradients without extra computation or additional gradient error. We conduct extensive experiments on Qwen and LLaMA models using a pretraining benchmark and multiple fine-tuning benchmarks to validate our theory and demonstrate competitive performance of our method in both accuracy and compression efficiency. We provide our code in the supplementary material for reproducibility.

Wen-Da Wei, Han-Bin Fang, Yang-Di Liu +3

Nanjing University, Nanjing, China · Tsinghua University, Beijing, China · Huazhong University of Science and Technology, Wuhan, China +1

Large Language Model Compression Task-Aware Compression Model Activations Large Language Model Training Bounded-Memory Theory

Apr 30, 2026cs.CL

Syntactically-guided Information Maintenance in Sentence Comprehension

Maintaining information in context is essential in successful real-time language comprehension, but maintenance is cognitively costly and can slow processing. We hypothesize that rational language users selectively maintain information that is crucial for future prediction, guided by syntactic structure. Under this view, two factors affect maintenance cost: the number of predicted heads and the number of incomplete dependencies. Although these factors have been treated as competing hypotheses in the literature, our account predicts that they are not reducible to one another. We show this is the case in a naturalistic reading time dataset in Japanese, a language in which the two factors contrast particularly clearly. We further show that there is a tradeoff such that readers that slow down for maintenance tend to benefit more from predictability, providing additional support for the proposed account. These patterns are not evident in English, however, and we highlight some issues to be resolved to understand the contribution of syntax in memory-efficient processing of various languages.

Shinnosuke Isono, Kohei Kajikawa

NINJAL · Georgetown University

Syntactic Structure Bounded-Memory Textual Dataset

Apr 23, 2026cs.LG

Universal Transformers Need Memory: Depth-State Trade-offs in Adaptive Recursive Reasoning

We study learned memory tokens as a computational scratchpad for a single-block Universal Transformer with Adaptive Computation Time (ACT) on Sudoku-Extreme, a combinatorial reasoning benchmark. Memory tokens are empirically necessary: no configuration without them reaches non-trivial performance. The optimal count has a sharp lower threshold (T=0 always fails, T=8 reliably succeeds) followed by a stable plateau (T=8-32, 57.4% +/- 0.7% exact-match) and a dilution boundary at T=64. Under halt-side pressure (lambda warmup), mean halt drops monotonically with memory size across the plateau (from 11.6 at T=8 to 8.3 at T=64), showing that memory tokens and ponder depth substitute as resources at fixed accuracy. We also identify a router initialization trap that causes the majority of training runs to fail: both default zero-bias and Graves' recommended positive bias settle into a shallow halt equilibrium the model cannot escape. Inverting the bias to -3 ("deep start") eliminates the failure mode, and ablation shows the trap is inherent to ACT initialization rather than an artifact of our architecture. With reliable training, ACT yields an order of magnitude lower seed variance than fixed-depth processing (+/-0.7 vs +/-9.3 pp); lambda warmup recovers 34% of compute at matched accuracy; and attention heads specialize into memory readers, constraint propagators, and integrators across recursive depth. Code: https://github.com/che-shr-cat/utm-jax.

Grigory Sapunov

Intento

Bounded-Memory Transformer Architectures Combinations Energy-Based Transformer Equilibrium

Apr 22, 2026cs.CR

Onyx: Cost-Efficient Disk-Oblivious ANN Search

Approximate nearest neighbor (ANN) search in AI systems increasingly handles sensitive data on third-party infrastructure. Trusted execution environments (TEEs) offer protection, but cost-efficient deployments must rely on external SSDs, which leaks user queries through disk access patterns to the host. Oblivious RAM (ORAM) can hide these access patterns but at a high cost; when paired with existing disk-based ANN search techniques, it makes poor use of SSD resources, yielding high latency and poor cost-efficiency. The core challenge for efficient oblivious ANN search over SSDs is balancing both bandwidth and access count. The state-of-the-art ORAM-ANN design minimizes access count at the ANN level and bandwidth at the ORAM level, each trading-off the other, leaving the combined system with both resources overutilized. We propose inverting this design, minimizing bandwidth consumption in the ANN layer and access count in the ORAM layer, since each component is better suited for its new role: ANN's inherent approximation allows for more bandwidth efficiency, while ORAM has no fundamental lower bounds on access count (as opposed to bandwidth). To this end, we propose a cost-efficient approach, Onyx, with two new co-designed components: Onyx-ANNS introduces a compact intermediate representation that proactively prunes the majority of bandwidth-intensive accesses without hurting recall, and Onyx-ORAM proposes a locality-aware shallow tree design that reduces access count while remaining compatible with bandwidth-efficient ORAM techniques. Compared to the state-of-the-art oblivious ANN search system, Onyx achieves

1.7-9.9\times

lower cost and

2.3-12.3\times

lower latency.

Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao +2

UC Berkeley, NVIDIA · NVIDIA · UT Austin, NVIDIA +1

Approximate Nearest-Neighbor Search Neural Architecture Search Search Algorithms Bounded-Memory Neural Network Inference

Apr 16, 2026cs.DB

RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems

Recent advances in query optimization have shifted from traditional rule-based and cost-based techniques towards machine learning-driven approaches. Among these, reinforcement learning (RL) has attracted significant attention due to its ability to optimize long-term performance by learning policies over query planning. However, existing RL-based query optimizers often exhibit unstable performance at the level of individual queries, including severe performance regressions, and require prolonged training to reach the plan quality of expert, cost-based optimizers. These shortcomings make learned query optimizers difficult to deploy in practice and remain a major barrier to their adoption in production database systems. To address these challenges, we present RELOAD, a robust and efficient learned query optimizer for database systems. RELOAD focuses on (i) robustness, by minimizing query-level performance regressions and ensuring consistent optimization behavior across executions, and (ii) efficiency, by accelerating convergence to expert-level plan quality. Through extensive experiments on standard benchmarks, including Join Order Benchmark, TPC-DS, and Star Schema Benchmark, RELOAD demonstrates up to 2.4x higher robustness and 3.1x greater efficiency compared to state-of-the-art RL-based query optimization techniques.

Seokwon Lee, Jaeyoung Sim, Sihyun Kim +3

Yonsei University BDAI Lab, Seoul 03722, South Korea · Microsoft Gray Systems Lab, Redmond, USA

Prompt Optimization Queries Bounded-Memory

Mar 9, 2026cs.RO

Rheos: Modelling Continuous Motion Dynamics in Hierarchical 3D Scene Graphs

3D Scene Graphs (3DSGs) provide hierarchical, multi-resolution abstractions that encode the geometric and semantic structure of an environment, yet their treatment of dynamics remains limited to tracking individual agents. Maps of Dynamics (MoDs) complement this by modeling aggregate motion patterns, but rely on uniform grid discretizations that lack semantic grounding and scale poorly. We present Rheos, a framework that explicitly embeds continuous directional motion models into an additional dynamics layer of a hierarchical 3DSG that enhances the navigational properties of the graph. Each dynamics node maintains a semi-wrapped Gaussian mixture model that captures multimodal directional flow as a principled probability distribution with explicit uncertainty, replacing the discrete histograms used in prior work. To enable online operation, Rheos employs reservoir sampling for bounded-memory observation buffers, parallel per-cell model updates and a principled Bayesian Information Criterion (BIC) sweep that selects the optimal number of mixture components, reducing per-update initialization cost from quadratic to linear in the number of samples. Evaluated across four spatial resolutions in a simulated pedestrian environment, Rheos consistently outperforms the discrete baseline under continuous as well as unfavorable discrete metrics. We release our implementation as open source.

Iacopo Catalano, Francesco Verdoja, Javier Civera +2

University of Turku, Finland · School of Electrical Engineering, Aalto University, Finland · University of Zaragoza, Spain +2

3D Scene Graphs Motion Model Scene Understanding Bounded-Memory

Jan 20, 2026cs.LG

ButterflyMoE: Compression-Scalable Ternary Experts via Structured Butterfly Orbits

In current Mixture of Experts (MoE) architectures, linear memory scaling is present, the memory grows as the number of experts increases.

N

independent expert weight matrices require

\mathcal{O}(N \cdot d^2)

memory which exceeds the memory budget of edge devices. Current compression methods like quantization, pruning, and low-rank factorization reduce constant factors, but the scaling bottleneck is still unresolved. We introduce ButterflyMoE, a method which treats experts not as independent matrices but as geometric reorientations of a shared quantized substrate. Diversity amongst the experts arises from viewing different angles of the shared capacity and not from redundant storage. Learned rotations are applied to a shared ternary prototype. With this, each expert yields

\mathcal{O}(d^2 + N \cdot d \log d)

memory-reducing per-expert cost from

\mathcal{O}(d^2)

to

\mathcal{O}(d \log d)

. The key insight is that training these rotations with quantization reduces activation outliers and stabilizes extreme low-bit training where other static methods collapse. Across language modeling benchmarks, ButterflyMoE achieves 80

\times

memory reduction at 8 experts with a highly favorable memory-accuracy tradeoff.At this 80x compression ButterflyMoE outperforms an equal memory dense baseline, showing that orbital parameterization extracts fundamentally more utility per byte. When scaled up to 256 experts, ButterflyMoE asymptotically compresses the memory by 150

\times

. ButterflyMoE reduces the constant factor of linear scaling with compression ratio growing with the expert count.

Aryan Karmore

Indian Institute of Information Technology, Nagpur

Experts Bounded-Memory Expert Demonstrations

Nov 28, 2025cs.LG

Poincaré Meets Bellman: Revisable Memory, Operational Quotients, and Evidence-Supported Learning in Changing Environments

Memory consolidation determines both what a learner can do now and which changes remain implementable later. We develop a finite-model synthesis of operational state abstraction and optimal control under the stability-evidence-revision (SER) framework. ``Poincaré meets Bellman'' names two complementary roles: qualitative dynamics identifies reusable action-response structure, and dynamic programming prices acquisition, retention, reuse, merging, and forgetting. Recurrence enters separately through the timing and value of future demands. We distinguish active quotient merging from historical information erasure, characterize exact repair by zero-error functional coding and causal migration, and derive a Bellman recursion over the joint law of hidden state and complete deployed memory. A first-return model yields an explicit retention rule. Conditional results show how factor sharing avoids enumerating combinations and how independent informative observations improve identification, while leaving some zero-error evidence budgets unchanged. Finite enumerations verify the coding and retention calculations. The synthesis gives an exact benchmark for specified finite models, without claiming universal recurrence, bounded-memory open-ended learning, or tractable global planning.

Xin Li

Department of Computer Science University at Albany

Bellman Equation Bounded-Memory Hamiltonian Invariant Synthesis