Datalog underpins reasoning tasks such as program analysis, but its programs are hard to write. Existing synthesizers automate this task but require users to state their intent as input-output examples. Large language models (LLMs) suggest a more natural route, text-to-Datalog synthesis from a natural-language question, yet how well they do so has not been systematically evaluated. We present DatalogBench, a benchmark of 136 text-to-Datalog synthesis tasks curated from existing Datalog-based artifacts. Synthesized programs are graded by execution on held-out inputs against an oracle validated by mutation analysis. Across six LLMs and four prompting configurations, exact match peaks at 68.4%, and relation descriptions or an input-output example have only modest, model-dependent effects. Under direct prompting, most failures occur at compile time, typically because a model invents auxiliary predicates that it never declares or types consistently. Two coding agents reach up to 83.8% and eliminate nearly all such failures, leaving mostly semantic errors concentrated in recursive tasks. DatalogBench thus identifies recursive reasoning and decomposition as open challenges for current LLMs and agents, and offers a reliable, execution-grounded measure of both.
Figures & tables
Figure 1: A DatalogBench task with relation signatures only. The prompt carries the question and the signatures, and Soufflé runs the candidate program on the held-out evaluation variants and compares its output with the expected facts.
Figure 2: The four phases of benchmark construction and what each produces.
Program complexity
Datalog-specific structure
Avg. / max rules
5.1 / 57
Recursive tasks
78
Avg. / max body atoms
2.3 / 10
Max recursive SCC size / count
9 / 4
Avg. / max largest arity
3.4 / 20
Avg. auxiliary predicates
1.4
Avg. / max strata
1.5 / 5
Tasks using negation / aggregation
34 / 22
Inputs
Outputs
Avg. relations
2.9
Avg. relations
1.5
Table 1: Structural and data statistics of DatalogBench . The largest arity of a program is the most arguments any of its predicates takes; strata are the layers of a stratified evaluation; an SCC is a set of mutually recursive predicates, and its count is the most recursive SCCs in any one program; trimmed averages exclude the five largest tasks. Tuple counts are for each task’s first evaluation variant.
Model
Signature
Description
CP (%)
EX (%)
EX † (%)
CP (%)
EX (%)
EX † (%)
GPT 5.6 Sol
77.2
55.9
60.3
72.1
51.5
57.4
Claude Opus 5
75.7
52.2
52.2
83.8
60.3
60.3
Gemini 3.7 Flash
81.6
61.8
63.2
83.1
65.4
66.9
DeepSeek V4 Pro
67.6
47.8
53.7
66.9
50.0
55.9
DeepSeek V4 FT
52.9
40.4
52.2
50.7
36.8
49.3
Table 2: Zero-shot results with relation signatures or descriptions. EX † also credits programs made exact by synthesizing only their omitted declarations. Bold marks each column’s best.
Agent / Model
Compile Pass
Exact Match
KD
GA
PA
FR
Overall
KD
GA
PA
FR
Overall
Codex / GPT 5.6 Sol
100.0
93.9
100.0
96.6
97.8
88.9
81.8
80.9
79.3
82.4
CC / Claude Opus 5
96.3
97.0
91.5
93.1
94.1
85.2
84.8
85.1
79.3
83.8
Table 3: Coding agents with relation signatures, no input–output example, and up to four turns (%). KD: knowledge discovery; GA: graph analytics; PA: program analysis; FR: formal reasoning.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
Provider
System
API identifier
Role in the design
Model
OpenAI
GPT 5.6 Sol
gpt-5.6-sol
Frontier breadth
Model
Anthropic
Claude Opus 5
claude-opus-5
Frontier breadth
Model
Google
Gemini 3.7 Flash
gemini-3.7-flash
Frontier breadth
Model
DeepSeek
DeepSeek V4 Pro
deepseek-v4-pro
Frontier breadth; scale contrast vs. Flash
Model
DeepSeek
DeepSeek V4 FT (Flash, thinking)
deepseek-v4-flash
Reasoning ablation, thinking arm
Model
DeepSeek
DeepSeek V4 FNT (Flash, non-thinking)
deepseek-v4-flash
Reasoning ablation, non-thinking arm
Appendix
Table 4: Models, agents, and symbolic baselines evaluated on DatalogBench , with the role of each in the design and the API identifier it was served under.
Program complexity
Specification load
Tier
n
Rules
Max SCC
Strata
Largest arity
Tier
n
Invented
Inputs
NL words
Easy
46
2
1
1
2
Easy
46
0
2
25
Medium
45
3
1
1
3
Medium
45
0
2
14
Hard
45
6
1
2
4
Hard
45
2
4
13
Appendix
Table 5: Difficulty tiers along two axes, as the median of each raw metric within a tier. Max SCC has median 1 in every tier because singleton SCCs dominate, including in non-recursive programs.
Program complexity
Specification load
Domain
Easy
Medium
Hard
Easy
Medium
Hard
Program analysis
10
19
18
0 7
14
26
Graph analytics
15
10
0 8
13
15
0 5
Formal reasoning
0 9
0 7
13
15
0 8
0 6
Knowledge discovery
12
0 9
0 6
11
0 8
0 8
Appendix
Table 6: Difficulty tier distribution by domain along each axis.
Domain
n
Recursive
Negation
Aggregation
Avg. Strata
Max SCC
Avg. Invented
Program analysis
47
42.6%
10
0 6
1.38
6
1.55
Graph analytics
33
75.8%
0 9
11
1.82
9
1.67
Formal reasoning
29
79.3%
10
0 4
1.62
3
1.59
Knowledge discovery
27
37.0%
0 5
0 1
1.30
7
0.63
Appendix
Table 7: Structural profile by domain.
Group
Class
Count
Share (%)
Predicate invention left incomplete
Undeclared auxiliary predicate
293
28.3
Untypable rule defining one
164
15.8
Soufflé dialect
Aggregate computed in a rule head
76
7.3
Malformed body aggregate
62
6.0
Reserved word used as a name
42
4.1
Operator from C or SQL
37
3.6
Appendix
Table 8: Causes of the 1,036 Direct compile failures, pooled over the 24 cells.
Model
Schema
Compile Pass
Exact Match
KD (%)
GA (%)
PA (%)
FR (%)
Overall
KD (%)
GA (%)
PA (%)
FR (%)
Overall
GPT 5.6 Sol
Signature
85.2
63.6
80.9
79.3
77.2
70.4
48.5
55.3
51.7
55.9
Description
81.5
51.5
80.9
72.4
72.1
70.4
36.4
55.3
44.8
51.5
Claude Opus 5
Signature
77.8
69.7
85.1
65.5
75.7
59.3
42.4
63.8
37.9
52.2
Description
92.6
87.9
83.0
72.4
83.8
74.1
60.6
59.6
48.3
60.3
Gemini 3.7 Flash
Signature
88.9
84.8
80.9
72.4
81.6
70.4
57.6
70.2
44.8
61.8
Appendix
Table 9: Zero-shot model performance by reasoning domain under both schemas.
Tool
Runs
Synthesis success (%)
CP (%)
EX (%)
Average F1
EGS
1
58.8±8.1
100.0±0.0
36.0±8.1
45.3±7.9
GenSynth
5
34.6±7.8
100.0±0.0
25.4±7.2
30.6±7.2
ProSynth
1
10.3±5.1
100.0±0.0
8.1±5.1
9.4±5.1
Appendix
Table 10: Symbolic synthesis from examples, as percentages over the 136 tasks; ± is the wider half of the percentile-bootstrap 95% interval. GenSynth averages five runs per task; EGS and ProSynth are deterministic single runs. Synthesis success means the tool returned a non-empty rule set.
Codex / GPT 5.6 Sol
CC / Claude Opus 5
Solved by agent, not by Direct
37
43
already solved by declaration repair
6 ( 16.2% )
0 ( 0.0% )
not explained by declaration repair
31
43
of which recursive / auxiliary predicate
23 / 13
32 / 25
Recursive ( 78 ): Direct → agent
42.3→74.4
35.9→76.9
Non-recursive ( 58 )
74.1→93.1
74.1→93.1
Appendix
Table 11: What agent interaction changed with relation signatures and no input–output example, against each agent’s matched Direct cell. Upper block: tasks the agent solves and the Direct cell does not, split by whether declaration repair alone solves them. Lower block: exact match (%) by reference structure, with each pair’s gap computed from the counts before percentages are rounded.
Jun 22, 2026·Yucheng Wu, Jundong Xu, Mingzhen Ju +4Reasoning Skills
State Key Laboratory of Multimedia Information Processing, Peking University · School of Computer Science, Peking University · School of Computing, National University of Singapore +3