Stranded Credit: Why Amortized Bounds Fail Under Persistence and Laziness

A potential argument has a premise that is easy to miss: the credit it accumulates is stored inside the data structure, and it is spendable only by later operations on the same mutable object. Persistent data structures keep every earlier version alive. Lazy structures defer work to a future consumer. In both cases credit can be created in a version nobody will touch again, or held by a thunk that may never be forced. The classic bounds are not false in those settings; they are simply no longer proved by the classic argument, and applying the argument anyway yields claims that fail on ordinary inputs.

The premise, stated in terms of the array

With n elements and capacity c, take Φ = 2n − c. An append that triggers a reallocation has true cost 1 + c and changes the potential by 2 − c, so the amortized cost is 3. The copies are paid for by potential accumulated in earlier operations on the same array. The accounting is legitimate because there is one array, and every operation sees the potential left behind by its predecessor.

Now make the array persistent and let an earlier version remain reachable. An update produces a new array sharing a prefix with the old one, and there are two ways to implement it, both of which break the accounting, in different directions.

The naive persistent array copies the whole buffer per update, at Θ(n) each; there is no amortization to do, and the structure is honestly expensive. The efficient persistent array is a tree: a radix-balanced trie indexed by the bits of the position, with an update cost of Θ(log n) in the word-RAM model, or Θ(log₃₂ n) when nodes branch 32 ways and n is counted in words. No operation in the trie is rare and expensive, so the ephemeral potential argument never gets a purchase. The structure has traded an amortized average for a uniform worst case.

The trade appears in the other direction as well. An implementation that keeps a small mutable change buffer and rebuilds it occasionally has a sound amortized bound as long as there is one buffer. A persistent version must either copy the buffer into each new version or share a mutable one. Sharing makes versions interfere and is a correctness bug; copying forfeits the saving. There is no persistent analogue of the statement “the potential belongs to the object” once the object has successors that outlive it.

Suspending the work relocates the cost

Laziness breaks the argument from the other side. A value may be represented by a thunk: a computation that runs at most once, the first time its result is demanded, with the result memoised. A structure can then perform expensive work speculatively, hoping someone demands it later.

The classic illustration is the queue built from two lists: a front list that is dequeued from and a rear list that is enqueued onto in reverse. An enqueue pushes onto the rear in O(1); a dequeue takes from the front; when the front runs empty, the rear is reversed, at Θ(n). The strict ephemeral version has an amortized O(1) bound. The persistent version is O(n) per operation in the worst case, because the version that paid for the reversal may never be used and the version that needs the reversed list may be one of several successors, each of which would have to trigger its own reversal.

The lazy version suspends the reversal, so enqueue is O(1) and the reversal runs when the front is first demanded, and a single operation can then cost O(n). The standard repair is incremental: keep a schedule list alongside the front, and perform one incremental step per operation. The bound becomes O(1) worst case per operation rather than O(1) amortized, and it survives persistence because no operation does more than a constant amount of work.

data Queue a = Queue [a] [a]   -- front in order, rear in reverse order

empty :: Queue a
empty = Queue [] []

-- O(1): the element joins the rear list.
enqueue :: a -> Queue a -> Queue a
enqueue x (Queue f r) = Queue f (x : r)

-- O(1) amortized: the reversal happens inside the dequeue that empties the front.
dequeue :: Queue a -> Maybe (a, Queue a)
dequeue (Queue (x : xs) r) = Just (x, Queue xs r)
dequeue (Queue [] r) = case reverse r of
  []     -> Nothing
  y : ys -> Just (y, Queue ys [])

The strict version pays for the reversal inside whichever dequeue finds the front empty, which is why its bound is amortized rather than per call: that one call performs Θ(n) work while its neighbours perform constant work. Scheduling the rotation one step at a time removes the spike, and what makes the schedule work is a length relationship: the schedule is at least as long as the rear list at the moment the rotation begins, so the rotation finishes before the elements it produces are needed as a front. The reversal’s total cost is then charged to the operations that ran while the rear was growing, and since each of them performs its own step, no operation is left holding a debt. This is the general technique, from amortized to worst case by incremental scheduling. The same transformation applies to a run of cheap steps that occasionally becomes a long one, such as the carry chain of a binary counter: spreading the carry across the increments that follow replaces the amortized bound with a bound on each call.

The failure is stranded credit, not persistent memory

The problem has a crisp name: stranded credit. In the ephemeral argument an operation deposits potential into the state and a later operation on that same state withdraws it. Persistence creates states that are never visited again, so deposits made in them are lost, and the withdrawal that was supposed to fund the work never occurs in the branch of history that continues.

A small accounting makes the loss concrete. Take a structure whose amortized cost of 3 per operation comes from a potential in [0, n], and suppose the structure is copied at a moment when the potential is at its maximum. The copy inherits the full potential; the original is frozen at that potential and can never release it. Operations on the copy begin with a deposit already at its peak, having paid nothing for it: the deposit was earned by operations on the abandoned original. Any bound stated for the copy’s own sequence of operations has to start its accounting from the copy point, so the inherited term is either lost from the proof or must be restated.

class Buffer:
    """Ephemeral buffer with amortized O(1) append via geometric growth."""
    def __init__(self, capacity):
        self.cells = [None] * capacity
        self.size = 0
        self.capacity = capacity

    def append(self, x):
        if self.size == self.capacity:        # rare, O(size)
            self.cells += [None] * self.capacity
            self.capacity *= 2
        self.cells[self.size] = x
        self.size += 1

    def copy(self):
        b = Buffer(0)
        b.cells, b.size, b.capacity = list(self.cells), self.size, self.capacity
        return b

a = Buffer(1)
for i in range(8):
    a.append(i)      # amortized O(1) across the sequence
b = a.copy()         # b inherits capacity but earned none of the credit
b.append(8)          # b's first append may pay a full copy

The final line is the failure in concrete form. b begins life exactly at the capacity at which a was about to reallocate, so b’s first append pays the whole copy. Over a sequence of appends on b alone the amortized bound holds again; over a sequence that interleaves append and copy, the copies push the structure onto its reallocation boundary arbitrarily often, and the argument for b’s own appends no longer bounds the total, because the boundary was inherited rather than earned.

This is why the persistence literature carries explicit caveats about which operations may be amortized. The classical persistence constructions pay for the generalization by tracking versions and copying nodes on access, and they do not claim that an ephemeral amortized bound lifts automatically.

Three statements that do survive

Picking between them is the design decision.

Worst case per operation states a bound for every single operation with no averaging. It is the strongest claim, composes freely with persistence, and is what the purely functional structures aim at. Its cost is that a structure which would be O(1) amortized often becomes O(log n).

Amortized along one version path states the bound for a sequence of operations following a single line of descent through the version tree. It is weaker than it looks, because callers hold references to arbitrary versions, and a bound that assumes linear access is not a bound for them.

Amortized with version-indexed potential keeps the potential argument but makes the potential a function of the whole set of live versions, charging copies to the live-version count. It is sound, and it proves bounds in which the cost per operation grows with the number of live versions, usually not what a caller wants, but honest.

Laziness adds a fourth consideration. A thunk is an obligation to do work later, and the work is performed by whichever consumer demands it first. Memoisation guarantees the work happens at most once, but the timing belongs to the consumer, so the bound must be stated for the consumer rather than for the producer. In a sequential setting a potential counting unforced thunks works, because each thunk is forced exactly once. In a concurrent setting two threads can enter the same thunk, one performs the work while the other waits, and the operation’s latency now includes a wait that the work-unit accounting attributes to a single operation.

The design constraint is easy to state and easy to forget: an amortized bound is a theorem about a sequence of operations on a single evolving state. Anything that multiplies states, persistence, laziness, concurrency, multiplies the ways the argument can be invalidated. Stating the bound in worst-case form, or scheduling the expensive work incrementally, is what makes the claim survive. The alternative recorded in the functional data structure literature is a different kind of proof entirely, in which the invariant is a length relationship between two lists or an accounting over node ranks; those hold at every point in time and therefore need no sequence to average over, which is the same reason the union-find bound survives being reasoned about one operation at a time. The trade-off is the same in each case: a uniform guarantee in exchange for a larger constant.