Solution Caching for Accelerated Optimization and Learning

21 concepts11 papers1 proposal

Many modern machine learning and optimization workflows suffer from a shared computational bottleneck: the need to repeatedly solve expensive optimization problems inside an iterative loop. For instance, in Decision-Focused Learning (DFL) or Predict-and-Optimize frameworks, a machine learning model predicts parameters for a downstream optimization problem, requiring the training loop to differentiate through a combinatorial solver at every gradient step. Similarly, in projection-free continuous optimization—such as Frank-Wolfe (Conditional Gradient) algorithms—every iteration requires querying a Linear Minimization Oracle (LMO) to find an extreme point of a feasible region.

Executing heavy-duty solvers or global oracle searches thousands of times is computationally crushing. However, a key geometric insight offers a way out: while the objective function changes slightly at each iteration, the underlying feasible space (the constraints) remains static. Consequently, the optimal solutions across iterations are highly redundant, frequently clustering around the same extreme points or vertices.

By maintaining a solution cache—a historical record of previously discovered optimal points—algorithms can bypass the solver entirely for the majority of iterations. This paradigm shift transforms expensive global optimization queries into cheap local lookups, drastically reducing wall-clock time while preserving accuracy and decision quality.

The Intuition: Redundancy in the Feasible Space

Why does caching work so effectively in these settings? Consider an optimization problem over a polytope. When an algorithm updates its parameters, the objective vector rotates slightly, but the vertices of the polytope remain fixed.

Iterative Objective Changes vs. Static Feasible Space:

      Vertex A (Cached)
        /\
       /  \   <-- Objective Vector 1 points here
      /    \
     /______\ 
  Vertex B    Vertex C (Objective Vector 2 points here)

If the objective vector rotates only a small amount, the new optimal solution is highly likely to be a vertex that the algorithm has already visited. Instead of treating every iteration as a brand-new optimization problem, the algorithm can treat its cache of past solutions as an inner approximation of the search space. Evaluating a new objective function over a finite set of cached points requires only a few basic linear operations, whereas invoking a full combinatorial or continuous solver might scale exponentially or require expensive matrix factorizations.

Lazified Oracles in Projection-Free Optimization

In continuous optimization, this strategy is known as lazification. In traditional Frank-Wolfe variants, the algorithm queries an LMO at every step to find a vertex that minimizes the linearization of the objective function.

As shown by Gábor Braun et al. in Lazifying Conditional Gradient Algorithms, we can replace this expensive exact oracle with a "weak separation oracle" backed by a cache of previously found vertices. Instead of computing a brand-new extreme point, the algorithm first performs a cheap linear scan over the cache. If an existing vertex satisfies a sufficient progress criterion—meaning it moves the optimization far enough toward the optimum—the algorithm reuses it. The full, expensive LMO is only triggered as a fallback when the cache fails to provide a valid direction.

The authors demonstrated that this simple lazy strategy yields cache hit rates frequently exceeding 90%, translating into orders-of-magnitude faster wall-clock times. This mechanism has been integrated into modern high-performance optimization ecosystems. For example, Mathieu Besançon et al. leveraged lazy oracles within FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank-Wolfe Algorithms and Conditional Gradients and its subsequent iterations (Improved algorithms and novel applications of the FrankWolfe.jl library) to scale projection-free methods to massive, structured optimization tasks where exact linear minimization would otherwise be computationally prohibitive.

Furthermore, Kazuma Tsuji et al. applied this lazification principle to pairwise conditional gradients in Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding. By prioritizing the reuse of cached atoms over expensive global searches, they eliminated inefficient "swap steps" and accelerated optimization in high- and infinite-dimensional spaces, such as kernel herding, where evaluating the global gradient is the primary bottleneck.

Solution Pools in Decision-Focused Learning

The exact same intuition applies when embedding optimization solvers within machine learning training loops. In Predict-and-Optimize pipelines, a neural network predicts cost vectors, and a solver computes the optimal decision based on those costs. Computing gradients through this step typically requires solving NP-hard combinatorial problems at every single epoch for every training instance.

To circumvent this, Jayanta Mandi et al. and Maxime Mulamba et al. introduced a solver-agnostic solution caching framework in Contrastive Losses and Solution Caching for Predict-and-Optimize. By storing the optimal solutions discovered during early training iterations, they constructed a discrete pool of candidate decisions. Instead of calling a heavy integer linear programming solver, the framework performs a fast linear search over this cache to evaluate contrastive loss functions. This approach achieves nearly constant training time per epoch while maintaining state-of-the-art decision quality.

This concept was expanded by Jayanta Mandi et al. in Decision-Focused Learning: Through the Lens of Learning to Rank, where they reframed DFL as a ranking problem over the cached solution pool. Rather than calling the solver continuously, the model is trained to correctly rank the pre-computed feasible solutions. As synthesized in their comprehensive review (Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities), intermittent solver execution combined with a solution cache completely mitigates the computational bottleneck of DFL, allowing models to scale to complex combinatorial problems.

The utility of caching extends to even more intricate optimization landscapes. For instance, Hyungki Im et al. applied solution caching to contextual stochastic linear optimization problems featuring robust, data-driven constraints (Smart Surrogate Losses for Contextual Stochastic Linear Optimization with Robust Constraints), proving that caching maintains model accuracy and decision feasibility while dramatically accelerating gradient updates.

Replay Buffers and Surrogate Landscapes

Beyond direct lookups, cached optimization data can be used to train smooth approximations of non-differentiable optimization landscapes.

In Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information, Arman Zharmagambetov et al. introduced LANCER, a framework that stores past solver evaluations in an experience replay buffer. Instead of querying a heavy-duty solver at every gradient step, the system reuses the buffer to train a neural network "surrogate" loss function. This decouples model training from solver execution, providing dense, smooth gradients and achieving high performance with orders of magnitude fewer solver calls.

[ML Model Updates] ---> [Check Cache / Replay Buffer] --(Hit)--> [Instant Gradient/Loss]
                               |
                            (Miss)
                               v
                     [Heavy-Duty Solver Call] ---> [Update Cache]

This strategy of caching outcomes to avoid redundant, expensive evaluations appears across diverse optimization domains:

Summary

Solution caching works because optimization trajectories and machine learning updates exhibit high geometric locality. By treating memory as a substitute for raw computation, lazified oracles and solution pools eliminate the need to solve identical or highly similar sub-problems from scratch. Whether applied to continuous projection-free gradients, combinatorial decision-focused learning, or neural architecture searches, caching transforms intractable optimization loops into highly efficient, scalable systems.

Key Foundational Work

Contrastive Losses and Solution Caching for Predict-and-Optimize (2021) — contributed 2 concept elements to this direction.
Lazifying Conditional Gradient Algorithms (2016) — contributed 2 concept elements to this direction.
Contrastive Losses and Solution Caching for Predict-and-Optimize (2021) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_solution_caching_ebf38eee,
  title = {solution caching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solution-caching/rdr_ebf38eeed2ed4ebbac576b6c6a6340bd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_solution_caching_ebf38eee_v1,
  title = {solution caching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solution-caching/rdr_ebf38eeed2ed4ebbac576b6c6a6340bd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake