Structural Caching for Scaling Combinatorial Search

This direction is merged into another direction: sub-problem memoization. Its last version stays readable and citable here.

Version 1 of 1156 papers203 conceptsfrozen 2026-10-04

In combinatorial optimization and automated reasoning, we often face a "state-space explosion." Whether we are solving a Satisfiability (SAT) problem, planning a robot's path, or optimizing a database query, the number of possible configurations grows exponentially with the size of the input. However, real-world problems are rarely random; they possess deep structural symmetries and recurring sub-patterns.

The core insight across this research direction is that we can tame exponential complexity by identifying, storing, and reusing the solutions to these recurring sub-problems. This is not merely simple memoization; it is a sophisticated form of structural caching that recognizes when two seemingly different branches of a search tree are, in fact, logically or mathematically identical.

The Intuition: Don't Solve the Same Problem Twice

Imagine searching a massive maze. If you find that a specific corridor always leads to a dead end, you shouldn't just remember that specific corridor; you should remember the shape of the dead end. If you encounter that same shape elsewhere in the maze, you can skip it entirely.

In computational terms, this is the transition from tree search to graph search. As David Hemmi, Guido Tack, and Mark Wallace demonstrate in A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems, caching the results of previously solved sub-problems allows algorithms to scale linearly in domains where traditional solvers become paralyzed. By breaking massive "multistage" problems into scenarios and solving them recursively, they transform redundant mathematical operations into simple table lookups.

Identifying Structural Equivalence

The hardest part of caching is knowing when two sub-problems are "the same." In many domains, the identity of a sub-problem isn't defined by its location in the search tree, but by its constraints.

  1. Component Decomposition: In model counting and Bayesian inference, researchers like Tian Sang and Paul Beame use "component caching." In A Dynamic Approach for MPE and Weighted MAX-SAT, they show how to identify independent sub-problems on the fly. If a set of variables becomes disconnected from the rest of the formula, its solution can be cached and reused whenever that specific sub-formula reappears.
  2. Canonical Representations: A more rigorous approach involves "canonicity." Adnan Darwiche and Guy Van den Broeck have shown in On the Role of Canonicity in Bottom-up Knowledge Compilation that forcing logical structures into a unique (canonical) form allows for "perfect" cache hit rates. If two logical functions are equivalent, they will map to the exact same memory address, allowing the solver to skip re-computation using a simple pointer comparison.
  3. Data-Centric Sub-problems: In machine learning, Jimmy Lin and Cynthia Rudin apply this to decision trees. In Generalized and Scalable Optimal Sparse Decision Trees, they identify sub-problems not by the rules used to reach a node, but by the specific subset of training samples remaining. This allows the algorithm to recognize that different paths through the tree actually lead to the same optimization problem.

From SAT Solvers to Large Language Models

This mechanism is remarkably versatile, appearing in almost every corner of computer science where search is required:

  • Constraint Satisfaction: Christophe Lecoutre and Lakhdar Sais adapted "transposition tables" from chess engines to CSPs in Transposition Tables for Constraint Satisfaction, pruning entire branches that lead to previously encountered unsatisfiable states.
  • Database Systems: In cloud-scale environments, Yiwen Zhu and colleagues at Microsoft's Gray Systems Lab describe in Towards Building Autonomous Data Services on Azure how hashing subexpressions within query plans allows the system to bypass redundant processing across massive workloads, improving efficiency by over 30%.
  • Neural Reasoning: Even modern AI is adopting these classical techniques. Gunhee Kim and Soochan Lee introduced the Recursion of Thought framework, which allows language models to break complex problems into independent contexts. By caching the results of these contexts, the model avoids redundant token generation for recurring sub-problems.

Why It Works: The Power of Decomposition

The success of structural caching relies on the fact that most complex problems are "decomposable." In Exact ASP Counting with Compact Encodings, Mohimenul Kabir and Kuldeep S. Meel show that breaking a formula into independent components is the only way to handle the "formula blowup" that occurs in exact model counting.

By treating a large problem as a collection of smaller, reusable parts, we shift the burden from computation (which is exponential) to memory (which is often manageable). As Charles Elkan noted in his early work on Conspiracy Numbers and Caching, recognizing that a new goal is just a "substitution instance" of a previously solved one can reduce an exponential search to something much closer to linear.

In essence, structural caching works because it exploits the hidden simplicity within complex systems. It turns the "curse of dimensionality" on its head: the more structured and repetitive a problem is, the more effectively we can solve it by remembering what we've already done.

Papers in this version

Showing 60 of 156 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_structural_caching_for_scaling_combinato_7bae10f3,
  title = {Structural Caching for Scaling Combinatorial Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-caching-for-scaling-combinatorial-search/rdr_7bae10f31ec141cab2560eb7828df6f7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_structural_caching_for_scaling_combinato_7bae10f3_v1,
  title = {Structural Caching for Scaling Combinatorial Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-caching-for-scaling-combinatorial-search/rdr_7bae10f31ec141cab2560eb7828df6f7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}