Placing text labels on a dense map is a hard combinatorial problem. Every label claims space its neighbors might need, and even simple versions of the problem are NP-complete. A recent study turned the job over to fine-tuned large language models (LLMs), which predict pixel coordinates for each landmark from text. Their placements track human-looking cartographic choices better than rule engines do. But the approach has three costs: a 9–14B-parameter model is run for every label, nothing prevents overlapping labels, and giving the model its neighbors' positions made its placements worse, not better.
We propose to split the work. A combinatorial solver handles the collisions and guarantees an overlap-free layout. The language model is consulted only for its judgment of which candidate position suits a given landmark, and only for landmarks whose placement is actually contested by neighbors and that a cheap learned scorer cannot confidently score. The question we want to answer is empirical and sharp: how much of the LLM's placement quality survives when its calls are cut by an order of magnitude, if the calls go to the collision hotspots of the map?
Core Claim
Label placement has a natural structure that generic LLM cost-cutting ignores. Candidate label positions form a conflict graph: each possible position is a node, and an edge joins two positions whose boxes overlap. Choosing a legible, non-overlapping layout means choosing a high-weight independent set, meaning a set of nodes with no edges between them.
Most landmarks sit in small, uncontested pieces of this graph, where any sensible scorer picks the same position. Semantic judgment only changes the final layout inside contested pieces, where the solver must decide which label yields. Our claim is that allocating LLM queries by conflict structure gives a much better quality-per-call trade-off than two alternatives: querying uniformly, or querying wherever a small model is uncertain regardless of geometry.
Asking the LLM about one landmark at a time also sidesteps the failure mode reported by Automated Label Placement on Maps via Large Language Models. That work instruction-tunes Llama, Gemma, Qwen and Phi models to emit coordinates. It found that adding neighbor descriptions to the prompt ("the Neighbor Paradox") hurt accuracy. We never ask the model to reason about neighbors; the solver does that.
Research Program
The pipeline
For each landmark we generate a fixed set of candidate boxes: the standard eight positions around the point, plus the position the fine-tuned LLM itself proposes. We build the rectangle conflict graph over these boxes.
Each candidate receives a score that estimates how appropriate it is for that landmark. The score comes from the cheapest source that is trusted, in this order:
- A geometry-only default (distance to point, standard position preference).
- A small "student" scorer. This is an MLP over landmark category, local geometry and a text embedding. It is trained online on the LLM's own scores, in the spirit of the teacher–student cache of Cache me if you Can. That paper serves confident queries from a k-NN or MLP student and falls back to GPT-4 otherwise. It saves 34% of calls on Banking77 at under 0.5% accuracy loss, but it works only on flat classification with no structure among queries.
- The LLM, prompted as a single-landmark scorer over the candidate list.
A weighted maximum-independent-set solver then selects at most one box per landmark. Because conflict components on real maps are small, it can solve most of them exactly with an integer program, and it falls back to greedy lookahead on large ones. For interactive panning and zooming it uses the dynamic independent-set maintenance of An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling.
The output is overlap-free by construction. This is a property the end-to-end LLM cannot offer, and one that the hardness results of The problem of compatible representatives and Geometric Systems of Disjoint Representatives tell us no heuristic gets optimally for free.
The router
The new ingredient is the router, which decides per landmark whether to pay for an LLM call. It escalates a landmark only when two conditions hold:
- its conflict component contains more than one landmark, and
- swapping the student's score for a plausible alternative would change the solver's chosen independent set.
We estimate the second condition cheaply by re-solving the small component with the student's top two scores perturbed.
This differs from SymRAG, which routes question-answering queries among symbolic, neural and hybrid paths using a per-query complexity score and system load. That paper reports that disabling routing inflates processing time by 169–1151%. Our router uses a signal SymRAG does not have: whether the decision can propagate through a graph of interacting outputs.
Theory as a lens, not a promise
Learning-augmented Maximum Independent Set shows that a membership oracle correct with probability $1/2+\epsilon$ yields an $O(\sqrt{\Delta}/\epsilon)$ approximation under persistent noise, where $\Delta$ is maximum degree. It does so by filtering each vertex through its neighbors' predictions, but it assumes every vertex is queried and ignores query cost. Our LLM at temperature zero is exactly a persistent-noise oracle. We will measure its empirical $\epsilon$ on MAPLE candidates and the $\Delta$ of real map conflict graphs. We will then test whether that paper's neighborhood filtering helps on top of our weighted solver. This makes the theory checkable in a real setting rather than claiming new bounds.
Compression as a secondary axis
Compression reduces the cost of each LLM call, while routing reduces how many calls are made. We will compose the router with a circuit-aware 3-bit oracle quantized in the style of Task-Circuit Quantization. That method keeps task-relevant weights at 16 bits while quantizing the rest, and recovers 96% of unquantized MMLU at 3.1 bits on Llama-3-8B-Instruct.
Scoring a discrete candidate list should be less fragile to low precision than emitting raw pixel coordinates. We test this directly by measuring coordinate RMSE and candidate-scoring accuracy under the same quantization.
Baselines
Naive geometric placement. The simplest reference is the standard eight-position model solved by unweighted greedy independent set with fixed position preferences. It uses no learning and no LLM calls. It anchors the latency floor and shows how much any semantic scoring is worth at all.
Classical metaheuristics. The second baseline is the strongest non-learned optimizer in the file: the discrete artificial bee colony method of A Hybrid Discrete Artificial Bee Colony Algorithm Based on Label Similarity, alongside the greedy lookahead of An Efficient Algorithm for Scatter Chart Labeling. Both run on the same candidate sets, with weights hand-tuned per landmark category on the MAPLE training split and a tuning budget matched to our student's training. No reported result found on Lacuna for either method on MAPLE, so we will produce those numbers ourselves.
End-to-end LLM (strongest existing method). The strongest existing method is the fine-tuned LLM of Shomer and Xu, run landmark by landmark with QLoRA. The file reports Phi-4 (14B) and Gemma 2 (9B) reaching RMSE as low as 28.4 pixels on MAPLE. We will reproduce this with the same models, prompt format (XML or List, which that paper found best) and retrieved guideline context. We then report its overlap rate, for which no reported result found on Lacuna, and its token and wall-clock cost.
A fair comparison uses:
- identical test regions,
- the same fine-tuned checkpoint as our oracle, and
- one GPU type for all latency measurements.
What counts as winning. We beat this baseline if we reach RMSE within about two pixels of the reproduced end-to-end number with zero overlaps, using at most 20% of its LLM calls.
Ablations. Three ablations isolate the key ingredient, and all three hold the call budget fixed:
- random allocation of LLM calls;
- entropy-only allocation, i.e. an OCaTS-style student-uncertainty gate with no conflict awareness;
- oracle-everywhere, i.e. the LLM scores every landmark before the solver runs, which gives the quality ceiling of the hybrid.
Why not just…?
Why not just use weighted MIS with hand-tuned category weights and no LLM? This is the most serious threat. MAPLE's ground truth is extracted from OpenStreetMap renderings, which are themselves produced by rule-based placement, so category rules may recover much of it. We therefore report the hand-weighted solver at matched tuning effort, and we break results out by category. Shomer and Xu found LLMs weakest on Leisure and Building. If hand weights match the hybrid everywhere, the honest conclusion is that MAPLE does not reward semantic judgment. We would then say so and restrict claims to the density-stress and guideline-following settings below.
Why not just train the small scorer on MAPLE labels and drop the LLM entirely? We absorb this alternative into the design rather than argue around it. A student trained directly on ground truth is the zero-LLM-call endpoint of our cost–quality curve. It will be reported as its own point, trained on ground truth rather than LLM scores. The proposal's claim survives only if a small budget of conflict-targeted calls moves that endpoint measurably. If it does not, the finding is still useful: the value of large models for this task would be demonstrably small.
Why not just compress the end-to-end LLM instead of routing? Circuit-aware quantization cuts per-call memory traffic by a constant factor (up to 8x per the TACQ results). It still issues one autoregressive generation per landmark and still permits overlaps. Routing attacks call count and the solver removes overlaps, so the two are complementary. The composed experiment in the program tests whether the savings multiply.
Why not just let the end-to-end LLM place labels and repair overlaps afterwards? Post-hoc repair is itself a label-placement problem. It discards the LLM's preferences exactly where labels collide, which is where they matter. We include "end-to-end LLM plus greedy nudge-to-free-space" as a baseline and expect it to lose RMSE in dense components.
Proposed Experiments
The primary benchmark is MAPLE (100 regions across Seattle, Los Angeles and San Francisco, over 1,200 landmarks). The metrics are:
- RMSE in pixels against ground truth,
- overlap rate,
- label yield (the fraction of landmarks placed),
- LLM calls and generated tokens per map, and
- end-to-end latency.
Because MAPLE regions average around a dozen landmarks, conflicts may be sparse. We will therefore build a density-scaled variant by rendering the same OpenStreetMap regions at wider extents and lower zoom. This multiplies landmarks per canvas and extracts ground truth with the same DBNet++ and ABINet pipeline.
Decisive check 1: the cost–quality curve. We sweep the LLM call budget from 0% to 100% of landmarks and plot RMSE against calls for conflict-aware, entropy-only and random allocation. The proposal is supported if conflict-aware allocation dominates the other two, with the gap widening as density grows. It is refuted if the curves coincide.
Decisive check 2: the Neighbor Paradox. We compare our per-landmark scoring against the neighbor-in-prompt variant of Shomer and Xu on the densest regions. This tests whether moving joint reasoning into the solver removes the degradation they reported.
Decisive check 3: the theory lens. We measure empirical $\epsilon$ and $\Delta$ for the LLM oracle and report whether neighborhood filtering from the learning-augmented MIS work changes yield. This tells us whether the theory's assumptions describe real maps.
Latency check. Finally, we time panning and zoom sequences using dynamic independent-set updates and count LLM calls per frame. This shows whether the hybrid can run interactively, which the end-to-end approach cannot.
References
- Automated Label Placement on Maps via Large Language Models
- Cache me if you Can: an Online Cost-aware Teacher-Student framework to Reduce the Calls to Large Language Models
- An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling
- The Problem of Compatible Representatives
- Geometric Systems of Disjoint Representatives
- SymRAG: Efficient Neuro-Symbolic Retrieval Through Adaptive Query Routing
- Learning-Augmented Maximum Independent Set
- Task-Circuit Quantization: Leveraging Knowledge Localization and Interpretability for Compression
- A Hybrid Discrete Artificial Bee Colony Algorithm Based on Label Similarity for Solving Point-Feature Label Placement Problem
- An Efficient Algorithm for Scatter Chart Labeling