[October 2026 edition]

Indexes and the Art of Searching, Part 8: Choosing Methods and a Decision Tree

Published: Oct 2, 2026
Reading time: ~13 min

Part 7 covered how evaluation functions are built. Part 8 looks at how to choose among the methods covered so far.

1. Settings Tuned to the Evaluation Data

The settings and results of a method reported in a paper are tuned to the data used to evaluate it. Move to different data, and the results change. The same pattern has come up in each field in earlier parts. Part 3 covered how BM25 and dense vector retrieval trade places as the winner on BEIR, and Part 4 covered out-of-distribution queries and the reproducibility of neural recommendation. Here I look more closely at the learned indexes introduced in Part 2 and at combinatorial optimization with neural methods.

Evaluations of learned indexes show that results depend on the data distribution. The evaluation using SOSD used 4 datasets, each with 200 million 64-bit integer keys. On the osm dataset, at almost every size, RBS, which narrows the range with a radix table and then runs binary search, matched or beat both learned and traditional indexes. That dataset has little local structure, so a model needs more memory to reach a comparable error. The face dataset contains about 100 huge outliers, which left the first 16 bits of RBS’s radix table nearly useless and caused a large drop in performance. On the amzn and wiki datasets, learned indexes were Pareto-optimal up to 100MB. Comparing index size against lookup speed, at every size up to 100MB a learned index was either the fastest at that size or reached a given speed with the smallest index. The paper states explicitly that it evaluated on real data because synthetic data is surprisingly easy to learn and favors learned indexes.

For workloads that include updates, there is the evaluation by Wongkham and colleagues. On 10 real datasets, ALEX and LIPP outperformed traditional indexes in more than 80% of data and workload combinations with a single thread, but some designs lost performance under concurrency. In realistic settings with updates, memory use dropped by up to 3.2 times. The paper recommends measuring how hard the data is and taking that hardness into account when deciding to use these indexes.

Combinatorial optimization with neural methods shows the same pattern. On the traveling salesman problem with 100 cities, the attention-based method of Kool and colleagues reached 8.12 with greedy construction (a 4.53% gap, 6 seconds) and 7.94 (2.26%) with 1 hour of sampling, against 7.76 for Concorde, LKH3, and Gurobi. The figures are average tour lengths, and the gap is how many percent longer the route is than the best solution. OR-Tools reached 7.99 (2.90%). The authors themselves write that beating specialized solvers such as Concorde is not their goal, and they note that quality degrades the further the problem size moves from the size used in training. A 2024 paper by Xia and colleagues reports that a simple distance-based baseline that needs no training outperformed complex machine learning models. A survey of neural routing solvers points out that past evaluations have favored methods overfitted to the training distribution and have compared them against weak classical baselines or under unfavorable time settings.

The same holds for learning how to choose branching variables in branch and bound. The method of Gasse and colleagues solved problems faster than SCIP’s default rule in almost every setting. On the maximum independent set problem, however, every machine learning method solved fewer instances than the default rule. Distributional MIPLIB evaluated on 3 unseen distributions, and on each of them SCIP matched or beat the learned methods.

Outside the range they were tuned for, the results change. So retrain a learned method on your own data, and always measure it before you rely on it.

2. Choosing a Search Algorithm as a Search Problem

With so many methods, and with their fit depending on the data, choosing a method becomes a search in its own right. When you look up a word in a dictionary, you go straight to the headword if you know it exactly, and if you only half remember it, you flip back and forth around where it should be. Changing your approach based on the nature of the problem comes naturally, and automating it means building something that takes a problem’s features and returns one method to use. Research has treated this as the algorithm selection problem. The textbook formulation defines a set of problems to solve, a set of available algorithms, and a performance measure, and builds a mapping that picks a high-performing algorithm for each problem.

SATzilla starts from the premise that the best SAT solver changes from instance to instance. It predicts the running time of each solver on each instance, picks a solver, and won 3 gold, 1 silver, and 1 bronze medals at the 2007 SAT Competition. ASlib is a collection of algorithm selection benchmarks. Of the gap between the single best solver and the ideal of picking the best solver for every instance, selection closed 0.90 on SAT11-RAND and 0.91 on CSP-MZN-2013, but at best only 0.15 on SAT11-INDU. The ASlib paper cautions that many of its scenarios come from papers that reported performance gains from selection.

