Asymmetric Archive Quantization for Latent Bayesian Optimization

When we optimize an expensive black-box function over discrete structures — molecules, prompts, mathematical expressions — a standard trick is to learn an encoder and decoder that map those structures into a small continuous vector space, then run search there. A Bayesian optimizer does this by fitting a Gaussian process, a probabilistic regression model whose predictions for any new point are weighted by its similarity to all previously evaluated points, and then proposing the next point to evaluate where predicted quality or uncertainty looks most promising. As the optimization accumulates history, that "compare one candidate against the entire past" step becomes the bottleneck: Gaussian process inference scales cubically in the number of stored points, and latent-space optimizers either crash (in the high-dimensional discrete-sequence benchmark of A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences, the solver Bounce ran out of memory after as few as 40 iterations) or quietly throw history away, as the trust regions of Local Latent Space Bayesian Optimization over Structured Inputs effectively do.

This one-versus-many pattern is exactly the situation that asymmetric distance computation was built for. In large-scale retrieval, permanent database entries are compressed while transient queries stay in full precision, because the two sides have different cost structures: database storage is cumulative and persistent, query handling is fleeting (AMES: Asymmetric and Memory-Efficient Similarity Estimation for Instance-Level Retrieval). No one has applied this asymmetry inside an optimization loop. The proposal here is to do precisely that: keep every evaluated latent point forever, but store the archive under product quantization, and evaluate full-precision candidates against that quantized archive through precomputed lookup tables. One ingredient makes this safe where the naive version breaks: instead of plugging a distorted asymmetric distance into the Gaussian process kernel, we move archive points onto the codebook grid and evaluate an ordinary kernel between each candidate and the reconstructed archive point.

Core Claim

The claim is that a Bayesian optimizer whose memory is a product-quantized archive — a "codebook memory" — can retain all observations within a strict evaluation budget at a tiny memory footprint, and that this complete-but-compressed memory buys sample efficiency that neither history-discarding trust regions nor simple genetic algorithms reach. Concretely: with the archive stored as $M$ byte-sized codes per point, ten thousand evaluations occupy tens of kilobytes rather than tens of megabytes, and scoring a batch of candidates against the archive costs a few table lookups and additions per pair, so nothing is ever discarded.

Research Program

Component 1: a PSD-safe asymmetric kernel. Product quantization splits a latent vector $z \in \mathbb{R}^D$ into $M$ blocks; each block is matched to the nearest of $K$ centroids, and only the centroid indices are stored. Reconstructing an archive point $\hat{z}_i$ from its indices gives its position on the codebook grid. We then use a standard squared-exponential kernel with a separate length-scale $\ell_m$ per block between a full-precision candidate $z_q$ and each reconstruction:

$$ k(z_q, \hat{z}_i) = \exp\!\Big(-\tfrac{1}{2} \sum_{m=1}^{M} \frac{\lVert z_q^{(m)} - c^{(m)}_{a_m(i)} \rVert^2}{\ell_m^2}\Big), $$

where $c^{(m)}_{a}$ is centroid $a$ of block $m$ and $a_m(i)$ is the stored index for archive point $i$. This is where the asymmetry lives, and it is deliberately representational rather than metric. Because the archive point has simply been relocated to $\hat{z}_i$, the kernel matrix over any mixture of candidates and reconstructions is an ordinary Gram matrix and is positive semi-definite by construction. This directly resolves the theoretical friction flagged in the gap analysis: naively embedding an asymmetric distance $d(z_q,\hat{z}_i) \neq d(\hat{z}_i, z_q)$ into a kernel would break positive semi-definiteness and invalidate posterior variances; our design never does that. The decomposition above also means the block distances can be precomputed once per candidate into $M$ small tables of $K$ entries, and the log-kernel against every archive point reduces to $M$ table lookups and additions — the same lookup-table trick that product quantization uses for inner-product search (Quantization based Fast Inner Product Search, Wan et al.). This is what lets the acquisition scan run over millions of decoded candidates at addition cost.

