When Can a Computation Forget? Semantic Lifetime Width and Query-Relative State Retirement

Abstract

Algorithms are usually analyzed by how much state they store, how wide their dependency graph is, or how many subproblems they retain. These measures are largely query independent: they describe the computation that exists, not the distinctions that still matter to the answer being requested. We introduce Semantic Lifetime Width (SLW), a query-relative measure defined from the number of future-equivalence classes that remain distinguishable at each stage. States are equivalent when every admissible continuation induces the same terminal outcome, so a certified retirement may merge them without preserving irrelevant historical detail. We prove retirement soundness, monotone coarsening of future equivalence, a lifetime-accounting identity for factorizable distinction systems, a quotient-state complexity bound, and polynomial tractability when certified width is logarithmic under polynomial transition and verification assumptions. We establish asymptotic separations from query-independent structural width: complete-graph parity has linear pathwidth but constant SLW, whereas delayed indexed-bit retrieval on a path-like sequential structure has constant pathwidth but linear SLW. Most strikingly, the same underlying computation supports two one-bit queries with constant versus linear SLW. Reproducible experiments verify the constructions and quantify state-volume reductions under expiring-history workloads, motivating query-relative state retirement as a distinct algorithm-design lens. This separates structural storage from answer-sensitive memory obligations.