Restricting Expressiveness to Solve the Utility Problem

21 concepts10 papers1 proposal

In machine learning, we intuitively expect that as a system acquires more knowledge, it should become faster and more capable. However, in symbolic AI and Explanation-Based Learning (EBL), early researchers encountered a frustrating paradox known as the utility problem: learning new rules can actually cause a system to slow down.

When an intelligent system learns by generalizing from its experiences, it faces a fundamental tension between how broadly applicable a rule is (its generality) and how cheap it is to execute (its efficiency). Understanding why this trade-off occurs—and how to bypass it by deliberately restricting what a system is allowed to express—reveals a deep truth about the computational cost of abstraction.

The Intuition: Why Generality is Expensive

To understand why learning can degrade performance, consider how a rule-based system applies its knowledge. When a system learns a highly specific rule, it acts like a direct database lookup. For example, a robotic assembly system might learn a rule for a precise sequence of joint movements to pick up a specific 2-inch red bolt. As Alberto Maria Segre demonstrates in On the Operationality/Generality Trade-off in Explanation-based Learning, such "operational" knowledge is incredibly fast to execute, but it is brittle; if the environment changes even slightly (e.g., the bolt is blue or 3 inches long), the rule fails to apply.

To solve this brittleness, EBL systems generalize explanations into abstract rules. Instead of a rule for a "2-inch red bolt," the system creates a rule for "any cylindrical fastener $X$."

While this broadens applicability, it introduces a massive computational tax. When the system executes, its matching engine must search through all known objects in its environment to find valid bindings for the variable $X$. If a rule contains multiple variables ($X$, $Y$, and $Z$) and specifies complex relationships between them, the matching engine must perform an unconstrained combinatorial search—essentially solving a subgraph isomorphism problem—just to see if the rule is relevant. As noted in A Transformational Analysis of the EBL Utility Problem, this drive for generality inadvertently introduces matching overhead that can easily exceed the cost of re-solving the problem from scratch.

The Matching Bottleneck and "Expensive Chunks"

This bottleneck was famously analyzed within the Soar cognitive architecture. In Soar, the system learns by creating "chunks"—compiled rules that skip over intermediate problem-solving steps.

However, as Milind Tambe et al. observed in Eliminating Expensive Chunks by Restricting Expressiveness, highly general chunks often become "expensive chunks." Because these rules attempt to cover too many potential scenarios or solution paths simultaneously, the system spends an exponential amount of time in its matching phase.

Highly General Rule:
  If Path(X, Y) and Connected(Y, Z) and AvoidsObstacle(Z) ...
  -> Matcher must evaluate all combinations of X, Y, and Z (Combinatorial Explosion)

Restricted Rule (Unique-Attributes):
  If CurrentLocation(X) and NextStep(Y) ...
  -> Matcher evaluates a single deterministic path (Linear Time)

The core insight of this line of research is that the utility problem is not a flaw in the learning algorithm itself, but rather a consequence of the expressiveness of the representational language. If the language allows rules to express arbitrary, multi-variable relationships, the matcher will inevitably suffer from combinatorial explosion.

The Solution: Restricting Expressiveness

If unrestricted expressiveness causes system slowdowns, the most direct remedy is to deliberately cripple the representational language. In The Problem of Expensive Chunks and its Solution by Restricting Expressiveness, Milind Tambe et al. proposed a structural solution: restricting the language to "unique-attributes."

By ensuring that an attribute can only have a single value at a time, the authors effectively removed the possibility of cross-product combinations during the matching phase. This structural constraint shifts the burden of search out of the automatic, low-level matching engine and up into the explicit problem-solving layer.

The consequences of this trade-off are symmetrical:

  1. Loss of Generality: The system can no longer learn a single, sweeping rule that solves an entire class of problems. It requires more training examples and must store a much larger volume of individual, specialized rules to achieve the same functional competence.
  2. Gain in Efficiency: Because each individual rule is structurally simple, the time required to check and execute a rule is strictly bounded. The system maintains a stable, real-time decision cycle even as its knowledge base grows.

Alternative Frontiers in the Generality-Efficiency Balance

Restricting expressiveness is a powerful hammer, but it is not the only way to navigate this trade-off. Other researchers have looked for ways to preserve expressiveness while mitigating search costs through different architectural mechanisms.

Search Control Bounding

Rather than limiting what a rule can say, why not limit when it can be learned? In Constraining Learning with Search Control, Jihie Kim et al. argued that unique-attribute restrictions make task encoding overly difficult for humans. Instead, they proposed incorporating search control knowledge directly into the learned rules. By adding specific conditions that mirror the original problem-solving path, they bounded the execution cost of the rule by the cost of the original search, though this similarly results in a localized reduction of rule generality.

Tuning the Level of Generalization

Instead of generalizing a rule as much as possible, a system can look for a middle ground. Masayuki Yamamura et al. suggested in An Augmented EBL and its Application to the Utility Problem that finding the "most specific common generalization" across multiple examples serves as an optimal balance point. This prevents the rule from becoming so abstract that it triggers excessive backtracking, while remaining general enough to be useful across recurring scenarios.

Hierarchies and Compiled Knowledge

The tension also manifests in how knowledge is structured. The authors of Generality and Computational proposed a hierarchical approach where general operators are applied first, followed by specialized ones, allowing the broad applicability of sub-templates to compensate for composition costs. Conversely, as explored in the context of the IMEX: Overcoming Intractability in Explanation Based Learning framework, relying heavily on pre-existing, high-level "compiled" knowledge makes finding explanations tractable but frequently forces the system into overly specific concept definitions.

Even in modern symbolic-statistical frameworks like PRISM, designed by Taisuke Sato et al. in PRISM: A Language for Symbolic-Statistical Modeling, the inherent generality of top-down exhaustive search algorithms often yields lower computational efficiency than highly specialized, model-specific alternatives.

Conclusion

The utility problem teaches us that knowledge acquisition is never free. A system that insists on maximum generality must pay a continuous tax in pattern-matching search costs. By understanding this trade-off, AI architects can intentionally design representational constraints—trading away elegant, universal abstractions in favor of a larger library of narrow, predictable, and computationally cheap rules.

Key Foundational Work

Generality and Computational Cost (1977) — contributed 2 concept elements to this direction.
On the Operationality/Generality Trade-off in Explanation-based Learning (1987) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_generality_efficiency_tradeoff_generalit_d54f2d81,
  title = {generality-efficiency tradeoff (generality vs. efficiency trade-off)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generality-efficiency-tradeoff-generality-vs-efficiency-trade-off/rdr_d54f2d815fc64756a792bb4eedf54f7d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_generality_efficiency_tradeoff_generalit_d54f2d81_v1,
  title = {generality-efficiency tradeoff (generality vs. efficiency trade-off)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generality-efficiency-tradeoff-generality-vs-efficiency-trade-off/rdr_d54f2d815fc64756a792bb4eedf54f7d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake