Quantizing Graph State-Space Models by Where Errors Travel in the Scan

Graph Mamba-style models turn a graph into a sequence and run a fast linear recurrence over it. They first sort nodes into a line, typically by degree (number of connections) or PageRank. They then scan that line with a state-space model, a recurrent layer whose state update $h_t = A_t h_{t-1} + B_t x_t$ has no nonlinearity. That linearity lets the whole sequence be computed in logarithmic depth with a parallel prefix scan. These models are memory-light and accurate on long-range graph tasks, but nobody has made them low-precision. The two literatures that should guide this disagree. Graph quantization work gives hubs (high-degree nodes) the most bits because their errors spread to many neighbors. State-space quantization work finds that the scan itself amplifies small errors, regardless of which tokens they came from.

The claim of this note is that in a graph state-space model, a token's sensitivity to rounding is set by two things together: how noisy its representation is, which depends on topology, and how far its error travels through the scan, which depends on its position in the imposed ordering and the learned decay rates. The second quantity has a closed form. It can be estimated offline and favors different tokens than degree alone does. The ordering also gives a hardware benefit: the graph is already sorted by degree before the scan, so a degree-and-position-aware bit budget becomes a few contiguous blocks of the sequence. Each block runs a uniform-precision scan kernel, which avoids the per-node divergence that has kept topology-aware mixed precision confined to custom accelerators.

What is already known and what is missing

On the graph side, two papers supply the motivation and part of the method. A²Q learns per-node bitwidths in message-passing networks, giving more bits to nodes that aggregate more information, and reaches an average of 1.70 bits per feature on Cora. MEGA shows that in-degree predicts quantization sensitivity. Both assume errors move along graph edges. In a graph state-space model they also move along the scan, which these papers do not model.

A competing paper complicates this picture. Fograph shows that summing many incoming neighbors averages out zero-mean quantization noise, so hubs can tolerate coarser communication. We take this seriously rather than set it aside. Our model separates the two effects: averaging governs the noise in a token, and the scan governs where that noise goes. The tension then becomes a testable decomposition instead of a contradiction.

Better Schedules for Low Precision Training constrains the design. It finds that graph networks tolerate low precision only if accumulation stays high precision, so we never quantize the scan's running accumulator below 16 bits within a block.

On the sequence side, three papers supply the scan analysis and our strongest baselines. MambaQuant identifies the parallel scan as an outlier amplifier. It fixes the problem with variance-aligning rotations and reports 75.6% on Vim-T at 8-bit weights and activations (W8A8), where QuaRot reaches 59.3%. Quamba2 sorts and clusters channels offline, searches per-layer precision, and compresses cached states to 8 bits, with a 1.6% average zero-shot drop on Mamba2-8B. Both treat every sequence position identically and were evaluated only on text and images. Sequential Parallel Duality in Prefix Scannable Models gives the tree-structured view of the scan but does not study rounding. Resurrecting RNNs shows diagonal recurrences with $|\lambda|\le 1$ are stable, which keeps our influence quantity bounded.

Finally, Graph Mamba supplies the host architecture: random-walk neighborhood tokens, degree- or PageRank-sorted ordering, and a bidirectional selective scan. It runs only in 16- or 32-bit floating point. Its temporal and heterogeneous relatives, such as DyG-Mamba and HeteGraph-Mamba, are likewise unquantized.

Core Claim

For a diagonal recurrence, a rounding error $e_i$ injected into token $i$'s scan input reaches the state at a later position $t$ as $\big(\prod_{j=i+1}^{t} A_j\big) B_i e_i$. Summing the squared reach over both scan directions gives an influence score

$$S_i = \sum_{t} \Big\| \prod_{j \text{ between } i,t} A_j \, B_i \Big\|^2 ,$$

where $A_j$ are the input-dependent diagonal decays and $B_i$ is the input projection at token $i$. If token $i$ is quantized at $b_i$ bits with step size proportional to its range $\Delta_i$, the expected output error is approximately $\sum_i S_i \Delta_i^2 2^{-2b_i}$. Minimizing this under an average bit budget $\bar b$ gives the standard reverse water-filling rule

$$b_i = \bar b + \tfrac{1}{2}\log_2 \frac{S_i \Delta_i^2}{\mathrm{GM}(S\Delta^2)},$$

where $\mathrm{GM}$ is the geometric mean over tokens. The topology enters through $\Delta_i$: averaged neighborhood tokens of hubs have small $\Delta_i$, as Fograph's argument predicts. It also enters through $S_i$, because the degree sort decides whether hubs sit early, where errors travel far, or late, where they die quickly.

The new elements are this product form, its use for allocation, and one structural fact. In a degree-sorted sequence, $S_i\Delta_i^2$ varies smoothly enough along the sequence to be approximated by a piecewise-constant bit assignment over a handful of contiguous segments.

Research Program