Selection has its own costs. SATzilla included the time for computing features and running pre-solvers in its own running time when comparing. The report on the selection competitions notes that on industrial SAT, feature computation can take more than half of the time budget. Training costs something too. Gagliolo and Schmidhuber pointed out that offline selection ignores the cost of solving the training instances with every algorithm, and they took an approach with no prior training that learns how to choose while solving problems. It tries methods to find out which is good, gives more time to the ones performing well, and occasionally tries the others to revise its view. Textbooks call this problem of allocating effort between exploring and exploiting a bandit problem. Because there is no upper bound on a method’s running time known in advance, the paper treated it as a bandit problem with losses that have no known upper bound. Frugal Algorithm Selection reduces the cost of labeling training data through active learning and timeout prediction. Hyperband allocates resources adaptively in hyperparameter optimization and stops runs early, and it reports speedups of 5 to 30 times over Bayesian optimization. It runs selection and solving together, which keeps selection from eating up the budget.

Whether a selection carries over to other data depends on the data used for training. A 2024 study by Dietrich and colleagues showed that a selector trained only on BBOB’s component functions performed poorly on a test set of 11,920 generated problems. A 2026 study by Cenikj and colleagues reports that selection models trained on BBOB and CEC generalize poorly to real problems such as robot trajectory optimization and UAV path planning, often performing no better than a dummy baseline. Meta-selection, which selects the selector itself, has also been tried, but in the experiments of Tornede and colleagues, on a majority of instances the single best selector matched or beat every meta-selection method. The results of studies like these are useful as a guide when picking the first candidates to try on your own data.

3. Designs That Keep Guarantees

If a method’s results depend on the distribution, one option is to secure a floor in the design for when predictions miss. The algorithms-with-predictions framework allows any predictor at all. When you look up a word in a dictionary, you open the page you guess it is on and widen the search from there. If the guess is right, a few pages are enough, and if it is wrong, you can switch to halving the remaining pages at the end, which keeps the effort roughly the same as an ordinary lookup. The chapter by Mitzenmacher and Vassilvitskii sets these two properties as goals: consistency, near-optimal performance when the prediction is good, and robustness, performance on par with an algorithm without predictions even when the prediction is far off. The binary search with predictions mentioned in Part 2 corresponds to this way of using a dictionary. If η is the distance between the predicted and actual positions, the number of comparisons is at most 2 log η, and because that distance is at most the length of the array, the number of comparisons stays within 2 times that of binary search however wrong the prediction is. Ski rental is the problem of deciding, without knowing how many days you will ski, whether to keep renting skis each day or buy them at some point. The ratio of the actual cost to the minimum cost you could have achieved knowing everything in advance is called the competitive ratio, and a parameter λ keeps the competitive ratio at 1+λ when the error is 0 and at 1+1/λ however large the error is. The smaller λ is, the more you trust the prediction: when it is right, the cost comes closer to the minimum, and when it is wrong, the ratio grows, so consistency and robustness trade off against each other.

Learned Bloom filters are built on the same idea. A Bloom filter tolerates one-sided error: a “not present” answer is always correct, and only a “present” answer is occasionally wrong. Letting a learned model make the decision can produce false negatives, where a key that is actually present gets a “not present” answer, so every key the model answers “not present” for is passed through a backup Bloom filter to prevent them. NeuroBack for SAT uses a GNN to predict once, in advance, which value each variable should be tried with first, true or false (its phase), favoring the side more likely to appear in a solution, and passes that to Kissat, a CDCL solver. It avoids the cost of running inference online at every step and leaves the skeleton of the search to the classical method. The authors report solving up to 5.2% more problems on SATCOMP-2022 and up to 7.4% more on 2023 (counting only problems where inference succeeded).

