Hashrope: A Persistent Data Structure for Mechanisms of LLM Context Management

Muntaser Syed; Ameerah Alsulami; Marius Silaghi

cs.DSOct 12, 2026

Hashrope: A Persistent Data Structure for Mechanisms of LLM Context Management

Authors: Muntaser Syed, Ameerah Alsulami, Marius Silaghi

Organizations: Florida Institute of Technology

Abstract

Serving stacks for large language models manage context through four recurring mechanisms: incremental edits to a growing context, branching and snapshotting for tree search, identification of reusable prefixes for KV-cache reuse, and encoding of repeated segments. Each mechanism is served today by a different specialist structure. We show that all four reduce to a single persistent weight-balanced rope whose every node carries a polynomial hash of its subtree over a Mersenne prime, so that the structure supports logarithmic edits and logarithmic verified content-identity queries at the same time. We validate each mechanism with pre-registered, replicated experiments, then compare against a deployed specialist per mechanism: the Ropey editing library, a faithful PagedAttention copy-on-write block table, and the vendored SGLang radix matcher. On workloads that interleave edits with identity queries, Hashrope is net-superior to Ropey by a factor that grows without bound (369.7x at one million characters). Against the radix matcher on a live vLLM stack serving Qwen2.5-7B-Instruct-1M on four A100 GPUs, Hashrope identifies a one-million-token shared prefix exactly and 1.20x faster, at a context length the dense engine cannot even prefill.

Figures & tables

Mechanism	Bound	Guard	Headline
Ingestion	exact tokens	0 divergences	7.6x at 16-way
Flatten	$O(N)$	0 re-hash / re-alloc	800x vs re-split
Branching	$O(B\log N)$ mem	$O(\log w)$ /fork	166x at 8 MB
Identify	$O(\log^{2}N)$	$2\lceil\log_{2}N\rceil$ steps	slope 0.028
Repetition	$O(\log q)$	1 node per repeat	$10^{6}$ x at $q{=}10^{4}$

TABLE I: Mechanism validation. Guards are deterministic (std = 0); timings are mean over 9 runs. Slopes are log-log wall-clock exponents.

$N$ (B)	re-split (ms)	in-order (ms)	guard L/S/H	speedup
64 K	11.2	0.003	30/15/30	3427x
256 K	48.9	0.050	126/63/126	1082x
1 M	199.2	0.272	510/255/510	735x
2 M	437.4	0.546	1022/511/1022	800x
4 M	865.0	1.166	2044/1023/2044	741x
8 M	1692.6	2.305	4092/2047/4092	734x

TABLE II: Flatten sweep, mean over nine runs. The guard column counts leaf re-allocations / splits / hash recomputations per flatten; the in-order materializer performs none at any size.

Fig. 1: Prefix-identification latency over context size at half-way divergence, nine runs per point, log-log. The hash LCP is near flat (the

O(\log^{2}N)

signature) while the byte scan is linear; the crossover falls near 1 MB, where long-context serving begins.

Study	Oracle / gate (0 mismatches)	Guard and negative control
Ingestion	whole-string token IDs, 3 tokenizer families	fixed-byte control fails: drift at token 1800, 6 invalid UTF-8 leaves
Flatten	bytes equal original and control arm, all cells	op counts: 0 splits, 0 re-allocs, 0 re-hashes vs $\Theta$ (leaves)
Identify	byte-level scan, 162 checks	steps $=2\lceil\log_{2}N\rceil$ exactly, content-independent
Branch	fork materialization, all cells	node count deterministic (std $=$ 0), $O(\log w)$ per fork
Repeat	bytes and hash equal naive arm	node count $=$ unit $+$ 1 exactly
vs Ropey	byte-identity and maintained hash $\equiv$ recompute, every edit step	bit-flip on maintained hash fails the gate

TABLE III: Verification ledger across all studies. Every oracle comparison in the paper returned zero mismatches; negative controls (injected faults) confirm each gate is non-vacuous.

$r$ (queries/cycle)	$N^{*}$	100 K	1 M	10 M
1	1 K	47.6x	369.7x	2901.8x
0.1	10 K	5.3x	32.2x	265.0x
0.01	300 K	0.7x	3.8x	27.7x

TABLE IV: Query-to-edit ratio ablation against Ropey: per-cycle speedup (Ropey over hashrope ), nine runs per point, 9/9 paired at and above each crossover

N^{*}

. Below

N^{*}

Ropey wins.

Fig. 2: Edit-plus-identity workload, hashrope (Rust) against Ropey 1.6.1 with the same polynomial hash: per-cycle latency over buffer size, nine runs per point. Ropey’s cycle is dominated by the

O(N)

fingerprint recompute (slope 1.013); hashrope reads the maintained fingerprint in

O(1)

(slope 0.150), so the gap widens without bound, 9/9 paired at every size.

$N$ (tok)	hashrope (µs)	paged b16	speedup b16	b8
1 K	25.9	13.9 $\mu$ s	0.54x	0.64x
4 K	30.1	25.9 $\mu$ s	0.86x	1.30x
16 K	31.6	62.3 $\mu$ s	1.97x	3.87x
64 K	33.8	219.5 $\mu$ s	6.49x	11.6x
256 K	35.0	834.9 $\mu$ s	23.9x	44.9x
1 M	37.1	3.61 ms	97.4x	168.7x

TABLE V: Branch-creation latency against the paged copy-on-write baseline over context size, reference block 16, nine runs per point; all sizes 9/9 paired at 1 M for every block size.

