Constrained Decoding with Arbitrary Constraints is NP-hard

Constrained decoding is getting more and more attention in the field of large language models (LLMs). It aims to generate sequences of tokens that satisfy certain constraints.

A typical example is to force the generation from LLM to satisfy a given JSON schema so that the generated JSON data can be used directly in a downstream application, such as tool use.

One natural question is: How hard is it to generate sequences of tokens that satisfy some constraints? Of course it will depend on the complexity of the constraints, but do we have a general answer?

In this post, we will show that constrained decoding with arbitrary constraints is NP-Hard by reducing the 3-SAT problem to the constrained decoding problem.

This result lets us know that it is intractable to apply constrained decoding to arbitrary constraints in general.

But luckily, we can still apply constrained decoding to many practical constraints that we encounter in real-world applications, such as context-free grammars, regular expressions, and JSON schemas.

Background

Sequence Generation with Constraints is a common problem in NLP. Given a language model $M$, a set of constraints $C$, and a desired sequence length $n$, the goal is to generate a sequence $x_1, x_2, \ldots, x_n$ such that each $x_i$ belongs to the language defined by the model and the entire sequence satisfies all the constraints in $C$. These constraints can range from simple grammatical rules to complex conditions based on the content and context.

On the other hand, the 3-SAT Problem is a well-known NP-complete problem in computational complexity theory. The 3-SAT problem involves determining whether there exists a truth assignment to a set of boolean variables that satisfies a given boolean formula in conjunctive normal form (CNF), where each clause has exactly three literals.

An instance of the 3-SAT problem is typically represented as a set of clauses, such as $(v_1 \lor \neg v_2 \lor v_3)$, where each variable $v_i$ can be either true or false. The goal is to find a truth assignment that satisfies all the clauses in the formula.

For example, here is a 3-SAT formula:

$$ (v_1 \lor \neg v_2 \lor v_3) \land (\neg v_1 \lor v_2 \lor v_3) \land (v_1 \lor v_2 \lor \neg v_3) $$

The Goal: Reduction to 3-SAT

To demonstrate that sequence generation under arbitrary constraints is NP-hard, we’ll reduce an instance of the 3-SAT problem to a sequence generation problem. If we can do this, it will prove that solving the sequence generation problem is at least as hard as solving 3-SAT, thereby establishing its NP-hardness.

Step 1: Mapping 3-SAT to Sequence Generation

Let’s start by considering a 3-SAT instance with variables $v_1, v_2, \ldots, v_k$. Each of these variables can be mapped to a specific position in the sequence that we wish to generate. The values of these variables (True or False) will be represented by the symbols generated by the language model, for example, 0 and 1. This requires that 0 and 1 are part of the language model’s vocabulary, which can be taken as granted.

Step 2: Converting Clauses to Constraints

Each clause in the 3-SAT formula, such as $(v_1 \lor \neg v_2 \lor v_3)$, can be translated into a constraint on the sequence of tokens. The constraint will dictate that the tokens in the sequence corresponding to $v_1$, $v_2$, and $v_3$ must satisfy the boolean condition of the clause. For instance, if $v_1$ is represented by a 1, $v_2$ by a 0, and $v_3$ by a 1, the clause $(v_1 \lor \neg v_2 \lor v_3)$ is satisfied, which means the sequence generated by the language model adheres to the constraint derived from this clause.

Step 3: Sequence Representation

The language model now needs to generate a sequence that represents a valid truth assignment for the 3-SAT formula. Each token in the sequence corresponds to a variable in the 3-SAT problem, and the generated symbol at each position indicates the truth value of that variable. The challenge lies in ensuring that the entire sequence satisfies all the constraints simultaneously, which corresponds to satisfying all the clauses in the 3-SAT formula.

Step 4: Demonstrating NP-Hardness

Here’s the key insight: If we can solve the sequence generation problem under these constraints efficiently, we can also solve the 3-SAT problem efficiently. This is because the sequence generation problem is effectively a search for a satisfying assignment for the 3-SAT formula. Since 3-SAT is NP-complete, solving it efficiently implies solving all problems in NP efficiently, making the sequence generation problem under arbitrary constraints NP-hard.

Conclusion

By reducing the 3-SAT problem to the sequence generation problem under arbitrary constraints, we have demonstrated that the latter is NP-hard. This reduction shows that the constrained decoding task is at least as hard as the hardest problems in NP, establishing its NP-hardness.

This result highlights the inherent complexity of generating sequences that satisfy arbitrary constraints and underscores the challenges involved in developing efficient algorithms for this task.

While constrained decoding is a powerful technique for enforcing specific conditions on generated sequences, it is essential to be aware of the computational complexity associated with this process, especially when dealing with general constraints.