BaCO: A Fast and Portable Bayesian Compiler Optimization Framework

Erik Orm Hellsten, Artur L. F. Souza, Johannes Lenfers, Rubens Lacouture, Olivia Hsu, Adel Ejjeh and 4 others

Modern compilers hand you a pile of knobs — tile sizes, unroll factors, thread counts, and the ORDER to run nested loops in — and finding the combination that makes code fastest is a brutal search, because the space mixes continuous, integer, categorical, and PERMUTATION parameters, many combinations are outright invalid (some you know upfront, some you only discover when compilation crashes), and every single trial costs a full compile-and-run; BaCO (Lund University, Stanford, and collaborators) is a Bayesian-optimization autotuner built for exactly this — it learns a cheap surrogate model of performance so it can propose only the most promising configurations, and crucially it gives the model a sense of DISTANCE between loop orderings (so it knows two similar orderings behave similarly rather than treating all reorderings as unrelated), precomputes the valid configurations to never waste a trial on a known-invalid one, and learns a feasibility model for the hidden failures — reaching expert-level code 2.9-3.9x faster than prior autotuners and 1.36-1.56x faster code on a tiny budget, across CPUs, GPUs, and FPGAs.

The argument in one glance

Problem

Modern compilers expose the knobs and leave the tuning to you

Rather than deciding every optimization internally, modern compilers — especially domain-specific ones for tensors, data-parallel code, and FPGAs — expose SCHEDULING PARAMETERS and let the user (or an autotuner) choose them: tile sizes, unroll factors, thread counts, parallelization schemes, and the order in which to run nested loops. Choosing well can mean an order-of-magnitude speedup, and choosing badly leaves the hardware idle. So the burden shifts from the compiler to a search: find the parameter configuration that makes the generated code fastest. The trouble is that the space of configurations is enormous, oddly shaped, riddled with invalid combinations, and expensive to sample — which makes finding the good configuration a genuinely hard problem.
What people did

Throw a general-purpose search at the configuration space

The established approach is autotuning: search the parameter space automatically. The tools reach for general search methods — random search, grid search, genetic algorithms (OpenTuner), or model-based methods like random forests (Ytopt) and earlier Bayesian optimizers (HyperMapper, ATF). Each proposes configurations, compiles and runs them, keeps what is fast, and iterates. Point one of these at the compiler's knobs and let it grind toward a good configuration.
Why it fell short

General search ignores the structure and wastes a tiny budget

General-purpose search founders on three features of the compiler-tuning space. PERMUTATIONS: loop orderings are permutation parameters with factorially many values AND real structure — the order 1-2-3-4 is nearly the same as 1-2-4-3 — yet tools treat them as unordered categoricals, so a near-miss teaches them nothing about its neighbors. CONSTRAINTS: many configurations are invalid, some by known rules (a loop bound must be a multiple of the tile size), some by hidden failures found only when compilation crashes or memory overflows — and blind search wastes precious trials rediscovering the same invalid regions. COST: each evaluation is a full compile-and-run, so budgets are tiny (tens of trials), and a method that is not extremely sample-efficient never converges in time. The paper surveys 14 autotuners and finds none support all these features together, so each leaves large performance unrealized.
This paper's idea

Specialize Bayesian optimization to the compiler-tuning domain

BaCO (Lund University, Stanford, and collaborators) is a Bayesian-optimization autotuner built for exactly this space, portable across CPU, GPU, and FPGA compilers. It learns a cheap SURROGATE model of performance from the few configurations it has tried, and proposes next only the ones the model predicts are both fast and likely-valid — so every expensive compile-and-run buys maximum information. Three specializations make it work. It gives permutations a DISTANCE METRIC (how similar two loop orderings are), so the model generalizes across orderings instead of treating them as unrelated. It precomputes the valid configurations with a Chain-of-Trees structure, so it never proposes a KNOWN-invalid configuration. And it learns a FEASIBILITY model that predicts HIDDEN failures, steering away from configurations that would crash. The result: expert-level code reached 2.9-3.9x faster than prior autotuners, and 1.36-1.56x faster code under a tiny budget.

Why this problem is worth solving

As compilers push more scheduling decisions onto autotuners, the quality of the autotuner increasingly determines the quality of the generated code — and the search it must do is unusually awkward. The awkwardness starts with the parameters themselves, especially the

