Database-Native Agent Routing via Relational Graph Aggregation

Full report

On this page

Executive Summary

We propose a deterministic, SQL-based routing engine that selects the best AI agent for an incoming query by leveraging historical query–agent interactions stored in relational tables. The design treats past queries and agents as a bipartite graph: each Query node connects via execution edges to Agent nodes, with edge attributes (success, latency, cost, quality, etc.). When a new query arrives, we find semantically similar historical queries (via vector search) and propagate information one hop from those query neighbors across their execution edges to candidate agents. In SQL this is implemented with joins and GROUP BY aggregations (mirroring a GNN’s message-passing but using standard relational operations). The aggregated statistics (weighted by similarity, recency, and evidence quality) form a feature vector for each agent. A versioned C# scoring policy then deterministically computes a score for each agent (using normalized success rate, cost, latency, reliability, availability, etc.), performs stable tie-breaking, and selects the agent. All decision details (query hash, neighbors, feature values, chosen agent, etc.) are logged for auditability.

This approach avoids the complexity of training and maintaining a separate Graph Neural Network (GNN). Instead, it uses native SQL Server features: vector data types and functions (for nearest-neighbor search) and set-based joins/aggregations (for message passing). Recent research shows that simple feature-aggregation methods can rival GNNs on many tasks, and indeed our method is analogous to collaborative filtering in recommender systems. The system is entirely deterministic and explainable (no black-box learning step), easier to version and monitor, and incurs only database infrastructure cost (which can be optimized with indexes, columnstore, etc.). We design for sub-50ms latency under realistic workloads (e.g. millions of historical queries, thousands of edges, tens of agents) by careful indexing and caching, and we compare this SQL-native router to a hypothetical GNN baseline across accuracy, complexity, and maintainability dimensions.

Literature Review of Agent Routing and Relational Aggregation

AI Agent Routing: Modern AI applications often involve many specialized agents (e.g. retrievers, planners, tool callers) cooperating in a workflow. A router agent’s job is to direct each query to the appropriate specialized agent. The routing logic can be rule-based, model-based, or LLM-based. In single-agent routing, one incoming input is sent to one agent; in multi-agent routing, an input may be handled by multiple agents in parallel. Good routing is crucial: mis-routing can cascade errors through the pipeline. Our work targets deterministic, data-driven routing rather than pure rule- or LLM-based methods.

Graph-Based Routing: Conceptually, routing can be viewed as a bipartite recommendation problem: queries are “users” and agents are “items”, and historical execution edges are user-item interactions. This is analogous to collaborative filtering in recommender systems, which groups users by behavior to suggest items. In our case, similar queries (neighbors) “vote” for the best agent(s) based on past performance. Unlike pure content-based routing, we use both semantics (via embeddings) and performance history.

Graph Neural Network (GNN) Baseline: A more complex approach would convert the relational history into a graph and train a GNN to predict the best agent. In fact, prior work (Relational Deep Learning) treats relational databases as graphs and applies message-passing neural networks. However, GNNs require training, introduce non-determinism, and are often opaque. Recent research shows that fixed one-hop aggregation features can rival GNNs on many benchmarks. For example, Sum/Mean/Max aggregations over neighbors (no learning) plus a simple classifier achieve competitive accuracy on 12 out of 14 graph tasks. This supports our choice of explicit SQL-based aggregation: it yields highly interpretable features and avoids the complexity of learned GNN layers, yet can provide similar predictive power.

SQL Graph Features: SQL Server offers “graph” tables (node/edge tables) and MATCH queries, but these are largely syntactic sugar over joins and add complexity. We instead use plain relational tables for queries, agents, and execution edges. (SQL Graph ensures referential integrity on node/edge IDs, but our joins accomplish the same with indexed foreign keys.) The key innovation is to do one-hop message passing via SQL: finding neighbor queries, joining through their execution edges, and grouping by agent. As noted by relational-learning research, a GNN message-passing step is essentially a SQL join + group-by aggregate. We exploit this by writing set-based T-SQL queries that scatter each query’s “message” (its weight) along edges and reduce (aggregate) at the agent.

Similarity Retrieval: Core to routing is finding historical queries semantically similar to the incoming query. Traditionally this is done by vector similarity search on embeddings. SQL Server 2025 introduced a native vector type and functions (VECTOR_DISTANCE, VECTOR_SEARCH) for exact and approximate nearest-neighbor search. Exact kNN (VECTOR_DISTANCE) scans, while approximate (VECTOR_SEARCH) uses ANN indexes (preview in SQL 2025/Azure) for speed. Our design uses these where available; if not (e.g. older SQL Server on-premise), we fall back to an external search service (e.g. Azure AI Search) to retrieve top-k query IDs. Thus we integrate embeddings into the DB if possible, but have a practical fallback.

Statistical Considerations: Using historical routing data can introduce bias (we only see outcomes of agents that were tried). We must guard against selection bias, survivorship bias, and cold-start issues. For example, a highly specialized agent might appear weak if it was only tried on difficult queries. We plan to include smoothing, minimum evidence thresholds, and possibly randomized exploration to mitigate such biases. Issues like Simpson’s paradox and nonstationarity (changing agent performance) will be addressed by monitoring and versioning (discussed later).

In summary, our approach combines ideas from recommender systems, feature-based graph aggregation, and SQL analytics. We leverage recent advances in SQL vector search and combine them with deterministic policy scoring in C#. The result is a fully explainable, SQL-native router with clear audit trails and performance optimizations.

Relational Schema Design

We model the data with ordinary relational tables (not SQL Graph tables) for flexibility and compatibility with vector search and SQL constructs. The key tables are:

• IncomingQueries (IncomingQueryId PK, QueryHash, TimestampUtc, Status, ContentKey etc.) – records each new query arrival. We store a hash of the query text (not raw text) to enable auditing without leaking content.
• HistoricalQueries (QueryId PK, IncomingQueryId FK, TimestampUtc, RefreshTimeUtc, Status, Category, etc.) – stores each past query instance with metadata (timestamp, category/class, versioning). Contains foreign key to the original incoming query event.
• QueryEmbeddings (QueryId PK FK, Embedding VECTOR, ModelVersion, ComputeTimeUtc) – stores the semantic embedding (vector) for each historical query. (Alternatively, this could be part of HistoricalQueries, but often stored separately due to vector size.) Index: create a vector index on this column (if available) for fast nearest-neighbor search.
• Agents (AgentId PK, Name, Role, Capabilities, etc.) – catalog of available agents. Use a surrogate INT key (no Id suffix in display names per spec).
• AgentCapabilities (AgentId FK, Capability, Version, etc.) – if needed, describes what each agent can do. This allows capability-based filtering (e.g. ignore agents lacking a required skill).
• QueryAgentExecutions (ExecutionId PK, QueryId FK, AgentId FK, StartTimeUtc, EndTimeUtc, LatencyMs, Status, ErrorCategory, ModelVersion, Env, etc.) – each row is an edge in the bipartite graph linking a query to an agent that attempted it. Records outcome metrics: success/failure, reward, cost, latency, quality scores, etc. Indexes: (QueryId), (AgentId) as foreign keys, and a composite index on (QueryId, AgentId) to cover lookups.

• ExecutionOutcomes (ExecutionId FK, Success, Reward, HumanScore, etc.) – (Optional) If separation of outcome data is needed (e.g. for extensibility). Could be merged with QueryAgentExecutions for simplicity.
• AgentAvailability (AgentId FK, IsAvailable, LastCheckedUtc, ExpiresUtc, etc.) – tracks which agents are currently available. This is joined to disable agents that are down or busy.
• AgentCostProfiles (AgentId FK, CostCoefficient, MaxCost, etc.) – e.g. dollar cost or token-cost weight for calling each agent, used in scoring.
• RoutingDecisions (DecisionId PK, IncomingQueryId FK, TimestampUtc, PolicyVersion, SelectedAgentId, Candidates, NeighborQueryIds, AggregatedFeatures, TieBreakReason, FallbackReason) – logs each routing decision for audit. Fields include: query hash, list of considered agents, list of neighbor query IDs (maybe JSON or separate table), aggregated agent features (could be JSON or normalized columns), the agent chosen, policy version used, and reason if fallback or tie-break. We store weights and feature vectors per decision for explainability.

• RoutingPolicyVersions (PolicyVersionId PK, Definition, CreatedUtc) – metadata about each scoring policy version.

Keys & Relationships: Use integer surrogate PKs for queries and agents. Foreign keys enforce integrity (e.g. each execution edge references a valid Query and Agent). All timestamps use UTC (DateTimeOffset) to avoid timezone issues. We include Version or TimestampUtc columns on critical tables to allow rolling updates and temporal reasoning. Queries and executions can be partitioned by date if volumes are huge.

Indexes:

• On HistoricalQueries, index on (Category, TimestampUtc) if filtering by query type or recency.
• On QueryEmbeddings, a vector index on the Embedding column (preview in SQL Server 2025/Azure). Also consider a regular index on (QueryId) if searching by ID.
• On QueryAgentExecutions, cluster on (QueryId) since we often join from query to edges. A covering index on (AgentId, QueryId, Success, LatencyMs, Reward, ModelVersion) will speed aggregation by agent. Also, an index on (AgentId) helps joins from edges to agents.
• On AgentAvailability, index on (AgentId, ExpiresUtc) to quickly find active agents.
• On RoutingDecisions, index on (TimestampUtc) and (IncomingQueryId), to retrieve past decisions if needed.

We do filtered indexes for “active” data: e.g., an index on QueryAgentExecutions where TimestampUtc is within the last N days (to skip stale edges). Columnstore indexes may be appropriate on very large, append-only tables like QueryAgentExecutions. Columnstore scanning can be 50–100× faster for analytics. We can maintain a clustered columnstore on QueryAgentExecutions for high-volume analytical queries (like aggregations over millions of edges), while keeping a filtered rowstore index on recent data for fast lookups.

Graph vs. Relational Tables: We considered using SQL Server’s graph tables (node/edge tables), but chose plain tables because: graph tables still use joins under the hood; they lack rich indexing options (beyond internal pseudo-columns); and vector search on graph nodes would still require relational support. Using standard tables makes the design clearer and fully compatible with all SQL features (search, window functions, etc.). In practice, our joins on regular tables implement the same connectivity semantics as a graph.

Similarity Retrieval Architecture

We need to find the top-K historical queries most semantically similar to the incoming query. We assume an embedding (e.g. OpenAI-based) has already been generated for each stored query. The options in SQL Server (as of 2025) are:

• Exact vector search: Use the new VECTOR data type and VECTOR_DISTANCE for kNN queries. This does an exhaustive distance calculation, which is precise but can be slow on large tables. It is currently recommended only for <50k vectors or when heavy filters reduce the search set.
• Approximate vector index: Use CREATE VECTOR INDEX and the VECTOR_SEARCH function (with TOP (k) WITH APPROXIMATE). This ANN index (DiskANN) is a preview feature in SQL Server 2025 and Azure SQL. It delivers orders-of-magnitude speedup on large data, but has limitations (initially read-only tables, preview-only syntax).

