uuugi/gclm-constrained-decoding

[Traditional Forward DFA (Outlines / SGLang)]
  Start (A) ─── Token X ───▶ [Valid Branch D] ─── Token Y ───▶ [Dead-End / Truncated Trap ❌]
  (Only checks if transition exists from current state)

[GCLM: Time-Bounded Backward Reachability (Ours)]
  Start (A) ─── Token X (Masked to -inf ⛔)
            └── Token B ───▶ State C ───▶ Goal / Closing '}' ✅
  (Preemptively prunes any branch that cannot reach Goal in <= T_rem steps)

# Base Step (t = 0):
R[0, s] = 1  if (s in S_goal)  else 0

# Vectorized Backward BFS (for t = 1 ... T_max):
R[t, s] = R[t-1, s]  OR  (∃ v ∈ V such that δ(s, v) >= 0 and R[t-1, δ(s, v)] == 1)

# Step 1: Vectorized check for valid transitions within remaining budget
ValidTokens(v) = (δ(s_curr, v) >= 0)  AND  R[min(T_rem - 1, T_max), clamp(δ(s_curr, v), 0)]

# Step 2: In-place O(1) logit masking
Logits[v] = Logits[v]  if ValidTokens(v) == 1  else -inf

gclm_project/
├── core/
│   ├── __init__.py
│   ├── fsm_builder.py          # Transitions tensor & vectorized backward BFS reachability table
│   ├── logit_processor.py      # Hugging Face LogitsProcessor compatible O(1) in-place masker
│   └── compiler.py             # Tokenizer-aware grammar/pattern compiler
├── benchmarks/
│   ├── synthetic_deadend.py    # Experiment 1: Dead-end trap avoidance benchmark
│   ├── json_budget_bench.py    # Experiment 2: Real-world strict budget JSON benchmark
│   ├── tool_calling_bench.py   # Experiment 3: Multi-step agent action budget benchmark
│   ├── scaling_bench.py        # Experiment 4: Complexity scaling (|S|=10~10,000) & plot generator
│   ├── real_model_bench.py     # Experiment 5: Real lightweight LLM (Qwen2.5) E2E benchmark
│   └── latency_bench.py        # Per-token runtime overhead benchmark
├── examples/
│   └── run_generation.py       # Live interactive generation demo with Transformers
├── tests/
│   ├── test_fsm_builder.py     # Unit tests for BFS reachability & multi-goal
│   └── test_logit_processor.py # Unit tests for batch masking & state progression
├── paper_figure_scaling.png    # Publication-ready 300-DPI scaling figure
├── requirements.txt
└── README.md

git clone https://huggingface.co/uuugi/gclm-constrained-decoding
cd gclm-constrained-decoding
pip install -r requirements.txt

git clone https://github.com/uuuugi/Goal-Conditioned-Reachability-Logit-Masker.git
cd Goal-Conditioned-Reachability-Logit-Masker
pip install -r requirements.txt

import torch
from transformers import AutoModelForCausalLM, AutoTokenizer, LogitsProcessorList
from core.fsm_builder import ReachabilityFSM
from core.logit_processor import GoalReachabilityLogitsProcessor

# 1. Load model and tokenizer
model_id = "Qwen/Qwen2.5-0.5B"
tokenizer = AutoTokenizer.from_pretrained(model_id)
model = AutoModelForCausalLM.from_pretrained(model_id)

vocab_size = model.config.vocab_size
max_budget = 15

# 2. Define FSM & Goal state
fsm = ReachabilityFSM(num_states=5, vocab_size=vocab_size)
fsm.add_transition(from_state=0, token_id=101, to_state=1)
fsm.add_transition(from_state=1, token_id=102, to_state=2)
fsm.set_goal_states([2])

# 3. Precompute reachability table (one-time offline step)
fsm.build_reachability(max_steps=max_budget)

# 4. Attach GCLM to Hugging Face LogitsProcessorList
gclm_processor = GoalReachabilityLogitsProcessor(fsm=fsm, max_budget=max_budget)
logits_processors = LogitsProcessorList([gclm_processor])

# 5. Generate with guaranteed reachability
inputs = tokenizer("Your prompt here", return_tensors="pt")
outputs = model.generate(
    **inputs,
    max_new_tokens=max_budget,
    logits_processor=logits_processors
)
print(tokenizer.decode(outputs[0]))

# Run Unit Tests
python -m pytest tests/ -v

# Run Experiment 1: Synthetic Dead-End Benchmark
python -m benchmarks.synthetic_deadend

# Run Experiment 2: Strict Budget JSON Benchmark
python -m benchmarks.json_budget_bench

# Run Experiment 3: Agent Tool-Calling Benchmark
python -m benchmarks.tool_calling_bench

# Run Experiment 4: Scaling Benchmark & Generate Paper Plots
python -m benchmarks.scaling_bench

# Run Experiment 5: Real Lightweight LLM Benchmark (Qwen2.5)
python -m benchmarks.real_model_bench --model Qwen/Qwen2.5-0.5B

@article{an2026gclm,
  title={Goal-Conditioned Reachability Logit Masker: Guaranteed Goal Satisfaction for Constrained LLM Generation in O(1) Time},
  author={An, ByeongUk},
  journal={arXiv preprint},
  year={2026}
}