Component 2: codebook centroids as the inference substrate. Cubic inference cost is handled not by discarding data but by treating the quantized archive as a compressed training set for a variational Gaussian process whose inducing points are drawn from the (cheap, byte-sized) archive codes themselves, so inference cost depends on the inducing budget rather than on the number of retained evaluations. The research question for this component is how much surrogate fidelity is lost to quantization noise at realistic code budgets — a question the retrieval literature already partially answers, since Product Quantization Network for Fast Image Retrieval maintains a mean average precision of 0.947 on CIFAR-10 at 16 bits and 0.945 even at 4 bits, suggesting trained codebooks degrade gracefully under extreme compression. We will measure the analogous quantity here: how much does acquisition quality (rank correlation between predicted and true objective over held-out candidates) drop as the code budget shrinks.

Component 3: codebooks trained for the objective, not for reconstruction. Plain product quantization codebooks are learned by $k$-means to minimize reconstruction error, which ignores the fitness landscape — the same "smoothness gap" that motivates objective-aligned retraining in Local Latent Space Bayesian Optimization over Structured Inputs. We borrow the asymmetric triplet loss of Product Quantization Network for Fast Image Retrieval — there, an unquantized anchor is compared against quantized positives and negatives so the representation stays discriminative under asymmetric retrieval — and retrain it for optimization: the anchor is a full-precision candidate, and positives/negatives are quantized archive points ranked above or below it in observed objective value. Codebooks are retrained periodically as the archive grows, exactly as LOL-BO periodically retrains its encoder, which also addresses the codebook domain-shift open problem in the retrieval literature: the codebook tracks the drifting distribution of where the optimizer has been looking. The Instruction-Coupled Kernel of InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models plays an analogous alignment role for soft prompts; our alignment is enforced at the codebook rather than the kernel.

Proposed Experiments

The primary testbed is the Practical Molecular Optimization benchmark of Sample Efficiency Matters: A Benchmark for Practical Molecular Optimization: 23 tasks (QED, DRD2, GSK3β, JNK3, and 19 multi-property objectives), a strict 10,000-oracle-evaluation budget, and the area under the curve of top-10 average score versus oracle calls as the headline metric. This benchmark is the right arena precisely because it is hostile to complex methods — the authors found that REINVENT ranked first and Graph GA second overall while most modern algorithms failed to solve the harder tasks within budget, and the companion survey found that in 128-dimensional latent versions of these tasks CMA-ES and SAASBO were the top performers. No scalar AUC value for REINVENT on PMO is reported on Lacuna, so comparisons will be run under the benchmark's own protocol rather than against a printed number.

