---
kind: concept
slug: constrained-conditional-models
title: Constrained conditional models
summary: >-
  Structured prediction by training several simple local classifiers independently and combining their
  scores at inference time, under hard constraints on the output (e.g. a positive answer, an integer
  answer) enforced by a beam search. Needs little jointly annotated data; the trade-offs are a heuristic
  search and a constraint check that can silently fall back to an infeasible-looking output.
tags: [structured-prediction, constrained-inference, beam-search, math-word-problems]
papers: ["1608.01413"]
related: []
status: draft
updated_at: 2026-10-18
---

## Overview

Some outputs are structures made of parts that depend on each other, such as
an expression tree built from numbers in a text. Training one model for the
whole structure needs jointly annotated data, which is expensive. Constrained
conditional models (CCMs) take a different route: several simple components
are learned independently, and the structure is chosen at inference time by
combining their scores while respecting constraints on the output. The paper
under this page uses the "L+I" scheme of CCMs, which learns independent local
components and combines them at inference [arxiv:1608.01413 §2]. The authors
cite the general CCM framework to Chang et al. (2012); no card exists for
that paper, so this page draws only on the 1608.01413 card.

The invariant the variants share is that the final output must satisfy the
constraints, and that the local scores are summed over the parts of that
output. The paper's objective is a weighted sum of relevance scores for
unused quantities and pairwise scores for used quantities, maximised over
the expressions that pass the constraints [arxiv:1608.01413 §4.1] [eq. 3].

## Variants

### Independent local classifiers with a beam search (1608.01413)

Two classifiers are trained separately on gold annotations: a binary SVM
that scores whether each quantity is needed, and a multiclass SVM that scores
the operation at the lowest common ancestor of each quantity pair
[arxiv:1608.01413 §4.3] [arxiv:1608.01413 §4.4]. Inference is a bottom-up
beam search with beam size k = 200 that keeps the top candidates at each
step and returns the best tree passing the constraints [arxiv:1608.01413
§4.1]. Card: [Solving General Arithmetic Word Problems](/papers/1608.01413).

The paper's constraints are a positive answer and, for "how many" questions,
an integral answer [arxiv:1608.01413 §4.1]. The paper reports accuracy for
each constraint on its own and for both together, on three datasets:

| Setting | AI2 | IL | Commoncore | Source |
|---|---|---|---|---|
| No constraint | 77.7 | 71.9 | 29.6 | [tab. 6] |
| Positive constraint only | 78.0 | 72.5 | 36.5 | [tab. 6] |
| Integral constraint only | 71.8 | 73.4 | 39.0 | [tab. 6] |
| Both constraints | 72.0 | 73.9 | 45.2 | [tab. 6] |

These are the authors' numbers, on their own dataset versions [arxiv:1608.01413
§5.1]. The table shows that the effect of a constraint depends on the dataset.

## When to use which

The only variant in the wiki so far is the one above, so the choice here is
about whether the CCM pattern fits your problem. The constraints that the
paper actually used are the ones you can check directly on a candidate output.
Use this pattern when:

| Situation | Use | Why |
|---|---|---|
| Few jointly annotated structures, but per-part labels exist | Independent local classifiers combined at inference | The paper trains each component on its own gold labels and uses no joint training [arxiv:1608.01413 §4] |
| Output must obey simple, checkable rules (sign, integrality) | Hard constraints checked during search | Constraints lifted the full system above the no-constraint baseline on IL and Commoncore [tab. 6] |
| Candidate space is small enough for a beam | Beam search with a fixed k | The paper uses k = 200 over expression trees [arxiv:1608.01413 §4.1] |
| Constraints are not known to help on your data | Measure each constraint separately | On AI2 the integral constraint lowered accuracy from 77.7 to 71.8, and the full system scored 72.0 [tab. 6] |
| Parts strongly depend on each other | Not covered by this card | The paper's score sums local terms over parts; it reports no test of strong dependence between them [arxiv:1608.01413 §4.1] |

Do not expect the pattern to remove the need for good features. The paper's
error analysis attributes most errors to the quantity-schema extraction
step, which feeds the classifiers [arxiv:1608.01413 §5.5].

## Implementation sketch

Language-agnostic pseudocode of the common core. The paper's variant uses
SVMs and an expression tree; the other parts are generic.

```pseudocode
# Train each local component on its own gold labels  [arxiv:1608.01413 §4]
relevance_model = train_binary(quantities, gold_relevance)
pair_model = train_multiclass(quantity_pairs, gold_lca_label)

# At inference, score every part of a candidate structure  [arxiv:1608.01413 §4.1]
def score(candidate):
    # Sum local scores over the parts of the candidate  [eq. 3]
    return (w_rel * sum(relevance_model.score(q) for q in unused(candidate))
            + sum(pair_model.score(p) for p in pairs(candidate)))

# Hard constraints, checked on the candidate  [arxiv:1608.01413 §4.1]
def feasible(candidate):
    # Positive answer
    if candidate.value < 0:
        return False
    # Integral answer, only when the question asks "how many"
    if is_how_many(question) and not is_integer(candidate.value):
        return False
    return True

# Beam search over partial structures, keeping the top k  [arxiv:1608.01413 §4.1]
beam = [empty_structure()]
while not all(s.is_complete() for s in beam):
    expanded = [t for s in beam for t in s.extensions()]
    beam = top_k(expanded, k=200, key=score)

# Return the best feasible structure; if none is feasible, the paper
# falls back to the top of the beam  [arxiv:1608.01413 §4.1]
feasible_ones = [s for s in beam if feasible(s)]
best = max(feasible_ones, key=score) if feasible_ones else beam[0]
```

Where variants differ: the scoring of partial structures inside the beam is
not stated in the paper, so the `top_k` key above is a choice you must make
[arxiv:1608.01413 §4.1].

## Contradictions

None known across the cards: only one card currently cites this concept.
Within the single paper, the constraints do not help on every dataset: on AI2
the no-constraint baseline (77.7) is above the full system (72.0), while on IL
and Commoncore the full system is the best result [tab. 6]. The authors
report the AI2 gain for the positive constraint alone (78.0) as the best AI2
number, not the full system [arxiv:1608.01413 §5.4].

## Papers

- [Solving General Arithmetic Word Problems](/papers/1608.01413): applies the L+I scheme with a relevance classifier, a pairwise operation classifier and a constrained beam search to multi-step arithmetic word problems.