# Grammar-Constrained Decoding in Needle: How It Enforces JSON Schemas

> Learn how Needle enforces JSON schemas using grammar-constrained decoding. Discover how finite-state automata and token pruning guarantee valid structured outputs.

- Repository: [Cactus Compute, Inc./needle](https://github.com/cactus-compute/needle)
- Tags: deep-dive
- Published: 2026-08-18

---

**Needle enforces JSON schemas by converting them into finite-state automata and pruning invalid tokens during generation, guaranteeing that structured outputs adhere to predefined grammatical rules.**

Cactus-compute's Needle implements grammar-constrained decoding to ensure that language model outputs—particularly tool arguments—adhere strictly to JSON schemas. By enforcing structural constraints at the token level rather than relying on post-hoc validation, Needle eliminates malformed JSON and guarantees parsable structured data.

## How Grammar-Constrained Decoding Works

### Schema-to-FSA Conversion

At the core of Needle's approach is the transformation of JSON schemas into **finite-state automata (FSA)**. According to the Needle source code, the implementation in [`needle/model/decode.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/decode.py) converts any provided JSON schema into an FSA that encodes every valid token sequence. This automaton represents all possible valid JSON structures that satisfy the schema constraints, creating a mathematical model of permissible outputs.

### Token-Level Constraint Enforcement

During text generation, the decoder consults the FSA to perform **token-level pruning** of the probability distribution. Only tokens that keep the current partial output on a valid path within the automaton remain in the candidate set. Tokens that would violate the schema constraints are immediately removed from consideration, forcing the model to select from grammatically valid continuations.

### Real-Time Validation and State Tracking

As each token is produced, the decoder updates the FSA state to reflect the new partial output. If the model attempts to output an illegal token, the decoder discards it and re-samples from the remaining allowed tokens. This real-time validation guarantees that the final generated string is guaranteed to be parsable according to the original schema.

## Implementation in the Needle Codebase

The grammar-constrained decoding system spans several key files in the cactus-compute/needle repository:

- **[`needle/model/decode.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/decode.py)** – Implements the conversion from JSON schema to FSA and the token-level pruning mechanism that enforces grammar constraints during decoding.
- **[`needle/cli.py`](https://github.com/cactus-compute/needle/blob/main/needle/cli.py)** – Exposes the `--no-grammar` CLI option, allowing users to bypass grammar constraints when free-form generation is required.
- **[`needle/model/__init__.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/__init__.py)** – Provides the public `Needle` class that forwards the `schema` argument to the underlying decoder.
- **[`needle/agent/tools.py`](https://github.com/cactus-compute/needle/blob/main/needle/agent/tools.py)** – Defines built-in tool descriptors including their JSON schemas, which are automatically fed to the decoder during tool invocation.

## Practical Usage Examples

### Enforcing Schemas with Grammar Constraints

To ensure outputs conform to a specific structure, pass a JSON schema to the `Needle.run()` method:

```python
from needle import Needle

# Define a JSON schema for a search tool

search_schema = {
    "type": "object",
    "properties": {
        "query": {"type": "string"},
        "max_results": {"type": "integer", "minimum": 1, "maximum": 10},
    },
    "required": ["query"],
    "additionalProperties": False,
}

needle = Needle(model="meta-llama/Meta-Llama-3-8B-Instruct")
result = needle.run(
    "Search for recent papers about AI safety.",
    schema=search_schema,  # Enables grammar-constrained decoding

)
print(result)  # Valid JSON adhering to search_schema

```

### Disabling Grammar Constraints

For applications requiring creative or unstructured text, disable constraints using the `grammar` parameter or the `--no-grammar` CLI flag:

```python
needle = Needle(model="meta-llama/Meta-Llama-3-8B-Instruct")
result = needle.run(
    "Write a short story about a robot learning emotions.",
    grammar=False,  # Equivalent to --no-grammar

)

```

### Direct Decoder Access

Advanced users can interact with the `GrammarDecoder` class directly:

```python
from needle.model.decode import GrammarDecoder

decoder = GrammarDecoder(
    model="meta-llama/Meta-Llama-3-8B-Instruct",
    schema=search_schema,
)

tokens = decoder.decode("Search for ...")

# tokens contains only sequences satisfying search_schema

```

## Summary

- **Grammar-constrained decoding** converts JSON schemas into finite-state automata to validate token sequences during generation.
- **Token-level pruning** in [`needle/model/decode.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/decode.py) removes invalid tokens from the probability distribution, ensuring only schema-compliant outputs are produced.
- **Real-time FSA state tracking** guarantees that partial outputs remain valid throughout the generation process.
- The **`--no-grammar`** flag in [`needle/cli.py`](https://github.com/cactus-compute/needle/blob/main/needle/cli.py) and the `grammar=False` parameter provide optional bypass mechanisms for unrestricted generation.
- Tool schemas defined in [`needle/agent/tools.py`](https://github.com/cactus-compute/needle/blob/main/needle/agent/tools.py) are automatically enforced when the agent invokes functions.

## Frequently Asked Questions

### How does Needle convert JSON schemas into enforceable constraints?

Needle converts JSON schemas into **finite-state automata (FSA)** in [`needle/model/decode.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/decode.py). The FSA encodes every valid token sequence allowed by the schema, creating a state machine that tracks whether the current generation path remains grammatically valid.

### Can I disable grammar-constrained decoding for specific generations?

Yes. You can disable constraints by passing `grammar=False` to the `Needle.run()` method, or by using the **`--no-grammar`** command-line flag defined in [`needle/cli.py`](https://github.com/cactus-compute/needle/blob/main/needle/cli.py). This allows the model to generate free-form text without schema validation.

### What happens when a token violates the schema during generation?

When a token would violate the schema, the decoder immediately **discards** it and re-samples from the remaining allowed tokens. The FSA state is updated in real-time, ensuring that invalid tokens are removed from the candidate set before being emitted.

### Which components handle the core grammar constraint logic?

The primary implementation resides in **[`needle/model/decode.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/decode.py)**, which handles the FSA conversion and token pruning. The public API surface in [`needle/model/__init__.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/__init__.py) forwards schema definitions to this module, while [`needle/agent/tools.py`](https://github.com/cactus-compute/needle/blob/main/needle/agent/tools.py) supplies schemas for built-in tool interactions.