🤖 AI

Learning Splitting Heuristics for Parallel String Solvers

This paper proposes a data-driven approach to automatically learn splitting heuristics for parallel string solvers, demonstrating that these learned heuristics significantly outperform manually designed ones in both the number of solved formulas and average solving time when implemented in Z3seq and Z3str4.

Original authors: Chenhao Gao, Peisen Yao

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chenhao Gao, Peisen Yao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, incredibly complicated jigsaw puzzle. This puzzle represents a computer program's logic, specifically one that deals with text (like passwords, user names, or file paths). Your goal is to figure out if there is a way to arrange the pieces so that everything fits together perfectly (a "satisfiable" solution) or if the puzzle is broken and impossible to complete (an "unsatisfiable" solution).

This is the job of a String Solver. However, these puzzles are often so huge and complex that a single person (or a single computer core) trying to solve them piece-by-piece would take forever.

The Problem: Too Many Choices, Too Slow

To solve these puzzles faster, computers use a strategy called "Divide and Conquer." Instead of trying to solve the whole thing at once, they split the big puzzle into two smaller piles. They then send these piles to different workers (computer cores) to solve simultaneously.

The critical question is: How do you decide which piece to cut the puzzle with?

If you cut it in the wrong place, you might end up with two huge, difficult piles that still take forever to solve.
If you cut it in the right place, you might instantly solve one half or make the remaining half very easy.

Currently, computers use hand-crafted rules (heuristics) to decide where to cut. Think of these rules like a recipe written by a human chef who has never tasted the specific ingredients in your kitchen. The chef might say, "Always cut the red piece first," but sometimes the red piece is actually the hardest part of the puzzle. These manual rules are often sub-optimal and require a lot of human effort to tweak.

The Solution: Owl (The Learning Chef)

The authors of this paper introduce a new tool called Owl. Instead of relying on a static recipe, Owl is a data-driven learner. It watches the computer solve thousands of puzzles, learns from its mistakes, and figures out the best way to cut the puzzle for each specific instance.

Here is how Owl works, using a simple analogy:

1. The Old Way: The "Taste Test" (Pairwise Classification)

Previous attempts to automate this used a method like a blind taste test. To decide between two pieces (Piece A and Piece B), the computer would ask, "If I pick A, is it better than B?" It would do this for every possible pair.

The Flaw: This is slow and prone to errors. If the computer makes a small mistake early on (thinking A is better than B), that mistake compounds, leading to a terrible final choice. It's like trying to rank 100 songs by only comparing them two at a time; one bad comparison ruins the whole list.

2. The Owl Way: The "Time Machine" (Regression)

Owl takes a smarter approach. Instead of asking "Is A better than B?", it asks, "How long will it take to solve the puzzle if I pick A?" and "How long will it take if I pick B?"

The Analogy: Imagine you are a project manager. Instead of asking your team, "Is Task A better than Task B?", you ask your AI assistant, "If we do Task A, how many hours will the project take? If we do Task B, how many hours?"
The Benefit: The AI gives you a specific number (e.g., "Task A takes 2 hours, Task B takes 10 hours"). This preserves the full picture. You don't just know A is "better"; you know it's much better. This avoids the chain of errors seen in the old method.

3. The Features: Reading the Crystal Ball

To make these predictions, Owl looks at two types of clues (features):

Static Features: These are like looking at the puzzle box cover. They tell Owl the shape of the pieces, how many red pieces there are, and the general complexity of the image.
Dynamic Features: These are like watching the puzzle being assembled in real-time. Owl checks: "Has this piece caused conflicts before? Does it seem to unlock other pieces quickly?"

By combining these clues, Owl builds a model that predicts the "solving time" for any potential cut. It then picks the cut that promises the shortest time.

The Results: Faster and Smarter

The authors tested Owl on two of the world's best puzzle solvers (Z3seq and Z3str4). They found that:

More Puzzles Solved: With Owl helping, the computers solved significantly more puzzles before running out of time. For example, with 4 workers, Z3seq solved 46 more puzzles than it could on its own.
Faster Speed: The average time to solve a puzzle dropped by about 44% to 59%.
Scalability: The more workers (computer cores) they added, the better Owl performed, proving it knows how to manage a team effectively.

Summary

In short, this paper replaces the "guess-and-check" manual rules for splitting complex text problems with a smart, learning system. Instead of asking "Which is better?", the system asks "How long will this take?" and uses that precise answer to make the best decision. This turns a slow, error-prone process into a fast, efficient one, allowing computers to solve complex string problems much more effectively.

Technical Summary: Learning Splitting Heuristics for Parallel String Solvers

Problem Statement

String constraint solvers are essential for verifying string-manipulating programs in domains such as security policy enforcement and symbolic execution. However, many practical string constraints are undecidable, and existing solvers often struggle with scalability and complex real-world instances. While multi-core architectures offer an opportunity for parallel solving, the effectiveness of divide-and-conquer strategies (specifically cube-and-conquer) relies heavily on the quality of splitting heuristics. These heuristics determine which atom (constraint) to branch on to partition the search space into subproblems.