We distinguish scenarios:

• On Azure SQL Database / Azure SQL Managed Instance, all features are available. We would create a vector index on the QueryEmbeddings table and perform an approximate search for nearest neighbors.
• On SQL Server 2025 on-premises, approximate index is in preview; if allowed, we can enable it. If not, we rely on exact search with VECTOR_DISTANCE (or VECTOR_SEARCH with no index, which falls back to scanning).
• On older SQL Server or other RDBMS, there is no native vector search. In that case, we propose a hybrid: use an external vector search service (e.g. Azure AI Search or a ML service) to get the top query IDs, then do the aggregation join entirely in SQL.

Current Capabilities: As of writing, Microsoft documentation states that vectors and VECTOR_DISTANCE are generally available in SQL 2025 (and Azure). Approximate VECTOR_INDEX and VECTOR_SEARCH are preview and supported only in SQL 2025/Azure SQL. Notably, the new VECTOR_SEARCH syntax requires enabling a preview flag and only works on Azure SQL or the latest SQL Server 2025 with updates. If that is not possible, the fallback plan is:

Fallback Design: Precompute or externally compute query embeddings, push them into an Azure AI Search index, and query that for the top N similar historical query IDs. Those IDs are then input to a temp table in SQL, after which the routing aggregation SQL runs against that candidate set. This keeps all heavy lifting (similarity search) outside the DB but uses the DB for the actual routing logic. (Alternatively, one could store precomputed similarity nearest-neighbor lists in SQL offline, but that is inflexible for new queries.)

Thus, our architecture is: User query → Router service → compute embedding (external or in-DB AI model) → SQL: run SELECT QueryId, VECTOR_DISTANCE(...) ORDER BY distance (or VECTOR_SEARCH for ANN) to get neighbors → SQL: join neighbors → aggregate metrics per agent → C#: score agents → return chosen agent.

Here, neighbors weighting can incorporate semantic similarity (via the distance output) and freshness (e.g. weight decay by query age). We can compute a weighted weight column in SQL such as SimilarityWeight = Exp(-λ * AgeDays) * (1 - Distance), or factor them in the aggregation query. This ensures more recent and more similar queries have more influence.

One-Hop Relational Message Passing (SQL)

We implement one-hop message passing entirely with SQL. The high-level steps are:

1. Identify neighbors: Use the incoming query’s embedding to retrieve top-K similar historical queries (by vector distance). This produces a table SimilarQueries(QueryId, SimilarityScore).
2. Weight by recency and quality: Optionally compute a combined weight for each neighbor, e.g. Weight = SimilarityScore * f(recency) * f(queryQuality). This can be done via a CTE or subquery.
3. Join to execution edges: Join these neighbor queries to the QueryAgentExecutions table to find all past attempts by any agent on those queries.
4. Aggregate by agent: Group the joined rows by AgentId and compute aggregated statistics: weighted success rate, average reward, average latency, average cost, failure rate, count (sample size), capability match, etc. Also track total weight and weighted sample size. Apply smoothing (e.g. add a small constant count) to agents with few edges to avoid spurious high rates.
5. Output feature vector: The query returns one row per agent with all aggregated features (normalized as needed). This is the input to the scoring policy.

A sketch of the T-SQL (with simplified fields) might look like:

-- 1. CTE of top-K neighbor queries (already pre-filtered by category, if needed):
WITH Neighbors AS (
    SELECT TOP(@K) q.QueryId,
           VECTOR_DISTANCE('cosine', @IncomingEmbedding, qe.Embedding) AS Distance,
           POWER(@DecayFactor, DATEDIFF(day, q.TimestampUtc, SYSUTCDATETIME())) AS RecencyWeight
    FROM HistoricalQueries q
    JOIN QueryEmbeddings qe ON q.QueryId = qe.QueryId
    WHERE q.TimestampUtc <= SYSUTCDATETIME()   -- only past
      AND q.Category = @CategoryFilter       -- optional filter by query type
    ORDER BY Distance
),
NeighborWeights AS (
    SELECT QueryId,
           (1.0 - Distance) * RecencyWeight AS Weight
    FROM Neighbors
),
AgentScores AS (
    SELECT e.AgentId,
           SUM(nw.Weight * CASE WHEN e.Success = 1 THEN 1 ELSE 0 END)
             / NULLIF(SUM(nw.Weight),0) AS WeightedSuccessRate,
           SUM(nw.Weight * e.Reward) / NULLIF(SUM(nw.Weight),0) AS WeightedAvgReward,
           SUM(nw.Weight * e.LatencyMs) / NULLIF(SUM(nw.Weight),0) AS WeightedAvgLatency,
           SUM(nw.Weight * e.Cost) / NULLIF(SUM(nw.Weight),0) AS WeightedAvgCost,
           SUM(nw.Weight * CASE WHEN e.ErrorCategory IS NOT NULL THEN 1 ELSE 0 END)
             / NULLIF(SUM(nw.Weight),0) AS WeightedFailureRate,
           SUM(nw.Weight) AS TotalWeight,
           COUNT(*) AS RawCount
    FROM NeighborWeights nw
    JOIN QueryAgentExecutions e
      ON nw.QueryId = e.QueryId
    WHERE e.AgentId IN (SELECT AgentId FROM AgentAvailability WHERE IsAvailable = 1)
    GROUP BY e.AgentId
)
SELECT
  a.AgentId,
  COALESCE(as.TotalWeight,0) AS SampleWeight,
  COALESCE(as.RawCount,0) AS RawCount,
  COALESCE(as.WeightedSuccessRate, 0) AS SuccessRate,
  COALESCE(as.WeightedAvgReward, 0) AS AvgReward,
  COALESCE(as.WeightedAvgLatency, 0) AS AvgLatency,
  COALESCE(as.WeightedAvgCost, 0) AS AvgCost,
  COALESCE(as.WeightedFailureRate, 0) AS FailureRate,
  ac.CostCoefficient AS AgentCost,
  ac.MaxCost AS AgentMaxCost,
  ac.AgentId AS AgentCapabilityId -- example of capability match, etc.