Measurement study. We train Graph Mamba models in floating point and calibrate $S_i$ and $\Delta_i$ on held-out graphs. We average $S_i$ within degree bins, because the decays are input-dependent and must be computable offline, and degree is already computed at inference for the ordering. We then inject controlled rounding into one token or block at a time and measure the output error. The first question is whether $S_i\Delta_i^2$ predicts measured per-token sensitivity better than degree alone (the MEGA/A²Q prior) or range alone (what per-token dynamic scaling captures).

Allocation algorithm. We solve for segment boundaries and per-segment bitwidths by dynamic programming over the degree-sorted sequence. The candidate weight-and-activation precisions are 2, 4 and 8 bits. The scan state carried between chunks stays at 8 bits, following Quamba2's finding that cached states are redundant. Accumulation inside chunks stays at 16 bits. Channel handling reuses Quamba2's offline sort-and-cluster, applied separately within each segment, because hub and leaf tokens have different outlier channels. Everything is post-training, with an optional short quantization-aware fine-tune as a secondary experiment.

Kernel. We implement the block-uniform scan as a chunked kernel in which each chunk has one precision. Speed and memory are measured on a commodity GPU and on a Jetson-class edge device, the platform Quamba2 used.

Baselines

The reference points are the floating-point Graph Mamba model and naive uniform W8A8 and W4A8 round-to-nearest quantization of the same checkpoint. The naive version tells us whether graph state-space models are fragile at all. No reported result was found on Lacuna for any quantized Graph Mamba, so these numbers must be produced here. The floating-point targets from the Graph Mamba paper are 0.7071 average precision on Peptides-Func and 0.8769 accuracy on Roman-Empire.

The strongest existing competitor is Quamba2's full pipeline (sort-and-cluster plus evolutionary per-layer precision search), ported unchanged to Graph Mamba. It is the most complete post-training method for selective state-space models and already deploys on edge hardware. Its reported result is a 1.6% average zero-shot drop at W4A8 on Mamba2-8B, a text model. We also run MambaQuant's rotation pipeline, which reported 75.6% versus QuaRot's 59.3% on Vim-T at W8A8. A degree-only allocation in the style of A²Q and MEGA, with bits set by degree bin and no scan term, completes the set of baselines.

For fairness, all methods use the same checkpoints and the same calibration graphs. Each gets an equal search or tuning budget, measured in calibration forward passes, and all comparisons are made at matched average bits per token including scale overhead.

Two ablations isolate the proposal's ingredients. The first keeps our segmentation but drops $S_i$, testing whether the scan-influence term matters. The second keeps per-token water-filling bits but removes the contiguity constraint. This shows what block-uniformity costs in accuracy and gains in speed.

We count the proposal as beating Quamba2 if it achieves at least half the accuracy gap closure at 4-bit average on Peptides-Func and Roman-Empire. It must also show no throughput loss relative to uniform W4A8 on ogbn-arxiv, where the floating-point model uses 3.85 GB per the Graph Mamba paper.

Why not just…?

Why not just use per-token dynamic activation scales? This is the most serious threat. Hub tokens differ from leaves mainly in magnitude, and per-token scaling adapts to magnitude for free. It cannot see $S_i$, though: two tokens of equal range at opposite ends of a long decay chain receive equal precision. The decisive test is the measurement study. If range alone predicts injected-error sensitivity as well as $S_i\Delta_i^2$, the scan term is unnecessary, and we would refocus the work on the contiguous-block kernel alone.

Why not just port Quamba2 or MambaQuant unchanged? They might work well, which is why they are the main baselines. Their allocation is uniform over sequence positions, and MambaQuant's KLT rotation is calibrated offline per channel, not per position. Neither can exploit the fact that the graph ordering tells us in advance which positions carry hubs. If Quamba2 matches us at equal bits, the proposal's claim fails.

Why not just keep the scan inputs and state in 16 bits and quantize only the projections? Much of the memory sits in the projection weights, so this might capture most of the savings. We run this configuration explicitly and report its accuracy and memory. The proposal is only worth it if quantizing scan inputs to 4 bits or fewer by segment yields meaningful additional memory or throughput at equal accuracy.

Why not learn per-node bitwidths with quantization-aware training, as A²Q does? Learned per-node bits scatter precision across warps on GPUs, and A²Q's own speedups come from a bit-serial accelerator. We include a learned-bits variant with a matched fine-tuning budget. If it wins on accuracy but loses on speed, that is the trade-off the contiguity constraint is designed to resolve.

Decisive Checks

The cleanest falsification test reverses the node ordering, placing hubs at the other end of the scan. If sensitivity follows degree alone, the high-precision segment stays on the hubs. If $S_i$ matters, the optimal segment boundaries shift and the measured error shifts with them, and the shift should match the influence-score prediction.

Second, on Peptides-Func, Roman-Empire, graph MNIST/CIFAR10 and ogbn-arxiv, we plot accuracy against average bits for all baselines. The question is whether our curve dominates Quamba2's below 4 bits.

Third, we report end-to-end latency for block-uniform versus per-token mixed precision on GPU, measured with the same kernel. This tests whether contiguity actually removes the divergence penalty.