PaperlayerView exact revision on arXiv

Source-linked AI summary

Budgeting Bytes: A Windowed Storage Roofline and Dual-Budget Architecture Ablations for Storage-Bound LLM Decoding

Hanhaodi Zhang

arXiv:2609.04238v1cs.AR

TL;DR

The paper asks how to design and accelerate autoregressive decoding when cheap hardware is constrained by storage bandwidth and RAM rather than FLOPs. It formalizes bytes-per-token and address determinism with a windowed roofline, evaluates dual budgets, and tests the framework on large-MoE deployment. The central result is that perfect expert prediction cannot overcome a saturated storage bus, whereas reducing bytes-per-token until the model fits the fast tier yields a measured 22× gain.

  • Problem

    Cheap-hardware decoding is governed by bytes moved per token across the slowest populated memory tier, but prior design and scaling approaches do not provide a theory for storage, prefetch windows, and address timing together.

  • Method

    The paper introduces an address-determinism taxonomy, a closed-form windowed roofline, dual-budget ablations across three sub-100M scales, and end-to-end large-MoE deployment measurements.

  • Results

    11.5 tok/s and a 22× jump result when Q2 K quantization fits the model in 16 GB unified memory, while perfect prediction provides no speedup on the bandwidth-saturated edge path.

  • Takeaways & Limitations

    Predictability becomes a throughput lever only when most of the model is cached in the fast tier and transfer time is comparable to compute; otherwise reducing bytes-per-token is the effective lever.

  • Takeaways & Limitations

    The large-MoE results are single-run per configuration, the Q2 K result measures throughput but not task quality, and the predictability boundary is charted on one A100 path and one edge board.

Abstract

from arXiv · show

Autoregressive decoding on cheap hardware is bound not by FLOPs but by the bytes each generated token must move across the slowest populated tier of a memory hierarchy. We treat bytes-per-token as a first-class design axis, organized by an address-determinism taxonomy that classifies parameters by when their fetch address becomes known during a token's forward pass (A0: at token sampling; A1: before attention; A2: layerwise data-dependent; A3: always read). This reduces prefetch scheduling to single-machine feasibility with release times, yielding a closed-form windowed roofline. We run dual-budget (bytes-per-token times storage) ablations across three sub-100M scales, then take the framework to real large-MoE deployment and report a substantial negative result the roofline predicts: on an 8GB edge board running Qwen3-30B-A3B (4-bit, 18GB), the model overflows RAM and decode is pinned at the eMMC bandwidth ceiling; predictive expert prefetch does not help -- not temporal-locality prefetch (net-negative), not even a trace-driven oracle with perfect prediction -- because the binding constraint is byte volume over a saturated bus, which prefetch cannot reduce. The lever that works is reducing bytes-per-token until the model fits the fast tier: quantized to fit a 16GB unified-memory device, the same model runs GPU-resident at 11.5 tok/s (22x). We reconcile this with GPU-serving expert-prefetch predictors: a frozen-model probe predicts Qwen3-30B routing from the pre-attention state at 91.2%, a scale-invariant predictability property, but this converts to throughput only where the fast tier caches most of the model and per-token transfer is comparable to compute -- measured to hold on an A100 PCIe-offload path and to fail on bandwidth-walled edge storage. Predictability is not speedup; we chart where the gap closes.

1 Introduction

The paper reframes cheap-hardware decoding around bytes moved per token and storage placement rather than FLOPs or parameter count. It contributes a windowed storage roofline, dual-budget ablations, and a validated toolchain for this regime.

  • Motivation: Cheap-hardware decoding is typically bandwidth-bound because each generated token performs roughly two operations per weight byte.Throughput therefore depends on bytes-per-token and whether storage-hierarchy transfers can be prefetched early enough to hide.
  • Motivation: A 28.9M-parameter model reaches 9.5 tok/s on an $8 ESP32-S3 when 25M parameters remain in flash and only ∼450 bytes per token are touched.Reading the same weights naively would reduce throughput to 0.4 tok/s.
  • Contributions: The address-determinism taxonomy turns prefetch scheduling into preemptive single-machine feasibility with release times and yields a closed-form hiding criterion.It unifies per-layer embeddings, lookup experts, and pre-attention routing.
  • Contributions: The study runs 23 dual-budget ablations across three sub-100M scales and validates a simulator against an MCU-class deployment with < 3% error.Microbenchmarks also find ternary quantization’s compute dividend is only 1.2× on multiplier-equipped cores, while its main value is byte halving.

