Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems

Woosang Jeon; Jaeyeon Kim; Sham Kakade; Yilun Du; Amrit Singh Bedi; Arun Kumar Chithanar; Chul Lee; Taehyeong Kim

cs.LGSep 30, 2026

Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems

Authors: Woosang Jeon, Jaeyeon Kim, Sham Kakade, Yilun Du, Amrit Singh Bedi, Arun Kumar Chithanar, Chul Lee, Taehyeong Kim, +1 more

Organizations: Seoul National University · Harvard University · University of Central Florida

Abstract

Next-token prediction has driven remarkable progress in large language models, yet a growing body of evidence suggests that they can struggle on problems governed by complex global constraints. In this work, we focus on this regime and ask whether some of these limitations arise from the inference interface induced by next-token prediction itself. We study this question through blackboard intelligence: an inference-time perspective in which a model works on a fixed, revisable canvas and searches over candidate solution states rather than committing to a causal, left-to-right trajectory. We instantiate this idea with diffusion language models, whose any-order prediction interface naturally exposes predictions over partially filled solution states. Our key observation is that mean confidence, a simple model-internal quantity available from the standard masked diffusion objective, provides a useful proxy for global coherence and can guide inference-time search and revision. Empirically, across ZebraLogic, Nurse Rostering, and Job-Shop Scheduling, Blackboard consistently improves inference while holding the fine-tuned LLaDA-8B-Instruct checkpoint fixed and substantially outperforms same-scale autoregressive baselines, reaching 90.4% accuracy on ZebraLogic-Hard, 76.4% exact feasibility on Nurse Rostering, and 80.2% optimality on JSSP. Stronger autoregressive search and refinement also fail to close the gap on ZebraLogic-Hard, while Blackboard surpasses tested frontier LLMs there and on JSSP despite their substantially greater scale and strong test-time reasoning. We open-source our codebase at https://github.com/jwoosang1/blackboard-intelligence.

Figures & tables

Figure 1 : Across three globally constrained domains, blackboard inference consistently improves LLaDA-8B-Instruct over its standard inference (shaded) and outperforms same-scale autoregressive baselines; on ZebraLogic-Hard and JSSP, it also exceeds the tested frontier LLMs.

Figure 2 : Illustration of globally constrained tasks . ZebraLogic asks for a feasible assignment satisfying all clues; Nurse Rostering asks for a feasible staff–day shift assignment satisfying roster constraints; and JSSP asks for a feasible schedule with globally minimum makespan.

Figure 3 : Curse of complexity on ZebraLogic . Frontier LLM accuracy degrades sharply with difficulty; LLaDA-8B blackboard remains high.

Figure 4 : Mean confidence trajectories on ZebraLogic. ( Left ) Aggregated over all evaluation instances, solved puzzles exhibit consistently higher mean confidence

\mathcal{C}_{\theta}

than failed ones. ( Right ) Per-puzzle trajectories: mean confidence rises smoothly toward

1.0

for correctly solved puzzles ( green ), whereas it remains unstable for incorrect ones ( red ).

Figure 5 : Mean confidence trajectories on JSSP. ( Left ) Across evaluation instances, inference trajectories that yield optimal solutions exhibit higher mean confidence than those that induce suboptimal solutions . ( Right ) Optimal-solution rate increases monotonically across quintiles of trajectory-averaged mean confidence.

Figure 6 : Accuracy–latency on ZebraLogic. Blackboard improves the same LLaDA-8B checkpoint, while autoregressive search and refinement show limited accuracy scaling.

Inference	NFE	Acc. (%)
Greedy	35	78.4
PRISM	54	79.2
LoPA	6.74	73.0
Blackboard (always-on)	280	86.8
Blackboard	129	90.4

Table 1 : dLLM inference on ZebraLogic.

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

	ZL official		ZL-Hard
Category	log_ss	Z3	log_ss	Z3
Small	1.26	0.3	2.37	6.0
Medium	3.58	8.0	4.35	19.8
Large	6.83	27.1	7.45	50.2
X-Large	12.38	83.6	12.60	161.4
Overall	5.92	28.9	6.69	59.4

