EviGraph: Proof-Carrying Selective Recommendation over Temporal Public-Service Knowledge Graphs

1 Introduction

• The motivating mismatch is that current kindergarten vacancies establish neither occasional-care availability nor a future booking, while missing administrative details need not invalidate an otherwise supported recommendation.Useful navigation distinguishes decision-critical evidence from information suited to follow-up.Source: §1 · p. 1
• EviGraph distinguishes critical eligibility and essential recommendation evidence from procedural or preference details that remain visible without independently blocking a recommendation.A language model links request requirements to candidate-local evidence; a deterministic compiler checks applicability and retains a proof.Source: §1 · p. 1
• The benchmark combines bilingual Hong Kong care requests with service, time, and provenance constraints, disjoint entities and structural templates, and executable policy references.The references expose their assumptions.Source: §1 · p. 1
• EviGraph recovers recall relative to an all-field compiler, but its verifier removes supported recommendations without removing unsupported ones.A strong rule-only baseline also limits claims of an intrinsic advantage from using a language agent; positive recommendation evidence is concentrated in kindergarten navigation and does not establish current availability.Source: §1 · p. 1

Retrieval and knowledge graphs

• Graph-guided retrieval methods connect evidence across entities and documents, whereas EviGraph studies which evidence authorizes decisions over fixed candidates with service, scope, and time constraints.Related approaches include Think-on-Graph, ToG-2, KG2RAG, and K-RagRec.Source: §2 · p. 2

Attribution and verification

• Attribution and correction work evaluates citation support or revises unsupported outputs; EviGraph instead measures whether decision-critical verification improves decisions beyond citation validity.The discussion notes that intrinsic self-correction can fail or degrade reasoning.Source: §2 · p. 2

Selective prediction and uncertainty

• EviGraph separates demonstrated ineligibility, which permits exclusion, from insufficient evidence, which calls for verification; its confidence curves are descriptive, not conformal guarantees.Related selective-prediction work includes SelectiveNet and selective question answering under domain shift.Source: §2 · p. 2

Structured reasoning and proof interfaces

• EviGraph adopts proof-carrying-code separation between an untrusted producer and a policy checker for typed obligation witnesses over extracted facts.Its checks establish applicability under the declared policy conditional on query interpretation and extraction, not real-world admission or availability.Source: §2 · p. 2

3.1 Decision interface

• RECOMMEND supports navigation without reserving a place, EXCLUDE requires demonstrated hard ineligibility, and VERIFY retains unresolved essential conditions.Evidence states are prioritized as CONFLICTING, MISSING, STALE, then SUPPORTED; a supported zero-vacancy fact need not justify a recommendation.Source: §3.1 · p. 2

3.2 Sources and reference construction

• The benchmark contains 6,300 scenarios and 25,500 candidate decisions across Base, Compositional, and Stress partitions, all based on historical public-service evidence.Claims preserve source, date, and service scope; general provider descriptions cannot establish a vacancy or person’s eligibility.Source: §3.2 · p. 2
• Compositional requests include 150 current/future contrasts across three domains, while positive recommendation references come from kindergarten vacancies and other care domains retain unresolved provider-specific needs.Reference labels are automated policy judgments rather than human assessments or observed service outcomes; controlled stress cases alter facts, dates, evidence order, or introduce contradictions.Source: §3.2 · pp. 2–3

3.3 Entity and template separation

• Entity-relation clusters and structural templates are separated across splits to hold out requirement compositions, without claiming unseen service families.Semantic similarities may remain, and the split does not claim complete semantic separation.Source: §3.3 · p. 3

4.1 Typed evidence obligations

• Typed obligations distinguish hard eligibility and essential recommendation requirements from procedural, preference, informational, or uncertain roles; procedural wording such as “hard” does not itself establish person-side ineligibility.Evidence-graph nodes include requirements, constraints, claims, services, scopes, time intervals, and sources, with typed edges for applicability, support, contradiction, scope, time, and provenance.Source: §4.1 · p. 3