parameters whose value is an ordering rather than a number or a category. The most important example is loop order: a nest of loops can be executed in any permutation of its levels (run loop 3 outermost, then 1, then 2, then 4), and the choice dramatically affects cache behavior and parallelism. Permutations are hard for a search for two reasons. There are FACTORIALLY many of them, so the space is huge. And, more subtly, they have STRUCTURE: the ordering 1-2-3-4 is very similar to 1-2-4-3 (one adjacent swap) and very different from 4-3-2-1 (fully reversed), so nearby orderings tend to perform similarly. A search that treats every ordering as an unrelated category throws that structure away — it cannot infer that a good ordering’s neighbors are probably good too, so it learns almost nothing from each expensive trial

. Getting value from a permutation parameter requires a notion of which orderings are close, and general-purpose autotuners simply do not have one.

The second and third difficulties compound the first. Many configurations are invalid, and the invalidity comes in two flavors that must be handled differently — the

the two ways a parameter configuration can be invalid. A KNOWN constraint is one you can state up front from the compiler’s rules — for instance, a loop bound must be an exact multiple of the tiling factor, or two parameters must not both be set. These can be checked without running anything, so an ideal search would simply never propose a configuration that violates them. A HIDDEN constraint is one you cannot know in advance: a configuration that looks valid but causes the compiler to run out of registers, exhaust memory, or crash — discovered only by trying it. Hidden constraints cannot be avoided by inspection; they can only be LEARNED from failed attempts. The two demand opposite treatments — prune the known ones away before searching, and build a model to predict the hidden ones — and mishandling either wastes the scarce evaluation budget

. And that budget is genuinely scarce, because every configuration must be compiled and run to measure, which can take seconds each, so a useful autotuner has only tens of trials to work with. Put together — structured permutations, two kinds of constraints, and a tiny budget — the compiler-tuning space needs a search that is both structure-aware and sample-efficient, which is exactly the gap BaCO fills.

What people did before, and where it broke

Random and grid search. Sample configurations blindly (random) or exhaustively on a lattice (grid). Simple and unbiased, but they learn nothing from past trials, ignore all structure, and waste most of a tiny budget on bad or invalid configurations.
Genetic algorithms (OpenTuner). Evolve a population of configurations. They can handle permutations, but they do not model constraints properly and are not sample-efficient enough for a tens-of-trials budget, so they need far more evaluations to converge.
Random-forest model search (Ytopt). Learn a random-forest surrogate of performance. Better than blind search, but the model misses permutation structure (it treats orderings without a distance), so it cannot generalize across loop orders.
Earlier Bayesian optimizers (HyperMapper, ATF). Use a surrogate and acquisition function, which is the right family — but they lack proper permutation kernels and hidden-constraint handling, so they stumble on exactly the features that make compiler tuning hard.
The gap. Of 14 surveyed autotuners, none handle permutation structure, known AND hidden constraints, and mixed parameter types together with the sample efficiency a compile-and-run budget demands. BaCO is built to do all of it at once, which is why it reaches expert performance in a fraction of the trials.

How BaCO works

Model performance cheaply, respect the structure, prune the invalid, and propose smart

Treat tuning as expensive black-box optimization new

Because each configuration costs a full compile-and-run, BaCO does not brute-force the space. It runs a Bayesian-optimization loop: from the handful of configurations tried so far, learn a cheap surrogate model of performance, use it to pick the most promising next configuration, evaluate that one, update the model, and repeat — so every expensive evaluation buys the most information.
↓ →
Model performance with a Gaussian process new

The surrogate is a Gaussian process that predicts a configuration's runtime AND its uncertainty, using a Matern kernel over a weighted distance that combines each parameter's own distance, with a learned lengthscale per parameter so the model can down-weight the ones that barely matter. Exponentially-scaled parameters (like tile sizes) are compared in log-space to densify the search.
↓ →
Give permutations a distance metric new

The key specialization: instead of treating loop orderings as unrelated categories, BaCO measures how similar two orderings are — trying Kendall distance (swapped pairs), Spearman rank correlation (squared position changes, which works best), and Hamming distance (changed positions). Now the model knows a good ordering's neighbors are probably good, so each trial informs many orderings.
↓ →
Precompute the valid space for known constraints new

