💻 computer science

Categorical Models of Amortized Cost: An Adjoint Relationship between Cost and Potential

This paper establishes that denotational models for type systems tracking amortized cost and potential, such as $\lambda$ -amor, are fundamentally characterized by an adjoint relationship between graded functors representing cost and potential, and demonstrates this framework through three concrete instances including a novel copresheaf-based model.

Original authors: David Binder, David Corfield, Dominic Orchard, Vineet Rajani

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Binder, David Corfield, Dominic Orchard, Vineet Rajani

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a programmer, a digital architect building a castle out of code. You know that every time you stack a brick, it takes a tiny bit of energy. Sometimes, stacking one brick is easy, but every hundredth brick requires you to haul a massive stone up a hill, which takes a lot more energy. If you just look at the worst-case scenario, you might think your castle-building robot will run out of battery after a few hundred bricks. But what if you could save up that extra energy? What if, every time you stacked an easy brick, you tucked a little "energy coin" into your pocket, and then used those saved coins to pay for the heavy lifting later? This is the magic of amortized cost analysis. It's a way of looking at a program not by its single most expensive moment, but by the average cost over a long journey, allowing us to prove that a program will finish its job without running out of resources, even if it occasionally hits a rough patch.

To do this, computer scientists use special "type systems"—think of them as strict rulebooks that check your code before you even run it. These rulebooks can track two things: the cost (the energy you spend right now) and the potential (the energy coins you save for later). The big question has always been: How do these two things actually work together in the deep, abstract math that underpins computer science? For a long time, we had the rulebooks, but we didn't have a clear picture of the machinery that made them tick. We knew the rules worked, but we didn't fully understand the "why" in a way that could be easily mixed with other complex features of programming.

This paper, titled "Categorical Models of Amortized Cost," steps into the deep end of the math pool to build a new, clearer picture of that machinery. The authors, a team of researchers from universities in the UK and Australia, propose a new way to model the relationship between spending energy (cost) and saving energy (potential). They discovered that these two concepts aren't just random rules; they are locked together in a beautiful mathematical dance called an adjoint relationship.

Imagine a vending machine. On one side, you have a "Cost" slot where you put in money to get a snack. On the other side, you have a "Potential" slot where you can store credits. The paper shows that the machine's internal gears are designed so that the way you put money in (the cost) and the way you pull credits out (the potential) are perfectly balanced, like two sides of a seesaw. The authors prove that for any system that tracks these costs and savings, this seesaw balance must exist. They didn't just guess this; they built a rigorous mathematical model using a branch of math called category theory, which treats computer programs like shapes and connections.

To make their idea concrete, they didn't just stop at theory. They built three different "versions" of this machine to show it works in practice. First, they showed a simple version that ignores the cost tracking entirely (like a toy model). Second, they took an existing, complex model used by other researchers and proved that it secretly fits their new "seesaw" design all along. Third, and most excitingly, they built a brand-new model using a mathematical structure called "copresheaves," which is like organizing your energy coins into a giant, flexible map that changes depending on how much fuel you have.

The paper also did something clever with the language of programming itself. The original system used a complicated command called "release" to spend your saved energy. The authors realized that this single command was actually doing three distinct things at once. By breaking it apart into three simpler, more primitive commands—pay (spend the energy), plet (store the result), and split (divide the cost)—they made the whole system easier to understand and easier to combine with other features like randomness or recursion. They even wrote a computer program to check their math, proving that their new, simpler rules are exactly the same as the old, complicated ones.

In short, this paper doesn't invent a new way to write code, but it provides the missing blueprint for why the current ways of tracking energy and savings work. It turns a black box of rules into a transparent, logical machine. By showing that cost and potential are two sides of the same mathematical coin, the authors give programmers and researchers a stronger foundation to build faster, safer, and more efficient software. They suggest that this new understanding will help us create even better tools for analyzing how long our programs will take to run, ensuring that our digital castles never run out of bricks.