The second testbed is the Ehrlich planted-motif sequence tasks at length 64 from the same survey, where most Bayesian methods lost to simple greedy mutation; this directly probes whether full quantized retention changes that verdict. Third, the GuacaMol multi-property tasks (Perindopril, Ranolazine, Zaleplon MPO) on which LOL-BO was evaluated — no scalar score for LOL-BO on these tasks is reported on Lacuna, so we will run LOL-BO ourselves under matched compute. The latent spaces are the grammar-constrained autoencoder spaces of Grammar Variational Autoencoder over ZINC 250K (its grammar masking lifts SMILES validity from 17% to 31% relative to a character VAE, and validity stays near 99% on arithmetic expressions), which matters because pathological decoded artifacts would contaminate the objective landscape. Alongside task scores we will report systems measurements: peak archive memory, largest $N$ retained before failure (Bounce's 40-iteration collapse is the reference failure), and acquisition scan throughput versus archive size.

Baselines

The naive reference point is uniform random sampling of the latent space, which the record shows is not competitive: on the Taxonomy Animal instruction task, InstructZero reports that the prompt-search baseline APE reached only 4% accuracy while latent Bayesian optimization reached 92%. Random sampling is included to calibrate task difficulty, run on identical oracles and budgets. The strongest simple competitors are Graph GA and REINVENT as configured in the PMO benchmark, because the benchmark authors' own finding — REINVENT first, Graph GA second, most modern methods failing under the 10,000-call budget — makes them the incumbent champions, not straw men. They will be run under the benchmark's published protocol with the same scoring oracles, the same 10,000-call limit, and the benchmark's default tuning rather than tuning we control. The strongest latent-space competitor is LOL-BO with its trust-region configuration and dynamic encoder retraining, which on penalized logP over ZINC reports a score of roughly 545 against roughly 26 for its predecessor T-LBO and used 10× fewer oracle calls than competing methods on DRD3 docking; we run it with the same VAE backbone and the same oracle budget as ours so the only difference is the memory mechanism. CMA-ES and SAASBO are included because the survey found them to be the best performers in 128-dimensional latent PMO tasks. Finally, the ablation that isolates the proposal's key ingredient is the identical optimizer with a full-precision sliding-window archive (quantization off, history truncated), and the same optimizer with symmetric quantization of both archive and candidates — the SDC configuration — plus codebooks trained by plain reconstruction $k$-means versus our asymmetric objective-aligned loss. Beating the baselines means a higher mean top-10 AUC across the 23 PMO tasks with no memory failures at $N = 10{,}000$, and the ablations must show that both the retention and the asymmetric training each contribute; if the windowed full-precision archive matches us, the contribution shrinks to a memory saving and we will say so.

Why not just…?

Why not just use a genetic algorithm on the discrete structures directly? This is the most serious objection, and the record backs it: in the PMO benchmark REINVENT and Graph GA beat most modern latent methods within budget, and on length-64 Ehrlich sequences greedy mutation beat most Bayesian methods. Two things temper this. First, genetic operators do not exist in some latent-optimization settings — InstructZero's soft-prompt space is a leading example — whereas a quantized archive transfers unchanged. Second, the benchmark evidence shows methods failing for memory and horizon reasons that retention directly targets; if our complete quantized archive still loses to Graph GA on PMO, that is a decisive negative result we will report, since it would show the sample-efficiency channel through memory is not real at this scale.

Why not just use trust regions and discard history, as LOL-BO already does? Trust regions sidestep the memory problem by never facing it: the Gaussian process sees only a local subset. That works when the optimum is reachable locally, and LOL-BO's penalized logP result (~545 versus ~26) shows local search is powerful. But discarding history means the surrogate cannot exploit long-range structure — earlier discoveries outside the current region — and the survey's evidence that memory pressure kills unbounded methods (Bounce exhausted memory within 40 iterations) shows the underlying tension is unsolved, merely avoided. Our head-to-head against LOL-BO on the same latent spaces, plus an ablation varying window size against full quantized retention, settles empirically whether complete memory helps, hurts, or is neutral.

Why not just use a standard scalable Gaussian process (inducing points, random features)? This is the alternative that would most plausibly match our sample efficiency, and we treat it as a genuine threat. A variational Gaussian process with a few hundred inducing points already makes inference cheap without any quantization. What it does not provide is the persistent archive itself: full-precision history still occupies $D$ floats per point, and scoring candidate batches still costs full kernel evaluations rather than table lookups. We will therefore run a same-budget variational Gaussian process on a windowed full-precision archive as a first-class baseline; if it matches our task scores, the honest conclusion is that asymmetric quantization here is a memory and throughput technology rather than a sample-efficiency technology, and we will frame the contribution accordingly.

Decisive Checks

The proposal succeeds if the quantized-archive optimizer retains all 10,000 PMO evaluations in memory on the order of tens of kilobytes, never exhibits the memory collapse documented for Bounce, and achieves mean top-10 AUC above Graph GA and LOL-BO across the 23 tasks, with the windowed and symmetric-quantization ablations confirming that full retention and asymmetric full-precision-versus-codebook evaluation are each load-bearing. It fails informatively if greedy baselines still win at this budget — in which case the deliverable becomes a clean characterization of when memory retention stops mattering, and the quantized archive stands on wall-clock and footprint alone. On the theory side, the positive semi-definiteness-by-relocation argument will be stated and proved formally, since it is the piece that distinguishes this design from the naive asymmetric-kernel route that the gap analysis correctly flags as broken.