Known constraints are handled by a Chain-of-Trees data structure that enumerates all feasible configurations ahead of time, so the search only ever proposes valid ones — never wasting a trial on a known-invalid configuration. This cut constraint-checking time 6x and random sampling 80x, and uniform sampling from the tree's leaves removes a parameter-order bias.
↓ →
Learn a feasibility model for hidden constraints new

Hidden failures (out-of-memory, register overflow, compiler crashes) cannot be known in advance, so BaCO trains a random-forest feasibility model that predicts the probability a configuration is valid, learning from every failed attempt. The acquisition function multiplies expected performance improvement by this feasibility probability, with a threshold that provably never permanently rules out a real solution.
↓ →
Propose, evaluate, update — portably new

Each round, a multi-start local search maximizes the feasibility-weighted expected improvement to pick the next configuration; BaCO compiles and runs it, updates both models, and iterates, converging in tens of trials. It treats each compiler as a black box needing only parameter ranges and known constraints, so the same framework tunes TACO (CPU), RISE & ELEVATE (CPU/GPU), and HPVM2FPGA (FPGA) with no per-compiler changes.

Evaluated on three real compiler systems — TACO (sparse tensor, CPU), RISE & ELEVATE (functional data-parallel, CPU and NVIDIA GPU), and HPVM2FPGA (Intel Arria 10 FPGA) — across 15 kernels, against random search, OpenTuner, Ytopt, and ATF, under tiny (tens of trials) to full evaluation budgets.

The idea

Give the model a notion of distance that reflects real similarity. The specialization that most distinguishes BaCO is how it treats loop orderings. A permutation is not a number and not an unordered label — it is an ordering with its own geometry, where some orderings are near-neighbors and others are far apart, and that geometry predicts performance because nearby orderings touch memory similarly. General autotuners flatten permutations into categories, losing this entirely, so a good ordering they discover tells them nothing about the ordering next to it. BaCO instead equips its model with a distance metric (Spearman rank correlation works best), so a single trial informs the model about a whole neighborhood of orderings. This is the match-the-representation-to- the-structure discipline the site keeps rewarding — the noisy-quantum page viewing outcomes in Hamming space to see that errors cluster, the spiking-network page threading data onto a locality-preserving curve — here giving a search a similarity metric so it can generalize across a factorial space instead of memorizing points in it.

When each evaluation is expensive, model the function and search the model. Compiling and running a configuration costs real time, so a search that samples blindly cannot afford enough trials to find the optimum. BaCO’s Bayesian-optimization backbone answers this by building a cheap SURROGATE — a Gaussian process that predicts performance and uncertainty from the few trials seen — and letting the surrogate, not the real compiler, guide where to look next, spending each precious evaluation where the model expects the most improvement. This is the surrogate-for-an-expensive-oracle discipline the site meets whenever measuring the real thing is costly: the GNN-scheduling page learns a cost model to pick kernels without trying them all, the GPU-microservice page forecasts stage performance it cannot afford to profile live. The move is always the same — replace an expensive query with a cheap prediction, and spend the real queries only where the prediction is most uncertain or most promising.

Prune what you can know, and learn what you cannot. Invalid configurations are budget poison, and BaCO’s cleanest idea is to split them by knowability and treat each optimally. Known constraints are stated up front, so there is no reason to ever propose a violating configuration — BaCO precomputes the entire feasible set (a Chain-of-Trees) and searches only inside it, so not one trial is wasted on a rule it already knew. Hidden constraints cannot be foreseen, so the only option is to LEARN them — a feasibility model that grows more accurate with every crash and steers the search away from failure-prone regions. Handling both, each in the way its knowability allows, is what keeps the tiny budget spent on informative, valid trials. It is the same spend-the-scarce-resource-only-where-it-counts discipline the edge-inference page applies to an IO budget and the accelerator page applies to offload — here applied to evaluation trials, by refusing to spend any on avoidable invalidity.

Tuning one kernel on a tiny budget

Why a structure-aware search converges where blind search stalls

Autotuning a compiler kernel where each trial is a full compile-and-run. Numbers from BaCO's evaluation.

Step 1 of 5

The knobs and the cost

