💻 computer science

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

This paper introduces two miniKanren library combinators, `prune` and `defrel/bank`, that enable bottom-up enumeration with observational deduplication and memoization to significantly improve the performance of relational program synthesis on deep targets, while also proposing a weighted variant to address cases where canonical depth-first ordering fails to find compact representatives.

Original authors: Nikolai Kudasov

Published 2026-07-29

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikolai Kudasov

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 detective trying to solve a mystery, but instead of looking for clues, you are trying to build a machine that can do a specific job, like turning the number 2 into 4, 3 into 9, and 4 into 16. You don't know the exact formula the machine uses; you only know the results. This is called "Programming by Example." To find the answer, you could try building every possible machine, one by one, starting with the simplest gears and levers, and testing each one to see if it works. This is a bit like a chef trying to find a secret recipe by baking every possible combination of flour, sugar, and eggs until one tastes right.

In the world of computer science, there is a special way of thinking called "relational programming." Instead of telling the computer exactly how to find the answer step-by-step, you describe what the answer looks like, and let the computer figure out the path. It's like telling a robot, "Find me a path through the maze," rather than "Turn left, then walk three steps, then turn right." The computer is great at exploring many paths at once, but it has a tricky habit: it tends to explore the same dead ends over and over again, or get stuck in a long, winding tunnel while missing a short, clever shortcut right next to it. This paper tackles that problem by teaching the computer how to be a smarter, more organized explorer.

The Problem: Getting Lost in the Maze

Imagine you are trying to find a specific key in a giant, messy attic filled with millions of keys. Most of these keys look different, but they all open the exact same door. If you are a clumsy explorer, you might pick up a key, try it, realize it works, and then spend hours picking up other keys that look different but also work, just to be sure. You are wasting time checking keys that do the exact same job.

In the world of computer programs, this happens all the time. When a computer tries to build a program to turn inputs into outputs, it generates thousands of different-looking code snippets. Many of these snippets are "twins" in disguise—they do the exact same thing even though they look different on the inside. A standard computer search method, which works like a deep-dive explorer, will check one twin, then the next, then the next, getting slower and slower as the attic gets bigger. It's like trying to find a needle in a haystack, but the haystack is made of millions of needles that all look slightly different.

The Solution: The "Prune" and the "Bank"

The authors of this paper, Nikolai Kudasov, came up with two clever tools to fix this mess. Think of them as a magical filter and a smart library.

1. The "Prune" Tool (The Filter)
Imagine you have a conveyor belt of keys coming out of a machine. The "Prune" tool is a guard standing next to the belt. As each key arrives, the guard checks what door it opens. If the guard has already seen a key that opens that same door, they simply toss the new key into the trash without even testing it. They only keep the very first key that opens a specific door. This way, the conveyor belt only carries unique, useful keys. The computer stops wasting time on duplicates.

2. The "Bank" Tool (The Smart Library)
Now, imagine that instead of building keys from scratch every time you need one, you have a magical library. When you ask the library for a key, it doesn't just give you one; it builds a whole shelf of unique keys once, from the bottom up, and saves them. If you ask for a key again later, the library just hands you the one it already built.

In the paper's language, this is called defrel/bank. It forces the computer to build its list of candidate programs in a specific, organized way (starting with the simplest ones) and saves the results. If the computer needs to use a small piece of a program later, it doesn't rebuild it; it just grabs the piece from the "bank." This saves a massive amount of time because the computer never has to do the same work twice.

The Twist: Sometimes "Fast" Isn't "Best"

The authors also realized that just being organized isn't always enough. Sometimes, the "Bank" builds its shelves in an order that is fast for the computer but slow for the human. For example, the Bank might build all the "multiplication" machines first, and only much later build the "addition" machines. If the answer you are looking for is an "addition" machine, the computer might have to check thousands of multiplication machines before it finally finds the one you need.

To fix this, they created a third tool called defrel/bank-w (the "Weighted" Bank). This tool is like a librarian who knows that some types of keys are more likely to be the answer. It uses a special "score" to decide which keys to show you first. It tries to show you the simplest, most compact keys first, even if they are buried deep in the library. This is great if you want the most elegant solution, but it can be slower if the answer is actually a complex, deep machine.

What They Found: Speed vs. Strategy