Appendix

Table 2 : ZebraLogic-Hard vs. the official ZebraLogic benchmark. Search-space sizes are comparable across tiers, while Z3 conflict counts are higher in our variant. Z3 conflicts are averaged over

32

runs with different random seeds.

	ZebraLogic	Nurse Rostering	JSSP
Base models (LLM / dLLM)	LLaMA-3.1-8B-Instruct / LLaDA-8B-Instruct
LoRA
Rank $r$ / $\alpha$ / dropout	$256$ / $256$ / $0.05$
Targets	q/k/v/o_proj
Optimization
Optimizer (weight decay $0.01$ )	AdamW

Appendix

Table 3 : SFT hyperparameters. LLM and dLLM configurations are matched within each task except for architecture-required masking and decoding mechanics.

Task	Metric	LLaDA-8B-Instruct	LLaMA-3.1-8B-Instruct
ZebraLogic-Hard ( $n=500$ )	exact feasibility	$0.8$ ( $4/500$ )	$0.4$ ( $2/500$ )
Nurse Rostering ( $n=500$ )	exact feasibility	$0.0$ ( $0/500$ )	$0.0$ ( $0/500$ )
JSSP ( $n=400$ )	exact optimality	$0.0$ ( $0/400$ )	$0.0$ ( $0/400$ )

Appendix

Table 4 : Performance before task-specific fine-tuning. ZebraLogic-Hard and Nurse Rostering report exact feasibility; JSSP reports exact optimality.

Class	Model	Inference	NFE	S	M	L	XL	All
Frontier LLMs	GPT-5.4		—	60.8	27.2	9.6	0.0	24.4
	GPT-5.4 (CoT prompting)		—	66.4	50.4	21.6	3.2	35.4
	GPT-5.4 Thinking		—	76.8	84.8	72.8	58.4	73.2
	Gemini 2.5 Pro		—	88.8	74.4	46.4	8.0	54.4
8B-LLM	LLaMA-3.1-8B	Greedy	80	80.8	48.0	8.8	0.8	34.6
	LLaMA-3.1-8B	Beam search	643	81.6	48.0	8.8	0.8	34.8

Appendix

Table 5 : Evaluation results on ZebraLogic-Hard.

Fill %	Solved $\mathcal{C}_{\theta}$	Failed $\mathcal{C}_{\theta}$	$\Delta$	Cohen’s $d$
10%	$0.893\pm 0.136$	$0.682\pm 0.093$	$+0.211$	1.81
20%	$0.913\pm 0.122$	$0.734\pm 0.100$	$+0.180$	1.61
30%	$0.937\pm 0.103$	$0.773\pm 0.096$	$+0.164$	1.64
40%	$0.956\pm 0.086$	$0.804\pm 0.089$	$+0.152$	1.73
50%	$0.975\pm 0.063$	$0.835\pm 0.087$	$+0.140$	1.84
60%	$0.984\pm 0.048$	$0.851\pm 0.091$	$+0.133$	1.84

Appendix

Table 6 : Progressive separation of

\mathcal{C}_{\theta}

trajectories at

10\%