FROM Agents a
LEFT JOIN AgentScores as ON a.AgentId = as.AgentId
LEFT JOIN AgentCostProfiles ac ON a.AgentId = ac.AgentId
WHERE a.IsActive = 1; -- further filter for active, compliant agents

This query exemplifies scatter (JOIN Neighbors→executions) and gather (GROUP BY AgentId). Each neighbor (with weight) “sends” its data along edges to the agent, which aggregates (reduces) them. The semantics mirror a GNN layer.

In the SQL, the SUM(nw.Weight * metric)/SUM(nw.Weight) does a weighted average. We use NULLIF(SUM(nw.Weight),0) to avoid divide-by-zero, defaulting to 0 when no evidence. Smoothing can be added by e.g. + epsilon to numerator and denominator for small counts. We also join AgentAvailability to skip agents currently down. Additional joins can incorporate AgentCapabilities or compliance flags to filter agents without required skills.

Join/Group vs. Message Passing: Each JOIN + GROUP BY implements one-hop message passing. The Neighbors CTE finds nodes at distance 1 in the query subgraph. The JOIN QueryAgentExecutions is the message (each neighbor sends its weight to connected agents). The GROUP BY AgentId is the reduce step, aggregating all messages arriving at each agent. This corresponds directly to the scatter-gather paradigm of graph processing.

The final SELECT normalizes and coalesces nulls to handle missing history. It outputs one row per eligible agent with a full feature vector. These features (success rate, latency, cost, sample size, etc.) will be fed into the deterministic C# scoring policy.

C# Scoring Policy Design

The C# policy consumes the SQL-derived features for each candidate agent and computes a single score to rank agents. It must be deterministic (no randomness) and versioned (weights can change over time). We design an interface and one concrete implementation as an example. We include [Display(Name=...)] on every property and XML docs as required.

using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Linq;

/// <summary>
/// Represents the aggregated feature metrics for a single agent as input to the scoring policy.
/// </summary>
public class AgentRoutingFeatures
{
    /// <summary>Identifier of the agent.</summary>
    [Display(Name = "Agent")]
    public int AgentId { get; set; }

    /// <summary>Weighted success rate (0.0–1.0).</summary>
    [Display(Name = "Success Rate")]
    public double SuccessRate { get; set; }

    /// <summary>Normalized fit to the query (0.0–1.0).</summary>
    [Display(Name = "Capability Fit")]
    public double CapabilityFit { get; set; }

    /// <summary>Average latency of past executions (in milliseconds).</summary>
    [Display(Name = "Latency")]
    public double AverageLatencyMs { get; set; }

    /// <summary>Average cost of past executions (in application-specific units).</summary>
    [Display(Name = "Cost")]
    public double AverageCost { get; set; }

    /// <summary>Agent reliability metric (e.g. 1 - failure rate).</summary>
    [Display(Name = "Reliability")]
    public double Reliability { get; set; }

    /// <summary>Total weighted sample size contributing to the above metrics.</summary>
    [Display(Name = "Sample Size")]
    public double SampleWeight { get; set; }

    /// <summary>Current availability flag (true if agent is available now).</summary>
    [Display(Name = "Availability")]
    public bool IsAvailable { get; set; }

    /// <summary>Time elapsed since last relevant data (freshness).</summary>
    [Display(Name = "Data Freshness (days)")]
    public double AgeDays { get; set; }

    /// <summary>External risk/compliance factor (0.0–1.0, higher means more risk).</summary>
    [Display(Name = "Risk Factor")]
    public double RiskFactor { get; set; }
}

/// <summary>
/// Represents the scoring result for an agent, including its computed score and tie-break info.
/// </summary>
public class AgentScore
{
    /// <summary>Identifier of the agent.</summary>
    [Display(Name = "Agent")]
    public int AgentId { get; set; }

    /// <summary>Computed score for ranking.</summary>
    [Display(Name = "Score")]
    public double Score { get; set; }

    /// <summary>Reason for tie-break selection if any (e.g. lexicographic lowest id).</summary>
    [Display(Name = "Tie-Break Reason")]
    public string TieBreakReason { get; set; }
}

/// <summary>
/// Interface for deterministic agent scoring policies.
/// </summary>
public interface IAgentScoringPolicy
{
    /// <summary>
    /// Selects the best agent based on the given feature vectors and current policy weights.
    /// </summary>
    /// <param name="features">Feature vectors for each eligible agent.</param>
    /// <param name="policyVersion">Identifier of the policy version to use.</param>
    /// <returns>The selected agent's score and decision reasoning.</returns>
    AgentScore SelectAgent(IEnumerable<AgentRoutingFeatures> features, string policyVersion);
}

/// <summary>
/// Example scoring policy using a weighted linear combination of features.
/// </summary>
public class WeightedLinearScoringPolicy : IAgentScoringPolicy
{
    private readonly double[] weights; // indices: 0=SuccessRate,1=CapabilityFit,2=Latency,3=Cost,4=Reliability,5=SampleSize,6=Freshness,7=Risk

