CA-HNM: Constraint-Aware Hard Negative Mining for Dense Retrieval with Structured Domain Models

1 Introduction

• Retrieval proximity can identify informative candidates, but incomplete relevance judgments mean highly ranked unjudged documents may still be relevant or ambiguous.Random negatives are often too easy, while lexical or dense retrieval can provide harder candidates [27]; missing positives and ambiguous cases may remain.Source: §1 · p. 2
• CA-HNM combines lexical and dense retrieval candidates with known-positive removal and deterministic compatibility rules based on a local typed context around the query target.It records relation, scope, target, or level evidence for selected negatives.Source: §1 · p. 2
• Across two collections, two encoders, two losses, and ten seeds, the evaluation compares constraint-aware selection with rank-matched and matched-mixed controls and tests structural variants.The study is organized around three questions about negative source, mixed pools, and available structure.Source: §1 · p. 2
• The paper separates retrieval hardness, positive annotation, and structured incompatibility, while leaving the inference-time retriever unchanged.Its contributions include explicit relation, scope, target, or level evidence and a multiseed evaluation across datasets, encoders, losses, and controls.Source: §1 · p. 2

2 Related Work

• Dense retrieval architectures span bi-encoders, late interaction, and learned sparse representations, with benchmark results varying across domains and tasks [22].This work focuses on how retrieval training signals are constructed or selected.Source: §2 · p. 3
• Hard-negative methods select candidates through retrieval signals, but unjudged high-ranking documents may still be relevant when judgments are incomplete.Examples include ANCE [27], RocketQA, ADORE, and BM25; effectiveness also depends on difficulty and sampling strategy.Source: §2 · p. 3
• Generated-supervision methods create training examples from text or model predictions, while generally not using explicit domain relations to test retrieved-candidate compatibility.Examples include Promptagator [3], InPars, GPL, and SyNeg [14].Source: §2 · p. 3
• Structured knowledge has supported search, retrieval, recommendation, and learning-resource annotation, with educational collections offering explicit concept relations.MOOCCubeX provides concepts and prerequisites, while Course-Skill Atlas provides hierarchical and related-skill structure.Source: §2 · p. 3
• CA-HNM addresses the gap between these lines by applying structured-domain incompatibility during offline hard-negative selection without changing the dual-encoder architecture or inference procedure.Prior work has mainly treated retrieval-based hardness, generated supervision, and structured knowledge as separate mechanisms.Source: §2 · p. 3

3.1 Dense Retrieval and Retrieval Hardness

• A candidate absent from the known-positive set is not thereby established as non-relevant, because relevance judgments may be incomplete.The formulation separates absence of positive annotation from operational incompatibility.Source: §3.1 · p. 4, §3 · p. 4
• Conventional hard-negative mining uses a retrieval-hardness criterion for unjudged candidates, with hardness based on BM25, dense similarity, or a transformation of retrieval rank.The hardness function is defined so that larger values indicate greater hardness, but it does not supply a domain-based incompatibility criterion.Source: §3.1 · p. 4

3.2 Structured Incompatibility

• The structured model is represented by concepts, typed relations, concept attributes, and document–concept associations, with each query assigned a target concept.Attributes can include labels, aliases, descriptions, or levels; the structure may be an ontology, taxonomy, knowledge graph, controlled vocabulary, or typed concept graph.Source: §3.2 · p. 4
• The operational incompatibility indicator is one when a candidate satisfies an implemented rule, and its violation set records the rule evidence used during mining.The rule types include relation, scope or granularity, target, and level mismatches; the violation set is not an independent relevance judgment.Source: §3.2 · p. 4
• Retrieval can rank a candidate close to the query without explaining why it is inappropriate, while structured context adds concept-relation, scope, target, or level signals.The figure contrasts conventional selection with compatibility evaluation against the target concept and its local structured context.Source: §3.2 · pp. 4–5, Figure 1 · p. 5
• A constraint-aware negative must be retrieval-hard, not a known positive, and satisfy at least one implemented incompatibility rule.The empirical comparison asks whether this selection changes training relative to candidates from comparable retrieval positions selected without the structured model.Source: §3.2 · p. 5
• The selected set excludes known positives and retains candidates meeting the hardness threshold and incompatibility test.This formalizes the requirement that retrieval-hardness alone does not make a candidate a constraint-aware negative.Source: §3.1 · p. 4, §3.2 · p. 5

4 Constraint-Aware Hard Negative Mining

• CA-HNM combines retrieval hardness with structured-domain incompatibility in a three-phase pipeline for negative selection and dual-encoder fine-tuning.The phases are candidate construction, structured incompatibility classification, and negative selection for retriever training.Source: §4 · p. 5

4.1 Candidate Construction

• Lexical or dense top-K candidates form the pool; known positives are removed before rules screen remaining candidates for target or conflicting evidence.A candidate is eligible when it appears among the top-K results of at least one retriever.Source: §4.1 · pp. 5–6, Figure 2 · p. 6

4.2 Target Context and Constraint Classification

• Rules use the target's local typed context to identify relational, scope/level, or target mismatches; matches, ambiguous cases, and candidates without explicit evidence are excluded.The available relation types around the target determine the context; the framework does not require one fixed ontology schema.Source: §4.2 · pp. 6–7

