Skip to content
STIMSMITH

Assumption-based Pruning

Concept WIKI v1 · 5/26/2026

Assumption-based pruning is a pruning scheme used for conditional constraint satisfaction problems (CSPs). In IBM's constraint-based random stimuli generation work for hardware verification, it was incorporated into an extension of the MAC algorithm to improve pruning when parts of a CSP become relevant or irrelevant depending on variable assignments.

Overview

Assumption-based pruning is a pruning scheme associated with conditional constraint satisfaction problems (CSPs). In the cited IBM hardware-verification application, many CSP instances were described as conditional: depending on the value assigned to some variables, extensive parts of the CSP may become irrelevant. The authors state that they extended the MAC algorithm and incorporated assumption-based pruning to solve such conditional problems efficiently. [C1]

Role in conditional CSPs

The evidence describes conditional problems as cases where variable assignments can determine whether large portions of a CSP are relevant. It also notes that conditional problems occur in applications such as manufacturing configuration, while the IBM hardware-verification setting included cases where a full problem could consist of several weakly coupled CSPs and the number of such CSPs could itself be a CSP variable. [C2]

Within this setting, assumption-based pruning is reported to strengthen pruning under conditionality by simultaneously considering the state of all "universes," where each universe contains only a particular subset of the conditional sub-problems. [C3]

Algorithmic context

The reported implementation context was an extension of the MAC algorithm. The evidence does not provide implementation details of the assumption mechanism itself, but it explicitly states that the MAC algorithm was extended and assumption-based pruning was incorporated for efficient handling of conditional problems. [C1]

Application context

The concept appears in a paper on constraint-based random stimuli generation for hardware verification. The same source describes IBM's random stimuli generation as a complex application relying on multiple AI techniques, including CSP and knowledge-representation techniques, to address growing hardware-system and business complexity. [C4]

In that application, the relevant tool context included Genesys PE, a stimuli generator for processor and multi-processor verification. The source reports that since 2000 Genesys PE had been used as the major functional verification tool for IBM PowerPC processor designs and deployed across unit, core, chip-level, and partially system-level verification. [C5]

Bibliographic reference

The evidence cites the dedicated publication: Geller, F., and Veksler, M. 2005. "Assumption-based pruning in conditional CSP." It appeared in CP, volume 3709 of Lecture Notes in Computer Science, pages 241–255, published by Springer. [C6]

LINKED ENTITIES

2 links
Conditional CSP used_in
Constraint Satisfaction Problem applies_to

CITATIONS

6 sources
6 citations
[1] Assumption-based pruning was incorporated into an extension of the MAC algorithm to solve conditional CSP problems efficiently. Constraint-Based Random Stimuli Generation for Hardware Verification
[2] Conditional problems are described as CSPs where variable assignments can make extensive parts of the CSP irrelevant; examples include weakly coupled CSPs where the number of sub-CSPs is itself a CSP variable. Constraint-Based Random Stimuli Generation for Hardware Verification
[3] Assumption-based pruning greatly enhances pruning under conditionality by simultaneously considering the state of all universes, each containing only a subset of conditional sub-problems. Constraint-Based Random Stimuli Generation for Hardware Verification
[4] IBM's random stimuli generation for hardware verification is presented as a complex application relying on AI techniques, with ongoing exploration of CSP and knowledge-representation techniques. Constraint-Based Random Stimuli Generation for Hardware Verification
[5] Genesys PE is described as a stimuli generator for processor and multi-processor verification and as the major functional verification tool for IBM PowerPC processor designs since 2000. Constraint-Based Random Stimuli Generation for Hardware Verification
[6] The reference list cites Geller and Veksler's 2005 paper 'Assumption-based pruning in conditional CSP' in CP, LNCS volume 3709, pages 241–255, Springer. Constraint-Based Random Stimuli Generation for Hardware Verification