    /// <summary>
    /// Initializes a new instance with specified weights (for demonstration).
    /// </summary>
    public WeightedLinearScoringPolicy()
    {
        // Example weights for each normalized feature. In practice these come from policy config.
        weights = new double[] { 5, 3, -1, -2, 4, 1, -0.1, -5 };
    }

    /// <inheritdoc />
    public AgentScore SelectAgent(IEnumerable<AgentRoutingFeatures> features, string policyVersion)
    {
        if (features == null) throw new ArgumentNullException(nameof(features));

        // Normalize and compute scores for each agent
        var scored = new List<AgentScore>();
        foreach (var f in features)
        {
            // Feature normalization: assume inputs are already scaled 0..1 or appropriate units.
            // If any feature is missing or sample is too small, handle gracefully (e.g., treat Rate=0 or skip).
            if (!f.IsAvailable || f.SampleWeight <= 0)
            {
                // Do not consider unavailable agents
                scored.Add(new AgentScore { AgentId = f.AgentId, Score = double.NegativeInfinity, TieBreakReason = "Unavailable or no history" });
                continue;
            }

            // Linear combination (higher better):
            double score =
                  weights[0] * f.SuccessRate
                + weights[1] * f.CapabilityFit
                + weights[2] * (-f.AverageLatencyMs)    // negative weight for latency
                + weights[3] * (-f.AverageCost)         // negative weight for cost
                + weights[4] * f.Reliability
                + weights[5] * Math.Log(1 + f.SampleWeight)  // log-sample-size
                + weights[6] * (-f.AgeDays)            // prefer fresh
                + weights[7] * (-f.RiskFactor);        // penalize risk

            scored.Add(new AgentScore { AgentId = f.AgentId, Score = score });
        }

        // Select agent with max score; stable tie-break by agent ID ascending
        var best = scored
            .OrderByDescending(a => a.Score)
            .ThenBy(a => a.AgentId)  // stable tie-break
            .FirstOrDefault();

        if (best == null || best.Score == double.NegativeInfinity)
        {
            // No qualified agent found
            return new AgentScore { AgentId = -1, Score = double.NaN, TieBreakReason = "No qualified agent" };
        }
        best.TieBreakReason = "Selected by max score (stable break on ID)";
        return best;
    }
}

Discussion: This example uses a simple weighted sum of features. We normalize or invert features appropriately (higher latency/cost are worse, so we multiply by –weight). The sample size is log-transformed to reduce impact of very large counts. Features with no evidence (zero SampleWeight) or agents marked unavailable get a -∞ score so they are never chosen. The ordering applies a stable tie-break (lowest AgentId) in case of equal scores. We include a policyVersion parameter that could switch weight sets if versions change. The [Display(Name=...)] annotations ensure that UI or documentation would show friendly field names (omitting “Id” suffix as requested). All public methods have XML <summary> and <param> tags for clarity.

In production, one would externalize the weights and maybe use a more sophisticated formula (e.g. a small decision tree or rules), but it must remain deterministic. We also define a special case: if no agent qualifies, the policy can return an abstention (AgentId = -1) or default agent. The “Tie-Break Reason” field records how ties were broken.

Statistical Validity and Bias Mitigation

Using historical routing data raises several pitfalls. We must proactively address:

• Selection Bias & Survivorship Bias: Agents that were tried more often will dominate counts. We mitigate by normalizing metrics (not using raw counts) and applying smoothing or minimum thresholds so rarely-used agents aren’t unfairly dismissed. We might also require a minimum SampleWeight before trusting high success rates. In extreme, we can ensure each agent is given some chance (epsilon-greedy) to avoid never exploring some agent.

• Cold-Start Agents: A newly deployed agent has no history. The policy should initially give it a chance (perhaps by inflating a neutral prior or smoothing) until enough data accrues. For a completely new agent, we could assign a default “starting score” equal to the average agent. Without this, the new agent might never be chosen.

• Cold-Start Queries: A query of a novel type may have few or no neighbors. If the neighbor set is empty, the router should have a fallback (e.g. route to a default agent or use content-based rules). We will detect “Missing history” and default to a safe agent or abstain.

• Non-Stationarity: Over time, agent performance can change (due to new model versions, data drift, etc.). We include timestamps and version tags on edges and possibly time-weight the data (as shown above). We can also periodically re-evaluate policy effectiveness and update weights.

• Correlated Outcomes & Simpson’s Paradox: If different agent work on systematically different queries, overall success rates may mislead. We could stratify by query category or include query-category features. Ensuring our query similarity step clusters truly similar queries helps reduce this effect.

• Reward Inconsistency & Rating Drift: If human quality scores or rewards drift over time or agents change their scoring, we include model/version fields on edges to filter or adjust older data.

• Exploration vs Exploitation: A purely deterministic best-agent approach could exploit known winners. We may allow occasional exploration (e.g. if no agent exceeds a threshold, choose randomly or alternate) – but this must be controlled to remain reproducible.

As a safeguard, we will track offline metrics (e.g. uplift from following the policy vs. other strategies) and perform A/B tests in a limited release. Statistical controls like holdout sets of queries can reveal if our routing is overfit to a narrow set of examples.

Performance and Scalability

We target 50ms 95th-percentile routing latency under reasonable load. To achieve this, we assume:

• Historical Data: 10 million historical query records, 50 million execution edges.
• Agents: ~100 specialized agents.
• Neighbors: retrieving top 50 similar queries.
• Concurrency: 200 concurrent routing requests.
• Hardware: SQL Server 2025 on a beefy VM (32 cores, 128GB RAM, SSD), ASP.NET Core service for routing.

Indexes:

• A clustered index on QueryAgentExecutions(QueryId, AgentId) ensures the join from queries to edges is indexed.
• A covering index on (AgentId, QueryId, Success, Reward, LatencyMs, Cost) covers the aggregates.
• A vector index on QueryEmbeddings (for Azure/SQL2025) accelerates nearest-neighbor search.
• Filtered indexes: e.g. a filtered index on AgentAvailability for only current agents, or on QueryAgentExecutions for recent data, reduce scanned rows.
• For very large edges, a clustered columnstore index on QueryAgentExecutions can vastly speed scans/aggregates. For example, a columnstore can make aggregations ~100× faster by scanning compressed columns. We might use a nonclustered columnstore on QueryId, AgentId, Success, Latency, Cost for analytics; combined with a rowstore B-tree on QueryId for lookups.

Partitioning: Tables like QueryAgentExecutions and HistoricalQueries should be partitioned by time (e.g. by month), so old data can be pruned or accessed efficiently via partition elimination. This speeds up queries limited to recent history.

Query Store & Plan Stability: We enable Query Store to capture and force good plans. We will recompile if parameter sniffing causes skew. Using OPTIMIZE FOR UNKNOWN or query hints can mitigate parameter variability (e.g. if K changes).

Caching and Precomputation:

• We cache recent routing results at the application layer for duplicate queries.
• If many queries fall into broad classes, we could precompute nearest neighbors in advance (e.g. nightly) and store them.
• Common sub-expressions (e.g. the aggregated metrics per agent) could be materialized and incrementally updated, or computed in a persisted stored procedure.

Concurrency: Routing is mostly read-only: vector search (read), joins/aggregations (read). Using a separate read replica for analysis queries could prevent contention. Tempdb usage should be monitored (GROUP BY and sorts). If tempdb becomes a bottleneck, we may need resource governance or rewrite queries.

Hardware & Topology: We assume at least 8 logical CPUs for vector search and 24+ for aggregation parallelism. Using an Always On availability group or read scale-out can help if load is high. SSDs for fast scan, large memory for caching hot indexes. We rely on the OS cache and SQL buffer pool – hit rates should be tuned.

Given the complexity, we would create a detailed benchmark plan (below) rather than claim the target outright. But with proper indexing (especially vector index and columnstores) and a modest neighbor count (50-100), achieving <50ms for the SQL part seems feasible.

Benchmark Harness Design

To validate performance, we design a repeatable benchmark. Key metrics to measure:

• Database execution time (ms) for the entire routing query (vector search + aggregation).
• End-to-end routing time including vectorization and C# scoring (ms).
• CPU usage, memory grants, I/O: track for each query.
• Logical reads and tempdb usage (affecting cache).
• Query plan stability: ensure consistent plans over runs.
• Throughput: requests per second and concurrent users vs latency.
• Tail latency: measure 95th/99th percentile.
• Cache behavior: separate tests for warm (in-cache) vs cold (clearing caches before run).

Data Generation: We provide scripts to generate synthetic but realistic data:

• HistoricalQueries: random timestamps, categories, and text features.
• QueryEmbeddings: use a smaller vector dimension (e.g. 128) filled with synthetic floats.
• Agents: e.g. 50 agents with varied capability sets.
• QueryAgentExecutions: assign each historical query to 1-5 random agents with random outcomes (success/failure), latencies, and costs. Include some correlation so better agents succeed more often.
• AgentAvailability: random up/down flags.
• Possibly use Faker or other libraries in C# or Python to populate millions of rows.

Benchmarking Tools: We recommend:

• Database timing: Use SQL Profiler / Extended Events or Query Store metrics (actual_duration, reads).
• Application timing: Use BenchmarkDotNet or a lightweight .NET client to issue queries and measure end-to-end. Instrumentation on CPU/memory.
• Write warm-cache tests (run once to load data, then measure) and cold-cache tests (flush buffer pool, repeat).
• Vary parameters: number of neighbors (k=10,50,100), number of historical edges.
• Ensure to measure tail latencies by capturing many runs and looking at percentiles.

We provide a C# harness using BenchmarkDotNet that calls the routing method under load. It logs execution times and SQL stats (via SqlCommand.Statistics or similar). We also script running trace for wait stats.

We will iterate on schema/indexes if needed based on observed bottlenecks. Only after data-driven proof can we confidently meet SLA.

Database-Native vs. GNN Comparison

In summary, the SQL-native approach is best when transparency, simplicity, and low latency are priorities. It excels for deterministic, audit-friendly routing and can be tuned for new evidence quickly. A GNN might excel in very large-scale or highly complex graphs where learned multi-hop patterns are needed, but it comes with significant overhead and opaqueness. For our problem – a bipartite history of agent outcomes – recent research suggests that well-chosen fixed features (like our aggregated success/cost stats) often suffice. We anticipate that for typical query-routing workloads, the SQL solution will match or outperform a learned GNN in both accuracy and operational robustness, except perhaps in extremely dynamic or graph-structured tasks beyond one-hop.

Observability and Auditability

Every routing decision is logged comprehensively to enable auditing and debugging. The RoutingDecisions table (or equivalent log) will contain:

• QueryHash: a secure hash of the incoming query content (no raw text).
• CandidateAgents: list of eligible agents considered.
• NeighborQueries: IDs (or hashes) of the historical queries retrieved and their similarity weights.
• AggregatedFeatures: the final feature vector computed for each agent (success rate, reward, etc.).
• PolicyVersion: which scoring policy version was used.
• FeatureWeights: the weights or coefficients applied (can also be in policy version metadata).
• SelectedAgentId: the agent chosen.
• TieBreakInfo: reason if tie-breaking was applied (e.g. “AgentId lowest”).
• FallbackReason: if the router abstained or used a fallback agent, the justification.
• DecisionTimeUtc: timestamp of routing decision.
• OutcomeCorrelationId: if we later correlate the query’s final result to judge accuracy, we store an ID linking to the post-action evaluation.