Current splitting heuristics are typically manually designed and static. They often fail to adapt to the specific structural characteristics of individual constraint instances. Furthermore, existing automated approaches in the SAT domain, such as pairwise classification, suffer from significant limitations when applied to SMT string solving:

Loss of Quantitative Information: Reducing solving times to binary labels discards fine-grained cost data.
Cascading Errors: Serial comparisons in pairwise classification lead to error accumulation, degrading prediction quality.
Scalability: Pairwise methods require linear (or worse) scans over candidate pairs, which is computationally expensive.
Domain Applicability: Prior automated methods have been validated primarily in SAT, with unproven applicability to SMT theories like strings.

Methodology

The authors introduce Owl, a data-driven framework that automatically generates splitting heuristics for parallel string solvers. The core innovation is reframing the atom selection problem from a classification task to a regression task.

1. Problem Formulation as Regression

Instead of comparing two atoms to determine which is "better" (classification), Owl predicts the continuous solving time ( $Time(\varphi, p)$ ) required to solve the subproblems induced by splitting on a specific atom $p$ .

Cost Definition: The target variable is defined based on the parallel execution outcome of the two branches ( $\varphi \land p$ and $\varphi \land \neg p$ ). For example, if both branches are satisfiable, the cost is the minimum of their solving times; if both are unsatisfiable, the cost is the maximum.
Advantage: This approach preserves the continuity of performance metrics, avoids the discretization errors of classification, and eliminates the need for exhaustive pairwise comparisons, thereby reducing inference overhead.

2. Feature Engineering

To support the regression model, the authors designed a comprehensive feature set of 77 features for each candidate atom, divided into two categories:

Static Features (66 features): Derived from the formula structure without solver execution. These include operator distributions (e.g., counts of str.increment, re.union), clause sizes, and graph properties (e.g., variable-clause degrees).
Dynamic Features (11 features): Captured via short-term lookahead and lookback heuristics during solver execution.
- Lookback: Tracks historical solver states, such as the number of times an atom appeared in conflict clauses or learned lemmas.
- Lookahead: Simulates limited constraint propagation (typically capped at ~600 conflicts) to observe immediate consequences, such as the number of new assignments or learned clauses.

3. Model Selection and Training

Algorithm: The system employs Random Forest Regression as the core predictive model. This choice balances predictive accuracy with inference speed and robustness to noisy labels (variations in solving times).
Training Data: A dataset is constructed by running the solver on diverse benchmark formulas, splitting on various atoms, and recording the resulting solving times and feature vectors.
Deployment: The trained model is integrated into the solver (Z3seq and Z3str4). At each decision point, the solver constructs a feature matrix for candidate atoms, sends it to a parallel worker process via IPC, and receives the predicted atom with the lowest estimated solving time.

Key Contributions

Novel Formulation: The paper proposes recasting the design of splitting heuristics for parallel string solving as a regression problem rather than a pairwise classification problem.
Practical Learning Framework: It introduces a framework that automatically generates heuristics using a rich set of 77 dedicated instance features (static and dynamic).
Implementation and Evaluation: The approach is implemented and evaluated on two state-of-the-art string solvers, Z3seq and Z3str4, demonstrating significant performance gains over manually designed heuristics.

Experimental Results

The authors evaluated Owl on 1,024 QF_SLIA formulas from the SMT-LIB repository using 4, 8, 16, and 32 threads.

Solving Capacity: With 4 threads, Z3seq(Owl) solved 46 more formulas (a 4.8% increase) than the baseline, and Z3str4(Owl) solved 9 more formulas. These improvements were sustained across all thread configurations.
Runtime Performance:
- Z3seq(Owl) achieved an average speedup of 1.44× at 32 threads.
- Z3str4(Owl) achieved an average speedup of 1.59× at 32 threads.
Prediction Accuracy: The regression models significantly outperformed the default lookahead heuristics and a pairwise classification baseline. For Z3seq, the model correctly identified the top 20% of atoms in nearly 45% of cases, compared to random performance for the baseline.
Overhead: The computational overhead of feature extraction and model inference was minimal, accounting for only 23.6% of the total solving time, which is comparable to or lower than the overhead of the default lookahead heuristic.
Feature Importance: Analysis revealed that while specific feature rankings vary between solvers (indicating solver-specific optimization needs), critical features like "number of assignments," "lookahead score," and specific string operation counts remain consistently important.

Significance and Claims

The paper claims that Owl provides a significant advancement in parallel string constraint solving by automating the design of splitting heuristics. By shifting from manual, static heuristics to data-driven regression models, the approach effectively adapts to the specific characteristics of complex string constraints.

The authors emphasize that their method:

Outperforms existing manually crafted heuristics in both the number of solved instances and average solving time.
Mitigates the issues of error accumulation and information loss inherent in pairwise classification approaches.
Demonstrates that learned heuristics can be efficiently integrated into existing CDCL( $T$ )-based solvers (Z3seq and Z3str4) to unlock the potential of parallel architectures.

The work concludes that while the sequential solver's efficiency bounds the overall speedup, the learned heuristics effectively maximize parallelism by creating well-balanced subproblems, leading to substantial practical improvements in solving capacity.