4.2 Shared query extraction and local linking

• The agent extracts requirements once per scenario and shares them across candidates, then links established obligations to visible rules or claims without changing query facts per candidate.Deterministic checks reject cross-candidate or nonexistent paths and incompatible service, grade, session, or time relationships; stated needs cannot establish provider capabilities.Source: §4.2 · p. 3

4.3 Time and scope are proof conditions

• A kindergarten vacancy can witness availability for that service and time, but cannot establish occasional-care availability or a future booking when scope or date mismatches.The checker compares compatible scope and effective dates before freshness; retrieval time cannot replace an absent update timestamp, and same-scope, same-time conflicts persist regardless of evidence order.Source: §4.3 · pp. 3–4, Figure 2 · p. 4

4.4 Minimal sufficient proof and selective compilation

• The compiler recommends only when every critical obligation has a valid witness; it excludes on demonstrated hard-eligibility failure and otherwise verifies unresolved cases.Procedural and preference gaps remain in the explanation rather than becoming critical blockers; the retained certificate is inclusion-minimal within its witness representation, not globally minimum.Source: §4.4 · p. 4

4.5 Bounded verification and adjudication

• Verification can downgrade only initial recommendations for cited critical-path defects, and one adjudication may restore an original recommendation by answering every accepted blocker with valid paths.Initial VERIFY and EXCLUDE decisions cannot be upgraded; calls and accepted or rejected blockers are logged.Source: §4.5 · p. 4

5.1 Models and comparisons

• All methods use GPT-5-mini, the same candidate set, and the same evidence pool, while differing in retrieval, representation, and processing.Comparisons include Rule-only, Direct prediction, Flat RAG, Critic-and-guard, All-field compiler, and EviGraph with and without verification.Source: §5.1 · p. 5

5.2 Ablations and stability

• Development ablations vary obligation checks and whether every information gap blocks recommendation, while three independent runs assess EviGraph’s stability.Compiler ablations share archived query extractions and link proposals; settings and baseline selection are fixed before held-out testing.Source: §5.2 · p. 5

5.3 Evaluation measures and statistical tests

• Evaluation distinguishes decision macro-F1, recommendation precision, recall and coverage, and error types, with paired entity-cluster intervals and Holm-corrected McNemar tests.The confidence score is descriptive rather than calibrated risk; effect sizes and cluster uncertainty remain primary, with results separated by partition and evaluated across slices.Source: §5.3 · p. 5

6.1 Do typed obligations recover useful recall?

• EviGraph achieves base and stress recommendation recall of 0.869 and 0.880, respectively, with no unsupported recommendations under the policy references.The comparison uses the same held-out candidates and source evidence pool; the all-field compiler issues no recommendations.Source: §6.1 · p. 5, Table 2 · p. 6
• EviGraph macro-F1 is 0.900, 0.864, and 0.900 on base, compositional, and stress cases; Rule-only scores 0.915, 0.816, and 0.927.EviGraph’s stress interval favors Rule-only, while base and compositional intervals include zero; EviGraph scores below its unverified variant in every partition.Source: Table 3 · p. 6, §6.1 · p. 6

6.2 Which components matter, and how stable are the results?

• Across three independent runs, EviGraph base recall averages 0.833 (standard deviation 0.115), with a minimum of 0.688.The passage characterizes recall recovery as not consistently robust across runs despite the favorable primary test result.Source: §6.2 · pp. 6–7
• Making every information gap blocking lowers macro-F1 across all three development partitions, while removing the verifier increases it in each partition.Scope, time, and semantic-check ablations have mixed effects, so the table does not support a claim that every added check improves average performance.Source: §6.2 · p. 6, Table 5 · p. 7

6.3 How informative is confidence?

• Confidence-ranked coverage curves do not establish calibrated risk, and confidence rankings differ by partition.Low error among issued recommendations does not ensure low error among all retained candidates.Source: §6.3 · p. 7

Verification and supported recommendations