4.3 Negative Selection, Controls, and Training

• Pure selection round-robins eligible candidates by primary violation type, preserving retrieval order within groups and retaining at most four per query.The rank-matched control uses the same retrieved pool but selects eligible non-positive candidates at approximately matched retrieval positions without structured constraints.Source: §4.3 · p. 7
• Mixed pools combine conventional and constraint-aware sources; matched-mixed replaces the constraint-aware source with rank-matched candidates under the same allocation procedure.Duplicates are removed before the four-negative budget is applied.Source: §4.3 · p. 7
• Selected examples fine-tune a standard dual encoder with triplet loss or cached MNRL; structured information affects negative-set composition, not encoder inputs.The encoder does not receive structured information during training or inference.Source: §4.3 · p. 8

5 Experimental Setup

• The study evaluates three questions: Pure versus rank-matched selection, Mixed versus matched-mixed pools, and the effects of structural variants.The principal experiment uses two datasets, two encoders, two losses, four negative strategies, and ten seeds.Source: §5 · p. 8, §5.2 · p. 9

5.1 Datasets

• MOOCCubeX and Course-Skill Atlas become query–document retrieval tasks, with concepts or skills as queries and resources or curriculum records as documents.Splits are query-level with no query or target overlap; results are interpreted separately because Course-Skill Atlas has more relevant documents per query.Source: §5.1 · p. 8

5.2 Compared Methods

• The methods include random, dense, rank-matched, CA-HNM-Pure, and mixed-pool comparisons; structural variants are analyzed as end-to-end sensitivities.Label-only, shuffled-graph, and no-structure variants can change candidate eligibility and negative-pool composition, so they are not treated as relation-level interventions.Source: §5.2 · p. 8

5.3 Evaluation and Statistical Analysis

• The study reports NDCG@10, MRR@10, MAP@100, and Recall@100, with RQ1 paired by seed and query for hierarchical 95% bootstrap intervals on NDCG@10.RQ2 reports mean NDCG@10 differences, while RQ3 is interpreted as end-to-end sensitivity; interval width is considered alongside the mean for Course-Skill Atlas.Source: §5.3 · p. 9

6.1 RQ1: Comparison with Rank-Matched Selection

• Absolute performance varies by configuration: CA-HNM-Pure leads all four Course-Skill Atlas metrics only for E5 with triplet loss, while other strategies lead in other settings.On MOOCCubeX, DPR-Random or DenseNeg has the highest absolute mean score in every encoder–loss block.Source: §6.1 · p. 9, Table 3 · p. 10
• CA-HNM-Pure has higher mean NDCG@10 in six of eight configurations; four hierarchical 95% bootstrap intervals are entirely above zero, while the other four span zero.Three of the four intervals entirely above zero occur under triplet loss.Source: §6.1 · p. 10, Figure 3 · p. 11

6.2 RQ2: Mixed Negative Pools

• CA-HNM-Mixed changes mean NDCG@10 by +0.0038 on Course-Skill Atlas and +0.0076 on MOOCCubeX relative to matched-mixed.Mean differences favor CA-HNM-Mixed on three of four Course-Skill Atlas metrics and all four MOOCCubeX metrics; the NDCG@10 differences are small.Source: §6.2 · p. 11

6.3 RQ3: Structural Sensitivity

• Structural variants differ across collections: shuffled-graph leads all four metrics on Course-Skill Atlas, while no-structure leads all four on MOOCCubeX.These variants can change candidate eligibility and negative-pool composition, so the results reflect end-to-end sensitivity rather than relation changes alone.Source: §6.3 · p. 12

7 Discussion

• The more consistent positive pattern under triplet loss may reflect how each objective uses negatives, but the experiments do not estimate the loss-by-selection interaction.Triplet loss contrasts each query–positive pair with the selected negative; cached MNRL distributes competition across explicit, cached, and in-batch examples.Source: §7 · p. 12
• CA-HNM-Mixed’s small NDCG@10 differences from matched-mixed on both collections indicate that replacing one source can depend on the remaining negative-pool composition.The mixed-pool experiment separates complete-pool performance from the contribution of its constraint-aware component.Source: §7 · p. 12
• Structural-variant scores cannot be attributed solely to relation semantics because variants can change candidate eligibility and negative-pool composition.A relation-level analysis would need candidate identities, retrieval positions, and pool sizes held fixed while relations are modified.Source: §7 · pp. 12–13
• Evidence is limited to two educational datasets with explicit structured metadata; Course-Skill Atlas has only 32 development queries.The mixed-pool and structural experiments are restricted to BGE with cached MNRL.Source: §7 · p. 13

• CA-HNM-Pure had higher mean NDCG@10 than rank-matched selection in six of eight configurations.Source: §8 · p. 13
• Four hierarchical 95% bootstrap intervals were entirely above zero, and the pattern was more consistent under triplet loss than cached MNRL.Source: §8 · p. 13
• In the BGE/cached-MNRL mixed experiment, CA-HNM-Mixed was close to matched-mixed in NDCG@10.Source: §8 · p. 13
• Structural variants showed that changing available structure can substantially alter the negative pool; future work will test fixed-candidate perturbations to separate relation semantics from candidate-composition effects.Source: §8 · p. 13