Incremental Computations Without Recomputing Everything

The moment you realize you’re wasting CPU

Picture a little data panel in your app. A user changes one input—say, a search filter—and the panel updates: counts change, rows re-sort, and a few summary numbers move.

Now picture what the typical “first version” does: rebuild the entire panel from scratch every time. It’s easy to write, and for small datasets it feels fine. Then the dataset grows, the UI becomes “live,” and suddenly your CPU graph looks like an anxious heartbeat.

This is where incremental computations enter the story. Jane Street’s Incremental library is designed to help you build computations that update efficiently when inputs change, rather than starting over every time. It’s inspired by “self-adjusting computations” from academic work and it’s meant for building large, interdependent calculations that stay in sync with changing data. (github.com)

From “functions” to a computation graph (DAG)

The key mental shift is: don’t treat your program like a single, one-shot function. Treat it like a graph of dependent computations.

A DAG (Directed Acyclic Graph) is a network of nodes with arrows showing dependencies, where arrows never create loops. Incremental builds exactly this style of dependency structure for you.

Inside the library, incremental values are represented as nodes in that DAG, and they can become stale (out of date) when upstream inputs change. Incremental then figures out which nodes actually need recomputation, and which can be skipped. (github.com)

If that sounds abstract, here’s the beginner-friendly takeaway: Incremental turns your “recompute everything” update strategy into “recompute only what depends on the changed inputs.”

The three characters: Var, map, and bind

Incremental’s API revolves around a few core ideas.

1) Variables (Var)

A variable is an input you can change over time. In Incremental, you create them with Var.create and then update them with Var.set.

In the library’s own example, two variables x and y are created, and an incremental value z depends on them. (github.com)

2) Mapping (map2, map, etc.)

A mapping takes one or more incremental values and produces a new incremental value by applying a function.

For example, if x and y are incremental variables, then map2 (Var.watch x) (Var.watch y) ~f:(fun x y -> x + y) creates an incremental z that represents x + y.

The important detail: Incremental tracks the dependency from z back to x and y. When x changes, Incremental knows z must be updated—without you manually wiring update propagation code.

3) Binding (bind, written like >>=)

bind is where Incremental gets genuinely powerful.

bind lets you build an incremental value whose internal computation can change depending on the value of another incremental.

In plain language: with bind, the structure of your dependency graph can reconfigure at runtime.

The interface explains it like this: bind ta ~f returns a node tb that behaves like f a, where a is the latest value of ta, and the function f is only called when ta changes. (github.com)

A classic pattern looks like an “if/then/else” that depends on an incremental boolean: when the condition flips, Incremental switches which branch is live.

“Observed” nodes are the only ones that matter

One of the easiest features to misunderstand is that Incremental doesn’t constantly recompute everything.

Incremental uses the idea of being observed:

• An incremental node becomes observed when you call observe on it.
• A node is necessary if there exists a dependency path from that node to an observed node.
• During stabilization, Incremental ensures correct values for necessary nodes and does not compute unnecessary ones. (github.com)

That leads to a practical outcome: if some part of your computation graph doesn’t feed anything the UI currently needs, Incremental can avoid doing the work.

So why does your CPU sometimes stop spiking after adopting Incremental? Because you’re giving it fewer “observed targets,” and it will only keep the relevant slice of the DAG up to date.

Stabilization: the moment updates actually propagate

Changing a variable doesn’t automatically mean everything updates immediately.

Incremental’s update propagation happens during stabilization, called stabilize.

At a high level, stabilize:

1. Walks the DAG in dependency order.
2. Recomputes nodes that are necessary and stale.
3. Ensures each node is computed at most once per stabilization run.

The library documentation explains this in terms of a recompute heap and a notion of height (an internal measure related to dependency distance). (github.com)

The point for beginners is simpler: stabilize is the “commit point” where Incremental propagates changes through the dependency graph.

Here’s a compact sketch of the flow:

module Inc : Incremental.S = Incremental.Make ()
open Inc

let x = Var.create 13
let y = Var.create 17
let z = map2 (Var.watch x) (Var.watch y) ~f:( + )

let z_observer = observe z

Var.set x 20;
stabilize ();

(* now z_observer reflects the updated z *)

Even if your nodes changed, nothing gets recomputed until you call stabilize.

Dynamic graphs, invalidation, and the tricky part that becomes intuitive

The “hard part” conceptually is bind.

When you bind, Incremental doesn’t just recompute a number—it may create or destroy parts of the DAG depending on upstream values. (github.com)

That means when the bound input changes, Incremental must prevent recomputing nodes that were created based on an old value. The implementation uses invariants involving node height to ensure stabilization stabilizes the left-hand side before recomputing nodes created by the right-hand side of a bind. It also marks nodes as invalid when the left side changes. (github.com)

This can feel slippery at first: how can a graph both change and remain manageable? The reassurance is that the library is designed so these complexities are internal. You write bind and let Incremental handle correctness.

Cutoffs: when “changed” shouldn’t mean “recompute”

Not every input change is meaningful. Sometimes floating-point noise shouldn’t trigger a whole dependency cascade.

Incremental introduces cutoff functions to control what “changed” means for a node.

By default, a node is considered changed when its new value is not physically equal to the previous value (a low-level equality check). But you can override that with set_cutoff to use a custom predicate—like “only propagate if the difference exceeds a threshold.” (github.com)

In performance-heavy apps, cutoffs become the difference between “fast enough” and “why is it still recomputing?”

A practical note on setup

Incremental is written for OCaml and depends on Jane Street’s Core ecosystem.

On the OPAM package index, the latest released version is listed as v0.17.0 (latest), published May 26, 2024. (opam.ocaml.org)

The package metadata in the repository also indicates requirements like OCaml >= 5.1.0 and a minimum dune >= 3.17.0 for the build. (github.com)

Meanwhile, the GitHub repository’s master branch can include newer preview work than the OPAM release, so version choice matters when you’re matching docs to code.

Why this shows up in UI engineering

Incremental isn’t only an algorithms library; it’s a user-interface library in disguise.

A big dynamic UI can be seen as “derived data” from an underlying model: the displayed view depends on the model, and as the model changes, only parts of the view should update.

Jane Street’s blog discusses using Incremental-style self-adjusting computation ideas to incrementalize work behind web interfaces, especially when naïve approaches repeatedly rebuild large structures. (blog.janestreet.com)

So the question isn’t whether your app “can use incremental.” The question is why you ever recomputed more than the changed inputs required.

The end of the tutorial: a mental model that sticks

Once Incremental clicks, the whole system becomes predictable.

• Your program builds a DAG of dependent computations.
• Some nodes are variables you change.
• Some nodes are derived via map and bind.
• Nodes do nothing until they’re observed.
• Calling stabilize recomputes only the necessary, stale parts of the graph.
• Cutoffs let you decide when a value change is “real enough” to propagate.

That’s it. Not magic. Just a disciplined way to stop doing expensive work repeatedly when only a small piece of the world changed.

Closing thought

Incremental computation feels like a quiet upgrade: you keep writing computations as values, but the runtime stops treating every update as a full reset. Over time, that can reshape how you design interactive systems—because it’s much easier to build responsive applications when the underlying engine refuses to waste effort.