The kernel exposes tile sizes, unroll factors, a parallelization scheme, and the order of its nested loops. Each configuration must be compiled and run to measure, taking seconds, so realistically you get only tens of trials — perhaps 60 — to find a configuration that rivals a human expert. Every trial is precious.

the space mixes continuous, integer, categorical, and permutation parameters, plus invalid combinations
choosing well can be an order-of-magnitude speedup; choosing badly wastes the hardware

Why it works

Loop orderings are permutations with real structure (near-neighbors perform similarly) → BaCO gives the model a distance metric (Spearman) so a trial informs a whole neighborhood → it generalizes across a factorial space instead of memorizing points.
Each evaluation is an expensive compile-and-run → a Gaussian-process surrogate predicts performance and uncertainty from few trials, and guides where to look → every real evaluation is spent where it buys the most information.
Known constraints can be checked without running → a Chain-of-Trees precomputes the feasible set and the search stays inside it → not one trial is wasted on a rule already known (constraint checks 6x faster, sampling 80x).
Hidden failures appear only at compile or run time → a random-forest feasibility model learns them from crashes and down-weights risky regions → the tiny budget goes to valid, informative trials, with a safeguard against ruling out real solutions.
The compiler is treated as a black box needing only ranges and known constraints → the same framework ports to CPU, GPU, and FPGA compilers unchanged → one autotuner beats experts across all three.

What it costs

Still too slow for the edit-compile loop. BaCO finds strong configurations in under 100 seconds, but that is still too long to run inside an interactive software-development loop — the dream of autotuning-in-the-editor remains unreached.
Parametric spaces only. BaCO tunes the knobs a compiler exposes; it does not tackle the phase-ordering problem (searching over unbounded sequences of transformations), so it needs compilers that present their optimizations as tunable parameters.
Still needs the ranges and known constraints. Users must define each parameter’s range and state the known constraints; only the hidden constraints are learned automatically, and that learning assumes compilation and execution give clear failure signals.
Single objective. BaCO optimizes runtime alone; it does not do multi-objective tuning (trading runtime against power, memory, or throughput), which many real deployments need.
Global hyperparameters and limited coverage. Its own hyperparameters (the priors, the feasibility threshold) are set globally rather than per-application, and the evaluation spans 15 kernels on 3 frameworks — portability to other domain-specific compilers (TVM, Halide) is argued but not demonstrated.

The evaluation

Fifteen kernels across three real compiler systems — TACO (sparse tensor, CPU), RISE & ELEVATE (functional data-parallel, CPU and NVIDIA GPU), and HPVM2FPGA (Intel Arria 10 FPGA) — compared against random search, OpenTuner, Ytopt, and ATF, from tiny (a third of the full budget) to full evaluation budgets.

Autotuning a compiler's parameter space

Property	Random / grid search	Genetic / RF autotuners (OpenTuner, Ytopt)
Permutation (loop-order) structure
Known constraints
Hidden constraints
Sample efficiency (tiny budget)
Portability (CPU/GPU/FPGA)	Generic but structure-blind	Varies by tool

BaCO is the only framework to beat the human expert on every benchmark across all three compilers, reaching expert-level performance 2.9-3.9x faster and producing 1.36-1.56x faster code under a tiny budget. Its ablation shows no single specialization dominates — removing any one costs about 20%, and the win comes from handling permutations, both kinds of constraints, and mixed types together.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

BaCO tunes the parameters a compiler exposes, not the deeper phase-ordering problem of searching over transformation sequences, so it needs compilers that present optimizations as tunable knobs and still relies on the user to supply each parameter’s range and the known constraints (only hidden constraints are learned, and that learning assumes clear compile/run failure signals). It optimizes runtime alone — no trading against power, memory, or throughput — and its own hyperparameters (priors, feasibility threshold) are set globally rather than per application. It reaches strong solutions in under 100 seconds, still too slow to sit inside an interactive edit-compile loop, and the evaluation covers 15 kernels on three frameworks, so portability to other domain-specific compilers is argued from the black-box design rather than demonstrated. None of this weakens the core lesson — that compiler autotuning is a search over a structured, constraint-riddled, expensive-to-sample space, and the way to win it is to give the model a distance metric that respects permutation structure, to prune known-invalid configurations before searching and learn the hidden ones, and to let a cheap surrogate spend each precious compile-and-run where it buys the most information, which together reach expert-level code several times faster than prior autotuners across CPU, GPU, and FPGA.

