Paying Once Per Patient: Linear-Time Attention for Private Synthesis of Full Health Histories

Hospitals want to share realistic fake patient records, called synthetic data, so that others can build models without seeing real people. The standard tool for a formal guarantee is differential privacy (DP), a promise that the released generator would look almost the same whether or not any one patient was in the training set. In practice this is enforced with DP-SGD: each patient's gradient is clipped to a fixed size and Gaussian noise is added before every update. The privacy cost is charged per patient, every time that patient's data touches a training step.

Here is the problem. Real longitudinal records are long. EHRSHOT patients have about 95 times more encounters than MIMIC-IV patients (EHRSHOT). The sequence generators in this area use standard attention, whose cost grows with the square of sequence length. That pushes practitioners to cut each history into short windows. Under patient-level DP, a model that sees one window of a patient still pays that patient's full privacy price, and everything outside the window is discarded for that step. We propose to remove the waste by building the generator from linear-time attention, a family of attention layers whose cost grows only linearly with length because they summarize the past in a fixed-size memory matrix. Each sampled patient then contributes their entire history to a single clipped gradient, at a per-token cost that stays flat however long the history gets.

Core Claim

At a fixed privacy budget ε and a fixed compute budget, a generator that trains on whole patient histories with linear-time attention will produce synthetic data with better long-range fidelity and better downstream utility on long-horizon prediction tasks than either of the two alternatives available today. The first alternative is a softmax-attention generator trained on one sampled window per patient. The second is a softmax-attention generator trained on full histories but given fewer steps to stay within the same compute budget.

The mechanism is accounting, not architecture for its own sake. DP-SGD utility depends heavily on how many noisy steps over how many patients one can afford. Quadratic attention makes full-history steps expensive, and truncation makes cheap steps uninformative. Linear attention is the one design that makes the full-history step both cheap and complete.

A second, scientific claim is attached. Delving into Differentially Private Transformer shows that DP noise makes softmax attention over-attend to rare tokens ("attention distraction"), because the exponential magnifies noisy scores. DyDiLA shows the opposite failure in linear attention: without the exponential, attention becomes too uniform ("oversmoothing"). Nobody has measured which failure dominates when DP noise meets linear attention. Rare clinical codes are exactly where this matters, so we treat it as a measured secondary question rather than an assumption.

Relation to Prior Work

The motivating work is private EHR synthesis. IGAMT builds a sequence-to-sequence Transformer autoencoder that handles mixed data types, missingness masks and irregular time gaps. It avoids end-to-end DP by applying noise only to a separate "imitator" network. We keep its handling of irregular time and missingness, but train the generator itself end-to-end under DP at full history length, which IGAMT's quadratic attention makes impractical. GHOSTS supplies a fidelity metric (normalized Wasserstein distance) and a utility protocol (train on synthetic, test on real) for hospital time series, which we adopt.

The method comes from the linear-attention literature. Lightning Attention / TransNormerLLM shows constant training speed from 1k to 128k tokens using block tiling. It also reports that learnable decay rates are numerically unstable, which led its authors to fixed decays per head. We expect DP noise to worsen that instability, so we inherit the fixed-decay design deliberately. BASED pairs a Taylor-approximated linear attention with a small exact sliding window to recover the ability to look up specific earlier facts. Its generation throughput is 24x that of FlashAttention-2, which makes sampling large synthetic cohorts cheap. Because sampling is post-processing, it costs no extra privacy, the same property DistilDP relies on. The delta-rule update analyzed by Irie et al. lets the memory overwrite stale associations, solving Reset Dyck-1 where plain accumulation fails. A patient's history has similar reset structure: a new admission supersedes old status.

Some work constrains what we claim. Differentially Private Learning Needs Hidden State proves that privacy loss saturates when intermediate optimization iterates are hidden. It is tempting to say the linear-attention memory matrix is such a hidden state, but that memory is a forward-pass activation inside one example, not a training iterate. We therefore claim no privacy amplification from it and use standard DP-SGD accounting. Tangent Transformers linearizes a Transformer in its weights to make DP fine-tuning convex for image classification. Its attention remains quadratic in length, so it addresses a different axis. For clipping, we reuse Phantom Clipping from Delving into Differentially Private Transformer. It is 4 to 100 times faster than Ghost Clipping and handles shared embeddings, which matters because our code-embedding table is tied to the output layer.

Research Program

Generator. We will build a decoder-only generator over event tokens. Each event is a token for its clinical code, a binned value, and a binned time gap since the previous event, preceded by static demographic tokens as in IGAMT. Each layer combines three pieces:

  • a chunkwise gated linear attention with fixed per-head decay, trained with Lightning-style tiling;
  • an optional delta-rule update;
  • a 64-token exact sliding window, as in BASED.

Activation checkpointing at chunk boundaries keeps training memory linear in history length.

Privacy accounting. The privacy unit is the patient. Each DP-SGD step works as follows:

  1. Sample patients by Poisson sampling.
  2. Compute each sampled patient's whole-history gradient.
  3. Clip that gradient as one unit.
  4. Add Gaussian noise.
  5. Track the total privacy cost with a standard moments-style accountant.

Gradient accumulation lets us reach the large logical batches DP needs without exceeding memory.

Analysis. We will measure attention entropy and attention mass on rare codes during DP training, comparing softmax and linear layers at matched ε. This tells us whether DP noise pushes linear attention toward oversmoothing or whether removing the exponential spares it from distraction. If oversmoothing appears, we will test a token-difference operator in the style of DyDiLA as a targeted fix. If it does not, the architecture stays simple.