Problem Statement
Type systems have been developed to track the computational cost $\kappa$ of programs, typically using cost-tracking monads $M_\kappa \tau$ to provide worst-case guarantees. However, worst-case analysis is often insufficient for functional data structures where amortized complexity is the relevant metric. Amortized analysis relies on the method of potentials, where cheap operations store potential (credits) to pay for expensive operations later. While systems like $\lambda$ -amor [Rajani et al. 2021] successfully track both cost and potential in the type system, they lack a general categorical model. Existing models, such as the step-indexed Kripke logical relations model in the original $\lambda$ -amor paper, are highly concrete and difficult to compose with other language features (e.g., recursion, probabilistic effects). There is a need for an abstract, compositional categorical framework that explains the structural relationship between cost and potential, facilitating the combination of amortized analysis with other computational effects.

Methodology
The authors approach the problem by identifying the abstract mathematical properties required for denotational models of type theories involving cost and potential.

Generalization of Cost Domain: The paper generalizes the cost domain from positive real numbers ( $\mathbb{R}^+$ ) to an arbitrary ordered commutative monoid $\mathcal{C}$ .
Refinement of Calculus: The authors introduce $\lambda$ -amor Core, a refined calculus derived from $\lambda$ -amor. This core removes the complex release primitive and replaces it with three more primitive constructs: pay (using potential to pay for cost), plet (functorial action for potential), and split (splitting cost). This decomposition is motivated by the need to align the syntax with the underlying categorical structures.
Categorical Modeling: The authors propose that cost and potential must be modeled by an adjoint relationship. Specifically:
- Cost is modeled by a graded monad $M$ (for sequencing costs) that is also a graded comonad (for splitting costs).
- Potential is modeled by a graded functor $P$ .
- Interaction: For every cost grade $p$ , there is an adjunction $P_p \dashv M_p$ . The unit of the adjunction corresponds to storing potential (store), and the counit corresponds to using potential to pay for cost (pay/release).
Formalization: The authors mechanize the type system and the verification of model laws in the Lean proof assistant.

Key Contributions
The paper makes three primary contributions:

Abstract Adjoint Model: The authors describe a general abstract model where cost and potential are related by a family of adjunctions between a strong graded monad (modeling cost) and a strong graded functor (modeling potential). They prove the soundness of this model with respect to the equational theory of $\lambda$ -amor Core.
Mechanization and Kripke Instance: They provide a mechanization of the type system in Lean and verify that the Kripke logical relations model from the original $\lambda$ -amor paper [Rajani et al. 2021] is a specific instance of their general categorical model. This connection was not previously observed and required non-trivial technical detail to prove.
Novel Copresheaf Model: They present a new model instance based on copresheaves over a monoidal category of costs. In this model, pairs and functions are modeled using Day convolution and its right adjoint. This provides a canonical construction for amortized cost models that differs from the Kripke model, particularly in how it interprets the cost graded monad.

Results

Soundness: The paper proves that every typing derivation in $\lambda$ -amor Core can be interpreted in the proposed adjoint model.
Equivalence: The Kripke logical relations model is shown to satisfy the laws of the general categorical model, confirming that the abstract structure captures the concrete semantics of the original system.
Decomposition: The paper demonstrates that the release operation in the original $\lambda$ -amor can be decomposed into pay, plet, and split, and that these primitives can be reconstructed from release.
Model Comparison: The copresheaf model is shown to coincide with the Kripke model for potential types but offers a distinct interpretation for the cost graded monad, avoiding the explicit forcing relation used in the Kripke model.

Significance
The paper claims to provide the missing "compositional" piece for understanding amortized cost analysis in type theory. By establishing that cost and potential are related via adjunctions, the authors offer a structural explanation for how amortized analysis works, moving beyond concrete, ad-hoc models. This framework allows for the potential combination of amortized cost tracking with other deterministic or probabilistic effects in a compositional manner. Furthermore, the refinement of the syntax into $\lambda$ -amor Core, driven by categorical insights, simplifies the equational theory and clarifies the interaction between cost and potential. The authors position this work as a foundation for constructing more expressive type theories for quantitative analysis and for integrating amortized cost models with other categorical models of computation.

More like this