Background

Respect the structure, model the expensive oracle, and never waste a trial

BaCO sits in the site’s compilers-and-autotuning cluster and rhymes with several ideas covered elsewhere on this site. Its signature move is to give the search a notion of DISTANCE that reflects real similarity — treating loop orderings as points in a structured space where near-neighbors behave alike, rather than as unrelated categories — which is the same match-the-representation-to-the- structure discipline the noisy-quantum page uses when it views outcomes in Hamming space to reveal that errors cluster near the truth, and the spiking-network page uses when it threads data onto a locality-preserving curve so connected work stays close. Its backbone is the surrogate-for-an-expensive-oracle pattern: when each evaluation is a costly compile-and-run, learn a cheap model of performance and let it decide where to spend the real queries, the same move the GNN-operator page makes with a learned cost model to pick kernels and the GPU-microservice page makes when it forecasts stage behavior it cannot profile live. And its constraint handling is a spend-the-scarce-budget-only-where-it-counts discipline split by knowability — prune the known-invalid configurations before searching (as the optimal-inlining page prunes its space by exploiting independence) and learn the hidden ones from failures — so no trial is wasted, the same refusal-to-waste-the-scarce-resource that the edge-inference page brings to an IO budget. Even its honest ablation — no single feature dominates, each worth about 20%, the win is the combination — is the composed-systems-win the site keeps seeing, where handling every awkward feature of a real problem at once, rather than any one cleverly, is what beats the experts.

If you remember only three things

1. Modern compilers expose scheduling knobs — tile sizes, unroll factors, thread counts, loop orderings — and leave an autotuner to search for the fastest configuration, but the space is brutally hard: it mixes continuous, integer, categorical, and PERMUTATION parameters (loop orders, factorially many but with real structure), many combinations are invalid (some by KNOWN rules, some by HIDDEN failures found only at compile/run time), and every trial costs a full compile-and-run, so budgets are tiny — and prior autotuners ignore permutation structure, waste trials on invalid configs, or cannot handle hidden constraints.
2. BaCO specializes Bayesian optimization for this domain: it learns a Gaussian-process surrogate of performance so each expensive evaluation is spent where the model predicts the most gain; it gives permutations a DISTANCE metric (Spearman rank correlation) so a good loop ordering informs the model about similar orderings instead of being an isolated point; it precomputes the feasible set with a Chain-of-Trees so it never proposes a known-invalid configuration (constraint checks 6x faster); and it learns a random-forest feasibility model to predict and avoid hidden failures, weighting expected improvement by feasibility probability.
3. The result reaches expert-level code 2.9-3.9x faster than prior autotuners and produces 1.36-1.56x faster code under a tiny budget across CPU, GPU, and FPGA compilers (TACO, RISE & ELEVATE, HPVM2FPGA) — the only framework to beat the human expert on every benchmark, even finding loop orderings experts missed — with an ablation showing no single specialization dominates. Honest limits: parametric spaces only (not phase-ordering), still needs user-supplied ranges and known constraints, single-objective, and under-100-second tuning still too slow for the edit loop. The durable lessons: give the search a distance metric that respects structure, model an expensive oracle with a cheap surrogate, and never waste a trial on avoidable invalidity.

Check yourself

Check your understanding

1. BaCO's signature specialization is giving loop orderings (permutation parameters) a distance metric, rather than treating them as unordered categories like prior autotuners. Predict why this matters so much for sample efficiency.
2. Each configuration BaCO tries requires a full compile-and-run, and its budget is only tens of trials. Predict why Bayesian optimization (a surrogate model plus an acquisition function) is the right tool for this regime.
3. BaCO splits invalid configurations into KNOWN constraints (precomputed and never proposed) and HIDDEN constraints (learned from failures). Predict why the two kinds demand opposite treatments.
4. BaCO's ablation shows that removing any single specialization (permutation kernel, transformations, priors, feasibility model) costs about 20%, but no single feature dominates. Predict what this reveals about why it beats prior autotuners.

Sources

arXiv:2212.11142 — BaCO: A Fast and Portable Bayesian Compiler Optimization Framework — ASPLOS 2023 (full text read via ar5iv).
ACM DL: BaCO (ASPLOS 2023) — published version.