• 21 policy-supported and 0 unsupported recommendations were withdrawn; 31 adjudications restored 10, reducing coverage without an observed reduction in unsupported actions.This is the primary GPT-5-mini evaluation; EviGraph w/o verifier issued 238 blind recommendations, compared with 217 retained by EviGraph.Source: §7 · p. 7

Proof checks and semantic correctness

• Decision errors rose from 233 to 239 on base, 18 to 22 on compositional, and 16 to 27 on stress cases, matching supported recommendations withdrawn.Rejected-link counts do not measure final decision errors because a candidate may retain a valid witness after an invalid link is discarded.Source: §7 · p. 7

Support and distribution boundaries

• Positive recommendation references occur only in kindergarten vacancy navigation, leaving positive-class recall unidentifiable in other care domains.Temporal contrasts provide positive controls under fixed source evidence, but support-enriched development sampling does not estimate natural request or website-error prevalence.Source: §7 · p. 7

Development ablations

• Removing scope checks raised development-scope F1 to 1.000, while removing time checks raised compositional false-recommendation rate to 0.571.The scope-ablation result is specific to its development subset.Source: §7 · p. 8

Cross-backbone results

• In the exploratory comparison, Opus reached base F1 0.944 and Sonnet 0.902, both with zero observed false recommendations; verification showed no observed gain across completed configurations.Cross-backbone differences also reflect uncontrolled provider interfaces and reasoning settings, so generality across services remains unresolved.Source: §7 · p. 8

What verification can correct

• Because verification acts only on initial recommendations, it can remove unsupported positives but cannot recover supported candidates already assigned VERIFY or EXCLUDE.When initial recommendations are all policy-supported, accepted downgrades can only reduce recall; evaluation should condition on errors available for correction.Source: §7 · p. 8

• Verification reduced macro-F1 in all GPT-5-mini partitions and yielded no gain with Claude, supporting separate assessment of proof construction and verification.Source: §8 · p. 8
• EviGraph requires evidence matching requested service, scope, and time while allowing unresolved paperwork or preferences to remain follow-up items.Source: §8 · p. 8
• Future work should use independently authored requests and broader provider-specific evidence, with human assessment of interpretation, applicability, and navigation utility.Source: §8 · p. 8

• Requests are synthetic or programmatically composed, and automated policy judgments replace human reference judgments.Neither human query understanding nor actual applications, admissions, reservations, or service outcomes are evaluated; bilingual renderings lack independent annotation.Source: Limitations · p. 9
• Historical evidence and research-assumed freshness windows mean a supported vacancy fact is not a current service guarantee.Sparse entities and unresolved provider evidence limit distributional coverage and recall identifiability.Source: Limitations · p. 9
• Candidate selection and temporal contrasts shape the evaluation distribution, while uncontrolled reasoning and serving configurations prevent isolating backbone effects.Findings are limited to the evaluated methods, domains, and partitions.Source: Limitations · p. 9

Ethical Considerations

• EviGraph is a research instrument, not an automated eligibility authority, and should not be used to deny care.Verification means evidence is insufficient for the stated request, not that a person is unsuitable; no real-world access or social-benefit claim is made.Source: Ethical Considerations · p. 9

A Evaluation Integrity

• Primary predictions were finalized before reference labels were revealed, and checks covered split separation, attribution, and candidate coverage.Archived responses support recomputation, but rerunning a language model may produce different outputs.Source: A Evaluation Integrity · p. 10

B Additional Decision Examples

• A current vacancy cannot establish future availability; removing the date requirement helps only when every other critical obligation is supported.A missing medical form is procedural follow-up, whereas a demonstrated age violation can establish ineligibility; requested grade also does not establish attended grade.Source: B Additional Decision Examples · pp. 10–11

C Interpretation of Reproducibility

• Reproducing the benchmark decisions makes its evidence, rules, selection, and proof conditions inspectable, but does not validate them against human judgments.Source: C Interpretation of Reproducibility · p. 11

D Benchmark Construction

