How do you get reliable structured JSON output from an LLM?

// Constrained decoding on a toy model: prompt-only vs JSON mode vs schema mode.
// The "model" is a bigram table P(next token | previous token). Real engines
// compile the schema into an automaton; this language is small enough to list.
const MODEL = {
  "<s>": [["Sure! ", 0.55], ["{", 0.45]],
  "Sure! ": [["{", 1.0]],
  "{": [['"sentiment": ', 0.9], ['"score": ', 0.1]],
  '"sentiment": ': [['"Positive"', 0.5], ['"positive"', 0.4], ['"mixed"', 0.1]],
  '"Positive"': [[", ", 1.0]],
  '"positive"': [[", ", 1.0]],
  '"mixed"': [[", ", 1.0]],
  ", ": [['"score": ', 1.0]],
  '"score": ': [["4.5", 0.5], ["4", 0.45], ['"five"', 0.05]],
  "4.5": [[",", 0.55], ["}", 0.45]],
  "4": [[",", 0.55], ["}", 0.45]],
  '"five"': [["}", 1.0]],
  ",": [["}", 1.0]],
  "}": [[" Hope this helps!", 0.55], ["<eos>", 0.45]],
  " Hope this helps!": [["<eos>", 1.0]],
};
const ENUM = ["positive", "negative", "neutral"];

function parse(text) {
  try { return { ok: true, value: JSON.parse(text) }; } catch { return { ok: false }; }
}
function schemaErrors(v) {
  if (typeof v !== "object" || v === null || Array.isArray(v)) return ["root is not an object"];
  const e = [];
  for (const k of ["sentiment", "score"]) if (!(k in v)) e.push(`missing "${k}"`);
  if ("sentiment" in v && !ENUM.includes(v.sentiment)) e.push(`sentiment ${JSON.stringify(v.sentiment)} not in enum`);
  if ("score" in v && !(Number.isInteger(v.score) && v.score >= 1 && v.score <= 5))
    e.push(`score ${JSON.stringify(v.score)} is not an integer 1-5`);
  return e;
}
const textOf = (path) => path.join("");
const isJson = (path) => { const r = parse(textOf(path)); return r.ok && typeof r.value === "object" && r.value !== null && !Array.isArray(r.value); };
const isSchema = (path) => isJson(path) && schemaErrors(parse(textOf(path)).value).length === 0;

// Every complete output the model can produce (the whole "language").
function allPaths(last = "<s>", acc = []) {
  if (last === "<eos>") return [acc];
  return MODEL[last].flatMap(([t]) => allPaths(t, t === "<eos>" ? acc : [...acc, t]));
}
const PATHS = allPaths();
const MODES = { "prompt only": () => true, "JSON mode": isJson, "JSON Schema (strict)": isSchema };

// The mask: token t is allowed after prefix if some valid output starts with prefix + t.
function allowed(prefix, valid, t) {
  const want = t === "<eos>" ? prefix : [...prefix, t];
  return PATHS.some((p) => valid(p) && (t === "<eos>" ? p.length === want.length : p.length >= want.length) &&
    want.every((x, i) => p[i] === x));
}
function decode(valid) {
  const out = [], notes = [];
  let last = "<s>";
  while (last !== "<eos>") {
    const cands = MODEL[last];
    const ok = cands.filter(([t]) => allowed(out, valid, t));
    const total = ok.reduce((s, [, p]) => s + p, 0);
    const [pick, p] = ok.reduce((a, b) => (b[1] > a[1] ? b : a));
    if (ok.length < cands.length) {
      const masked = cands.filter((c) => !ok.includes(c)).map(([t, q]) => `[${t}] (${q.toFixed(2)})`);
      notes.push(`masked ${masked.join(", ")} -> picked [${pick}] (${(p / total).toFixed(3)} after renormalising)`);
    }
    if (pick !== "<eos>") out.push(pick);
    last = pick;
  }
  return { out, notes };
}
// Probability that SAMPLING (not greedy) in a mode yields a schema-valid object.
function sampleProb(valid, goal) {
  let sum = 0;
  for (const p of PATHS.filter(valid)) {
    if (!goal(p)) continue;
    let prob = 1, last = "<s>", prefix = [];
    for (const t of [...p, "<eos>"]) {
      const ok = MODEL[last].filter(([x]) => allowed(prefix, valid, x));
      prob *= ok.find(([x]) => x === t)[1] / ok.reduce((s, [, q]) => s + q, 0);
      if (t !== "<eos>") prefix = [...prefix, t];
      last = t;
    }
    sum += prob;
  }
  return sum;
}

console.log(`possible outputs: ${PATHS.length} | parse as a JSON object: ${PATHS.filter(isJson).length} | match the schema: ${PATHS.filter(isSchema).length}`);
for (const [name, valid] of Object.entries(MODES)) {
  const { out, notes } = decode(valid);
  const text = textOf(out), r = parse(text);
  console.log(`\n== ${name} (greedy, temperature 0)`);
  for (const n of notes) console.log(`  ${n}`);
  console.log(`  output : ${text}`);
  console.log(`  parse  : ${r.ok ? "ok" : "FAILS"}`);
  if (r.ok) { const e = schemaErrors(r.value); console.log(`  schema : ${e.length ? e.join("; ") : "ok"}`); }
}
console.log("\n== sampling instead of greedy: P(output matches schema)");
for (const [name, valid] of Object.entries(MODES)) {
  const p = sampleProb(valid, isSchema);
  console.log(`  ${name.padEnd(21)} ${p.toFixed(4)}  expected attempts with retry-until-valid: ${p > 0 ? (1 / p).toFixed(1) : "never"}`);
}