2 Related Work

Prior work explores cheap-address lookups, expert swapping, static offload, and expert-activation prediction, but generally does not model bandwidth-aware prefetching across multi-tier storage. This paper places these mechanisms within a shared address-determinism and hiding framework.

  • Capacity via cheap-address lookups: Cheap-address lookup methods store per-token or context-indexed expert information in tables, but prior systems do not jointly model bandwidth, prefetching, and multi-tier storage.The paper identifies PLE and MoLE-LUTs as sharing the A0 access pattern while differing in value determinism.
  • MoE under constraints: SmallThinker overlaps expert fetch with attention, EdgeMoE manages expert swap-in, and empirical work reports MoE slowdown on Jetson-class hardware from footprint and dispatch.Theorem 1 interprets these outcomes as consequences of available hiding windows.
  • Production static offload: llama.cpp’s static offload keeps attention in fast memory and places expert FFN tensors in slow memory, reaching ∼30 tok/s on 6 GB VRAM plus 32 GB RAM.The paper adds theory for why this placement is near-optimal and where it breaks, along with an A0 tier.
  • Expert-prefetch prediction: Expert-prefetch predictors report 80–85% accuracy and ∼1.3–2× speedups in GPU-VRAM caching settings, but the CPU/edge streaming path remains unmeasured.This paper supplies a same-model/same-data paired A0-vs-A1 probe for that missing setting.
  • Scaling laws and quantization: FLOP-side scaling laws operate at ≥100M parameters, whereas this work prices effective capacity per byte class and adds calibration for the sub-100M storage-bound regime.The related quantization literature supplies 4-bit and ternary methods but does not establish this storage-bound calibration.

3 Taxonomy and the Windowed Roofline

The windowed roofline classifies weight groups by when their addresses become known, then tests whether their transfers fit within compute-time windows. This connects prefetchability, bandwidth, storage, and bytes-per-token through explicit feasibility conditions.

  • Taxonomy: Address-determinism classes range from A0, known at token sampling, through A1 and A2, to A3 weights that are always read.Each class receives a release time based on when its fetch address is revealed.
  • Windowed roofline: Theorem 1 states that all I/O is hidden exactly when every compute-timeline interval has sufficient bandwidth for transfers whose release and use times lie inside it.Otherwise, exposed latency equals the maximum interval deficit, and EDF attains that latency.
  • Windowed roofline: The feasibility problem is a preemptive single-machine scheduling instance with release times and deadlines, with compute time mapped to the I/O machine through measured parallelism.This supplies the scheduling basis for the theorem’s density condition and EDF optimality.
  • Corollaries: A1 windows decompose into per-layer inequalities, whereas A0 windows are maximal and tolerate the slowest storage; A2 bytes remain exposed on slow tiers.Longer context widens A1 windows and therefore helps prefetching.
  • Dual budgets: A device with bandwidth B and target rate R requires bpt ≤ B/R after hidden fractions, while flash imposes a separate storage cap.Precomputation can reduce bpt at the cost of maximal storage, so the two budgets are not interchangeable.
  • Capacity pricing: Effective capacity is decomposed as Neff ≈ NA3 + γ1NA1 + γ0NA0 to estimate exchange rates among address-determinism classes.The decomposition is introduced as a first-order ansatz based on equal-loss dense-equivalent parameter counts.

4 Experimental Setup

The experiments compare dense, routed, lookup-based, and PLE-augmented models under controlled training recipes across three sub-100M scales. They measure loss alongside analytically computed bytes-per-token and storage, with paired seeds for key comparisons.

  • Training setup: All variants train on TinyStories with an identical AdamW recipe, cosine schedule, 20k steps, batch 64, 512 context, bf16, and one A100 per run.The dataset contains 486M tokens and uses a 4k BPE vocabulary.
  • Model variants: The model families include dense networks, fine-grained top-2 MoEs with pre- or post-attention routers, and MoLE-style LUT experts, each MoE augmented with PLE.All variants share a trunk with RoPE, RMSNorm, and a tied head.
  • Scales and controls: Experiments cover approximately 6M, 16–24M, and 40–60M parameter scales, with RQ2 comparisons using seed-paired runs 1337, 42, and 7.Bytes-per-token and storage are computed analytically at 4-bit weights.
  • Generality: The setup also tests a MiniMind-3-shaped model with d768, 8 layers, a 6.4k vocabulary, coarse 4×top-1 MoE, and 328M tokens of Chinese text.This extends the main recipe beyond the TinyStories configurations.