The authors tested these tools on a set of math and string puzzles (like turning "Hello" into "Hello, World!"). Here is what they discovered:

The "Bank" is a speed demon: On 6 out of 8 difficult math problems, the defrel/bank tool was 9 to 99 times faster than the old, standard way of searching. It was so fast that it solved problems in a fraction of a second that the old method took minutes to finish.
But it has a blind spot: The Bank is so organized that it sometimes misses the answer if that answer is hidden in a part of the library it visits late. For example, if the answer involves adding numbers in a specific way (like $(1+x)^5$ ), the Bank might get stuck checking thousands of multiplication examples first. In these cases, the old, slower method actually wins because it checks things in a different order.
The "Weighted" Bank is a trade-off: The defrel/bank-w tool is excellent at finding the most compact, elegant answers. It found the right answer for a tricky string puzzle in 10.4 milliseconds, beating the standard method's 31.5 milliseconds. However, for very deep math problems, it sometimes got stuck trying to check too many possibilities and timed out.

The Bottom Line

This paper doesn't claim to have solved every problem in computer science. Instead, it shows that by adding a little bit of "pruning" (filtering out duplicates) and "banking" (saving work for later), we can make computer programs that build other programs much, much faster.

The authors suggest that if you are building a system to solve puzzles, you should use the Bank tool as your default because it is usually the fastest. However, if you are looking for a very specific, compact solution, or if the problem is shallow and simple, you might want to use the Weighted Bank or even the old-fashioned method. It's not about one tool being perfect; it's about having the right tool for the shape of the puzzle you are trying to solve. The paper ends by suggesting that future work will test these tools on even more complex puzzles, like building programs that understand lists or typed data, to see if this speed-up holds up in the real world.

Technical Summary: Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

Problem Statement

Modern Program-by-Example (PBE) synthesizers typically rely on bottom-up enumeration with observational deduplication. This approach maintains a worklist of candidate expressions, deduplicates them based on their behavior on example inputs, and expands them level-by-level until a match is found. While highly effective in imperative and functional settings, this strategy sits awkwardly in relational programming (specifically miniKanren), where the natural search discipline is top-down resolution against a fair stream of candidates.

Existing miniKanren recipes for PBE, such as writing a relational interpreter and running it "backwards" or using an "enumerate-and-test" approach with depth bounds, suffer from significant inefficiencies at realistic search depths. The primary issue is that the search tree contains many behaviorally equivalent expressions. A naive depth-bounded enumerator creates a fresh deduplication table at every recursive level, failing to reuse work performed at previous levels. This leads to an exponential blowup in search space where behaviorally identical candidates are re-evaluated repeatedly.

Methodology

The authors propose two small library combinators built on top of an unmodified $\mu$ Kanren core to bridge the gap between bottom-up PBE synthesis and relational programming. These combinators introduce bottom-up enumeration and observational deduplication without altering the host search discipline.

1. The `prune` Combinator

The first combinator, prune, filters an answer stream based on a user-supplied key function.

Mechanism: It wraps a goal and emits at most one state per distinct value of the key function (e.g., the input/output behavior of a candidate expression).
Handling Logic Variables: To handle cases where the key depends on unbound logic variables, prune uses a sentinel value (skip-prune). If a key cannot be computed because a term is not yet ground, the state is emitted without being recorded in the deduplication table. It is subject to deduplication only once the variable is bound and the term becomes ground.
Scope: Deduplication is strictly per-call. A fresh hash table is created for each invocation of prune to avoid conflating "seen as an outer variable" with "seen as an inner variable," which would otherwise break completeness in recursive definitions.

2. The `defrel/bank` Combinator

The second combinator, defrel/bank, extends prune to achieve true bottom-up enumeration with shared deduplication across all call sites of a relation.