These fields (or JSON blobs) are designed to answer any question like “Why did we pick agent X instead of Y?” without exposing query text. We explicitly store the hashed query ID to tie back to results if needed, and we record all intermediate data.

In addition to logging each decision, we will expose metrics and traces:

• Counters: total requests, re-routes, fallbacks, by agent.
• Histograms: decision latencies, number of neighbors found, feature values distribution.
• Alerts: e.g. if no agent qualified for many requests, or if routing latency spikes.

These observability practices follow best practices of agent routing: for example, Patronus AI emphasizes adding logging and testing to agent routers, and our detailed decision log will allow diagnosing whether a failure is due to routing vs. agent performance.

Test Suite

We provide a suite of tests covering edge cases and ensuring determinism. Below is a sketch of representative tests (using xUnit for brevity):

using Xunit;
using System.Linq;

public class RoutingPolicyTests
{
    private IAgentScoringPolicy policy = new WeightedLinearScoringPolicy();

    /// <summary>Clear best agent: one agent has highest success and lowest cost.</summary>
    [Fact]
    public void TestClearBestAgent()
    {
        var features = new[]{
            new AgentRoutingFeatures { AgentId=1, SuccessRate=0.9, CapabilityFit=1.0, AverageLatencyMs=100, AverageCost=10, Reliability=0.9, SampleWeight=100, IsAvailable=true, AgeDays=1, RiskFactor=0.0 },
            new AgentRoutingFeatures { AgentId=2, SuccessRate=0.5, CapabilityFit=1.0, AverageLatencyMs=50, AverageCost=5, Reliability=0.5, SampleWeight=100, IsAvailable=true, AgeDays=1, RiskFactor=0.0 }
        };
        var result = policy.SelectAgent(features, "v1");
        Assert.Equal(1, result.AgentId);
    }

    /// <summary>Tie-breaking: two agents have equal score.</summary>
    [Fact]
    public void TestTieBreak()
    {
        // Make features identical except agent IDs
        var f1 = new AgentRoutingFeatures { AgentId = 1, SuccessRate = 1.0, CapabilityFit = 1.0, AverageLatencyMs = 0, AverageCost = 0, Reliability = 1.0, SampleWeight=10, IsAvailable=true, AgeDays=0, RiskFactor=0.0 };
        var f2 = new AgentRoutingFeatures { AgentId = 2, SuccessRate = 1.0, CapabilityFit = 1.0, AverageLatencyMs = 0, AverageCost = 0, Reliability = 1.0, SampleWeight=10, IsAvailable=true, AgeDays=0, RiskFactor=0.0 };
        var result = policy.SelectAgent(new[]{ f1, f2 }, "v1");
        // Should pick lower AgentId due to stable tie-break
        Assert.Equal(1, result.AgentId);
        Assert.Contains("stable break", result.TieBreakReason);
    }

    /// <summary>Missing history: no neighbors found (empty features).</summary>
    [Fact]
    public void TestMissingHistory()
    {
        var features = Enumerable.Empty<AgentRoutingFeatures>();
        var result = policy.SelectAgent(features, "v1");
        Assert.Equal(-1, result.AgentId); // -1 indicates no qualified agent
    }

    /// <summary>Cold-start agent: agent with zero sample weight but available.</summary>
    [Fact]
    public void TestColdStartAgent()
    {
        var f = new AgentRoutingFeatures { AgentId = 5, SuccessRate = 0.0, CapabilityFit = 0.5, AverageLatencyMs = 100, AverageCost = 1, Reliability = 0.0, SampleWeight = 0, IsAvailable = true, AgeDays = 100, RiskFactor = 0.0 };
        var result = policy.SelectAgent(new[]{ f }, "v1");
        Assert.Equal(-1, result.AgentId); // no history, should not pick
    }

    /// <summary>Unavailable top agent: best agent is marked unavailable.</summary>
    [Fact]
    public void TestUnavailableAgent()
    {
        var f1 = new AgentRoutingFeatures { AgentId=1, SuccessRate=0.9, AverageLatencyMs=50, AverageCost=5, Reliability=0.9, SampleWeight=10, IsAvailable=false, AgeDays=1, CapabilityFit=1.0, RiskFactor=0 };
        var f2 = new AgentRoutingFeatures { AgentId=2, SuccessRate=0.5, AverageLatencyMs=100, AverageCost=10, Reliability=0.5, SampleWeight=10, IsAvailable=true, AgeDays=1, CapabilityFit=1.0, RiskFactor=0 };
        var result = policy.SelectAgent(new[]{ f1, f2 }, "v1");
        Assert.Equal(2, result.AgentId); // second agent should win because first is unavailable
    }

    /// <summary>Extreme latency outlier should reduce agent score.</summary>
    [Fact]
    public void TestLatencyOutlier()
    {
        var f1 = new AgentRoutingFeatures { AgentId=1, SuccessRate=0.8, AverageLatencyMs=10, AverageCost=5, Reliability=0.8, SampleWeight=50, IsAvailable=true, AgeDays=1, CapabilityFit=1.0, RiskFactor=0 };
        var f2 = new AgentRoutingFeatures { AgentId=2, SuccessRate=0.8, AverageLatencyMs=10000, AverageCost=5, Reliability=0.8, SampleWeight=50, IsAvailable=true, AgeDays=1, CapabilityFit=1.0, RiskFactor=0 };
        var result = policy.SelectAgent(new[]{ f1, f2 }, "v1");
        Assert.Equal(1, result.AgentId); // outlier latency penalizes agent 2
    }