Baselines

Naive reference points. One is a model trained directly on real data with no privacy, which gives the utility ceiling. The other is the downstream task trained on nothing synthetic, meaning a count-feature gradient-boosting model fit on the few labeled EHRSHOT shots alone. EHRSHOT reports that such count-based models match or beat its 141M-parameter autoregressive model (CLMBR-T-base) on long horizons once there are more than 64 shots. A synthetic cohort that cannot beat this floor has no reason to exist.

Strongest existing private EHR generator. This is IGAMT, run on MIMIC-IV-ED with its released design. The file reports 82% train-on-synthetic accuracy for blood-pressure classification versus 80.5% for training on real data (IGAMT). We will reproduce that task and match ε. Beating IGAMT means reaching at least parity on this short-history task, where we expect no advantage, and clearly exceeding it on long-history fidelity and EHRSHOT tasks. For EHRSHOT trained on DP synthetic data, no reported result was found on Lacuna, so all numbers there will be new.

For non-private faithfulness, GHOSTS reports a train-on-synthetic SOFA-score AUROC of about 0.80, against about 0.79 for real data and about 0.74 for DoppelGANger. We use it as a fidelity reference, not a privacy-matched competitor.

Truncated softmax and full-history softmax. These are the most important competitors because they test the core claim directly. Both use the same decoder, tokenizer, Phantom Clipping, ε, δ, accountant and hyperparameter search budget, with FlashAttention-2 replacing linear attention.

  • In the truncated variant, each sampled patient contributes one random window of length 512 to 2k. This is still patient-level DP.
  • In the full-history variant, each patient contributes their whole history, with steps cut so total GPU-hours match.

Our claim is beaten if either matches our model on the long-horizon metrics below.

Mamba. A state-space model with the same parameter count and training protocol tests whether any linear-time recurrence suffices. On recall-heavy benchmarks BASED beats Mamba by 10.36 points at 1.3B parameters (BASED).

Ablations isolating the key ingredient. The first keeps our architecture but trains on single windows. It separates "whole-history gradient" from "linear attention." The second removes the linear component, leaving only the sliding window. It tests whether long-range memory is actually used.

Why not just…?

Why not just use FlashAttention-2 on full histories? FlashAttention keeps memory linear, so full histories are feasible. The cost is that compute stays quadratic, and under a fixed budget that means fewer DP steps. Lightning Attention keeps constant speed to 128k where FlashAttention-based LLaMA slows sharply (Qin et al.). Whether this compute gap translates into a utility gap at EHR history lengths is an empirical question, not a given. The compute-matched full-history softmax baseline settles it, broken down by patient history length. If the gap does not grow with length, our central claim is wrong.

Why not just truncate to recent windows, since long-horizon information may live in simple counts? This is a real threat. EHRSHOT's finding that count models win at long horizons suggests long-range detail may not matter much. We answer it two ways. We report the truncated baseline on EHRSHOT's long-horizon tasks. We also directly measure long-range fidelity: the agreement between real and synthetic co-occurrence of codes separated by more than a year. If truncation matches us on both, the honest conclusion is that full histories are not worth their cost for these tasks.

Why not just synthesize a count-feature table with a DP marginal method like AIM? AIM gives clean DP guarantees and needs no neural network (FHAIM). If downstream users only fit gradient-boosting models on counts, it may be enough. It cannot, however, yield sequences for training sequence models, and it cannot represent time order or irregular gaps. We will run AIM on an EHRSHOT count table as a baseline. We will also report where it wins, which is likely on count-based downstream models at large ε.

Why not just use Mamba? It shares linear cost. The BASED results suggest weaker lookup of specific earlier facts, but those results come from language, not EHR data. The matched Mamba baseline will show whether that weakness survives DP noise on clinical sequences.

Proposed Experiments

We will use three datasets, each for a different purpose:

  • MIMIC-IV-ED: short histories, for comparison with IGAMT.
  • MIMIC-IV: scale, more patients.
  • EHRSHOT: long histories, with its 15 few-shot tasks and its patient splits. The generator is trained only on training-split patients.

EHRSHOT has only 6,739 patients, so tight ε will be hard. We will report ε of 1, 4 and 8 with δ well below one over the number of patients, and state plainly where utility collapses.

We will report four kinds of metrics:

  • Utility: train-on-synthetic, test-on-real AUROC on all 15 EHRSHOT tasks, and blood-pressure accuracy on MIMIC-IV-ED.
  • Fidelity: code-frequency error, normalized Wasserstein distance on vitals, and the long-range co-occurrence statistic described above. All are stratified by history-length quartile.
  • Privacy, audited empirically: membership-inference AUC, exposure of inserted canary patients (following the canary tests of Yu et al.), and nearest-neighbor exact-collision rates in the spirit of TableGAN-MCA.
  • Cost: GPU-hours for training and patients generated per second.

Three checks are decisive:

  1. At matched ε and compute, our model must beat both softmax variants on long-horizon fidelity and on long-horizon EHRSHOT tasks. The margin must widen in the top history-length quartile.
  2. The whole-history ablation must account for most of that gain. If the window-trained linear model performs as well, the benefit came from the architecture rather than from paying once per patient, and the paper's thesis changes accordingly.
  3. The attention diagnostics must show whether DP noise causes distraction in softmax layers and oversmoothing in linear layers, measured on rare codes. Whichever way this falls, it is a reportable result that neither prior line of work has measured.