Canonical Variables: It memoizes a relation against canonical fresh variables (the first $N$ fresh variables of an empty state), representing the most general call of the relation.
The "Bank": The relation body is executed once against these canonical variables to produce a canonical stream (the "bank"). This stream is built bottom-up and contains exactly one representative per equivalence class (determined by the #:prune key).
Replay: Subsequent calls to the relation do not re-execute the body. Instead, they replay the canonical stream against the caller's specific arguments. This involves walking the canonical substitution, renaming internal variables to the caller's namespace, and unifying the results with the caller's arguments.
Efficiency: This approach ensures that the deduplication work is performed only once per (run ...) query, regardless of how many times the relation is called recursively.

3. The `defrel/bank-w` Variant (Best-First)

The standard defrel/bank uses depth-first recursion, which biases the enumeration order (e.g., favoring right-spine chains of multiplication over addition). To address cases where the target solution lies deep in the canonical order, the authors introduce defrel/bank-w.

Weighted Streams: This variant attaches admissible upper bounds (weights) to immature stream cells.
Depth-Decay: A decay factor is applied to weights at recursive call sites. This ensures that shallower representatives have lower weights and are emitted first by the sorted merge logic (mplus-w).
Lazy Heuristics: The system uses a "lazy-ceiling" discipline where weights are peeked without forcing the underlying thunk, preventing infinite loops during the construction of the canonical stream. This implements an A*-style search where the weight ceiling acts as an admissible heuristic.

Key Contributions

prune: A generic answer-stream deduplication combinator keyed on user-supplied functions, supported by helpers (ground-key, when-ground) to lift term-level functions into prune keys.
defrel/memo and defrel/bank: Combinators for relation memoization against canonical fresh variables. defrel/bank specifically provides bottom-up enumeration with shared deduplication, effectively transplanting the standard PBE "worklist" pattern into the relational setting.
defrel/bank-w: A depth-decayed best-first variant that uses weights on immature streams to recover best-first enumeration, allowing the system to find compact representatives even when the natural depth-first order misses them.
Implementation Tricks: The paper details engineering optimizations, such as using pairing heaps for sorted merges and "thunk-collapse" techniques, to ensure the memoized approach performs competitively with depth-bounded baselines.

Results

The authors present a preliminary empirical evaluation on arithmetic and string PBE benchmarks (depths 0–6).

Performance Gains: On 6 out of 8 deep arithmetic targets, defrel/bank is 9–99× faster than the depth-bounded baseline (bounded). This is because bank avoids re-pruning sub-expressions at every recursive level.
Enumeration Order Bias: The performance of defrel/bank is highly dependent on the enumeration order. It excels when the target solution lies early in the canonical depth-first order (e.g., $x^k$ or $x^k + c$ ). However, it struggles or times out on targets like $(1+x)^k$ , which appear very late in the canonical stream (e.g., position 243,158 for depth 4).
Best-First Trade-offs: defrel/bank-w successfully finds compact representatives for targets like $(1+x)^k$ early in the search. However, it incurs a "breadth-first cost": emitting a depth- $K$ cell requires emitting all cells of depth $<K$ . On wide behavior spaces (thousands of distinct behaviors at depth 3), this leads to timeouts on deep arithmetic targets where defrel/bank succeeds.
Comparison with Host Baseline: A non-relational host-language baseline (host-bank) performs well on shallow targets and $(1+x)^k$ families but fails catastrophically on deep right-spine targets due to the cost of building an exhaustive bank outside the relational engine. defrel/bank retains the relational interface while recovering most of the host-bank's speedup where the enumeration bias is favorable.

Significance and Claims

The paper claims that these combinators successfully bring the standard tool of bottom-up enumeration with observational deduplication into the relational setting without leaving the relational paradigm or changing the host search discipline.

Opt-in Semantics: The approach is strictly opt-in. It does not alter the semantics of standard miniKanren relations; deduplication only applies to relations explicitly wrapped in prune or defined via defrel/bank.
Completeness: The authors argue that pruning preserves completeness with respect to the user-supplied equivalence. For every behavior, at least one representative is found.
Limitations: The authors are modest about the scope, noting that the evaluation is preliminary, limited to two domains (arithmetic and string), and relies on a specific grammar. They acknowledge that defrel/bank is not a universal solution; its success depends on the interaction between the target's shape and the enumeration order. They explicitly state that fair conjunction cannot resolve the enumeration bias of defrel/bank because the bias lies in which cells exist in the bank, not how they are interleaved.
Future Work: The paper identifies several directions for future work, including iterative deepening over the canonical body to fix the $(1+x)^k$ bias without breadth-first costs, saturation detection, and extending the approach to richer constraint stores and other PBE domains (e.g., bit-vectors, lists).

In summary, the paper demonstrates that by memoizing relations against canonical variables and pruning by observational equivalence, one can achieve significant performance gains in relational PBE synthesis, provided the enumeration order aligns with the target's structure.