5 Results

Across hardware and model scales, the experiments test whether storage-aware design choices improve loss, throughput, or both. Pre-attention routing preserves quality and creates a hiding window, while activation sparsity can hurt small models despite reducing computation.

  • Kernel and activation results: 1.20× over int4 was achieved by ternary kernels using a branchless LUT.Branching kernels were 6× slower.
  • Routing comparisons: Four of four paired comparisons favored pre-attention routing across the 24M and 60M comparisons.The differences were not significant, indicating that the A1 prefetch window costs little at these scales.
  • Routed-capacity valuation: γ1 ranged from 0.12 to 0.35 across scales and fit variants, indicating routed bytes were worth roughly a fifth of resident bytes.The authors report the range because the dense-fit parameter E is weakly identified, while γ1 ≪1 remains robust.
  • Frontier overview: The quality–bpt frontier spans d256, d384, and d512, with A0 series storage 6–10× larger.Conditional capacity dominates the starved end, while dense models dominate the affluent end.

5.4 The A0 corner is Pareto-dominated here

At sub-100M scale, storage-heavy A0 lookup experts are not Pareto-efficient under the joint quality, bytes-per-token, and storage budgets. Smaller pre-attention MoE models instead occupy a better frontier, especially when bytes are scarce.

  • A0 lookup experts: +0.17–0.19 loss is incurred by LUT experts versus same-scale dense models across the tested span.The storage cost is 6–10×, with losses of +0.171, +0.191, and +0.165 at 9M, 24M, and 60M.
  • A0 lookup experts: The 9M pre-attention MoE beats the 24M LUT variant simultaneously on loss, bpt, and storage.The reported values are 1.497 versus 1.533 loss, 1.87 versus 3.16 MB bpt, and 4.3 versus 52.7 MB storage.
  • Dual-budget interpretation: Single-axis bpt optimization is actively misleading in this regime.The LUT comparison shows that reducing bytes per token alone can trade away too much quality and storage efficiency.
  • Frontier reading: At bpt < 3 MB, pre-attention MoE+PLE reaches 1.4969 at 1.87 MB versus dense 1.5212 at 2.73 MB.At approximately 5 MB, the design trades 35% lower bpt for a 0.005–0.010 loss increase and roughly 1.5× bandwidth-bound decode speed.
  • Generality and routing placement: The MiniMind-shaped A2 MoE has the same 32.7 MB bpt as dense, so its byte axis provides no benefit.Moving routing before attention improves loss by 0.022 in the coarse shape, while PLE adds a further 0.013; the fine-grained split differs.

5.7 Real-tier deployment: an end-to-end accounting check

The deployment experiments validate the roofline across compute-bound and I/O-bound hardware, then show that routing predictability helps only when expert I/O can be hidden. Device bandwidth, access granularity, and model fit determine whether prefetch changes throughput.

  • USB storage validation: 5.28 tok/s was predicted using 26 MB/s effective bandwidth, within 1.5% of measurement.Approximately 40 scattered requests per token produced granularity efficiency η ≈0.68; the sequential-bandwidth roofline overestimated throughput at 7.7 tok/s.
  • Hardware regime comparison: 94.5 tok/s was achieved on the RK3588 because the 23 MB model fit in 7.5 GB RAM and the run was compute-bound.Overlap added only 12% over serial execution, while measured eMMC bandwidth ranged from 277 MB/s sequential to 42 MB/s at 4 KB granularity.
  • Predictive prefetch: A1 probes hide 83% of expert wait on slow storage, compared with 59% for A0 probes.The expected exposed expert I/O is modeled as (1 − p)s/B under Theorem 1.
  • Information versus time: Temporal-locality prefetch reached only 18.8% and 28.7% on the fine-grained and coarse models, respectively.The experiments attribute the useful 83% predictability to the current token’s pre-attention hidden state rather than previous-token expert reuse.
  • Production routing predictability: 91.2% average top-8 hit rate was reached for Qwen3-30B-A3B from pre-attention hidden states.This was measured on 3.6k documents, versus a 6.2% random baseline, but the result establishes predictability rather than speedup.
  • Deployment planning: Strata projects Qwen3-30B-A3B on an 8 GB RK3588 with eMMC at 0.2 → 2.7 tok/s from static offload to prefetch.The planner uses RAM, slow-storage bandwidth, measured granularity efficiency η, and the windowed roofline.