The reach of predictions has limits too. Tree Search With Predictions shows that while binary search with predictions on a sorted array needs only O(log η), generalizing to trees does not achieve O(log η) in general, and on a tree of pathwidth k the cost is O(k log η). An array corresponds to a tree that is a single path, and pathwidth grows as the branching becomes more tangled, so the more a tree branches, the weaker the effect of predictions becomes. Once you leave the array, it becomes hard to make good use of predictions.

The same thinking applies when you have an LLM write search code. A 2026 study by Wang and colleagues reports that prompting an LLM to optimize yields median speedups of only 1.03 to 1.12 times, and that formalizing the variables, constraints, and objective and handing them to a verified solver wins on correctness.

4. A Decision Tree for Large-Scale Data

I have tried to organize the content of the earlier parts, in my own way, into a procedure for choosing methods on large-scale data. Thresholds for record counts and memory differ by environment, so decide them by experimenting on your own data, following the steps at the end of the tree.

What shape does the answer take?
├─ Keys, ranges, order (Parts 1 and 2)
│    ├─ Few updates: use sorting + binary search or a B-tree as the baseline.
│    │               Add learned indexes as candidates if the key distribution is smooth and the workload is read-heavy
│    ├─ Many updates: B-tree, LSM-tree, hash table
│    ├─ Need to rule out absence first: Bloom filter, skip index
│    └─ Identity, changed ranges: hashing
├─ Patterns, words (Part 3)
│    ├─ Strings: measure by alphabet and pattern length. For many patterns, the Aho–Corasick algorithm
│    └─ Documents: use an inverted index + BM25 as the baseline, and add a reranker if needed
├─ Similarity, relatedness (Part 4)
│    ├─ ANN: use graph-based indexes as the baseline for standard embeddings.
│    │       Measure out-of-distribution queries, filtering, and memory limits with your own queries
│    ├─ Need both lexical and semantic matching: combine BM25 and vectors, and fuse the rankings
│    └─ Recommendation: candidate generation → ranking. Use neighborhood methods or iALS as the baseline
└─ Constructing solutions (Parts 5–7)
     ├─ Need guarantees: formalize and hand off to an existing solver (MIP, SAT, CP-SAT).
     │                  For repeated queries on the same graph, preprocess (CH, HL)
     ├─ A good solution is enough: start from local search as the baseline, choose simulated annealing,
     │                               PSO, ACO, and others by their components and parameters, and tune on your own data
     └─ Evaluation function: consider relaxation → feature design → verifiers in that order, and close the holes

Steps common to every branch
 1. Build an evaluation set from your own data, queries, and load (include hard queries, out-of-distribution queries, and updates)
 2. Put simple baselines in place first (binary search, BM25, neighborhood methods, existing solvers)
 3. Only where the baseline falls short, add approximations and preprocessing, cheapest first
 4. Include every cost in the evaluation: construction, preprocessing, updates, memory, inference, and feature computation
 5. Keep the component with worst-case guarantees, and layer learning and approximation on top of it
 6. When the distribution, updates, or queries change, go back to 1

The re-evaluation in step 6 ties back to the view from Part 1 of an index as a system you keep maintaining.

5. Four Design Decisions

A system’s performance comes down, by and large, to four decisions: what to arrange in advance for which queries, what to summarize, at what granularity to detect changes, and how much accuracy you can give up. Whether you picked the best search or exploration algorithm for the conditions only starts to matter once those four are settled. B-trees, Bloom filters, and HNSW differ only in how they answer those four questions; they all solve the same problem of reaching the answer by reading as small a part of the whole dataset as possible.

Search over solution spaces has the same shape of decisions. Route finding that preprocesses the road network is an example of deciding what to summarize in advance at the cost of space and time, and methods that give up optimality guarantees to discard branches are another answer to how much accuracy you can give up. What sets search apart is that it discards branches based on local evaluations without being able to see the whole set of candidates, so the decision about which branches to discard directly affects the quality of the answer. Choosing whether to make data easy to look up, to look it up, or to search for a solution is also a decision about how far ahead to prepare for the queries still to come, and what to give up in exchange.