• The 6,300-scenario benchmark uses automated policy rules, with positive references concentrated in kindergarten navigation and no estimate of natural care-request prevalence.The partitions contain 4,500 Base, 300 Compositional, and 1,500 Stress scenarios; entity clusters, service identifiers, and structural query relations are split-disjoint, while semantic similarities may remain.Source: D Benchmark Construction · p. 11

E Query and Proof Interfaces

• Requirements are extracted once per scenario and linked to candidate-visible rules or claims; deterministic checks reject invalid attribution, scope, and time relationships.The proof is relative to the normalized query and published research policy, not evidence of actual admission or reservation.Source: E Query and Proof Interfaces · pp. 11–12

F Method Configurations

• Rule-only uses fixed bilingual extraction, while EviGraph adds bounded verification only for initial recommendations and cannot upgrade initial VERIFY or EXCLUDE candidates.Ablations share query extractions and local-link responses, helping isolate the changed checks.Source: F Method Configurations · p. 12

G Execution and Reproducibility

• Resource and latency comparisons are descriptive because methods used separate execution windows and development selection and test evaluation used different service tiers.Retry allowances were amended before reference access for eligible identity failures; unequal retry workloads remain a comparison condition, and all attempts were archived.Source: G Execution and Reproducibility · pp. 12–13, Table 8 · p. 13

H Development Results

• Rule-only leads the development comparison; removing its time checks raises its compositional false-recommendation rate to 0.571 and stress rate to 0.143.Removing scope checks raises base macro-F1 to 1.000 in this subset, showing that a check’s contribution depends on the evaluated query distribution.Source: H Development Results · p. 13

I Evaluation Measures and Statistical Interpretation

• Decision macro-F1 averages RECOMMEND, VERIFY, and EXCLUDE, while confidence discounts critical-obligation proof coverage for unresolved procedural, preference, and informational obligations.The resulting risk–coverage curves are descriptive and do not establish a calibrated risk bound.Source: I Evaluation Measures and Statistical… · p. 13

J Blind Results and Stability

• Verification withdraws 21 supported recommendations without removing unsupported ones, and all three paired macro-F1 intervals favor EviGraph without the verifier.This is a loss of useful coverage, not a citation-validity failure; mechanical rejection counts alone do not identify semantic error causes.Source: J Blind Results and Stability · p. 14

K Held-Out Evaluation and Reproducibility

• Benchmark checks establish that evaluation can be performed, but do not establish effectiveness; reported decisions are reproducible without validating the references against human judgments.Test results cannot change prompts, evidence roles, decision thresholds, or experimental settings.Source: K Held-Out Evaluation and… · p. 14

L Exploratory Cross-Backbone Evaluation

• The cross-backbone evaluation uses a fixed 250-scenario development subset and all 1,926 test scenarios, totaling 7,206 candidate decisions; no test candidate subset is selected for comparison.Primary GPT-5-mini outputs are reused without new benchmark inference.Source: L Exploratory Cross-Backbone Evaluation · p. 14
• Paired entity-cluster bootstrap intervals and effect sizes are primary; candidate-level McNemar tests are diagnostic, with the full 57-comparison Holm allocation retained for 42 completed comparisons.Incomplete partitions are omitted from tables, and dependence between candidates limits independent-pair interpretations.Source: L Exploratory Cross-Backbone Evaluation · p. 16
• Across completed Claude configurations, EviGraph exceeds Direct and Flat RAG with zero observed false recommendations, while Rule-only remains competitive, particularly on Stress.The reported repetition variability limits claims of consistently reliable coverage.Source: L Exploratory Cross-Backbone Evaluation · p. 16
• Sonnet recommendation recall falls from 0.86 to 0.80 on base, 0.94 to 0.90 on compositional, and 0.95 to 0.85 on stress, while precision remains 1.00.Opus recall remains 0.98, 1.00, and 0.83, respectively, with and without verification; unchanged test decisions do not establish stability across repeated execution.Source: L Exploratory Cross-Backbone Evaluation · p. 16