    /// <summary>Small-sample overperformance: ensure smoothing (not fully implemented, but check sample weight usage).</summary>
    [Fact]
    public void TestSmallSampleOverperformance()
    {
        var f1 = new AgentRoutingFeatures { AgentId=1, SuccessRate=1.0, AverageLatencyMs=10, AverageCost=1, Reliability=1.0, SampleWeight=1, IsAvailable=true, AgeDays=0, CapabilityFit=1.0, RiskFactor=0 };
        var f2 = new AgentRoutingFeatures { AgentId=2, SuccessRate=0.5, AverageLatencyMs=5, AverageCost=2, Reliability=0.5, SampleWeight=10, IsAvailable=true, AgeDays=0, CapabilityFit=1.0, RiskFactor=0 };
        var result = policy.SelectAgent(new[]{ f1, f2 }, "v1");
        // Without smoothing, agent1 might win despite tiny sample; policy uses log(sample).
        Assert.Equal(2, result.AgentId);
    }

    /// <summary>Deterministic selection on repeated calls.</summary>
    [Fact]
    public void TestDeterministicRepeat()
    {
        var features = new[]{
            new AgentRoutingFeatures { AgentId=3, SuccessRate=0.7, CapabilityFit=0.9, AverageLatencyMs=50, AverageCost=5, Reliability=0.7, SampleWeight=20, IsAvailable=true, AgeDays=2, RiskFactor=0.1 },
            new AgentRoutingFeatures { AgentId=4, SuccessRate=0.6, CapabilityFit=0.8, AverageLatencyMs=30, AverageCost=6, Reliability=0.6, SampleWeight=20, IsAvailable=true, AgeDays=2, RiskFactor=0.1 }
        };
        var r1 = policy.SelectAgent(features, "v1");
        var r2 = policy.SelectAgent(features, "v1");
        Assert.Equal(r1.AgentId, r2.AgentId);
        Assert.Equal(r1.Score, r2.Score);
    }
}

These tests illustrate key scenarios. In a real suite, we would also simulate SQL timeout or vector-search failure by mocking the data retrieval layer; the policy should then catch exceptions and fall back. But for core logic, the above covers selection, ties, cold starts, and determinism.

Mermaid Architecture and Sequence Diagrams

flowchart LR
    subgraph RouterService
        A[User Query] --> B[Router Agent Logic]
        B --> C[SQL Server]
        C --> D[QueryEmbeddings Table]
        C --> E[HistoricalQueries Table]
        C --> F[QueryAgentExecutions Table]
        C --> G[Agents Table]
        C --> H[AgentAvailability]
        D -->|vector search| C
        E -->|fetch neighbors| C
        F -->|aggregate to agents| C
        G -->|agent metadata| C
        H -->|availability filter| C
        B --> J[Selected Agent Call]
        B --> K[Decision Log]
    end
    J --> L[Specialized Agent Executes]

Sequence Diagram:

sequenceDiagram
    participant User
    participant RouterService
    participant Database
    participant AgentX

    User->>RouterService: Submit query
    RouterService->>Database: Compute embedding + VECTOR_SEARCH
    Database-->>RouterService: List of similar Query IDs
    RouterService->>Database: Aggregate outcomes JOIN QueryAgentExecutions
    Database-->>RouterService: Feature vectors per Agent
    RouterService->RouterService: Apply C# Scoring Policy
    RouterService->>AgentX: Route to best Agent
    RouterService->>DecisionLog: Record decision (hash, neighbors, features, choice)

These diagrams summarize the architecture and data flow: the router service queries the database for neighbors and aggregates, then calls the chosen agent.

Capacity Limits and Unresolved Questions

• Embedding Dimensions: High-dimensional vectors (e.g. 1536) increase storage and search cost. We assume SQL can handle this (it stores vectors as floats). If embeddings grow very large, performance may drop.
• Number of Neighbors: Choosing K too large (hundreds) can slow the join stage. We assume K ~50–100.
• Database Size: We targeted 10M queries, 50M edges. Larger (100M+) may require aggressive partitioning or dedicated analytics DB.
• Plan Stability: We must guard against parameter sniffing on the TOP K. The Query Store plan may change if K or filters vary widely.
• Vector Index Read-Only: The current vector index makes the table read-only. We assume this is acceptable (embedding table is append-only anyway). Future releases may lift this.
• Changing Policies: When updating weights, ensure we version policies and can compare A/B results.
• Unresolved: The weight values and combination formula are domain-specific and need empirical tuning. We have not addressed multi-hop beyond one (we assume one-hop is sufficient given our problem statement). If deeper graph patterns become relevant, the relational approach might need extension (e.g. two-hop joins) but with complexity.
• Limits on Fallback: If vector search fails (service down) or SQL times out, the router should have a static fallback (e.g. round-robin or default agent). Designing this reliably is left as future work.

Conclusion: This design is grounded in recent research and current SQL Server capabilities. It avoids unproven custom GNN systems, instead using proven SQL features and deterministic policy engineering. The deliverables include the schema, T-SQL, C# code, benchmarks, and all documentation to implement and evaluate this routing engine in production.

Sources: Microsoft SQL Server documentation, AI agent-routing tutorials, Stanford RelBench, Redgate blog on vector search, IBM on collaborative filtering, and the FAF GNN research. These informed the design, performance claims, and comparisons.