$P$ (tok)	hashrope (µs)	paged b16 (µs)	speedup b16	b8
0	16.0	5.6	0.35x	0.40x
4 K	17.5	20.0	1.14x	2.14x
16 K	21.5	67.1	3.13x	7.81x
64 K	23.3	239	10.3x	20.9x
256 K	24.4	948	38.9x	74.6x

TABLE VI: Ecological replay of real 120B-model tree-of-thought search: branch-creation speedup (paged over hashrope ) by prepended prefix length

P

, nine runs per point; sub-crossover cells where the paged table wins are included.

Fig. 3: Branch memory against a faithful PagedAttention block-table copy-on-write baseline, five branches per context. The paged table is

\Theta(N/B)

per branch; hashrope adds an

O(\log w)

shared spine per branch, so compression grows with context size.

$L$	radix (ms)	hashrope (ms)	flat (ms)	speedup
1 K	0.034	17.83	0.003	0.00x
4 K	0.118	17.77	0.003	0.01x
16 K	0.462	14.32	0.006	0.03x
64 K	2.24	13.07	0.018	0.17x
128 K	3.82	15.57	0.038	0.25x
256 K	7.47	15.53	0.082	0.48x

TABLE VII: Single-query prefix identification against the vendored SGLang radix matcher over shared-prefix length

L

(tokens), mean over nine runs; the flat scan is the

O(L)

floor. Crossover near 571 K.

Fig. 4: Identification latency on the live stack over shared-prefix length, log-log, nine runs per point. The live-stack crossover

L^{*\prime}

is bracketed between 524,288 and 1,000,000 tokens; the dashed line is the crossover predicted in advance by the CPU-only study, which lands inside the bracket.

Cell	J/tok off	J/tok on	ratio	TTFT off $\to$ on
Realistic	2.48	0.110	22.7x	56 ms $\to$ 21 ms
$L{=}131\,K$	1555	22.3	69.6x	7.8 s $\to$ 0.22 s
$L{=}262\,K$	5258	35.0	150.4x	26.6 s $\to$ 0.47 s
$L{=}393\,K$	10901	50.1	217.6x	54.6 s $\to$ 0.67 s
$L{=}524\,K$	18131	65.3	277.6x	92.5 s $\to$ 0.87 s

TABLE VIII: Live-stack prefix-cache effect, mean over nine runs, all rows 9/9 paired with p

=

0.002. The reduction is the engine’s; the identity layer adds zero GPU work by construction.

Fig. 5: The engine prefix-cache effect on the live stack (top: GPU energy per generated token, cache off over cache on; bottom: time to first token), nine runs per point. The reduction, 69.6x to 277.6x across the sweep, is attributed to the vLLM cache, not to hashrope . The shaded region marks the dense-attention serving wall, beyond which the engine cannot prefill; identification (Fig. 4 ) keeps working there.

LLM Context Management

Large language model context management studies how to select, compress, retrieve, and organize information within bounded model inputs.

See all 250 papers

Akashic: A Low-Overhead LLM Inference Service with MemAttention
Jul 7, 2026Yang Liu, Zhaokai Luo, Huayi Jin +7LLM Serving Memory-Augmented Language Models
Xiaohongshu Inc., China · ShangHai JiaoTong University · Peking University
HHR: Hierarchical Hash Retrieval for Efficient LLM Generation
Oct 1, 2026Lianjun Liu, Tiantian Zheng, You Huang +5Long-Context Language Model Inference LLM Inference Acceleration
Hainan University, Haikou, China · Xiamen University, Xiamen, China · Zhejiang Normal University, Jinhua, China
InferScale: GPU-Native KV Injection for Personalized LLM Serving
Jul 29, 2026Peter Li, Prashant PandeyLLM Serving Memory-Augmented Language Models
Northeastern University Boston, Massachusetts, USA

Jul 7, 2026J/K move · Enter open · S save

Akashic: A Low-Overhead LLM Inference Service with MemAttention

Yang Liu, Zhaokai Luo, Huayi Jin, Ruozhou He+6

Xiaohongshu Inc., China · ShangHai JiaoTong University · Peking University

LLM Serving Memory-Augmented Language Models Memory-Efficient Inference LLM Context Management Memory-Augmented Language Model Agents

Open paper AskPDF arXiv

Recent LLM-based agent systems continuously accumulate context across multi-turn interactions, tool invocations, and cross-session workflows. Replaying the full history for every request quickly becomes impractical: long contexts increase prefill cost, may exceed context limits, and often bury task-relevant evidence in irrelevant content, degrading both serving efficiency and output quality. We propose Akashic, a low-overhead memory system built around MemAttention, which organizes context into bounded chunks and models semantic relationships across chunks, preserving cross-chunk evidence without repeatedly rewriting the full history. Akashic further applies hardware-software co-designed memory placement to co-locate likely co-retrieved chunks, reducing retrieval fragmentation and I/O overhead. Across four representative workloads and three model sizes, Akashic improves task accuracy by up to 10.2 points, throughput by up to 1.21x, and sustainable request rate by up to 1.88x over strong prior memory baselines.

Abstract

LLM Context Management

Explore similar work

Akashic: A Low-Overhead LLM Inference Service with MemAttention

HHR: Hierarchical Hash Retrieval for Efficient LLM Generation

InferScale: GPU-Native KV Injection for Personalized LLM Serving