5.9 Over-training moves the frontier

Under a bytes-per-token constraint, a smaller conditional-capacity model trained far beyond Chinchilla can approach dense-model quality while streaming substantially fewer bytes per token.

  • 1.2524 loss after 100k steps and approximately 3.3B tokens improves the 24M A1+A0 model from 1.3489.This reaches within 0.013 of the 40M dense model's 1.2397 loss at its Chinchilla-scale budget.
  • The 24M A1+A0 configuration streams 4.84 MB per token versus 18.8 MB for the 40M dense model.That is 3.9× fewer bytes per token while approaching the dense model's loss.
  • When decode speed is binding, training a smaller conditional-capacity model far past Chinchilla is the reported winning move.The paper presents this as a storage-bound instantiation of inference-aware scaling.

5.10 Large-MoE deployment: a measured negative result and the fit-first lever

The large-MoE deployment shows that predictive prefetch cannot overcome bandwidth saturation when the model overflows fast memory; reducing bytes per token until the model fits is the effective lever.

  • Measured negative result: The 18 GB Qwen3-30B-A3B model overflows the 8 GB RK3588, forcing experts to stream from eMMC at 0.19 tok/s.At 40960 context, the KV cache reserves approximately 3.75 GB; reducing context to 2048 frees RAM and raises decode to 0.51 tok/s.
  • Measured negative result: Perfect expert prediction provides no speedup, changing throughput only from 0.12 to 0.13 tok/s.Temporal-locality prefetch is net-negative, falling from 0.19 to 0.12 tok/s at a 46.7% top-8 hit rate.
  • Measured negative result: At approximately 277 MB/s, the device is already at the eMMC sequential ceiling, so prefetch changes byte timing but not per-token byte volume.Each token reads approximately 500–900 MB, leaving no scheduling solution once the bus is saturated.
  • Fit-first lever: Quantizing Qwen3-30B-A3B to Q2 K reduces the model to 11 GB, fitting the M4's 16 GB unified memory and enabling GPU-resident decoding at 11.5 tok/s.This is a 22× increase over the eMMC-overflow baseline; at 4-bit and 18 GB, the model still overflows the 16 GB device and runs at 1.2 tok/s on Metal.
  • Predictability boundary: Predictive prefetch pays only when the fast tier caches most of the model and transfer remains comparable to compute.The paper identifies this intermediate regime on an A100 offload path, while bandwidth-walled edge storage sits below it and a fully fitted model sits above it.

6 Limitations

The paper's evidence is constrained by limited seeds, calibration assumptions, single-run deployment measurements, and incomplete coverage of the intermediate predictor regime.

  • Dense seed variance is ±0.013 with n=2, exceeding MoE variance, so cross-architecture deltas below approximately 0.01 require paired designs.The paired-design requirement is used for RQ2.
  • The compute-time model is calibrated at a single anchor, while γ linearity is a first-order ansatz for one 8×top-2 granularity.The estimate is reported as a range rather than a point.
  • Large-MoE deployment results are single-run per configuration, and the Q2 K fit result measures throughput and coherence but not 2-bit task quality.The fitted-tier result therefore does not establish quality preservation under 2-bit quantization.
  • The predictor boundary is measured on one A100 offload path and one edge board, while the intermediate regime is inferred from endpoints rather than swept end-to-end.The intermediate regime is defined by a large but incomplete fast-tier fraction with transfer comparable to compute.
  • The roofline addresses autoregressive decoding and does not cover non-autoregressive workloads such as TTS or diffusion.

7 Conclusion

The paper formulates storage-bound decoding around bytes per token and address determinism, then uses the resulting roofline to identify when prefetch is futile and when fitting the model in fast memory is decisive.

  • The framework combines a scheduling theorem, a per-byte exchange rate, and dual storage and bytes-per-token budgets into a precomputed device frontier.Address determinism determines which bytes can be hidden during the forward pass.
  • When a model overflows the fast tier onto a bandwidth-saturated bus, no prefetch schedule, including a perfect oracle, improves throughput.The bottleneck is byte volume rather than access pattern.
  • Reducing bytes per token until the model is resident enables ordinary compute acceleration, producing a measured 22× improvement.The paper reports this as the effective lever in the large-MoE deployment.
  • Routing prediction is useful only in the intermediate regime where most, but not all, of the model fits in the fast tier and the tier boundary is critical.The roofline's practical value is identifying the device regime before optimizing the wrong bottleneck.
Loading 2609.04238v1…