-fill intervals on ZebraLogic-Hard (

n_{\text{solved}}{=}392

n_{\text{failed}}{=}108

Grid cells	Solved $\mathcal{C}_{\theta}$	Failed $\mathcal{C}_{\theta}$	$\Delta$	$p$
8	0.997	0.880	$+0.118$	$0.003$
12	0.997	0.822	$+0.175$	$<0.001$
16	0.975	0.810	$+0.165$	$0.010$
20	0.942	0.860	$+0.082$	$<0.001$
24	0.896	0.808	$+0.087$	$<0.001$
30	0.872	0.806	$+0.066$	$<0.001$

Appendix

Table 7 : Grid-size-controlled separation of mean trajectory

\mathcal{C}_{\theta}

on ZebraLogic-Hard. Separation is significant at every grid size.

Figure 7 : Constraint propagation is graph-localized on ZebraLogic-Hard: the correct–wrong response gap is largest at direct clue links and decays with distance.

Inference	S	M	L	XL	All
Greedy initial solution	80.8	48.0	8.8	0.8	34.6
Self-critique (up to 3 rounds)	68.0	33.6	3.2	0.0	26.2
Perfect-verifier refinement (up to 3 rounds)	82.4	51.2	11.2	1.6	36.6

Appendix

Table 9 : Autoregressive refinement results by ZebraLogic-Hard tier. All refinement methods start from the same deterministic LLaMA-3.1-8B solution used in the main greedy baseline and are evaluated on the full

n=500

test set.

Inference	Time / inst.	Peak memory	FLOPs / inst.	Accuracy (%)
Greedy	2.40 s	17.1 GB	8.2 T	34.6
Beam search ( $B=8$ )	2.61 s	18.0 GB	17.2 T	34.8
Beam search ( $B=64$ )	5.59 s	25.7 GB	85.1 T	35.0
Self-critique	19.14 s	17.1 GB	59.8 T	26.2
Perfect-verifier refinement	6.03 s	17.1 GB	20.5 T	36.6

Appendix

Table 10 : Hardware-matched autoregressive inference-time diagnostic on ZebraLogic-Hard. All methods use the same fine-tuned LLaMA-3.1-8B checkpoint and are measured on an NVIDIA RTX PRO 6000 GPU.

Setting	NFE	Accuracy
Greedy	35	78.4%
Blackboard Search (w/o trigger)	866	84.6%
Blackboard (w/o trigger)	280	86.8%
Blackboard Search	273	90.2%
Blackboard	129	90.4%

Appendix

Table 11 : Trigger and intervention ablation on ZebraLogic-Hard. The bottom two rows use the validation-selected trigger

(\rho,\tau)=(0.8,1.0)

Depth $d$	S	M	L	XL	All
$d{=}3$	100.0	99.2	87.2	75.2	90.4
$d{=}4$	100.0	97.6	84.0	76.8	89.6
$d{=}5$	100.0	97.6	84.8	75.2	89.4

Appendix

Table 12 : Lookahead-depth ablation for Blackboard on ZebraLogic-Hard. Each cell reports solve rate (%).

Model	NFE	S	M	L	XL	All
LLaDA-8B (greedy)	32	96.6	89.6	74.5	50.0	80.9
LLaDA-8B (Blackboard, w/o trigger)	223	96.6	93.6	78.0	48.5	82.4
LLaDA-8B (Blackboard)	145	96.6	93.9	83.5	58.5	85.6

Appendix

Table 13 : Results on the adapted official ZebraLogic benchmark (

n=1000

, search-space bins Small/Medium/Large/X-Large following Lin et al. [2025] ). Blackboard uses

(\rho,\tau)=(2/3,1.0)

; non-triggered puzzles keep their greedy result.

Figure 9 : Mean confidence trajectories on Nurse Rostering. ( Left ) Aggregated over evaluation instances, solved rosters exhibit higher mean confidence than failed ones. ( Right ) Illustrative d1 trajectories: the solved trajectory converges toward high confidence, whereas the shown failed trajectory undergoes substantial late-stage variation.

Conflict band	d0	d1	d2	d3	All
Cohen’s $d$	2.48	2.18	2.03	1.82	2.16

Appendix

Table 14 : Separation between solved and failed Nurse Rostering trajectories, measured by Cohen’s

d

of trajectory-averaged mean confidence.

Class	Model	Inference	NFE	d0	d1	d2	d3	All
Frontier LLMs	GPT-5.4		—	52.0	8.0	3.2	0.0	15.8
	GPT-5.4 (CoT prompting)		—	91.2	67.2	31.2	14.4	51.0
	GPT-5.4 Thinking		—	92.0	90.4	84.0	77.6	86.0
	Gemini 2.5 Pro		—	73.6	41.6	14.4	8.0	34.4
8B-LLM	LLaMA-3.1-8B	Greedy	97	39.2	8.0	5.6	2.4	13.8
	LLaMA-3.1-8B	Beam search	773	42.4	8.0	6.4	2.4	14.8

Appendix

Table 15 : Evaluation results on Nurse Rostering. Instances are grouped by Z3-conflict difficulty bands (d0–d3); All is exact feasibility over the full evaluation set.

Method	Cascade applied	Mean NFE	Exact feasibility (%)
LLaDA-8B greedy	–	22	73.0
Cascade on every instance	100%	325	57.4
Confidence-triggered Blackboard	19.6%	120	76.4

Appendix

Table 16 : Effect of confidence-triggered steering on Nurse Rostering. The full cascade is evaluated on all

500

instances; Blackboard applies it only to triggered instances and otherwise retains the greedy roster.

Class	Model	Inference	NFE	% opt	% within 5%
Frontier LLMs	GPT-5.4		—	11.0	16.5
	GPT-5.4 (CoT prompting)		—	30.0	37.2
	GPT-5.4 Thinking		—	77.0	90.2
	Gemini 2.5 Pro		—	27.8	35.0
8B-LLM	LLaMA-3.1-8B	Greedy	85	45.0	66.2
	LLaMA-3.1-8B	Beam search	850	71.2	89.5

Appendix

Table 17 : Evaluation results on JSSP.

Method	3 $\times$ 3	4 $\times$ 3	4 $\times$ 4	5 $\times$ 4	5 $\times$ 5	6 $\times$ 6	8 $\times$ 8
GPT-5.4	35/35/1.11	27/39/1.11	17/23/1.20	2/10/1.23	1/ 6/1.29	0/ 0/1.37	0/ 0/1.58
GPT-5.4 (CoT)	82/82/1.02	77/84/1.07	47/60/1.06	7/21/1.17	6/ 9/1.19	0/ 2/1.36	0/ 0/2.19
GPT-5.4 (thinking)	100/100/1.00	96/100/1.00	94/99/1.00	79/100/1.01	73/96/1.01	40/60/1.05	0/ 8/1.15
Gemini 2.5 Pro	88/88/1.01	46/57/1.10	43/59/1.09	15/22/1.19	7/15/1.28	2/ 2/1.53	0/ 0/1.59
LLaMA-3.1-8B (beam-10)	100/100/1.00	98/100/1.00	90/97/1.00	72/92/1.01	67/91/1.01	22/78/1.04	0/ 0/11.12
LLaMA-3.1-8B (sample-BoN $T{=}1.0$ )	90/90/1.01	95/98/1.00	81/91/1.01	58/88/1.02	57/85/1.02	21/67/1.04	0/ 0/12.19

Appendix

Table 18 : JSSP per-size results. Each cell reports % optimal / % within

5\%

/ mean

\mathrm{ms\_ratio}

. Mean

\mathrm{ms\_ratio}

is computed over valid outputs only. Blackboard uses the validation-selected setting

(\rho,\tau)=(0.5,0.7)

with

N{=}10

(Section 4.1 ). The bottom row corresponds to the Blackboard entry in Table 17 .

Method	Mean NFE	% within 5%	Mean ms ratio
dLLM greedy	22	91.0	1.013
dLLM BoN (w/o trigger)	217	96.2	1.007
dLLM Blackboard	149	95.2	1.008

Appendix

Table 19 : Blackboard versus untriggered BoN on JSSP. Blackboard uses the validation-selected setting

(\rho,\tau)=(0.5,0.7)

Model	Valid trajectories	% optimal	Median $\mathrm{ms\_ratio}$	Unique makespans
LLaMA-3.1-8B	2,164	35.1	1.039	2.65
LLaDA-8B	2,219	51.0	1.000	2.88

Appendix

Table 20 : Per-trajectory JSSP quality before Best-of-

N

selection on the

226

puzzles for which the validation-selected Blackboard trigger fires. Both models are sampled with

N=10

and

T=1.0

; metrics are computed over valid trajectories. Unique makespans is the average number of distinct makespans among the

N=10

samples per puzzle.

Task	Statistic	$(\rho,\tau)$	Precision (%)	Recall (%)	Selection score
ZebraLogic-Hard	late-phase min	$(0.80,1.00)$	92.7	85.1	$F_{1}=88.7$
Nurse Rostering	late-phase mean	$(0.90,0.95)$	97.6	71.0	$F_{0.5}=90.8$
JSSP	late-phase min	$(0.50,0.70)$	21.4	79.6	$F_{1}=33.8$

Appendix

Table 21 : Pre-test trigger selection from greedy trajectories. Precision and recall refer to detecting greedy failures. ZebraLogic and JSSP select the pair with maximum

F_{1}

; Nurse Rostering selects by

F_{0.5}

to prioritize precision and avoid overwriting already-correct rosters.

Candidate width $k$	3	5 (main)	7
Recovered instances	21/25	22/25	23/25
Recovery rate	84%	88%	92%
Mean NFE	286–317	440–484	594–635

Appendix

Table 22 : ZebraLogic corrective-operator sensitivity on greedy failures (

n=25

). Recovery is unchanged across

\alpha\in\{0.85,0.90,0.95\}

; NFE ranges report variation across these

\alpha

settings.

Task	Result	Estimate [95% CI]
ZebraLogic-Hard	LLaDA greedy	78.4 [74.6, 81.8]
	LLaMA greedy	34.6 [30.6, 38.9]
	Paired greedy gap	+43.8 [+39.2, +48.2]
	LLaDA Blackboard	90.4 [87.5, 92.7]
Nurse Rostering	LLaDA greedy	73.0 [68.9, 76.7]
	LLaDA Blackboard	76.4 [72.5, 79.9]

Appendix

Table 23 : Uncertainty for selected main-task results. Marginal rates report

95\%

Wilson intervals; the ZebraLogic-Hard greedy gap uses a paired bootstrap with

20{,}000

resamples.

Model	Mode	Acc	Median latency	Median output tok.
GPT-5.4	standard	$24.4\%$	$16.2$ s	$965$
GPT-5.4	CoT	$35.4\%$	$31.0$ s	$2{,}207$
GPT-5.4	thinking	$73.2\%$	$72.9$ s	$3{,}934$
Gemini 2.5 Pro	thinking	$54.4\%$	$101.4$ s	$11{,}000$

Appendix

Table 24 : Frontier API references on ZebraLogic-Hard (

n=500

Model	Mode	Exact feasibility
GPT-5.4	standard	$15.8\%$
GPT-5.4	CoT	$51.0\%$
GPT-5.4	thinking	$86.0\%$
Gemini 2.5 Pro	thinking	$34.4\%$

Appendix

Table 25 : Frontier API references on Nurse Rostering (

n=500

). The metric is exact-feasibility rate.

Model	Mode	% opt	% within 5%	Mean ms ratio	Med lat	Med tok
GPT-5.4	standard	11.0	16.5	1.233	$4$ s	$224$
GPT-5.4	CoT	30.0	37.2	1.185	$40$ s	$2{,}686$
GPT-5.4	thinking	77.0	90.2	1.015	$170.6$ s	$10{,}472$
Gemini 2.5 Pro	thinking	27.8	35.0	1.201	$106.5$ s	$11{,}758$

Appendix

Table 26 : Frontier API references on JSSP. All rows use the full

n{=}400

evaluation set. % optimal and % within

5\%

use the full set as denominator, with invalid outputs counted as failures. Mean

\mathrm{ms\_ratio}

is computed over valid outputs only.

Domain	Problem type	Confidence role	Corrective action
Rotating-shift roster	unique feasibility	trajectory-level ranking	$\mathcal{C}_{\theta}$ -BoN
Asymmetric TSP	permutation optimization	compute allocation	objective-BoN

Appendix

Table 27 : Summary of supplementary transfer studies.

Method	All	d0	d1	d2	d3
LLaMA-3.1-8B (greedy)	8.8	13.8	5.0	5.0	11.2
LLaMA-3.1-8B (beam-10)	26.2	35.0	21.2	23.8	25.0
LLaMA-3.1-8B (Sample-BoN-10)	17.5	21.2	15.0	13.8	20.0
LLaDA-8B (greedy)	95.3	98.8	98.8	92.5	91.2
LLaDA-8B (Blackboard)	97.8	98.8	98.8	95.0	98.8

Appendix

Table 28 : Rotating-shift roster exact-match feasibility (%) by solver-backtrack difficulty. Each band contains

80

held-out instances.

Method	Trigger rate	Mean decodes	Exact feasibility (%)
LLaDA-8B (greedy)	–	1.00	95.3
BoN-10 on every instance	100%	11.00	97.8
Confidence-triggered Blackboard	4.7%	1.47	97.8

Appendix

Table 29 : Selective confidence-ranked BoN on rotating-shift roster. A fired instance receives ten additional stochastic completions.

Model and inference	% optimal	% within $5\%$	g3 % optimal
LLaMA-3.1-8B (greedy)	68.7	81.3	40.8
LLaMA-3.1-8B (objective-BoN-10)	89.0	94.7	75.0
LLaDA-8B (greedy)	70.7	82.3	39.5
LLaDA-8B (Blackboard)	92.7	97.3	82.9

Appendix

Table 30 : ATSP results on

300

held-out instances. Invalid permutation matrices count as failures for both metrics.

Method	All	g0	g1	g2	g3
LLaDA-8B (greedy)	70.7	91.9	84.0	68.0	39.5
LLaDA-8B (Blackboard)	92.7	98.6	97.3	92.0	82.9

Appendix

Table 31 : LLaDA-8B ATSP exact-optimal rate (%) by optimality-gap quartile. g0 has the largest optimality gap; g3 has the smallest gap.

Method	Trigger rate	Mean decodes	% optimal
LLaDA-8B (greedy)	–	1.0	70.7
Objective-BoN-10 on every instance	100%	11.0	92.7
Confidence-triggered Blackboard	70%	8.0	92.7

Appendix

Table 32 : Compute effect of confidence-triggered objective BoN on ATSP. A fired instance receives ten additional candidates, selected by minimum tour length.

Explore similar work

Scheduling Thoughts: Learning the Order of Thought in Diffusion Language Models
Jun 22, 2026Jiawei Xu, Minghui Liu, Aakriti Agrawal +2Diffusion Language Models Masked Diffusion Language Models
University of Maryland, College Park · University of California, Los Angeles.
Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata
Jul 8, 2026Meihua Dang, Stefano ErmonConstrained Decoding Diffusion Language Models
Stanford University
IFHierBench: Hierarchical Instruction Following for Large Language Models
Jul 30, 2026Yuetian Mao, Chunyang ChenInstruction-Tuned Models Instruction
Technical University of Munich

Jun 22, 2026, cs.LGJ/K move · Enter open · S save

Scheduling Thoughts: Learning the Order of Thought in Diffusion Language Models

Jiawei Xu, Minghui Liu, Aakriti Agrawal, Yifan Chen+1

University of Maryland, College Park · University of California, Los Angeles.

Diffusion Language Models Masked Diffusion Language Models Autoregressive Decoding Thoughts

Open paper AskPDF arXiv

Masked diffusion language models decode by iteratively unmasking tokens, where the unmasking order defines an "order of thought" that strongly influences generation quality yet is typically chosen heuristically. We derive a tractable upper bound on the sequential decoding mismatch, measured by the Kullback-Leibler divergence and expressed in terms of the model's pathwise log-likelihood, with tightness under sufficient model expressivity. This bound induces a dense self-aware reward over ordered trajectories, casting order selection as a principled policy optimization problem with a frozen denoiser. We instantiate this idea as Self-Aware Scheduling (SAS), which learns a lightweight order policy using Group Relative Policy Optimization and applies seamlessly to both any-order and semi-autoregressive decoding. On Sudoku with 1B MDM, SAS improves puzzle accuracy from 82.0% (best heuristic schedule) to 91.8%, and reaches 97.5% with second-stage fine-tuning along learned trajectories. On mathematical reasoning with LLaDA-8B, SAS improves pass@1 on GSM8K from 64% to 76% and on MBPP from 39.5% to 41%, consistently matching or exceeding heuristic schedules across generation lengths and block sizes. Project page: https://jimmyxu123.github.io/SAS

Abstract

Explore similar work

Scheduling Thoughts: Learning the Order of Thought in Diffusion Language Models

Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

IFHierBench: Hierarchical Instruction Following for Large Language Models